课题三线性方程组的迭代法.docx
《课题三线性方程组的迭代法.docx》由会员分享，可在线阅读，更多相关《课题三线性方程组的迭代法.docx（16页珍藏版）》请在冰点文库上搜索。
课题三线性方程组的迭代法
课题三线性方程组的迭代法
一、问题提出
对课题二所列目的和意义的线性方程组，试分别选用Jacobi迭代法，Gauss-Seidol迭代法和SOR方法计算其解。
1、设线性方程组
=
x*=（1,-1,0,1,2,0,3,1,-1,2）T
2、设对称正定阵系数阵线方程组
=
x*=（1,-1,0,2,1,-1,0,2）T
3、三对角形线性方程组
=
x*=（2,1,-3,0,1,-2,3,0,1,-1）T
二、要求
1、体会迭代法求解线性方程组，并能与消去法做以比较；
2、分别对不同精度要求，如ε=10-3，10-4，10-5由迭代次数体会该迭代法的收敛快慢；
3、对方程组2，3使用SOR方法时，选取松弛因子ω=0.8，0.9，1，1.1，1.2等，试看对算法收敛性的影响，并能找出你所选用的松弛因子的最佳者；
4、给出各种算法的设计程序和计算结果。
三、目的和意义
1、通过上机计算体会迭代法求解线性方程组的特点，并能和消去法比较；
2、运用所学的迭代法算法，解决各类线性方程组，编出算法程序；
3、体会上机计算时，终止步骤‖x（k+1）-x（k）‖<ε或k>（予给的迭代次数），对迭代法敛散性的意义；
4、体会初始解x（0），松弛因子的选取，对计算结果的影响。
四、迭代计算
1、雅可比迭代法
在进行雅可比迭代之前，我们应该先判断迭代是否能够收敛，这里我们使用雅可比迭代法收敛的充分必要条件（即，迭代矩阵的谱半径小于等于1）。
1、判断方程组一使用雅可比迭代法是否收敛
在matlab软件中编写程序：
D=diag（diag（A））;
L=-tril（A,-1）;
U=-triu（A,1）;
B=D\（L+U）;
t=eig（B）
r=max（abs（t））
可求出方程组一的雅可比迭代矩阵的特征值分别为：
{1.6604+3.8389i；1.6604-3.8389i；-3.3952；-1.3286+1.5704i；
-1.3286-1.5704i；-0.4754；-0.1912；0.9785；0.9568；1.4628}
显然，其谱半径大于1，则雅可比迭代法不收敛，故不可用雅可比迭代法进行迭代求解。
可用消去法求解，编写matlab高斯列主元消去法的程序如下：
functionX=Gauss_pivot（A,b）
n=length（b）;
X=zeros（n,1）;
c=zeros（1,n）;
d1=0
fori=1:
n-1
max=abs（A（i,i））;
m=i;
forj=i+1:
n
ifmaxmax=abs（A（j,i））;
m=j;
end
end
if（m~=i）
fork=i:
n
c（k）=A（i,k）;
A（i,k）=A（m,k）;
A（m,k）=c（k）;
end
d1=b（i）;
b（i）=b（m）;
b（m）=d1;
end%选主元
fork=i+1:
n
forj=i+1:
n
A（k,j）=A（k,j）-A（i,j）*A（k,i）/A（i,i）;
end
b（k）=b（k）-b（i）*A（k,i）/A（i,i）;
A（k,i）=0;
end
end%消去
X（n）=b（n）/A（n,n）;
fori=n-1:
-1:
1
sum=0;
forj=i+1:
n
sum=sum+A（i,j）*X（j）;
end
X（i）=（b（i）-sum）/A（i,i）;
end%回代求解
调用该函数程序，可求解得：
X=[1.0000；-1.0000；-0.0000；1.0000；2.0000；-0.0000；3.0000；1.0000；-1.0000；2.0000]
这与x*=（1,-1,0,1,2,0,3,1,-1,2）T相同。
2、判断方程组二使用雅可比迭代法是否收敛
与方程组一相似，求出方程组二的雅克比迭代矩阵的特征值为：
{-1.9407；-1.0222；-0.2171；0.2039；0.9974；0.4796；0.7943；0.7048}
其谱半径为1.9407，大于1，则方程组二使用雅可比迭代法仍然不收敛，故不可用雅可比迭代法求解。
调用高斯列主元消去法程序，可求得：
X=[1.0000；-1.0000；0.0000；2.0000；1.0000；-1.0000；0.0000；2.0000]
这与x*=（1,-1,0,2,1,-1,0,2）T相同。
3、判断方程组三使用雅可比迭代法是否收敛
与方程组一、方程组二相似，求出方程组二的雅克比迭代矩阵的特征值为：
{-0.4797；-0.4206；-0.3274；-0.2077；-0.0712；0.0712；0.2077；0.3274；0.4206；0.4797}
其谱半径为0.4797，小于1，则方程组三使用雅可比迭代法收敛，故可用雅可比迭代法求解。
编写matlab雅克比求解线性方程组的程序如下：
function[x2,k]=Jacobimethod（A,b,x0,N,emg）
n=length（A）;
x1=zeros（n,1）;x2=zeros（n,1）;
x1=x0;k=1;
r=10;
whiler>=emg
fori=1:
n
sum=0;
forj=1:
n
ifi~=j
sum=sum+A（i,j）*x1（j）;
end
end
x2（i）=（b（i）-sum）/A（i,i）;
end
t=abs（x2-x1）;
r=max（t）;
x1=x2;
k=k+1;
ifk>N
disp（'迭代失败，返回'）;
return;
end
k
end
调用雅克比求解线性方程组的程序，取初值x0=[0;0;0;0;0;0;0;0;0;0]，不同精度下求得解为：
ε=10-3：
则x2=[2.0000；1.0000；-2.9997；-0.0006；1.0008；-2.0015；3.0010；-0.0016；1.0007；-1.0007]，迭代次数k=10
ε=10-4：
则x2=[2.0000；1.0000；-2.9999；-0.0002；1.0002；-2.0003；3.0002；-0.0003；1.0001；-1.0001]，迭代次数k=12
ε=10-5：
则x2=[2.0000；1.0000；-3.0000；0.0000；1.0000；-2.0000；3.0000；0.0000；1.0000；-1.0000]，迭代次数k=15
由方程组三雅克比的迭代过程可以看出，精度越高，所需迭代次数就越多，迭代速度也就越慢，但是其解也越来越接近与真值。
当ε=10-5时，x2=[2.0000；1.0000；-3.0000；0.0000；1.0000；-2.0000；3.0000；0.0000；1.0000；-1.0000]，这与真值基本是相同的。
2、高斯-赛德尔迭代法
同样，在进行高斯-赛德尔迭代之前，我们应该先判断迭代是否能够收敛，这里我们使用高斯-赛德尔迭代法收敛的充分必要条件（即，迭代矩阵的谱半径小于等于1）。
1、判断方程组一使用高斯-赛德尔迭代法是否收敛
在matlab软件中编写程序：
D=diag（diag（A））;
L=-tril（A,-1）;
U=-triu（A,1）;
B=（D-L）\U;
t=eig（B）
r=max（abs（t））
可求出方程组一的高斯-赛德尔迭代矩阵的特征值分别为：
{0；17.1222；-0.8196+4.1041i；-0.8196-4.1041i；0.9839；0.8639；
-0.0220+0.1529i；-0.0220-0.1529i；0.4784；0.0000}
显然，其谱半径为r=17.1222，大于1，则高斯-赛德尔迭代法不收敛，故不可用高斯-赛德尔迭代法进行迭代求解。
2、判断方程组二使用高斯-赛德尔迭代法是否收敛
与方程组一相似，求出方程组二的高斯-赛德尔迭代矩阵的特征值为：
{0；0.9947；0.5849+0.0782i；0.5849-0.0782i；0.3075+0.2159i；0.3075-0.2159i；0.0291；-0.0000}
其谱半径r=0.9947，小于1，则方程组二使用高斯-赛德尔迭代法仍然收敛，故可用高斯-赛德尔迭代法求解。
编写matlab高斯-赛德尔迭代法程序如下：
functionX=gseid（A,b,x0,delta,max1）
N=length（b）;
fork=1:
max1
forj=1:
N
ifj==1
X
（1）=（b
（1）-A（1,2:
N）*x0（2:
N））/A（1,1）;
elseifj==N
X（N）=（b（N）-A（N,1:
N-1）*（X（1:
N-1））'）/A（N,N）;
else
X（j）=（b（j）-A（j,1:
j-1）*X（1:
j-1）'-A（j,j+1:
N）*x0（j+1:
N））/A（j,j）;
end
end
t=abs（X'-x0）;
r=max（t）;
x0=X';
if（rbreak
end
k
end
调用高斯-赛德尔求解线性方程组的程序，取初值x0=[0;0;0;0;0;0;0;0;0;0]，不同精度下求得解为：
ε=10-3：
则x2=[1.3126；-1.3619；0.0775；1.8468；1.0320；-1.0685；0.0209；1.9882]，迭代次数k=7
ε=10-4：
则x2=[1.1604；-1.1886；0.0377；1.9166；1.0133；-1.0342；0.0082；1.9953]，迭代次数k=132
ε=10-5：
则x2=[1.0160；-1.0188；0.0038；1.9917；1.0013；-1.0034；0.0008；1.9995]，迭代次数k=569
由方程组二的高斯-赛德尔迭代过程可以看出，精度越高，所需迭代次数就越多，迭代速度也就越慢，但是其解也越来越接近与真值。
当ε=10-5时，x2=[1.0160；-1.0188；0.0038；1.9917；1.0013；-1.0034；0.0008；1.9995]，这与真值x*=（1,-1,0,2,1,-1,0,2）T基本是相同的。
3、判断方程组三使用高斯-赛德尔迭代法是否收敛
与方程组一、方程组二相似，求出方程组二的高斯-赛德尔迭代矩阵的特征值为：
{0；0.2302；0.1769；0.1072；0.0431；0.0051；-0.0000+0.0000i；-0.0000-0.0000i；0.0000；-0.0000}
其谱半径为0.2302，小于1，则方程组三使用高斯-赛德尔迭代法收敛，故可用高斯-赛德尔迭代法求解。
调用高斯-赛德尔求解线性方程组的程序，取初值x0=[0;0;0;0;0;0;0;0;0;0]，不同精度下求得解为：
ε=10-3：
则x2=[2.0016；0.999；-3.0021；-0.0028；0.9986；-2.0003；3.00010.0001；1.0000；-1.0000]，迭代次数k=4
ε=10-4：
则x2=[1.9999；0.9998；-3.0002；-0.0001；1.0000；-2.0000；3.00000.0000；1.0000；-1.0000]，迭代次数k=6
ε=10-5：
则x2=[2.0000；1.0000；-3.0000；-0.0000；1.0000；-2.0000；3.00000.0000；1.0000；-1.0000]，迭代次数k=8
当ε=10-5时，x2=[2.0000；1.0000；-3.0000；-0.0000；1.0000；-2.0000；3.00000.0000；1.0000；-1.0000]，这与真值x*=（2,1,-3,0,1,-2,3,0,1,-1）T是相同的。
3、超松弛迭代法
1、判断方程组一使用超松弛迭代法是否收敛
在matlab软件中编写程序：
w=1.3
D=diag（diag（A））;
L=-tril（A,-1）;
U=-triu（A,1）;
B=（D-w*L）\（（1-w）*D+w*U）;
t=eig（B）
r=max（abs（t））
可求出方程组一的超松弛迭代矩阵的谱半径为r=164.0633，大于1，则超松弛迭代法不收敛，故不可用超松弛迭代法进行迭代求解。
2、判断方程组二使用超松弛迭代法是否收敛
与方程组一相似，取w=1.3求出方程组二的超松弛迭代矩阵的特征值为：
{0.9902；0.4505+0.3101i；0.4505-0.3101i；0.1697+0.4168i；
0.1697-0.4168i；0.0452；-0.0972+0.1215i；-0.0972-0.1215i}
其谱半径r=0.9902，小于1，则方程组二使用超松弛迭代法收敛，故可用超松弛迭代法求解。
编写超松弛迭代法的matlab程序如下：
function[x,k]=SOR（A,b,w,N,r）
x0=zeros（1,length（b））;
[n,n]=size（A）;
k=1;
whilek<=N
x
（1）=（b
（1）-A（1,2:
n）*x0（2:
n）'）/A（1,1）;
fori=2:
n
x（i）=（1-w）*x0（i）+w*（b（i）-A（i,1:
i-1）*x（1:
i-1）'-A（i,i+1:
n）*x0（i+1:
n）'）/A（i,i）;
end
ifmax（abs（x-x0））<=r
break;
end
k=k+1;
x0=x;
end
ifk==N+1
disp（'超过最大迭代次数，求解失败！
'）;
end
调用超松弛求解线性方程组的程序，取初值x0=[0;0;0;0;0;0;0;0;0;0]，取ε=10-5，分别取ω=0.8，0.9，1，1.1，1.2，1.3，1.4，1.5，1.6，1.7，1.8，1.9，2时，可得到不同的解：
ω=0.8：
则x=[1.0208；-1.0245；0.0049；1.9892；1.0017；-1.0044；0.0011；1.9994]，迭代次数k=10
ω=0.9：
则x=[1.0182；-1.0214；0.0043；1.9906；1.0015；-1.0039；0.0009；1.9995]迭代次数k=604
ω=1：
则x=[1.0160；-1.0188；0.0038；1.9917；1.0013；-1.0034；0.0008；1.9995]迭代次数k=570
ω=1.1：
则x=[1.0144；-1.0169；0.0034；1.9926；1.0012；-1.0031；0.0007；1.9996]迭代次数k=538
ω=1.2：
则x=[1.0129；-1.0151；0.0030；1.9933；1.0011；-1.0027；0.0007；1.9996]迭代次数k=510
ω=1.3：
则x=[1.0116；-1.0136；0.0027；1.9940；1.0010；-1.0025；0.0006；1.9997]迭代次数k=484
ω=1.4：
则x=[1.0106；-1.0124；0.0025；1.9945；1.0009；-1.0023；0.0005；1.9997]迭代次数k=459
ω=1.5：
则x=[1.0097；-1.0113；0.0023；1.9950；1.0008；-1.0021；0.0005；1.9997]迭代次数k=437
ω=1.6：
则x=[1.0089；-1.0104；0.0021；1.9954；1.0007；-1.0019；0.0004；1.9997]迭代次数k=416
ω=1.7：
则x=[1.0082；-1.0096；0.0019；1.9958；1.0007；-1.0018；0.0004；1.9998]迭代次数k=396
ω=1.8：
则x=[1.0076；-1.0088；0.0018；1.9961；1.0006；-1.0016；0.0004；1.9998]迭代次数k=378
ω=1.9：
则x=[1.0070；-1.0081；0.0016；1.9964；1.0006；-1.0015；0.0003；1.9998]迭代次数k=361
ω=2：
则超过最大迭代次数，求解失败！
当ω=1.9时，x=[1.0070；-1.0081；0.0016；1.9964；1.0006；-1.0015；0.0003；1.9998]，这与真值x*=（1,-1,0,2,1,-1,0,2）T是基本相同的。
而当ω=2，则超过最大迭代次数，求解失败！
3、判断方程组三使用超松弛迭代法是否收敛
与方程组一、方程二相似，取w=1.3求出方程组二的超松弛迭代矩阵的特征值为：
{-0.1055+0.2808i；-0.1055-0.2808i；-0.2957+0.0505i；-0.2957-0.0505i；-0.2635+0.1433i；-0.2635-0.1433i；-0.1505+0.2595i；-0.1505-0.2595i；-0.2094+0.2148i；-0.2094-0.2148i}
其谱半径r=0.3000，小于1，则方程组三使用超松弛迭代法收敛，故可用超松弛迭代法求解。
调用超松弛求解线性方程组的程序，取初值x0=[0;0;0;0;0;0;0;0;0;0]，取ε=10-5，分别取ω=0.8，0.9，1，1.1，1.2时，可得到不同的解：
ω=0.8：
则x=[2.0000；1.0000；-3.0000；-0.0001；0.9999；-2.0000；3.0000；-0.0000；1.0000；-1.0000]，迭代次数k=12
ω=0.9：
则x=[2.0000；1.0000；-3.0000；-0.0000；1.0000；-2.0000；3.0000；-0.0000；1.0000；-1.0000]迭代次数k=10
ω=1：
则x=[2.0000；1.0000；-3.0000；-0.0000；1.0000；-2.0000；3.0000；0.0000；1.0000；-1.0000]迭代次数k=9
ω=1.1：
则x=[2.0000；1.0000；-3.0000；0.0000；1.0000；-2.0000；3.0000；-0.0000；1.0000；-1.0000]迭代次数k=9
ω=1.2：
则x=[2.0000；1.0000；-3.0000；0.0000；1.0000；-2.0000；3.0000；-0.0000；1.0000；-1.0000]迭代次数k=11
ω=1.3：
则x=[2.0000；1.0000；-3.0000；0.0000；1.0000；-2.0000；3.0000；-0.0000；1.0000；-1.0000]迭代次数k=13
当ω=1.1时，x=[2.0000；1.0000；-3.0000；0.0000；1.0000；-2.0000；3.0000；-0.0000；1.0000；-1.0000]，此时，迭代次数最少，并且与真值x*=（2,1,-3,0,1,-2,3,0,1,-1）T是相同的。
五、结果讨论与分析
1、迭代法与消去法的比较
在科学计算与工程设计中，我们常会遇到求解线性方程组的问题，对于系数矩阵为低阶稠密矩阵的线性方程组时，可以用列主元消去法进行消元。
而对于系数矩阵大型稀疏矩阵的情况，直接消去法就显得比较繁琐，而迭代法比较实用。
例如：
方程组二可以用高斯-赛德尔迭代法求解，方程组三可以用雅克比和高斯-赛德尔迭代法求解。
但是，当阶数比较高时，很难满足迭代法的收敛条件，此时只能用消去法进行求解，例如:
方程组一是十阶矩阵，不满足迭代法收敛的条件，故只能用消去法进行求解。
2、不同精度及初值对迭代法的收敛速度的影响
一般而言，所要求的精度越高，收敛速度越慢，即所需迭代的次数越多。
但是，所求结果也就越接近真实解。
例如，方程组二使用高斯-赛德尔迭代计算，精度越高，所需迭代次数就越多，迭代速度也就越慢，但是其解也越来越接近与真值。
当ε=10-5时，x2=[1.0160；-1.0188；0.0038；1.9917；1.0013；-1.0034；0.0008；1.9995]，这与真值x*=（1,-1,0,2,1,-1,0,2）T基本是相同的。
一般而言，初值的选取对迭代计算是没有影响的。
3、对方程组二、三使用SOR方法时，选取松弛因子ω=0.8，0.9，1，1.1，1.2等，试看对算法收敛性的影响，并能找出你所选用的松弛因子的最佳者。
松弛因子对算法的收敛性有一定的影响，由方程组二和方程组三可以看出，取不同的松弛因子ω时，会对迭代速度及解的准确性产生影响。
对于方程组组二，当ω取1.9时，可以使迭代次数最少并且使迭代解最接近于真解。
而对于方程组三，最佳松弛因子为ω=1.1。
升级会员 