3.4 不动点迭代法的收敛条件在线视频

今天我们学习第四节

不动点迭代法的收敛条件

不动点迭代法满足什么条件收敛呢

我们给出下面的定理3.3

假定函数(x)

属于C[ a, b]

(x)是[a , b]上的连续函数

并且满足下列条件

对于任意的x属于[a, b]

有(x)也在[a, b]之中

(x)大于等于a

小于等于b

我们称这个条件为映内性条件

第二,(x) 在(a, b)内可导

并存在正数

L小于1

使对任意X属于[a, b]

都有(x)绝对值小于等于L

我们称这个条件为压缩性条件

如果满足以上两个条件则迭代过程

xk+1=(xk)

对任意的初值x0属于[a , b]

均收敛于方程X=(x)的根x*

且有如下误差估计式

xk-x*的绝对值

小于等于L/1-L

乘以xk-xk-1的绝对值

我们把这个不等式@

xk-x*的绝对值

小于等于Lk /1-L

乘以x1-x0的绝对值

我们把这个不等式记为(4)

我们看到

定理3.3中的两个条件和定理3.2

中的两个条件完全一样

因此如果(x)满足定理3.3

中的条件,

那么(x)

在[a, b]中就一定存在唯一不动点.

下面我们来证明

由迭代过程xk+1=(xk)产生的数列

收敛于(x)唯一不动点.

并且来验证不等式3和不等式4成立

首先证明收敛性

由于(x)在[a, b]上

满足映内性与压缩性条件

根据定理3.2

(x)在[a,b]中存在唯一不动点

我们设这个不动点为x*

满足x*=(x*)

并且由(x)在[a, b]上满足映内性

所以在[a, b]中

任取X0,由迭代格式

xk+1=(xk)产生的数列

一定也属于[a, b].

下面

我们将xk+1与x*相减

Xk+1等于

φ(xk)

X*是不动点

等于(x*)

因此

xk+1-x*就等于(xk)- (x*)

由(x)

在[a b]上可导

所以根据微分中值定理

就等于’(ξ)

乘xk-x*

这里ξ属于开区间ab

将上式两边取绝对值

你就得到了下式.再根据压缩性条件

我们有

’(ξ)的绝对值

小于L

这里L大于零小于1

那么就得到了

下面的不等式

xk+1-x*

的绝对值小于等于L乘

乘xk-x*的绝对值

对k反复递推

就得到

xk-x*的绝对值

小于等于L的k次方

乘以x0-x*的绝对值

两边取极限

令k趋于无穷

那么由于L大于零小于1

所以Lk趋于零

从而就有xk趋于x*

这样就证明了不动点序列的收敛性

下面我们来证明不等式3成立

考察

xk+1-xk

xk+1-xk=(xk)- ( xk-1)

根据微分中值定理等于’(ξk)

乘以xk-xk-1

两边取绝对值

上式成立

这里ξk属于开区间(a, b)

同样

由压缩性条件

’(ξk)的绝对值

小于等于L

所以我们得到了

上面的不等式a

也就是xk+1-xk

的绝对值

小于等于L乘以xk-xk-1的绝对值

我们把这个不等式记为a式

类似的

我们还可以推出

x*-xk+1的绝对值

等于x*-(xk)的绝对值

小于等于L乘以x*-xk

的绝对值

我们把这个不等式记为b式

另一方面

xk+1-xk我们在其中插项

xk+1-xk

绝对值就等于

xk+1-x*+x*-xk的绝对值

整理一下等于

x*-xk再减去括号

x*-xk+1括号的绝对值

根据绝对值不等式，大于等于

x*-xk的绝对值

再减去

x*-xk+1的绝对值

根据不等式b

大于等于

（1-L）

乘以x*-xk的绝对值

由于0

我们将1-L除到不等号的左边去

那么就得到了xk-x*的绝对值

小于等于1/1-L

乘以xk+1-xk的绝对值

我们把这个不等式记为c式

综合a, c两式就得到了不等式3.

下面我们来证明不等式4成立

由前面导出的不等式a式

我们有xk+1-xk的绝对值

小于等于L乘

以xk-xk-1的绝对值

将这个不等式反复递推k-1次

就得到

xk+1-xk的绝对值

小于等于Lk乘

x1-x0的绝对值

我们把这个不等式记为d式

再利用我们刚刚导出的不等式3

将d式带入3式

就得到了下面的不等式4

这样我们就完成了

定理3.3的证明

定理3.3中的两个不等式

具有重要意义

我们先来看不等式3的重要性

不等式3

它将

相邻近似误差

与近似解与精确解的误差

联系起来了

那么

只要相邻近似解充分接近

就能够保证

近似解与精确解充分接近

在迭代中

我们通常

取终止准则为

xk-xk-1的绝对值

小于ε

或者

xk-xk-1的绝对值

除以1+xk的

绝对值

小于ε

用这个作为终止准则

来

停止迭代

再来看不等式4的重要性

不等式4告诉我们

数列xk

收敛于x*快慢

与压缩系数L的大小有关

那么L是大于零小于1的一个正数

这不等式告诉我们

L越小

也就是越靠近零

那么

Lk趋于零的速度越快

从而xk

收敛于x*速度也越快

L越大越靠近1

那么xk

收敛于x*速度越慢

这里L是迭代函数(x)的导数

的绝对值

在区间[a,b]上的一个上限。

下面我们考察这个例子

求方程

f(x)=x3-x-1=0

在x0=1.5附近的根

我们前边做过这道题

给出了两种迭代法

迭代法1和迭代法2

取初值x0=1.5

那么迭代法1产生的序列是收敛的

迭代法2产生的序列是发散的

下面我们分析下原因

迭代法1

对应的迭代函数

记为1(x)等于x+1开立方

迭代法2对应的迭代函数

记为2(x)

等于x3-1

我们对1(x)求导

那么就得到了1’(x)等于

3乘以x+1的

三分之二次方分之一

在区间[1,2]

1’(x)的绝对值

小于等于

3乘2的三分之二次方分之一

这个分数是小于1的

也就说

它满足定理3.3中的压缩性条件

所以迭代法1是收敛的

在看2(x)的导数

2’(x)=3x2

在[1, 2]中

它的最大值

大于等于3

由于不满足

压缩性条件

所以迭代法2产生的迭代法数列发散

定理3.3中说的收敛是

全局收敛

所谓全局收敛

指的是

在某个确定范围内任取初值

迭代法都收敛。

一般满足全局收敛

是很困难的，

下面我们来介绍局部收敛的概念。

如果存在x*的某个邻域U

x-x*的绝对值小于等于δ

使得迭代过程xk+1=(xk)

对于任意的初值x0属于U

均收敛于x*

那么我们就称迭代过程xk+1=(xk)

在根 x*

的邻域内具

有局部收敛性

定义3.3是我们给出的

迭代法在

根 x*附近具有局部收敛性的一个定义

那么满足什么条件

迭代法才能局部收敛呢

我们给出下面的定理

设 x*为方程x = (x)的根，

也就是x*是(x)的不动点

若(x)

在x*

附近连续且(x*)的绝对值

小于1

则迭代过程

xk+1=(xk)

在x*附近具有局部收敛性

那么定理3.4告诉我们

迭代函数的导数

在根处的绝对值要小于1

这是迭代法

具有局部收敛性的一个充分条件

下面我们看

这样的一个例子

证明迭代公式

xk+1等于

xk(x²k+3a)/3x²k+a

产生的数列收敛于根号a

我们按照定理3.4来验证

设xk+1=(xk)

这里(x)等于

3x2+a分之

x乘以x2+3a

容易验证

(根号a)等于根号a

也就是根号a是(x)的不动点

下面我们对(x)求导

将根号a带入’(x)

得到其值等于零

那么由定理3.4

我们说

数列xk+1=(xk)

它收敛于根号a

本节讨论了

不动点迭代法的收敛条件

求解方程的不动点迭代法是不唯一的

有的收敛有的发散

因此我们在构造迭代法时

要注意

使迭代函数满足局部收敛的条件

下一节

我们将介绍牛顿迭代法

牛顿迭代法是求解非线性方程的近似根的最有效的方法之一