中山大学-数值分析heyheyhey.docxVIP

数值分析期中复习 By 11软件工程胡震heyheyhey 注：以下概念均以李庆阳教材的定义为准 误差分析 主要概念：绝对误差(Absolute Error)、相对误差(Relative Error)、有效数字(Significant Digits)、截断误差(Truncation Error)、舍入误差(Round off Error)、精度损失(Loss of Significance) 绝对误差：Ep = ?p – p 相对误差：Rp = Ep / p 阶段误差：实际运算只能完成有限项或有限步运算，因此要将有些需用极限或无穷过程进行的运算有限化，对无穷过程进行截断，这样产生的误差称为截断误差。 求有效数字位数：若近似值?x的误差限是某一位的半个单位，该位到?x的第一位非零数字共有n位，就说?x有n位有效数字。接下来将用几个例子来说明： x = 2 ?x = 2.7182 Ex = x - ?x = 0 0.0005。从5开始向前一直数到?x的第一个不为0的数字。个数即为有效数字位数。因此有4位有效数字。 y = 0.000068, ?y = 0.00006 Ey = y - ?y = 0.000008 0.00005，此例中有效数字位数为0 精度丢失： 避免非常接近的两个数相减 稳定性 四则运算的误差传播（Propagation of Error） 加法：p + q = (Ep +?p) + (Eq + ?q) = ?p + ?q + Ep + Eq 乘法：pq = (Ep +?p)(Eq + ?q) = ?p?q + ?pEq + ?qEp + Ep Eq Rpq = (pq - ?p?q) / pq = Ep /p + Eq /q + EpEq/pq ≈ Ep /p + Eq /q = Rp + Rq 除法： 求解非线性方程 不动点迭代 : 不动点定义 若y = g(x)是一个连续函数，是一个不动点迭代序列，若 ，则p是y = g(x)的一个不动点。 不动点定理 假设g∈C[a, b]， 并且满足以下两个条件： g是[a, b] 到[a, b]上的映射（说明了不定点存在） g是一个压缩映射（说明了不动点的唯一性） 事前误差估计压缩映射的定义：存在一个正实数K，使得对于任意x∈(a, b)，都有成立 事前误差估计 事后误差估计 事后误差估计 说明：可能很多人看了很多概念，还是不明白这些和求解非线性方程组有什么关系。 其实思路大概是这样的：首先构造一个合适的迭代格式，由f(x) = 0变为g(x) = x的形式，然后找到一个闭区间[a, b]，使得g(x)在[a, b]是一个压缩映射，于是对于[a, b]中的任何一个初值， 不动点迭代一定收敛于方程的根。用不动点法求的跟只是一个近似值。需要注意的一点是在做题之前，先判断能否使用不动点迭代来求解方程。先求出不动点，只有吸性不动点才能使用不动点迭代来求解方程。 e.g 求解方程x3 – x – 1 = 0 解：首先判断可以使用不动点迭代 构造迭代格式：x = 3x+ 可以验证在[1, 2]上，h(x)是一个压缩映射。1≤32 = h(1) ≤h(x)≤h(2)≤3 |h(x)| = |1/3 * 13 因此对于[1, 2]中任何一个初值，不动点迭代一定收敛于方程的根。 ps : 试位法 牛顿迭代法 基本形式：pk = g(pk-1) = pk-1 – f(Pk-1) / f(pk-1) 使用条件： 且存在p∈[a, b],f(p) = 0以及f(p) ≠0 牛顿迭代法与不动点迭代法有很多的相似性，可以对比着来掌握。 特殊的牛顿迭代法：求A, pk = （pk-1 +Ａ／pk-1）/ 2 重要定理： g(x)可以表示成(x - p)k h(x)的形式。 关于收敛阶数的说明： 若p为单重根(f(p) != 0)，则收敛为二阶 若p为多重根,k阶的（f(p) = 0, f(2)(p) = 0, … , f(k)(p) != 0） En+1 ≈ |(k-1)/k| * |En| 对于多重根的情况，可以对牛顿迭代法进行改良 方法： 弦割法收敛速度为1.618^2 ＞２ 求解线性方程组（预测考试会有两题出现） 高斯消去法（Gauss Elimination） 主要是做初等行变换，然后回代，称为向前消去（Forward Elimination ） 缺陷：初等行变换过程中，可能出现大数除小数的情况，因此需要优化，要使用Partial Pivoting 每次要将最大的先导元素放在上面，如上例：－０.００１＜２．５，因此交换第二三行。 向前消去法的复杂度：（ｎ３－ｎ）／３ 三个范数 范数三个性质：a.