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

数值计算方法,第四章 计算函数零点和极值点的迭代法,本章讨论非线性方程（组）的求解问题,1不动点 设非线性方程组 f(x) = 0 (4.1-1),4.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)的不动点。,4.1 不动点迭代法及其收敛性,x(k+1) = (x(k)，k = 0, 1, 2, 注： (1) 求零点求不动点 (2) (.)称为迭代函数，x(k)称为迭代序列 (3) 不同方法构造迭代函数，得不同的迭代序列,4.1 不动点迭代法及其收敛性,2迭代法的基本问题 (1) 如何构造适当的迭代函数(.)使迭代序列x(k)收敛 (2) 收敛的速度和误差 (3) 如何加速,4.1 不动点迭代法及其收敛性,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内有且仅有一根。,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法 2. 迭代序列的收敛性 因为可以有多种迭代函数，所产生的迭代序列x(k)有可能： (1) 收敛快 (2) 收敛慢 (3) 不收敛,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法 例1 f(x) = x3 x 1 = 0，求f在x = 1.5附近的根，初值取x(0) = 1.5。(p328) 取 收敛 k=1, x0=1.5 x1=(1+x0)(1/3) while abs(x1-x0)0.00001 k=k+1, x0=x1; x1=(1+x0)(1/3) end,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法 例1 f(x) = x3 x 1 = 0，求f在x = 1.5附近的根，初值取x(0) = 1.5。(p328) 取(x) = x3 1 不收敛 k=1, x0=1.5 x1=x03-1 while abs(x1-x0)0.00001 x1=x03-1 end,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法 定理4.1-1 (1)设(x)Ca，b, 且对于任意x a, b 有 (x) a，b，则在a，b上必有不动点。 (2) 进一步，若(x)C1a，b，且存在L1，使对于任意的x a，b有 | (x)| L 1 (4.1-4) 则对于任意的x(0) a，b，x(k+1) = (x(k)收敛于唯一不动点x* a，b。,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法 定理4.1-1 (2) 进一步，若(x)C1a，b，且存在L1，使对于任意的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 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法 定理4.1-1 (1)设(x)Ca，b, 且对于任意x a, b 有 (x) a，b，则在a，b上必有不动点。 证明：(1) 若(a) = a或(b) = b，则结论显然成立 现设a 0，(b) = (b) b 0， 故存在x* a，b，使(x*) = 0，即 (x*) x* = 0 (x*) = x*,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法 证明: (2)设(x)C1a，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,4.1.1 解一元方程的迭代法 证明: (2)设(x)C1a，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,4.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 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法 (4.1-5) 注：(1) 若L 1，则收敛很慢，须考虑加速问题 (2) (4.1-5)中第一式为后验公式迭代停止准则; 第二式为先验公式预测迭代次数 (3) 定理是以a，b中任一点作初值，迭代都收敛，称为全局收敛。,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法 (4.1-5) 注：(3) 定理是以a，b中任一点作初值，迭代都收敛，称为全局收敛。 （此要求较难满足，故考虑在） x*的某一邻域内局部收敛性,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法 定理4.1-2 设x*为的不动点, 在x*的某邻域内连续, 且|(x*)| 0, 只要x(0)x*，x*+，就有迭代法 x(k+1) = (x(k)收敛。 证明: |(x*)| 0，使x* ，x*+ U(x*)， 且 x x* ，x* + 有| (x)| q 1,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法 定理4.1-2 设x*为的不动点, 在x*的某邻域内连续, 且|(x*)| 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 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法 定理4.1-2 设x*为的不动点, 在x*的某邻域内连续, 且|(x*)| 0, 只要x(0)x*，x*+，就有迭代法 x(k+1) = (x(k)收敛。 证明: 存在 0，使 x x* ，x* + ， |(x) x*| ，即(x) x*，x*+， 由定理4.1-1知， 任意x(0)x*，x*+，迭代法x(k+1)=(x(k)收敛。,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法 定理4.1-2 设x*为的不动点, 在x*的某邻域内连续, 且|(x*)| 0, 只要x(0)x*，x*+，就有迭代法 x(k+1) = (x(k)收敛。 注：只要x(0)充分接近x*，且|(x(0)| 明显小于1，则x(k)收敛于x*。,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法 例2 求方程x = ex在0.5附近的根。 由于| (0.5)| = e0.5 0.61明显小于1，故收敛 解：Matlab代码如下 k=1, x0=0.5 x1=exp(-x0) while abs(x1-x0)0.00001 x1=exp(-x0) end,4.1 不动点迭代法及其收敛性,4.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 1，称超线性收敛 (3) p = 2，称平方收敛,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法 3. 收敛阶 因为 |x(k+1)x*| = |(x(k)(x*)| = |()|x(k)x*|， 其中在x(k)和x*之间。则 所以若(x*) 0，则为线性收敛 想得到更高阶的收敛性，须(x*) = 0，通常可考虑泰勒展式。,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法 3. 收敛阶 定理4.1-3 设x*为的不动点，正整数p 2，若(p)在x*的某邻域内连续，且满足 (4.1.6) 则x(k)p阶局部收敛。 证明： (x*) = 0(1)，x(k)局部收敛。,4.1 不动点迭代法及其收敛性,定理4.1-3 设x*为的不动点，正整数p 2，若(p)在x*的某邻域内连续，且满足 (4.1.6) 则x(k)p阶局部收敛。 证明： (x*) = 0(1)，x(k)局部收敛。 设(x)在x*处展开为,4.1 不动点迭代法及其收敛性,定理4.1-3 设x*为的不动点，正整数p 2，若(p)在x*的某邻域内连续，且满足 (4.1.6) 则x(k)p阶局部收敛。 证明：设(x)在x*处展开为 由(4.1-6)知，,4.1 不动点迭代法及其收敛性,定理4.1-3 设x*为的不动点，正整数p 2，若(p)在x*的某邻域内连续，且满足 (4.1.6) 则x(k)p阶局部收敛。 证明：由(4.1-6)知 所以 即x(k)p阶局部收敛。,4.1 不动点迭代法及其收敛性,例3 设f C2a，b， x*为f的单重零点， (x) = x r1(x)f(x) r2(x)f 2(x)。 试确定未知函数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,4.1 不动点迭代法及其收敛性,例3 设f C2a，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,4.1 不动点迭代法及其收敛性,例3 设f C2a，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 不动点迭代法及其收敛性,例3 设f C2a，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 不动点迭代法及其收敛性,例3 设f C2a，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 不动点迭代法及其收敛性,例3 设f C2a，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 不动点迭代法及其收敛性,例3 设f C2a，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 不动点迭代法及其收敛性,例3 设f C2a，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 不动点迭代法及其收敛性,4.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 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法 4. 加速 1在x(k)和x*之间 2在x(k+1)和x*之间 因为x(k) x*，所以当k充分大时， (1) (2),4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法 4. 加速 1在x(k)和x*之间 2在x(k+1)和x*之间 因为x(k) x*，所以当k充分大时， (1) (2) 即 (4.1-7),4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法 4. 加速 即 (4.1-7),4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法 4. 加速 即 (4.1-7) 记 则 比x(k)收敛得快。,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法 4. 加速 定理4.1-4 设x(k)线性收敛于x*，且k0， 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)+kek,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法 4. 加速 定理4.1-4 设x(k)线性收敛于x*，且k0， ek=x(k) x* 0, 0 | | 1 (线性收敛) 则 证明： x(k+1) x(k) =( 1)+kek,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法 4. 加速 定理4.1-4 设x(k)线性收敛于x*，且k0， ek=x(k) x* 0, 0 | | 1 (线性收敛) 则 证明： x(k+1) x(k) =( 1)+kek 又 x(k+2) 2x(k+1) + x(k) = (x(k+2) x(k+1) (x(k+1) x(k) = ( 1) +k+1ek+1 ( 1) +kek = ( 1) +k+1( +k)ek (1) +kek,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法 4. 加速 定理4.1-4 设x(k)线性收敛于x*，且k0， ek=x(k) x* 0, 0 | | 1 (线性收敛) 则 证明： x(k+1) x(k) =( 1)+kek 又 x(k+2) 2x(k+1) + x(k) = ( 1) +k+1( +k)ek (1) +kek,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法 4. 加速 定理4.1-4 设x(k)线性收敛于x*，且k0， ek=x(k) x* 0, 0 | | 1 (线性收敛) 则 证明： x(k+1) x(k) =( 1)+kek 又 x(k+2) 2x(k+1) + x(k) = ( 1) +k+1( +k)ek (1) +kek = ( 1)2 + kek,4.1 不动点迭代法及其收敛性,k =k+1+(2)k+k+1k0,4.1.1 解一元方程的迭代法 4. 加速 定理4.1-4 设x(k)线性收敛于x*，且k0， ek=x(k) x* 0, 0 | | 1 (线性收敛) 则 证明：又因为,4.1 不动点迭代法及其收敛性,x(k+1) x(k) =( 1)+kek x(k+2) 2x(k+1) + x(k) = ( 1)2 + kek,4.1.1 解一元方程的迭代法 4. 加速 定理4.1-4 设x(k)线性收敛于x*，且k0， ek=x(k) x* 0, 0 | | 1 (线性收敛) 则 证明：又因为 所以,4.1 不动点迭代法及其收敛性,x(k+1) x(k) =( 1)+kek x(k+2) 2x(k+1) + x(k) = ( 1)2 + kek,4.1.1 解一元方程的迭代法 4. 加速 定理4.1-4 设x(k)线性收敛于x*，且k0， ek=x(k) x* 0, 0 | | 1 (线性收敛) 则 证明：所以 ,4.1 不动点迭代法及其收敛性,x(k+1) x(k) =( 1)+kek x(k+2) 2x(k+1) + x(k) = ( 1)2 + kek,4.1.1 解一元方程的迭代法 4. 加速 定理4.1-4 设x(k)线性收敛于x*，且k0， ek=x(k) x* 0, 0 | | 1 (线性收敛) 则 注：(1) (4.1-7) 称为Aitken加速,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法 4. 加速 定理4.1-4 设x(k)线性收敛于x*，且k0， ek=x(k) x* 0, 0 | | 1 (线性收敛) 则 注：(2) k = 1，2， 称为史蒂文生迭代法。,4.1 不动点迭代法及其收敛性,4.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 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法 4. 加速 例4 用迭代法和Steffensen迭代法求函数 f(x) = x lnx 2在区间(2, +)内的零点，取x(0) = 3 解：Steffensen迭代法的计算公式为： 取初值x(0) = 3作迭代，结果见p336,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法 4. 加速 例4 用迭代法和Steffensen迭代法求函数 f(x) = x lnx 2在区间(2, +)内的零点，取x(0) = 3 解：迭代法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,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法 4. 加速 解：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 不动点迭代法及其收敛性,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) 其收敛性有下述压缩映射（不动点）原理,4.1 不动点迭代法及其收敛性,4.1.2 解非线性方程组的迭代法 定理4.1-5 设在闭区域 上满足条件 存在q, 0q1, 使x, y ,有|(x) (y)|q|xy| 且x (x) 。则 (1) 存在唯一不动点x* ，且 x(0) ，迭代向量列收敛于x*。 (2) 证明与定理2.4-3及定理4.1-1相似,4.1 不动点迭代法及其收敛性,4.1.2 解非线性方程组的迭代法 定理4.1-5 设在闭区域 上满足条件 存在q, 0q1, 使x, y ,有|(x) (y)|q|xy| 且x (x) 。则 (1) 存在唯一不动点x* ，且 x(0) ，迭代向量列收敛于x*。 (2) 注：(1) 保证序列,4.1 不动点迭代法及其收敛性,4.1.2 解非线性方程组的迭代法 注：(2) 若i(x)在 上可微， (x) = (1(x)，2(x)，n(x)T 记 则压缩条件|(x)(y)|q|xy|可用下式替代 其中D(x)是(x)在点x处的Jacobi矩阵,4.1 不动点迭代法及其收敛性,4.1.2 解非线性方程组的迭代法 例5 用不动点迭代法求非线性方程 在闭域 内的根。 解：(1) 取x(0) = (1，-1.5)T，按迭代公式： k = 0，1，2， 产生的序列收敛（见p339）,4.1 不动点迭代法及其收敛性,4.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) while abs(x1-x0)0.0001 k=k+1, x0=x1; x1=log(1-x0(2),-sqrt(4-x0(1)2) end,4.1 不动点迭代法及其收敛性,4.1.2 解非线性方程组的迭代法 例5 用不动点迭代法求非线性方程 在闭域 内的根。 解： (2) 按迭代公式： k = 0，1，2， 产生的序列未必收敛（见p340）,4.1 不动点迭代法及其收敛性,4.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 x1=sqrt(4-x0(2)2),1-exp(x0(1) end,4.1 不动点迭代法及其收敛性,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,4.2 Newton迭代法及其变形,4.2.1 一元非线性方程 1. 牛顿迭代方法 即考虑方程 f (x(k) + f (x(k)(x x(k) = 0,4.2 Newton迭代法及其变形,4.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迭代法及其变形,4.2.1 一元非线性方程 2. 收敛性 (1) 若x*是f(x)的单重根： f (x*) = 0，f (x*) 0 因为 而 一般不为0，所以，Newton法是局部二阶收敛的 由定理4.1-3,4.2 Newton迭代法及其变形,4.2.1 一元非线性方程 2. 收敛性 例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。,4.2 Newton迭代法及其变形,4.2.1 一元非线性方程 2. 收敛性 例1 用Newton法求非线性方程f(x) = xex 1 = 0在(0，1)内的根，取x(0) = 0.5。 解：因为f (x) = (1 + x)ex，故其Newton迭代公式为 k = 0，1，2， k=0,x0=0.5 x1=x0-(x0*exp(x0)-1)/(1+x0)*exp(x0) while abs(x1-x0)0.00001 x1=x0-(x0*exp(x0)-1)/(1+x0)*exp(x0) end,4.2 Newton迭代法及其变形,4.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迭代法及其变形,4.2.1 一元非线性方程 2. 收敛性 (2) 若x*是f(x)的重根，即有 f(x) = (x x*)mg(x)，其中g(x*) 0，m 2,4.2 Newton迭代法及其变形,4.2.1 一元非线性方程 2. 收敛性 (2) 若x*是f(x)的重根，即有 f(x) = (x x*)mg(x)，其中g(x*) 0，m 2,4.2 Newton迭代法及其变形,4.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迭代法及其变形,4.2.1 一元非线性方程 2. 收敛性 (3) (2)的改进中若取 易知有(x*) =0所以，若事先知道x*的重数，则可改迭代公式为 (4.2-6) 此时，迭代序列x(k)是二阶收敛的。,4.2 Newton迭代法及其变形,4.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,4.2.1 一元非线性方程 例2 是方程x4 4x2 + 4 = 0的二重根 (1) 采用Newton法 即 注：迭代15次,4.2 Newton迭代法及其变形,4.2.1 一元非线性方程 例2 是方程x4 4x2 + 4 = 0的二重根 (2) 采用(4.2-6) k=0,x0=1.5 x1=x0-(x02-2)/(2*x0) while abs(x1-x0)0.00001 x1=x0-(x02-2)/(2*x0) end 迭代5次,4.2 Newton迭代法及其变形,4.2.1 一元非线性方程 例2 是方程x4 4x2 + 4 = 0的二重根 (3) 采用(4.2-7) 即 迭代5次,4.2 Newton迭代法及其变形,4.2.2 多元非线性方程组 f (x) = 0 (4.1-1),4.2 Newton迭代法及其变形,4.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迭代法及其变形,4.2.2 多元非线性方程组 1. Newton迭代公式 用线性函数近似表示，即有 (i = 1，2，n) 其矩阵形式： f (x(k) + Df (x(k)( x x(k) = 0 (4.2-1),4.2 Newton迭代法及其变形,4.2.2 多元非线性方程组 1. Newton迭代公式 (i = 1，2，n) 其矩阵形式： f (x(k) + Df (x(k)( x x(k) = 0 (4.2-1),4.2 Newton迭代法及其变形,4.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迭代法及其变形,4.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迭代法及其变形,4.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迭代法及其变形,4.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迭代法及其变形,4.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迭代法及其变形,4.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)Sx(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),4.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)-1f(x(k) f(x*) = Df (x(k) -1f(x*) f(x(k) + Df (x(k)(x(k) x*),4.2 Newton迭代法及其变形,|x(k+1) x*| C|x(k) x*|2,4.2.2 多元非线性方程组 2. 收敛性 证明： 若x(k) S，就有 x(k+1)x* = Df (x(k) -1f(x*) f(x(k) + Df (x(k)(x(k) x*),4.2 Newton迭代法及其变形,|x(k+1) x*| C|x(k) x*|2,4.2.2 多元非线性方程组 2. 收敛性 证明： 若x(k) S，就有 x(k+1)x*=Df (x(k) -1f(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*)2,4.2 Newton迭代法及其变形,|x(k+1) x*| C|x(k) x*|2,4.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,4.2 Newton迭代法及其变形,|x(k+1) x*| C|x(k) x*|2,4.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 1M 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,4.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 max|D2f(x* t(x(k) x*)|：0 t 1M |Df(x(k)-1|D,4.2 Newton迭代法及其变形,|x(k+1) x*| C|x(k) x*|2,4.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 max|D2f(x* t(x(k) x*)|：0 t 1M |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,4.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,4.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 C2 x(1) S 再由归纳法可证：x(k) S （k） 由 知，Newton法是局部二阶收敛的。,4.2 Newton迭代法及其变形,4.2.2 多元非线性方程组 例3 用Newton法求非线性方程组 在点(1.5，1)附近的根。 解： 由迭代公式 有,4.2 Newton迭代法及其变形,4.2.2 多元非线性方程组 例3 用Newton法求非线性方程组 在点(1.5，1)附近的根。 解：由迭代公式 有 从x(0) = (1.5，1)T出发，计算结果见p345表4.2-3。,4.2 Newton迭代法及其变形,4.2.2 多元非线性方程组 例3 用Newton法求非线性方程组 在点(1.5，1)附近的根。 解：由迭代公式 有 从x(0) = (1.5，1)T出发，计算结果见p345表4.2-3。,4.2 Newton迭代法及其变形,4.2.2 多元非线性方程组 例3 用Newton法求非线性方程组 在点(1.5，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)*f x1=x0+dx while norm(x1-x0)0.00001 dx=-inv(df)*f x1=x0+dx en