超松弛迭代法中松弛因子_的选取方法.docVIP

()2006年2006青海师范大学学报自然科学版

第1期()No.1JournalofQinghaiNormalUniversityNaturalScience

ω超松弛迭代法中松弛因子的选取方

法

胡枫,于福溪

()青海师范大学计算机系,青海西宁810008

ω摘要:本文对线性方程组数值解法中的超松弛迭代法进行了算法分析,对于超松弛迭代法中松弛因子的选取提出了不同的几种方法,并对其中的逐步实验算法进行了分析与程序设计,使得超松弛迭代算法能在计算机上高效执行.

关键词:线性方程组;超松弛迭代法;松弛因子;程序;

()文章编号:1001-7542200601-0042-04中图分类号:TP301.6文献标识码:A

科学计算和工程设计中,经常会遇到求解线性代数方程组的问题,而且在计算方法的其它分支的研究也往往归结为此类问题,如何利用计算机求解线性方程组,是我们共同关心的课题.在计算机上求解

[1]线性代数方程组的数值解法有两类:一类是直接解法,就是指经过有限步运算求得方程组的解的一类方法,此类方法比较适应于系数矩阵稠密的中、小型线性方程组;另一类是迭代解法,适用于解大型、稀疏矩阵的线性方程组.超松弛迭代法是解线性方程组的迭代加速方法,是求解大型线性方程组的有效方

ω法之一,通过选择恰当的松弛因子,它能使收敛速度较慢的迭代法变的收敛快,使发散的迭代法可能变成收敛,因此超松弛迭代算法有极高的应用价值.

1超松弛迭代法算法

111基本概念

()超松弛迭代法简称为SORSuccessiveOver-Relaxation法,是求解线性代数方程组的一种迭代加

[1]k速方法,它是在高斯—塞德尔迭代法的基础上进行加速的,将前一步的结果x与高斯—塞德尔迭代i

()()k+1k+1[2]方法的迭代值x适当的加权平均,期望获得更好的近似值x.其迭代公式如下:iii-1nω()()()()k+1kk+1k)((ω)xax111(ax)i=1,2,,n;k=0,1,2,=1-x+b--ijjijjiii66aiij=1j=i

ωSOR法中的取值对迭代公式的收敛速度影响很大,它的好坏直接影响到加速的快慢.为了保证迭

[2]ωω代过程的收敛,必须要求02,超松弛法取12.但是在1和2之间仍然有很多的取值,究

ω竟如何取值没有统一的规定.作者经过多次的实验、分析与研究提出了选取的几种方法.

ω112松弛因子的选取方法

逐步实验法11211

ω()ω()将的取值区间1,2进行M等分,分别取1+1/M,1+2/M,,1+M-1M,通过公式111

ω依次对同一个精度要求求出迭代次数k的值,在求的同时比较出最少的迭代次数k,并将此次的值保

ω,1+M-1M中最优的的值.算法步骤如下:留,这样就得到了1+1/M,1+2/M,

第一步:给定M的值

()ω1+M-1/M按照公式,第二步:对于分别取1+1/M,1+2/M,i-1nω()()()()k+1kk+1ijkax(ω)ax(x)i=1,2,,n;k=0,1,2,=1-x+b--ijjijii66aiij=1j=i

根据给定的精度要求迭代,求出迭代次数k的值.

收稿日期:2005-04-16

作者简介:胡枫(1969-),女(土族),青海民和人,青海师范大学计算机系副教授,硕士,研究方向:数据挖掘与算法研究.

ω第三步:经比较,找出k值最小的确定为最优值.

11212折半查找法

ω()ω将松弛因子的区间1,2进行折半,每个小区间的长度为1/2,取其中点的值3/2,按照公式111

ω迭代,求出迭代次数k,如果k不超过指定的发散常数,则可确定的值,否则将分成的两个小区间再折

()ω半,即将1,