非线性方程组迭代解法DFP方法与BFS方法

1、非线性方程组的拟牛顿法数理学院 汪玉霞 李锋摘要：本文主要介绍基于非线性方程组的牛顿法的秩1拟牛顿法和秩2拟牛顿法，并对每个方法举出相应的例子来说明在迭代过程中根的变化情况以及根随迭代序列的变化图，并对这两种迭代法进行总结。关键词：牛顿迭代法 非线性方程组 Broyden拟牛顿法 Abstact: This paper mainly introduces two kind of quasi Newton method based on Newton iterative method for solving nonlinear equation group, and for each metho

2、d we give corresponding example to illustrate the variation of the changes of root with iterative sequence . Key words: Newton iterative method nonlinear equation group Broyden method 1.非线性方程组的牛顿迭代法设非线性方程组 （1.1） 其中是实变量，分别是个变量的元函数，且至少有一个是自变量的非线性函数，若记 则（1.1）可以等价地记为 （1.2） 一般地，当Jacobi矩阵非奇异时，可得 （1.3） 这就是

3、非线性方程组的（1.3）的Newton迭代法。利用迭代法（1.3）求解非线性方程组（1.1）的近似解，每一步迭代需要解一个线性方程组，且这一步与下一步的Jacobi矩阵的逆矩阵也不相同，因此计算量较大，可以证明Newton迭代法具有二阶收敛速度，但对迭代初始值的要求很高，即充分靠近精确解。一般地，（1.3）可改写为： 2.Broyden秩1拟牛顿法一般地，（1.3）可改写为： 考虑用比较简单的矩阵来逼近,将迭代公式改写为 （2.1）这里依赖于及，为了避免都要重新计算，我们考虑下一步只是对进行修正，它要求满足方程 （2.2）成为拟牛顿方程。它表明矩阵关于点及具有“差商”性质，即当时，即为关于点及

4、的差商，但当时并不确定，为此我们限制是由的一个低秩修正矩阵得到的，即 （2.3）其中是秩为的修正矩阵，有（2.3.1），（2.3.2），（2.3.3）组成的迭代法就称为拟牛顿法。它通过给定初始近似和矩阵，根据这三式可以逐次计算得到和，从而可以避免每一步都要计算的雅可比矩阵，这样使得计算量减少，这种算法由于（2.3.3）中的有不同的算法，因此可以得到许多不同的拟牛顿法，常有的拟牛顿法是为秩1矩阵和为秩2矩阵的方法。秩1算法是指 （2.4）中修正矩阵的秩时的拟牛顿法，因为对任何的阶的秩1矩阵都可以表示为，其中，于是有 （2.5）下面主要是选择合适的使得它们满足拟牛顿方程 （2.6）若记，有 （2.

5、7）则可以得到 即若，则得 代入（2.2）中得到 ， （2.8）若取，只要，就有，则 （2.9）由此可以得到一种秩1拟牛顿法 （2.10）此算法称为布罗伊登（Broyden）秩1方法。3. 秩2拟牛顿法 现在考虑 （3.1）中校正矩阵为秩2矩阵的情形，即的情形，此时，可以表示为 其中，都是阶矩阵，将的第一、二列向量分别记作，的第一、二列向量分别记作，则 （3.2）代入拟牛顿法方程记，即代入： 中得 或写成 （3.3）现取 ， （3.4）则可得 （3.5）显然，如果取，使得 ， （3.6）从而拟Newton方程也满足。令 （3.7） （3.8）其中是一个实参数，经过整理后可以得到 （3.9）选取

6、不同的参数就可以得到不同的公式，从而得到解方程组的不同的秩2拟牛顿迭代法。4.拟牛顿法的实现例1：对非线性方程组，其中 ， 应用Broyden秩1拟牛顿方法，取迭代格式为： 其中：计算结果为： 迭代次数为 详细结果如下表所示：迭代次序 x1 x2 x3 1.e+00 0.e+00 0.e+00 0.e+00 2.e+00 9.e-01 1.e+00 6.e-01 3.e+00 9.e-01 1.e+00 6.e-01 4.e+00 9.e-01 1.e+00 6.e-01 5.e+00 9.e-01 1.e+00 6.e-01 6.e+00 9.e-01 1.e+00 6.e-01 7.e+0

7、0 9.e-01 1.e+00 6.e-01 8.e+00 9.e-01 1.e+00 6.e-01可以看出，整个迭代过程还是比较平稳的，在迭代进行到第二次的时候，数值解已经比较稳定，说明了这一方法的有效性。例2：对非线性方程组，初值取 应用以下秩2拟牛顿方法（BFS方法），取迭代格式为： 计算结果为： 迭代次数为 详细结果如下表所示： 迭代次序 x y z 1.e+000 0.e+000 0.e+000 0.e+000 2.e+000 4.e-001 8.e-002 -5.e-001 3.e+000 5.e-001 7.e-003 -5.e-001 4.e+000 5.e-001 2.e-0

8、04 -5.e-001 5.e+000 5.e-001 5.e-007 -5.e-001 6.e+000 5.e-001 1.e-011 -5.e-001 7.e+000 5.e-001 -7.e-010 -5.e-001可以看到在迭代三次以后，根就很平稳不再有大的起伏，向更高的精度逼近，但BFS方法数值稳定性更强一些。矩阵在每次迭代过程中一般不会发生很大的变化。 参考文献1徐瑞民. 二元非线性方程组求根的牛顿迭代法J. 山东轻工业学院学报: 自然科学版, 2009, 23(4): 89-91.2李湘.非单调线性搜索及其在共轭梯度法和拟牛顿法中的应用D.湖南大学,20083晁玉翠.求解非线性方

9、程组的修正牛顿法研究D. 哈尔滨工业大学,20074 He Y, Zhang Y, Shang Y, et al. Two-level Newton iterative method for the 2D/3D steady Navier-Stokes equationsJ. Numerical Methods for Partial Differential Equations, 2012, 28(5):16201642.5 Clarkson M J, Zombori G, Thompson S, et al. The NifTK software platform for image-guided i