《数值计算》课程教学课件（讲稿）第6章 线性方程组的迭代解法（2/2）

x(1)求Ax=b的近似解为r(1) = b-Ax(1)求x的剩余向量z(1)修正向量求Az=r(1)的近似解为x(2) = x(1) + z(得Ax=b的改进解用双精r(2) = b - Ax(2)求x(2)的剩余向量度求解z(2)解Az=r(2)的近似解为x(3) = x(2) + z(2)得Ax=b的改进解Iz(k)ε 时依此类推，直到得到满足精度要求的解迭代终止返回

上页 下页 返回 用双精 度求解 (1) 求Ax  b的近似解为 x (1) (1) (1) 求x 的剩余向量 r  b  Ax (1) (1) 求Az  r 的近似解为 z (2) (1) (1) 得Ax  b的改进解 x  x z (2) (2) (2) 求x 的剩余向量 r  b  Ax (2) (2) 解Az  r 的近似解为 z (3) (2) (2) 得Ax  b的改进解 x  x  z 依此类推,直到得到满足精度要求的解 修正向量 迭代终止 |z (k ) |  时

二、选代法的收敛性设解线性方程组的选代格式x(k+1) = Bx(k) + f而方程组的精确解为*,则x*=Bx*+f两式相减，得x(k+1) -x*= Bx(k) -Bx* = B(x(k) -x*)令α(k) =x(k)-x*k = 0,1,2,...上页下页返回

上页 下页 返回 二、迭代法的收敛性 设解线性方程组的迭代格式 x Bx f k k   ( 1) ( ) 而方程组的精确解为x*,则 x*  Bx* f 两式相减,得 * * ( 1) ( ) x x Bx Bx k k     ( *) ( ) B x x k   * ( ) ( ) x x k k 令   k  0,1,2, 

则e(k+1) = Be(k) = B"g(k-1)" =... = Bk+lg(0)注意e()=x(0)-x＊为非零常数向量因此选代法收敛的充要条件lime(k+1) = lim(x(k+1)k→00k-→>80等价于对任何算子范数有limBk可转变为A-A→0当k→0k-→0定义Rnxn设: A=(ag)nn A, =(aft")E福lima)=a, 对所有 1<ij≤n 成立。上真lim Ak=A是指k-00k→8下页返圆

上页 下页 返回 则 (k 1) (k)   B  2 ( 1)  k B   1 (0)    k B 注意 (0)  x (0)  x*为非零常数向量 因此迭代法收敛的充要条件 lim lim( * ) ( 1) ( 1) x x k k k k         0 lim 0 1    k k 可转变为 B 定义 设： ( ) , ( ) . ( ) n n n n k A aij n n Ak aij R       Ak A k    lim 是指 ij k ij k a  a   ( ) lim 对所有 1 i, j  n 成立。 等价于对 任何算子范数有 || Ak  A||  0 当 k  

定理1设x=Bx+存在唯一解，则从任意x()出发，迭代x(k+1)=Bx(k)+ 收敛 B →0II Bkx II>0max证明：Bk→0← Bk→0←I x IIX+0Bx→0对任意非零向量x成立一Bx0对任意非零向量x成立一从任意出发=…6，则g(k)=Bte(0)（岁k第在(k)收敛上页下页返圆

上页 下页 返回 || B x ||  0 k  对任意非零向量 x 成立  定理1 设 x Bx f      存在唯一解，则从任意 x (0) 出发，  迭代 x Bx f k k      ( 1) ( ) 收敛   0 k B 证明： Bk  0 || Bk ||  0 0 || || || || max 0   x B x k x     “”：对任意非零向量 x 有  || || 0 || || || ||  k  k B x B x  “”：取  则 i T x (0.1.0) ( )   第 i 位 0 bij (k )  0   B k x  对任意非零向量 x 成立  (0) x  * (0) (0) x x   从任意 出发， 记    ，则 0 ( ) (0)   k  B k   （当 k  ） { } (k ) x  收敛

定理2Bk→0 p(B)<1证明：对A做Jordan分解，有p-"AP=其中2.1J.=n,=n，a,为A的特征值。Ci=1AAI:xnS2则有D-P-APD=D:SR易证:II A ll=II D-p-I APDIl= max(I2, I+)= p(A)+i≤i是由IxIl,=Il(PD)-xIl, 导出的算子范数。上页所以只要取8<，就有AIl<p(A)+。下页返圆

上页 下页 返回 定理2 Bk  0   ( B )  1 证明：“” 若  是 B 的特征值, 则 k 是 Bk 的特征值。 则 [ (B)] k = [ max |  | ]k = |  m k |   ( Bk )  || Bk ||  0   (B) < 1  “” 首先需要一个引理 对任意  > 0, 存在算子范数|| · || 使得 || A ||   (A)   。 由  (B) < 1 可知存在算子范数|| · || 使得 || B || < 1。 || Bk ||  || B ||k  0 当 k   Bk  0 证明：对A 做 Jordan 分解，有 ，其中 ， ， i 为 A 的 特征值。 令 ，则有 易证： 是由 导出的算子范数。 所以只要取 <  ，就有|| A || <  (A)   。             r J J P AP . 1 1 ni ni i i Ji               1 1 0   r i ni n 1                  1 2 1 n D                           r r D P APD         1 1 1 1              || || || || max( | | ) ( ) 1 1 1 1 A D P APD i A i r 1 1 || x || || (PD) x || v    