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

m教材《数值分析》陈晓江主编武汉理工大学出版社Y参考书目《数值分析》李庆扬、王能超、易大义编清华大学出版社施普林格出版社《科学和工程计算基础》施妙根、顾丽珍编清华大学出版社上页下页返圆

上页 下页 返回 教材 《数值分析》 陈晓江主编 武汉理工大学出版社  参考书目 《数值分析》 李庆扬、王能超、易大义编 清华大学出版社 施普林格出版社 《科学和工程计算基础》 施妙根、顾丽珍编 清华大学出版社

复习：矩阵范数算子范数由向量范数·lp导出关于矩阵AERnxn的p范数：则II Ax I , IIABI,≤IIA,IBIp = max l Ax Il,pIl All,= maxX+0IIx I ,[风,=1II Ax ,≤II A, II xIp之特别有：II A Il..= maxail（行和范数）l≤isn-II A Il, = maxa;（列和范数）1≤jSni=lIAllz=amax(ATA)（谱范数）上页下页返圆

上页 下页 返回 复习：矩阵范数 算子范数 由向量范数|| · ||p 导出关于矩阵 A  Rnn 的 p 范数: p x p p p Ax x Ax A p x max || || || || || || || || max 0 | | | | 1           则 p p p p p p Ax A x AB A B || || || || || || || || || || || ||     特别有：      n j A aij i n 1 || || max | | 1 （行和范数）     n i A aij j n 1 1 || || max | | 1 （列和范数） || || ( ) A 2 max A A T   （谱范数 ）

>谱半径定义矩阵A的谱半径记为p(A)= max1 2, l, 其中a,为1SiSnA的特征根。定理对任意算子范数·有 p(A)≤I AI定理若A对称， 则有 Il AIl2=P(A)上页下页返回

上页 下页 返回 定理 对任意算子范数|| · || 有 (A) || A|| 定理 若A对称，则有 || || ( ) A 2   A  谱半径 定义 矩阵A的谱半径记为  (A) = ，其中i为 A 的特征根。 max | | 1 i i n   

第六章线性方程组的选代解法s1问题的提出82雅可比选代法83高斯-赛德尔迭代法84迭代法的收敛性85逐次超松弛选代法上页下页返回

上页 下页 返回 第六章 线性方程组的迭代解法 §1 问题的提出 §2 雅可比迭代法 §4 迭代法的收敛性 §5 逐次超松弛迭代法 §3 高斯-赛德尔迭代法

84迭代法的收敛性一、迭代法的改善设为线性方程组Ax=b的近似解称r=b-Ax为剩余向量，称Ax=r的解为修正向量，用表示，Az=r令x=x+z是精确解吗+Ax=A(x+z)=Ax+Az=b-r+r=b上页下页返回

上页 下页 返回 §4 迭代法的收敛性 一、迭代法的改善 设x为线性方程组Ax  b的近似解,称 Ax  r r  b Ax 为剩余向量,称 的解为修正向量, 用z表示, Az  r 令 x  x z Ax  A(x z)  Ax  Az  br  r  b z是精确解吗

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) 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    