4计算函数零点和极值点的迭代法

第4章  计算函数零点和极值点的迭代法 本章讨论非线性方程（组）的求解问题 4.1  不动点迭代法及其收敛性 1．不动点 设非线性方程组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)的不动点。 注：(1) 求零点 求不动点 (2) (.)称为迭代函数，{x(k)}称为迭代序列 (3) 不同构造迭代函数，得不同的迭代序列 2．迭代法的基本问题 (1) 如何构造适当的迭代函数(.)使迭代序列{x(k)}收敛 (2) 收敛的速度和误差 (3) 如何加速 4.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]内有且仅有一根。 2. 迭代序列的收敛性 因为可以有多种迭代函数，所产生的迭代序列{x(k)}有可能： (1)    收敛快 (2)    收敛慢 (3)    不收敛 例1  f(x) = x3 – x – 1 = 0，求f在x = 1.5附近的根，初值取x(0) = 1.5。(p328) 取 ——收敛 取(x) = x3 – 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-5) ：(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* (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*| 矛盾，所以不动点唯一。 由|x(k) – x*| = |( x(k-1)) – (x*)| L|x(k-1) – x*| … L k|x(0) – x*| 及0 < L < 1知 即x(k)收敛于x*。 并且由|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)|，代入上式的右边，即得 注：(1) 若L 1，则收敛很慢，须考虑加速问题 (2) (4.1-5)中第一式为后验公式—迭代停止准则 第二式为先验公式—预测迭代次数 (3)    定理是以[a，b]中任一点作初值，迭代都收敛，称为全局收敛。 （此要求较难满足，故考虑在） x*的某一邻域内—局部收敛性 定理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 < 1 x [x* –，x* + ]，|(x) –x*| = |(x) – (x*)| = |'(ξ)| |x – x*| q|x – x*| < ，即(x) [x* –，x* + ]，由定理4.1-1知，任意x(0) [x* –，x* + ]，迭代法x(k+1) = (x(k))收敛。 注：只要x(0)充分接近x*，且| '(x(0))| 明显小于1，则{x(k)}收敛于x*。 例2  求方程x = e–x在0.5附近的根。 由于| '(0.5)| = e–0.5 0.61明显小于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，称平方收敛 因为| x(k+1) –x*| = |(x(k)) – (x*)| = |'(ξ)| |x(k) – x*|，其中ξ在x(k)和x*之间。 则 所以若 '(x*) 0，则为线性收敛 想得到更高阶的收敛性，须 '(x*) = 0，通常可考虑麦克劳林展式。 定理4.1-3  设x*为的不动点，正整数p 2，若(p)在x*的某邻域内连续，且满足 (4.1.6) 则{x(k)}p阶局部收敛。 证明：∵ '(x*) = 0(<1)，∴x(k)局部收敛。设(x)在x*处展开为 由(4.1-6)知， 所以 即{x(k)}p阶局部收敛。 例3  设f C2[a，b]， (x) = x – r1(x)f(x) – r2(x)f 2(x)，x*为f的单重零点。试确定未知函数r1(x)、r2(x)，使迭代法x(k+1) = (x(k))至少是三阶局部收敛的。解：由定理4.1-3知，应有 '(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*) = 0即取 ，则有 '(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) 其中 令"(x*) = 0，有 ，即取 ，则有"(x*) = 0从而只要同时取 ， ，迭代法至少具有三阶局部收敛性。 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-7) 记 ，则{ }比{x(k)}收敛得快。 定理4.1-4  设{x(k)}线性收敛于x*，且k 0，ek = x(k) – x* ≠ 0   0 < | | < 1    (线性收敛) 则 证明：因为 所以ek+1 = ( +εk)ek，其中εk 0 x(k+1) – x(k) = x(k+1) – x* – (x(k) – x*) = ek+1 – ek = [( – 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]ek = [( – 1)2 + k]ek. 其中 k = εk+1 +( – 2 )εk +εk+1εk 0 所以 注：(1) (4.1-7)成为Aitken加速 (2)   k = 1，2，… 称为史蒂文生迭代法。 例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收敛。 Steffensen迭代法的计算公式为： 取初值x(0) = 3作迭代，结果见p336 迭代法x(k+1) = ln x(k) + 2： x0=3 k=1 x1=log(x0)+2 while (abs(x1-x0)>0.0000001) x0=x1;k=k+1 x1=log(x0)+2 end Steffensen迭代法 x0=3 k=1 y=log(x0)+2 z=log(y)+2 x1=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) end 4.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) 其收敛性有下述压缩映射（不动点）原理 Th4.1-5  设Φ在闭区域 上满足条件 (1) 存在q，0 < q < 1，使x，y ，有||Φ(x) – Φ(y)|| q||x – y|| (2) x Φ(x) 则 (1) 存在唯一不动点x* ，且 x(0) ，迭代向量列收敛于x*。 (2) 证明与Th2.4-3相似 注： (1) 保证序列 (2) 若i(x)在 上可微，Φ(x) = (1(x)，2(x)，…，n(x))T 记 ，则压缩条件可用下式替代 例5  4.2    Newton迭代法及其变形 4.2.1  一元非线性方程 f(x) = 0 1. 牛顿迭代方法 线性化：  设f(x)在点x(k)处可微，则展开 用线性部分近似示 f(x) f(x(k)) + f '(x(k))( x – x(k)) 即考虑方程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) 2. 收敛性 (1) 若x*是f(x)的单重根： f(x*) = 0，f '(x*) ≠ 0 因为 一般不为0 所以，牛顿法是局部二阶收敛的  ——由定理4.1-3 例1  用Newton法求非线性方程f (x) = xex – 1 = 0在(0，1)内的根，取x(0) = 0.5。 解：因为f (x) = (1 + x)ex，故其Newton迭代公式为 ，k = 0，1，2，… 从x(0) = 0.5出发，计算结果见p342表4.2-1。 (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，则 当m 2时， '(x*) ≠ 0，由| '(x*)| < 1，知Newton迭代法一阶收敛。 (3) (2)的改进中若取 ，易知有 '(x*) = 0所以，若事先知道x*的重数，则可改迭代公式为 (4.2-6) 此时，迭代序列{x(k)}是二阶收敛的。 或令 ，则x*是 的单重零点，应用Newdon法于u(x)，有 (4.2-7) 迭代序列也是二阶收敛的 例2  是方程x4 – 4x2 + 4 = 0的二重根 (1) 采用Newdon法 即 (2) 采用(4.2-6) (3) 采用(4.2-7) ， 即 计算结果见343页表4.2-2 4.2.2  多元非线性方程组 f(x) = 0    (4.1-1) 1. Newdon迭代公式 线性化 设f(x) = [f1(x)，f2(x)，…，fn(x)]T在点x(k)处可微，将fi(x)在点x(k)处展开 用线性函数近似表示，即有 (i = 1，2，…，n) 其矩阵形式：f(x(k)) + Df (x(k))( x – x(k)) = 0    (4.2-1) 其中 是f(x)在点x(k)处的Jacobi矩阵 若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)的Newdon迭代公式，其迭代函数为 x – [Df (x)]-1f(x) 注：由于求逆较难，一般可解方程组： Df(x(k))Δx(k) = – f(x(k)) 求得Δx(k) = x(k+1) – x(k)即得迭代公式： k = 0，1，2，…    (4.2-3) 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无关。 证明：因为Df(x)在x*处连续，且Df(x*)可逆，故存在 > 0，使在S = {x | ||x – x*|| ≤ } N上Df(x)可逆，且f二次连续可微于S。又因为f(x*) = 0，所以若x(k) S，就有 x(k+1) – x* = x(k) – x* – [Df (x(k))]-1[f(x(k)) –f(x*)]      （f (x*) = 0） = [Df (x(k))] -1[f(x(k)) –f(x*) + Df (x(k))(x(k) – x*)] ||x(k+1) – x*|| ≤ ||[Df (x(k))] -1|| || f(x(k)) –f(x*) + 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在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无关。  ||x(k+1) – x*|| ≤ D M ||x(k) – x*||2 = C||x(k) – x*||2 . 只要C < 1，就有||x(1) – x*|| ≤ C||x(0) – x*||2 ≤ C2 ≤   x(1) S  再由归纳法可证：x(k) S  （k） 注：由 知，Newton法是局部二阶收敛的。 例3  用Newton法求非线性方程组 在点(1，5，1)附近的根。 解： 由迭代公式 有 从x(0) = (1，5，1)T出发，计算结果见p345表4.2-3。 注：虽然Newton法收敛较快，但 (1) 要求x(0)充分靠近x*才能保证其收敛性 (2) 每一次迭代须解方程组Df(x(k))Δx(k) = – f(x(k)) 当Df(x(k))不可逆时无法继续 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的零点。 方法(1) 依次令 进行“试探”，直到(4.2-10)满足，再进行下一次迭代，若选不到k，则Newton下山法失败 方法(2) 求 的最小值点* 令x(k +1) = x(k) – *[Df (x(k))]-1f(x(k)) 这样迫使序列{|| f(x(k))||}严格单调下降，从而从某个x(k)开始进入x*的附近。  4.3  无约束优化问题的下降迭代法 问题：求函数F(x)的最小值，即确定x* Rn使 注：(1) 该问题为最优化理论中无约束化问题 (2) 上述最小值点记为 4.3.0  预备知识 (1) 设F(.)具二阶连续偏导数，记 F的梯度 g为多元向量值函数，故有Jacobi阵： 称为F的Hesse矩阵 (2) 泰勒展开： (3) (4) 设     ——二次函数，其中A正定，b为向量 则F(x) = Ax + b  其中 (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，并在此方向上移动一步： 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*，则此方法有效，否则无效。 方法：不同规则对应不同的方法。 注：(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)知，应有gkTpk < 0            (4.3-3) 例如取pk = – gk （F(x)沿负梯度方向下降最快）称为最速下降 (2) 步长因子的选取： tk可沿射线x = x(k) + tpk (t > 0) 进行一维搜索来确定 例如，取 tk = argminF(x(k) + tpk)    (4.3-4)    称为最佳步长因子 实际计算不易求得，通常求不精确最佳步长因子 例如，使用“成功-失败”试探法 先取定一步长因子，若F(x(k) + pk) < F(x(k))，则成功，否则失败，再取步长因子/2比较，... 4.3.1  最速下降法 1. 迭代公式 取pk = – gk ( = F(x(k)))即为最速下降法，其迭代公式（以选最佳步长因子为例） k = 0，1，2，...    (4.3-5) 例1  设 (4.3-6) ——二次函数，其中A正定，则 ——可以求出最佳步长因子tk 事实上：因为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 – tkAgk 另一方面： 所以 而 所以 – [F(x(k) – tkgk)]Tgk = – [F(x(k+1))]Tgk = – gk+1Tgk = 0    (4.3-7) 从而0 = [gk – tkAgk]Tgk = gkTgk – tkgkTAgk       (4.3-8) 所以二次函数(4.3-6)最速下降法的迭代公式为