解线性方程组迭代方法

1、关于解线性方程组的迭代方法第一张，PPT共四十页，创作于2022年6月 定义:设xk是Rn上的向量序列， 又设x*（x1*，x 2*,，x n*)是Rn上的向量. 则称向量x*是向量序列x k的极限 ，若一个向量序列有极限,称这个向量序列是收敛的.向量序列的极限如果向量序列x k收敛于向量x*的充分必要定理1（i =1,2,n）条件是第二张，PPT共四十页，创作于2022年6月矩阵序列的极限定义: 设Ak是 上的矩阵序列.若存在矩阵 则称矩阵A 是矩阵序列A k的极限，记为若一个矩阵序列有极限,称这个矩阵序列是收敛的.使得矩阵序列A k收敛于矩阵A 的充分必要定理2（i, j =1,2,n）条

2、件是这里第三张，PPT共四十页，创作于2022年6月证：依次取 x 为 ，其中则所以定理3的充要条件是对任何xRn，有设矩阵定理4，则 的充要条件是( A) 0, 记 xTLTx = a , 则有xTLTx =xT(D L)xxTAx=xT(D L LT)x=p a a =p 2a 0所以第二十六张，PPT共四十页，创作于2022年6月所以, 迭代矩阵BG-S的谱半径(BG-S) 1,从而当方程组 Ax=b的系数矩阵A 是实对称正定矩阵时,G-S 迭代法收敛Remark:G-S迭代法的计算过程比Jacobi迭代法更简单。计算过程中只需用一个一维数组存放迭代向量。G-S迭代不一定比Jacobi迭

3、代收敛快。Jacobi迭代和G-S迭代的收敛范围并不一致，即Jacobi迭代收敛，G-S迭代不一定收敛，反之亦然。前面的定理1、定理2对于Jacobi迭代和G-S迭代都适用。第二十七张，PPT共四十页，创作于2022年6月(i=1,2, n; k = 1,2,3, )四 超松驰(SOR)迭代法G-S迭代格式第二十八张，PPT共四十页，创作于2022年6月定理7. 若A 是对称正定矩阵,则当02时SOR迭代法解方程组 A x = b 是收敛的定理8. 若A 是严格对角占优矩阵,则当01时SOR迭代法解方程组 A x = b 是收敛的.迭代矩阵：第二十九张，PPT共四十页，创作于2022年6月例3

4、：用松弛迭代法解方程组：解：松弛法迭代格式为：第三十张，PPT共四十页，创作于2022年6月 设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 极值问题: 设 A 是n 阶对称阵 ( Ax, y ) = ( x, Ay ) ; ( Ax，x ) 0, 且( Ax, x) = 0 x = 0 五 最速下降法第三十一张，PPT共四十页，创作

5、于2022年6月定理9. 设A =( aij )nn为实对称正定矩阵, b , xR n, 则 x 使二次函数 取极小值 x 是线性方程组 Ax = b的解。 证明: (1) u 是方程组 Ax = b 的解 Au b=0. 任意 xR n, 令y = x u (Ay, y) 0(2) 设 u 使 f (x) 取极小值. 任取非零 xR n, 任意 tR 第三十二张，PPT共四十页，创作于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) 出发,以负梯度方向 r 为搜索方向，选择步长t1, 得 x (1) = x (0) + t1r, 求函数 f (x) 极小值在 x 处，梯度方向是 f (x) 增长最快方向；负梯度方向是 f (x) 下降最快方向。第三十三张，PPT共四十页，创作于2022年6月梯度:由f (x)的表达式，易知对于任意x (0) Rn, f (x)在 x (0)处的负梯度方向为记 r (0) = b- Ax (0)，即r (0)的方向就是负梯度的方向，也是 Ax = b 的对应于x (0)的残向量。若r (0) =0，则x (0)即为Ax = b的解，若r (0) 0

7、 ，则从x (0)出发，沿r (0)方向的x为：其中为参数，这里x 表明在 r(0)方向上以 为步长，对x(0) 做了一次修正，为确定 ，使函数第三十四张，PPT共四十页，创作于2022年6月取最小值。令解得：又所以，= 0 时f (x)取最小值，令x (1) =x (0) +0 r (0)，从x (1)出发沿f (x)在x (1)处的负梯度方向r (1) = b-Ax (1)上求使 f (x)的值最小的点，记为x (2)，则第三十五张，PPT共四十页，创作于2022年6月x (1) = x (0) +0 r (0)继续下去则得迭代格式： 第三十六张，PPT共四十页，创作于2022年6月结论1

8、：第m+1次和第m 次负梯度方向是正交的，即 (r (m+1) , r (m) ) = 0 结论2：最速下降法有误差估计式 这里1 和n 为A 的最大和最小特征值，|A 定义为注：由结论2可以看出，当1 和n 相差较大时，最速下降法收敛缓慢。第三十七张，PPT共四十页，创作于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 关于A共轭 p1, p2 , pm 线性无关(Ap1, p2)=0 两个向量 p1, p2 共轭:第三十八张，PPT共四十页，创作于2022年6月共轭梯度法基本思想：由最速下降法中的下降向量r (k) 构造出关于A共轭向量组 p (k) ，并以 p (k)作为下降方向来构造迭代算法。定理10. A是n阶对称正定矩阵, p(1), p(2) , p(n) 是关于A共轭的向量组, 任取 x (0)R n , 计算tk = ( b Ax (k -1) , p(k) / (A p(k