第五章解线性方程组的迭代法 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