当前位置:首页 >> 能源/化工 >>

求解病态线性方程组的模拟退火算法


第25卷第4期 2009年8月









V01.25.№.4
Aug.2009

COLLEGE MATHEMATICS

求解病态线性方程组的模拟退火算法
王福昌,

胡顺田

/>
(防灾科技学院基础部,河北三河065201)

[摘要]病态方程组的条件数较大,当输入数据有微小扰动或计算过程中的舍入误差都可能引起输出 数据的很大扰动,使得解严重失真,因此求解此类方程组是相当困难的.本文尝试使用模拟退火算法来求解病 态线性方程组,得到了较好的结果,并与传统的求解方法作了简单的比较. [关键词]线性方程组;病态方程组;模拟退火算法 [中图分类号]0241.6 [文献标识码]A [文章编号]1672—1454(2009)04—0069—04







在图像处理、反演问题、模型参数估计等许多领域都需要求解病态线性方程组,但是由于病态方程 组的条件数较大,输入数据有微小扰动或计算过程中的舍人误差都可能引起输出数据的很大扰动,即问 题的解很不稳定,因此求解此类方程组是相当困难的u]. 考虑如下形式的线性方程组
Ax—b。 (1)

其中A为挖阶非奇异方阵,x和b为咒维向量. 当系数矩阵A的条件数很大时,计算中的舍入误差常常造成解的巨大误差,这时方程组称为病态 方程组.常规的一些方法,如均衡处理、选主元法等,对病态问题几乎无能为力.方程组的病态问题严重 影响了计算结果的准确性和可靠性,人们一直在寻找有效的解法.现在已有的很多解法,如条件预优法、 迭代校正法、投影法、递推法、刚性常微分方程法、遗传算法[1’23等等.从算法的简便性、有效性上看,很 多并不理想.如有的算法有效性较好但比较复杂;有的算法实际上只能处理病态程度不太严重、问题规 模较小的问题,当问题的规模增大、病态程度加剧时,解的精度会十分明显甚至急剧下降等等[2。]. 本文使用文献E4]提出的模拟退火算法思想,针对病态方程组,给出了具体的求解步骤,并在 MATLAB环境下编程,针对经典的两个病态方程组进行了测试,得到了理想的结果.

2模拟退火算法原理
高温状态下的物质降温时其内部能量随之下降,如果降温过程充分缓慢,则在降温过程中物质体系 始终处于平衡状态,从而降到某一低温时,其内能可以达到最小,称这种降温为退火过程.模仿退火过程 的寻优方法称为模拟退火算法(Simulated
Annealing

Algorithms,SAA),它能够以随机搜索技术从概

率的意义上找出目标函数的全局最小点.模拟退火算法包含的基本步骤如下[5酒]: (i)随机给定初始状态T0和初始点‰,计算该点的函数值f(x。),设定合理的退火策略; (ii)对系统状态进行随机扰动厶,得到新点工7=工+△,重新计算f(x7)和差zaf=f(x7)--f(x);
[收稿日期]2007一01—15; [修改日期]2007—04—25

[基金项目]防灾科技学院教学建设与教学研究项目(08A07)

万   方数据

70









第25卷

(iii)若Aft0,则接受新点,作为下一次模拟退火的初始点; (iv)若Af>0,则计算新点的接受概率P(Af,T)=exp(--Af/(K?Tj),产生[o,1]之间均匀分布 的为随机数,..若P≤r,则接受新点,作为下一次模拟退火的初始点,否则仍取原来的点作为下一次模拟 退火的初始点.以上步骤称为Metroplolis过程; (v)按照降温规则逐渐降低控制温度,增加迭代次数,直至达到结束准则,停止迭代.否则返回(ii). 在具体应用时,对不同的问题设计不同的更详细的计算规则.

3用模拟退火算法求解线性方程组
要使用模拟退火算法来求解此方程组,首先要把问题(1)转化为一个函数优化问题,为此构造如下 的优化问题
minf(x)一(A工一6)丁(A工一6),x6风”.
(2)

易见,f(x‘)=0舒Ax。=b,即z’是方程组Ax=b的解. 按照模拟退火算法的一般原理,结合上面的问题,给出求解病态方程组问题的具体步骤: (i)选取初始温度丁0和最低温度丁,,每一温度下的迭代次数L。。,邻域规模因子scale或正态分布 标准差盯,温度下降因子口.给定问题(2)的初始近似的解粕,计算E(x。)=0 Axo一6 Il;. (ii)对于高维连续函数,每次更新只在一个方向上产生随机扰动优于在多个方向上同时产生扰动, 新解可以以不同的概率分布产生L4].假设从当前解x一(z。,z:,…,z。)丁中随机选取一个分量z,,产生 随机扰动z,7=z,+△,其中△是整个实轴上服从正态分布N(o,盯2)的随机变量或者限制在当前解分量 的一个邻域范围内,即A—scale×(rand一0.5),其中rand为0,1之间的一个随机数.计算E(z7) 一||Ax7一b||i和△E—E(x7)一E(工).

(iii)如果AE<O,那么接受/为新的近似解.否则随机选取口∈[o,1],计算P=i/(1+exp(z姬/T)).如
果P>口,则仍接受√为新的近似值,否则仍取近似解为_ (iv)重复(ii),(iii)步,实施温度下降服从丁一T。exp(一ck)(惫为迭代次数)的降温策略,直至到达 最低温度T,或满足E(x)<e,其中£为预先给定的充分小的正数.

4算例及计算结果
为了检验本文方法的有效性,本文选取如下3个典型问题进行计算:


例1 例2

aij一再末i,i,J一1,2,…,,z.
‘‘J ‘

alj一1,a,l=1,J一1,2,…,以. ad=口卜一l,』+ai.J—l,i,歹22,3,…,,2.

例3

a“一max(i,J),i,J一1,2,3,…,,2.

以上3例中,例1的系数矩阵为Hilbert矩阵,例2的系数矩阵为Pascal矩阵.当咒一20时,条件数 分别为1.9084×1018和2.0959×1020,可见它们是典型的病态矩阵.例3中当咒一20时,条件数为 1.1425×103,是良态方程组.由于系数矩阵病态时,方程组的计算解未必会有很大误差口],因此右端项 的取法不能太特殊,否则这样的算例难以说明算法的有效性.这里将3个例子右端项分别取为6f

一芝:口口(i一1,2,…,咒),显然精确解为工一(1,1,…,1)1’.
jj

』一

对上面两个病态例子,如果采用常用的经典算法求解,可以看到: (i)LU分解方法:随着系数矩阵阶数咒的增大,LU方法所求的解与精确解的误差愈来愈大.以矩 阵阶数n为横坐标,数值解与精确解误差向量的1-范数为纵坐标,见图1. (ii)Jacobi方法:当n一20时。Jacobi迭代矩阵谱半径分别为18.4921,10.5115和35.4303,均大于 1,故Jacobi方法不收敛.

万   方数据

第4期

王福昌,等:求解病态线性方程组的模拟退火算法

71

写 童



椭 黪



矩阵阶数n

矩阵阶数n

图1使用LU分解方法求解例1和例2时的误差图像

(iii)GS方法:当靠一20时,GS迭代矩阵谱半径分别为0.9074,0.7958和2.9067,例1和2的谱半 径较大,收敛速度较慢,例3不收敛. (iv)SOR方法:SOR方程与GS方法类似,当松驰因子∞一0.8时,其迭代矩阵的谱半径分别为 0.8659,0.7128和2.9440.例1和2的谱半径较大,收敛速度较慢,例3不收敛. (v)模拟退火方法:取初始温度To一1000和最低温度TI一0.0001,每一温度下的迭代次数 L。,一50,邻域规模因子scale----0.01,温度下降因子c一0.01,温度下降规律服从T—Toexp(--ck),k为 迭代次数.

图2使用GS与SOR方法求解例1和例2时迭代矩阵的谱半径

图2给出了使用GS和SOR方法求解例1和例2时迭代矩阵的谱半径随着矩阵阶数的变化情况, 其中◇和△分别对应例1和例2中迭代矩阵的谱半径. 上面3个例子的数值实验结果,见表1.例1至例3中使用各种算法的花费时间和数值解与精确解 误差向量的1一范数依次用逗号隔开,测试矩阵A均为20阶方阵.
表1数值实验结果

从前面的结果可以看出,本文提出的算法除了在计算时间方面花费较多外,在适用范围,计算精度 上均优于传统的矩阵分解和迭代算法.笔者的计算机配置为Pentium IV3.0G,512MB内存,
MATLAB 7.1环境,计算结果均在此环境下做出.

万   方数据

72









第25卷

5讨



模拟退火算法参数的选择对于其求解的有效性至关重要,这里对于变量X的维数行较大时,每次只 对X的一个分量进行扰动.如果一次对多个分量进行扰动,则由于很难在多个方向上同时达到极小点, 效率会大大降低,笔者的数值试验也证明了这一点.另外,模拟退火初始点的选择和问题的复杂性本身 对算法的有效性也有一定的影响,在最优点附近如何结合局部化策略,提高算法收敛的速度和精度,这 些都是有待进一步研究的问题. [参 考


献]

1-13黄松奇,黄守佳.用遗传算法求解病态线性方程组[J].数学的实践与认识,2003,33(8):97—100. [2] 胡圣荣,罗锡文.病态线性方程组的新解法:误差转移法[J].华南农业大学学报,2001,22(4):92—94.

[3]史文谱,刘迎曦,李翠华,等.黄金分割法在求解线性方程组中的应用[J].大学数学,2003,19(3):77—81. [4]靳利霞,唐焕文,李斌,等。一类连续函数模拟退火算法及其收敛性分析[J].计算数学,2005,27(1):19—30. [5] 刘怀亮.模拟退火算法及其改进[J].广州大学学报(自然科学版),2005,4(6):503—506. [6]项宝卫,余学芬,骆兆文.模拟退火算法在优化中的研究进展[J].台州学院学报,2005,27(6):6—9. [7]胡圣荣,罗锡文.病态线性方程组的一种特殊情况[J].华中农业大学学报,1999,18(1):98—99.

Simulated Annealing Algorithm for Solving
WANG
Fu—chang。

lII—conditioned Linear Systems

HU Shun—tian

(The Institute of Disaster-Prevention Science and Technology,Sanhe,Hebei 065201,China)

Abstract:The ill—conditioned condition number of these systems In this article,the

linear
so

systems is

very

difficult
error

to

be

solved using traditional methods,because
cause

the

large that the little

of input data may be
to

the large

error

of

output

data.

simulated annealing algorithms(SAA)is presented

solve these

systems.By compared with the

traditional methods。a good solution is obtained. Key words:linear system;ill—conditioned linear system


simulated annealing algorithm

万   方数据

求解病态线性方程组的模拟退火算法
作者: 作者单位: 刊名: 英文刊名: 年,卷(期): 王福昌, 胡顺田, WANG Fu-chang, HU Shun-tian 防灾科技学院,基础部,河北,三河,065201 大学数学 COLLEGE MATHEMATICS 2009,25(4)

参考文献(7条) 1.胡圣荣;罗锡文 病态线性方程组的一种特殊情况[期刊论文]-华中农业大学学报 1999(01) 2.项宝卫;余学芬;骆兆文 模拟退火算法在优化中的研究进展[期刊论文]-台州学院学报 2005(06) 3.刘怀亮 模拟退火算法及其改进[期刊论文]-广州大学学报(自然科学版) 2005(06) 4.靳利霞;唐焕文;李斌 一类连续函数模拟退火算法及其收敛性分析[期刊论文]-计算数学 2005(01) 5.史文谱;刘迎曦;李翠华 黄金分割法在求解线性方程组中的应用[期刊论文]-大学数学 2003(03) 6.胡圣荣;罗锡文 病态线性方程组的新解法:误差转移法[期刊论文]-华南农业大学学报(自然科学版) 2001(04) 7.黄松奇;黄守佳 用遗传算法求解病态线性方程组[期刊论文]-数学的实践与认识 2003(08)

本文链接:http://d.g.wanfangdata.com.cn/Periodical_dxsx200904014.aspx


相关文章:
关于病态线性方程组解法的开题报告
(5)求解病态线性方程组的混合算法:首先通过变分原理将求解线性方程组 的问题转化为等价的求解无约束函数最优化问题的极小值。通过研究 BFGS 算法 和模拟退火算法的...
病态线性方程组的求解
本文的算法迭代虽能保证收敛,但与精确解误差到底怎样,还应将解代入 原方程,衡量、检验求得解可信程度;另外,如何克服求解病态线性方程 组收敛缓慢的问题,还有...
模拟退火算法基本原理介绍
二、模拟退火算法的模型 模拟退火算法可以分解为解空间、目标函数和初始解三部分。 模拟退火的基本思想: (1) 初始化:初始温度 T(充分大),初始解状态 S(是算法...
模拟退火算法解决TSP问题
模拟退火算法解决TSP问题_计算机软件及应用_IT/计算机_专业资料。模拟退火算法解决...的计算 过程简单,通用,鲁棒性强,适用于并行处理,可用于求解复杂的非线性优化问...
模拟退火算法简介与实例
模拟退火算法由于要计算相临状态,这与 Ising 模拟的计算模拟有相似之处,因此本文 也将对 Ising 做一个介绍。本文介绍算法的基本思想并做一个例子求解 TSP 问题(...
模拟退火算法
[键入文字] [键入文字] 模拟退火算法摘要:本文采用一种模拟退火算法(SAA) ,通过对热力学中退火过程的模拟,寻找全局 极小值,可望在较短时间里求得更优近似解。...
模拟退火算法求解TSP问题
模拟退火算法求解TSP问题_院校资料_高等教育_教育专区。毕业论文设计 模拟退火算法在 TSP 问题中的应用研究 摘要 旅行商问题, TSP 问题 即(Traveling Salesman ...
模拟退火算法及其Matlab实现
模拟退火算法及其Matlab实现_IT/计算机_专业资料。...与求解 线性规划的单纯形法、Karmarkar 投影尺度法,...退火算法解非线性方程组... 3页 免费 模拟退火算法...
基于模拟退火算法的旅行商问题求解
13 I 基于模拟退火算法的旅行商问题求解光信息科学与技术 指导教师 董铸祥 张明强 摘要: 易于描述却难以处理的 NP 难题, 其可能的路径 摘要 旅行商问题是组合...
更多相关标签:
病态线性方程组求解 | 病态线性方程组的求解 | 求解病态潮流常用算法 | 求解病态潮流的算法 | 病态线性方程组 | 病态线性方程组的解法 | 病态方程组求解 | matlab病态方程组求解 |