【文章內(nèi)容簡介】 線性方程組解法 ? 矩陣 的特征值 的絕對值最大值稱為矩陣 A的譜半徑，即 167。 迭代法的收斂性 nnR ??A, 1 , 2 , ..,i in? ?1( ) m a x iin?????A? 定理 (迭代法基本定理 )：設(shè)有方程組x=Bx+f，對于任意初始向量 x0及任意 f，迭代公式 xk+1=Bxk+f收斂的充要條件是 ( ) 1? ?B167。 迭代法的收斂性 ? 定理 (迭代收斂的充分條件 )：設(shè)有迭代式 xk+1=Bxk+f，如果 ，則對于任意初始向量 x0，這個迭代過程收斂于方程組 x=Bx+f的唯一解 x*，并且有事后估計 1q??B*1 11k k kq?? ? ??x x x x以及事前估計 * 1 01kk qq? ? ??x x x x167。 迭代法的收斂性 ?定義：如果對于方陣 ，有 nn?A1, 1 , 2 , .. .,nii ijj j ia a i n?????則稱方陣 對角占優(yōu) 。 ? 定理：如果方程組 Ax=b的系數(shù)陣 對角占優(yōu) ，則方程組有唯一解且對任意初始向量 x0雅可比迭代 和 高斯－塞德爾迭代都收斂于真解。 167。 迭代法的收斂性 【 思考題 】 如何對方程組進(jìn)行調(diào)整，使用 GaussSeidel迭代格式求解時收斂？ 12131 2 3879897xxxxx x x? ? ???? ? ???? ? ??? 定理：如果方程組 Ax=b的系數(shù)陣 對稱正定 ，則方程組有唯一解且對任意初始向量 x0高斯－塞德爾迭代 收斂于真解。 167。 迭代法的收斂性 ? Jacobi迭代格式的收斂性 167。 迭代法的收斂性 Jacobi迭代矩陣 1 ()?? ? ?J D U L 特征方程 0? ??IJ1 ( ) 0? ?? ? ?I D U L1 ( ) 0?? ? ? ? ?D D U L167。 迭代法的收斂性 由于 1 0? ?D0? ? ? ?D U L所以 注意到 ? ? ?A D U L所以， 將 A的對角線元素乘以 后取行列式，令其等于零，就是 Jacobi迭代矩陣的特征方程 。 ?? 例 討論用 Jacobi迭代格式解方程組的收斂性。 167。 迭代法的收斂性 1238 1 1 12 10 1 41 1 5 3xxx?? ? ? ? ? ?? ? ? ? ? ???? ? ? ? ? ?? ? ? ? ? ???? ? ? ? ? ?解： Jacobi迭代矩陣的特征方程為 8 1 12 10 1 01 1 5???????展開得 167。 迭代法的收斂性 Jacobi迭代格式收斂。 3400 12 3 0??? ? ?解得 1 2 , 30 .1 4 6 0 8 4 , 0 .0 7 3 0 4 1 0 .2 1 4 4 8 7 i??? ? ? ?1 2 3( ) m a x{ , , } 0. 22 65 8 1? ? ? ?? ? ?B? GaussSeidel迭代格式的收斂性 167。 迭代法的收斂性 GaussSeidel迭代矩陣 1() ?? ? ?G D L U 特征方程 0? ??IG1( ) 0? ?? ? ?I D L U1( ) ( ) 0??? ? ? ? ?D L D L U167。 迭代法的收斂性 由于 1( ) 0???DL( ) 0? ? ? ?D L U所以 注意到 ? ? ?A D U L所以， 將 A的對角線以下元素乘以 后取行列式，令其等于零，就是 GaussSeidel迭代矩陣的特征方程 。 ?167。 迭代法的收斂性 【 思考題 】 GaussSeidel迭代矩陣 1() ?? ? ?G D L U至少有 1個特征值為零，為什么？ ? 例 討論用GaussSeidel迭代格式解方程組的收斂性。 167。 迭代法的收斂性 1238 1 1 12 10 1 41 1 5 3xxx?? ? ? ? ? ?? ? ? ? ? ???? ? ? ? ? ?? ? ? ? ? ???? ? ? ? ? ?解： GaussSeidel迭代矩陣特征方程為 8 1 12 10 1 05???? ? ?????展開得 167。 迭代法的收斂性 GaussSeidel迭代格式收斂。 2( 400 10 1 ) 0? ? ?? ? ?解得 1 2 , 30 , ( 1 17 ) / 80??? ? ? ?1 2 3( ) m a x{ , , } 0. 06 40 38 1? ? ? ?? ? ?G167。 迭代法的收斂性 ?作業(yè)： (1) 寫出 下面方程組的 Jacobi迭代格式和 GaussSeidel迭代格式的算法 (2) 討論它們的收斂性。 1232 1 1 11 1 1 11 1 2 1xxx?? ? ? ? ? ?? ? ? ? ? ??? ? ? ? ? ?? ? ? ? ? ??? ? ? ? ? ?167。 (Gauss Elimination) 第三章 線性方程組解法 ? 高斯消去法是最古老的數(shù)值方法之一，現(xiàn)在仍然是一個很有用的方法，它在計算機上容易實現(xiàn)。 167。 高斯消去法 ? 其基本思想是在各個方程之間進(jìn)行乘法和加減運算，逐步消去方程中的未知數(shù)。它分為 消去 和 回代 兩個過程。 ?A x b 給定線性方程組 167。 高斯消去法 11 12 1 1 121 22 2 2 212......... ... ... ... ... ......nnn n nn n na a a x ba a a x ba a a x b? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ??? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?第一步消元，令 ，用 乘第一個方程再加到第 i個方程上作為第 i個新方程，消去 x1的項，變?yōu)? 1 1 11/ , 2 , 3 , .. .,iim a a i n??1im?逐次進(jìn)行同樣過程，最后，經(jīng)過 n1次消元，得到： 167。 高斯消去法 11 12 1 1 1( 1 ) ( 1 ) ( 1 )22 2 2 2( 1 ) ( 1 ) ( 1 )2...0 ...... ... ... ... ... ...0 ...nnn nn n na a a x ba a x ba a x b? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ??? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?以上這些步驟叫 消元過程 。 167。 高斯消去法 11 12 1 1 1( 1 ) ( 1 ) ( 1 )22 2 2 2( 1 ) ( 1 )...0 ...0 ... ... ... ... ...0 0 ...nnnnnn n na a a x ba a x ba x b??? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ??? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?然后，從第 n個方程開始，依次解出 xn, xn1, … x1 167。 高斯消去法 ( 1 ) ( 1 )/nnn n nnx b a???( 1 ) ( 1 ) ( 1 )1( ) /ni i ii i ij j iijix b a x a? ? ????? ?1 , ... , 1in???高斯消去法的計算量 167。 高斯消去法 ? 消去過程的計算量。第一步計算乘數(shù)mi1,(i=2,3,…, n)需要 i1次除法運算，計算aij(2)(i,j=2,3,…, n)需要 (i1)2次乘法運算以及 (i1)2次加減法運算。 利用求和公式 211( 1 ) / 2 , ( 1 ) ( 2 1 ) / 6 , 1nniii n n i n n n n??? ? ? ? ? ??? 得到 167。 高斯消去法 第 k步 加減法次數(shù) 乘法次數(shù) 除法次數(shù) 1 (n1)2 (n1)2 n1 2 (n2)2 (n2)2 n2 … … … … N1 1 1 1 合計 n(n1)(2n1)/6 n(n1)(2n1)/6 n(n1)/2 于是 消去過程 乘除法次數(shù)為 2( 1 ) / 3nn ?消去過程 加減法次數(shù)為 ( 1 ) ( 2 1 ) / 6n n n??167。 高斯消去法 ?計算 b(n1)的計算量 ( 1 ) ( 2) ... 2 1 ( 1 ) / 2n n n n? ? ? ? ? ? ? ? 乘除法次數(shù)為 加減法次數(shù)為 ( 1 ) / 2nn ?167。 高斯消去法 ?回代計算量 乘除法次數(shù)為 加減法次數(shù)為 ( 1 ) / 2nn ?1 2 ... ( 2)