线性方程组数值求解

1、 数值分析课程设计线性方程组数值求解算法研究院（系）名称 专 业 班 级 学 号 学 生 姓 名 指 导 教 师 摘 要本课程设计用matlab就线性方程组数值方法，Jacobi迭代法，Gauss-Seidel迭代法，超松弛法对所设计的问题进行求解，并编写程序在Matlab中实现，在文章中对各种迭代法进行了收敛性分析。接着用几种不同方法对线性方程组进行求解及结果分析，最后对此次课程设计进行了总结。 关键词：线性方程组，迭代，Matlab，结果分析一、 提出问题直接法得到的解是理论上准确的，但是我们可以看得出，它们的计算量都是n3数量级，存储量为n2量级，这在n比较小的时候还比较合适（n<

2、1000 ），但是对于现在的很多实际问题，往往要我们求解很大的n的矩阵，而且这些矩阵往往是系数矩阵就是这些矩阵含有大量的0元素。对于这类的矩阵，在用直接法时就会耗费大量的时间和存储单元。因此我们有必要引入一类新的方法：迭代法。迭代法具有的特点是速度快。与非线性方程的迭代方法一样，需要我们构造一个等价的方程，从而构造一个收敛序列，序列的极限值就是方程组的根,如何建立迭代格式，向量序列Xk是否收敛条件等。二、 算法的基本思想线性方程组的数值法a) 直接法直接法是指在无舍入误差存在的情况下，经过有限步运算即可求得方程组解的算法，因此，又称为精确法。这种方法是通过矩阵约化将原方程组化为与之等价的三角形

3、方程组或其他形式的可直接求解的方程组而实现的。由于实际中存在舍入误差的影响，这种方法只能求得线性方程组的近似解。通常用来解低阶稠密矩阵方程组及某些大型稀疏矩阵方程组比较著名的方法有：Gauss消去法，主元消去法，LU分解法，QR分解法，Cholesky分解法等。b) 迭代法迭代法是用某种极限过程去逐步逼近线性方程组精确解的方法。迭代法具有需要计算机的存储单元较少，程序设计简单和原始系数矩阵在计算过程中始终不变等优点，但存在收敛性与收敛速度问题。迭代法是解大型稀疏矩阵方程组，尤其是由微分方程离散后得到的大型方程组的重用方法。比较著名的方法有：jacobi迭代法，Gauss-seidel迭代法，超

4、松弛迭代法，梯度法，理查森迭代法。与解f(x)=0 的不动点迭代相类似,将AX=b改写为X=BX+f 的形 式,建立雅可比方法的迭代格式： k+1=BX(k)+f ,其中，B称为迭代矩阵.其计算精度可控,特别适用于求解系数为大型稀疏矩阵(sparse matrices)的方程组.三、 算法的推导及步骤对方程组做等价变换则，我们可以构造序列若同时：所以，序列收敛与初值的选取无关定义：（收敛矩阵）定理： 矩阵G为收敛矩阵，当且仅当G的谱半径<1由知，若有某种范数 则，迭代收敛1. Jacobi迭代格式很简单：2. GaussSeidel迭代在Jacobi迭代中，使用最新计算出的分量值3. 松

5、弛迭代(SOR)记则可以看作在前一步上加一个修正量。若在修正量前乘以一个因子 有对Gauss-Seidel迭代格式写成分量形式，有四、 算法分析（稳定.收敛.误差）1. 算法及收敛性：1.1. Jacobi迭代矩阵记易知，Jacobi迭代有收敛条件：迭代格式收敛的充要条件是G的谱半径<1。对于Jacobi迭代，我们有一些保证收敛的充分条件若A满足下列条件之一，则Jacobi迭代收敛。 A为行对角占优阵 A为列对角占优阵 A满足1.2. GaussSeidel迭代矩阵GaussSeidel收敛条件：迭代格式收敛的充要条件是G的谱半径<1。我们看一些充分条件若A满足下列条件之一，则Ga

6、uss-Seidel迭代收敛。 A为行或列对角占优阵 A对称正定阵1.3. 松弛迭代(SOR)松弛迭代收敛A对称正定，则松弛迭代收敛SOR方法收敛的快慢与松弛因子w的选择有密切关系.但是如何选取最佳松弛因子,即选取w=w*,使r(Gw )达到最小,是一个尚未很好解决的问题.实际上可采用试算的方法来确定较好的松弛因子.经验上可取1.4<w<1.6.2. 稳定性分析取：a*x=d a=5 2 1;-1 4 2;2 -3 10 d=-12;20;3(1)考察用J、G-S及SOR解此方程组的收敛性.(2)分别用雅可比迭代法、高斯-赛德尔迭代法及逐次超松弛迭代法解此方程组。要求时迭代中止，观

7、察收敛速度。(1) J迭代矩阵的谱半径：max(abs(eig(D*(L+U)= 0.506G-S迭代矩阵的谱半径：max(abs(eig(inv(D-L)*U)= 0.2000SOR迭代矩阵的谱半径：max(abs(eig(inv(D-w*L)*(1-w)*D+w*U)=0.9756所以用J、G-S及SOR均收敛（且有 ）。(2)Jacbio： X =-4.0000 3.0000 2.0000 n =18GaussSeidel： X =-4.0000 3.0000 2.0000 n =8SOR( )： X =-4.0000 3.0000 2.0000 n =482可见高斯-赛德尔迭代法要比雅

8、可比迭代公式的收敛速度快。同时，如果超松弛迭代法的 选取不当不但不会加速收敛还会对收敛速度造成很恶劣的结果.3. 误差分析设方程组 AX=b,其中， A=(aij)n 为非奇异阵， X=(x1,x2,xn)T, b=(b1,b2,bn)T.由于原始数据aij, bi往往是观测数据，难免带有误差，因此， 我们下面讨论原始数据的微小变化对方程组的影响.设A精确b有误差，得到解即 而于是 说明右端相对误差 在解放大 倍.设b精确A有误差，得到解即 或者 只要|A|充分小使得上式表明：当|A|充分小，矩阵 A 的相对误差在解中可能放大了倍.五、 算法的实现（代码+算例）1. Jacobi迭代代码fun

9、ction x,n=jacbio(a,d,x)stop=1.0e-4; %迭代的精度L=-tril(a,-1);U=-triu(a,1);D=inv(diag(diag(a);X=D*(L+U)*x+D*d; % J迭代公式n=1;while norm(X-x,inf)>=stop % 时迭代中止否则继续x=X;X=D*(L+U)*x+D*d;n=n+1;endXn2. GaussSeidel迭代代码function x,n=Gauss_Seidel_iterative(a,d,x)stop=1.0e-4;%迭代的精度L=-tril(a,-1);U=-triu(a,1);D=(diag(

10、diag(a);X=inv(D-L)*U*x+inv(D-L)*d; % G-S迭代公式n=1;while norm(X-x,inf)>= stop % 时迭代中止否则继续x=X;X=inv(D-L)*U*x+inv(D-L)*d;n=n+1;endXn3. 松弛迭代(SOR)迭代代码function x,n=successive(a,d,x)stop=1.0e-4;%迭代的精度w=1.44; %松弛因子L=-tril(a,-1);U=-triu(a,1);D=(diag(diag(a);X=inv(D-w*L)*(1-w)*D+w*U)*x+w*inv(D-w*L)*d;% SOR迭代

11、公n=1;while norm(X-x,inf)>=stop % 时迭代中止否则继续x=X;X=inv(D-w*L)*(1-w)*D+w*U)*x+w*inv(D-w*L)*d;n=n+1;endXn4. 算法实例4.1 jacbio迭代a=5 2 1;-1 4 2;2 -3 10;>> x=0;0;0; >> d=-12;20;3;>> x,n=jacbio(a,d,x)X =-4.0000;3.0000;2.0000n =184.2 Gauss迭代a=5 2 1;-1 4 2;2 -3 10;>> x=0;0;0; >> d

12、=-12;20;3;>> x,n=Gauss_Seidel_iterative(a,d,x)X =-4.0000;3.0000;2.0000n = 84.3 SOR迭代a=5 2 1;-1 4 2;2 -3 10;>> x=0;0;0; >> d=-12;20;3;>> x,n=jacbio(a,d,x)X =-4.0000;3.0000;2.0000n =482六、 应用实例1. 道路交通流量2. 电网中的电流流量3. 营养减肥食谱七、 知识拓展线性方程组是近似求解微分方程的基础，因而是人类揭示自然规律的基础；边界问题的内点个数决定着线性方程组的阶数，在实际问题中我们遇到的求解区域往往很大，如计算天气预报的大气层区域、计算海洋动力的海域、计算油气储量的含油区域等等，为提高精度就要将网格划