第二章 22解线性方程组的迭代法 数学与统计学院
第二章 2.2 解线性方程组的迭代法 数学与统计学院
c1x1+a12x2+ b a2Ix+a222+.a2nxn=b2 anIxtan2x2 t 矩阵表示记为AX=b 这里A=(an),我们假设N≠0 X 6=(6 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分裂为 Q-C,Q≠O Ax=b冷(-C)x=b 冷(-QC)x=Qb 冷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 − − = − = − = = +
迭代过程 x+l Bxk+g,(2) B称为迭代矩阵 给定初值x0,就得到向量序列 9 定义:若 limx=x,称逐次逼近法收敛, n→ 否则,称逐次逼近法不收敛或发散
迭代过程 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)的解。 证 lim xki =lim(Bxk +g)=x= Bx+g k- →0 k→o
问题: 是否是方程组(1)的解? 定理1:任意给定初始向量 ,若由迭 代公式(2)产生的迭代序列收敛到 , 则 是方程组(1)的解。 证: 0 x * x * x * x * * 1 lim lim( ) . k k k k x Bx g x Bx g + → → = + = +
逐次逼近法收敛的条件 定理2:对任意初始向量x,由(2)得到 的迭代序列收敛的充要条件是迭代矩阵 的谱半径p(B)<1 证:」x=Bx+g [k+I=Bxx +8 x=B(xk-x)=…=B(x0-x) 因此 lim(rkii -x)=0 lim b=0p(B)<1 k k →)0
逐次逼近法收敛的条件 定理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比较困难, 所以我们希望用别的办法判断是否有 lim b+=0 定理3:若逐次逼近法的迭代矩阵满足酬<1, 则逐次逼近法收敛 Remark:因为矩阵范数‖Bl,B,|Bl都可以 直接用矩阵的元素计算,因此,用定理3, 容易判别逐次逼近法的收敛性
要检验一个矩阵的谱半径小于1比较困难, 所以我们希望用别的办法判断是否有 定理3:若逐次逼近法的迭代矩阵满足 , 则逐次逼近法收敛。 Remark:因为矩阵范数 , , 都可以 直接用矩阵 的元素计算,因此,用定理3, 容易判别逐次逼近法的收敛性。 1 lim 0. k k B + → = B 1 1 B F B B
问题:如何判断可以终止迭代? 定理4:若迭代矩阵满足‖酬|<1则 k+1-x≤ (3) 1-B B k+1-x∥≤ 1-/x1(4) Remark (4)式给出了一个停止迭代的判别准则。 2)(3)式指出驯<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