1、2 線性方程組的誤差分析 /* Error Analysis for Linear system of Equations */,求解 時，A 和 的誤差對解 有何影響？, 設(shè) A 精確， 有誤差 ，得到的解為 ，即,絕對誤差放大因子,又,相對誤差放大因子,2 Error Analysis for ., 設(shè) 精確，A有誤差 ，得到的解為 ，即,Wait a minute Who said that ( I + A1 A ) is invertible?,(只要 A充分小，使得,大,2 Error Analysis for ., cond (A) 取決于A，與解題方法無關(guān)。,常用條件數(shù)有：,co

2、nd (A)1,cond (A),cond (A)2,特別地，若 A 對稱，則,條件數(shù)的性質(zhì)： 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 .,精確解為,A1 =,解：考察 A 的特征根,39206 1, 測試病態(tài)程度：,此時精確解為,2.0102 200%,2 Error Analysis for .,cond (H2) =,27,cond (H3) ,748,

3、cond (H6) =,2.9 106,cond (Hn) as n ,注：一般判斷矩陣是否病態(tài)，并不計算A1，而由經(jīng)驗得出。 行列式很大或很小（如某些行、列近似相關(guān)）； 元素間相差大數(shù)量級，且無規(guī)則； 主元消去過程中出現(xiàn)小主元； 特征值相差大數(shù)量級。,2 Error Analysis for ., 近似解的誤差估計及改善：,設(shè) 的近似解為 ，則一般有,cond (A), 改善方法：,Step 1:近似解,Step 2:,Step 3:,Step 4:,若 可被精確解出，則有 就是精確解了。,經(jīng)驗表明：若 A 不是非常病態(tài)（例如： ），則如此迭代可達到機器精度；但若 A 病態(tài)，則此算法也不能改

4、進。,HW: p.66 #2, #4, #5,3 Jacobi 法和 Gauss - Seidel 法 /* Jacobi 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. Step 1 Set k = 1; Step 2 While ( k Nmax) do steps 3-6 Step 3 F

5、or i = 1, , n Set ; /* compute xk */ Step 4 If then Output (X ); STOP; /* successful */ Step 5 For i = 1, , n Set X 0 = X ; /* update X0 */ Step 6 Set k +; Step 7 Output (Maximum number of iterations exceeded); STOP. /* unsuccessful */,What if aii = 0?,迭代過程中，A 的元素 不改變，故可以事先調(diào)整好 A 使得 aii 0，否則 A不可逆。,必須

6、等X(k)完全計算 好了才能計算X(k+1)，因此 需要兩組向量存儲。,A bit wasteful, isnt it?,3 Jacobi & Gauss-Seidel Iterative Methods, Gauss - Seidel Iterative Method, ,只存一組向量即可。,寫成矩陣形式：,Gauss-Seidel 迭代陣,3 Jacobi & Gauss-Seidel Iterative Methods,注：二種方法都存在收斂性問題。 有例子表明：Gauss-Seidel法收斂時，Jacobi法可能不收斂；而Jacobi法收斂時， Gauss-Seidel法也可能不收斂。,p.76 #2 給出了例子。 收斂性