《基于重开始共轭思想的改进多项式插值法》-工学论文，软件工程论文-论文范文参考-科学狗论文网

网站首页词典首页

标题

基于重开始共轭思想的改进多项式插值法

范文

胡梦英++贺祖国

摘要：本文针对多项式插值逼近模型提出了一种改进的算法。新算法基于重开始共轭的思想，利用差商代替导数并构造共轭方向，保留了插值的优点，同时能提高运算效率，适用于导数信息不可用或是导数计算十分复杂的问题。实验结果表明，新算法是有效可行的。

关键词：无约束最优化；多项式插值；重开始共轭梯度法

中图分类号：0224

文献标识码：A

DOI： 10.3969/j.issn.1003-6970.2015.11.013

本文著录格式：胡梦英，贺祖国.基于重开始共轭思想的改进多项式插值法[J].软件，2015，36 （11）：48-51

0 引言

考虑无约束极小化问题

其中f：Rn→R二次连续可微。

解决上述问题的方法有直接法和使用导数的方法两种。

使用导数的方法是在算法的设计中借助目标函数的导数或二阶导数来构造下降的搜索方向。由于迭代时用到目标函数的梯度和二阶导数，每一次迭代为下一次迭代提供较多的信息量，所以使用导数的方法收敛速度都比较快。但是当函数的导数信息不可用或导数的计算十分复杂时，该类算法受限。典型的算法有最速下降法、牛顿法、共轭梯度法和拟牛顿法等。

直接法与使用导数的方法相比，算法设计中不用到目标函数的导数，只使用函数值，编程及算法的实现相对容易，适用范围广，迭代比较简单，具有良好的全局优化性等优点。但是，由于可用信息的减少，其实现难度也相应增加，所以直接法的收敛速度通常比较慢。经典的直接法有单纯形法、模式搜索法、RosenBrock法、Powell法等。

本文基于重开始共轭梯度法中共轭方向的构造原理，将其运用于多项式插值算法中得到重开始共轭插值法。新算法不使用导数，且相比于一次多项式插值，算法效率得到很大的提高。

1 重开始共轭梯度法

共轭梯度法是最优化问题中最常用的方法之一。它不仅是求解大规模线性系统的主要工具，而且很适合求解与非线性优化问题。

共轭梯度法的基本思想是把共轭性与最速下降方法相结合，利用已知点处的梯度构造一组共轭方向，并沿这组方向进行搜索，求出目标函数的极小点。共轭梯度法的迭代格式如下：

Xk+1=Xk+akdk

其中，步长ak是由某种线搜索产生，搜索方向dk的迭代格式如下：

重开始共轭梯度法是在迭代n步或n+1步之后，重新取负梯度方向作为搜索方向。这是因为对于一般非二次函数而言，n步迭代后共轭梯度法产生的搜索方向往往不再具有共轭性。

2 多项式插值法

多项式插值法属于直接法，其主要思想是用插值的方法来构造目标函数的多项式逼近模型，计算过程中不需要函数的导数信息，而是使用差商代替导数。适用于导数不存在或是导数计算十分复杂的目标函数。插值函数类通常可选取一次多项式函数、二次多项式函数和不含交叉项的二次函数。本文使用一次多项式插值模型逼近目标函数。

4.1 选用的测试函数

本文选取两个可变维数的测试函数。函数一：

从表中结果分析：无论对于一些维数很大的大型测试问题，还是次数较高的函数来说，重开始插值共轭法具有良好的计算效能。相比于单纯的线性插值法，重开始插值共轭法的迭代次数少，运行时间短，并能收敛到很高的精度，误差小。

5 结论

本文提出的重开始插值共轭算法结合了一次多项式插值法和重开始共轭梯度法的优点。当导数信息不可用时或导数的计算十分复杂时，本算法有极大的优势，同时又利用了重开始共轭思想，可以有效地提高算法效率。数值结果也说明了新算法是一种有效可行的方法。

随便看

科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。