应用数值分析非线性方程求解

第七章非线性方程数值求解NumericalValueAnalysis§7.3Newton迭代法华长生制作1

§7.3Newton迭代法将f(x)在点xn作Taylor展开:

——Taylor展开线性化f(x)=0

近似于

f(xn)+f′(xn)(x-xn)=0(1)从(1)解出x,记为xn+1,则1.Newton迭代公式建立2它对应的迭代方程为显然是f(x)=0的同解方程，故其迭代函数为

在f(x)=0的根x*的某个邻域内,在x*的邻域R内，对任意初值，应用公式（2）来解方程的方法就称为牛顿迭代法。它是解代数方程和超越方程的有效方法之一.42.Newton迭代法的几何意义

与x轴(y=0)的交点x，作为下一个迭代点xn+1,即

用f(x)在xn处的切线Newton迭代法又称切线法.43、牛顿迭代法的步骤步一、准备。选定初始近似值，计算步二、迭代。按公式迭代一次，得到新的近似值，计算步三、控制。如果满足或.则终止迭代，以作为所求的根；否则转步四。此处是允许误差,15而 其中c是取绝对值或相对误差的控制常数，一般可取c=1。步四、修改。如果迭代次数达到预定指定的次数N，或者 ,则方法失败；否则以代替转步二继续迭代。16例用Newton迭代法求下面方程的一个正根,计算结果精确到7位小数.解:由Newton迭代法x1

=1.4666667,…,x4

=1.3688081x5

=1.3688081迭代5次精度达10-7x*

≈

1.36880874.Newton迭代法收敛定理（1）Newton迭代公式在单根情况下至少2阶收敛;定理7.3.1

设f(x*)=0,,且在x*的邻域上存在,连续,则可得84.Newton迭代法收敛定理证：将f(x)在xn处作2阶Taylor展开,并将解x*代入9所以，Newton法至少二阶收敛.

注意到ξn在xn及x*之间,10

Newton法在重根情形下的收敛阶20

有局部线性收敛性,重数m越高,

越接近于1,收敛越慢。20

Newton迭代法的特征

Newton迭代公式是一种特殊的不动点迭代,其迭代函数为:

Newton迭代是局部线性化方法,它在单根附近具有较高的收敛速度.

方法有效前提:135.Newton迭代法的应用----------开方公式对于给定正数应用牛顿迭代法解二次方程可导出求开方值的计算公式设是的某个近似值，则自然也是一个近似值，上式表明，它们两者的算术平均值将是更好的近似值。

定理

开方公式对于任意给定的初值均为平方收敛。

14牛顿迭代法的优缺点在单根附近,牛顿迭代法具有平方收敛的速度，所以在迭代过程中只要迭代几次就会得到很精确的解。优点缺点重根情形下为局部线性收敛;2.牛顿迭代法计算量比较大:因每次迭代除计算函数值外还要计算微商值;3.选定的初值要接近方程的解，否则有可能得不到收敛的结果;21牛顿迭代法的改进缺点克服:

局部线性收敛

------改进公式或加速2.每步都要计算微商值

-----简化Newton迭代法或弦截法3.初值近似问题-------二分法求初值或”下山算法”21方法一、若已知重数m(m>1),则利用m构造新的迭代公式:此时,至少2阶收敛.6.Newton法的改进(I)---重根情形不实用:m往往不确定.17方法二、取,再对函数F(x)用Newton迭代:此时,X*为F(x)的单根,所以是2阶收敛.缺点：要用到二阶导数.18Newton迭代法需要求每个迭代点处的导数复杂！这种格式称为简化Newton迭代法精度稍低6.Newton法的改进(II)19则Newton迭代法变为这种格式称为弦截法收敛阶约为1.61820例用简化Newton法和弦截法解下面方程的根，并和Newton迭代法比较

解:由简化Newton法由弦截法由Newton迭代法21x0=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无论哪种迭代法：Newton迭代法简化Newton法弦截法用Newton迭代法求解:x0=2x1=-3.54x2=13.95x3=-279.34x4=122017是否收敛均与初值的位置有关.例:x0=1x1=-0.5708x2=0.1169x3=-0.0011x4=7.963110-10x5=0收敛发散迭代法的局部收敛性236.Newton法的改进(III):牛顿下山法

一般地说，牛顿法的收敛性依赖于初值的选取，如果偏离较远，则牛顿法可能发散。为了防止发散，通常对迭代过程再附加一项要求，即保证函数值单调下降：

满足这项要求的算法称为下山法。牛顿下山法采用以下迭代公式：其中称为下山因子。牛顿下山法只有线性收敛.24第七章非线性方程数值求解NumericalValueAnalysis§7.4Aitken加速方案/Steffensen迭代法华长生制作25改进、加速收敛

/*acceleratingconvergence*/有些迭代过程虽收敛，但速度很慢。为了达到所要求的精度，需要迭代的次数很多，由此必须设法加速迭代过程。1.基本思想上式说明，将预测值x0和校正值x1作线性组合作为x*的一个新近似值，可能比x1更好。令：

ξ介于x0与x*之间，设变化不大，，则有微分中值定理x0----x*的预测值26一般地，有线性组合校正残差27

简单迭代公式的加速设是根的某个近似值，用迭代公式校正一次得假设，则有据此可导出如下加速公式：其一步分为两个环节：

迭代:改进:2829在方法1中含有L（或q），实际应用中不便。下面设法消除L（或q），得到一种新的加速方法---Aitken（埃特金）方法。

x0——prediction推广，有下面一般计算公式：

x1=g(x0)——updatingx2=g(x1)——further

updating30埃特金迭代法求方程的实根31定理7.4.1设序列线性收敛于x*,则的Aitken序列存在,且即比更快收敛于x*.3233Steffensen迭代