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

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

在科學研究的數(shù)學問題中更多的是非線性問題，它們又常常歸結為非線性方程或非線性方程組的求解問題。第6頁，共43頁，2023年，2月20日，星期五4.1方程求根與二分法4.1.1引言（1.1）單變量非線性方程的一般形式其中也可以是無窮區(qū)間.f(x)是高次多項式函數(shù)或超越函數(shù)（1.2）

如果函數(shù)是多項式函數(shù)，即其中為實數(shù)，則稱方程(1.1)為次代數(shù)方程.超越函數(shù)不能表示為多項式的函數(shù)如(x)=3x5-2x4+8x2-7x+1(x)=e2x+1-xln(sinx)-2高次代數(shù)方程超越方程第7頁，共43頁，2023年，2月20日，星期五

若是的重零點，且充分光滑，則

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

如果實數(shù)滿足，則稱是方程(1.1)的根，或稱是的零點.若可分解為其中為正整數(shù)，且則稱為方程(1.1)的重根，或為的重零點，時為單根.結論第8頁，共43頁，2023年，2月20日，星期五通常方程根的數(shù)值解法大致分為三個步驟進行：非線性問題一般不存在直接的求解公式，要使用迭代法.本章將介紹常用的求解非線性方程的近似根的幾種數(shù)值解法①

判定根的存在性。即方程有沒有根？如果有根，有幾個根？②確定根的分布范圍。即將每一個根用區(qū)間隔離開來，這個過程實際上是獲得方程各根的初始近似值。③根的精確化。將根的初始近似值按某種方法逐步精確化，直到滿足預先要求的精度為止.第9頁，共43頁，2023年，2月20日，星期五如何求方程的有根區(qū)間？

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

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

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

求方程3x-1-cosx=0的有根區(qū)間。方程等價變形為3x-1=cosx，y=3x-1與y=cosx的圖像只有一個交點位于[0.5，1]內。第10頁，共43頁，2023年，2月20日，星期五對的根進行搜索計算，

例2

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

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

h=(b-a)/n

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

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

計算f(xi)的值,依據(jù)函數(shù)值異號及實根的個數(shù)確定有根區(qū)間,通過調整步長，總可找到所有有根區(qū)間。

解

第11頁，共43頁，2023年，2月20日，星期五4.1.2二分法求解方程f(x)=0的近似根的一種常用的簡單方法。原理基本思想設函數(shù)f(x)在閉區(qū)間[a,b]上連續(xù),且f(a)f(b)<0,則f(x)=0在(a,b)內必有實根區(qū)間。逐步將區(qū)間二等分,通過判斷區(qū)間端點f(x)的符號,逐步將有根區(qū)間縮小,直至有根區(qū)間足夠地小,便可求出滿足精度要求的近似根。具體做法第12頁，共43頁，2023年，2月20日，星期五以此類推由二分法的過程知(1)(2)(3)作為根的近似可得一個近似根的序列

第13頁，共43頁，2023年，2月20日，星期五（1.3）且(4)只要二分足夠多次（即充分大），便有這里為預定的精度.要使解：例3用二分法求方程在區(qū)間上的根，誤差限為，問至少需對分多少次？第14頁，共43頁，2023年，2月20日，星期五二分法的算法

步驟1準備

計算在有根區(qū)間端點處的值

步驟2二分

計算在區(qū)間中點處的值

步驟3判斷

若，則即是根，計算過程結束，否則檢驗.

若，則以代替，否則以代替.此時中點即為所求近似根.誤差，

反復執(zhí)行步驟2和步驟3，直到區(qū)間長度小于允許第15頁，共43頁，2023年，2月20日，星期五第16頁，共43頁，2023年，2月20日，星期五例4

求方程在區(qū)間內的一個實根，要求準確到小數(shù)點后第2位.欲使只需，即只要二分6次，便能達到預定的精度.

解得到新的有根區(qū)間第17頁，共43頁，2023年，2月20日，星期五二分法對多個零點的情況，只能算出其中一個零點。

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

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

草圖以確定根的大概位置。或用搜索程序，將[a,b]分為若干小區(qū)間，對每一個滿足f(ak)·f(bk)<0的區(qū)間調用二分法程序，可找出區(qū)間[a,b]內的多個根，且不必要求f(a)·f(b)<0。第18頁，共43頁，2023年，2月20日，星期五迭代法的基本思想基本思路同解迭代公式給定初值存在等價于迭代函數(shù)？轉換是否唯一幾何意義第19頁，共43頁，2023年，2月20日，星期五轉換例子(1)x=1(x)=x3-6x2+10x-2;(2)

;(3)

;(4)

;例：已知方程

x3-6x2+9x-2=0

在

[3,4]

內有一根，考慮迭代？哪種轉換方法好第20頁，共43頁，2023年，2月20日，星期五幾何含義xyy=xxyy=xx*x*y=g(x)y=g(x)x0p0x1p1x0p0x1p1第21頁，共43頁，2023年，2月20日，星期五幾何含義xyy=xxyy=xx*x*y=(x)y=(x)x0p0x1p1x0p0x1p1第22頁，共43頁，2023年，2月20日，星期五壓縮映像定理定理設(x)C[a,b]

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

對x[a,b]

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

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

xk+1

=

(xk)

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

中的唯一不動點x*。(b)有如下的誤差估計可用|xk+1-xk

|來控制收斂精度L

越小收斂越快第23頁，共43頁，2023年，2月20日，星期五壓縮映像定理證明(a)由壓縮映像定理可知，不動點x*

存在且唯一。第24頁，共43頁，2023年，2月20日，星期五壓縮映像定理證明(b)又第25頁，共43頁，2023年，2月20日，星期五全局收斂與局部收斂

定理的條件保證了不動點迭代的全局收斂性。即迭代的收斂性與初始點的選取無關。

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

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

在x*

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

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

鄰域

N(x*)

=[x*-,x*+],

使得對

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

<1,則由x0N(x*)開始的迭代都收斂。第26頁，共43頁，2023年，2月20日，星期五迭代過程的收斂速度定義則稱該迭代為r階收斂。(1)當r=1時稱為線性收斂，此時C<1；(2)當r=2時稱為二次收斂，或平方收斂；(3)當r>1時稱為超線性收斂。

二分法線性收斂

不動點迭代中，若

’(x*)0，則取極限得(C為常數(shù))線性收斂第27頁，共43頁，2023年，2月20日，星期五P階收斂設迭代xk+1=(xk)

，若(p)(x)

在x*的某鄰域內連續(xù)，則該迭代法具有p階收斂的充要條件是定理并且有證明：充分性.根據(jù)泰勒展開有第28頁，共43頁，2023年，2月20日，星期五必要性的證明必要性.設迭代xk+1=(xk)是p階收斂。迭代兩邊取極限

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

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

p0<p，

與迭代p

階收斂矛盾p0=p第29頁，共43頁，2023年，2月20日，星期五迭代過程的加速

設有不動點迭代：設：缺點：每次迭代需計算第30頁，共43頁，2023年，2月20日，星期五埃特金算法設：Aitken加速當x

收斂到x*時，修正項分子趨于零。

第31頁，共43頁，2023年，2月20日，星期五一點注記第32頁，共43頁，2023年，2月20日，星期五Newton迭代

基本思想：將非線性方程線性化設xk

是f(x)=0

的近似根，將f(x)

在

xk

一階Taylor展開:，在xk

和x

之間。xyx*xkxk+1條件：

f’(x)0第33頁，共43頁，2023年，2月20日，星期五Newton迭代

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

設f(x)

在其零點x*的某個鄰域內二階連續(xù)可導且f’(x)0，則存在

x*的某個

鄰域

N(x*)

=[x*-,x*+],

使得對

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

。第34頁，共43頁，2023年，2月20日，星期五Newton迭代

Newton法也可以看作一類特殊的加速迭代取(x)=x+f(x)第35頁，共43頁，2023年，2月20日，星期五收斂性定理定理設f

C2[a,b]，且

f

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

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

且f”(x)

0

；(3)初始點x0

[a,b]

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

的唯一零點x*。第36頁，共43頁，2023年，2月20日，星期五全局收斂性定理定理設f

C2[a,b]，且

f

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

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

且f”(x)

0

；則對任意初始點x0

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

的唯一零點x*。(3)第37頁，共43頁，2023年，2月20日，星期五舉例（一）例：設計一個二階收斂算法計算(a>0)。解：轉化為求x2-a=0的正根Newton迭代：二階收斂第38頁，共43頁，2023年，2月20日，星期五重根情形

設x*

是f(x)

的m(m2)

重根，Newton法是否收斂？Taylo