第六章解线性方程组的迭代法 2
2 第六章 解线性方程组的迭代法
迭代法 ■ 求解线性方程的直接法： 。时间复杂度：O(n) ●空间复杂度：O(n2) ●理论上可经过有限次四则运算得到准确解，但因数值计算有舍入误差， 得到的仍然是近似解 ·适用情况：中等规模 ■求解线性方程的送代法： ●高阶稀疏线性方程组 ●主要运算：矩阵与向量的乘法 ●送代格式的构造 ●收敛性、收敛速度 3
迭代法 求解线性方程的直接法： 时间复杂度： 空间复杂度： 理论上可经过有限次四则运算得到准确解，但因数值计算有舍入误差， 得到的仍然是近似解 适用情况：中等规模 求解线性方程的迭代法： 高阶稀疏线性方程组 主要运算：矩阵与向量的乘法 迭代格式的构造 收敛性、收敛速度 3 3 O n( ) 2 O n( )
迭代法 ■ 基本思想：将线性方程组AX=b等价变形为X=MK十g , 构造送代关系式：x+=Mx)+g。若向量序列x) 收敛到x,则 X*=Mx*+g→Ax*=b ■例如： A=N-P→x=N-Px+N-b ■如何设计送代格式？ 收敛性、收敛速度 ■ 收敛条件（是否与初始值相关） 优点：占用存储空间少，程序实现简单，尤其适合于 高阶稀疏线性方程组
迭代法 基本思想：将线性方程组 等价变形为 ，构造迭代关系式： 。若向量序列 收敛到 ，则 例如： 如何设计迭代格式？ 收敛性、收敛速度 收敛条件（是否与初始值相关） 优点：占用存储空间少，程序实现简单，尤其适合于 高阶稀疏线性方程组 Ax b = x Mx g = + ( 1) ( ) k k + x Mx g = + ( ) k x * x x Mx g Ax b ** * = +⇔ = − − 1 1 A N P x N Px N b = −⇒= + 4
迭代法 ■ 收敛性分析： x(k+1)-x*=Mx(k)-Mx*=M(x()-x*) =.=Mk+(x0)-X*) ■向量序列x)收敛台limM=0 与初值的选取无关 定理：求解线性方程组送代格式xk+=Mx+g收敛的 充分必要条件是p(M)<1 ■推论：若矩阵M的范数‖M‖2<1，则x+)=Mx+g收敛 ■常用矩阵范数：‖M山或Ml 注意：当川M≥1或川M≥1时，不能断定送代序列发散 ,例如 0.9 0 M= 0.20.8 5
迭代法 收敛性分析： 向量序列 收敛 定理：求解线性方程组迭代格式 收敛的 充分必要条件是 推论：若矩阵 的范数 ，则 收敛 常用矩阵范数： 或 注意：当 或 时，不能断定迭代序列发散 ，例如 ( 1) ( ) ( ) 1 (0) * * ( *) ( *) kk k k + + −= − = − = = − x x Mx Mx M x x Mx x ( ) k x lim 0 k k→∞ ⇔ = M 与初值的选取无关 ( 1) ( ) k k + x Mx g = + ρ()1 M < M || || 1 M p < ( 1) ( ) k k + x Mx g = + 1 || || M || || M ∞ 1 || || 1 M ≥ || || 1 M ∞ ≥ 0.9 0 0.2 0.8 = M 5
Jacobi送代 ■基本思想：求解第i个方程得到第i个未知量 a11X1+.+anXn=b anx1+.+AmnXn=bn 1 x=。(ax,+.tanx。-bh) 1 -1 X2=(a21X1+a23x3+.+a1nxn-b) → 22 x=ax+.叶ak1-b） 6
Jacobi迭代 基本思想：求解第 个方程得到第 个未知量 6 + + = + + = n nn n n n n a x a x b a x a x b 1 1 11 1 1 1 112 2 11 11 2 21 1 23 3 1 2 22 1 1 1 1 1 ( ) 1 ( ) 1 ( ) n n n n n n nn n n nn x ax ax b a x ax ax ax b a x ax a x b a − − − = ++ − − = + ++ − ⇒ − = ++ − i i