数值分析：7.3-7.4非线性方程求解.ppt

第七章第七章 非线性方程数值求解非线性方程数值求解§ 7.3 Newton迭代法 §7.3　　Newton 迭代法迭代法将将f(x)f(x)在点在点xn作作TaylorTaylor展开展开: : ——Taylor——Taylor展开线性化展开线性化f(x)=0 近似于近似于 f(xn)+ f′(xn)(x-xn)=0 (1)从从(1)解出解出x, 记为记为xn+1 , ,则则1. Newton1. Newton迭代公式建立迭代公式建立迭代公式建立迭代公式建立2它对应的迭代方程为 显然是f(x)=0的同解方程，故其迭代函数为 在 f(x)=0的根 x* 的某个邻域 内, 在 x* 的邻域R 内，对任意初值 ，应用应用公式（2）来来解方程的方法就称为解方程的方法就称为牛顿迭代法牛顿迭代法它是解代数方程和它是解代数方程和超越方程的有效方法之一超越方程的有效方法之一.42. Newton2. Newton迭代法的几何意义迭代法的几何意义迭代法的几何意义迭代法的几何意义 与与x轴轴(y=0)的交点的交点x x，，作为下一个迭代点作为下一个迭代点xn+1 , ,即即 用用f(x)f(x)在在 xn 处处的切线的切线Newton迭代法又称切线法迭代法又称切线法.43 3、牛顿迭代法的步骤、牛顿迭代法的步骤步一步一、准备。

选定初始近似值 ，计算步二步二、迭代按公式 迭代一次，得到新的近似值 ，计算步三步三、控制如果 满足 或 .则终止迭代，以 作为所求的根；否则转步四此处 是允许误差, 15而 其中c是取绝对值或相对误差的控制常数，一般可取c=1步四步四、修改如果迭代次数达到预定指定的次数N，或者 ,则方法失败；否则以 代替 转步二继续迭代164. Newton4. Newton迭代法收敛定理迭代法收敛定理迭代法收敛定理迭代法收敛定理（（1））Newton迭代公式在单根情况下至少迭代公式在单根情况下至少2阶收敛阶收敛;定理定理定理定理7.3.17.3.1 设设 f(x*)=0, , 且在且在 x* 的邻域的邻域 上上 存在存在, 连续连续, 则可得则可得84. Newton4. Newton迭代法收敛定理迭代法收敛定理迭代法收敛定理迭代法收敛定理证：证：证：证：将将f(x)在在 xn 处作处作2阶阶Taylor展开展开,并将解并将解x*代入代入9 所以，所以，NewtonNewton法至少二阶收敛法至少二阶收敛. . 注意到注意到ξ ξn n 在在xn 及及x*之间之间,10 NewtonNewtonNewtonNewton法在重根情形下的收敛阶法在重根情形下的收敛阶法在重根情形下的收敛阶法在重根情形下的收敛阶20 有局部线性收敛性有局部线性收敛性, , 重数重数m越高越高, , 越接近于越接近于1,收敛越慢。

收敛越慢20 NewtonNewton迭代法的特征迭代法的特征迭代法的特征迭代法的特征 • Newton迭代公式是一种特殊的不动点迭代迭代公式是一种特殊的不动点迭代,其其迭代函数为迭代函数为:• Newton迭代是局部线性化方法迭代是局部线性化方法,它在单根附它在单根附近具有较高的收敛速度近具有较高的收敛速度.• 方法有效前提方法有效前提:135. Newton5. Newton迭代法的应用迭代法的应用迭代法的应用迭代法的应用--------------------开方公式开方公式 对于给定正数 应用牛顿迭代法解二次方程可导出求开方值 的计算公式 设 是 的某个近似值，则 自然也是一个近似值，上式表明，它们两者的算术平均值将是更好的近似值 定理定理 开方公式对于任意给定的初值开方公式对于任意给定的初值 均为均为平方收敛平方收敛 14牛顿迭代法的优缺点牛顿迭代法的优缺点在单根附近, 牛顿迭代法具有平方收敛的速度，所以在迭代过程中只要迭代几次就会得到很精确的解。

优点优点缺点缺点1.重根情形下为局部线性收敛;2. 牛顿迭代法计算量比较大: 因每次迭代除计算函数值外还要计算微商值;3. 选定的初值要接近方程的解，否则有可能得 不到收敛的结果;21牛顿迭代法的改进牛顿迭代法的改进缺点克服缺点克服: 1.局部线性收敛2. ------改进公式或加速改进公式或加速2.2.每步都要计算微商值每步都要计算微商值 ----------简化简化NewtonNewton迭代法或弦截法迭代法或弦截法3. 3. 初值近似问题初值近似问题 --------------二分法求初值或二分法求初值或”下山算法下山算法”21方法一、方法一、 若已知重数m(m>1), 则利用m构造新的 迭代公式: 此时 , 至少2阶收敛. 6. Newton6. Newton6. Newton6. Newton法的改进法的改进法的改进法的改进(I)---(I)---(I)---(I)---重根情形重根情形重根情形重根情形不实用不实用: m: m往往不确定往往不确定. .17方法二、方法二、 取 , 再对函数F(x)用Newton迭代:此时, X*为F(x)的单根, 所以是2阶收敛. 缺点：要用到二阶导数缺点：要用到二阶导数. .18NewtonNewton迭代法迭代法需要求每个迭代点处的导数需要求每个迭代点处的导数 复杂！复杂！这种格式称为这种格式称为 简化简化NewtonNewton迭代法迭代法精度稍低精度稍低6. Newton6. Newton6. Newton6. Newton法的改进法的改进法的改进法的改进(II)(II)(II)(II)19则则NewtonNewton迭代法变为迭代法变为这种格式称为这种格式称为弦截法弦截法收敛阶约为收敛阶约为1.6181.61820 例例例例 用简化用简化Newton法和弦截法解下面方程的根，并和法和弦截法解下面方程的根，并和Newton 迭代法比较迭代法比较 解解解解: :由简化由简化Newton法法由弦截法由弦截法由由Newton迭代法迭代法21x0= 0.5x1= 0.3333333333x2 = 0.3497942387x3 = 0.3468683325x4 = 0.3473702799x5 = 0.3472836048x6 = 0.3472985550x7 = 0.3472959759x8 = 0.3472964208x9 = 0.3472963440x10 = 0.3472963572x11 = 0.3472963553x0=0.5;x1=0.4;x2 = 0.3430962343x3 = 0.3473897274x4 = 0.3472965093x5 = 0.3472963553x6 = 0.3472963553简化简化Newton法法由弦截法由弦截法要达到精度要达到精度10-8 简化简化Newton法迭代法迭代11次次弦截法迭代弦截法迭代5次次Newton迭代法迭代迭代法迭代4次次x0 =0.5;x1 =0.3333333333x2 =0.3472222222x3 =0.3472963532x4 =0.3472963553由由Newton迭代法迭代法22无论哪种迭代法：无论哪种迭代法：NewtonNewton迭代法迭代法简化简化NewtonNewton法法弦截法弦截法用用NewtonNewton迭代法求解迭代法求解: :x0 = 2x1 = -3.54x2 = 13.95x3 = -279.34x4 = 122017是否收敛均与初值的位置有关是否收敛均与初值的位置有关. .例例例例: : : :x0 =1x1 = -0.5708x2 = 0.1169x3 = -0.0011x4 = 7.963110-10x5 = 0收敛收敛发散发散•迭代法的迭代法的迭代法的迭代法的局部收敛性局部收敛性局部收敛性局部收敛性236. Newton6. Newton法的改进法的改进法的改进法的改进(III) : (III) : 牛顿下山牛顿下山法法 一般地说，牛顿法的收敛性依赖于初值一般地说，牛顿法的收敛性依赖于初值 的选取，如的选取，如果果 偏离偏离 较远，则牛顿法可能发散。

较远，则牛顿法可能发散 为了防止发散，通常对迭代过程再附加一项要求，即保为了防止发散，通常对迭代过程再附加一项要求，即保证函数值单调下降：证函数值单调下降： 满足这项要求的算法称为下山法满足这项要求的算法称为下山法 牛顿下山法采用以下迭代公式：牛顿下山法采用以下迭代公式：其中其中 称为下山因子称为下山因子 牛顿下山法只有线性收敛牛顿下山法只有线性收敛.24第七章第七章 非线性方程数值求解非线性方程数值求解§ 7.4 Aitken加速方案/Steffensen迭代法改进、加速收敛改进、加速收敛 /* accelerating convergence */有些迭代过程虽收敛，但速度很慢为了达到所要求的精度，有些迭代过程虽收敛，但速度很慢为了达到所要求的精度，需要迭代的次数很多，由此必须设法加速迭代过程需要迭代的次数很多，由此必须设法加速迭代过程Ø1.1.基本思想基本思想 上式说明，将预测值上式说明，将预测值x0和校正值和校正值 x1 作作线性组合线性组合作为作为x*的一个新的一个新近似值，可能比近似值，可能比x1更好。

令：更好令： ξ介于介于x0与与x*之间，设之间，设 变化不大，变化不大， ，则有，则有微分中值定理微分中值定理x0 ---- x*的的预测值预测值26一般地，有一般地，有线性组合校正残差27 简单迭代公式的加速简单迭代公式的加速 设 是根 的某个近似值，用迭代公式校正一次得假设 ， 则有据此可导出如下加速公式：其一步分为两个环节： 迭代: 改进:2829 在方法在方法1中含有中含有L（或（或q）），实际应用中不便下面设，实际应用中不便下面设法消除法消除L （或（或q）），，得到一种新的得到一种新的加速方法加速方法------Aitken（（埃特金）方法埃特金）方法 x0 ——prediction 推广，有下面一般计算公式推广，有下面一般计算公式：： x1=g(x0) ——updatingx2=g(x1) ——further updating30埃特金迭代法求方程的实根31定理定理7.4.1 设序列 线性收敛于x*, 则 的Aitken序列 存在,且 即 比 更快收敛于x*.3233SteffensenSteffensen迭代迭代在Aitken加速法中,只要有三个相邻的点就可以进行加速,即对任意线性收敛序列 构建的. 现将其与不 动点迭代 方法结合起来: 迭代函数 迭代初始值 迭代序列34或写成不动点迭代形式35See you next time!《《应用数值分析应用数值分析》》：：例题例题 7.3.2；；习题习题 7.10、、7.15、、7.16、、7.1836。