基于Thiele-連分式逼近的改進(jìn)迭代算法及收斂性分析

郭 巧，楊 兵，葛小竹，顏玉柱

(安徽職業(yè)技術(shù)學(xué)院，安徽 合肥 230601)

0 引言

一般地，高階非線性方程求根時，參考最多的是迭代函數(shù)算法，其迭代效果也各不一樣[1-3].Newton迭代法，由于其較為簡單的迭代格式、較為快速的迭代收斂速度，一直被作為經(jīng)典迭代法運(yùn)用于非線性方程求根運(yùn)算.但是Newton迭代法收斂階數(shù)較低，本文以此為突破口，結(jié)合Thiele-連分式逼近、泰勒冪級數(shù)展開、Viscovatov算法等相關(guān)知識，通過兩次迭代，推導(dǎo)出第一項、第二項和第三項截斷多項式逼近的迭代算法.通過分析其收斂性，構(gòu)造出一類基于Thiele-連分式逼近的高階收斂的迭代算法.其中，由Thiele-連分式第一項截斷后推導(dǎo)出的迭代算法(Newton迭代公式)為二階收斂，第二項截斷后推導(dǎo)出的迭代算法為三階收斂，第三項截斷后推導(dǎo)出的迭代算法為四階收斂.在給定背景下證明此改進(jìn)迭代算法的收斂階數(shù)、效率指數(shù)和收斂速度更優(yōu)于Newton迭代，最后給出了數(shù)值實例.

1 預(yù)備知識

定義1.1[4]給定多項式

(1.1)

上述式子為Thiele-連分式.

定義1.2[4]假定在x=x0這一點，函數(shù)f(x)為n階可導(dǎo)，n=1,2,3,…，若f(x)可以展開成如下形式：

(1.2)

由

通過Viscovatov算法，則得到

定義1.3[5]假設(shè)函數(shù)f(x)一個迭代格式為

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

2 迭代算法

假定在x=x0這一點，函數(shù)f(x)為n階可導(dǎo)，n=1,2,3,…，則由公式(1.2)可知：

(1)函數(shù)f(x)的第一項截斷多項式可表示為

令其等于0，化簡后得到

x=x0-b0b1.

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

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

(2.1)

(2)函數(shù)f(x)的第二項截斷多項式可表示為

令其等于0，化簡后得到

根據(jù)定義(1.2)中的Viscovatov方法，得到

于是得到如下迭代格式：

(2.2)

(3)函數(shù)f(x)的第三項截斷多項式可表示為

令其等于0，于是有

(2.3)

由于式(2.3)含有(x-xk)2項，為簡化計算，令f(x)的第一項截斷多項式近似為零后化為

x=x0-b0b1.

(2.4)

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

(2.5)

根據(jù)定義(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次收斂.

設(shè)en=xn-a表示n次迭代誤差，如果誤差方程可寫成：

則由定義3.1，得到該方法為p階收斂.

定理3.1非線性方程f(x)=0(f:I?R→R)的單根為a∈I，I為開區(qū)間，假設(shè)xn→a，則由式(2.2)定義的迭代算法收斂階數(shù)p=3，并且滿足誤差方程，則

證明 因為a是f(x)的單根，則由泰勒展開得到f(xn)，f′(xn)在a點的表達(dá)式為

于是有

化簡計算后得到

于是有

所以，得到

(3.1)

由于en=xn-a，式(3.1)簡化為

定理3.2非線性方程f(x)=0(f:I?R→R)的一個單根為a∈I，I為開區(qū)間，假設(shè)x0→a，則由公式(2.6)定義的迭代算法收斂階數(shù)p=3，并且滿足誤差方程：

證明 因為a為f的單根，則運(yùn)用泰勒展開得到f(xn),f′(xn),f″(xn),f′″(xn)在a點的表達(dá)式：

經(jīng)過計算后有

于是，

可以得到

兩式相除后得到

(3.2)

又因為

(3.3)

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

(3.4)

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

4 數(shù)值實例

例4.1 求方程f(x)=x5-3x+2=0的根，取初值x0=-1.反復(fù)利用公式(2.1)(2.2)(2.6)和Newton迭代法，令|xn-xn+1|≤10-5時迭代終止，通過Python軟件編程，計算結(jié)果如表1所示.

表1 例4.1計算結(jié)果

由表1可知，在給定條件下，Thiele-連分式逼近的第一項截斷迭代即Newton迭代，需要迭代8次才能滿足收斂，第二項和第三項截斷迭代分別迭代4次和3次即可達(dá)到收斂.

綜上證實，基于Thiele-連分式逼近的改進(jìn)迭代格式中，其截斷多項式的收斂速度、收斂階數(shù)、收斂效果隨n值的增大而增加.