简单迭代法的加速、牛顿法与弦截法在线视频

大家好 今天我们来介绍

简单迭代法的加速

即Steffensen方法

首先我们给出

一个数列收敛速度的概念

如果数列xn

当n趋向于∞的时候

极限是x*

如果我们能够存在一个正数r和a

使得xn+1 减掉x*的绝对值

除以xn减掉x*的绝对值的r次方

当n趋向于∞的时候 极限是a

这时候我们就称

这个数列xn是r阶收敛于x*

或者xn这个数列

它的收敛阶是r

特别的 当r=1的时候

我们称为线性收敛

r>1的时候 称为超线性收敛

r=2 我们称为平方收敛

接下来 我们给出一个迭代格式

它的收敛速度的定理

即定理8.4

我们假设迭代函数φ(x)

在x*附近有r阶导数 r≥2

而且 x*等于φ(x*)

即x*是方程的根

φ在x*的一阶导数 二阶导

一直到r-1阶导都等于零

φ在x*的r阶导

是不等于零的

那这个时候 我们可以得出

这个迭代格式xn+1等于φ(xn)

所产生的迭代序列xn

是r阶收敛于x*的

下面

我们来看一下这个定理的证明

由于φ'(x*)等于0

我们由定理8.3

即可以知道存在一个δ大于0

当我的初值在这x*的邻域的时候

迭代格式所产生的迭代序列是收敛于x*

而且 xn也在x*的一个δ邻域上

下面 我们来看一下

这个迭代序列它的收敛阶

讨论xn+1-x*

除以(xn-x*)它的r次方

当n趋向于∞时候的极限

根据定义

xn+1应该等于φ(xn)

x* 等于φ(x*)

所以xn+1-x*

除以(xn-x*)的r次方

就等于φ(xn)-φ(x*)

除以(xn-x*)的r次方

下面我们把φ(xn)在x*点作Taylor展开

即φ(xn)等于φ(x*)

加上φ'(x*)乘以xn-x*

加一直加

展到这个r-1阶

它的余项是

φ的r阶导数在ξ的值

除以r的阶乘

乘以(xn-x*)的r次方

根据条件

我们这里的φ在x*的一阶导

二阶导 一直到r-1阶导都等于零

因此φ(xn)就等于φ(x*)

加上φ的r阶导数在ξ点的值

除以r的阶乘乘以(xn-x*)的r次方

由这个式子

我们即可以得到

xn+1-x*除以(xn-x*)的r次方

它就应该等于

φ(r)阶导数在ξ的值除以r的阶乘

我们这个时候

令n趋向于∞

那由于ξ

是介于xn和x*之间

而当n趋向于∞的时候

xn收敛于x*

因此 夹迫着ξ就收敛于x*

那因此 这个时候它的极限

就是φ的r阶导数

在x*的值除以r的阶乘

它是不等于零的

根据一个数列收敛阶的定义

即可以知道我们这里的迭代序列(xn)

它是r阶收敛于x*的

如果迭代函数φ

在x*的一阶导的绝对值是

大于0 小于1的

那这个时候的迭代法

是线性收敛的

根据这个迭代法的

收敛阶的这个定理

看一下这样一个例题

我们来证明

当x0充分接近于根号下a时

这个迭代格式xn+1等于

xn乘上xn²+3a除以

3xn²+a所产生的迭代序列

收敛于根号下a

而且它的收敛阶是3

对于这个迭代格式

它所对应的迭代函数φ

应该等于x乘以x²+3a

除以3x²+a

如果x*

是方程的根

即x*等于φ(x*)

我们可以求解方程

得到x*等于0

或者x*等于正负根号下a

现在我们来对迭代函数φ求它的导数

它的φ的一阶导

应该是等于(x²-a)²

除以(3x²+a)²

这个一阶导在根号a

我们把x等于根号a

代入φ'表达式就可以得到

φ'(根号a)等于0

由定理8.3我们可以知道

只要在根这一点

它的一阶导的绝对值

严格小于1都是收敛的

这里一阶导是等于零

所以当初值充分接近于根号a的时候

我们的迭代格式一定是收敛的

而且收敛到根号a

下面我们再来看φ它的二阶导

φ的二阶导

求出来是16ax乘以(x²-a)

除以(3x²+a)³

把x=根号a代入

φ''在根号下a的值

也是等于0

现在我们再来求它的三阶导

然后算出φ的三阶导在根号下a

它的值 是1/2a

这时候不等于0

由此我们可以看出

对于这个迭代格式来说

它的迭代函数φ

在根号a这一点

它的一阶导等于0

二阶导等于0

但是它的三阶导不等于0

我们由定理8.4即可以得出来

这个迭代格式所产生的序列

它的收敛阶是三阶收敛的

下面 我们给出简单迭代法的加速

即Steffensen方法

在第四章的时候

我们给出过

如果一个数列是线性收敛的

我们可以对这个数列做一个加速

即Aitken加速

即我们用这个数列

它的相邻的三项xn xn+1和xn+2

重新做这样一个线性组合

即xn-(xn+1-xn)²

除以xn+2-2xn+1+xn

我们把组合之后的这个数

记为(Xn) 拔

这个(Xn) 拔

我们称为序列{xn}的

一个Aitken系列

这个序列(Xn) ̅

它的收敛速度

要比xn收敛的速度要快

利用这种加速方法

我们把Aitken加速技巧

用于线性收敛的迭代序列

即可以得到Steffensen方法

它的计算过程

是这样子的

我们已知xn做一次迭代

得到yn等于φ(xn)

然后把yn代入迭代格式

计算一次

得到zn等于φ(yn)

我们把

这里的xn yn和zn

做一个Aitken加速

即xn-(yn-xn)²除以

zn-2yn+xn

我们把这个值

作为我们迭代一次得到的值

记xn+1

我们可以证明

当φ'(x*)不等于0的时候

即简单迭代法是一个线性收敛的时候

我们做了这种加速之后的

Steffensen的方法

至少是二次局部收敛的

这个

就是简单迭代法的加速

接下来我们来介绍

求解非线性方程的牛顿法和弦截法

首先 我们来看牛顿法

牛顿法 它的迭代思想

和前面的简单迭代法不一样

我们这里的一个基本思想是将

非线性方程线性化

以线性方程的解来逼近非线性方程的解

比方说

我们对于这条曲线y等于f(x)

非线性方程的解

即是这条曲线与x轴的交点

我们在求解的时候

给了初值x0

我们来做

曲线在x0 f(x0)处

它的切线即

y-f(x0)=f'(x0)(x-x0)

这条切线与x轴的交点

我们可以计算出来

即令y=0计算出

x等于x0-f(x0)除以f'(x0)

这个时候

我们可以以切线与x轴的交点

作为曲线与x轴交点的一个近似

如果这个结果不够好的话

我们再来做

过x1 f(x1)这一点的切线

那这条切线与x轴的交点

我们记为x2

x2就应该等于

x1-f(x1)除以f'(x1)

我们可以一直这样做下去

即可以得到牛顿迭代公式

即xn+1等于

xn-f(xn)除以f'(xn)

我们按照这样的一个迭代公式

来求方程f(x)等于0的近似解的方法

即称为牛顿法

由此我们可以看出

牛顿法它的几何意义

实际就是以曲线

在一点xn f(xn)的切线

与x轴的交点来作为

曲线与x轴交点的一个近似

故牛顿法

我们又称为是切线法

下面我们来看一下

我们用牛顿法来求解方程

x³+10x-20=0的根

我们的初值还是取1.5

根据牛顿法的迭代公式

xn+1等于

xn-fx(n)除以f'(xn)

那这里的f(x)

是x³+10x-20

它的导数 是3x²+10

我们代到这个公式里边

即可以得

对于这个方程

牛顿法迭代公式为 xn+1等于

xn减掉xn³+10x-20

除以3xn²+10

把初值x0等于1.5代入

即可以得x1=1.5970149

把x1代入右端

可以得到x2 x3 x4

我们会发现

经过三次迭代

这个序列就已经收敛了

所以我们可以看出来

牛顿法 它的收敛速度是非常快的

下面我们来看一下

牛顿法它的收敛性

我们假设这个函数f(x)

它在其零点x*附近是二阶可微的

而且 f'(x*)不等于0

即x*

是这个方程的一个单根

那这个时候

我们可以存在一个δ>0

只要我的初值在x*的

这个小的δ邻域的时候

牛顿法所产生的迭代序列

至少是二阶收敛于x*的

我们来看一下它的证明

对于牛顿法来说

它的迭代函数φ就应该等于

x 减掉f(x)除以f'(x)

而这个根

我们记为 x*=φ(x*)

我们来看一下迭代函数的

一阶导φ'(x*）

求导之后

是f(x*)乘以f''(x*)

除以[f'(x*)]²

那从这个表达式

我们可以看出来

我们为什么要求f'(x*)不等于0

由于x*是根

所以f(x*) 等于0

那因此 f(x*)

应该等于0

那也就是说

对于牛顿迭代法来说

它的迭代函数

在x*的一阶导等于0

根据定理8.4

我们可以知道

牛顿法至少是二阶收敛的

对于牛顿法

我们做一下说明

当求的根是一个单根的时候

牛顿法它的收敛速度快 精度高 稳定性好

但是它对初值要求比较苛刻

由于每次迭代

需要计算函数值 导数值各一次

因此计算量大

所以它只适用于

求解那种导数易求的情况

如果当这个根是重根

是r重根 r是大于1的

那这个时候牛顿法是线性收敛的

而且我们可以证明

当n趋向于∞的时候

xn+1-x*的绝对值

除以xn-x*的绝对值

它的极限是r-1/r

那因此我们这里可以看出来

r越大

这个迭代序列

它的收敛速度越慢

对于这种重根的问题

我们如何来求解

这个就是改进的牛顿法

对于重根的问题

我们在求解的时候

可以对牛顿法做以下改进

第一种改进方法是

引入一个新的函数μ

等于f(x)除以f'(x)

如果x*是f(x)=0

这个方程的一个重根

我们可以证明

x*就是μ(x)等于0

它的一个单根

那这个时候

我们可以对μ用牛顿法

即可以得到其迭代公式

xn+1等于

xn减掉μ(xn)除以μ'(xn)

那这时候它所对应的

迭代格式的收敛阶至少是2

第二种改进的方法

是我们构造这样一个迭代格式

xn+1等于

xn-r倍f(xn)除以f'(xn)

那其中这个r

就是这个根的重数

它是大于 等于2的

可以证明

以上两种改进方法

都是至少二阶收敛的

最后我们来给大家

简单介绍一下弦截法

所谓弦截法

实际上是对牛顿法的一种改进

在牛顿公式当中

如果我们把这个导数f'(xn)

用它的差商来代替

即f'(xn)近似的等于

f(xn)-f(xn-1)除以

xn-xn-1

我们即可以得到这样一个迭代公式

xn+1等于xn减掉

f(xn)除以f(xn)-f(xn-1)

再乘以(xn-xn-1)

我们按照这个公式

来求方程f(x)等于0近似解的方法

就称为弦截法

我们来看一下弦截法

它的几何意义

它的几何意义实际上是用曲线上

过两点(xn-1,f(xn-1))

(xn,f(xn))的直线

与x轴的交点

作为曲线与x轴交点的近似

那因此这个弦截法又称为割线法

或者是线性插值法

我们知道过这两点

(x0,f(x0)) (x1,f(x1))的割线方程

或者它的线性差值函数为

y-f(x1)等于f(x1)-f(x0)

除以x1-x0

再乘以(x-x1)

它与x轴的交点

我们记为x2等于x1-f(x1)

除以f(x1)-f(x0)

再乘以(x1-x0)

那这时候

我们可以用x2

作为我的这个根的一个近似

如果精度不够

我们可以过(x1,fx1)

(x2,fx2)

重新做一条弦

然后来求出它与x轴的交点为x3

依次下去

我们就可以得到割线法

它对应的迭代公式

对于弦截法

我们做一个说明

弦截法通常需要两个初值

x0，x1才能运行

在实际当中

我们通常取有根区间的两个端点作为初值

对于弦截法的收敛性

我们有这样一个结论

即定理8.6

设f(x)在x*附近二阶连续可微

而且 f(x*)等于0

f'(x*)不等于0

即x*是方程的一个单根

那这个时候我们可以证明

存在一个δ大于0

当x0 x1在x*的一个δ邻域的时候

由弦截法所产生的序列

它是收敛于x*

而且它的收敛阶

至少是1.618

那对于这个定理的证明

有兴趣的同学可以参考相应的文献

好 我们关于第八章的内容

就介绍这么多

谢谢大家