郭 巧,楊 兵,吳昌廣

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

0 引言

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

1 預(yù)備知識(shí)

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

f(x)+x=x,

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

(1)

其中,xn稱為迭代序列,h(x)稱為迭代函數(shù),式(1)稱為不動(dòng)點(diǎn)迭代或簡(jiǎn)單迭代.

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

則稱迭代序列收斂.

2 四類改進(jìn)迭代算法

2.1 點(diǎn)切式迭代

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

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

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

(2)

圖1 點(diǎn)切式迭代

2.2 切割式迭代

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

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

化簡(jiǎn)得到

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

令

則

(3)

圖2 切割式迭代

2.3 點(diǎn)點(diǎn)式迭代

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

化簡(jiǎn)得到

因?yàn)橹本€A0A1與y1=x相交于點(diǎn)C(x2,y2),代入即得

化簡(jiǎn)得到

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

(4)

圖3 點(diǎn)點(diǎn)式迭代

2.4 點(diǎn)斜式迭代

(5)

式(5)即為點(diǎn)斜式迭代.

圖4 點(diǎn)斜式迭代

3 收斂性分析

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

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

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

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

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

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

證明 1)收斂性分析

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

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

2)誤差分析

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

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

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

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

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

證明 1)收斂性分析

對(duì)于公式(3),令

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

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

2)誤差分析

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

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

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

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

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

證明 1)收斂性分析

2)誤差分析

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

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

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

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

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

證明 1)收斂性分析

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

2)誤差分析

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

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

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

4 數(shù)值實(shí)例

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

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

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