迭代法解线性方程组

迭代法解线性方程组

　　下面是一篇关于迭代法解线性方程组的论文,对正在写有关数学论文的写作者有一定的参考价值和指导作用!

　　摘 要: 现实生活中许多数学模型都可以归结为解线性方程组,线性方程组的解法有很多种,其中数值分析中迭代法是比较重要的一种。本文利用系数矩阵A的对角线上元素的和给出了线性方程组Ax=b的一种新的迭代格式。

　　关键词: 数值分析迭代法线性方程组

　　在工程技术、自然科学和社会科学中的许多问题最终都可归结为解线性方程组,因此线性方程组的求解对于解决实际问题是极其重要的。线性方程组的解法有很多种,其中数值分析中的迭代法是比较重要的一种。

　　迭代法的基本思想是将线性方程组:

　　Ax=b(其中A∈R,b∈R),(1)

　　经过变换构造出一个等价同解方程组:x=Mx+c,然后改写成Jacobi迭代式:

　　x=Mx+c(k=0,1,2,…),(2)

　　或者Gauss-Seidel迭代式:

　　x=Bx+Bx+c(k=0,1,2,…)(其中B+B=M),

　　选定初始向量:x=(x,x,…,x),反复不断地使用迭代式来构造一个序列:{x}(k=0,1,2,…)。如果{x}(k=0,1,2,…)收敛,它就是该方程组的近似解序列,否则它就没有实用价值。本文利用系数矩阵A的对角线上元素的和给出了系数为对称正定矩阵的线形方程组Ax=b的一种新的定常迭代格式,如果系数矩阵A为可逆的非正定矩阵,可以通过预处理转化为正定矩阵,令A:=AA,b:=Ab即可。且充分考虑加快计算速度。

　　一、收敛定理及证明

　　1.引理:如果M是一个n×n矩阵,对任意的n维向量c迭代格式(2)收敛的充分必要条件是ρ(M)<1,其中ρ(M)为矩阵的M谱半径。

　　证明见文献[1]。

　　2.定理1:如果A为对称正定n×n矩阵,则线形方程组Ax=b的迭代格式

　　x=[I-A]x+(3)

　　是收敛的。

　　证明见文献[3]。

　　对任意系数为正定矩阵的线性方程组,迭代格式(3)都是收敛的,因为收敛速度取决于迭代矩阵谱半径的大小,谱半径越小,收敛速度越快,谱半径越大,收敛速度越慢。但迭代格式(3)只能保证迭代矩阵的谱半径小于1,如果迭代矩阵的谱半径非常接近1,其收敛速度是非常慢的。

　　下面通过在迭代格式(3)中引入一个因子来改进收敛速度。

　　构造迭代格式:

　　{y=[I-A]x+b(4)

　　或者与(4)等价的迭代格式:

　　x=[I-A]x+b(5)

　　3.定理2:如果A为对称正定n×n矩阵,则线性方程组Ax=b的迭代格式(5)是收敛的。

　　证明:设λ(i=1,2,…,n)为A的n个特征值,因为A是对称正定矩阵,所以λ>0(i=1,2,…,n),λ+λ+…+λ=a+a+…+a。

　　I-A的n个特征值为1-(i=1,2,…,n),

　　显然-1<1-<1(i=1,2,…,n),

　　这样有ρ[I-A]<1,由引理知迭代格式(5)是收敛的。

　　如果正定线性方程组Ax=b的系数矩阵特征值的分布相对比较集中,还可以进一步对定理2的迭代格式进行改进,以加快计算速度。

　　当系数矩阵的特征值分布比较集中时,(i=1,2,…,n)近似等于,

　　即A的特征值近似等于。

　　构造迭代格式:

　　{y=[I-A]x+b(6)

　　或者与(6)等价的迭代格式:

　　x=[I-A]x+b(7)

　　因为当系数矩阵的特征值分布比较集中时,(i=1,2,…,n)近似等于,这时迭代格式(7)的迭代矩阵[I-A]的谱半径就与0非常接近,从而使得收敛速度极快。

　　4.定理3:迭代格式(7)收敛的充分必要条件是:

　　<,i=1,2,…,n(8)

　　证明:迭代格式(7)收敛的充分必要条件是其迭代矩阵I-A的谱半径小于1,

　　而矩阵I-A的谱半径小于1的充分必要条件是:

　　<2,即<,i=1,2,…,n。

　　5.推论1:迭代格式(7)收敛的充分条件是λ≤2λ。

　　证:因为λ≤2λ,所以得到:<,i=1,2,…,n,

　　即迭代格式(7)是收敛的。

　　二、实验结果

　　在特征值分布比较集中时,分别用迭代格式(7)对应的算法(iterativen函数)与Gauss_seidel迭代算法、Cholesky分解算法对系数矩阵的阶数J=100,200,500,1000的4个线性方程组进行计算,对所耗时间进行比较,结果如下表:

　　Iterativen,Gauss_seidel,Cholesky算法耗时比较表

　　虽然Gauss_seidel算法的迭代次数比Iterativen算法少,但是Gauss_seidel算法在求逆的过程中浪费了大量的时间。当系数矩阵的特征值比较集中时,Iterativen算法要远远优于其他2种方法。

　　参考文献:

　　[1]Kelley C T.Iterative Methods for Linear and Nonlinear Equations[M].Philade-lphia U.S.A:SIAM,1995.

　　[2]张传林.数值方法[M].北京:中国科学文化出版社,2001:80-150.

　　[3]戈卢布・G.H,范洛恩・C.F著.袁亚湘译.矩阵计算[M].北京:科学出版社,2002.

　　[4]许波,刘征.Matlab工程数学应用[M].北京:清华大学出版社,2000.

　　[5]James W Demmel.Applied Numerical Linear Algebra[M].Philadelphia U.S.A:SIAM,1997.

【迭代法解线性方程组】相关文章：

最小比值旋转迭代法在生产计划中的应用10-09

学习教案进学解10-07

学习教案进学解10-07

作文素材：解网10-07

解简易方程教案10-05

《进学解》教学方案10-08

庖丁解牛教案01-06

解函数题中类比的应用10-26

歇后语解生肖09-06

庖丁解牛教案10-08