Romberg求积公式、Gauss型求积公式在线视频

大家好

我是北京理工大学的满洪英老师

今天我们来学习第八章非线性方程求根

在本章 我们主要讨论这样一些方程

f(x)=0的根

其中fx是一个非线性函数

如f(x)是这样的一个五次多项式

或者f(x)=e2x+1-xln(sinx)-2这样的非线性函数

我们首先给出一个方程重根的概念

如果一个函数

f(x)在a点等于零

即f(a)=0

f在a点的一阶导数等于0

二阶导数等于0 一直到k-1阶导数等于0

但是 它在a点的k阶导数不等于0

这样的话 我们就称

x=a是方程的一个k重根

或者是函数f(x)的一个k重零点

如果a是f(x)的k重根

等价于我们可以把函数f(x)分解为

(x-a)的k次方乘以Ф(x)

其中Ф在a点的函数值不等于0

首先我们来讨论求解非线性方程的

对分区间法 即二分法

对分法的原理是

如果一个函数f(x)在闭区间上连续

它在区间的两个端点的函数值异号

即f(a)·f(b)<0

根据根的存在性定理

f在(a b)上必然有一个根

而这个区间[a b]我们称为方程f(x)=0的一个有根区间

在下文中

我们假设x*是方程f(x)=0它的一个根

二分法是怎么来进行的

首先 我们不妨假设f(a)<0 f(b)>0

我们取区间ab的中点为x0等于2分之a+b

如果f(x₀)=0

x0即为这个方程的根

即x*=x0

如果f(x0)<0

那这个时候

我们取a₁=x0 b₁=b

那这个时候

a₁ b₁就是我们一个新的有根区间

如果f(x0)>0

我们取a₁=a b₁=x0

那这个时候

a₁ b₁也是我们的一个有根区间

我们可以继续做下去

以[a₁ b₁]作为新的有根区间

我们来取它的中点

为x₁=(a₁+b₁)/2

我们通过判断x₁这个点

它的函数值是否是等于零

或者大于零 或者小于零

得到新的有根区间[a₂ b₂]

依次下去我们可以得到一个有根区间序列

即ab包含a₁ b₁

包含a₂ b₂

一直包含an bn

这个时候我们即可以取xn

等于(an+bn)/2

即an bn这个区间的中点

作为第n个近似值

我们分析一下

如果我们选择有根区间的中点作为根的近似的话

误差是什么样子的

我们首先来看第0步产生的误差

这时候x0是(a+b)/2

那因此x0-x*

即近似解和真解 它的差的绝对值是小于等于(b-a)/2

第k步产生的近似解xk

与真解x*的误差

应该是小于等于

[ak bk]这个小区间

它的长度的一半

即2的k+1次方分之b-a

有了这个误差估计之后

对于给定的一个精度ε

我们即可以由误差来估计二分法所需要的

对分的步数k

即求解这个不等式

b-a除以2的k+1次幂

小于ε就可以得到

这个需要对分的步数k

应该大于[ln(b-a)-lnε]除以ln2减掉1

这个 就是我们来求解

一个方程f(x)=0的二分法

二分法 它的优点是非常简单

而且

对函数f(x)它的要求不高

只需要是一个连续函数即可

它的缺点

是无法来求复数根

以及偶数重根的情况

第二个缺点

是这个方法它的收敛速度比较慢

因此二分法主要用于给出

其它近似迭代方法的初值

下面我们来看一个例子

我们用二分法来求方程f(x)=x³+10x-20=0

它的唯一实根

要求误差超不过0.5乘以10的-4次方

我们要用二分法 首先

要给出一个有根区间

我们这里验证f(1)是小于0 f(2)是大于0

那因此[1 2]就是它的一个有根区间

我们说这个有根区间上的根

是不是单根

我们来验证一下

如果我们来求f的导数

它是3x²+10>0

因此这个函数在区间上面 是单调增加的

方程 在区间[1 2]上有唯一的根

现在我们来估计一下对分区间的次数

根据这个估计式

n应该大于等于ln(2-1)

减掉ln0.5乘以10的-4次方

再除以ln2 减1

这个值 大约是13.288

因此这个时候我们取n=14即可

即做14次对分

就可以保证我们的这个近似解的精度达到要求

计算的流程如下

首先第一个有根区间是[1 2]

我们取它的中点是1.5

1.5的函数值是-1.6小于0

因此我们得到

下一个的有根区间是[1.5 2]

它的中点是1.75

对应的函数值2.8大于0

第二个有根区间即为[1.5 1.75]

再取它的中点1.625

对应的函数值大于0

我们可以一直这样计算下去

经过14次对分我们得到

第14个有根区间是[1.5945436 1.5946046]

这个时候我们即可以取这个有根区间的中点

1.5945741作为

我们这个方程它的根的一个近似

以上 我们就是二分法的介绍

接下来 我们来介绍求解非线性方程的简单迭代法

简单迭代法的一般形式

我们对一个方程f(x)=0

首先构造它的一个等价变换

把它变形成x=φ(x)的形式

由等价形式

我们可以构造相应的一个迭代格式

xn+1=φ(xn)

那这个时候

我们如果给定初值x0

代入迭代公式的右端

即可以计算出φ(x0)即为x1

我们可以一直这样做下去

逐次代入就可以迭代产生一个序列xn

可以以xn来作为方程f(x)=0

它的根的一个近似

而其中的这个函数φ 我们称为迭代函数

我们有这样一个结论

如果我的迭代序列{xn} 收敛于一个点x*

迭代函数φ在x*处连续

这个时候我们可以证明x*即是方程的根

即f(x*)=0

这个很容易证明

我们在迭代格式xn+1等于φ(xn)的两端同时取极限

令n趋向于无穷大

即得x*等于φ(x*) 即f(x*)=0

接下来 我们来看这样一个例子

用简单迭代法来求方程f(x)=x³+10x-20=0的根

要求精确到0.5乘以10的-6次方

我们要构造一个迭代格式

首先要对方程做一个等价变形

变形成x等于φ(x)的形式

我们来看第一种变形

我们在方程的两端同时加上x

即可以得到x=x³+11x-20

因此对应的迭代格式

即为xn+1=x³n+11xn-20

我们来取

这个有根区间[1 2]它的一个中点

即x0=1.5作为初值代入计算

可以得到x₁=-0.125

x₂=-21.376953

x₃=-10023.861

通过这几步简单的迭代我们可以看出来

由这个迭代格式产生的迭代序列是发散的

下面 我们再对这个方程来做一个等价变形

我们把刚才变形的式子

减掉17.75x再除以-16.75

它也是等于x

那所以由此即可以得到迭代格式

xn+1=xn³+11xn-20

减掉17.75xn 再除以-16.75

我们以初值x0还是取1.5

即可以计算得到

x₁ 1.5970149 x₂ x₃

x₄ x₅ x₆

我们会发现迭代六次之后啊

这个序列已经收敛了

我们会发现

我们第二种变形形式构造的迭代格式

所产生的迭代序列

就是收敛的

这时候我们即可以取x₅=1.5945621

作为这个非线性方程的根

下面我们对

这个方程再做一种等价变形

我们这里是把x³+10x提取一个公因子x

把20移到方程的右端

即可以得到x等于20除以x²+10

对应的迭代格式 是xn+1等于20除以xn²+10

还是取初值x0=1.5

代入计算

我们会发现 当我们迭代15次之后

我们得到的第14个近似值x₁₄和

第15个近似值x₁₅

它们之间的误差

小于二分之一乘以10的-6次方

那因此这个时候 我们就可以取

x₁₅=1.5945622

作为这个方程根的一个近似

对于格式三我们可以看出来

这个迭代格式 也是收敛的

我们经过15次迭代 即可以达到精度的要求

我们再来对它做一种等价变形

这个时候

我们是把10x留在左端

20和x³这两项移到右端

然后 两边再同时除以10

即可以得到x等于2减掉10分之x³

对应的迭代格式 是

xn+1等于2减xn³除以10

还是取初值x0=1.5

那这个时候 我们

进行迭代我们会发现

需要迭代48次才能达到我们的精度的要求

通过这个例子我们会发现

我们对这样的一个非线性方程可以做

各种不同的变形形式

得到不同的迭代格式

而这些迭代格式有的是收敛的

有的是发散的

同是收敛的迭代格式

而有的收敛的速度快 有的收敛的速度慢

那这样的话就说明

我们对同一个方程可以构造不同的迭代格式

产生迭代序列的收敛性也就不同

那这也就一个问题

迭代法的收敛性与什么有关

我们怎样构造具有收敛性的迭代法

我们要希望这个迭代序列收敛的话

实际上我们就是来看一下我们

迭代得到的这个xk+1

和根x*它们之间的距离

因此 我们这时候需要讨论xk+1-x*

根据迭代格式的表达

它就等于φ(xk)-φ(x*)

由此我们可以看出

迭代格式的收敛性

和这个迭代函数φ是有关系的

接下来我们就给出迭代法的收敛条件

第一个定理叫压缩映象原理

设函数φ在区间[a b]上满足

对任意的x属于[a b]

φ(x)都是大于等于a 小于等于b

第二个 是存在一个常数L大于0小于1

使得对任意的x y属于闭区间[a b]

都有φ(x)-φ(y)的绝对值小于等于L

乘上x-y的绝对值

这个条件 我们通常称为压缩条件

即像经过这个映射φ之后

像的距离

它小于等于L乘以原像的距离

由这两个条件我们即可以得出来

方程x=φ在[a b]内有唯一的根

而且对任意的初值x0属于闭区间[a b]

迭代格式

所产生的序列收敛于x*

而且 我们有下述这样的两个误差估计

我们要证明这个定理

需要证明以下几个问题

第一个结论就是 根存在是唯一的

第二个

我们这个迭代序列收敛

第三 我们要证明这样两个误差估计

我们来看一下 证明

先证根的存在性

由于φ在闭区间[a b]上连续

我们令ψ=x-φ

ψ也是连续的

ψ(a)=φ-φ(a)

它就应该小于等于0

φ(b)=b-φ(b)大于等于0

我们有连续函数的介值定理

即可以知道

ψ这个函数在闭区间[a b]上

肯定有一个0点

这个0点我们记为x*

它即是方程的根

下面我们再证明根的唯一性

假设我们这里有两个根

x*和x∽

x*就等于φ(x*)

x∽等于φ(x∽)

那这个时候x*减掉x∽的绝对值

就等于φ(x*)减掉φ(x∽)它的绝对值

我们由压缩条件即可以知道它小于等于L

乘上x*减掉x∽的绝对值

而L 小于1

那因此我们这时候就得到了一个矛盾

即x*减掉x∽的绝对值

小于x*减掉x∽的绝对值

那说明我们的假设不成立

根的唯一性 我们即得到了证明

接下来我们来证明这个迭代序列的收敛性

我们设方程x等于φ(x)在闭区间上有根x*

我们由迭代公式就可以知道

xn减掉x*的绝对值

等于φ(xn-1)减掉φ(x*)的绝对值

那它应该小于等于L

乘上xn-1减掉x*的绝对值

以此类推我们即可以得到

xn减掉x*的绝对值

小于等于L的n次方乘上x0减掉x*的绝对值

由于L是一个大于0小于1的常数

那因此啊

我们令n趋向于无穷大

即可以得到xn 当n趋向于无穷大的极限

即为x*

也即我们的迭代序列是

收敛于方程的根

接下来我们来证明这个误差估计

第一个误差估计是

近似解和真解的误差小于等于L的n次方除以1-L

乘上行x₁-x₀的绝对值

我们由前面

刚刚得到xn-x*的绝对值

小于等于L的n次方乘以x₀-x*的绝对值

这个式子不能给我们误差估计 因为x*

在实际当中我们是未知的

我们把x₀-x*利用三角不等式

小于等于x₀减掉x₁的绝对值

加上x₁-x*的绝对值

然后我们再利用

第一式子

我们即可以得到它小于等于x₁-x₀的绝对值

加上L乘上x₀-x*的绝对值

由这个不等式我们

把右端的L乘上x₀-x*的绝对值移过去

就可以得x₀-x*的绝对值小于

1-L分之1 乘上x₁-x₀的绝对值

我们把这个估计式(2)代入估计式(1)

即可以得到我们要的误差估计

即近似解和真解的误差小于等于

L的n次方除以1-L

乘上x₁-x₀的绝对值

通过这个误差估计我们可以看出来

L越小

迭代序列xn收敛于x*的速度也就越快

最后我们来证明

x*-xn的绝对值小于1-L分之1

乘上xn减掉xn-1的绝对值

由于我们前面得到了

x*-x的绝对值小于等于L乘上x*减掉xn-1的绝对值

我们把x*减掉xn-1的绝对值

利用三角不等式

小于等于x*减掉xn的绝对值

加上xn减xn-1的绝对值

我们再利用式子(3)它小于等于

L倍的x*减xn-1的绝对值

加上xn减xn-1的绝对值

然后把右端的L倍x*减xn-1的绝对值移到左端

然后再把1-L给它除过去

即可以得到x*减xn-1的绝对值

小于1-L分之1 xn减掉xn-1的绝对值

然后我们把它代入(3)式

即可以得到我们需要的估计

x*-xn的绝对值

小于L除以1-L乘上xn减xn-1的绝对值

那L是严格小于1的

因此它小于1-L分之1

xn减掉xn-1的绝对值

这个误差估计说明什么

说明近似解和真解的误差它是

可以小于1-L分之1乘以xn减xn-1的绝对值

也即我们可以用相邻两次计算结果的误差来

作为真解和近似解的误差的一个估计的标准

那所以在实际计算当中啊

只要前后两次计算的结果的误差足够小

我们即可以保证xn具有足够的精度

这里有一个问题是

定理当中的压缩条件

φ(x)- φ(y)的绝对值

小于等于L乘上x-y的绝对值

在实际当中不容易验证

那因此我们在实际当中啊

通常是把

这个条件转换成φ的导数的一个性质

这即定理8.2

定理8.2为

φ也是要求它在闭区间上满足第一个条件

和定理8.1是一样的

我们把第二个压缩条件转换成了

存在L大于0小于1

使得对任意的x属于闭区间[a b]

φ它的导数

是绝对值小于等于L

在这两个条件之下

方程存在唯一的根

而且对任意的初值x0属于[a b]迭代格式都收敛

而且有相同的这个误差估计

我们这里要证明定理8.2

只需要证明如果定理8.2的条件满足

定理8.1的条件也即成立

我们来看一下对任意的x属于闭区间[a b]

由微分中值定理可以知道φ(x)-φ((y)

等于φ'(ξ)乘以(x-y)

这个ξ 介于x y之间

两边取绝对值 我们就可以得到

φ(x)-φ((y)的绝对值

小于等于

L乘上x-y的绝对值

也就说只要定理8.2的条件满足定理8.1的条件

即成立

那由定理8.1我们即可以证明结论

但是 一般来说

构造迭代函数使其在较大区间上满足定理比较困难

所以在实际当中

我们转为讨论在根附近的情况

即定理8.3局部收敛性定理

如果我的迭代函数在根的附近邻域内

一阶连续可微

而且x*=φ(x*)

φ'(x*)的绝对值 严格小于1

那这个时候我们可以找到一个正数δ

小于等于δ*

使得对任意的x₀属于x*的δ邻域

迭代序列都收敛于x*

这个证明也比较简单

我们由

极限的保号性

可以证明由φ'(x*)的绝对值小于1可以得到

存在一个δ大于0

使得只要x在x*的δ领域上

φ'(x)的绝对值小于等于L小于1

另外φ(x)-x*的绝对值

它等于φ(x)-φ(x*)的绝对值

那这个时候

我们利用第一个性质

我们即可以得到

它小于等于L乘上x-x*的绝对值

那应该是小于δ的

那所以这样的话我们也证明了

φ(x)属于x*-δ

到x*+δ

由此我们就可以得出来

定理8.3在x*的一个小的δ邻域上

满足定理8.2的条件一和条件二

那由定理8.2我们可以知道迭代序列

是收敛于x*的

下面我们利用这些定理来看一下

我们前面所构造迭代格式的收敛性

对于第一种方法

我们的迭代函数是x³+11x-20

那它的导数 是3x²+11

它在整个区间上 都是大于11的

它不满足定理8.2

但是定理8.2是个充分条件不满足

也不一定不收敛

那我们在后面会讨论

实际上只要在真解x*这一点

它迭代函数的一阶导数

严格大于1

这时候得到的迭代序列一定是发散的

对于我们的算法三

我们的迭代函数是20除以x²+10

那这个时候

迭代函数在[1 2]上它的值域是

大于1 小于2的

而且它的导数φ’

它是-40x除以x²+10²

那它的绝对值在[1 2]这个区间上是

小于等于80除以11²

这个值大约是0.6611

严格小于1

那因此我们可以看出来这个迭代函数在区间[1 2]上

满足定理8.2因此迭代收敛

对于方法四我们的迭代函数是

2减掉10分之x³

它的导数 是10分之3倍的x²

这个迭代函数在[1 2]上不满足定理8.2的条件

但是如果我们把这个区间给它压缩一下

在[1.5 1.7]这个区间上

我们可以验证它的迭代函数的导数

是小于等于0.867 严格小于1

而且迭代函数在这个区间上也是大于1.5小于1.7

这个迭代函数

它在区间[1.5 1.7]上满足定理8.2

因此迭代格式收敛

但是由于这里的这个L压缩因子

它是0.867

我们的方法三要大

那因此 它的收敛的速度要比方法三要慢