数值线性代数课设.doc

数值线性代数课程设计报告
姓名:陶英
学号:081410124
任课教师:杨熙
南京航空航天大学
2016 年 6 月 22日
求解线性方程组的三种迭代法及其结果比较
摘要
当今的环境下,数值计算越来越依赖于计算机。大规模科学计算和工程技术中许多问题的解决,最终归结为大型稀疏线性方程组的求解,其求解时间在整个问题求解时间中占有很大的比重,有的甚至达到80%。由于现今科学研究和大型项目中各种复杂的可以对计算精度和计算速度的要求越来越高。因此,作为大规模科学计算基础的线性代数方程组的高效数值求解引起了人们的普遍关注。这种方程组的求解一般采用迭代法。
关于迭代法,是有很多种解决公式的:Jacobi,G-S和超松弛迭代法。这三种方法的原理大致相同,Jacobi需要给定初向量,G-S则需要给定初值,超松弛法是对Guass-Seidel迭代法的加权平均改造。而本文则是对大型稀疏线性方程组迭代求解与三种迭代法(Jacobi,Gauss-Seidel和超松弛迭代法)的收敛速度与精确解的误差比较做出研究。
关键词:Jacobi迭代法;Gauss-Seidel迭代法;SOR迭代法;线性方程组
1 方法与理论的叙述

:
对于非奇异线性方程组Ax=b,令A=D-L-U,其中
则原方程组可改写为:
()
其中
给定初始向量:
由()可以构造迭代公式:
其分量形式为:
2. Guass-Seidel迭代法:
类似于Jacobi迭代法,给定初值:
令
则得到Guass-Seidel公式:
其分量形式为:
(SOR 迭代法):
SOR迭代法是对Guass-Seidel迭代法的加权平均改造,即
为Guass-Seidel迭代解,即
它的分量形式为:
其中ω称为松弛因子,当ω>1时称为超松弛;当ω<1时叫低松弛;ω=1时就是
Guass-Seidel迭代。
上述三种经典迭代法收敛的充分必要条件是迭代矩阵谱半径小于1。
谱半径不易求解,而在一定条件下,通过系数矩阵A的性质可判断迭代法的收敛性。
定理1:
若系数矩阵A是严格对角占优或不可约对角占优,则Jacobi迭代法和Gauss-Seidel迭代法均收敛。
定理2:
(1)SOR迭代法收敛的必要条件是0<w<2;
(2)若系数矩阵A严格对角占优或不可约对角占优且0<w<1,则SOR迭代法收敛。w=1时,SOR迭代法退化为Gauss-Seidel迭代法。
2 数值结果

考虑两点边值问题:
容易知道它的精确解为:
为了将微分方程离散,把[0,1]区间n等分,令h=1/n,,得到差分方程
,从而得到迭代方程组的系数矩阵A。
对=1,a=1/2,n=100,分别用jacobi,G-S,超松弛迭代法分别求线性方程组的解,要求4位有效数字,然后比较与精确解的误差。
对=,=,=,考虑同样问题。

由于本题中线性方程组的系数矩阵为三对角矩阵,所以可以采用紧缩方法存储,即
然后在矩阵乘法时对下标处理一下即可。但是考虑到三种迭代方法的一般性,且本题中n=200并不是很大,所以实验中并没有采用紧缩存储,而是采用了直接存储。
边值条件的处理
由于差分得到的方程组的第一行和最后一行中分别出现了边值y(0)与y(1)作为常数项,因此要在常向量的第一项和最后一项作一些修改:

首先确定要求的精度tol ,我们希望当
则停止迭代。
对于迭代格式,若且,则迭代序列的
第k 次近似解和精确解之间有估计式。
由题目要求知我们需要有,而由上面的迭代估计,只要,即即可。而本题中q可近似取为,因此最后令迭代终止条件为
迭代中最佳松弛因子的选取
由于SOR 迭代法的效果和其松弛因子w的选取有关,所以有必要选取合适的松弛因子。当选择最佳松弛因子
时,SOR 方法的迭代速度最快。
Matlab实现:
迭代矩阵是n-1阶的,不是n阶;
等号右端向量b的最后一项,不是ah^2,而是ah^2-eps-h

带入a=1/2,=1
代码:
>> clear
>> x=linspace(0,1);
truy=(1-)/(1-exp(-1/1))*(1-exp(-x./1))+x.*;
figure;
plot(x,truy,'g','LineWidth',);
hold on;
Grid
图:

Jacobi法:代码见附录
Eps=1
结果:
迭代次数k:22273
结果与精确解的比较图(绿色粗线是精确解,黑色细线