数值分析迭代加速、牛顿法及弦截法

1、数值分析迭代加速、牛顿法及弦截法3.3 迭代收敛的加速方法迭代收敛的加速方法3.3.1 埃特金加速收敛方法 对于收敛的迭代过程，只要迭代足够多次，就可以使结果达到任意的精度，但是有时迭代过程收敛较慢，从而使计算量变得很大. 设 x0 是根 x*的某个近似值, 用迭代公式校正一次得 x1=(x0)而由微分中值定理，有假设 (x) 改变不大, 近似地取某个近似值 L, 则有由于 x2-x*L(x1-x*). 若将校正值 x1=(x0) 再校正一次，又得 x2=(x1)将它与(3.1)式联立，消去未知的L，有由此推知在计算了 x1 及 x2 之后，可用上式右端作为 x* 的新近似,记作 x1，一般情

2、形是由xk计算 xk+1, xk+2，记它表明序列xk的收敛速度比xk的收敛速度快.(3.1)式称为埃特金(Aitken) 2加速方法. 可以证明也称为埃特金 ( Aitken ) 外推法. 可以证明:为线性收敛,则埃特金法为平方收敛； 注：埃特金(Aitken)加速迭代法也可写成下面格式若)(1kkxx 为 p ( p 1)阶收敛，导数连续，则埃特金法为 2p1 阶收敛.的 p 阶若3.3.2 3.3.2 斯蒂芬森斯蒂芬森(Steffensen)(Steffensen)迭代法迭代法 埃特金方法不管原序列xk是怎样产生的，对xk进行加速计算，得到序列 xk . 如果把埃特金加速技巧与不定点迭代

3、结合，则可得到如下的迭代法：称为斯蒂芬森(Steffensen)迭代法. 实际上(3.3)是将不定点迭代法(2.2)计算两步合并成一步得到的，可将它写成另一种不动点迭代其中 对不动点迭代(3.5)有以下局部收敛性定理. 若x*为(3.5)定义的迭代函数(x)的不动点，则x*为(x)的不定点. 反之，若x*为(x)的不动点，设(x)在 x* 连续 ，(x*)1，则x*是(x)的不动点，且斯蒂芬森迭代法(3.3)是2阶收敛的. 3.4 牛牛 顿顿 法法3.4.1 牛顿法及其收敛性 牛顿法实质上是一种线性化方法，其基本思想是将非线性方程 f(x)=0 逐步归结为某种线性方程来求解. 设已知方程f(x

4、)=0有近似根x0，且在 x0附近f(x)可用一阶泰勒多项式近似，表示为当 f(x0)0 时，方程 f(x)=0 可用线性方程(切线) 近似代替，即 f(x0)+f(x0)(x-x0)=0. (4.1)解此线性方程得得迭代公式此式称为牛顿(Newton)迭代公式.牛顿法的几何意义：设xk是根x*的某个近似值，过曲线y=f(x)上横坐标为xk的点Pk引切线，并将该切线与x轴交点的横坐标xk+1作为x*的新的近似值. 注意到切线方程为这样求得的值xk+1必满足(4.1), 从而就是牛顿公式(4.2)的计算结果. xyx*xky=f(x)xk+1PkPk+1xk+2牛顿迭代法的收敛性设x*是 f(x

5、) 的一个单根，即 f(x*)=0，f(x*)0, 有牛顿迭代法的迭代函数为由定理4可得由此得到，当x*为单根时，牛顿迭代法在根x*的邻近是二阶(平方)收敛的.设fC2a, b, 若x*为 f(x)在a, b上的根，且 f(x*)0，则存在 x* 的邻域 U, 使得任取初值 x0U，牛顿法产生的序列 xk 收敛到 x*，且满足 解 将原方程化为 xex= 0，则牛顿迭代公式为取 x0=0.5，迭代得x1=0.566311, x2=0.5671431, x3=0.5671433. f(x)=xex， f(x)=1+ex， 例1 用牛顿迭代法求方程x=ex在x=0.5附近的根.例2 对于给定的正数

6、 C，应用牛顿法解二次方程我们现在证明，这种迭代公式对于任意初值x00都是收敛的.推导出求开方值 的计算公式.C事实上，对(4.5)式进行配方整理，易知以上两式相除得据此反复递推有记整理(4.6)式，得对任意初值x00，总有|q|0)重根时，则 f(x) 可表为 f(x)=(x-x*)mg(x).其中 g(x*)0，此时用牛顿迭代法(4.2)求 x* 仍然收敛，只是 收敛速度将大大减慢. 事实上，因为迭代公式令ek=xkx*，则可见用牛顿法求方程的重根时仅为线性收敛.从而有两种的方法：1) 取如下迭代函数得到迭代公式下面介绍一个求重数m的方法，令则求m重根具有2阶收敛. 但要知道x*的重数m.

7、由式得因此得估计m的式子为对f(x)=(x-x*)mg(x), g(x*)0，令函数则为求(x)=0的单根x*的问题，对它用牛顿法是二阶(平方)收敛的. 其迭代函数为2) 将求重根问题化为求单根问题.从而构造出迭代方法为 例3 用牛顿迭代法求函数 f(x)=(x-1)sin(x-1)+3x-x3+1=0 在0.95附近之根. 解 取x0 = 0.95 用牛顿迭代法求得的xk见右表. 可见xk收敛很慢.kxkkm01234560.950.97442790.98705830.99348780.99673280.99835760.99919010.50900.50470.50070.51252.03

8、692.01902.00282.0511由重根数m=2, 用(4.13)式加速法，作求得 x0=0.95, x1=0.9988559, x2=x3=1.收敛速度大大加快于直接用牛顿迭代公式.3.5 弦截法与抛物线法弦截法与抛物线法用牛顿法求方程 f(x)=0的根，每步除计算 f(xk)外还要算 f(xk)，当函数 f(x) 比较复杂时，计算 f(x)往往比较困难，为此可以利用已求函数值 f(xk),f(xk-1),来回避导数值 f(xk)的计算. 这类方法是建立在插值原理基础上的，下面介绍弦截法与抛物线法.3.5.1 3.5.1 弦截弦截( (割线割线) )法法设 xk, xk-1是 f(x)

9、=0的近似根，我们利用 f(xk), f(xk-1)构造一次插值多项式 p1(x)，并用 p1(x)=0 的根作为方程f(x)=0 的新的近似根 xk+1，由于因此有这样导出的迭代公式(5.2)可以看做牛顿公式11)()( kkkkxxxfxf中的导数 用差商 取代的结果.)(kxf (5.2)式有明显的几何意义： 设曲线y=f(x)上横坐标为xk-1和xk的点分别为Pk-1和Pk, 则差商 表示弦 的斜率, 弦 的方程为11)()( kkkkxxxfxfkkPP1 kkPP1 Ox*xk+1xkPkxk-1yxPk-1因此，按(5.2)式求得xk+1实际上是两点弦线 与x轴交点的横坐标(令y

10、=0解出x即可).这种算法因此而形象地称为弦截(割线)法.kkPP1 注：弦截法与切线法(牛顿法)都是线性化分法，但两者有本质的区别. 切线法在计算 xk+1 时只用到前一步的值 xk，而弦截法要用到前面两步的结果 xk-1, xk，因此使用这种方法必须先给出两个开始值 x0, x1.定理6 假设f(x)在根x*的邻域内: |x-x*|具有二阶连续导数，且对任意x有f(x)0，所取的初值x0, x1，那么当邻域充分小时，弦截法(5.2)将按阶收敛到x*. 这里p是方程2-1=0的正根.定理证明可见P116.因为(5.2)式用到前两点xk-1和xk的值，故此方法又称为双点割线法.每步只用一个新点

11、xk的值，此方法称为单点割线法.如果把(5.2)式中的xk-1改为x0，即迭代公式为例4 用牛顿迭代法和割线法求方程 f(x)=x4+2x2x3=0， 在区间(1, 1.5)内之根(误差为10-9). 解 取x0=1.5，用牛顿法, 可得x6；取x0=1.5, x1=1，用双点割线法，迭代6次得到同样的结果，而采用单点割线法，则迭代18次得x18=1.124123029.* *3.5.2 3.5.2 抛物线法抛物线法设已知方程 f(x)=0的三个近似根 xk, xk-1, xk-2，我们以这三点为节点构造二次插值多项式 p2(x)，并适当选取 p2(x) 的一个零点 xk+1 作为新的近似根，

12、这样确定的迭代过程称为抛物线法，亦称为密勒(Mller)法. 在几何图形上, 这种方法的基本思想是用抛物线y=p2(x)与 x 轴的交点 xk+1 作为所求根 x* 的近似位置.Ox*xk+1xky=P2(x)xk-2yxy=f(x)xk-1抛物线法的几何意义见下面图形.现在推导抛物线法的计算公式. 插值多项式有两个零点式中因子在(5.3)式定出一个值xk+1，我们需要讨论根式前正负号的取舍问题.在xk, xk-1, xk-2三个近似值中，自然假定xk更接近所求的根x*，这时，为了保证精度，我们选(5.3)式中接近xk的一个值作为新的近似根xk+1. 为此，只要取根式前的符号与的符号相同. 例5