非线性方程组数值解

浙江大学研究生学位课程《实用数值计算方法》1

１.非线性方程的解法２.非线性方程组的线性化解法

－－牛顿迭代法３.非线性方程组的极值求解法

－－最速下降法|

单纯形法－－共轭梯度法|

Powell方法－－变尺度法|

（可变矩阵方法）|直接法

DFP方法

|浙江大学研究生学位课程《实用数值计算方法》2

４.1

引言

在科学研究中，常常会遇到非线性方程或非线性方程组的问题。例如解方程或一般的，我们记非线性方程为浙江大学研究生学位课程《实用数值计算方法》34.1

非线性方程组的一般形式是：

其中fi（i=1,2,…,n）是n维实空间Ｒn

上的实值函数。用向量形式表示：

这里均是n维向量。为了方便计，还是用

分别表示上述向量。简记为：浙江大学研究生学位课程《实用数值计算方法》44.1cadcadb图4.1非线性方程求根示意图浙江大学研究生学位课程《实用数值计算方法》54.1

方程的解亦称方程的根或函数的零点。

根可能是实数或复数。

若则称为单根；

若而，则称为k重根。

常见的求解问题有两种：

(1)要求定出在给定范围内的某个解。

(2)要求定出在给定范围内的全部解。

非线性问题，除少数情况外，一般不能

不利用公式求解。而要采用某种迭代解法。即构造出一近似值序列逼近真解。浙江大学研究生学位课程《实用数值计算方法》64.1

迭代过程的收敛性一般与初值的选取和方

程的性态有关，某些解法仅与初值有关。

收敛速度一般由迭代方法所决定，方程的性态也会起一些作用。

本章主要介绍非线性方程组的解法，而方程的解法用较少的篇幅在4.2中扼要介绍。

解非线性方程和方程组有很大区别。后者要困难得多。主要的区别在于一维情形可以找到一个根的范围，然后缩小，最终找到根。而多维情况则很难确定根的存在。直到你求得它的解。浙江大学研究生学位课程《实用数值计算方法》74.2非线性方程的解法4.2.1二分法对于连续函数，如果在和处异号：则在内至少有一个根。浙江大学研究生学位课程《实用数值计算方法》84.2.1

用图来表示这个过程：０yxababab

确定根所在的范围［a,b］对有的函数也是一件困难的事。所幸的是，在实际应用中，根据其物理或工程的背景，在绝大部分场合是不困难的。对给定的函数也有确定范围的方法。图4.2二分法方程求根浙江大学研究生学位课程《实用数值计算方法》9abbax1x1x2x3dcfc4.2.1图4.3寻找隔根区间示意1浙江大学研究生学位课程《实用数值计算方法》10acb4.2.1图4.4寻找隔根区间示意2图4.5寻找隔根区间示意3浙江大学研究生学位课程《实用数值计算方法》11例如，在［a,b］之间寻找f(x)可能有的根可以用等分试探法：ab4.2.1图4.6等分试探法寻找隔根区间示意浙江大学研究生学位课程《实用数值计算方法》12用二分法求函数FUNC位于（x1,x2）之间的根，准确性为

XACC。FUNCTIONRTBIS(FUNC,X1,X2,XACC)PARAMETER(JMAX=40)FMID=FUNC(X2)F=FUNC(X1)IF(F*FMID.GE.0.)PAUSE'函数FUNC在x1,x2处不异号'IF(F.LT.0.)THENRTIBIS=X1DX=X2-X1ELSERTBIS=X2DX=X1-X2ENDIFDO11J=1,JMAXDX=DX*0.5XMID=RTBIS+DXFMID=FUNC(XMID)IF(FMID.LE.0.)RTBIS=XMIDIF(ABS(DX).LT.XACC.OR.FMID.EQ.0.)RETURN11CONTINUE

PAUSE'迭代次数越界'END4.2.1浙江大学研究生学位课程《实用数值计算方法》13FUNCTIONFF(X)FF=X*X+2.5*X+0.5+SIN(X)ENDPROGRAMROOTFINDEXTERNALFFX1=-1.0X2=0.0ROOT=RTBIS(FF,X1,X2,1.0E-5)PRINT*,'方程在（-1，0）区间内有一个根，X=',ROOTSTOPEND4.2.1浙江大学研究生学位课程《实用数值计算方法》144.2.2线性插值法（又称弦位法）xf(x)图4.7SecantMethod浙江大学研究生学位课程《实用数值计算方法》154.2.2浙江大学研究生学位课程《实用数值计算方法》164.2.2浙江大学研究生学位课程《实用数值计算方法》174.2.2f(x)x1432图4.8线性插值法求根示意浙江大学研究生学位课程《实用数值计算方法》184.2.2f(x)x1345图4.9线性插值法发散示例浙江大学研究生学位课程《实用数值计算方法》194.2.3Newton法F(x)x图4.10Newton法示意浙江大学研究生学位课程《实用数值计算方法》204.2.3F(x)x图4.11导数变化对算法的影响浙江大学研究生学位课程《实用数值计算方法》21每次函数求值相当的收敛阶为：

b.求fk'有时工作量大，甚至不可能。

(4)选用收敛域较大的方法（如二分法）先进行迭代，然后再用Newton法。

－－组合方法。

4.2.4二次插值法

设f(x)=0的三个近似解及函数值

构造二次函数g(y)使得：浙江大学研究生学位课程《实用数值计算方法》224.2.4浙江大学研究生学位课程《实用数值计算方法》234.2.4F(x)xg(x)f(x)图4.12二次插值法求根示意浙江大学研究生学位课程《实用数值计算方法》244.2.4(1)要有三个初始值

(2)当。且收敛速度是1.84

阶。（单根）二重根的收敛阶是1.23。

(3)(4)发生超射、越界。表4.1各种插值方法的比较浙江大学研究生学位课程《实用数值计算方法》25

4.2.5

组合方法（BrentMethod）

能否有一种方法综合上述方法的优点呢？Brent做了一些工作。

Brent把二分法和二次插值法结合起来。（１）一定收敛。（２）收敛速度至少线性。（３）在解附近足够光滑时，收敛速度将是1.84或1.23。

有关多项式的求根还有一些特殊方法。浙江大学研究生学位课程《实用数值计算方法》26

4.3非线性方程组及牛顿法

非线性方程组的向量形式可表示为

解法：

1.几乎不可能用直接法

2.线性化，迭代逼近。牛顿法

3.最优化，求函数极小值。下降法。例如，求的极小值点。

最速下降法，共轭梯度法，变尺度方法。浙江大学研究生学位课程《实用数值计算方法》274.3.1牛顿法为方便计，用二维情形来讨论。

假定（4-6）的解作线性函数（Taylor展开，取一阶精度）浙江大学研究生学位课程《实用数值计算方法》284.3.1在内用线性函数（4-7）代替非线性方程组(4-6)中的f1,f2,从而

如果在中矩阵（称Jacobi矩阵）

非奇异，则可解出。浙江大学研究生学位课程《实用数值计算方法》294.3.1浙江大学研究生学位课程《实用数值计算方法》304.3.1浙江大学研究生学位课程《实用数值计算方法》314.3.1浙江大学研究生学位课程《实用数值计算方法》32

4.3.2牛顿法的改进

改进１带松弛因子的牛顿迭代格式改善了对初始值近似程度的要求。浙江大学研究生学位课程《实用数值计算方法》334.3.2(4-10)中引入了松弛因子，有浙江大学研究生学位课程《实用数值计算方法》344.3.2图4.13凸函数示例浙江大学研究生学位课程《实用数值计算方法》354.3.2浙江大学研究生学位课程《实用数值计算方法》364.3.2图4.140.618法搜索极小点过程浙江大学研究生学位课程《实用数值计算方法》374.3.2

(2)二次插值法求一维函数极小值：图4.15二次插值法进行一维极小点搜索浙江大学研究生学位课程《实用数值计算方法》384.3.2

改进２.带阻尼因子的牛顿迭代格式

克服了矩阵的奇异或病态。(4-10)中引入阻尼因子：

的选取可以在满足(4-12)的前提下取很大值。（１）改善对初值的要求（２）当＝０时为牛顿法，收敛最快。（３）为满足(4-12)，实际上需要多次试算，工作量大。

改进3.

修正牛顿法

尽可能减少矩阵求逆次数。浙江大学研究生学位课程《实用数值计算方法》394.3.2

一种简单的办法是每次使用同一个Jacobi矩阵的逆。

但大大影响收敛速度。另一种办法是若干次迭代后求一个矩阵逆：

它减少了矩阵求逆，又保证了收敛。换一个角度看，如果说它的求逆次数与牛顿法相同(k次)，则它的收敛阶为m+1。

浙江大学研究生学位课程《实用数值计算方法》404.3.2或

迭代格式(4-15)具有３阶收敛速度。

对一维情况，Newton法在几何上表现为m步迭代过程保持斜率f'(xk)不变。如图4.16：f(x)x0图4.16m=2的迭代效果作为特例，取m=2:浙江大学研究生学位课程《实用数值计算方法》414.3.2

非线性代数方程组求解问题

1.Newton--Raphson迭代法2.极值化求解。

问题的转化：浙江大学研究生学位课程《实用数值计算方法》424.4

最速下降法

4.4.1极值化求解的零极值点。

求解(4-16)的极值点也是一个无约束的最优化问题。浙江大学研究生学位课程《实用数值计算方法》434.4.1

求解最优化问题，通常采用下降法。下降法

一般描述如下：浙江大学研究生学位课程《实用数值计算方法》444.4.1

下降法的迭代步骤浙江大学研究生学位课程《实用数值计算方法》454.4.1

最速下降法取

因此浙江大学研究生学位课程《实用数值计算方法》464.4.1等高线图：f(x)=Cif(x1,x2)=Ci图4.17等高线图4.18偏导数示意浙江大学研究生学位课程《实用数值计算方法》474.4.2

讨论与改进

优点：１.程序简单，每步迭代计算量少，存储省。

２.对于不太好的初始点x0，往往也能收敛。

缺点：

最速下降法是名不符实的，一般来说，它只有线性的收敛速度。浙江大学研究生学位课程《实用数值计算方法》484.4.2图4.19锯齿形搜索路径情况浙江大学研究生学位课程《实用数值计算方法》494.4.2浙江大学研究生学位课程《实用数值计算方法》504.4.2浙江大学研究生学位课程《实用数值计算方法》514.4.2

一般来说，开始几步下降速度较快，但越靠近极小值点越慢。

改进：浙江大学研究生学位课程《实用数值计算方法》524.4.2

最速下降法算法框图：停停图4.20最速下降法算法框图浙江大学研究生学位课程《实用数值计算方法》534.4.2图4.21搜索路径示意浙江大学研究生学位课程《实用数值计算方法》544.5共轭梯度法

（ConjugateGradientMethods）4.5.1

共轭方向图4.22共轭方向浙江大学研究生学位课程《实用数值计算方法》554.5.1

浙江大学研究生学位课程《实用数值计算方法》564.5.1浙江大学研究生学位课程《实用数值计算方法》574.5.1图4.23二次函数的共轭方向图4.24二次函数浙江大学研究生学位课程《实用数值计算方法》584.5.1浙江大学研究生学位课程《实用数值计算方法》594.5.1浙江大学研究生学位课程《实用数值计算方法》604.5.1浙江大学研究生学位课程《实用数值计算方法》614.5.2共轭梯度法

ConjugateGradientMethod利用共轭方向，对二次型求极值问题可以得到n步收敛的结果。

现在的问题是：

1.如何构造n个共轭方向？

2.对一般的非线性函数f(x)怎么办？

3.由于舍入误差等影响，n次迭代不收敛时怎么办？浙江大学研究生学位课程《实用数值计算方法》624.5.2浙江大学研究生学位课程《实用数值计算方法》634.5.2浙江大学研究生学位课程《实用数值计算方法》644.5.10浙江大学研究生学位课程《实用数值计算方法》654.5.2浙江大学研究生学位课程《实用数值计算方法》664.5.2共轭梯度法是从梯度向量出发构造共轭向量。

*由于误差积累等因素，对二次型，迭代

n次也未能达到极小点。

*

F-R方法和P-R方法的区别在于它们对二次型是一样的。而对一般函数用P-R方法可能更合适。

*共轭梯度法具有二次收敛速度。

那么对一般的函数的共轭梯度法又是怎样的呢？浙江大学研究生学位课程《实用数值计算方法》674.5.2

在极小值点附近进行二次逼近：浙江大学研究生学位课程《实用数值计算方法》684.5.2

但是求导数

f(xk)是必须的。

另外，我们总假定f(x)在极值点附近性质足够好，满足各种要求。

对一般函数f(x)，共轭梯度法(4-23)有限步收敛几乎是不可能的。如果迭代k步达到精度（kn）,则xk就作为x*的近似。当经过n步迭代仍不可能满足要求时，令

再进行第二次循环。但是，实际计算中，不一定迭代

k=n步才进行“重置”。浙江大学研究生学位课程《实用数值计算方法》694.5.2

(1)

在极小点附近是一个高度偏心的二次函数。则进行（m+n）次迭代（１

m<n）就收敛了。而进行

k次迭代（k

n）就重置的话，有可能会不收敛。

(2)

在极小点附近或稍远处不是二次函数。此时称“扭曲”现象。则留有非二次函数的痕迹，故可能对收敛很有害。此时最好重置。浙江大学研究生学位课程《实用数值计算方法》70

4.5.2

共轭梯度法ConjugateGradientMethods

算法框图图4.25共轭梯度法算法框图浙江大学研究生学位课程《实用数值计算方法》714.5.2

(3)如何判别是高度偏心的二次函数还是扭曲的函数呢？启发性的办法是：对一般非二次函数，若x0离x*较远，则迭代n次不收敛时，就重置。但以后不再重置。对既高度偏心，又严重扭曲的函数，则经常性的重置是有好处的。浙江大学研究生学位课程《实用数值计算方法》724.5.2它在点（1,1）处有极小值4.

其图象为：图4.26函数等高线图浙江大学研究生学位课程《实用数值计算方法》734.5.2

表4.3

最速下降法计算结果浙江大学研究生学位课程《实用数值计算方法》744.5.2表4.4各种重置循环的共轭梯度法计算结果浙江大学研究生学位课程《实用数值计算方法》754.6牛顿过程及变度量法4.6.1Newton--Raphson迭代把函数f(x)在第k次近似解xk附近进行Taylor展开：浙江大学研究生学位课程《实用数值计算方法》764.6.1浙江大学研究生学位课程《实用数值计算方法》774.6.1浙江大学研究生学位课程《实用数值计算方法》784.6.1图4.27初值对Newton-Raphson方法的影响浙江大学研究生学位课程《实用数值计算方法》794.6.1浙江大学研究生学位课程《实用数值计算方法》80

然而这个方法的致命弱点是要计算

Jk-1。4.2提供的办法，即迭代若干次修改一次Jk-1，是一种方案。但不是最好的。

4.6.2变量的尺度变换

为改变函数的偏心程度，从而改变极小化方法的收敛性质，采用变量替换是个很好的措施。浙江大学研究生学位课程《实用数值计算方法》814.6.2浙江大学研究生学位课程《实用数值计算方法》824.6.2图4.28函数进行尺度变换的效果浙江大学研究生学位课程《实用数值计算方法》834.6.2

尺度变换目的是把函数的偏心程度降到最低限度（它放大或缩小各个坐标），但并不能完全消除偏心问题。

把尺度变换应用于各种算法，都有一定效果。

一般地浙江大学研究生学位课程《实用数值计算方法》844.6.2即变换后的二次函数偏心率为０，它是圆。它用最速下降法一步可以达到极小点。现在希望直接处理原来的函数，而定义一个算子。用它产生通过极小点的向量。考虑这样的Ｔ：

从Newton--Raphson过程浙江大学研究生学位课程《实用数值计算方法》854.6.2浙江大学研究生学位课程《实用数值计算方法》864.6.3变尺度法

——DFP方法

——BFGS方法

常用的度量是浙江大学研究生学位课程《实用数值计算方法》874.6.3浙江大学研究生学位课程《实用数值计算方法》884.6.3浙江大学研究生学位课程《实用数值计算方法》894.6.3浙江大学研究生学位课程《实用数值计算方法》904.6.3浙江大学研究生学位课程《实用数值计算方法》914.6.3浙江大学研究生学位课程《实用数值计算方法》924.6.3浙江大学研究生学位课程《实用数值计算方法》934.6.3浙江大学研究生学位课程《实用数值计算方法》944.6.3浙江大学研究生学位课程《实用数值计算方法》954.6.3

变尺度法VariableMatrixMethods

算法框图：图4.29变尺度法算法框图浙江大学研究生学位课程《实用数值计算方法》964.6.3浙江大学研究生学位课程《实用数值计算方法》974.6.3浙江大学研究生学位课程《实用数值计算方法》984.6.3浙江大学研究生学位课程《实用数值计算方法》994.6.3浙江大学研究生学位课程《实用数值计算方法》1004.6.3表4.5各种方法比较浙江大学研究生学位课程《实用数值计算方法》1014.7直接法（Simplex,Powell）

大量的目标函数是很复杂的，有时连解析式都没有，因而它的导数

f(x)很难求，有时甚至不存在。4.7.1单纯形法

SimplexMethodNelder--Mead(1965)提出这种简单的方法。它不需要求导数（梯度）对变元不多的情况是有效的。程序简单。浙江大学研究生学位课程《实用数值计算方法》1024.7.1

单纯形的思想是在n维空间的(n+1)个点

(它们构成单纯形)上引进函数值比较。丢弃最坏的点并代之以新点。它们仍然构成单纯形。以此逐步逼近极小点。浙江大学研究生学位课程《实用数值计算方法》1034.7.1图4.30单纯形法中的反射浙江大学研究生学位课程《实用数值计算方法》1044.7.1图4.31单纯形法中的延伸浙江大学研究生学位课程《实用数值计算方法》1054.7.1浙江大学研究生学位课程《实用数值计算方法》1064.7.1

图4.32单纯形法中的收缩浙江大学研究生学位课程《实用数值计算方法》1074.7.1

e)缩小边长图4.33单纯形法中的缩小边长浙江大学研究生学位课程《实用数值计算方法》1084.7.1

单纯形法（Simplex）框图：解x*

x0图4.34单纯形法计算框图浙江大学研究生学位课程《实用数值计算方法》109以上的迭代过程直到满足精度为止。

精度：则x0作为所求的近似解。

4.7.2

Powelll方法

Powelll方法是一种不依赖于目标函数梯度的直接搜索法。它逐步构造共轭方向并作为搜索方向，因此Powell方法也是一种共轭方向法。

它的基本过程如下：浙江大学研究生学位课程《实用数值计算方法》1104.7.2图4.35Powell搜索路径表4.6Powell方法解题过程5.02.5浙江大学研究生学位课程《实用数值计算方法》1114.7.2浙江大学研究生学位课程《实用数值计算方法》1124.7.2

Powell方法过程图示：图4.36Powell方法计算过程图示浙江大学研究生学位课程《实用数值计算方法》1134.7.2

循环上面(1)--(3)，直至P0点函数值不再减小为止。

当循环k次(kn)以后，un与它前面的k-1个向量un-k+1,,un-1共轭。因此对于二次函数，理论上只要循环n次即可求得极小值。即具

有二次收敛性。事实上，因为

P0和Pn是沿相同方向un求得的极小值，所以PnP0与un方向共轭。图4.37共轭方向浙江大学研究生学位课程《实用数值计算方法》1144.7.2

图4.38Powell方法计算过程示意浙江大学研究生学位课程《实用数值计算方法》1154.7.2表4.7Powell方法第一次循环计算结果浙江大学研究生学位课程《实用数值计算方法》116图4.39单纯形法求一维极值示意图（1）4.7.2浙江大学研究生学位课程《实用数值计算方法》117图4.40单纯形法求一维极值示意图（2）4.7.2浙江大学研究生学位课程《实用数值计算方法》1184.7.2

但是，实际计算中对二次函数也不能保证

n步内达到极小值点。

因为每一循环都用Pn--P0“挤掉”u1,所以新的向量系ui(I=1,…,n)有可能线性相关，例如，某一循环中，如果

1

０则

这样，u2,u3,…,Pn--P0是线性相关的。

当发生这种情况时，以后的搜索就在

n维的子空间中进行。最后的解就不正确。解决的办法是Pn--P0不是挤掉u1