计算函数零点和极值点的迭代法.ppt
157页
数值计算方法第四章 计算函数零点和极值点的迭代法 2/96本章讨论非线性方程（组）的求解问题本章讨论非线性方程（组）的求解问题 3/961．不动点设非线性方程组设非线性方程组 f(x) = 0 (4.1-1)4.1 不动点迭代法及其收敛性 4/96非线性方程组非线性方程组 f(x) = 0 (4.1-1)等价：等价： x = (x) (4.1-2)则有迭代格式：则有迭代格式：x(k+1) = (x(k))，，k = 0, 1, 2, …若若 连连续续，，且且迭迭代代序序列列{x(k)}收收敛敛到到x*，，则则两两边边取取极极限得限得x* = (x*)，，即即x*满满足足(4.1-2)，，从从而而满满足足(4.1-1)，，即即x*为为f 的的零零点称x*为为 (x)的不动点的不动点4.1 不动点迭代法及其收敛性 5/96x(k+1) = (x(k))，，k = 0, 1, 2, …注：注：(1) 求零点求零点求不动点求不动点(2) (.)称为迭代函数，称为迭代函数，{x(k)}称为迭代序列称为迭代序列(3) 不同方法构造迭代函数，得不同的迭代序列不同方法构造迭代函数，得不同的迭代序列4.1 不动点迭代法及其收敛性 6/962．迭代法的基本问题(1) 如如何何构构造造适适当当的的迭迭代代函函数数 (.)使使迭迭代代序序列列{x(k)}收敛收敛(2) 收敛的速度和误差收敛的速度和误差(3) 如何加速如何加速4.1 不动点迭代法及其收敛性 7/964.1.1 解一元方程的迭代法解一元方程的迭代法1. 根的隔离设设一一元元方方程程f(x) = 0，，f 连连续续，，其其实实根根可可能能有有很很多多，，需需将将各各根根隔隔离离，，即即f在在某某区区间间[a，，b]内内有有且且仅仅有有一一根。
根方方法法：：设设f C[a，，b]，，f(a)f(b) < 0，，且且f在在[a，，b]上上单调，则单调，则f在在[a，，b]内有且仅有一根内有且仅有一根4.1 不动点迭代法及其收敛性 8/964.1.1 解一元方程的迭代法解一元方程的迭代法2. 迭代序列的收敛性因因为为可可以以有有多多种种迭迭代代函函数数，，所所产产生生的的迭迭代代序序列列{x(k)}有可能：有可能：(1) 收敛快收敛快(2) 收敛慢收敛慢(3) 不收敛不收敛4.1 不动点迭代法及其收敛性 9/964.1.1 解一元方程的迭代法解一元方程的迭代法例例1 f(x) = x3 – x – 1 = 0，，求求f在在x附附近近的的根根，，初初值值取取xp328)取取 —— 收敛收敛x1=(1+x0)^(1/3) k=k+1, x0=x1; x1=(1+x0)^(1/3)end4.1 不动点迭代法及其收敛性 10/964.1.1 解一元方程的迭代法解一元方程的迭代法例例1 f(x) = x3 – x – 1 = 0，，求求f在在x附附近近的的根根，，初初值值取取x。
p328)取取 (x) = x3 – 1 —— 不收敛不收敛x1=x0^3-1while abs(x1-x0)>0.00001 && k<5 k=k+1, x0=x1; x1=x0^3-1end4.1 不动点迭代法及其收敛性 11/964.1.1 解一元方程的迭代法解一元方程的迭代法定定理理4.1-1 (1)设设 (x) C[a，，b], 且且对对于于任任意意x [a, b]有有 (x) [a，，b]，则，则 在在[a，，b]上必有不动点上必有不动点2) 进进一一步步，，若若 (x) C1[a，，b]，，且且存存在在L<1，，使使对于任意的对于任意的x [a，，b]有有 | '(x)| L < 1 (4.1-4)则则对对于于任任意意的的x(0) [a，，b]，，x(k+1) = (x(k))收收敛敛于唯一不动点于唯一不动点x* [a，，b]4.1 不动点迭代法及其收敛性 12/964.1.1 解一元方程的迭代法解一元方程的迭代法定定理理4.1-1 (2) 进进一一步步，，若若 (x) C1[a，，b]，，且且存存在在L<1，使对于任意的，使对于任意的x [a，，b]有有 | '(x)| L < 1 (4.1-4)则则对对于于任任意意的的x(0) [a，，b]，，x(k+1) = (x(k))收收敛敛于唯一不动点于唯一不动点x* [a，，b]。
且有且有 (4.1-5)4.1 不动点迭代法及其收敛性 13/964.1.1 解一元方程的迭代法解一元方程的迭代法定定理理4.1-1 (1)设设 (x) C[a，，b], 且且对对于于任任意意x [a, b]有有 (x) [a，，b]，则，则 在在[a，，b]上必有不动点上必有不动点证明：证明：(1) 若若 (a) = a或或 (b) = b，则结论显然成立，则结论显然成立现设现设a < (a)，， (b) < b，令，令 (x)= (x) – x，则，则 (x) C[a，，b]，且，且 (a) = (a) – a > 0，， (b) = (b) – b < 0，，故存在故存在x* [a，，b]，使，使 (x*) = 0，即，即 (x*) – x* = 0 (x*) = x*4.1 不动点迭代法及其收敛性 14/964.1.1 解一元方程的迭代法解一元方程的迭代法证明证明: (2)设设 (x) C1[a，，b]，且满足，且满足(4.1-4)，，若若有有x1*, x2* [a，，b]，，x1* x2*，， (xi*) = xi* i = 1, 2由微分中值定理由微分中值定理|x1* – x2*| = | (x1*) – (x2*)| = | '(ξ)| |x1* – x2*| L|x1* – x2*| < |x1* – x2*|矛盾，所以不动点唯一。
矛盾，所以不动点唯一4.1 不动点迭代法及其收敛性| '(x)| L < 1 15/964.1.1 解一元方程的迭代法解一元方程的迭代法证明证明: (2)设设 (x) C1[a，，b]，且满足，且满足(4.1-4)，由，由|x(k) – x*| = | ( x(k-1)) – (x*)| L|x(k-1) – x*| … L k|x(0) – x*|及及0 < L < 1知知即即x(k)收敛于收敛于x*4.1 不动点迭代法及其收敛性| '(x)| L < 1 16/964.1.1 解一元方程的迭代法解一元方程的迭代法证明证明: (2) 由由|x(k) – x*| L|x(k-1) – x*| 得得 |x(k) – x*| L|x(k-1) – x(k) + x(k) – x*| L|x(k-1) – x(k)| + L|x(k) – x*|从而有从而有又因又因|x(k) – x(k-1)| = | (x(k-1)) – (x(k-2))| L| x(k-1) – x(k-2)| … L k-1| x(1) – x(0)|，，代代入上式的右边，即得入上式的右边，即得4.1 不动点迭代法及其收敛性 17/964.1.1 解一元方程的迭代法解一元方程的迭代法(4.1-5)注：注：(1) 若若L 1，则收敛很慢，须考虑加速问题，则收敛很慢，须考虑加速问题(2) (4.1-5)中中第第一一式式为为后后验验公公式式—迭迭代代停停止止准准则则; 第二式为先验公式第二式为先验公式—预测迭代次数预测迭代次数(3) 定定理理是是以以[a，，b]中中任任一一点点作作初初值值，，迭迭代代都都收收敛敛，，称为全局收敛。
称为全局收敛4.1 不动点迭代法及其收敛性 18/964.1.1 解一元方程的迭代法解一元方程的迭代法(4.1-5)注注：：(3) 定定理理是是以以[a，，b]中中任任一一点点作作初初值值，，迭迭代代都都收敛，称为全局收敛收敛，称为全局收敛此要求较难满足，故考虑在）（此要求较难满足，故考虑在）x*的某一邻域内的某一邻域内—局部收敛性局部收敛性4.1 不动点迭代法及其收敛性 19/964.1.1 解一元方程的迭代法解一元方程的迭代法定定理理4.1-2 设设x*为为 的的不不动动点点, '在在x*的的某某邻邻域域内内连连续续, 且且| ’(x*)|<1, 则则存存在在 > 0, 只只要要x(0) [x*– ，，x*+ ]，就有迭代法，就有迭代法 x(k+1) = (x(k))收敛证证明明: ∵∵| '(x*)|<1，，及及 '(x)在在U(x*)内内连连续续，，存在存在 > 0，使，使[x*– ，，x*+ ] U(x*)，，且且 x [x* – ，，x* + ]有有| '(x)| q < 14.1 不动点迭代法及其收敛性 20/964.1.1 解一元方程的迭代法解一元方程的迭代法定定理理4.1-2 设设x*为为 的的不不动动点点, '在在x*的的某某邻邻域域内内连连续续, 且且| ’(x*)|<1, 则则存存在在 > 0, 只只要要x(0) [x*– ，，x*+ ]，就有迭代法，就有迭代法 x(k+1) = (x(k))收敛。
收敛证明证明: 存在存在 > 0，使，使[x*– ，，x*+ ] U(x*)，，且且 x [x* – ，，x* + ]有有| '(x)| q < 1 x [x* – ，，x* + ]，，| (x) – x*| = | (x) – (x*)| = | '(ξ)| |x – x*| q|x – x*| < ，，4.1 不动点迭代法及其收敛性 21/964.1.1 解一元方程的迭代法解一元方程的迭代法定定理理4.1-2 设设x*为为 的的不不动动点点, '在在x*的的某某邻邻域域内内连连续续, 且且| ’(x*)|<1, 则则存存在在 > 0, 只只要要x(0) [x*– ，，x*+ ]，就有迭代法，就有迭代法 x(k+1) = (x(k))收敛证明证明: 存在存在 > 0，使，使 x [x* – ，，x* + ]，，| (x) – x*| < ，即，即 (x) [x*– ，，x*+ ]，，由定理知，由定理知，任任意意x(0) [x*– ，，x*+ ]，，迭迭代代法法x(k+1)= (x(k))收敛。
收敛4.1 不动点迭代法及其收敛性 22/964.1.1 解一元方程的迭代法解一元方程的迭代法定定理理4.1-2 设设x*为为 的的不不动动点点, '在在x*的的某某邻邻域域内内连连续续, 且且| ’(x*)|<1, 则则存存在在 > 0, 只只要要x(0) [x*– ，，x*+ ]，就有迭代法，就有迭代法 x(k+1) = (x(k))收敛注注：：只只要要x(0)充充分分接接近近x*，，且且| '(x(0))| 明明显显小小于于1，则，则{x(k)}收敛于收敛于x*4.1 不动点迭代法及其收敛性 23/964.1.1 解一元方程的迭代法解一元方程的迭代法例例2 求方程求方程x = e–x在附近的根在附近的根由于由于| '(0.5)| = e 明显小于明显小于1，故收敛，故收敛解：解：Matlab代码如下代码如下x1=exp(-x0)while abs(x1-x0)>0.00001 && k<25 k=k+1, x0=x1; x1=exp(-x0)end4.1 不动点迭代法及其收敛性 24/964.1.1 解一元方程的迭代法解一元方程的迭代法3. 收敛阶定义定义4.1-1 设设x(k) x*，记，记ek= x(k) - x* 若存在若存在p 1，及，及c≠ 0，使，使则称则称{x(k)}是是p阶收敛的，或称收敛阶为阶收敛的，或称收敛阶为p（（p越高收敛越快）越高收敛越快）注：注：(1) p = 1，，0 < c < 1，称为线性收敛；，称为线性收敛；(2) p > 1，称超线性收敛，称超线性收敛(3) p = 2，称平方收敛，称平方收敛4.1 不动点迭代法及其收敛性 25/964.1.1 解一元方程的迭代法解一元方程的迭代法3. 收敛阶因因 为为 |x(k+1)–x*| = | (x(k))– (x*)| = | '(ξ)||x(k)–x*|，，其中其中ξ在在x(k)和和x*之间。
则之间则所以若所以若 '(x*) 0，则为线性收敛，则为线性收敛想想得得到到更更高高阶阶的的收收敛敛性性，，须须 '(x*) = 0，，通通常常可可考考虑泰勒展式虑泰勒展式4.1 不动点迭代法及其收敛性 26/964.1.1 解一元方程的迭代法解一元方程的迭代法3. 收敛阶定定理理4.1-3 设设x*为为 的的不不动动点点，，正正整整数数p 2，，若若 (p)在在x*的某邻域内连续，且满足的某邻域内连续，且满足(4.1.6)则则{x(k)}p阶局部收敛阶局部收敛证明：证明：∵∵ '(x*) = 0(<1)，，∴∴x(k)局部收敛局部收敛4.1 不动点迭代法及其收敛性 27/96定定理理4.1-3 设设x*为为 的的不不动动点点，，正正整整数数p 2，，若若 (p)在在x*的某邻域内连续，且满足的某邻域内连续，且满足(4.1.6)则则{x(k)}p阶局部收敛阶局部收敛证明：证明：∵∵ ‘(x*) = 0(<1)，，∴∴x(k)局部收敛局部收敛设设 (x)在在x*处展开为处展开为4.1 不动点迭代法及其收敛性 28/96定定理理4.1-3 设设x*为为 的的不不动动点点，，正正整整数数p 2，，若若 (p)在在x*的某邻域内连续，且满足的某邻域内连续，且满足(4.1.6)则则{x(k)}p阶局部收敛。
阶局部收敛证明：设证明：设 (x)在在x*处展开为处展开为由由(4.1-6)知，知，4.1 不动点迭代法及其收敛性 29/96定定理理4.1-3 设设x*为为 的的不不动动点点，，正正整整数数p 2，，若若 (p)在在x*的某邻域内连续，且满足的某邻域内连续，且满足(4.1.6)则则{x(k)}p阶局部收敛阶局部收敛证明：由证明：由(4.1-6)知知所以所以即即{x(k)}p阶局部收敛阶局部收敛4.1 不动点迭代法及其收敛性 30/96例例3 设设f C2[a，，b]，， x*为为f的单重零点，的单重零点， (x) = x – r1(x)f(x) – r2(x)f 2(x)试试确确定定未未知知函函数数r1(x)、、r2(x)，，使使迭迭代代法法x(k+1) = (x(k))至少是三阶局部收敛的至少是三阶局部收敛的解解:由定理知，应有由定理知，应有 '(x*)= "(x*)=0因因 为为 '(x)=1-r1'(x)f(x)-r1(x)f '(x)-r2'(x)f 2(x) - 2r2(x)f (x)f '(x)而而f(x*) = 0，，f '(x*) ≠ 0（（单单重重零零点点）），，令令 '(x*) = 0有有1 – r1(x*)f '(x*) = 04.1 不动点迭代法及其收敛性 31/96例例3 设设f C2[a，，b]，， x*为为f的单重零点，的单重零点， (x) = x – r1(x)f(x) – r2(x)f 2(x)。
试试确确定定未未知知函函数数r1(x)、、r2(x)，，使使迭迭代代法法x(k+1) = (x(k))至少是三阶局部收敛的至少是三阶局部收敛的解解: 令令 '(x*) = 0有有1 – r1(x*)f '(x*) = 04.1 不动点迭代法及其收敛性 32/96例例3 设设f C2[a，，b]，， x*为为f的单重零点，的单重零点， (x) = x – r1(x)f(x) – r2(x)f 2(x)试试确确定定未未知知函函数数r1(x)、、r2(x)，，使使迭迭代代法法x(k+1) = (x(k))至少是三阶局部收敛的至少是三阶局部收敛的解解: 令令 '(x*) = 0, 有有1 – r1(x*)f '(x*) = 0即取即取 ，则有，则有 '(x*) = 0，此时有，此时有 '(x)=- r1'(x)f(x) - r2'(x)f 2(x) - 2r2(x)f (x)f '(x)4.1 不动点迭代法及其收敛性 33/96例例3 设设f C2[a，，b]，， x*为为f的单重零点，的单重零点， (x) = x – r1(x)f(x) – r2(x)f 2(x)。
试试确确定定未未知知函函数数r1(x)、、r2(x)，，使使迭迭代代法法x(k+1) = (x(k))至少是三阶局部收敛的至少是三阶局部收敛的解解:即取即取 ，则有，则有 '(x*) = 0，此时有，此时有 '(x)=- r1'(x)f(x) - r2'(x)f 2(x) - 2r2(x)f (x)f '(x) "(x) = -r1"(x)f(x)-r1'(x)f '(x)-r2"(x)f 2(x) -4r2'(x)f(x)f '(x)-2r2(x)[f '(x)]2-2r2'(x)f(x)f "(x)4.1 不动点迭代法及其收敛性 34/96例例3 设设f C2[a，，b]，， x*为为f的单重零点，的单重零点， (x) = x – r1(x)f(x) – r2(x)f 2(x)试试确确定定未未知知函函数数r1(x)、、r2(x)，，使使迭迭代代法法x(k+1) = (x(k))至少是三阶局部收敛的至少是三阶局部收敛的解解: "(x) = -r1"(x)f(x)-r1'(x)f '(x)-r2"(x)f 2(x) -4r2'(x)f(x)f '(x)-2r2(x)[f '(x)]2-2r2'(x)f(x)f "(x)4.1 不动点迭代法及其收敛性 35/96例例3 设设f C2[a，，b]，， x*为为f的单重零点，的单重零点， (x) = x – r1(x)f(x) – r2(x)f 2(x)。
试试确确定定未未知知函函数数r1(x)、、r2(x)，，使使迭迭代代法法x(k+1) = (x(k))至少是三阶局部收敛的至少是三阶局部收敛的解解: "(x) = -r1"(x)f(x)-r1'(x)f '(x)-r2"(x)f 2(x) -4r2'(x)f(x)f '(x)-2r2(x)[f '(x)]2-2r2'(x)f(x)f "(x)其中其中令令 "(x*) = 0，有，有4.1 不动点迭代法及其收敛性 36/96例例3 设设f C2[a，，b]，， x*为为f的单重零点，的单重零点， (x) = x – r1(x)f(x) – r2(x)f 2(x)试试确确定定未未知知函函数数r1(x)、、r2(x)，，使使迭迭代代法法x(k+1) = (x(k))至少是三阶局部收敛的至少是三阶局部收敛的解解: 令令 "(x*) = 0，有，有4.1 不动点迭代法及其收敛性 37/96例例3 设设f C2[a，，b]，， x*为为f的单重零点，的单重零点， (x) = x – r1(x)f(x) – r2(x)f 2(x)。
试试确确定定未未知知函函数数r1(x)、、r2(x)，，使使迭迭代代法法x(k+1) = (x(k))至少是三阶局部收敛的至少是三阶局部收敛的解解: 令令 “(x*) = 0，有，有即取即取 , 则有则有 "(x*) = 0从而只要同时取从而只要同时取迭代法至少具有三阶局部收敛性迭代法至少具有三阶局部收敛性4.1 不动点迭代法及其收敛性 38/964.1.1 解一元方程的迭代法解一元方程的迭代法4. 加速幂法中曾有幂法中曾有Aitken加速，这里使用同一思想加速，这里使用同一思想:设设x(k) x*，由中值定理，，由中值定理，x(k+1) – x* = (x(k)) – (x*) = '(ξ1)(x(k) – x*) ξ1在在x(k)和和x*之间之间x(k+2) – x*= (x(k+1)) – (x*)= '(ξ2)(x(k+1)–x*) ξ2在在x(k+1)和和x*之间之间因因为为x(k) x*，，所所以以当当k充充分分大大时时，， '(ξ1) '(ξ2) 4.1 不动点迭代法及其收敛性 39/964.1.1 解一元方程的迭代法解一元方程的迭代法4. 加速 ξ1在在x(k)和和x*之间之间 ξ2在在x(k+1)和和x*之间之间因因为为x(k) x*，，所所以以当当k充充分分大大时时，， '(ξ1) '(ξ2) 4.1 不动点迭代法及其收敛性 40/964.1.1 解一元方程的迭代法解一元方程的迭代法4. 加速 ξ1在在x(k)和和x*之间之间 ξ2在在x(k+1)和和x*之间之间因因为为x(k) x*，，所所以以当当k充充分分大大时时，， '(ξ1) '(ξ2) 即即 (4.1-7)4.1 不动点迭代法及其收敛性 41/964.1.1 解一元方程的迭代法解一元方程的迭代法4. 加速即即 (4.1-7)4.1 不动点迭代法及其收敛性 42/964.1.1 解一元方程的迭代法解一元方程的迭代法4. 加速即即 (4.1-7)记记则则{ }比比{x(k)}收敛得快。
收敛得快4.1 不动点迭代法及其收敛性 43/964.1.1 解一元方程的迭代法解一元方程的迭代法4. 加速定理定理4.1-4 设设{x(k)}线性收敛于线性收敛于x*，且，且 k 0，，ek=x(k) – x*≠ 0, 0 < | | < 1 (线线性性收收敛敛)则则证明：由证明：由 知知ek+1 = ( +εk)ek，其中，其中εk0 x(k+1) – x(k) = x(k+1) – x* – (x(k) – x*) = ek+1 – ek =[( – 1)+εk]ek4.1 不动点迭代法及其收敛性 44/964.1.1 解一元方程的迭代法解一元方程的迭代法4. 加速定理定理4.1-4 设设{x(k)}线性收敛于线性收敛于x*，且，且 k 0，，ek=x(k) – x*≠ 0, 0 < | | < 1 (线线性性收收敛敛)则则证明：证明： x(k+1) – x(k) =[( – 1)+εk]ek4.1 不动点迭代法及其收敛性 45/964.1.1 解一元方程的迭代法解一元方程的迭代法4. 加速定理定理4.1-4 设设{x(k)}线性收敛于线性收敛于x*，且，且 k 0，，ek=x(k) – x*≠ 0, 0 < | | < 1 (线线性性收收敛敛)则则证明：证明： x(k+1) – x(k) =[( – 1)+ k]ek又又 x(k+2) – 2x(k+1) + x(k) = (x(k+2) – x(k+1)) – (x(k+1) – x(k)) = [( – 1) + k+1]ek+1 – [( – 1) + k]ek = [( – 1) + k+1]( + k)ek– [( –1) + k]ek4.1 不动点迭代法及其收敛性 46/964.1.1 解一元方程的迭代法解一元方程的迭代法4. 加速定理定理4.1-4 设设{x(k)}线性收敛于线性收敛于x*，且，且 k 0，，ek=x(k) – x*≠ 0, 0 < | | < 1 (线线性性收收敛敛)则则证明：证明： x(k+1) – x(k) =[( – 1)+ k]ek又又 x(k+2) – 2x(k+1) + x(k) = [( – 1) + k+1]( + k)ek– [( –1) + k]ek4.1 不动点迭代法及其收敛性 47/964.1.1 解一元方程的迭代法解一元方程的迭代法4. 加速定理定理4.1-4 设设{x(k)}线性收敛于线性收敛于x*，且，且 k 0，，ek=x(k) – x*≠ 0, 0 < | | < 1 (线线性性收收敛敛)则则证明：证明： x(k+1) – x(k) =[( – 1)+ k]ek又又 x(k+2) – 2x(k+1) + x(k) = [( – 1) + k+1]( + k)ek– [( –1) + k]ek = [( – 1)2 + k]ek 4.1 不动点迭代法及其收敛性 k = k+1+( –2) k+ k+1 k0 48/964.1.1 解一元方程的迭代法解一元方程的迭代法4. 加速定理定理4.1-4 设设{x(k)}线性收敛于线性收敛于x*，且，且 k 0，，ek=x(k) – x*≠ 0, 0 < | | < 1 (线线性性收收敛敛)则则证明：又因为证明：又因为4.1 不动点迭代法及其收敛性x(k+1) – x(k) =[( – 1)+ k]ekx(k+2) – 2x(k+1) + x(k) = [( – 1)2 + k]ek 49/964.1.1 解一元方程的迭代法解一元方程的迭代法4. 加速定理定理4.1-4 设设{x(k)}线性收敛于线性收敛于x*，且，且 k 0，，ek=x(k) – x*≠ 0, 0 < | | < 1 (线线性性收收敛敛)则则证明：又因为证明：又因为所以所以4.1 不动点迭代法及其收敛性x(k+1) – x(k) =[( – 1)+ k]ekx(k+2) – 2x(k+1) + x(k) = [( – 1)2 + k]ek 50/964.1.1 解一元方程的迭代法解一元方程的迭代法4. 加速定理定理4.1-4 设设{x(k)}线性收敛于线性收敛于x*，且，且 k 0，，ek=x(k) – x*≠ 0, 0 < | | < 1 (线线性性收收敛敛)则则证明：所以证明：所以4.1 不动点迭代法及其收敛性x(k+1) – x(k) =[( – 1)+ k]ekx(k+2) – 2x(k+1) + x(k) = [( – 1)2 + k]ek 51/964.1.1 解一元方程的迭代法解一元方程的迭代法4. 加速定理定理4.1-4 设设{x(k)}线性收敛于线性收敛于x*，且，且 k 0，，ek=x(k) – x*≠ 0, 0 < | | < 1 (线线性性收收敛敛)则则注：注：(1) (4.1-7)称为称为Aitken加速加速4.1 不动点迭代法及其收敛性 52/964.1.1 解一元方程的迭代法解一元方程的迭代法4. 加速定理定理4.1-4 设设{x(k)}线性收敛于线性收敛于x*，且，且 k 0，，ek=x(k) – x*≠ 0, 0 < | | < 1 (线线性性收收敛敛)则则注：注：(2) k = 1，，2，，…称为史蒂文生迭代法。
称为史蒂文生迭代法4.1 不动点迭代法及其收敛性 53/964.1.1 解一元方程的迭代法解一元方程的迭代法4. 加速例例4 用迭代法和用迭代法和Steffensen迭代法求函数迭代法求函数f(x) = x – lnx – 2在在区区间间(2, + )内内的的零零点点，，取取x(0) = 3解：将解：将f(x) = 0化为等价的方程化为等价的方程x = lnx + 2 = (x)，，由于由于 '(x) = 1/x在在[2，，+ )上满足上满足| '(x)| ≤ 1/2 <1，且，且2 < (x) < + ，，所以迭代法所以迭代法x(k+1) = ln x(k) + 2收敛4.1 不动点迭代法及其收敛性 54/964.1.1 解一元方程的迭代法解一元方程的迭代法4. 加速例例4 用迭代法和用迭代法和Steffensen迭代法求函数迭代法求函数f(x) = x – lnx – 2在在区区间间(2, + )内内的的零零点点，，取取x(0) = 3解：解：Steffensen迭代法的计算公式为：迭代法的计算公式为：取初值取初值x(0) = 3作迭代，结果见作迭代，结果见p3364.1 不动点迭代法及其收敛性 55/964.1.1 解一元方程的迭代法解一元方程的迭代法4. 加速例例4 用迭代法和用迭代法和Steffensen迭代法求函数迭代法求函数f(x) = x – lnx – 2在在区区间间(2, + )内内的的零零点点，，取取x(0) = 3解：迭代法解：迭代法x(k+1) = ln x(k) + 2：：x0=3k=1x1=log(x0)+2while (abs(x1-x0)>0.0000001) x0=x1; k=k+1 x1=log(x0)+2end4.1 不动点迭代法及其收敛性 56/964.1.1 解一元方程的迭代法解一元方程的迭代法4. 加速解：解：Steffensen迭代法：迭代法：x0=3k=1y=log(x0)+2z=log(y)+2x1=z-(z-y)^2/(z-2*y+x0)while (abs(x1-x0)>0.0000001) x0=x1;k=k+1 y=log(x0)+2 z=log(y)+2 x1=z-(z-y)^2/(z-2*y+x0)end4.1 不动点迭代法及其收敛性 57/964.1.2 解非线性方程组的迭代法解非线性方程组的迭代法设非线性方程组设非线性方程组 f(x) = 0 (4.1-1)考虑等价形式考虑等价形式 x = Φ(x) (4.1-2)迭代公式迭代公式 x(k+1) = Φ(x(k)) k=0，，1，，2，，… (4.1-3)其收敛性有下述压缩映射（不动点）原理其收敛性有下述压缩映射（不动点）原理4.1 不动点迭代法及其收敛性 58/964.1.2 解非线性方程组的迭代法解非线性方程组的迭代法定理定理4.1-5 设设Φ在闭区域在闭区域 上满足条件上满足条件存存 在在 q, 0 则则(1) 存存在在唯唯一一不不动动点点x* ，，且且 x(0) ，，迭迭代代向向量列收敛于量列收敛于x*2) 证明与定理及定理相似证明与定理及定理相似4.1 不动点迭代法及其收敛性 59/964.1.2 解非线性方程组的迭代法解非线性方程组的迭代法定理定理4.1-5 设设Φ在闭区域在闭区域 上满足条件上满足条件存存 在在 q, 0 内的根解：解：(1) 取取x(0) = (1，，-1.5)T，按迭代公式：，按迭代公式： k = 0，，1，，2，，…产生的序列收敛（见产生的序列收敛（见p339））4.1 不动点迭代法及其收敛性 62/964.1.2 解非线性方程组的迭代法解非线性方程组的迭代法解：解：(1) 取取x(0) = (1，，-1.5)T，按迭代公式：，按迭代公式： k = 0，，1，，2，，…产生的序列收敛（见产生的序列收敛（见p339））k=1,x0=[1,-1.5]x1=[log(1-x0(2)),-sqrt(4-x0(1)^2)] k=k+1, x0=x1; x1=[log(1-x0(2)),-sqrt(4-x0(1)^2)]end4.1 不动点迭代法及其收敛性 63/964.1.2 解非线性方程组的迭代法解非线性方程组的迭代法例例5 用不动点迭代法求非线性方程用不动点迭代法求非线性方程在闭域在闭域 内的根。 内的根解：解： (2) 按迭代公式：按迭代公式： k = 0，，1，，2，，…产生的序列未必收敛（见产生的序列未必收敛（见p340））4.1 不动点迭代法及其收敛性 64/964.1.2 解非线性方程组的迭代法解非线性方程组的迭代法解：解：(2) 按迭代公式：按迭代公式： k = 0，，1，，2，，…产生的序列未必收敛（见产生的序列未必收敛（见p340））k=1,x0=[1,-1.5]x1=[sqrt(4-x0(2)^2),1-exp(x0(1))]while abs(x1-x0)>0.0001 & k<10 k=k+1, x0=x1; x1=[sqrt(4-x0(2)^2),1-exp(x0(1))]end4.1 不动点迭代法及其收敛性 65/964.2.1 一元非线性方程一元非线性方程f(x) = 01. 牛顿迭代方法线性化：线性化： 设设f (x)在点在点x(k)处可微，则展开式处可微，则展开式用线性部分近似表示用线性部分近似表示f (x) f (x(k)) + f '(x(k))( x – x(k)) 即考虑方程即考虑方程 f (x(k)) + f '(x(k))(x – x(k)) = 04.2 Newton迭代法及其变形 66/964.2.1 一元非线性方程一元非线性方程1. 牛顿迭代方法即考虑方程即考虑方程 f (x(k)) + f '(x(k))(x – x(k)) = 04.2 Newton迭代法及其变形 67/964.2.1 一元非线性方程一元非线性方程1. 牛顿迭代方法即考虑方程即考虑方程 f (x(k)) + f '(x(k))(x – x(k)) = 0若若f '(x(k)) ≠ 0，则有，则有令：令： k = 0，，1，，2，，… (4.2-4)称为称为Newton迭代公式迭代公式其迭代函数为其迭代函数为(4.2-5)4.2 Newton迭代法及其变形 68/964.2.1 一元非线性方程一元非线性方程2. 收敛性(1) 若若x*是是f(x)的单重根：的单重根：f (x*) = 0，，f '(x*) ≠ 0因为因为而而一一般般不不为为0，，所所以以，，Newton法法是是局局部部二二阶阶收收敛敛的的 ——由定理由定理4.2 Newton迭代法及其变形 69/964.2.1 一元非线性方程一元非线性方程2. 收敛性例例1 用用Newton法法求求非非线线性性方方程程f(x) = xex – 1 = 0在在(0，，1)内的根，取内的根，取x(0)。 解：因为解：因为f '(x) = (1 + x)ex，故其，故其Newton迭代公式为迭代公式为 k = 0，，1，，2，，…从从x(0)出发，计算结果见出发，计算结果见p342表4.2 Newton迭代法及其变形 70/964.2.1 一元非线性方程一元非线性方程2. 收敛性例例1 用用Newton法法求求非非线线性性方方程程f(x) = xex – 1 = 0在在(0，，1)内的根，取内的根，取x(0)解：因为解：因为f '(x) = (1 + x)ex，故其，故其Newton迭代公式为迭代公式为 k = 0，，1，，2，，…x1=x0-(x0*exp(x0)-1)/((1+x0)*exp(x0))while abs(x1-x0)>0.00001 & k<10 k=k+1, x0=x1; x1=x0-(x0*exp(x0)-1)/((1+x0)*exp(x0))end4.2 Newton迭代法及其变形 71/964.2.1 一元非线性方程一元非线性方程2. 收敛性(2) 若若x*是是f(x)的重根，即有的重根，即有 f(x) = (x – x*)mg(x)，其中，其中g(x*) ≠ 0，，m 2因为因为f '(x) = m(x – x*)m-1g(x) + (x – x*)mg'(x)记记x = x* + h，则，则4.2 Newton迭代法及其变形 72/964.2.1 一元非线性方程一元非线性方程2. 收敛性(2) 若若x*是是f(x)的重根，即有的重根，即有 f(x) = (x – x*)mg(x)，其中，其中g(x*) ≠ 0，，m 24.2 Newton迭代法及其变形 73/964.2.1 一元非线性方程一元非线性方程2. 收敛性(2) 若若x*是是f(x)的重根，即有的重根，即有 f(x) = (x – x*)mg(x)，其中，其中g(x*) ≠ 0，，m 24.2 Newton迭代法及其变形 74/964.2.1 一元非线性方程一元非线性方程2. 收敛性(2) 若若x*是是f(x)的重根，即有的重根，即有 f(x) = (x – x*)mg(x)，其中，其中g(x*) ≠ 0，，m 2当当m 2时，时， '(x*)≠0，且，且| '(x*)| < 1所以所以Newton迭代法一阶收敛。 迭代法一阶收敛4.2 Newton迭代法及其变形 75/964.2.1 一元非线性方程一元非线性方程2. 收敛性(3) (2)的改进中若取的改进中若取易易知知有有 '(x*) =0所所以以，，若若事事先先知知道道x*的的重重数数，，则则可可改迭代公式为改迭代公式为 (4.2-6)此时，迭代序列此时，迭代序列{x(k)}是二阶收敛的是二阶收敛的4.2 Newton迭代法及其变形 76/964.2.1 一元非线性方程一元非线性方程2. 收敛性(3)或令或令则则x*是是u的单重零点，应用的单重零点，应用Newton法于法于u(x)，有，有 (4.2-7)迭代序列也是二阶收敛的迭代序列也是二阶收敛的4.2 Newton迭代法及其变形f(x) = (x – x*)mg(x)，其中，其中g(x*) ≠ 0，，m 2 77/964.2.1 一元非线性方程一元非线性方程例例2 是方程是方程x4 – 4x2 + 4 = 0的二重根的二重根(1) 采用采用Newton法法即即注：迭代注：迭代15次次4.2 Newton迭代法及其变形 78/964.2.1 一元非线性方程一元非线性方程例例2 是方程是方程x4 – 4x2 + 4 = 0的二重根的二重根(2) 采用采用(4.2-6)x1=x0-(x0^2-2)/(2*x0)while abs(x1-x0)>0.00001 & k<10 k=k+1, x0=x1; x1=x0-(x0^2-2)/(2*x0)end迭代迭代5次次4.2 Newton迭代法及其变形 79/964.2.1 一元非线性方程一元非线性方程例例2 是方程是方程x4 – 4x2 + 4 = 0的二重根的二重根(3) 采用采用(4.2-7)即即迭代迭代5次次4.2 Newton迭代法及其变形 80/964.2.2 多元非线性方程组多元非线性方程组 f (x) = 0 (4.1-1)4.2 Newton迭代法及其变形 81/964.2.2 多元非线性方程组多元非线性方程组f (x) = 0 (4.1-1)1. Newton迭代公式线线性性化化 设设f (x) = [f1(x)，，f2(x)，，…，，fn(x)]T在在点点x(k)处可微，将处可微，将fi(x)在点在点x(k)处展开处展开用线性函数近似表示，即有用线性函数近似表示，即有 (i = 1，，2，，…，，n)4.2 Newton迭代法及其变形 82/964.2.2 多元非线性方程组多元非线性方程组1. Newton迭代公式用线性函数近似表示，即有用线性函数近似表示，即有 (i = 1，，2，，…，，n)其矩阵形式：其矩阵形式： f (x(k)) + Df (x(k))( x – x(k)) = 0 (4.2-1)4.2 Newton迭代法及其变形 83/964.2.2 多元非线性方程组多元非线性方程组1. Newton迭代公式 (i = 1，，2，，…，，n)其矩阵形式：其矩阵形式： f (x(k)) + Df (x(k))( x – x(k)) = 0 (4.2-1)4.2 Newton迭代法及其变形 84/964.2.2 多元非线性方程组多元非线性方程组1. Newton迭代公式 (i = 1，，2，，…，，n)其矩阵形式：其矩阵形式： f (x(k)) + Df (x(k))( x – x(k)) = 0 (4.2-1)其中其中是是f (x)在点在点x(k)处的处的Jacobi矩阵矩阵4.2 Newton迭代法及其变形 85/964.2.2 多元非线性方程组多元非线性方程组1. Newton迭代公式矩矩阵阵形形式式：： f (x(k)) + Df (x(k))( x – x(k)) = 0 (4.2-1)若若Df(x(k))可逆，则由可逆，则由(4.2-1)解出解出 x = x(k) – [Df (x(k))]-1f(x(k))令令 x(k+1) = x(k) – [Df (x(k))]-1f(x(k)) (4.2-2)称称(4.2-2)为为解解方方程程组组(4.2-1)的的Newton迭迭代代公公式式，，其迭代函数为其迭代函数为 x – [Df (x)]-1f(x)4.2 Newton迭代法及其变形 86/964.2.2 多元非线性方程组多元非线性方程组1. Newton迭代公式令令 x(k+1) = x(k) – [Df (x(k))]-1f(x(k)) (4.2-2)称称(4.2-2)为为解解方方程程组组(4.2-1)的的Newton迭迭代代公公式式，，其迭代函数为其迭代函数为 x – [Df (x)]-1f(x)4.2 Newton迭代法及其变形 87/964.2.2 多元非线性方程组多元非线性方程组1. Newton迭代公式令令 x(k+1) = x(k) – [Df (x(k))]-1f(x(k)) (4.2-2)称称(4.2-2)为为解解方方程程组组(4.2-1)的的Newton迭迭代代公公式式，，其迭代函数为其迭代函数为 x – [Df (x)]-1f(x)注：由于求逆较难，考虑注：由于求逆较难，考虑(4.2-2)的变形：的变形：[Df (x(k))](x(k+1) – x(k)) = – f(x(k))即解方程组：即解方程组： Df(x(k))Δx(k) = – f(x(k))求得求得Δx(k) = x(k+1) – x(k)4.2 Newton迭代法及其变形 88/964.2.2 多元非线性方程组多元非线性方程组1. Newton迭代公式 x(k+1) = x(k) – [Df (x(k))]-1f(x(k)) (4.2-2)注：由于求逆较难，考虑注：由于求逆较难，考虑(4.2-2)的变形：的变形：[Df (x(k))](x(k+1) – x(k)) = – f(x(k))即解方程组：即解方程组： Df(x(k))Δx(k) = – f(x(k))求得求得Δx(k) = x(k+1) – x(k)，即得迭代公式：，即得迭代公式： k = 0，，1，，2，，… (4.2-3)4.2 Newton迭代法及其变形 89/964.2.2 多元非线性方程组多元非线性方程组2. 收敛性定定理理4.2-1 设设x*是是f (x)的的零零点点，，f (x)在在x*的的某某一一领领域域N内二次连续可微，且内二次连续可微，且Df (x*)可逆，可逆，则则存存在在闭闭球球S = {x | ||x – x*|| ≤ } N，，由由S内内任任一一点点x(0)出出发发，，按按公公式式(4.2-2)产产生生的的序序列列{x(k)}被被包包含在含在S内内 (x(0) S{x(k)} S )，，且有且有||x(k+1) – x*|| ≤ C||x(k) – x*||2，其中，其中C与与k无关。 无关 4.2 Newton迭代法及其变形x(k+1) = x(k) – [Df (x(k))]-1f(x(k)) 90/964.2.2 多元非线性方程组多元非线性方程组2. 收敛性证明：证明： 因为因为Df(x)在在x*处连续处连续, 且且Df(x*)可逆可逆,故存在故存在 > 0，使在，使在S = {x | ||x – x*|| ≤ } N上上Df(x)可逆，且可逆，且f(x)二次连续可微于二次连续可微于S又因为又因为f(x*) = 0，所以若，所以若x(k) S，就有，就有x(k+1)–x*=x(k)–x*–[Df (x(k))]-1[f(x(k)) –f(x*)]= [Df (x(k))] -1[f(x*) –f(x(k)) + Df (x(k))(x(k) – x*)]4.2 Newton迭代法及其变形||x(k+1) – x*|| ≤ C||x(k) – x*||2 91/964.2.2 多元非线性方程组多元非线性方程组2. 收敛性证明：证明： 若若x(k) S，就有，就有x(k+1)–x*= [Df (x(k))] -1[f(x*) –f(x(k)) + Df (x(k))(x(k) – x*)]4.2 Newton迭代法及其变形||x(k+1) – x*|| ≤ C||x(k) – x*||2 92/964.2.2 多元非线性方程组多元非线性方程组2. 收敛性证明：证明： 若若x(k) S，就有，就有x(k+1)–x*=[Df (x(k))] -1[f(x*)–f(x(k))+Df (x(k))(x(k)–x*)] ||x(k+1) – x*||≤||[Df (x(k))] -1||||f(x*)–f(x(k))+Df(x(k))(x(k)–x*)||≤||[Df(x(k))]-1||max{||D2f(x*-t(x(k)-x*))||:0 ≦≦ t ≦≦1} ||x(k) - x*||2 （其中（其中f(x(k))=f(x*)+Df(x(k))(x(k)-x*)+D2f(x*-t(x(k)-x*))(x(k)-x*)24.2 Newton迭代法及其变形||x(k+1) – x*|| ≤ C||x(k) – x*||2 93/964.2.2 多元非线性方程组多元非线性方程组2. 收敛性证明：证明： 若若x(k) S，就有，就有x(k+1)–x*≤||[Df(x(k))]-1||max{||D2f(x*-t(x(k)-x*))||:0 ≦≦ t ≦≦1} ||x(k) - x*||24.2 Newton迭代法及其变形||x(k+1) – x*|| ≤ C||x(k) – x*||2 94/964.2.2 多元非线性方程组多元非线性方程组2. 收敛性证明：证明： 若若x(k) S，就有，就有||x(k+1) – x*||≤||[Df(x(k))]-1||max{||D2f(x*-t(x(k)-x*))||:0 ≦≦ t ≦≦1} ||x(k) - x*||2因为因为f 在在S上二次连续可微，所以上二次连续可微，所以max{||D2f(x*– t(x(k) – x*))||：：0 ≤ t ≤ 1}≤M[Df(x(k))]-1在在S上连续上连续, 所以所以||[Df(x(k))]-1||≤D这里这里M、、D与与k无关。 无关4.2 Newton迭代法及其变形||x(k+1) – x*|| ≤ C||x(k) – x*||2 95/964.2.2 多元非线性方程组多元非线性方程组2. 收敛性证明：证明： 若若x(k) S，就有，就有||x(k+1) – x*||≤||[Df(x(k))]-1||max{||D2f(x*-t(x(k)-x*))||:0 ≦≦ t ≦≦1} ||x(k) - x*||2max{||D2f(x*– t(x(k) – x*))||：：0 ≤ t ≤ 1}≤M ||[Df(x(k))]-1||≤D4.2 Newton迭代法及其变形||x(k+1) – x*|| ≤ C||x(k) – x*||2 96/964.2.2 多元非线性方程组多元非线性方程组2. 收敛性证明：证明： 若若x(k) S，就有，就有||x(k+1) – x*||≤||[Df(x(k))]-1||max{||D2f(x*-t(x(k)-x*))||:0 ≦≦ t ≦≦1} ||x(k) - x*||2max{||D2f(x*– t(x(k) – x*))||：：0 ≤ t ≤ 1}≤M ||[Df(x(k))]-1||≤D||x(k+1)–x*||≤DM||x(k) – x*||2 = C||x(k) – x*||2 .4.2 Newton迭代法及其变形||x(k+1) – x*|| ≤ C||x(k) – x*||2 97/964.2.2 多元非线性方程组多元非线性方程组2. 收敛性证明：证明： 若若x(k) S，就有，就有 ||x(k+1)–x*||≤DM||x(k) – x*||2 = C||x(k) – x*||2 .4.2 Newton迭代法及其变形||x(k+1) – x*|| ≤ C||x(k) – x*||2 98/964.2.2 多元非线性方程组多元非线性方程组2. 收敛性证明：证明： 若若x(k) S，就有，就有||x(k+1)–x*||≤DM||x(k) – x*||2 = C||x(k) – x*||2 .只要只要C < 1，就有，就有||x(1) – x*|| ≤ C||x(0) – x*||2 ≤ C 2 ≤ x(1) S 再由归纳法可证：再由归纳法可证：x(k) S （（ k））由由知，知，Newton法是局部二阶收敛的。 法是局部二阶收敛的4.2 Newton迭代法及其变形 99/964.2.2 多元非线性方程组多元非线性方程组例例3 用用Newton法求非线性方程组法求非线性方程组在点，在点，1)附近的根附近的根解：解：由迭代公式由迭代公式有有4.2 Newton迭代法及其变形 100/964.2.2 多元非线性方程组多元非线性方程组例例3 用用Newton法求非线性方程组法求非线性方程组在点，在点，1)附近的根附近的根解：由迭代公式解：由迭代公式有有从从x(0)，，1)T出发，计算结果见出发，计算结果见p345表4.2 Newton迭代法及其变形 101/964.2.2 多元非线性方程组多元非线性方程组例例3 用用Newton法求非线性方程组法求非线性方程组在点，在点，1)附近的根附近的根解：由迭代公式解：由迭代公式有有从从x(0)，，1)T出发，计算结果见出发，计算结果见p345表4.2 Newton迭代法及其变形 102/964.2.2 多元非线性方程组多元非线性方程组例例3 用用Newton法求非线性方程组法求非线性方程组在点，在点，1)附近的根附近的根解：解：Matlab代码：代码：k=0,x0=[1.5;1]f=[x0(1)+2*x0(2)-3;2*x0(1)^2+x0(2)^2-5];df=[1,2;4*x0(1),2*x0(2)]; dx=-inv(df)*fx1=x0+dxwhile norm(x1-x0)>0.00001 & k<10 k=k+1, x0=x1; f=[x0(1)+2*x0(2)-3;2*x0(1)^2+x0(2)^2-5]; df=[1,2;4*x0(1),2*x0(2)]; dx=-inv(df)*f x1=x0+dxend4.2 Newton迭代法及其变形 103/964.2.2 多元非线性方程组多元非线性方程组注：虽然注：虽然Newton法收敛较快，但法收敛较快，但(1) 要求要求x(0)充分靠近充分靠近x*才能保证其收敛性才能保证其收敛性(2) 每一次迭代须解方程组每一次迭代须解方程组Df(x(k))Δx(k) = – f(x(k))当当Df(x(k))不可逆时无法继续不可逆时无法继续4.2 Newton迭代法及其变形 104/964.2.2 多元非线性方程组多元非线性方程组3. 改进——Newton下山法为为改改善善对对初初始始值值的的要要求求，，在在迭迭代代公公式式中中引引入入松松弛弛因因子子 k：：x(k+1) = x(k) – k[Df (x(k))]-1f (x(k))或或 Df (x(k))Δx(k) = – k f (x(k))其中其中 k的选取满足：的选取满足： ||f (x(k +1))|| < || f (x(k))|| (4.2-10)即即|| f (x(k))||严格单减，且严格单减，且{x(k)}收敛于收敛于f 的零点。 的零点4.2 Newton迭代法及其变形 105/964.2.2 多元非线性方程组多元非线性方程组3. 改进——Newton下山法其中其中 k的选取满足：的选取满足： ||f (x(k +1))|| < || f (x(k))|| (4.2-10)即即|| f (x(k))||严格单减，且严格单减，且{x(k)}收敛于收敛于f 的零点4.2 Newton迭代法及其变形 106/964.2.2 多元非线性方程组多元非线性方程组3. 改进——Newton下山法 k的选取满足：的选取满足： ||f (x(k +1))|| < || f (x(k))|| (4.2-10)即即|| f (x(k))||严格单减，且严格单减，且{x(k)}收敛于收敛于f 的零点方法方法(1) 依次令依次令进进行行“试试探探”，，直直到到(4.2-10)满满足足，，再再进进行行下下一一次次迭代，若选不到迭代，若选不到 k，则，则Newton下山法失败下山法失败4.2 Newton迭代法及其变形 107/964.2.2 多元非线性方程组多元非线性方程组3. 改进——Newton下山法方法方法(2) 求求的最小值点的最小值点 *令令 x(k +1) = x(k) – *[Df (x(k))]-1f(x(k)) 这这样样迫迫使使序序列列{|| f (x(k))||}严严格格单单调调下下降降，，从从而而从某个从某个x(k)开始进入开始进入x*的附近。 的附近4.2 Newton迭代法及其变形 108/964.2.2 多元非线性方程组多元非线性方程组3. 改进——Newton下山法例例4 求解非线性方程组求解非线性方程组初值取初值取x(0)，，1]T(1) 用用Newton法：法：4.2 Newton迭代法及其变形 109/964.2.2 多元非线性方程组多元非线性方程组3. 改进——Newton下山法例例4 求解非线性方程组求解非线性方程组初值取初值取x(0)，，1]T(2) 用用Newton下山法：下山法：4.2 Newton迭代法及其变形 110/96问题：求函数问题：求函数F(x)的最小值，即确定的最小值，即确定x* Rn 使使注：注：(1) 该问题为最优化理论中无约束化问题该问题为最优化理论中无约束化问题(2) 上述最小值点记为上述最小值点记为4.3 无约束优化问题的下降迭代法 111/964.3.0 预备知识预备知识(1) 设多元函数设多元函数F(.)具二阶连续偏导数，具二阶连续偏导数，记记 ——F的梯度的梯度g为多元向量值函数为多元向量值函数4.3 无约束优化问题的下降迭代法 112/964.3.0 预备知识预备知识(1) 设多元函数设多元函数F(.)具二阶连续偏导数，具二阶连续偏导数，故有故有Jacobi阵：阵：称为称为F的的Hesse矩阵矩阵4.3 无约束优化问题的下降迭代法 113/964.3.0 预备知识预备知识(2) 多元函数泰勒展开：多元函数泰勒展开：(3)4.3 无约束优化问题的下降迭代法 114/964.3.0 预备知识预备知识(4) 设二次函数设二次函数其中其中A正定，正定，b为向量为向量则（梯度）则（梯度） F(x) = Ax + b 其中其中4.3 无约束优化问题的下降迭代法 115/964.3.0 预备知识预备知识(5) 下降迭代法下降迭代法——求求目目标标：：构构造造使使F(x)逐逐步步严严格格下下降降（（递递减减））的的迭迭代代序序列：列：F(x(k +1)) < F(x(k)) k = 0，，1，，2，，...方方法法：：设设已已有有点点x(k)，，若若从从x(k)出出发发沿沿任任何何方方向向移移动动F(x)都不再严格减少，则都不再严格减少，则x(k)为局部最小值点。 为局部最小值点若若至至少少有有一一个个方方向向，，使使F(x)严严格格减减少少，，则则从从中中任任选选一方向一方向pk，并在此方向上移动一步，并在此方向上移动一步4.3 无约束优化问题的下降迭代法 116/964.3.0 预备知识预备知识(5) 下降迭代法下降迭代法——求求方法：方法：若若至至少少有有一一个个方方向向，，使使F(x)严严格格减减少少，，则则从从中中任任选选一方向一方向pk，并在此方向上移动一步，并在此方向上移动一步4.3 无约束优化问题的下降迭代法 117/964.3.0 预备知识预备知识(5) 下降迭代法下降迭代法——求求方法：方法：若若至至少少有有一一个个方方向向，，使使F(x)严严格格减减少少，，则则从从中中任任选选一方向一方向pk，并在此方向上移动一步，并在此方向上移动一步 x(k +1) = x(k) + tkpk (4.3-1)其中其中tk > 0（称为步长因子）使（称为步长因子）使 F(x(k +1)) = F(x(k) + tkpk) < F(x(k)) (4.3-2)4.3 无约束优化问题的下降迭代法 118/964.3.0 预备知识预备知识(5) 下降迭代法下降迭代法——求求方法：方法： x(k +1) = x(k) + tkpk (4.3-1)其中其中tk > 0（称为步长因子）使（称为步长因子）使 F(x(k +1)) = F(x(k) + tkpk) < F(x(k)) (4.3-2)4.3 无约束优化问题的下降迭代法 119/964.3.0 预备知识预备知识(5) 下降迭代法下降迭代法——求求方法：方法：x(k +1) = x(k) + tkpk (4.3-1)其中其中tk > 0（称为步长因子）使（称为步长因子）使 F(x(k +1)) = F(x(k) + tkpk) < F(x(k)) (4.3-2)若若此此方方法法产产生生的的序序列列{x(k)}收收敛敛于于x*，，则则此此方方法法有有效，否则无效。 效，否则无效不同规则对应不同的方法不同规则对应不同的方法4.3 无约束优化问题的下降迭代法 120/964.3.0 预备知识预备知识注注：：(1) 下降方向下降方向pk的选取：的选取：由泰勒展式知，当由泰勒展式知，当t充分小时充分小时 F(x(k) + tpk) = F(x(k)) + t [ F(x(k))]Tpk +o(t) = F(x(k)) + t gkTpk +o(t)其中其中o(t)为为t的高阶无穷小，梯度的高阶无穷小，梯度gk= F(x(k))由由(4.3-2) F(x(k +1)) = F(x(k) + tk pk) < F(x(k))知，应知，应有有 gkTpk < 0 (4.3-3)4.3 无约束优化问题的下降迭代法 121/964.3.0 预备知识预备知识注注：：(1) 下降方向下降方向pk的选取：的选取：由泰勒展式知，当由泰勒展式知，当t充分小时充分小时 F(x(k) + tpk) = F(x(k)) + t gkTpk +o(t)其中其中o(t)为为t的高阶无穷小，梯度的高阶无穷小，梯度gk= F(x(k))由由(4.3-2) F(x(k +1)) = F(x(k) + tk pk) < F(x(k))知，应知，应有有 gkTpk < 0 (4.3-3)4.3 无约束优化问题的下降迭代法 122/964.3.0 预备知识预备知识注注：：(1) 下降方向下降方向pk的选取：的选取：由泰勒展式知，当由泰勒展式知，当t充分小时充分小时 F(x(k) + tpk) = F(x(k)) + t gkTpk +o(t)其中其中o(t)为为t的高阶无穷小，梯度的高阶无穷小，梯度gk= F(x(k))由由(4.3-2) F(x(k +1)) = F(x(k) + tk pk) < F(x(k))知，应知，应有有 gkTpk < 0 (4.3-3)例例如如取取 pk = – gk （（F(x)沿沿负负梯梯度度方方向向下下降降最最快快））称为最速下降称为最速下降4.3 无约束优化问题的下降迭代法 123/964.3.0 预备知识预备知识注注：：(2) 步长因子的选取：步长因子的选取：tk可沿射线可沿射线x = x(k) + tpk (t > 0) 进行一维搜索来确定进行一维搜索来确定例如，取例如，取 tk = argminF(x(k) + tpk) (4.3-4)称为最佳步长因子。 称为最佳步长因子实际计算不易求得，通常求不精确最佳步长因子实际计算不易求得，通常求不精确最佳步长因子例如，使用例如，使用“成功成功-失败失败”试探法：试探法：4.3 无约束优化问题的下降迭代法 124/964.3.0 预备知识预备知识注注：：(2) 步长因子的选取：步长因子的选取： tk = argminF(x(k) + tpk) (4.3-4)称为最佳步长因子称为最佳步长因子实际计算不易求得，通常求不精确最佳步长因子实际计算不易求得，通常求不精确最佳步长因子例如，使用例如，使用“成功成功-失败失败”试探法：试探法：4.3 无约束优化问题的下降迭代法 125/964.3.0 预备知识预备知识注注：：(2) 步长因子的选取：步长因子的选取：tk = argminF(x(k) + tpk) (4.3-4)称为最佳步长因子称为最佳步长因子实际计算不易求得，通常求不精确最佳步长因子实际计算不易求得，通常求不精确最佳步长因子例如，使用例如，使用“成功成功-失败失败”试探法：试探法：先先取取定定一一步步长长因因子子 ，，若若F(x(k) + pk) < F(x(k))，，则则成功，否则失败，再取步长因子成功，否则失败，再取步长因子 /2比较，比较，...4.3 无约束优化问题的下降迭代法 126/964.3.1 最速下降法最速下降法1. 迭代公式取取pk = – gk ( = F(x(k)))即即为为最最速速下下降降法法，，其其迭迭代代公公式（以选最佳步长因子为例）式（以选最佳步长因子为例） k = 0，，1，，2，，... (4.3-5)4.3 无约束优化问题的下降迭代法 127/964.3.1 最速下降法最速下降法1. 迭代公式例例1 设二次函数设二次函数 (4.3-6)其中其中A正定，则正定，则——可以求出最佳步长因子可以求出最佳步长因子tk事实上：因为事实上：因为 所以所以4.3 无约束优化问题的下降迭代法 128/964.3.1 最速下降法最速下降法1. 迭代公式例例1 设二次函数设二次函数 (4.3-6)其中其中A正定，则正定，则事实上：事实上：而而所以所以0=-[ F(x(k)–tkgk)]Tgk= -[ F(x(k+1))]Tgk= -gk+1Tgk (4.3-7)4.3 无约束优化问题的下降迭代法 129/964.3.1 最速下降法最速下降法1. 迭代公式例例1 设二次函数设二次函数 (4.3-6)其中其中A正定，则正定，则事实上：事实上： 0 = -gk+1Tgk (4.3-7)4.3 无约束优化问题的下降迭代法 130/964.3.1 最速下降法最速下降法1. 迭代公式例例1 设二次函数设二次函数 (4.3-6)其中其中A正定，则正定，则事实上：事实上： 0 = -gk+1Tgk (4.3-7)而而 g(x) = F(x) = Ax + b，， 所以所以gk = Ax(k) + b gk+1 = Ax(k+1) + b = A(x(k) – tkgk) + b = Ax(k) + b – tkAgk = gk – tkAgk4.3 无约束优化问题的下降迭代法 131/964.3.1 最速下降法最速下降法1. 迭代公式例例1 设二次函数设二次函数 (4.3-6)其中其中A正定，则正定，则事实上：事实上： 0 = -gk+1Tgk (4.3-7) gk+1 = Ax(k) + b – tkAgk = gk – tkAgk4.3 无约束优化问题的下降迭代法 132/964.3.1 最速下降法最速下降法1. 迭代公式例例1 设二次函数设二次函数 (4.3-6)其中其中A正定，则正定，则事实上：事实上： 0 = -gk+1Tgk (4.3-7) gk+1 = Ax(k) + b – tkAgk = gk – tkAgk从而从而0 = [gk – tkAgk]Tgk = gkTgk – tkgkTAgk (4.3-8)4.3 无约束优化问题的下降迭代法 133/964.3.1 最速下降法最速下降法1. 迭代公式例例1 设二次函数设二次函数 (4.3-6)其中其中A正定，则正定，则所以二次函数所以二次函数(4.3-6)最速下降法的迭代公式为最速下降法的迭代公式为 k = 0，，1，，2，，... (4.3-9)4.3 无约束优化问题的下降迭代法 134/964.3.1 最速下降法最速下降法2. 算法流程图求求F(x)的最小值的最小值4.3 无约束优化问题的下降迭代法输入输入F，，eps，，x = x0计算计算F(x)，，g(x)= F(x)若若|| g(x)|| > epst = argminF(x – t*g(x))x = x – t*g(x)计算计算F(x)，，g(x)= F(x)输出输出x，，F(x) 135/964.3.1 最速下降法最速下降法例例1 用最速下降法求解极值问题用最速下降法求解极值问题 其中其中F(x1，，x2) = 2x12 + 2x1x2 + 5x22取取x(0) = [1，，-1]T出发。 见出发见p350））解：解：F(x)是二次函数，且是二次函数，且4.3 无约束优化问题的下降迭代法 136/964.3.1 最速下降法最速下降法例例1 用最速下降法求解极值问题用最速下降法求解极值问题 其中其中F(x1，，x2) = 2x12 + 2x1x2 + 5x22解：解：4.3 无约束优化问题的下降迭代法 137/964.3.1 最速下降法最速下降法例例1 用最速下降法求解极值问题用最速下降法求解极值问题 其中其中F(x1，，x2) = 2x12 + 2x1x2 + 5x22解：解：4.3 无约束优化问题的下降迭代法 138/964.3.1 最速下降法最速下降法注：因为最优因子注：因为最优因子tk满足：满足：gk+1Tgk = 0 (4.3-7)所所以以方方向向pk+1与与pk总总是是互互相相垂垂直直的的，，称称为为锯锯齿齿状状下下降（图）此方向在接近极小值点时收敛速度变慢降（图）此方向在接近极小值点时收敛速度变慢4.3 无约束优化问题的下降迭代法 139/964.3.2 变尺度法变尺度法1. 思想为改善收敛速度，考虑在为改善收敛速度，考虑在x*处的泰勒展开处的泰勒展开:因为因为 x*= argminF(x) g(x*) = F(x*) = 0 又因为又因为 F(x) = g(x) H(x*)(x – x*)4.3 无约束优化问题的下降迭代法 140/964.3.2 变尺度法变尺度法1. 思想 F(x) = g(x) H(x*)(x – x*)4.3 无约束优化问题的下降迭代法 141/964.3.2 变尺度法变尺度法1. 思想 F(x) = g(x) H(x*)(x – x*)设设H正定正定(从而可逆从而可逆)，令，令H(x*)(x – x*) = g(x) x* = x – [H(x*)]-1g(x) = x – Bg(x) (4.3-10)上上式式表表明明：：用用B = [H(x*)]-1作作用用于于– g(x)，，将将使使最最速速下降方向下降方向– g(x)变为直指变为直指x* 启示：用启示：用–Bg(x)作搜索方向。 作搜索方向4.3 无约束优化问题的下降迭代法 142/964.3.2 变尺度法变尺度法2. 迭代公式为为 了了 保保 证证 –Bg(x)是是 下下 降降 方方 向向 ，， 由由 (4.3-3)知知 ，， 只只 须须 g(x)T(–Bg(x)) < 0，，即即 g(x)TBg(x) > 0所以当所以当B正定时（正定时（g(x)TBg(x) > 0））必有必有–Bg(x)为下降方向，从而迭代公式为为下降方向，从而迭代公式为 x(k +1) = x(k) – tkBkgk k = 0, 1, 2, ...(4.3-11)其中其中tk为步长因子，可通过一维搜索来确定为步长因子，可通过一维搜索来确定4.3 无约束优化问题的下降迭代法gkTpk < 0 143/964.3.2 变尺度法变尺度法2. 迭代公式x(k +1) = x(k) – tkBkgk k = 0, 1, 2, ...(4.3-11)注：注：(1) 当当 Bk = I时时, (4.3-11)即为最速下降法的迭代公式即为最速下降法的迭代公式(2) 当当Bk = [H(x(k))]-1时，迭代公式为时，迭代公式为 x(k+1) = x(k) – tk[H(x(k))]-1gk k=0,1,2,...(4.3-12) = x(k) – tk[Dg(x(k))]-1gk (Dg(x(k))为为g的的Jacobi矩阵矩阵)即为即为Newton下山法下山法4.3 无约束优化问题的下降迭代法 144/964.3.2 变尺度法变尺度法2. 迭代公式x(k +1) = x(k) – tkBkgk k = 0, 1, 2, ...(4.3-11)注：注：(2) 当当Bk = [H(x(k))]-1时，迭代公式为时，迭代公式为 x(k+1) = x(k) – tk[H(x(k))]-1gk k=0,1,2,...(4.3-12)(3) 由由于于F(x)的的Hesse矩矩阵阵H(x) = Dg(x)之之逆逆可可能能在在某某些点不存在些点不存在4.3 无约束优化问题的下降迭代法 145/964.3.2 变尺度法变尺度法2. 迭代公式x(k +1) = x(k) – tkBkgk k = 0, 1, 2, ...(4.3-11)注：注：(2) 当当Bk = [H(x(k))]-1时，迭代公式为时，迭代公式为 x(k+1) = x(k) – tk[H(x(k))]-1gk k=0,1,2,...(4.3-12)(3) 由由于于F(x)的的Hesse矩矩阵阵H(x) = Dg(x)之之逆逆可可能能在在某某些些点点不不存存在在，，即即使使存存在在，，计计算算量量也也很很大大，，所所以以考考虑虑从从[H(x(k))]-1的近似方阵出发，每次迭代进行修正的近似方阵出发，每次迭代进行修正4.3 无约束优化问题的下降迭代法 146/964.3.2 变尺度法变尺度法3. DFP方法考虑对考虑对Bk = [H(x(k))] -1附加条件附加条件(1) Bk应正定应正定(2) 从从Bk到到Bk+1应简单：应简单：Bk+1= Bk+ ΔBk(3) Bk满足拟满足拟Newton条件：条件：Bk+1yk=sk，其中，其中yk=gk+1– gk，，sk= x(k +1) – x(k) 从而从而(ΔBk) yk = (Bk+1-Bk)yk=sk –Bkyk，，设设ΔBk = skvkT–BkykwkT，，(vk，，wk待定待定)4.3 无约束优化问题的下降迭代法 147/964.3.2 变尺度法变尺度法3. DFP方法(1) Bk应正定应正定(2) 从从Bk到到Bk+1应简单：应简单：Bk+1= Bk+ ΔBk(3) Bk满足拟满足拟Newton条件：条件：Bk+1yk=sk，其中，其中yk=gk+1– gk，，sk= x(k +1) – x(k) 从而从而(ΔBk) yk = (Bk+1-Bk)yk=sk –Bk yk设设ΔBk = skvkT–Bk ykwkT，，(vk，，wk待定待定)解之得解之得4.3 无约束优化问题的下降迭代法 148/964.3.2 变尺度法变尺度法3. DFP方法(1) Bk应正定应正定(2) 从从Bk到到Bk+1应简单：应简单：Bk+1= Bk+ ΔBk(3)4.3 无约束优化问题的下降迭代法 149/964.3.2 变尺度法变尺度法3. DFP方法(1) Bk应正定应正定(2) 从从Bk到到Bk+1应简单：应简单：Bk+1= Bk+ ΔBk(3)所以所以4.3 无约束优化问题的下降迭代法 150/964.3.2 变尺度法变尺度法3. DFP方法x(k +1) = x(k) – tkBkgk k = 0, 1, 2, ...(4.3-11)Bk正定，满足拟正定，满足拟Newton条件：条件： (4.3-20)(4.3-20)称为称为DFP方法方法注：注：(1) 通常取通常取B0 = I(2) DFP方方法法很很有有效效，，但但由由于于舍舍入入误误差差的的影影响响，，可可能破坏能破坏Bk的正定性，使计算失效。 的正定性，使计算失效4.3 无约束优化问题的下降迭代法 151/964.3.2 变尺度法变尺度法3. DFP方法x(k +1) = x(k) – tkBkgk k = 0, 1, 2, ...(4.3-11)Bk正定，满足拟正定，满足拟Newton条件：条件： (4.3-20)(4.3-20)称为称为DFP方法方法注：可采用重置措施：注：可采用重置措施：即即当当函函数数值值不不下下降降时时取取Bk = I，，继继续续迭迭代代，，并并且且当当迭代迭代n + 1次后，令次后，令x(0) = x(n+1)，，Bn = I，重新迭代，重新迭代4.3 无约束优化问题的下降迭代法 152/964.3.2 变尺度法变尺度法3. DFP方法例例2 用用DFP方法求解方法求解minF(x1，，x2)：：取取解：解：k = 0，，取取B0 = I，，即即为为最最速速下下降降法法 x(1) = x(0) – t0B0g04.3 无约束优化问题的下降迭代法 153/964.3.2 变尺度法变尺度法3. DFP方法例例2 用用DFP方法求解方法求解minF(x1，，x2)：：解：解：k = 0，，取取B0 = I，，即即为为最最速速下下降降法法 x(1) = x(0) – t0B0g04.3 无约束优化问题的下降迭代法 154/964.3.2 变尺度法变尺度法3. DFP方法例例2 用用DFP方法求解方法求解minF(x1，，x2)：：解：解：k = 1，取，取其中其中s0 = x(1) – x(0)，，y0 = g1 – g04.3 无约束优化问题的下降迭代法 155/964.3.2 变尺度法变尺度法3. DFP方法例例2 用用DFP方法求解方法求解minF(x1，，x2)：：解：解： k = 1，取，取其中其中s0 = x(1) – x(0)，，y0 = g1 – g0搜索方向：搜索方向：p1 = – B1g14.3 无约束优化问题的下降迭代法 156/964.3.2 变尺度法变尺度法3. DFP方法4.3 无约束优化问题的下降迭代法 157/964.3.2 变尺度法变尺度法4. BFGS方法比比DFP更好的方法是更好的方法是BFGS方法，其中方法，其中(4.3-21)4.3 无约束优化问题的下降迭代法 。
