3.6 迭代法收敛阶在线视频

今天我们讲第六节

迭代法的收敛阶

前两节

我们介绍了不动点迭代法和牛顿法

在求解过程中我们发现

即便迭代法收敛

收敛的快慢程度也不一样

我们说这是因为

迭代法的收敛阶不同

本节讨论迭代法的收敛阶

我们首先给出收敛阶的定义

设迭代序列xk可以收敛于x*

并且假设xk不等于x*

如果迭代误差

ek等于xk

减x*的绝对值

满足以下极限式

e k+1比上ek的p次方

当k趋于无穷时

极限等于C

这里P大于零

则当C大于零时

称该迭代过程是P阶收敛

C称为渐进误差常数

特别

当P等于1

C小于1时

称迭代线性收敛

P等于2时

称二阶收敛也称平方收敛

如果渐进误差常数C等于零

则称迭代法超P阶收敛

我们说

收敛阶P越大

收敛速度越快

渐进误差常数C

也会影响收敛速度

但是它的意义

不如收敛阶意义大

下面看一个实例

比较线性收敛数列

与二次收敛数列

首先

假设

xk+1的绝对值

比上xk的绝对值

当k趋于无穷时

极限为0.5

对比收敛阶的定义

我们可以判定

数列xk

它线性收敛于零

我们再给出下面的极限式

xk+1bar

绝对值比上

xkbar绝对值的平方

这个比值

当k趋于无穷时

极限是0.5

那么这个极限式告诉我们

xkbar

二次收敛于零

根据以上两个极限式

可以得到

当k充分大的时候

我们有下面两个近似式成立

左侧的近似式是

xk+1绝对值比上xk的绝对值

约等于0.5

右侧

xk+1bar的绝对值比上

xkbar绝对值的平方

约等于0.5

下面我们根据这两个近似式来分析

xk

与xkbar收敛到零的快慢

根据这两个近似式

我们得到了下面的两个近似的

递推公式

先看上一行

我们导出

xk绝对值近似等于

0.5乘以xk-1的绝对值

这是根据

左侧的这个近似公式

导出来的一个递推公式

那么反复递推

最后我们得到了

xk的绝对值

近似的等于0.5的k次方

乘以x0的绝对值

再根据

上边右侧的那个近似式

得到下面这个

近似的递推式

xkbar的绝对值

约等于0.5成xk-1bar

绝对值的平方

反复递推

随后得到

0.5的2k-1次方

乘以x0bar绝对值的2的k次方

在以上两个递推公式中

我们均取初值

绝对值为1

这样我们就得到了两个公式

一个就是依据上的递推公式得到

x7约等于7.8125乘以10的负三次方

依据下面这个递推公式我们得到

x7bar约等于5.8775

乘10的-39次方

很显然xkbar二次收敛于0

它的速度远远快于xk

线性收敛于零

下面我们来分析

不动点迭代法的收敛速度

它的收敛阶

假设迭代函数φ(x)

在闭区间[a,b]上具有一阶连续导式

并且还假设迭代法xk等于

φ(xk-1)

收敛于x*

x*是φ(x)的不动点

则有

xk+1-x*等于

φ(xk)-φ(x*)

因为φ(x)可导

依据

微分中值定理等于φ’(ξ)

乘以xk-x*

这里ξ位于xk与x*之间

我们将xk-x*

除到等号的左边去

两边取绝对值

得到上述公式

两边对k取极限

由于ξ位于xk与x*之间

xk收敛于x*

并且

并且φ’(x)在x*点连续

所以当k趋于无穷时

右边的极限值

就是φ’(x*)的绝对值

由此我们得到了下面的结论

如果φ’(x*)不等于零

并且φ’(x*)的绝对值小于1

则迭代法

xk+1=φ(xk)线性收敛

如果φ’(x*)=0

则迭代法

至少超线性收敛

因此我们在构造不动点迭代法的时候

我们希望φ’(x*)

绝对值尽量小

下面我们考查

牛顿迭代法的收敛速度

首先假设f(x)具有连续的二阶导数

并且假设

x*是方程f(x)=0的一个单根

所谓单根意味着

f(x*)=0

f’(x*)≠0

我们设

xk是x*的一个近似根

将f(x)

在xk处作泰勒展开

展开到二阶项

得到下面的公式

这里ξ位于x与xk之间

在上式中

令x等于x*

那我们得到下面的公式

注意

f(x*)=0

对于这个公式

我们假设

f ’(xk) ≠0

等式两边除以f ’(xk)

得到以下公式

将划了下划线的两项

移到等号的左边去

得到以下公式

对照牛顿迭代法

我们发现等号的左侧

实际上就是

xk+1

因此我们可以把刚才的公式整理成

如下公式

首先

我们将x*移项整理之后

我们得到如下等式

将x*-xk的平方

除到等号的左边去

得到如下公式

两边取绝对值求极限

令k趋于无穷

由于ξ位于xk与x*之间

当k趋于无穷时

ξ也趋于x*

那么分母的极限是f ’(x*)

所以最后我们得到了

如下极限式子

对照收敛阶的定义

我们得知

牛顿法在求单根的时候

至少是平方收敛

也就是二阶收敛

牛顿下山法

是线性收敛

割线法

是超线性收敛

下面我们再来看一个例子

分别用不动点迭代

与牛顿法来求解方程

3x-ex+4=0

的一个正根α

与一个负根β

首先我们设方程左边函数为f(x)

寻找方程的有根区间

通过计算

我们发现f(1)大于零, f(2)小于0

这样在区间[1,2]中

有方程的一个正根

我们先来求这个正根

将原方程做不动点变形

那么得到了这样的一个不动点方程

这个方程是怎么得来的呢

不难发现

只要我们把ex移到等号的右边去

两边取对数

就得到了这样一个不动点方程

依据此方程构造迭代法

我们建立了(1)式不动点迭代法

取初值x0=2

误差限是10的-5次方

得到如下的计算结果

我们发现迭代第七次第八次的结果

五位数字完全一样

这样我们的近似正根

α约等于2.4217

我们发现f(-1)大于零,

f(-2)小于零

这样在区间[-2, -1]中

方程有负根

如果我们仍然采用

迭代格式(1)来求解

会发现

在[-2, -1]中取初值

迭代格式(1)

或者发散或收敛到正根

无法求负根

这样我们需要

更换迭代法

为了求负根我们构造迭代法(2)

xk+1=

exk-4再除以3

取初值x0=-2

误差限不变

仍然等于10的-5次方

得到如下计算结果

x5=-1.2365

x6=-1.2365

x5和x6的结果

一样

因此

我们得到了一个

负根β的近似值-1.2365

下面我们再构造牛顿迭代法

求正根取出值x0=2

得到下面的计算结果

x4=2.4217

x5=2.4217

x4和x5

结果完全一样

那么

求得了方程的一个正跟

这个比用不动点方法

迭代法(1)算出的结果

速度提高几乎一倍

求负根我们取初值

x0=-2

那么得到了下面的计算结果

x3

和x4的结果完全一样

具有相同的五位数字

我们可以看出

应用牛顿法

无论是求正根还是求负根

它的计算速度

比不动点方法都快

在上面的讨论中

我们

介绍了牛顿法求单根

可以达到二阶收敛

那么它求重根的效果如何呢

我们看下面的例子

应用牛顿法

解方程ex-x-1=0

不难验证

x*=0是这个方程的二重根

那么我们采用牛顿法求解

列出下表

这是我们的计算结果

从表中可以看出

初值取1

我们迭代到第13次

近似解

下降为10的-4次方

迭代14步

近似解下降到10的-5次方

这个下降的速度是比较慢的

因此

我们说牛顿法求重根x*=0

是线性收敛

一般的我们有:牛顿法求m重根

它是具有线性的收敛速度

本节我们讨论了迭代法的收敛阶

迭代法收敛的快慢

依赖于它的收敛阶

收敛阶越大

迭代法的收敛速度就越快

一般的不动点迭代法的收敛阶

是一阶线性收敛

牛顿法局部收敛

它求单根的收敛阶是二阶平方收敛

但是牛顿法求重根只有线性收敛

我们下一节将讨论重根的计算