基于Thiele-连分式逼近的改进迭代算法及收敛性分析

郭 巧，杨 兵，葛小竹，颜玉柱

(安徽职业技术学院，安徽 合肥 230601)

0 引言

一般地，高阶非线性方程求根时，参考最多的是迭代函数算法，其迭代效果也各不一样[1-3].Newton迭代法，由于其较为简单的迭代格式、较为快速的迭代收敛速度，一直被作为经典迭代法运用于非线性方程求根运算.但是Newton迭代法收敛阶数较低，本文以此为突破口，结合Thiele-连分式逼近、泰勒幂级数展开、Viscovatov算法等相关知识，通过两次迭代，推导出第一项、第二项和第三项截断多项式逼近的迭代算法.通过分析其收敛性，构造出一类基于Thiele-连分式逼近的高阶收敛的迭代算法.其中，由Thiele-连分式第一项截断后推导出的迭代算法(Newton迭代公式)为二阶收敛，第二项截断后推导出的迭代算法为三阶收敛，第三项截断后推导出的迭代算法为四阶收敛.在给定背景下证明此改进迭代算法的收敛阶数、效率指数和收敛速度更优于Newton迭代，最后给出了数值实例.

1 预备知识

定义1.1[4]给定多项式

(1.1)

上述式子为Thiele-连分式.

定义1.2[4]假定在x=x0这一点，函数f(x)为n阶可导，n=1,2,3,…，若f(x)可以展开成如下形式：

(1.2)

由

通过Viscovatov算法，则得到

定义1.3[5]假设函数f(x)一个迭代格式为

xk+1=φ(xk),k=0,1,2,…，

2 迭代算法

假定在x=x0这一点，函数f(x)为n阶可导，n=1,2,3,…，则由公式(1.2)可知：

(1)函数f(x)的第一项截断多项式可表示为

令其等于0，化简后得到

x=x0-b0b1.

根据定义(1.2)中的Viscovatov方法，得到b0=f(x0)，b1=1/f′(x0).于是得到如下迭代格式：

xn+1=xn-f(xn)f′(xn)-1.

(2.1)

(2)函数f(x)的第二项截断多项式可表示为

令其等于0，化简后得到

根据定义(1.2)中的Viscovatov方法，得到

于是得到如下迭代格式：

(2.2)

(3)函数f(x)的第三项截断多项式可表示为

令其等于0，于是有

(2.3)

由于式(2.3)含有(x-xk)2项，为简化计算，令f(x)的第一项截断多项式近似为零后化为

x=x0-b0b1.

(2.4)

将式(2.4)代入(2.3)，得到

(2.5)

根据定义(1.2)中的Viscovatov方法，得到

将b0,b1,b2,b3代入式(2.5)，得到

(2.6)

3 公式的收敛性

以逼近非线性方程f(x)=0的单根a处的迭代法为背景，其中，f:I⊂R→R满足f(a)=0，f′(a)≠0.首先需要了解以下定义[6-7]：

|xn+1-a|≤M|xn-a|p,

则称{xn}为p阶收敛到a，其中，n=0,1,2,….若p=1，则称{xn}线性收敛；若p=2，或p=3，…，或p=n，则称{xn}二次收敛，或三次收敛，…，或n次收敛.

设en=xn-a表示n次迭代误差，如果误差方程可写成：

则由定义3.1，得到该方法为p阶收敛.

定理3.1非线性方程f(x)=0(f:I⊂R→R)的单根为a∈I，I为开区间，假设xn→a，则由式(2.2)定义的迭代算法收敛阶数p=3，并且满足误差方程，则

证明 因为a是f(x)的单根，则由泰勒展开得到f(xn)，f′(xn)在a点的表达式为

于是有

化简计算后得到

于是有

所以，得到

(3.1)

由于en=xn-a，式(3.1)简化为

定理3.2非线性方程f(x)=0(f:I⊂R→R)的一个单根为a∈I，I为开区间，假设x0→a，则由公式(2.6)定义的迭代算法收敛阶数p=3，并且满足误差方程：

证明 因为a为f的单根，则运用泰勒展开得到f(xn),f′(xn),f″(xn),f′″(xn)在a点的表达式：

经过计算后有

于是，

可以得到

两式相除后得到

(3.2)

又因为

(3.3)

将(3.2)乘以(3.3)后得到

(3.4)

将en=xn-a代入(3.4)，于是，

4 数值实例

例4.1 求方程f(x)=x5-3x+2=0的根，取初值x0=-1.反复利用公式(2.1)(2.2)(2.6)和Newton迭代法，令|xn-xn+1|≤10-5时迭代终止，通过Python软件编程，计算结果如表1所示.

表1 例4.1计算结果

由表1可知，在给定条件下，Thiele-连分式逼近的第一项截断迭代即Newton迭代，需要迭代8次才能满足收敛，第二项和第三项截断迭代分别迭代4次和3次即可达到收敛.

综上证实，基于Thiele-连分式逼近的改进迭代格式中，其截断多项式的收敛速度、收敛阶数、收敛效果随n值的增大而增加.