3.7 重根的计算与加速收敛在线视频

今天我们讲第七节

重根的计算与加速收敛

上节我们讲过应用牛顿法求重根

只能达到线性收敛

那么采用什么方法求重根

能加速收敛

本节

我们介绍两种方法

首先我们定义

u(x)=f(x)/f'(x)

假设

方程f(x)=0有m重根

它的根为x*

我们可以证明

无论x*

是方程f(x)=0的重根或单根

它总是方程u(x)=0的单根

根据假设

x*

是f(x)的

m重零点

我们可以把f(x)分解为

f(x)等于

(x-x*)m乘以g(x)

这里g(x)满足

x趋于x*时

它的极限不等于0

将f(x)的上述表达式求导

我们得到f'(x)的表达式

将f(x)与f'(x)

带入u(x)表达式

得到下述式子

消去

x-x*的m-1次方

得到下式

这里我们将

g(x)比上

mg(x)+(x-x*)g'(x)

记为h(x)

由于u(x)可以表示成

x-x*乘以h(x)

我们可以看到

x*

它一定是方程u(x)等于0的根

下面我们要证明

x*是方程u(x)=0的单根

要证明这个结论

只要证明

h(x)

当x趋于x*时极限不为0

我们来求

h(x)当x趋于x*时的极限

根据h(x)的定义

我们得到

当x趋于x*时

h(x)的极限等于m分之一

不等于零

因此

x*

是u(x)的

单零点

这样我们就可以

把求原方程f(x)=0的

重根x*的问题转化为

求方程u(x)=0的单根x*

我们给出

求重根的第一种方法

设u(x)=f(x)/f'(x)

应用牛顿法

求u(x)=0的根

得到如下迭代函数

那么

根据下述迭代函数

我们构造迭代法

xk+1=φ(xk)

可以证明

当迭代函数φ(x)具有

二阶连续导数的时候

迭代格式（1）至少二阶收敛于x*

下面我们介绍第二种求重根的方法

定义迭代函数

h(x)等于

x减去m乘以

f(x)/f'(x)

基于这个函数

构造迭代格式xk+1

等于h(xk)

注意在h(x)表达式中

系数m

它是根x*的重数

可以证明

当f(x)具有

三阶连续导数的时候

xk至少二阶收敛于x*

以上我们介绍了两种求重根的方法

一种是迭代法（1）

一种是迭代法（2）

迭代法（1）

它迭代函数φ(x)的表达式

比较复杂

那么它的优点是

不需要知道重根的重数

而且公式（1）

它既适用于求重根

也适用于求方程的单根

迭代法（2）

公式比较简单类似于牛顿法

但是

需要知道根的重数

当知道根的重数的时候，适用于

用公式（2）来求重根

我们下面举例来说明

以上两个公式的应用

求解方程

ex-x-1=0

采用刚才介绍的两个求重根的公式

公式（1）和公式（2）

来计算，初值x0取1。

计算结果如下表

第二列

是采用公式（2）计算

公式（2）是已知根的重数是2

我们采用公式二来求重根

大家看到

第三步迭代x3

它已经下降到

10的-6次方

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

第4步第5步

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

那么可以看出

这个xn当n趋于无穷的时候，它是

比较快速的收敛到0

再看最后一列

依据公式（1）来求解方程

那么xn的下降速度也是比较快的

迭代到第三步

x3下降到10的-5次方

第4步第5步x4，x5

下降到到10的-11次方

均达到了二阶收敛

我们也发现

x4，x5

都下降到了10的负11次方

x5呢

与x4相同

这是因为

由于是求重根当k较大的时候

分母接近于零

所以说误差比较大

因此求重根的方法

不适于迭代步数太多

下面我们介绍第二个内容加速收敛

当迭代法

线性收敛速度比较慢的时候

我们可以采用加速技巧

来提高它的收敛速度

我们介绍的第一种方法

是埃特金加速

首先介绍差分的概念

给定一个数列Pn

n从0到无穷

令ΔPn=Pn+1-Pn

这里n是非负整数

ΔPn称为Pn点的一阶向前差分

接下来我们来定义Pn点的

高阶向前差分

ΔkPn等于

Pn点的

k-1阶向前差分的

一阶向前差分

我们把ΔkPn

称为Pn点的k阶向前差分

下面我们举个例子

求Pn点的二阶向前差分

根据定义

它等于Pn点的

一阶向前差分的一阶向前差分

现在计算

ΔPn等于

Pn+1减Pn

用一阶向前差分的算子来作用

得到了

ΔPn+1减去ΔPn

按照一阶向前差分的定义

带入计算

我们得到了最后的结果

Pn+2减去2倍的Pn+1

再加Pn

可以看出Pn点的二阶向前差分

它实际上也是

数列Pn不同项的一个线性组合

下面我们来介绍

埃特金加速技巧

设数列Pn

线性收敛于极限P

并且当n充分大时

我们假设

Pn-p

Pn+1-P

Pn+2-P符号一致

这意味着我们要求

Pn收敛于P是单侧收敛

从一个方向趋于P

并且还假设

下述近似式成立

Pn+1-P比上Pn-p

近似等于Pn+2-P

比上Pn+1-P

将这个近似式交叉相乘

得到下面的公式

由这个近似式

解出P的表达式

求解这个近似表达式

我们得到P的下述式子

将P的这个近似公式

用差分的符号来表述

可以表述为

P约等于Pn减去ΔPn的平方比上Δ²Pn

注意后面这个分数的分子

是Pn点的一阶

向前差分的平方

分母是Pn点的二阶向前差分

我们把这个式子的计算结果

记为Pnbar

以上我们推导了

埃特金加速公式

我们把公式右边

记为

{Δ2}Pn

{Δ2}

称为艾特金加速算子

这样Pnbar可以表示为

将Pn应用

埃特金加入算子进行加速

计算结果

按照右式来算

我们有下述的结果

Pnbar

比数列Pn

更快的收敛于极限P

那么

如何来体现这种更快呢

给出下面的极限式子

Pnbar-P比上Pn-P

当n趋于无穷时

极限为零

这个式子告诉我们

在n趋于无穷的过程中

分子Pnbar-P

是比分母Pn-P

更高阶的无穷小

下面我们来看

埃特金加速度的计算顺序

首先我们构造数列Pn

根据迭代法

计算P0,P1,P2,P3

每进行三步迭代

就可以执行一次

埃特金加速

依据P0,P1,P2

我们可以对P0点进行埃特金加速

加速的结果记为P0bar

再根据P1,P2,P3

对P1点进行埃特金加速

得到结果P1bar

这样产生了埃特金加速数列

下面我们介绍第二种加速技巧

斯蒂芬森加速

设数列Pn

线性收敛于P

数列Pn是由迭代法

Pn+1=g(Pn)产生的数列

P是迭代函数g(x)的不动点

我们将初值P0

记为P0(0)上标是0

斯蒂芬森加速采用的加速算子

跟前面一样仍然是埃特金加速算子

我们来看斯蒂芬森加速数列的构造

首先取初值P0(0)

采用迭代函数g(x)

迭代两步

得到P1(0)

P2(0)

将这三点

带入埃特金加速公式进行加速

也就是说

我们对P0(0)

进行埃特金加速

得到的结果

记为P0(1)上标是1

注意这时和埃特金加速有所不同了

我们不是对P2(0)再进行迭代

而对P0(1)

进行迭代,迭代两步

得到P1(1)和P2(1)

对第二列的这三点进行埃特金加速

也就是说

我们对P0(1)进行埃特金加速

计算结果记为P0(2)上标是2

这样产生了

斯蒂芬森数列P0(i)

一般的我们有P0(i)

迭代两步得到了P1(i)，P2(i)

对P0(i)进行埃特金加速

得到了P0(i+1)

那么由这个构造过程可以看出

斯蒂芬的加速与埃特金加速的区别

就在于埃特金加速

它是对原始数列的项进行加速

而斯蒂芬森它是对新的加速点

进行迭代, 迭代两步之后

在新的加速点进行加速

那么斯蒂芬斯数列它的收敛效果

如何呢

我们给出下面的定理

设不动点方程x=g(x)有解P

并且假设g'(p)不等于1

如果存在正数δ

使得g(x)在[P-δ,P+δ]中

具有连续的三阶导数

那么斯蒂芬斯加速数列

满足对于P0

属于[P-δ,P+δ]

一定二次收敛于P

这个定理我们不做证明

这个定理告诉我们

当g'(P)不等于1时

不论原迭代法是否收敛

斯蒂芬森加速均收敛

并且至少是二阶收敛

如果g'(P)=1

则斯蒂芬斯数列收敛速度有所下降

我们下面看这道例题

分别用不动点方法

与牛顿法求解方程

ex-x-1=0

这里初值P0=1

这个方程

我们前面算过

下面我们

首先用不动点方法与牛顿法来求解

然后再用斯蒂芬斯方法来加速

首先给出牛顿法迭代函数g1(x)

构造牛顿迭代法

Pn+1=g1(Pn)

可以证明

牛顿法求方程的重根是线性收敛

再构第二个迭代函数

g2(x)=ex-1

对应的迭代法是

Pn+1=g2(Pn)

大家看到,用这个迭代法

计算到第5步

P5

迭代点已经上升到10的41次方

距0很远

所以这个迭代法是发散的

那么下面对这两种迭代法一个是线性收敛

一个是发散来进行

斯蒂芬森加速.我们看看加速的效果

这是史蒂芬森数列

我们把计算结果列在下面这张表中

大家看到了对g1(x)

进行加速

注意g1(x)是

牛顿法

那么加速的效果列在表中第二列

我们算到第三步P3

迭代点已经下降到10的-7次方

P4下降到10的-10次方

P5下降到10的-11次方

这个下降的速度是很快的

所以说斯蒂芬斯加速

加速牛顿法它是二阶收敛

再来看

Steffensen加速

g2(x)不动点方法

那么迭代到第17次

第18次这个迭代点

也是向零靠近,下降到10的-5次方

这告诉我们两种方法

用斯蒂芬森加速均收敛

一个是二阶收敛

一个是线性收敛

为什么是线性收敛呢?

我们说

因为g2(x)的导数

在零点的值是1

所以它的迭代速度有所下降

那么斯蒂芬森方法

是不是加速任何数列

都能够有很好的效果呢

我们说如果

迭代法的收敛阶在二阶以上

那么用斯蒂芬森加速是失效的

本节介绍了重根的计算

与加速收敛

我们介绍了两种重根的计算方法

介绍两种加速方法

一种是斯蒂芬森加速

一种是埃特金加速

斯蒂芬森加速

对于改进一阶收敛或发散的方法

有很大效果

当原迭代收敛些大于1时

斯蒂芬森方法对其改善不大