线性方程组的迭代解法

目录摘要 (1)关键词 (1)Abstract (1)Keywords (1)前言 (1)1.基本迭代法 (1)1.1 雅可比迭代法 (2)1.2 高斯-塞德尔迭代法 (3)1.3 超松弛迭代法 (4)2.迭代法的收敛性 (5)2.1 迭代法基本定理 (6)2.2 迭代法收敛的充分条件 (7)参考文献 (8)学生姓名：贾亚鹏 学号：20085031177 数学与信息科学学院 数学与应用数学 指导教师：李景杰 职称：副教授摘 要：本文介绍了线性方程组的迭代解法，并依次进行收敛性分析。

关键词：线性方程组；迭代法；收敛性Iterative method of linear equationsAbstract: In this paper, we mainly introduce some iterative methods of linear equations, and make analysis about algorithm convergence. Key words: linear equations; iterative method; convergence前言：考虑线性方程组Ax b =，其中A 为非奇异矩阵，当A 为低阶稠密矩阵时，选主元消去法是有效方法。

但是，对于工程技术中产生的大型稀疏矩阵方程组（A的阶数很n 大，但零元素较多），迭代法求解更为合适。

1. 基本迭代法设有Ax b =，()n nij A a R ⨯=∈为非奇异矩阵.将A 分裂为A M N =-,M 为可选择的非奇异矩阵，且使Mx d =容易求解，称M 为分裂矩阵。

11Ax b x M Nx M b --=⇔=+可构造一阶定常迭代法(0)(1)()()(0,1,...,)k k x xBx f k +⎧⎨=+=⎩初始向量其中111()B M N M M A I M A---==-=-1f M b-=称1B I M A -=-为迭代法的迭代矩阵。

设0,(1,2,...,)ii a i n ≠=并将A 写为三部分121,1111212,12221,11,21,12,100000000n n n n n n n n nn n n n n a a a a a a a a A D L U a a a a a a a ---------⎡⎤⎡⎤⎡⎤⎢⎥⎢⎥---⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥=--≡--⎢⎥⎢⎥⎢⎥---⎢⎥⎢⎥⎢⎥⎣⎦⎢⎥⎢⎥---⎣⎦⎣⎦1.1雅可比迭代法 由0,(1,2,...,)ii a i n ≠=取,M D A D N ==-则解Ax b =的雅可比迭代法(0)(1)()()(0,1,...,)k k x xBx f k +⎧⎨=+=⎩初始向量其中111(),B I D A D L U J f D b---=-=+≡=记()()()()12(,,,)k k k k n x x x x =由雅可比迭代公式有(1)()()k k Dx L U x b+=++或1(1)()()11,(1,2,,)i nk k k ii iij jijji j j i a xa xa xb i n -+==+=--+=∑∑于是解的雅可比迭代法的计算公式为(0)(0)(0)(0)121(1)(1)()11(,,,)()(1,2,,;0,1,)Tn i n k k k ii ij j ij j ii j j i x x x x x b a x a x a i n k -++==+⎧=⎪⎪=--⎨⎪⎪==⎩∑∑ 表示迭代次数雅可比迭代计算公式简单，每迭代一次只需计算一次矩阵和向量的乘法，且计算过程中原始矩阵A 始终不变。

1.2高斯—赛德尔迭代法 取()M D L A M N=-=-下三角阵，则解得Ax b =的高斯—赛德尔迭代法为(0)(1)()(),(0,1,)k k x x bx f k +⎧⎨=+=⎩初始向量其中11()()B I D L A D L U G--=--=-=1()f D L b-=-称1()G D L U-=-为解Ax b =的高斯-赛德尔迭代法的迭代矩阵。

记()()()()12(,,,)k k k k Tn x x x x =则由迭代公式得(1)()()k k D L x Ux b+-=+即1(1)(1)()11,(1,2,,)i nk k k ii ii ij jijjj j i a xb a xa xi n -++==+=--=∑∑于是解Ax b =的高斯-赛德尔迭代法的迭代计算公式为(0)(0)(0)(0)121(1)(1)()11(,,,)()(1,2,,;0,1,)Tn i n k k k ii ij j ij j ii j j i x x x x x b a x a x a i n k -++==+⎧=⎪⎪=--⎨⎪⎪==⎩∑∑高斯-赛德尔迭代法可以看作为雅可比迭代法的一种改进，由计算公式可知，高斯-赛德尔迭代法每迭代一次只需计算一次矩阵与向量的乘积。

1.3超松弛迭代法取分裂矩阵M 为带参数的下三角阵，1()M D L ωω=-其中0ω>为可选择的松弛因子，构造迭代法使其迭代矩阵为11()((1))L I M A D L D U ωωωω--≡-=--+从而得到解的逐次超松弛迭代法(0)(1)(),(0,1,)k k x x L x f k ω+⎧⎨=+=⎩其中1()((1))L D L D U ωωωω-=--+1()f D L bωω-=-下面给出解Ax b =的SOR 迭代法分量计算公式 记()()()()12(,,,)k k k k T nxx x x =则公式可得(1)()()((1))k k D L x D U x bωωωω+-=-++由此得到Ax b =的SOR 方法计算公式为(0)(0)(0)(0)121(1)()(1)()1(,,,)()(1,2,,;0,1,)Tn i n k k k k ii i ij j ij j ii j j i x x x x x x b a x a x a i n k ωω-++==⎧=⎪⎪=+--⎨⎪⎪==⎩∑∑ ，为松弛因子2.迭代法的收敛性 设Ax b = (3.1)其中n n A R ⨯∈为非奇异矩阵，记*x 为的精确解，且设有等价的方程组Ax b x Bx f =⇔=+于是**x Bx f=+ (3.2)设有解Ax b =的一阶定常迭代法(1)()k k x Bx f+=+ (3.3)引入误差向量()()*(0,1,2,)k k x x k ε=-=由（3.3）式减（3.2）式得到的误差向量递推公式定义1 设有矩阵序列()()k n n k ij A a R ⨯=∈ 及()n nij A a R⨯=∈如果2n 个数列极限存在且有()lim (,1,2,,)k ijij k aa i j n →∞==则称{}k A 收敛于A ，记为lim k k A A→∞=定理1lim lim 0k k k k A A A A →∞→∞=⇔-=其中⋅为矩阵的任意一种算子范数证明：显然有lim lim 0k k k k A A A A ∞→∞→∞=⇔-=在利用矩阵范数的定价性，可证明定理对其他算子范数亦对。

定理2lim lim n nk k k k A A x R A x Ax⨯→∞→∞=⇔∈=对任何向量都有定理3 设()n nij B b R⨯=∈则lim 0k k B →∞=的充分条件是矩阵的谱半径()1B ρ< 2.1迭代法基本定理：设有方程组x Bx f =+及一阶定常迭代法(1)()k k x Bx f+=+对任意选取初始向量(0)x ，迭代法收敛的冲要条件是矩阵B 的谱半径()1B ρ<证明：(充分性）设()1B ρ<易知()Ax f A I B ==-其中有唯一解，记为*x 则**x Bx f=+误差向量()*(0)k k k x x B εε=-= (0)(0)*x x ε=-由设()1B ρ<，应用定理3，有lim 0kk B →∞=于是对任意(0)x 有lim 0kk ε→∞=则()*lim k k xx→∞=（必要性）设对任意(0)x 有()*lim k k xx→∞=其中(1)()k k x Bx f+=+显然，极限*x 是方程组的解，且对任意(0)x 有()*(0)0()k k k x x B k εε=-=→→∞由定理2知lim 0kk B →∞=再由定理3，即得()1B ρ<2.2迭代法收敛的充分性条件： 设有方程组x Bx f =+ n nB R ⨯∈即一阶定常迭代法(1)()k k x Bx f+=+如果有某种算子范数1B q =<则（1） 迭代法收敛，即对任取(0)x 有()*lim k k xx →∞=**x Bx f =+（2）*()*(0)k k x xq x x-≤-（3）*()()(1)1k k k qx x x x q--≤--（4） *()(1)(0)1k k q x xx x q-≤--参考文献[1]李庆扬，王能超，易大义.数值分析（第四版）[M]，北京：清华大学出版社，2001 [2]傅凯新，黄云清，舒 适.数值计算方法[M]，长沙：湖南科学技术出版社，2002 [3]冯果忱，刘经伦.数值代数基础[M]，长春：吉林大学出版社，1991。