第4章解线性方程组的迭代法2.pptVIP

* §2 线性方程组的误差分析 /* Error Analysis for Linear system of Equations */ 求解 时，A 和 的误差对解 有何影响？ ? 设 A 精确， 有误差　 ，得到的解为 ，即 绝对误差放大因子 又 相对误差放大因子 §2 Error Analysis for . ? 设 精确，A有误差 　 ，得到的解为 ，即 Wait a minute … Who said that ( I + A?1? A ) is invertible? (只要? A充分小，使得 是关键 的误差放大因子，称为 A的条件数，记为cond (A) , 越 则 A 越病态， 难得准确解。 大 §2 Error Analysis for . 注: ? cond (A) 的具体大小与 || · || 的取法有关，但相对大小一致。 ? cond (A) 取决于A，与解题方法无关。 ? 常用条件数有： cond (A)1 cond (A)? cond (A)2 特别地，若 A 对称，则 条件数的性质： ? A可逆，则 cond (A)p ? 1； ? A可逆，? ? R 则 cond (? A) = cond (A) ； ? A正交，则 cond (A)2=1； ? A可逆，R正交，则 cond (RA)2 = cond (AR)2 = cond (A)2 。 §2 Error Analysis for . 精确解为 例： 计算cond (A)2 。 A?1 = 解：考察 A 的特征根 39206 1 ? 测试病态程度： 给　一个扰动 ，其相对误差为 此时精确解为 2.0102 200% §2 Error Analysis for . 例：Hilbert 阵 cond (H2)? = 27 cond (H3)? ? 748 cond (H6)? = 2.9 ? 106 cond (Hn)?? ? as n ? ? 注：一般判断矩阵是否病态，并不计算A?1，而由经验得出。 ? 行列式很大或很小（如某些行、列近似相关）； ? 元素间相差大数量级，且无规则； ? 主元消去过程中出现小主元； ? 特征值相差大数量级。 §2 Error Analysis for . ? 近似解的误差估计及改善： 设　　 的近似解为　 ，则一般有 cond (A) 误差上限 ? 改善方法： Step 1:　　　　　近似解 Step 2: Step 3: Step 4: 若　 可被精确解出，则有 就是精确解了。 经验表明：若 A 不是非常病态（例如： ），则如此迭代可达到机器精度；但若 A 病态，则此算法也不能改进。 HW: p.66 #2, #4, #5 §3 Jacobi 法和 Gauss - Seidel 法 /* Jacobi Gauss-Seidel Iterative Methods */ ? Jacobi Iterative Method 写成矩阵形式： A = L U D B Jacobi 迭代阵 §3 Jacobi Gauss-Seidel Iterative Methods Algorithm: Jacobi Iterative Method Solve given an initial approximation . Input: the number of equations and unknowns n; the matrix entries a[ ][ ]; the entries b[ ]; the initial approximation X0[ ]; tolerance TOL; maximum number of iterations Nmax. Output: approximate solution X[ ] or a message of failure. St