武汉大学信息与计算科学系：《数值分析》第二章 求解线性方程组的数值解法（2-2）解线性方程组的迭代法

第二章 22解线性方程组的迭代法 数学与统计学院

第二章 2.2 解线性方程组的迭代法 数学与统计学院

X1十a12X+ b +∴ax=b 2 nn ax1+ax+∵·ax=b n 矩阵表示记为AX=b 这里A=(a)n我们假设A|=0, xn),b=(b b

11 1 12 2 1 1 21 1 22 2 2 2 1 1 2 2 (1) n n n n n n nn n n a x a x a x b a x a x a x b a x a x a x b  + + =   + + =     + + = ( ) , 0, X , . 1 1 ij n n T AX b A T n n a (x (b , , ) , , ) x b b  = =  = = 矩阵表示记为 这里 我们假设 A

解线性方程组的两类方法 直接法:经过有限次运算后可求得方程组精确解的 方法(不计舍入误差!) 迭代法:从解的某个近似值出发,通过构造一个 无穷序列去逼近精确解的方法

解线性方程组的两类方法 直接法: 经过有限次运算后可求得方程组精确解的 方法(不计舍入误差!) 迭代法：从解的某个近似值出发，通过构造一个 无穷序列去逼近精确解的方法

迭代法研究的主要问题 1)迭代格式的构造; 2)迭代的收敛性分析; 3)收敛速度分析 4)复杂性分析;(计算工作量) 5)初始值选择

迭代法研究的主要问题 1）迭代格式的构造； 2）迭代的收敛性分析； 3）收敛速度分析； 4）复杂性分析；（计算工作量） 5）初始值选择

迭代格式的构造 把矩阵A分裂为 A=Q-C,|≠0, 则 Ax=bso-C)x=b 令>x=Bx+g

迭代格式的构造 把矩阵A分裂为 则 A Q C Q = −  , 0,1 1 ( ) ( ) . Ax b Q C x b I Q C x Q b x Bx g − − =  − =  − =  = +

迭代过程 k+/s Bx t g,(2) B称为迭代矩阵。 给定初值x就得到向量序列 0 定义:若 limx=x,称逐次逼近法收敛, 否则,称逐次逼近法不收敛或发散

迭代过程 B称为迭代矩阵。 给定初值 就得到向量序列 定义：若 称逐次逼近法收敛， 否则，称逐次逼近法不收敛或发散。 1 , (2) k k x Bx g + = + 0 x , 0 1 , , , n x x x * lim , n n x x → =

问题:x是否是方程组(1)的解? 定理1:任意给定初始向量x°,若由迭 代公式(2)产生的迭代序列收敛到x 则x是方程组(1)的解 证: Iim xk=lim( Bxk+g)=x Bx+g k→o k

问题： 是否是方程组（1）的解？ 定理1：任意给定初始向量 ，若由迭 代公式（2）产生的迭代序列收敛到 ， 则 是方程组（1）的解。 证： 0 x * x * x * x * * 1 lim lim( ) . k k k k x Bx g x Bx g + → → = +  = +

逐次逼近法收敛的条件 定理2:对任意初始向量x0,由(2)得到 的迭代序列收敛的充要条件是迭代矩阵 的谱半径p(B)<1 证:∫ Bx t k+I Bxk tg klX=B(k-x)=.=b(ro-x) 因此 im(xk+1-x)=0今lmBA=0冷p(B)<1 k→ k→o

逐次逼近法收敛的条件 定理2：对任意初始向量 ，由（2）得到 的迭代序列收敛的充要条件是迭代矩阵 的谱半径 证： 因此 ( ) 1. B  0 x * * 1 * * 1 * 1 0 ( ) ( ). k k k k k x Bx g x Bx g x x B x x B x x + + +  = +    = + − = − = = − * 1 1 lim( ) 0 lim 0 ( ) 1. k k k k x x B B  + + → → − =  =  

要检验一个矩阵的谱半径小于1比较困难, 所以我们希望用别的办法判断是否有 im B k+1 0 k→ 定理3:若逐次逼近法的迭代矩阵满足<1, 逐次逼近法收敛。 Remark:因为矩阵范数‖B,Bl,Bl都可以 直接用矩阵的元素计算,因此,用定理3, 容易判别逐次逼近法的收敛性

要检验一个矩阵的谱半径小于1比较困难， 所以我们希望用别的办法判断是否有 定理3：若逐次逼近法的迭代矩阵满足 ， 则逐次逼近法收敛。 Remark:因为矩阵范数 ， ， 都可以 直接用矩阵 的元素计算，因此，用定理3， 容易判别逐次逼近法的收敛性。 1 lim 0. k k B + → = B 1 1 B F B B 

问题:如何判断可以终止迭代? 定理4:若迭代矩阵满足|f<1则 k+1-x/≤ (3) k+1-X l∥(4) Remark 1)(4)式给出了一个停止迭代的判别准则。 2)(3)式指出B<1越小收敛越快

问题：如何判断可以终止迭代？ 定理4：若迭代矩阵 满足 则 （3） （4） Remark: 1) (4)式给出了一个停止迭代的判别准则。 2) (3）式指出 越小收敛越快。 ， B 1 1 * 1 1 0 1 k k B x x x x B + + −  − − * 1 1 1 k k k B x x x x B + + −  − − B 1