雅可比迭代法和高斯超松弛迭代
更新时间:2023-07-18 04:02:01 阅读量: 实用文档 文档下载
本文主要介绍两种最常用的代数方程组迭代求解方法,原理即其使用方法
雅可比迭代法和高斯-赛德尔迭代法以及超松弛迭代
对于给定的方程x Ax b用下式逐步代入求近似解的方法称为迭代法。如xk(当k )的极限存在,此极限即方程组的真正解,此迭代法收敛,否则称迭
代法收敛。
x
k 1
A
xk
b
k 0,1,2...1、雅可比(Jacobi)迭代法
设有方程组
Ax=b (56)
其展开形式为
a11 a1n x1 b1
(57) a n1 ann x n b n
系数矩阵A为非奇异阵,且aii 0(i=1-n)A可分解为 A=D+A0 (58)其中:
0 a1n
D a110
A 0
0 a nn
a
m1 0
改写线性方程组(57)式,将第i个方程(i=1~n)表示为xi的表达式:n
x1
i a(bi aijxj) (59)
iijj 1
i
改写后的(57)式的矩阵表达式为:
本文主要介绍两种最常用的代数方程组迭代求解方法,原理即其使用方法
x Ax b(60)其中
很容易看出(56)式和(60)式间系数矩阵A与在如下关系
及自由项列阵b与之间存
(61)
用迭代法解(60)式,其迭代公式为
(62)
初始向量为x0。此法称雅可比迭代法,代次数。雅可比迭代法的分量形式为
称为雅可比迭代法的迭代矩阵。k为迭
(63)
雅可比迭代法分量形式(63)式也可改写为
(64)
本文主要介绍两种最常用的代数方程组迭代求解方法,原理即其使用方法
(64)式更方便于编程求解。
雅可比迭代法公式简单,迭代思路明确。每迭代一次只需计算n个方程的向量乘法,程序编制时需设二个数组分别存放xk和xk+1便可实现此迭代求解。
2、高斯-赛德尔(Gauss-seidel)迭代法
由雅可比迭代法可知,在计算xk+1的过程中,采用的都是上一迭代步的结果xk。考察其计算过程,显然在计算新分量xik+1时,已经计算得到了新的分量,
。有理由认为新计算出来的分量可能比上次迭代得到的分量有所
改善。希望充分利用新计算出来的分量以提高迭代解法的效率,这就是高斯-赛德尔迭代法(简称G-S迭代法)对(64)式进行改变可以得到G-S迭代法的分量形式
(65)
G-S迭代法的分量形式亦可表示为
(66)
(65)式也可写成矩阵形式。方程组的系数A在(58)式基础上还可进一步分解,若将A0继续分解为一个下三角阵A0L和一个上三角阵A0U ,则系数矩阵的分解则可表达为
(67)
其中:
(68)
本文主要介绍两种最常用的代数方程组迭代求解方法,原理即其使用方法
(65)式可写成矩阵形式
按向量的迭代次数归并可得
若(D+
)的逆存在,则有
高斯-赛德尔迭代的矩阵形式可表达为
(69)
高斯-赛德尔迭代法每步迭代的计算量与雅可比迭代相当,但在计算机进行计算时,只需存放x一个数组。
用迭代法求解时要注意迭代法的收敛性①。无论是用雅可比迭代法或高斯-赛德尔迭代法都存在解的收敛问题,甚至有的线性方程组,用雅可比迭代法解是收敛的,而用高斯-赛德尔迭代法解却是发散的。反之亦然。
当线性方程组(56)中的系数矩阵A(n阶矩阵)为严格对角优势矩阵,即A的每一行对角元素的绝对值都严格大于同行其它元素之和:
则可证明上述二种迭代法收敛。
定理 如果线性方程组的系数矩阵A为严格对角优势矩阵,则对求解线性方程组Ax=b的雅可比迭代法和高斯-赛德尔迭代法均收敛。
本文主要介绍两种最常用的代数方程组迭代求解方法,原理即其使用方法
有限单元法的求解方程Ka=P中,系数矩阵K具有主元占优的特点,但却不能保证是严格对角优势矩阵,因此采用雅可比迭代法时要注意解的收敛问题。高斯-赛德尔迭代法的收敛性要求在下一节超松弛迭代法时一并讨论。
2、逐次超松弛迭代法
逐次超松弛迭代法(Successive Over Relaxation Merhod,简称SOR法)是高斯-赛德尔迭代法的一种加速收敛的方法。是大型稀疏矩阵线性方程组的有效解法之一。首先用另一种变换形式讨论一下迭代过程。对于(56)式的线性方程组
Ax=b
当系数矩阵主元aii=1(I=1,2,..,n)时将式中系数矩阵分解为
(70)
则可(56)式的等价方程组
(71)
它的迭代公式为
当进行了k次迭代得到xk后,xk一般地与真解x间仍存在差异。如何改进xk得到下一次迭代的结果xk+1,可以引入xk的剩余向量rk
(73)
此时,迭代公式(72)可表示为
(74)
由此可见应用迭代法得到逐次改进的解xk+1,实质上是用k次迭代后的剩余向量rk来改进解的第k次近似rk。因此可以引进一个加速迭代的模式来改进迭代法。令
(75)
本文主要介绍两种最常用的代数方程组迭代求解方法,原理即其使用方法
其中ω称为松弛因子。
式(75)是迭代公式(74)的一个改进,可以选择松弛因子ω加速迭代过程的收敛。式(75)的分量形式为
(76)
若对上述改进的迭代公式,按高斯-赛德尔迭代法尽量利用最新迭代得到的分量的原则,又可得到新的迭代公式
(77)
当线性方程组的系数矩阵A具有非零主元(aii≠0,i=1,2,3,…n)的特点时,可以得到主元为1的方程组形式
(78)
此时迭代公式(77)可改写为
(79)
bi aijxjaii j 1
xixi
k 1
xi
k
k
i 1
k 1
aijxjk j 1
n
k 1
xik 1
i 1n
k 1
xi bi aijxj aijxjk
j 1aiij 1aii aii na bii 1aijk 1 ij k
1 xj xj
j 1aii aiij 1aii
迭代公式(79)式称为松弛因子迭代法。当 =1,(79)式就是高斯-赛德尔迭
代法;当ω<1时(79)式称为低松弛法;当ω>1时(79)式称为超松弛法,即SOR方法。由于加速迭代收敛一般选取ω>1,因此(79)式一般称为超松弛迭代法(SOR方法)。
本文主要介绍两种最常用的代数方程组迭代求解方法,原理即其使用方法
可以证明如果线性方程组的系数矩阵A为对称正定矩阵。ω的选取0<ω<2时,则解方程组的SOR方法一定收敛。由于有限单元法的求解方程其系数矩阵具有对称、正定的特点,因此SOR方法是迭代求解的一种常见方法。
用超松弛迭代法求解时,应选择超松弛因子,适当的超松弛因子将会加快收敛速度。
超松弛因子一般可取1.2左右。
超松弛代法和高斯-赛德尔迭代要优于雅可比迭代。而由于选择了超松弛因子ω,一般超松弛迭代效率要高于高斯-赛德尔迭代。超松弛因子无法事先确定最优值,可在迭代过程中根据收敛速度进行调整。
用超松弛迭代法求解思路明确,编程简单,存储迭代解xk只需一个数组。但需注意超松弛因子的选择。
在用迭代法求解有限元方程时,仍需按系数矩阵(刚度矩阵)在计算机内的存储方式,与直接解法中的高斯消去法和三角分解法所讨论的相似,考虑系数矩阵特点,修改(79)式中元素的下标及迭代涉及的元素。如采用雅可比迭代或高斯-赛德尔迭代时,也应作此修正。读者可以进行修改并验证。 附程序
#include<iostream> #include<math.h> #include<iomanip> using namespace std;
#define kk 50 //定义最大方程元数 #define exp 1e-5//定义结束门限值 int n,ll,hh,i,j;
double A[kk][kk],x[kk][kk],b[kk],y[kk],a[kk],z[kk],m,nn,d,e=1,w; void main() {
cout<<"
**********************************************************************"<<endl; cout<<" ***本程序可以用雅可比迭代法,塞德尔迭代法,逐次超松弛法求解线性方程组***"<<endl; cout<<" ***************************制作人:李小龙*****************************"<<endl;
cout<<" ***********************说明:方程最多个数为**************************"<<endl; cout<<"
**********************************************************************"<<endl; //*********************************数据的输入******************************** bb:cout<<"输入的方程元数"<<endl;
本文主要介绍两种最常用的代数方程组迭代求解方法,原理即其使用方法
cin>>n;
cout<<"请输入方程系数矩阵:"<<"\n"; for(i=0;i<n;i++) for(j=0;j<n;j++) cin>>A[i][j];
cout<<"请输入右边向量:"<<"\n"; for(i=0;i<n;i++) cin>>b[i];
//*******************************判断是否对角占优************************* for(i=0;i<n;i++) {
for(j=0;j<n;j++) {
nn=0; if(i==j) {
d=fabs(A[i][i]); } else
nn=nn+fabs(A[i][j]); }
if(nn>d) {
cout<<"该方程不对角占优,迭代不收敛"<<endl; cout<<"是否继续?是(),否()"<<endl; cin>>hh; if(hh!=1) goto bb; else exit(1); } }
//********************************计算出迭代矩阵************************* for(i=0;i<n;i++) {
b[i]=b[i]/A[i][i];
for(j=0;j<n;j++) {
if(i==j) {
x[i][i]=0; } else {
本文主要介绍两种最常用的代数方程组迭代求解方法,原理即其使用方法
x[i][j]=-A[i][j]/A[i][i]; } } }
//*******************************输出迭代矩阵***************************** cout<<"计算出迭代矩阵为:"<<endl; for(i=0;i<n;i++) {
for(j=0;j<n;j++)
cout<<x[i][j]<<" "; cout<<b[i]<<" "; cout<<endl; }
//****************************迭代方法的选择***************************** cout<<"请你选择迭代方法!"<<endl; cout<<endl; cout<<endl;
cout<<"选用雅可比迭代法,请输入()!"<<endl; cout<<endl; cout<<endl;
cout<<"选用塞德尔迭代法,请输入()!"<<endl; cout<<endl; cout<<endl;
cout<<"选用逐次超松弛法,请输入()!"<<endl; cout<<endl; cout<<endl; cin>>ll;
//*****************************赋迭代初值*********************************** for(i=0;i<n;i++) {
y[i]=1; z[i]=1; }
int f=1; switch(ll) {
case 1:goto cc; break;
case 2:goto aa; break;
case 3:goto dd; }
//***************************雅可比迭代法************************************ cc:while(e>exp)
本文主要介绍两种最常用的代数方程组迭代求解方法,原理即其使用方法
for(i=0;i<n;i++) {
z[i]=y[i]; nn=0;
for(j=0;j<n;j++) {
nn=nn+x[i][j]*z[j]; y[i]=nn+b[i]; }
e=fabs(z[i]-y[i]); if(i==0) {
cout<<"第"<<f++<<"次迭代"; }
cout<<setw(8)<<setprecision(8)<<y[i]<<" }
cout<<endl; }
cout<<endl; cout<<endl;
cout<<"最后结果为:"<<endl; cout<<endl; for(i=0;i<n;i++) {
cout<<"X"<<"["<<i<<"]"<<"="<<y[i]; cout<<endl; }
exit(1);
//******************************************************************* aa: while(e>exp) {
for(i=0;i<n;i++) {
z[i]=y[i]; nn=0;
for(j=0;j<n;j++) {
nn=nn+x[i][j]*y[j]; y[i]=nn+b[i]; }
e=fabs(z[i]-y[i]); if(i==0)
"; 塞德尔迭代法
本文主要介绍两种最常用的代数方程组迭代求解方法,原理即其使用方法
cout<<"第"<<f++<<"次迭代"; }
cout<<setw(8)<<setprecision(8)<<y[i]<<" "; }
cout<<endl; }
cout<<endl; cout<<endl;
cout<<"最后结果为:"<<endl; cout<<endl; for(i=0;i<n;i++) {
cout<<"X"<<"["<<i<<"]"<<"="<<y[i]; cout<<endl; }
exit(1);
//******************************************************************* dd: cout<<"输入加速因子W:"<<endl; cin>>w;
while(e>exp) {
for(i=0;i<n;i++) {
z[i]=y[i]; nn=0;
for(j=0;j<n;j++) {
nn=nn+x[i][j]*y[j];
y[i]=(1-w)*z[i]+w*(nn+b[i]); }
e=fabs(z[i]-y[i]); if(i==0) {
cout<<"第"<<f++<<"次迭代"; }
cout<<setw(8)<<setprecision(8)<<y[i]<<" }
cout<<endl; }
cout<<endl; cout<<endl;
cout<<"最后结果为:"<<endl;
逐
次
"; 超
松
弛
法
本文主要介绍两种最常用的代数方程组迭代求解方法,原理即其使用方法
cout<<endl; for(i=0;i<n;i++) {
cout<<"X"<<"["<<i<<"]"<<"="<<y[i]; cout<<endl; }
exit(1); }
//******************************************************************************
程
序
结
束
正在阅读:
雅可比迭代法和高斯超松弛迭代07-18
变得和姚明一样高大作文550字07-13
化学反应过程与设备(反应器设计和优化)05-14
绿色消费的伦理价值09-01
修改完 防水方案12-01
乡镇上半年市委农工部年度工作总结报告08-04
门当户对辩论的例子02-03
- 教学能力大赛决赛获奖-教学实施报告-(完整图文版)
- 互联网+数据中心行业分析报告
- 2017上海杨浦区高三一模数学试题及答案
- 招商部差旅接待管理制度(4-25)
- 学生游玩安全注意事项
- 学生信息管理系统(文档模板供参考)
- 叉车门架有限元分析及系统设计
- 2014帮助残疾人志愿者服务情况记录
- 叶绿体中色素的提取和分离实验
- 中国食物成分表2020年最新权威完整改进版
- 推动国土资源领域生态文明建设
- 给水管道冲洗和消毒记录
- 计算机软件专业自我评价
- 高中数学必修1-5知识点归纳
- 2018-2022年中国第五代移动通信技术(5G)产业深度分析及发展前景研究报告发展趋势(目录)
- 生产车间巡查制度
- 2018版中国光热发电行业深度研究报告目录
- (通用)2019年中考数学总复习 第一章 第四节 数的开方与二次根式课件
- 2017_2018学年高中语文第二单元第4课说数课件粤教版
- 上市新药Lumateperone(卢美哌隆)合成检索总结报告
- 高斯
- 迭代法
- 迭代
- 松弛
- 可比
- 伦理视角下企业管理中的公正问题
- 科技英语文献翻译英文资料原文
- j.1467-9701.2009.01184.x
- 冬小麦冠层光谱的方向性特征分析
- 中央电大历届管理学基础试题库试卷代号2064
- 八下第五单元练习
- 宁波市城市更新研究报告
- 女孩子爱上你的十五种情感表现
- 石家庄某公司人力资源管理制度
- 毛城小学二年级后进生转化工作计划
- 八年级上册语文文言古诗专题复习
- 责任护士心得体会
- 新视野大学英语第三版读写教程第四册课文翻译
- 南康市职业中专2013年学校工会工作计划
- 鲁教版小学四年级上册语文第二单元测试题
- 云南省临沧市八年级下学期数学期末考试试卷
- 从“老鼠爱大米”说起
- 学生知识竞赛试题综合题库
- ASN.1编解码模块在LTE协议栈中的研究与应用
- 2011考研时事政治