解線性方程組迭代方法

1、關(guān)于解線性方程組的迭代方法第一張，PPT共四十頁，創(chuàng)作于2022年6月 定義:設(shè)xk是Rn上的向量序列， 又設(shè)x*（x1*，x 2*,，x n*)是Rn上的向量. 則稱向量x*是向量序列x k的極限 ，若一個向量序列有極限,稱這個向量序列是收斂的.向量序列的極限如果向量序列x k收斂于向量x*的充分必要定理1（i =1,2,n）條件是第二張，PPT共四十頁，創(chuàng)作于2022年6月矩陣序列的極限定義: 設(shè)Ak是 上的矩陣序列.若存在矩陣 則稱矩陣A 是矩陣序列A k的極限，記為若一個矩陣序列有極限,稱這個矩陣序列是收斂的.使得矩陣序列A k收斂于矩陣A 的充分必要定理2（i, j =1,2,n）條

2、件是這里第三張，PPT共四十頁，創(chuàng)作于2022年6月證：依次取 x 為 ，其中則所以定理3的充要條件是對任何xRn，有設(shè)矩陣定理4，則 的充要條件是( A) 0, 記 xTLTx = a , 則有xTLTx =xT(D L)xxTAx=xT(D L LT)x=p a a =p 2a 0所以第二十六張，PPT共四十頁，創(chuàng)作于2022年6月所以, 迭代矩陣BG-S的譜半徑(BG-S) 1,從而當方程組 Ax=b的系數(shù)矩陣A 是實對稱正定矩陣時,G-S 迭代法收斂Remark:G-S迭代法的計算過程比Jacobi迭代法更簡單。計算過程中只需用一個一維數(shù)組存放迭代向量。G-S迭代不一定比Jacobi迭

3、代收斂快。Jacobi迭代和G-S迭代的收斂范圍并不一致，即Jacobi迭代收斂，G-S迭代不一定收斂，反之亦然。前面的定理1、定理2對于Jacobi迭代和G-S迭代都適用。第二十七張，PPT共四十頁，創(chuàng)作于2022年6月(i=1,2, n; k = 1,2,3, )四 超松馳(SOR)迭代法G-S迭代格式第二十八張，PPT共四十頁，創(chuàng)作于2022年6月定理7. 若A 是對稱正定矩陣,則當02時SOR迭代法解方程組 A x = b 是收斂的定理8. 若A 是嚴格對角占優(yōu)矩陣,則當01時SOR迭代法解方程組 A x = b 是收斂的.迭代矩陣：第二十九張，PPT共四十頁，創(chuàng)作于2022年6月例3

4、：用松弛迭代法解方程組：解：松弛法迭代格式為：第三十張，PPT共四十頁，創(chuàng)作于2022年6月 設(shè)x, yR n, 記 ( x , y) = xT y ( x, y ) = ( y, x ); ( t x, y ) = t ( x, y); ( x+ y, z ) = ( x, z ) + ( y, z ); ( x, x) 0, 且( x, x) = 0 x = 0;I 方程組問題: Ax = bII 極值問題: 設(shè) A 是n 階對稱陣 ( Ax, y ) = ( x, Ay ) ; ( Ax，x ) 0, 且( Ax, x) = 0 x = 0 五 最速下降法第三十一張，PPT共四十頁，創(chuàng)作

5、于2022年6月定理9. 設(shè)A =( aij )nn為實對稱正定矩陣, b , xR n, 則 x 使二次函數(shù) 取極小值 x 是線性方程組 Ax = b的解。 證明: (1) u 是方程組 Ax = b 的解 Au b=0. 任意 xR n, 令y = x u (Ay, y) 0(2) 設(shè) u 使 f (x) 取極小值. 任取非零 xR n, 任意 tR 第三十二張，PPT共四十頁，創(chuàng)作于2022年6月令g(t) = f ( u + t x), 當t=0時, g(0)= f (u)達到極小值, 所以 , 即( Au b , x ) = 0 Au b = 0所以, u 是方程組 Ax = b 的

6、解.最速下降法基本思想：從初值點x (0) 出發(fā),以負梯度方向 r 為搜索方向，選擇步長t1, 得 x (1) = x (0) + t1r, 求函數(shù) f (x) 極小值在 x 處，梯度方向是 f (x) 增長最快方向；負梯度方向是 f (x) 下降最快方向。第三十三張，PPT共四十頁，創(chuàng)作于2022年6月梯度:由f (x)的表達式，易知對于任意x (0) Rn, f (x)在 x (0)處的負梯度方向為記 r (0) = b- Ax (0)，即r (0)的方向就是負梯度的方向，也是 Ax = b 的對應(yīng)于x (0)的殘向量。若r (0) =0，則x (0)即為Ax = b的解，若r (0) 0

7、 ，則從x (0)出發(fā)，沿r (0)方向的x為：其中為參數(shù)，這里x 表明在 r(0)方向上以 為步長，對x(0) 做了一次修正，為確定 ，使函數(shù)第三十四張，PPT共四十頁，創(chuàng)作于2022年6月取最小值。令解得：又所以，= 0 時f (x)取最小值，令x (1) =x (0) +0 r (0)，從x (1)出發(fā)沿f (x)在x (1)處的負梯度方向r (1) = b-Ax (1)上求使 f (x)的值最小的點，記為x (2)，則第三十五張，PPT共四十頁，創(chuàng)作于2022年6月x (1) = x (0) +0 r (0)繼續(xù)下去則得迭代格式： 第三十六張，PPT共四十頁，創(chuàng)作于2022年6月結(jié)論1

8、：第m+1次和第m 次負梯度方向是正交的，即 (r (m+1) , r (m) ) = 0 結(jié)論2：最速下降法有誤差估計式 這里1 和n 為A 的最大和最小特征值，|A 定義為注：由結(jié)論2可以看出，當1 和n 相差較大時，最速下降法收斂緩慢。第三十七張，PPT共四十頁，創(chuàng)作于2022年6月六 共軛梯度法A是n階對稱正定矩陣,非零向量 p1, p2Rn n個向量 p1, p2 , pm 共軛概念:(Api , pj )=0(ij; i, j = 1,2,m )非零向量 p1, p2 , pm Rn p1, p2 , pm 關(guān)于A共軛 p1, p2 , pm 線性無關(guān)(Ap1, p2)=0 兩個向量 p1, p2 共軛:第三十八張，PPT共四十頁，創(chuàng)作于2022年6月共軛梯度法基本思想：由最速下降法中的下降向量r (k) 構(gòu)造出關(guān)于A共軛向量組 p (k) ，并以 p (k)作為下降方向來構(gòu)造迭代算法。定理10. A是n階對稱正定矩陣, p(1), p(2) , p(n) 是關(guān)于A共軛的向量組, 任取 x (0)R n , 計算tk = ( b Ax (k -1) , p(k) / (A p(k