基于函數(shù)值不動點逼近的四類改進迭代算法

郭 巧,楊 兵,吳昌廣

(1.安徽職業(yè)技術(shù)學(xué)院計算機與信息技術(shù)學(xué)院,安徽 合肥 230611;2.安徽職業(yè)技術(shù)學(xué)院智能制造學(xué)院,安徽 合肥 230611;3.南京理工大學(xué)計算機學(xué)院,江蘇 南京 210094)

0 引言

迭代法是非線性數(shù)值逼近求根的常用方法[1-4],主要有簡單迭代法、Newton迭代法、弦割法,雖然這些方法運算簡單,但都存在一定的局限性,如重根附近發(fā)散、迭代速率較低等.為避免諸如此類的問題,本文提出四類改進的求解非線性數(shù)值逼近的迭代法,并通過收斂性分析和數(shù)值實例驗證,在保證收斂的前提下,其迭代速度明顯優(yōu)于簡單迭代.

1 預(yù)備知識

定義1.1[5]將非線性方程f(x)=0等式兩邊同時加上x,得到

f(x)+x=x,

令h(x)=f(x)+x,將非線性方程求根等價變形為x=h(x).給定初始值x0,則有

(1)

其中,xn稱為迭代序列,h(x)稱為迭代函數(shù),式(1)稱為不動點迭代或簡單迭代.

定義1.2 若對于任意x0∈[a,b],由式(1)產(chǎn)生的迭代序列滿足:

則稱迭代序列收斂.

2 四類改進迭代算法

2.1 點切式迭代

如圖1所示,設(shè)非線性方程f(x)=0在點x0附近有一個單根,可將非線性方程等價變形為x=h(x),求非線性方程f(x)=0的根,即為求方程y1=x和y2=h(x)交點的橫坐標(biāo).

過A0(x0,h(x0))作曲線y2=h(x)的切線交y1=x于B,切線方程為y-h(x0)=h′(x0)(x-x0).

如此重復(fù),得到點切式迭代公式:

(2)

圖1 點切式迭代

2.2 切割式迭代

如圖2所示,連接A0A1并延長交y1=x于點C,設(shè)C點橫坐標(biāo)為x1,則直線A0A1的方程為

將C(x1,x1)代入直線A0A1方程,得到

化簡得到

如此重復(fù),得到切割式迭代公式:

令

則

(3)

圖2 切割式迭代

2.3 點點式迭代

如圖3所示,在曲線y2=h(x)上取兩點A0(x0,h(x0)),A1(x1,h(x1)),則直線A0A1的方程為

化簡得到

因為直線A0A1與y1=x相交于點C(x2,y2),代入即得

化簡得到

如此重復(fù),則得點點式迭代公式:

(4)

圖3 點點式迭代

2.4 點斜式迭代

(5)

式(5)即為點斜式迭代.

圖4 點斜式迭代

3 收斂性分析

本文研究求解非線性方程f(x)=0的變形x=h(x)在單根a處的迭代法.

定義3.1[6]設(shè)x*為h(x)的一個不動點,h′(x)在x*的某領(lǐng)域N(x*)連續(xù)且|h′(x*)|<1,則迭代法對任意x(0)∈N(x*)收斂.

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

則稱數(shù)列{xn}p階收斂到a.

定理3.1 設(shè)x*為h(x)的一個不動點,如果xn→x*,則由公式(2)定義的迭代法二階收斂,且誤差方程為

其中,en=xn-x*,H(x*)為代替h(x*)的算法表達式.

證明 1)收斂性分析

當(dāng)x=x*時,h(x*)=x,則H′(x*)=0,由定義3.1可知,迭代公式(2)收斂.

注 若對H′(x)繼續(xù)求導(dǎo),得到的H″(x*)≠0.

2)誤差分析

對于公式(2),將H(x)在x*附近泰勒展開,得到

由xn+1=H(xn),x*=H(x*),en=xn-x*,H′(x*)=0,故上式變形為

故由公式(2)定義的迭代法二階收斂.

定理3.2 設(shè)x*為h(x)的一個不動點,如果xn→x*,則由公式(3)定義的迭代法二階收斂,且誤差方程為

其中,en=xn-x*,H(x*)為代替h(x*)的算法表達式.

證明 1)收斂性分析

對于公式(3),令

對H(x)求導(dǎo)得到

當(dāng)x=x*時,h(x*)=x,由公式(2)可知,A′(x*)=0,由公式(1)可知,A(xn)→x*,則h(A(xn))→h(x*)→x*,代入上式,有H′(x*)=0,由定義3.1可知,迭代公式(3)收斂.

2)誤差分析

對于公式(3),將H(x)在x*附近泰勒展開,則有

由xn+1=H(xn),x*=H(x*),en=xn-x*,H′(x*)=0,故上式變形為

故由公式(3)定義的迭代法二階收斂.

定理3.3 設(shè)x*為h(x)的一個不動點,如果xn→x*,則由公式(4)定義的迭代法二階收斂,且誤差方程為

其中,en=xn-x*,H(x*)為代替h(x*)的算法表達式.公式(5)定義的迭代法線性收斂.

證明 1)收斂性分析

2)誤差分析

對于公式(4),將H(x)在x*附近泰勒展開,有

由xn+1=H(xn),x*=H(x*),en=xn-x*,H′(x*)=0,故上式變形為

故由公式(4)定義的迭代法二階收斂.

定理3.4 設(shè)x*為h(x)的一個不動點,如果xn→x*,則由公式(5)定義的迭代法線性收斂,且誤差方程為

其中,en=xn-x*,H(x*)為代替h(x*)的算法表達式.

證明 1)收斂性分析

因為B為曲線h(x)在過橫坐標(biāo)為x0和x1兩點所構(gòu)成的直線的斜率,故B為常數(shù),則H′(x*)≠0,且|H′(x*)|<1,由定義3.1可知,迭代公式(5)收斂.

2)誤差分析

對于公式(5),將H(x)在x*附近泰勒展開,則有

由xn+1=H(xn),x*=H(x*),en=xn-x*,故上式變形為

故由公式(5)定義的迭代法線性收斂.

4 數(shù)值實例

例4.1 求非線性方程f(x)=e-x-x=0的根,取初值x0=0.5,令|xn-xn+1|≤10-4,通過簡單迭代法的公式(1)、點切式迭代法的公式(2)、切割式迭代法的公式(3)、點點式迭代法的公式(4)、點斜式迭代法的公式(5)迭代算法,通過Matlab編程,計算結(jié)果見表1.

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

由表1可以看出,在初始值和精度要求相同的情況下,求解非線性方程近似根簡單迭代法需要迭代14次才能達到精度要求,但是改進的點切式迭代法只需要迭代3次,切割式迭代法、點點式迭代法、點斜式迭代法分別只需要迭代2次,而點斜式迭代法在第一次迭代運算后就達到與第二次基本相同的迭代結(jié)果,改進的迭代算法收斂速度更快,并且能有效避免重根附近發(fā)散,該算法在機器人軌跡規(guī)劃算法中具有較高的應(yīng)用和推廣潛力.