一种求解非线性方程组的修正...g-Marquardt算法_韩扬.pdf

第 卷 第期 年 月青 岛 大 学 学 报（自 然 科 学 版）（）文章编号：（）：一种求解非线性方程组的修正 算法韩扬，芮绍平（淮北师范大学数学科学学院，淮北 ）摘要：通过修改 （）参数，结合信赖域方法给出一种新的求解方程组的算法。在局部误差界条件下，证明了该算法具有局部快速收敛性。数值实验结果表明，此算法稳定、有效。关键词：算法；方程组；参数；局部快速收敛性中图分类号：文献标志码：收稿日期：基金项目：安徽省高等学校自然科学研究项目（批准号：）资助；淮北师范大学实验室开放项目（批准号：）资助。通信作者：芮绍平，男，博士，教授，主要研究方向为最优化理论与算法。：非线性方程组在电学、力学、经济管理、工程技术、生物医学、运筹优化等方面有着广泛的应用。本文主要讨论非线性方程组（，）（，）（，）（）向量形式为（）（）其中，（，），（）：，连续可微，式（）的解集记为，现假设非空。求解非线性方程组的迭代方法有很多，其中高斯牛顿法是经典的方法之一，然而，在实际计算中，当雅可比矩阵奇异或充分接近奇异时，高斯牛顿方法试探步出现无法求解的困难，（）方法是高斯牛顿方法的一种改进，在第次迭代时，计算试探步（）（）其中，（），（）是（）在处的雅可比矩阵，表示转置，是单位矩阵，是 方法的迭代参数，当奇异或接近奇异时，引入的克服了迭代步无法求解的困难。若非线性方程组（）对应的雅可比矩阵（）是 连续的且非奇异的，初始点接近式（）的解，并且在选取合适的情况下，方法与高斯牛顿方法一样具有二次收敛性。由于雅可比矩阵（）非奇异这一条件过强，文献 选择，并利用局部误差界条件证明了 方法具有二次收敛性。在本文中，表示范数。方法中，参数对方法的有效性具有重要作用，有很多研究对做了一些探讨 。文献 在文献 的基础上继续改进，取，数值效果得到改善；文献 用凸组合形式将文献 和文献 中的参数结合起来，数值效果得到进一步改善；文献 取，其中由信赖域技术更新，缓解当初始点远离解集时的困难。第期韩扬等：一种求解非线性方程组的修正 算法考虑到当序列 远离解集时，可能较大，进而导致参数过大，使计算效率降低，本文构造（），若（），其他（）其中，每步由信赖域策略更新，当序列 靠近解集时，趋近于，接近于，当时，接近于，当序列 远离解集，非常大时，接近于，使的取值范围得到了有效的控制，避免迭代步过小，进而提高计算效率。特别地，当，时，该参数即为文献 中所提出的参数，即是本文构造的一种特殊形式。基于修正的方法取（）（）为非线性方程组（）的价值函数，则（）第次迭代时的实际下降量和预估下降量为：（），其中，（）为 方法的试探步，比率 确定和参数的更新。在实际应用中，由于非单调线搜索技术效果较好 ，本文利用非单调技术并取实际下降量?（）（），其中（）（），；（），为正整数。经过这种处理，每次迭代时，比较（）与 （），新的比率为?，代替原比率在算法中的作用，下面给出基于修正的算法，即 算法。算法 给定，：；如果，则停止计算；否则，转 ；计算（），其中取式（）；计算?，令，?，?计算，?，?，?令：，转 。在 算法中，是给定的常数且为的下界，当迭代序列接近解时，能防止试探步过大带来的数值困难。收敛性分析定义设，且，若存在常数（），使得（）（，），（）其中，（，），则称（）在上满足局部误差界条件。假设（）设（）连续可微，（）在（，）为非线性方程组（）提供了局部误差界，其中，（，），；青 岛 大 学 学 报（自 然 科 学 版）第 卷（）（），（）在（，）上是 连续的，存在，和使得（）（），（，）（）（）（），（，）（）进而有（）（）（）（），（，）（）引理若假设成立，（，），对所有充分大的，有（）存在，使得；（）存在，使得?，其中 （），；（）存在，使得?，?（），其中，。证明：引理（）的证明与文献 类似，不再赘述，下面证明（）和（）。先证（），若，则，那么，此时（）（）（?）当?充分小，存在，使得（?）?。若，则，那么，由式（），得（）（）?）综上，对所有充分大的，有?。再证（），若，由引理（）及式（），得（）（）?若，则，由引理（）及式（），得（）（?）?（）综上，对所有充分大的，有?，?（）。引理若假设成立，对所有充分大的，有（?）。证明：令（），由式（）可知，算法产生的是（）的极小点，再由式（）及引理（）得（?）（?）?）（?）?（?）?（?）故（?）。用奇异值分解该技术证明 算法的局部收敛性。设（?）的奇异值分解为第期韩扬等：一种求解非线性方程组的修正 算法（?）?，?其中，（?，?，?），?，（）。同理，设（）的奇异值分解为（），?（）其中，（，），（，），。根据矩阵摄动定理，因为（）是 连续的，得 （，）?，则?，?（）又因序列 收敛于，假设对所有充分大的，有?，再结合式（）有?（）引理在假设成立下，对所有充分大的，有（）（?）；（）（?）；（）（?）。定理当假设成立，若，则 算法产生的 二阶收敛于式（）的解；若，则 算法产生的 线性收敛于式（）的解。证明：若，由式（）和式（），有（）（）（）（）（）（）由引理（）、引理和式（）可得?（?）（?）（?）（?）（）由式（）、式（）、式（）、式（）及引理，有?（）（）（?）（）此外，有?（，）?（）再由式（）和引理，对任意充分大的，?（?），所以，（?）。结合式（），当，则（），二阶收敛于非线性方程组（）的解。若，则 算法产生的 线性收敛于非线性方程组（）的解，证明方法及过程与，时类似。数值实验数值实验时，参数为：，或，青 岛 大 学 学 报（自 然 科 学 版）第 卷停机准则为 或迭代次数超过 （）。具体结果见表，其中取标准测试函数的初始点，“”为函数的计算次数，“”为雅可比矩阵的计算次数，“”为函数的范数的最终值，“”为问题的计算时间，单位为秒（），“”表示为迭代次数超过 （）或算法失败，表中的第四列表示初始点的选取分别为，及 。所有算法均在 且配置为 ，位 的计算机上运行。表数值实验结果算例 .对比 算法和文献 的算法（简记为 ）的有效性，标准测试函数（）来自文献 ，测试函数（）由标准函数（）根据文献 中的方法改进而来，即（）（）（）（）（）其中，（）是列满秩矩阵。显然，（），（）（）（）的秩为，当，（，），（）的秩为。第期韩扬等：一种求解非线性方程组的修正 算法从表中的数值实验结果可以看出，算法相对稳定，对于大部分测试的实验结果，算法的计算时间小于 算法的计算时间，并且当选取的初始点远离解集时，算例在参数 及、算例在参数 及 ，和算例在参数 及，时，算法的计算量和计算时间均小于 算法。结论本文结合信赖域方法提出了一种求解非线性方程组的修正的 算法（算法），在不必假设雅可比矩阵非奇异的局部误差界条件下，证明了该算法具有局部快速收敛性。可根据实际应用的需要，通过改变和值以优化的选取，数值实验结果表明，算法稳定有效。然而雅可比矩阵的计算量和收敛速度还需继续改善，如何节约雅可比矩阵的计算量和提升收敛速度是今后有待解决的问题。参考文献 ，（）：，：，：，：，（）：，（）：，：，（）：，（）：，：，：？，（）：，（）：，（）：，（）：，（）：，（）：，（）：，：，（），（）：青 岛 大 学 学 报（自 然 科 学 版）第 卷 ，（）：，（，）：（）（），：；（上接第页），：，：，：，（）：，（，）：，：；