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 Rnn 的 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 br 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