數(shù)值分析10-方程求根的迭代法

第四章方程求根的迭代法遠(yuǎn)在公元前1700年的古巴比倫人就已有關(guān)于一、二次方程的解法。《九章算術(shù)》(公元前50~100年)其中“方程術(shù)”有聯(lián)立一次方程組的一般解法。1535年意大利數(shù)學(xué)家坦特格里亞(TorTaglia)發(fā)現(xiàn)了三次方程的解法，卡當(dāng)(H·Cardano)從他那里得到了這種解法，于1545年在其名著《大法》中公布了三次方程的公式解，稱為卡當(dāng)算法。后來(lái)卡當(dāng)?shù)膶W(xué)生弗瑞里(Ferrari)又提出了四次方程的解法。此成果更激發(fā)了數(shù)學(xué)家們的情緒，但在以后的二個(gè)世紀(jì)中，求索工作始終沒(méi)有成效，導(dǎo)致人們對(duì)高次代數(shù)方程解的存在性產(chǎn)生了懷疑。1799年，高斯證明了代數(shù)方程必有一個(gè)實(shí)根或復(fù)根的定理，稱此為代數(shù)基本定理，并由此可以立刻推理n次代數(shù)方程必有n個(gè)實(shí)根或復(fù)根。但在以后的幾十年中仍然沒(méi)有找出高次代數(shù)方程的公式解。一直到18世紀(jì)，法國(guó)數(shù)學(xué)家拉格朗日用根置換方法統(tǒng)一了二、三、四方程的解法。但求解五次方程時(shí)未能如愿,開(kāi)始意識(shí)到有潛藏其中的奧妙,用現(xiàn)代術(shù)語(yǔ)表示就是置換群理論問(wèn)題。在繼續(xù)探索5次以上方程解的艱難歷程中，第一個(gè)重大突破的是挪威數(shù)學(xué)家阿貝爾(N·Abel1802-1829)1824年阿貝爾發(fā)表了“五次方程代數(shù)解法不可能存在”的論文，但并未受到重視，連數(shù)學(xué)大師高斯也未理解這項(xiàng)成果的重要意義。1828年17歲的法國(guó)數(shù)學(xué)家伽羅華(E·Galois1811-1832)寫(xiě)出了劃時(shí)代的論文“關(guān)于五次方程的代數(shù)解法問(wèn)題”，指出即使在公式中容許用n次方根，并用類似算法求五次或更高次代數(shù)方程的根是不可能的文章呈交法蘭西科學(xué)院后，因輩份太低遭到冷遇，且文稿丟失。1830年伽羅華再進(jìn)科學(xué)院遞稿，得到泊松院士的判詞“完全不能理解”。后來(lái)伽羅華命運(yùn)不佳，投考名校巴黎工科大學(xué)落榜，屈就高等師院，并卷入政事兩次入獄，被開(kāi)除學(xué)籍，又決斗受傷，死于1832年。決斗前，他把關(guān)于五次代數(shù)求解的研究成果寫(xiě)成長(zhǎng)信，留了下來(lái)。十四年后，法國(guó)數(shù)學(xué)家劉維爾(J·Liouville)整理并發(fā)表了伽羅華的遺作，人們才意識(shí)到這項(xiàng)近代數(shù)學(xué)發(fā)展史上的重要成果的寶貴。38年后，即1870年，法國(guó)數(shù)學(xué)家若當(dāng)(C·Jordan)在專著《論置換與代數(shù)方程》中闡發(fā)了伽羅華的思想，一門(mén)現(xiàn)代數(shù)學(xué)的分支—群論誕生了。在前幾個(gè)世紀(jì)中，曾開(kāi)發(fā)出一些求解代數(shù)方程的有效算法，它們構(gòu)成了數(shù)值分析中的古典算法。至于超越方程則不存在一般的求根方式。

在科學(xué)研究的數(shù)學(xué)問(wèn)題中更多的是非線性問(wèn)題，它們又常常歸結(jié)為非線性方程或非線性方程組的求解問(wèn)題。4.1方程求根與二分法4.1.1引言（1.1）單變量非線性方程的一般形式其中也可以是無(wú)窮區(qū)間.f(x)是高次多項(xiàng)式函數(shù)或超越函數(shù)（1.2）

如果函數(shù)是多項(xiàng)式函數(shù)，即其中為實(shí)數(shù)，則稱方程(1.1)為次代數(shù)方程.超越函數(shù)不能表示為多項(xiàng)式的函數(shù)如(x)=3x5-2x4+8x2-7x+1(x)=e2x+1-xln(sinx)-2高次代數(shù)方程超越方程

若是的重零點(diǎn)，且充分光滑，則

次方程在復(fù)數(shù)域有且只有個(gè)根（含重根，重根為個(gè)根）.超越方程它在整個(gè)軸上有無(wú)窮多個(gè)解，若取值范圍不同，解也不同，因此討論非線性方程(1.1)的求解必須強(qiáng)調(diào)的定義域，即的求解區(qū)間

如果實(shí)數(shù)滿足，則稱是方程(1.1)的根，或稱是的零點(diǎn).若可分解為其中為正整數(shù)，且則稱為方程(1.1)的重根，或?yàn)榈闹亓泓c(diǎn)，時(shí)為單根.結(jié)論通常方程根的數(shù)值解法大致分為三個(gè)步驟進(jìn)行：非線性問(wèn)題一般不存在直接的求解公式，要使用迭代法.本章將介紹常用的求解非線性方程的近似根的幾種數(shù)值解法①

判定根的存在性。即方程有沒(méi)有根？如果有根，有幾個(gè)根？②確定根的分布范圍。即將每一個(gè)根用區(qū)間隔離開(kāi)來(lái)，這個(gè)過(guò)程實(shí)際上是獲得方程各根的初始近似值。③根的精確化。將根的初始近似值按某種方法逐步精確化，直到滿足預(yù)先要求的精度為止.如何求方程的有根區(qū)間？

設(shè)f(x)∈C[a,b],且

f(a)f(b)<0,存在ξ∈(a,b)，使f(ξ)=0.根的存在性定理——閉區(qū)間上連續(xù)函數(shù)的介值定理有根區(qū)間如果f(x)在[a,b]上還是單調(diào)遞增或遞減的，則f(x)=0僅有一個(gè)實(shí)根。(1)描圖法

畫(huà)出y=f(x)的略圖，從而看出曲線與x軸交點(diǎn)的大致位置。也可將f(x)=0等價(jià)變形為g1(x)=g2(x)的形式，y=g1(x)與y=g2(x)兩曲線交點(diǎn)的橫坐標(biāo)所在的子區(qū)間即為含根區(qū)間。例1

求方程3x-1-cosx=0的有根區(qū)間。方程等價(jià)變形為3x-1=cosx，y=3x-1與y=cosx的圖像只有一個(gè)交點(diǎn)位于[0.5，1]內(nèi)。對(duì)的根進(jìn)行搜索計(jì)算，

例2

求方程的有根區(qū)間.由此可知方程的有根區(qū)間為(2)逐步搜索法

先確定方程f(x)=0的所有實(shí)根所在的區(qū)間為[a,b],從x0=a出發(fā),以步長(zhǎng)

h=(b-a)/n

其中n是正整數(shù)，在[a,b]內(nèi)取定節(jié)點(diǎn)：

xi=x0＋ih(i=0,1,2，……，n)

計(jì)算f(xi)的值,依據(jù)函數(shù)值異號(hào)及實(shí)根的個(gè)數(shù)確定有根區(qū)間,通過(guò)調(diào)整步長(zhǎng)，總可找到所有有根區(qū)間。

解

4.1.2二分法求解方程f(x)=0的近似根的一種常用的簡(jiǎn)單方法。原理基本思想設(shè)函數(shù)f(x)在閉區(qū)間[a,b]上連續(xù),且f(a)f(b)<0,則f(x)=0在(a,b)內(nèi)必有實(shí)根區(qū)間。逐步將區(qū)間二等分,通過(guò)判斷區(qū)間端點(diǎn)f(x)的符號(hào),逐步將有根區(qū)間縮小,直至有根區(qū)間足夠地小,便可求出滿足精度要求的近似根。具體做法以此類推由二分法的過(guò)程知(1)(2)(3)作為根的近似可得一個(gè)近似根的序列

（1.3）且(4)只要二分足夠多次（即充分大），便有這里為預(yù)定的精度.要使解：例3用二分法求方程在區(qū)間上的根，誤差限為，問(wèn)至少需對(duì)分多少次？二分法的算法

步驟1準(zhǔn)備

計(jì)算在有根區(qū)間端點(diǎn)處的值

步驟2二分

計(jì)算在區(qū)間中點(diǎn)處的值

步驟3判斷

若，則即是根，計(jì)算過(guò)程結(jié)束，否則檢驗(yàn).

若，則以代替，否則以代替.此時(shí)中點(diǎn)即為所求近似根.誤差，

反復(fù)執(zhí)行步驟2和步驟3，直到區(qū)間長(zhǎng)度小于允許例4

求方程在區(qū)間內(nèi)的一個(gè)實(shí)根，要求準(zhǔn)確到小數(shù)點(diǎn)后第2位.欲使只需，即只要二分6次，便能達(dá)到預(yù)定的精度.

解得到新的有根區(qū)間二分法對(duì)多個(gè)零點(diǎn)的情況，只能算出其中一個(gè)零點(diǎn)。

即使f(x)在[a,b]上有零點(diǎn)，也未必有f(a)f(b)<0。

不管有根區(qū)間多大,總能求出滿足精度要求的根,且對(duì)函數(shù)f(x)的要求不高,只要連續(xù)即可,計(jì)算亦簡(jiǎn)單。優(yōu)點(diǎn)缺點(diǎn)注：用二分法求根，最好先給出f(x)

草圖以確定根的大概位置?；蛴盟阉鞒绦颍瑢a,b]分為若干小區(qū)間，對(duì)每一個(gè)滿足f(ak)·f(bk)<0的區(qū)間調(diào)用二分法程序，可找出區(qū)間[a,b]內(nèi)的多個(gè)根，且不必要求f(a)·f(b)<0。迭代法的基本思想基本思路同解迭代公式給定初值存在等價(jià)于迭代函數(shù)？轉(zhuǎn)換是否唯一幾何意義轉(zhuǎn)換例子(1)x=1(x)=x3-6x2+10x-2;(2)

;(3)

;(4)

;例：已知方程

x3-6x2+9x-2=0

在

[3,4]

內(nèi)有一根，考慮迭代？哪種轉(zhuǎn)換方法好幾何含義xyy=xxyy=xx*x*y=g(x)y=g(x)x0p0x1p1x0p0x1p1幾何含義xyy=xxyy=xx*x*y=(x)y=(x)x0p0x1p1x0p0x1p1壓縮映像定理定理設(shè)(x)C[a,b]

且可導(dǎo)，若(2)0L<1，使得|’(x)|L

對(duì)x[a,b]

成立(1)a(x)b對(duì)一切x[a,b]

都成立則有(a)對(duì)任意x0[a,b]，由

xk+1

=

(xk)

產(chǎn)生的迭代序列均收斂到(x)在[a,b]

中的唯一不動(dòng)點(diǎn)x*。(b)有如下的誤差估計(jì)可用|xk+1-xk

|來(lái)控制收斂精度L

越小收斂越快壓縮映像定理證明(a)由壓縮映像定理可知，不動(dòng)點(diǎn)x*

存在且唯一。壓縮映像定理證明(b)又全局收斂與局部收斂

定理的條件保證了不動(dòng)點(diǎn)迭代的全局收斂性。即迭代的收斂性與初始點(diǎn)的選取無(wú)關(guān)。

這種在x*的鄰域內(nèi)具有的收斂性稱為局部收斂性。定理中的條件|’(x)|L

<1可以適當(dāng)放寬(2’)’(x)

在x*

的某個(gè)鄰域內(nèi)連續(xù)，且|’(x*)|<1由’(x)

的連續(xù)性及|’(x*)|<1即可推出：存在x*的某個(gè)

鄰域

N(x*)

=[x*-,x*+],

使得對(duì)

xN(x*)都有|’(x)|L

<1,則由x0N(x*)開(kāi)始的迭代都收斂。迭代過(guò)程的收斂速度定義則稱該迭代為r階收斂。(1)當(dāng)r=1時(shí)稱為線性收斂，此時(shí)C<1；(2)當(dāng)r=2時(shí)稱為二次收斂，或平方收斂；(3)當(dāng)r>1時(shí)稱為超線性收斂。

二分法線性收斂

不動(dòng)點(diǎn)迭代中，若

’(x*)0，則取極限得(C為常數(shù))線性收斂P階收斂設(shè)迭代xk+1=(xk)

，若(p)(x)

在x*的某鄰域內(nèi)連續(xù)，則該迭代法具有p階收斂的充要條件是定理并且有證明：充分性.根據(jù)泰勒展開(kāi)有必要性的證明必要性.設(shè)迭代xk+1=(xk)是p階收斂。迭代兩邊取極限

，由(x)的連續(xù)性可知x*=(x*)

。設(shè)p0是滿足的最小正整數(shù)。由充分性的證明過(guò)程可知迭代p0階收斂。又若

p0<p，

與迭代p

階收斂矛盾p0=p迭代過(guò)程的加速

設(shè)有不動(dòng)點(diǎn)迭代：設(shè)：缺點(diǎn)：每次迭代需計(jì)算埃特金算法設(shè)：Aitken加速當(dāng)x

收斂到x*時(shí)，修正項(xiàng)分子趨于零。

一點(diǎn)注記Newton迭代

基本思想：將非線性方程線性化設(shè)xk

是f(x)=0

的近似根，將f(x)

在

xk

一階Taylor展開(kāi):，在xk

和x

之間。xyx*xkxk+1條件：

f’(x)0Newton迭代

Newton法可以看作下面的不動(dòng)點(diǎn)迭代：其中’(x*)=0Newton法至少二階局部收斂定理

設(shè)f(x)

在其零點(diǎn)x*的某個(gè)鄰域內(nèi)二階連續(xù)可導(dǎo)且f’(x)0，則存在

x*的某個(gè)

鄰域

N(x*)

=[x*-,x*+],

使得對(duì)

x0N(x*)，Newton法產(chǎn)生的序列以不低于二階的收斂速度收斂到x*

。Newton迭代

Newton法也可以看作一類特殊的加速迭代取(x)=x+f(x)收斂性定理定理設(shè)f

C2[a,b]，且

f

滿足(1)f(a)f(b)<0(2)對(duì)

x[a,b]，f’(x)0

且f”(x)

0

；(3)初始點(diǎn)x0

[a,b]

滿足f(x0)f”(x0)>0；則Newton法產(chǎn)生的序列收斂到f在[a,b]

的唯一零點(diǎn)x*。全局收斂性定理定理設(shè)f

C2[a,b]，且

f

滿足(1)f(a)f(b)<0(2)對(duì)

x[a,b]，f’(x)0

且f”(x)

0

；則對(duì)任意初始點(diǎn)x0

[a,b]，Newton法產(chǎn)生的序列收斂到f在[a,b]

的唯一零點(diǎn)x*。(3)舉例（一）例：設(shè)計(jì)一個(gè)二階收斂算法計(jì)算(a>0)。解：轉(zhuǎn)化為求x2-a=0的正根Newton迭代：二階收斂重根情形

設(shè)x*

是f(x)

的m(m2)

重根，Newton法是否收斂？Taylor展式Newton迭代：線性收斂。且重?cái)?shù)m

越高，收斂越慢。提高收斂階

提高收斂速度但m通常無(wú)法預(yù)先知道！法一：取二階收斂法二：將求f(x)的重根轉(zhuǎn)化為求另一個(gè)函數(shù)的單根。構(gòu)造針對(duì)(x)的具有二階收斂的Newton迭代：令，則x*是(x)的單重根。降低初始點(diǎn)的要求例：求

sin(x)-x/6=0的正根。Newton下山法：kk

為數(shù)列中滿足的最大數(shù)。

算法7.2

(Newton下山法)給