第五章解线性方程组的迭代法 1
1 第五章 解线性方程组的迭代法
线性方程组的求解 ■ 在科学研究和工程应用中，求解线性方程组是非常基 础的问题 一般的线性方程组 a11x1+…+a1mXn=b : Ax=b anlx1+…+annXn=bm ■ (Gram公式)当且仅当det(A)≠0时，方程组有雅一解 D =分i=12, a … 01i-1 b a1i+1 D=det(A),D.det an ani-1 bn ani+
¡ 在科学研究和工程应用中，求解线性方程组是非常基 础的问题 ¡ 一般的线性方程组 ¡ （Gram公式）当且仅当 时，方程组有唯一解 2 1 1 1 1 1 1 1 n n n n n n n a x a x b a x a x b A x = b det(A) 0 11 1 1 1 1 1 1 1 1 1 , 1,2, , det( ), det i i i i n i n ni n ni nn D x i n D a a b a a D D a a b a a A
线性方程组的求解 ■求解线性方程组的方法可分为 。直接解法：采用消元（初等变换）、矩阵分解等技巧；从理论上来说， 直接法经过有限次四则运算（假设运算无舍入误差），可以得到线性方 程组的精确解 ·迭代解法：采用送代、分块、预条件处理等技巧；将线性方程的解视为 某种极限过程的向量序列，近似解 3
¡ 求解线性方程组的方法可分为 l 直接解法：采用消元（初等变换）、矩阵分解等技巧；从理论上来说， 直接法经过有限次四则运算（假设运算无舍入误差） ，可以得到线性方 程组的精确解 l 迭代解法：采用迭代、分块、预条件处理等技巧；将线性方程的解视为 某种极限过程的向量序列，近似解 3
迭代法 ■ 求解线性方程的直接法： ●时间复杂度：O(n) ●空间复杂度：O(n2) ·理论上可经过有限次四则运算得到准确解，但因数值计算有舍入误差， 得到的仍然是近似解 ·适用情况：中等规模 ■ 求解线性方程的迭代法： ●高阶稀疏线性方程组 ●主要运算：矩阵与向量的乘法 ●送代格式的构造 ●收敛性、收敛速度
¡ 求解线性方程的直接法： l 时间复杂度： l 空间复杂度： l 理论上可经过有限次四则运算得到准确解，但因数值计算有舍入误差， 得到的仍然是近似解 l 适用情况：中等规模 ¡ 求解线性方程的迭代法： l 高阶稀疏线性方程组 l 主要运算：矩阵与向量的乘法 l 迭代格式的构造 l 收敛性、收敛速度 4 3 O(n ) 2 O(n )
迭代法 基本思想：将线性方程组Ax=b等价支形为X=MK十g ,构造送代关系式：xk+)=Mx+g。若向量序列x) 收敛到x*,则 x*=Mx*+g台Ax*=b ■例如： A=N-P→X=N-Px+Nb ■如何设计迭代格式？ ■收敛性、收敛速度 ■收敛条件（是否与初始值相关） ■优点：占用存储空间少，程序实现简单，尤其适合于 高阶稀疏线性方程组 5
¡ 基本思想：将线性方程组 等价变形为 ，构造迭代关系式： 。若向量序列 收敛到 ，则 ¡ 例如： ¡ 如何设计迭代格式？ ¡ 收敛性、收敛速度 ¡ 收敛条件（是否与初始值相关） ¡ 优点：占用存储空间少，程序实现简单，尤其适合于 高阶稀疏线性方程组 Ax b x Mx g (k1) (k ) x Mx g (k ) x * x x* Mx*g Ax* b 1 1 A N P x N Px N b 5
迭代法 ■ 收敛性分析： x(k+1)-x*=Mx(k)-Mx*M(x()-x*) =…=Mk+1(x0)-X*) ■ 向量序列x收敛台limM=0 与初值的选取无关 定理：求解线性方程组送代格式x+D=Mx)+g收敛的 充分必要条件是p(M<1 ■推论：若矩阵M的范数M2<l,则x+=Mx+g收敛 0 常用矩阵范数：IM山或Ml ■ 注意：当川M≥1或川M≥1时，不能断定送代序列发散 例如 0.9 0 M= 0.2 0.8 6
¡ 收敛性分析： ¡ 向量序列 收敛 ¡ 定理：求解线性方程组迭代格式 收敛的 充分必要条件是 ¡ 推论：若矩阵 的范数 ，则 收敛 ¡ 常用矩阵范数： 或 ¡ 注意：当 或 时，不能断定迭代序列发散 ，例如 ( 1) ( ) ( ) 1 (0) * * ( *) ( *) k k k k x x Mx Mx M x x M x x (k ) x lim 0 k k M 与初值的选取无关 (k1) (k ) x Mx g (M) 1 M || || 1 M p (k1) (k ) x Mx g 1 || M || || || M 1 || M || 1 || || 1 M 0.9 0 0.2 0.8 M 6
Jacobis迭代 基本思想：求解第i个方程得到第i个未知量 a11X1+…+a41nXn=b1 an1x1+…+amXn=bn 1 X=(ax+…+a.-h) 1 -1 X2=(a21X1+a23x3+…+a1mxn-b2） → 22 -1 (anx1+…+anm-xn-1-bn） 7
¡ 基本思想：求解第 个方程得到第 个未知量 7 n nn n n n n a x a x b a x a x b 1 1 11 1 1 1 1 12 2 1 1 11 2 21 1 23 3 1 2 22 1 1 1 1 1 ( ) 1 ( ) 1 ( ) n n n n n n n n n n nn x a x a x b a x a x a x a x b a x a x a x b a i i
Jacobi迭代 ■Jacobi送代格式： x=二(a,+tax0-) a11 x=二(a,+ax+ta-) a22 x=a+a,--,) i=1 i=i+】 8
¡ Jacobi迭代格式： 8 ( 1) ( ) ( ) 1 12 2 1 1 11 ( 1) ( ) ( ) ( ) 2 21 1 23 3 1 2 22 ( 1) ( ) ( ) 1 1 1 1 1 ( ) 1 ( ) 1 ( ) k k k n n k k k k n n k k k n n n n n n nn x a x a x b a x a x a x a x b a x a x a x b a ( ) 1 1 ( ) 11 ( 1) ( ) i n j i k ij j ij k ij j ii k i a x a x b a x
Jacobis送代 ■ Jacobi送代矩阵： 0 -012 一n 61 a 一021 0 ,D= 022 a22 a22 a22 .: X-) 一lnl -0n2 ann ann Ax=b→(D-(D-A)x=b 台Dx=(D-A)x+b 台x=D(D-A)x+Db M=D-(D-A)=I-D-A g=D-b 9
¡ Jacobi迭代矩阵： 9 12 1 1 ( 1) 11 11 ( ) 11 1 1 11 ( 1) 21 2 ( ) 2 2 2 22 22 22 22 ( 1) ( ) 1 2 0 0 , 0 n k k k n k k k n n nn n n n nn nn nn a a b a a a x x a a a b x x a a a a x x a a a b a a a D 1 1 1 1 1 ( ( )) ( ) ( ) ( ) , Ax b D D A x b Dx D A x b x D D A x D b M D D A I D A g D b
Jacobi送代 1958 ■Jacobi迭代收敛条件的充分必要条件： p(M)∑ai=1,2,,n (2)A为严格列对角占优阵，即a>∑a,bj=12,n 则Jacobi送代收敛 ■ 通常，对角元越占优，收敛速度就越快；但也有反倒 ,如： a网A 10
¡ Jacobi迭代收敛条件的充分必要条件： ¡ 定理：若线性方程组 的系数矩阵 满足下列条件 之一： （1） 为严格行对角占优阵，即 （2） 为严格列对角占优阵，即 则Jacobi迭代收敛 ¡ 通常，对角元越占优，收敛速度就越快；但也有反例 ，如： 10 (M) 1 Ax b A A , 1,2, , . ii ij j i a a i n A , 1,2, , . jj ij i j a a j n 1 1 1/ 2 1/ 2 1 A 2 1 3 / 4 1/12 1 A