第四章 非线性方程和非性方程组的解法 4.1 非线性方程的解法 4.2 非线性方程组的线性化解法 4.3 非线性方程组的极值求解法

Presentation on theme: "第四章 非线性方程和非性方程组的解法 4.1 非线性方程的解法 4.2 非线性方程组的线性化解法 4.3 非线性方程组的极值求解法"— Presentation transcript:

1 第四章 非线性方程和非性方程组的解法 4.1 非线性方程的解法 4.2 非线性方程组的线性化解法 4.3 非线性方程组的极值求解法
第四章 非线性方程和非性方程组的解法 　4.1 非线性方程的解法 4.2 非线性方程组的线性化解法　　　 　4.3 非线性方程组的极值求解法 4.4 最速下降法 4.5 共轭梯度法 4.6 牛顿过程及变度量法 4.7 直接法 4.8 方法的选择与总结 浙江大学研究生学位课程 《实用数值计算方法》

2 １.非线性方程的解法 ２.非线性方程组的线性化解法 －－牛顿迭代法 ３.非线性方程组的极值求解法 －－最速下降法 | 单纯形法
　　１.非线性方程的解法 　　２.非线性方程组的线性化解法 　　　－－牛顿迭代法 　　３.非线性方程组的极值求解法 　　　－－最速下降法　|　单纯形法 　　　－－共轭梯度法　|　Powell 方法 　　　－－变尺度法 | 　　　（可变矩阵方法）|　直接法 　　　　DFP 方法 | 浙江大学研究生学位课程 《实用数值计算方法》

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

4 其中fi（i=1,2,…,n）是n维实空间Ｒn 上的 实值函数。用向量形式表示：
4.1 非线性方程组的一般形式是： 其中fi（i=1,2,…,n）是n维实空间Ｒn 上的 　　实值函数。用向量形式表示： 这里　　　　　均是n维向量。为了方便 　　计，还是用　　　　分别表示上述向量。 简记为： 浙江大学研究生学位课程 《实用数值计算方法》

5 4.1 d c a d b c a 图 4.1 非线性方程求根示意图 浙江大学研究生学位课程 《实用数值计算方法》

6  方程的解亦称方程的根或函数的零点。  根可能是实数或复数。  若 则 称为单根； 若 而 ，则 称为 k 重根。
4.1  方程的解亦称方程的根或函数的零点。  　根可能是实数或复数。  　若　　　　　　　　　　则　称为单根； 　　若　 　　而　　　　　，则　称为 k 重根。 常见的求解问题有两种： 　(1) 要求定出在给定范围内的某个解。 　(2) 要求定出在给定范围内的全部解。  非线性问题，除少数情况外，一般不能 　　不利用公式求解。而要采用某种迭代解法。 　　即构造出一近似值序列　　　　　　　　 　　逼近真解 。 浙江大学研究生学位课程 《实用数值计算方法》

7  迭代过程的收敛性一般与初值的选取和方 程的性态有关，某些解法仅与初值有关。  收敛速度一般由迭代方法所决定，方程的
4.1  　 迭代过程的收敛性一般与初值的选取和方 　　程的性态有关，某些解法仅与初值有关。  收敛速度一般由迭代方法所决定，方程的 　　性态也会起一些作用。 本章主要介绍非线性方程组的解法， 而方程的解法用较少的篇幅在4.2中扼要介绍。 　　解非线性方程和方程组有很大区别。后者 　　要困难得多。主要的区别在于一维情形可 　　以找到一个根的范围，然后缩小，最终找 　　到根。而多维情况则很难确定根的存在。 　　直到你求得它的解。 浙江大学研究生学位课程 《实用数值计算方法》

8 4.2 非线性方程的解法 4.2.1 二分法 对于连续函数 ，如果在 和 处异号： 则 在 内至少有一个根。 浙江大学研究生学位课程
4.2 非线性方程的解法 4.2.1 二分法 　　　对于连续函数　　，如果在 　　　　 和　　　处异号：　　　　　　 　　　则　　在　　内至少有一个根。 浙江大学研究生学位课程 《实用数值计算方法》

9 用图来表示这个过程： 确定根所在的范围［a,b］对有的函数 也是一件困难的事。所幸的是，在实际应 用中，根据其物理或工程的背景，在绝大
4.2.1 用图来表示这个过程： y a a b b ０ a b x 图 4.2 二分法方程求根 确定根所在的范围［a,b］对有的函数 　　也是一件困难的事。所幸的是，在实际应 　　用中，根据其物理或工程的背景，在绝大 　　部分场合是不困难的。对给定的函数也有 　　确定范围的方法。 浙江大学研究生学位课程 《实用数值计算方法》

10 图 4.3 寻找隔根区间示意1 a x1 b c f c x1 d a x2 x3 b 4.2.1 浙江大学研究生学位课程
图 4.3 寻找隔根区间示意1 浙江大学研究生学位课程 《实用数值计算方法》

11 4.2.1 图 4.4 寻找隔根区间示意2 a c b 图 4.5 寻找隔根区间示意3 浙江大学研究生学位课程 《实用数值计算方法》

12 例如，在［a,b］之间寻找 f(x) 可能有 的根可以用等分试探法： a b 图 4.6 等分试探法寻找隔根区间示意 4.2.1
　　的根可以用等分试探法： a b 图 4.6 等分试探法寻找隔根区间示意 浙江大学研究生学位课程 《实用数值计算方法》

13 用二分法求函数FUNC位于（x1,x2）之间的根，准确性为XACC。 FUNCTION RTBIS (FUNC,X1,X2,XACC)
4.2.1 用二分法求函数FUNC位于（x1,x2）之间的根，准确性为XACC。 FUNCTION RTBIS (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.) THEN RTIBIS=X1 DX=X2-X1 ELSE RTBIS=X2 DX=X1-X2 ENDIF DO 11 J=1, JMAX DX=DX*0.5 XMID=RTBIS+DX FMID=FUNC(XMID) IF (FMID.LE.0.) RTBIS=XMID IF (ABS(DX) .LT. XACC .OR. FMID .EQ. 0.) RETURN 11 CONTINUE PAUSE '迭代次数越界' END 浙江大学研究生学位课程 《实用数值计算方法》

14 PRINT *, '方程在（-1，0）区间内有一个根，X=', ROOT STOP
4.2.1 FUNCTION FF(X) FF = X*X + 2.5*X SIN(X) END PROGRAM ROOTFIND EXTERNAL FF X1=-1.0 X2=0.0 ROOT=RTBIS(FF, X1, X2, 1.0E-5) PRINT *, '方程在（-1，0）区间内有一个根，X=', ROOT STOP 浙江大学研究生学位课程 《实用数值计算方法》

15 4.2.2 线性插值法（又称弦位法） f(x) x 图 4.7 Secant Method 浙江大学研究生学位课程 《实用数值计算方法》

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

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

18 4.2.2 f(x) 2 3 4 x 1 图 4.8 线性插值法求根示意 浙江大学研究生学位课程 《实用数值计算方法》

19 4.2.2 f(x) x 1 3 4 5 图 4.9 线性插值法发散示例 浙江大学研究生学位课程 《实用数值计算方法》

20 Newton 法 F(x) x 图 Newton 法示意 浙江大学研究生学位课程 《实用数值计算方法》

21 4.2.3 F(x) x 图 导数变化对算法的影响 浙江大学研究生学位课程 《实用数值计算方法》

22 每次函数求值相当的收敛阶为： b. 求 fk' 有时工作量大，甚至不可能。 (4) 选用收敛域较大的方法（如二分法）
　　　　每次函数求值相当的收敛阶为： 　　b. 求 fk' 有时工作量大，甚至不可能。 　(4) 选用收敛域较大的方法（如二分法） 　　 先进行迭代，然后再用Newton法。 　　　　－－组合方法。 二次插值法 　　　　设 f(x)=0 的三个近似解及函数值 构造二次函数g(y)使得： 浙江大学研究生学位课程 《实用数值计算方法》

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

24 4.2.4 F(x) g(x) f(x) x 图 二次插值法求根示意 浙江大学研究生学位课程 《实用数值计算方法》

25 (1) 要有三个初始值 (2) 当 。且收敛速度 是 1.84 阶。（单根） 二重根的收敛阶是1.23。 (3) (4) 发生超射、越界。
4.2.4 (1) 要有三个初始值 (2) 当 。且收敛速度 是 1.84 阶。（单根） 二重根的收敛阶是1.23。 (3) (4) 发生超射、越界。 表 4.1 各种插值方法的比较 浙江大学研究生学位课程 《实用数值计算方法》

26 4.2.5 组合方法（Brent Method） 能否有一种方法综合上述方法的优 点呢？Brent 做了一些工作。
　　　　能否有一种方法综合上述方法的优 　　点呢？Brent 做了一些工作。 　　　　Brent 把二分法和二次插值法结合 　　起来。 　　（１）一定收敛。 　　（２）收敛速度至少线性。 　　（３）在解附近足够光滑时，收敛速度　 　　　　　将是 1.84 或 1.23。 　　有关多项式的求根还有一些特殊方法。 浙江大学研究生学位课程 《实用数值计算方法》

27 4.3 非线性方程组及牛顿法 非线性方程组的向量形式可表示为 解法： 1. 几乎不可能用直接法 2. 线性化，迭代逼近。牛顿法
4.3 非线性方程组及牛顿法 非线性方程组的向量形式可表示为 　　解法： 1. 几乎不可能用直接法 2. 线性化，迭代逼近。牛顿法 3. 最优化，求函数极小值。下降法。 例如， 求 的极小值点。 最速下降法，共轭梯度法，变尺度方法。 浙江大学研究生学位课程 《实用数值计算方法》

28 作线性函数（Taylor 展开，取一阶精度）
牛顿法 　　　　为方便计，用二维情形来讨论。 假定（4-6）的解 　　作线性函数（Taylor 展开，取一阶精度） 浙江大学研究生学位课程 《实用数值计算方法》

29 在 内用线性函数（4-7）代替 非线性方程组(4-6)中的f1,f2, 从而 如果在 中矩阵（称Jacobi矩阵） 非奇异，则可解出。
4.3.1 　　　　在　　　　内用线性函数（4-7）代替 　　非线性方程组(4-6)中的f1,f2, 从而 如果在　　　　中矩阵（称Jacobi矩阵） 　　非奇异，则可解出。 浙江大学研究生学位课程 《实用数值计算方法》

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

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

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

33 牛顿法的改进 　　改进１ 带松弛因子的牛顿迭代格式改善了 　　对初始值近似程度的要求。 浙江大学研究生学位课程 《实用数值计算方法》

34 4.3.2 (4-10) 中引入了松弛因子　　，有 浙江大学研究生学位课程 《实用数值计算方法》

35 4.3.2 图 凸函数示例 浙江大学研究生学位课程 《实用数值计算方法》

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

37 4.3.2 图 法搜索极小点过程 浙江大学研究生学位课程 《实用数值计算方法》

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

39 的选取可以在满足(4-12)的前提下取很大值。 （１）改善对初值的要求 （２）当 ＝０时为牛顿法，收敛最快。
4.3.2 改进２.带阻尼因子的牛顿迭代格式 克服了矩阵　　　的奇异或病态。(4-10)中 引入阻尼因子　： 　的选取可以在满足(4-12)的前提下取很大值。 　（１）改善对初值的要求 　（２）当　＝０时为牛顿法，收敛最快。 　（３）为满足(4-12)，实际上需要多次试算， 　　　　工作量大。 　　改进3.　修正牛顿法 尽可能减少矩阵求逆次数。 浙江大学研究生学位课程 《实用数值计算方法》

40 一种简单的办法是每次使用同一个Jacobi 矩阵的逆。
4.3.2 　　一种简单的办法是每次使用同一个Jacobi 　　矩阵的逆。 　　但大大影响收敛速度。 　　另一种办法是若干次迭代后求一个矩阵逆： 它减少了矩阵求逆，又保证了收敛。 　　 换一个角度看，如果说它的求逆次数与 　　牛顿法相同(k次)，则它的收敛阶为m+1。 浙江大学研究生学位课程 《实用数值计算方法》

41 作为特例，取m=2: 或 迭代格式(4-15)具有３阶收敛速度。 在几何上表现为m步迭代 过程保持斜率 f'(xk) 不变。 如图4.16：
4.3.2 作为特例，取m=2: 　　或 　迭代格式(4-15)具有３阶收敛速度。 对一维情况，Newton法 　在几何上表现为m步迭代 　过程保持斜率 f'(xk) 不变。 　如图4.16： f(x) x 图 m=2的迭代效果 浙江大学研究生学位课程 《实用数值计算方法》

42 非线性代数方程组求解问题 1. Newton--Raphson 迭代法 2. 极值化求解。 问题的转化： 4.3.2 浙江大学研究生学位课程
　　非线性代数方程组求解问题 1. Newton--Raphson 迭代法 2. 极值化求解。 　　问题的转化： 浙江大学研究生学位课程 《实用数值计算方法》

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

44 4.4.1 　　求解最优化问题，通常采用下降法。下降法 一般描述如下： 浙江大学研究生学位课程 《实用数值计算方法》

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

46 4.4.1 最速下降法取 因此 浙江大学研究生学位课程 《实用数值计算方法》

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

48 4.4.2 讨论与改进 优点： １. 程序简单，每步迭代计算量少，存储省。 ２. 对于不太好的初始点x0，往往也能收敛。 缺点：
4.4.2　讨论与改进 　　优点： １. 程序简单，每步迭代计算量少，存储省。 ２. 对于不太好的初始点x0，往往也能收敛。 　　缺点： 　　　最速下降法是名不符实的，一般来说， 　它只有线性的收敛速度。 浙江大学研究生学位课程 《实用数值计算方法》

49 4.4.2 图 锯齿形搜索路径情况 浙江大学研究生学位课程 《实用数值计算方法》

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

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

52 4.4.2 　　　　一般来说，开始几步下降速度 　　较快，但越靠近极小值点越慢。 　　　　改进： 浙江大学研究生学位课程 《实用数值计算方法》

53 4.4.2 最速下降法算法框图： 停 停 图 最速下降法算法框图 浙江大学研究生学位课程 《实用数值计算方法》

54 4.4.2 图 搜索路径示意 浙江大学研究生学位课程 《实用数值计算方法》

55 4.5 共轭梯度法 （Conjugate Gradient Methods）
4.5.1 共轭方向 图 共轭方向 浙江大学研究生学位课程 《实用数值计算方法》

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

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

58 4.5.1 图 二次函数的共轭方向 图 二次函数 浙江大学研究生学位课程 《实用数值计算方法》

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

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

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

62 4.5.2 共轭梯度法 Conjugate Gradient Method 利用共轭方向，对二次型求极值问题 可以得到n步收敛的结果。
　　　　利用共轭方向，对二次型求极值问题 　　可以得到n步收敛的结果。 　　　　现在的问题是： 　　1.如何构造n个共轭方向？ 　　2.对一般的非线性函数f(x)怎么办？ 　　3.由于舍入误差等影响，n次迭代不收敛 　　　时怎么办？ 浙江大学研究生学位课程 《实用数值计算方法》

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

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

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

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

67 * F-R方法和P-R方法的区别在于它们对二 次型是一样的。而对一般函数用P-R方法 可能更合适。
4.5.2 　　　　共轭梯度法是从梯度向量出发构造 　　共轭向量。 　　* 由于误差积累等因素，对二次型，迭代 　　 n次也未能达到极小点。 　　* F-R方法和P-R方法的区别在于它们对二 次型是一样的。而对一般函数用P-R方法 　　 可能更合适。 　　* 共轭梯度法具有二次收敛速度。 　　　　那么对一般的函数的共轭梯度法 又是怎样的呢？ 浙江大学研究生学位课程 《实用数值计算方法》

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

69 达到精度（kn）,则xk就作为x*的近似。 当经过n步迭代仍不可能满足要求时，令
4.5.2 　　　　但是求导数f(xk)是必须的。 另外，我们总假定f(x)在极值点附近 　　性质足够好，满足各种要求。 对一般函数f(x)，共轭梯度法(4-23)有 限步收敛几乎是不可能的。如果迭代k 步 达到精度（kn）,则xk就作为x*的近似。 当经过n步迭代仍不可能满足要求时，令 　　再进行第二次循环。 　　　　但是，实际计算中，不一定迭代 　　k=n 步才进行“重置”。 浙江大学研究生学位课程 《实用数值计算方法》

70 则进行（m+n）次迭代（１m<n）就 收敛了。而进行 k 次迭代（k  n）就 重置的话，有可能会不收敛。
4.5.2 (1)　在极小点附近是一个高度偏心的二次 　　　函数。 　　　则进行（m+n）次迭代（１m<n）就 　　　收敛了。而进行 k 次迭代（k  n）就 　　　重置的话，有可能会不收敛。 (2)　在极小点附近或稍远处不是二次函数。 　　　此时称“扭曲”现象。 　　　则　　　留有非二次函数的痕迹，故 　　　可能对收敛很有害。此时最好重置。 浙江大学研究生学位课程 《实用数值计算方法》

71 共轭梯度法 Conjugate Gradient Methods 算法框图
4.5.2 共轭梯度法 Conjugate Gradient Methods 算法框图 图 共轭梯度法算法框图 浙江大学研究生学位课程 《实用数值计算方法》

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

73 4.5.2 　　　它在点（1,1）处有极小值4. 其图象为： 图 函数等高线图 浙江大学研究生学位课程 《实用数值计算方法》

74 4.5.2 　　　　　表4.3　最速下降法计算结果 浙江大学研究生学位课程 《实用数值计算方法》

75 4.5.2 　表4.4 各种重置循环的共轭梯度法计算结果 浙江大学研究生学位课程 《实用数值计算方法》

76 4.6 牛顿过程及变度量法 4.6.1 Newton--Raphson 迭代 把函数f(x)在第k次近似解 xk 附近进行
Taylor展开： 浙江大学研究生学位课程 《实用数值计算方法》

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

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

79 图 4.27 初值对Newton-Raphson 方法的影响
4.6.1 图 初值对Newton-Raphson 方法的影响 浙江大学研究生学位课程 《实用数值计算方法》

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

81 改一次Jk-1，是一种方案。但不是最好的。
　　　　然而这个方法的致命弱点是要计算 　　Jk-1。4.2提供的办法，即迭代若干次修 　　改一次Jk-1，是一种方案。但不是最好的。 变量的尺度变换 　　　　为改变函数的偏心程度，从而改变极 　　小化方法的收敛性质，采用变量替换是个 很好的措施。 浙江大学研究生学位课程 《实用数值计算方法》

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

83 4.6.2 图 函数进行尺度变换的效果 浙江大学研究生学位课程 《实用数值计算方法》

84 尺度变换目的是把函数的偏心程度降 到最低限度（它放大或缩小各个坐标）， 但并不能完全消除偏心问题。 把尺度变换应用于各种算法，都有一
4.6.2 　　　　尺度变换目的是把函数的偏心程度降 　　到最低限度（它放大或缩小各个坐标）， 　　但并不能完全消除偏心问题。 　　　　把尺度变换应用于各种算法，都有一 　　定效果。 　　　　一般地 浙江大学研究生学位课程 《实用数值计算方法》

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

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

87 变尺度法 　 —— DFP方法 　 —— BFGS方法 常用的度量是 浙江大学研究生学位课程 《实用数值计算方法》

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

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

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

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

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

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

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

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

96 变尺度法 Variable Matrix Methods 算法框图：
4.6.3 变尺度法 Variable Matrix Methods 算法框图： 图 变尺度法算法框图 浙江大学研究生学位课程 《实用数值计算方法》

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

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

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

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

101 4.6.3 表4.5 各种方法比较 浙江大学研究生学位课程 《实用数值计算方法》

102 大量的目标函数是很复杂的，有时连解析式都没有，因而它的导数
4.7 直接法（Simplex, Powell） 　　大量的目标函数是很复杂的，有时连解析式都没有，因而它的导数 　　　　　　　　f(x) 　很难求，有时甚至不存在。 单纯形法　Simplex Method Nelder--Mead (1965)提出这种简单的方法。它不需要求导数（梯度） 对变元不多的情况是有效的。 程序简单。 浙江大学研究生学位课程 《实用数值计算方法》

103 (它们构成单纯形)上引进函数值比较。丢弃 最坏的点并代之以新点。它们仍然构成单纯 形。以此逐步逼近极小点。
4.7.1 　　　　单纯形的思想是在n维空间的(n+1)个点 　　(它们构成单纯形)上引进函数值比较。丢弃 　　最坏的点并代之以新点。它们仍然构成单纯 　　形。以此逐步逼近极小点。 浙江大学研究生学位课程 《实用数值计算方法》

104 4.7.1 图 单纯形法中的反射 浙江大学研究生学位课程 《实用数值计算方法》

105 4.7.1 图 单纯形法中的延伸 浙江大学研究生学位课程 《实用数值计算方法》

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

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

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

109 4.7.1 单纯形法（Simplex）框图： 解x*x0 图 单纯形法计算框图 浙江大学研究生学位课程 《实用数值计算方法》

110 Powelll 方法是一种不依赖于目标函数 梯度的直接搜索法。 它逐步构造共轭方向并作为搜索方向， 因此Powell方法也是一种共轭方向法。
　　　　以上的迭代过程直到满足精度为止。 　　精度： 　　　　则x0作为所求的近似解。 Powelll 方法 　　　　 Powelll 方法是一种不依赖于目标函数 　　梯度的直接搜索法。 　　　　它逐步构造共轭方向并作为搜索方向， 　　因此Powell方法也是一种共轭方向法。 　　它的基本过程如下： 浙江大学研究生学位课程 《实用数值计算方法》

111 表4.6 Powell 方法解题过程 图 4.35 Powell搜索路径 4.7.2 5.0 2.5 浙江大学研究生学位课程
《实用数值计算方法》

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

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

114  循环上面(1)--(3)，直至P0点函数值不再减 小为止。  当循环k次(kn)以后，un与它前面的k-1个
4.7.2 　  循环上面(1)--(3)，直至P0点函数值不再减 　　 小为止。 　  当循环k次(kn)以后，un与它前面的k-1个 　　 向量 un-k+1,,un-1共轭。因此对于二次函数， 　　 理论上只要循环n次即可求得极小值。即具 　　 有二次收敛性。事实上，因为 　　　　P0和Pn是沿相同方向un求得的极小值， 　　所以PnP0与un方向共轭。 图 共轭方向 浙江大学研究生学位课程 《实用数值计算方法》

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

116 4.7.2 表4.7 Powell方法第一次循环计算结果 浙江大学研究生学位课程 《实用数值计算方法》

117 4.7.2 图 单纯形法求一维极值示意图（1） 浙江大学研究生学位课程 《实用数值计算方法》

118 4.7.2 图 单纯形法求一维极值示意图（2） 浙江大学研究生学位课程 《实用数值计算方法》

119 因为每一循环都用Pn--P0“挤掉”u1,所以 新的向量系ui(I=1,…,n)有可能线性相关， 例如，某一循环中，如果1０则
4.7.2 　  但是，实际计算中对二次函数也不能保证 　　n步内达到极小值点。 　　因为每一循环都用Pn--P0“挤掉”u1,所以 　　新的向量系ui(I=1,…,n)有可能线性相关， 　　例如，某一循环中，如果1０则 　　这样，u2,u3,…, Pn--P0是线性相关的。 　　　　当发生这种情况时，以后的搜索就在 　　n 维的子空间中进行。最后的解就不正确。 　　解决的办法是Pn--P0不是挤掉u1。而是挤掉 　　ur, 而r０。一般取最大下降方向（the Direction of the Largest Decrease) 浙江大学研究生学位课程 《实用数值计算方法》

120 这是因为最大下降方向ur已经在平均方向 Pn-P0中得到最充分的体现。  这一简单的思想有两种例外情况：此时 并不修改方向。 4.7.2
　 这一简单的思想有两种例外情况：此时 　　并不修改方向。 浙江大学研究生学位课程 《实用数值计算方法》

121 b) Pn-P0方向上二阶导数很大，这表明在 Pn附近有可能有极小点。
4.7.2 　　因为下列两个原因之一成立： 　　a) Pn-P0方向的下降主要不是因为f. b) Pn-P0方向上二阶导数很大，这表明在 　　　 Pn附近有可能有极小点。 图 4.41 函数变化的影响 浙江大学研究生学位课程 《实用数值计算方法》

122 图4.42 修正Powell算法框图： fEf0 4.7.2 收敛准则 P*= Pkn,计算结束 浙江大学研究生学位课程
《实用数值计算方法》

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

124 4.7.2 P* 图 计算结果图示 浙江大学研究生学位课程 《实用数值计算方法》

125 4.8 方法的选择与总结 4.8.1 方法的选择 1. 原则： （1）有效性 （２）运算量 （３）存储量 2. 非线性代数方程
4.8 方法的选择与总结 方法的选择 1.　原则： （1）有效性 （２）运算量 （３）存储量 2.　非线性代数方程 （１）二分法具有良好的有效性 （２）二次插值和有理插值运算 量少 （３）一般采用组合方法 浙江大学研究生学位课程 《实用数值计算方法》

126 3. 非线性方程组 （１）一般采用最优化方法 （２）对于无梯度（或不易求梯度）问题， 一般不用ＣＧ方法，因为稳定性太 差。
4.8.1 　3. 非线性方程组 　（１）一般采用最优化方法 　（２）对于无梯度（或不易求梯度）问题， 　　　　一般不用ＣＧ方法，因为稳定性太 　　　　差。 　　　　 用有限差商近似导数不是好的选择。 　　　　但是当问题很大时（n200）由于存 　　　　贮的限制，ＰＯＷ方法和ＶＭ方法 　　　　不能用时，只能考虑ＣＧ方法。 　　　　　　对小问题（2 n  10）,选择 　　　　ＰＯＷ方法或ＶＭ方法（差商近似 　　　　导数）均可考虑。有效性依赖于问 　　　　题。 浙江大学研究生学位课程 《实用数值计算方法》

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

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

129 1.迭代法，而不是解析法 2.线性化，极值化方法 3.降维法 4.下降法 5.插值逼近法 6.组合法 7.梯度方向 共轭方向 改变度量
4.8.2 算法思想小结 1.迭代法，而不是解析法 　 线性化，极值化方法 　 降维法 　 下降法 　 插值逼近法 　 组合法 　 梯度方向 　　 共轭方向 　　 改变度量 浙江大学研究生学位课程 《实用数值计算方法》

130 第四章　习 题 浙江大学研究生学位课程 《实用数值计算方法》

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