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

第4章 计算函数零点和极值点的迭代法本章讨论非线性方程（组）的求解问题4.1 不动点迭代法及其收敛性1不动点设非线性方程组f(x) = 0 (4.1-1)等价： x = F(x) (4.1-2)则有迭代格式：x(k+1) = F(x(k)，k = 0，1，2，若F连续，且迭代序列x(k)收敛到x*，则两边取极限得x* = F(x*)，即x*满足(4.1-2)，从而满足(4.1-1)，即x*为f零点。称x*为F(x)的不动点。注：(1) 求零点求不动点(2) F(.)称为迭代函数，x(k)称为迭代序列(3) 不同方法构造迭代函数，得不同的迭代序列2迭代法的基本问题(1) 如何构造适当的迭代函数F(.)使迭代序列x(k)收敛(2) 收敛的速度和误差(3) 如何加速4.1.1 解一元方程的迭代法1. 根的隔离设一元方程f(x) = 0，f连续，其实根可能有很多，需将各根隔离，即f在a，b内有且仅有一根。方法：设f Ca，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)取收敛取j(x) = x3 1不收敛定理4.1-1 (1) 设j(x) Ca，b，且对于任意x a，b有j (x) a，b，则j在a，b上必有不动点。(2) 进一步，若j(x) C1a，b，且存在L 1，使对于任意的x a，b有|j (x)| L 1 (4.1-4)则对于任意的x(0) a，b，x(k+1) = j(x(k)收敛于唯一不动点x* a，b。且有 (4.1-5)证明：(1) 若j(a) = a或j(b) = b，则结论显然成立现设a j(a)，j(b) 0，y(b) = j(b) b 0，故存在x* a，b，使y(x*) = 0，即j(x*) x* = 0 j(x*) = x*(2) 设j(x) C1a，b，且满足(4.1-4)，若有x1*，x2* a，b，x1* x2*，j(xi*) = xi* i = 1，2由微分中值定理，|x1* x2*| = |j(x1*) j (x2*)| = |j()| |x1* x2*| L|x1* x2*| |x1* x2*| 矛盾，所以不动点唯一。由|x(k) x*| = |j( x(k-1) j (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)| = |j(x(k-1) j (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*为j的不动点，j 在x*的某邻域内连续，且|j (x*)| 0，只要x(0) x* d，x* + d，迭代法x(k+1) = j(x(k)收敛。证明：|j(x*)| 0，使x* d，x* + d U(x*)，且 x x* d，x* + d有|j (x)| q 1 x x* d，x* + d，|j(x) x*| = |j(x) j(x*)| = |j()| |x x*| q|x x*| d，即j(x) x* d，x* + d，由定理4.1-1知，任意x(0) x* d，x* + d，迭代法x(k+1) = j(x(k)收敛。注：只要x(0)充分接近x*，且|j (x(0)| 明显小于1，则x(k)收敛于x*。例2 求方程x = ex在0.5附近的根。由于|j (0.5)| = e0.5 0.61明显小于1，故收敛3. 收敛阶定义4.1-1 设x(k) x*，记ek= x(k) - x* 若存在p 1，及c0，使则称x(k)是p阶收敛的，或称收敛阶为p（p越高收敛越快）注：(1) p = 1，0 c 1，称超线性收敛(3) p = 2，称平方收敛因为| x(k+1) x*| = |j(x(k) j(x*)| = |j()| |x(k) x*|，其中在x(k)和x*之间。则所以若j (x*) 0，则为线性收敛想得到更高阶的收敛性，须j (x*) = 0，通常可考虑麦克劳林展式。定理4.1-3 设x*为j的不动点，正整数p 2，若j(p)在x*的某邻域内连续，且满足 (4.1.6)则x(k)p阶局部收敛。证明：j (x*) = 0(1)，x(k)局部收敛。设j(x)在x*处展开为由(4.1-6)知，所以即x(k)p阶局部收敛。例3 设f C2a，b，j (x) = x r1(x)f(x) r2(x)f 2(x)，x*为f的单重零点。试确定未知函数r1(x)、r2(x)，使迭代法x(k+1) = j(x(k)至少是三阶局部收敛的。解：由定理4.1-3知，应有j (x*) = j (x*) = 0因为j (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（单重零点），令j (x*) = 0，有1 r1(x*)f (x*) = 0即取，则有j (x*) = 0此时有j (x) = r1(x)f(x) r2(x)f 2(x) 2r2(x)f (x)f (x) j (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)其中令j(x*) = 0，有，即取，则有j(x*) = 0从而只要同时取，迭代法至少具有三阶局部收敛性。4. 加速幂法中曾有Aitken加速，这里使用相同的思想若x(k) x*，由中值定理， x(k+1) x* = j (x(k) j (x*) = j(1)(x(k) x*) 1在x(k)和x*之间x(k+2) x* = j (x(k+1) j (x*) = j(2)(x(k+1) x*) 2在x(k+1)和x*之间因为x(k) x*，所以当k充分大时，j (1) j (2) 即 (4.1-7)记，则比x(k)收敛得快。定理4.1-4 设x(k)线性收敛于x*，且k 0，ek = x(k) x* 0 0 |l | 1 (线性收敛)则证明：因为所以ek+1 = (l +k)ek，其中k 0 x(k+1) x(k) = x(k+1) x* (x(k) x*) = ek+1 ek = (l 1) + kek又x(k+2) 2x(k+1) + x(k) = (x(k+2) x(k+1) (x(k+1) x(k)= (l 1) + k+1ek+1 (l 1) + kek= (l 1) + k+1(l + k)ek (l 1) + kek= (l 1)2 + m kek.其中m k = lk+1 +(l 2 )k +k+1k 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 = j (x)，由于j (x) = 1/x在2，+)上满足|j (x)| 1/2 1，且2 j (x) 0.0000001) x0=x1;k=k+1 x1=log(x0)+2endSteffensen迭代法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.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) 若ji(x)在上可微，(x) = (j1(x)，j2(x)，jn(x)T记，则压缩条件可用下式替代例5 4.2 Newton迭代法及其变形4.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) = 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时，j (x*) 0，由|j (x*)| 0，使在S = x | |x x*| d N上Df(x)可逆，且f二次连续可微于S。又因为f(x*) = 0，所以若x(k) S，就有x(k+1) x* = x(k) x* Df (x(k)-1f(x(k) f(x*) （f (x*) = 0）= Df (x(k) -1f(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 MDf (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 .只要Cd 1，就有|x(1) x*| C|x(0) x*|2 Cd2 d 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下山法为改善对初始值的要求，在迭代公式中引入松弛因子wk：x(k+1) = x(k) wkDf (x(k)-1f(x(k)或Df(x(k)x(k) = wk f(x(k)其中wk的选取满足：|f (x(k +1)| | f(x(k)|. (4.2-10)即| f(x(k)|严格单减，且 x(k)收敛于f的零点。方法(1) 依次令进行“试探”，直到(4.2-10)满足，再进行下一次迭代，若选不到wk，则Newton下山法失败方法(2) 求的最小值点w*令x(k +1) = x(k) w*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) 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) 进行一维搜索来确定例如，取 tk = argminF(x(k) + tpk) (4.3-4) 称为最佳步长因子实际计算不易求得，通常求不精确最佳步长因子例如，使用“成功-失败”试探法先取定一步长因子l，若F(x(k) + lpk) epst = argminF(x t*g(x)x = x t*g(x)计算F(x)，g(x)= F(x)输出x，F(x)注：因为最优因子tk满足：gk+1Tgk = 0 (4.3-7)所以方向pk+1与pk总是互相垂直的，称为锯齿状下降（图4.3-1）此方向在接近极小值点时收敛速度变慢。例1 用最速下降法求解极值问题，其中F(x1，x2) = 2x12 + 2x1x2 + 5x22，取x(0) = 1，-1T出发。解：F(x)是二次函数，且见p3504.3.2 变尺度法1. 思想为了改善收敛速度，考虑在x*处的泰勒展开：因为g(x*) = 0 所以 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)作搜索方向。2. 迭代公式为了保证Bg(x)是下降方向，由(4.3-3)知，只须g(x)T(Bg(x) 0。所以当B正定时（g(x)TBg(x) 0），必