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

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

在科學(xué)研究的數(shù)學(xué)問題中更多的是非線性問題，它們又常常歸結(jié)為非線性方程或非線性方程組的求解問題。在科學(xué)研究的數(shù)學(xué)問題中更多的是非線性問題，它們又常常4.1方程求根與二分法4.1.1引言（1.1）單變量非線性方程的一般形式其中也可以是無窮區(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ù)方程超越方程4.1方程求根與二分法4.1.1引言（1.1）單變

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

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

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

判定根的存在性。即方程有沒有根？如果有根，有幾個根？②確定根的分布范圍。即將每一個根用區(qū)間隔離開來，這個過程實(shí)際上是獲得方程各根的初始近似值。③根的精確化。將根的初始近似值按某種方法逐步精確化，直到滿足預(yù)先要求的精度為止.通常方程根的數(shù)值解法大致分為三個步驟進(jìn)行：非線性問題一般不存如何求方程的有根區(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僅有一個實(shí)根。(1)描圖法

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

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

例2

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

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

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ù)值異號及實(shí)根的個數(shù)確定有根區(qū)間,通過調(diào)整步長，總可找到所有有根區(qū)間。

解

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

以此類推由二分法的過程知(1)(2)(3)作為根的近似可得一（1.3）且(4)只要二分足夠多次（即充分大），便有這里為預(yù)定的精度.要使解：例3用二分法求方程在區(qū)間上的根，誤差限為，問至少需對分多少次？（1.3）且(4)只要二分足夠多次（即充分大），便有這二分法的算法

步驟1準(zhǔn)備

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

步驟2二分

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

步驟3判斷

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

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

反復(fù)執(zhí)行步驟2和步驟3，直到區(qū)間長度小于允許二分法的算法步驟1準(zhǔn)備計(jì)算在有根區(qū)數(shù)值分析10-方程求根的迭代法課件例4

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

解得到新的有根區(qū)間例4求方程在區(qū)間內(nèi)的一個實(shí)根，要求準(zhǔn)確到二分法對多個零點(diǎn)的情況，只能算出其中一個零點(diǎn)。

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

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

草圖以確定根的大概位置?；蛴盟阉鞒绦?，將[a,b]分為若干小區(qū)間，對每一個滿足f(ak)·f(bk)<0的區(qū)間調(diào)用二分法程序，可找出區(qū)間[a,b]內(nèi)的多個根，且不必要求f(a)·f(b)<0。二分法對多個零點(diǎn)的情況，只能算出其中一個零點(diǎn)。

即使f(x迭代法的基本思想基本思路同解迭代公式給定初值存在等價于迭代函數(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)換方法好轉(zhuǎn)換例子(1)x=1(x)=x3-6x2+10幾何含義xyy=xxyy=xx*x*y=g(x)y=g(x)x0p0x1p1x0p0x1p1幾何含義xyy=xxyy=xx*x*y=g(x)y=幾何含義xyy=xxyy=xx*x*y=(x)y=(x)x0p0x1p1x0p0x1p1幾何含義xyy=xxyy=xx*x*y=(x)y壓縮映像定理定理設(shè)(x)C[a,b]

且可導(dǎo)，若(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]

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

|來控制收斂精度L

越小收斂越快壓縮映像定理定理設(shè)(x)C[a,b]且可導(dǎo)，若(2壓縮映像定理證明(a)由壓縮映像定理可知，不動點(diǎn)x*

存在且唯一。壓縮映像定理證明(a)由壓縮映像定理可知，不動點(diǎn)x*存壓縮映像定理證明(b)又壓縮映像定理證明(b)又全局收斂與局部收斂

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

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

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

在x*

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

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

鄰域

N(x*)

=[x*-,x*+],

使得對

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

<1,則由x0N(x*)開始的迭代都收斂。全局收斂與局部收斂定理的條件保證了不動點(diǎn)迭代的全局收斂性。迭代過程的收斂速度定義則稱該迭代為r階收斂。(1)當(dāng)r=1時稱為線性收斂，此時C<1；(2)當(dāng)r=2時稱為二次收斂，或平方收斂；(3)當(dāng)r>1時稱為超線性收斂。

二分法線性收斂

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

’(x*)0，則取極限得(C為常數(shù))線性收斂迭代過程的收斂速度定義則稱該迭代為r階收斂。(1)當(dāng)P階收斂設(shè)迭代xk+1=(xk)

，若(p)(x)

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

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

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

p0<p，

與迭代p

階收斂矛盾p0=p必要性的證明必要性.設(shè)迭代xk+1=(xk)是迭代過程的加速

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

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

埃特金算法設(shè)：Aitken加速當(dāng)x收斂到x*時，修一點(diǎn)注記一點(diǎn)注記Newton迭代

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

是f(x)=0

的近似根，將f(x)

在

xk

一階Taylor展開:，在xk

和x

之間。xyx*xkxk+1條件：

f’(x)0Newton迭代基本思想：將非線性方程線性化設(shè)xk是Newton迭代

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

設(shè)f(x)

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

x*的某個

鄰域

N(x*)

=[x*-,x*+],

使得對

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

。Newton迭代Newton法可以看作下面的不動點(diǎn)迭代：Newton迭代

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

C2[a,b]，且

f

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

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è)fC2[a,b]，且f滿足全局收斂性定理定理設(shè)f

C2[a,b]，且

f

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

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

且f”(x)

0

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

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

的唯一零點(diǎn)x*。(3)全局收斂性定理定理設(shè)fC2[a,b]，且f滿舉例（一）例：設(shè)計(jì)一個二階收斂算法計(jì)算(a>0)。解：轉(zhuǎn)化為求x2-a=0的正根Newton迭代：二階收斂舉例（一）例：設(shè)計(jì)一個二階收斂算法計(jì)算(a重根情形

設(shè)x*

是f(x)

的m(m2)

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

越高，收斂越慢。重根情形設(shè)x*是f(x)的m(m2)重根，N提高收斂階

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

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

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

算法7.2

(Newton下山法)給定初始點(diǎn)x0，精度要求1.如果|f(xk)|<

,停機(jī)，輸出xk2.計(jì)算，=13.如果|f(xk+dk)|<|f(xk)|，令xk+1=xk+dk

，返回第1步；

否則折半，重新計(jì)算第3步Newton法的收斂依賴于初始點(diǎn)的選取。降低初始點(diǎn)的要求例：求sin(x)-x/6=0的正根。割線法Newton法的缺點(diǎn)：每步迭代都要計(jì)算導(dǎo)數(shù)值

只需計(jì)算函數(shù)值，避免計(jì)算導(dǎo)數(shù)；切線斜率割線斜率xk-1xkxk+1xk+1切線割線

需要兩個初始點(diǎn)；

收斂比Newton法稍慢，但對初始點(diǎn)要求同樣高。割線法Newton法的缺點(diǎn)：每步迭代都要計(jì)算導(dǎo)數(shù)值只需計(jì)割線法公式

兩點(diǎn)割線法

單點(diǎn)割線法割線法公式兩點(diǎn)割線法單點(diǎn)割線法誤差估計(jì)引理

設(shè)f(x)在其零點(diǎn)x*的某個鄰域

N(x*)

=[x*-,x*+]內(nèi)存在連續(xù)的二階導(dǎo)數(shù)，且f’(x)0，又設(shè)xk-1,xkN(x*)\{x*}，且互不相等，則由兩點(diǎn)割線法的誤差

ek=xk-x*

滿足其中誤差估計(jì)引理設(shè)f(x)在其零點(diǎn)x*局部收斂性定理定理

設(shè)x*

是f(x)的單重零點(diǎn)，f”(x)在x*的某個鄰域內(nèi)連續(xù)，則存在x*的一個鄰域N(x*)

=[x*-,x*+]，使得當(dāng)x0,x1

N(x*)時，由兩點(diǎn)割線法產(chǎn)生的序列收斂到x*，且收斂階為局部收斂性定理定理設(shè)x*是f(x)本章結(jié)束謝謝！本章結(jié)束謝謝！人有了知識，就會具備各種分析能力，明辨是非的能力。所以我們要勤懇讀書，廣泛閱讀，古人說“書中自有黃金屋?！蓖ㄟ^閱讀科技書籍，我們能豐富知識，培養(yǎng)邏輯思維能力；通過閱讀文學(xué)作品，我們能提高文學(xué)鑒賞水平，培養(yǎng)文學(xué)情趣；通過閱讀報刊，我們能增長見識，擴(kuò)大自己的知識面。有許多書籍還能培養(yǎng)我們的道德情操，給我們巨大的精神力量，鼓舞我們前進(jìn)。人有了知識，就會具備各種分析能力，數(shù)值分析10-方程求根的迭代法課件第四章方程求根的迭代法第四章方程求根的迭代法遠(yuǎn)在公元前1700年的古巴比倫人就已有關(guān)于一、二次方程的解法?！毒耪滤阈g(shù)》(公元前50~100年)其中“方程術(shù)”有聯(lián)立一次方程組的一般解法。1535年意大利數(shù)學(xué)家坦特格里亞(TorTaglia)發(fā)現(xiàn)了三次方程的解法，卡當(dāng)(H·Cardano)從他那里得到了這種解法，于1545年在其名著《大法》中公布了三次方程的公式解，稱為卡當(dāng)算法。后來卡當(dāng)?shù)膶W(xué)生弗瑞里(Ferrari)又提出了四次方程的解法。此成果更激發(fā)了數(shù)學(xué)家們的情緒，但在以后的二個世紀(jì)中，求索工作始終沒有成效，導(dǎo)致人們對高次代數(shù)方程解的存在性產(chǎn)生了懷疑。遠(yuǎn)在公元前1700年的古巴比倫人就已有關(guān)于一、二次方程的解法1799年，高斯證明了代數(shù)方程必有一個實(shí)根或復(fù)根的定理，稱此為代數(shù)基本定理，并由此可以立刻推理n次代數(shù)方程必有n個實(shí)根或復(fù)根。但在以后的幾十年中仍然沒有找出高次代數(shù)方程的公式解。一直到18世紀(jì)，法國數(shù)學(xué)家拉格朗日用根置換方法統(tǒng)一了二、三、四方程的解法。但求解五次方程時未能如愿,開始意識到有潛藏其中的奧妙,用現(xiàn)代術(shù)語表示就是置換群理論問題。在繼續(xù)探索5次以上方程解的艱難歷程中，第一個重大突破的是挪威數(shù)學(xué)家阿貝爾(N·Abel1802-1829)1824年阿貝爾發(fā)表了“五次方程代數(shù)解法不可能存在”的論文，但并未受到重視，連數(shù)學(xué)大師高斯也未理解這項(xiàng)成果的重要意義。1799年，高斯證明了代數(shù)方程必有一個實(shí)根或復(fù)根的定理，稱此1828年17歲的法國數(shù)學(xué)家伽羅華(E·Galois1811-1832)寫出了劃時代的論文“關(guān)于五次方程的代數(shù)解法問題”，指出即使在公式中容許用n次方根，并用類似算法求五次或更高次代數(shù)方程的根是不可能的文章呈交法蘭西科學(xué)院后，因輩份太低遭到冷遇，且文稿丟失。1830年伽羅華再進(jìn)科學(xué)院遞稿，得到泊松院士的判詞“完全不能理解”。后來伽羅華命運(yùn)不佳，投考名校巴黎工科大學(xué)落榜，屈就高等師院，并卷入政事兩次入獄，被開除學(xué)籍，又決斗受傷，死于1832年。決斗前，他把關(guān)于五次代數(shù)求解的研究成果寫成長信，留了下來。1828年17歲的法國數(shù)學(xué)家伽羅華(E·Galois181十四年后，法國數(shù)學(xué)家劉維爾(J·Liouville)整理并發(fā)表了伽羅華的遺作，人們才意識到這項(xiàng)近代數(shù)學(xué)發(fā)展史上的重要成果的寶貴。38年后，即1870年，法國數(shù)學(xué)家若當(dāng)(C·Jordan)在專著《論置換與代數(shù)方程》中闡發(fā)了伽羅華的思想，一門現(xiàn)代數(shù)學(xué)的分支—群論誕生了。在前幾個世紀(jì)中，曾開發(fā)出一些求解代數(shù)方程的有效算法，它們構(gòu)成了數(shù)值分析中的古典算法。至于超越方程則不存在一般的求根方式。十四年后，法國數(shù)學(xué)家劉維爾(J·Liouville)整理并發(fā)

在科學(xué)研究的數(shù)學(xué)問題中更多的是非線性問題，它們又常常歸結(jié)為非線性方程或非線性方程組的求解問題。在科學(xué)研究的數(shù)學(xué)問題中更多的是非線性問題，它們又常常4.1方程求根與二分法4.1.1引言（1.1）單變量非線性方程的一般形式其中也可以是無窮區(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ù)方程超越方程4.1方程求根與二分法4.1.1引言（1.1）單變

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

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

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

判定根的存在性。即方程有沒有根？如果有根，有幾個根？②確定根的分布范圍。即將每一個根用區(qū)間隔離開來，這個過程實(shí)際上是獲得方程各根的初始近似值。③根的精確化。將根的初始近似值按某種方法逐步精確化，直到滿足預(yù)先要求的精度為止.通常方程根的數(shù)值解法大致分為三個步驟進(jìn)行：非線性問題一般不存如何求方程的有根區(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僅有一個實(shí)根。(1)描圖法

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

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

例2

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

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

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ù)值異號及實(shí)根的個數(shù)確定有根區(qū)間,通過調(diào)整步長，總可找到所有有根區(qū)間。

解

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

以此類推由二分法的過程知(1)(2)(3)作為根的近似可得一（1.3）且(4)只要二分足夠多次（即充分大），便有這里為預(yù)定的精度.要使解：例3用二分法求方程在區(qū)間上的根，誤差限為，問至少需對分多少次？（1.3）且(4)只要二分足夠多次（即充分大），便有這二分法的算法

步驟1準(zhǔn)備

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

步驟2二分

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

步驟3判斷

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

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

反復(fù)執(zhí)行步驟2和步驟3，直到區(qū)間長度小于允許二分法的算法步驟1準(zhǔn)備計(jì)算在有根區(qū)數(shù)值分析10-方程求根的迭代法課件例4

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

解得到新的有根區(qū)間例4求方程在區(qū)間內(nèi)的一個實(shí)根，要求準(zhǔn)確到二分法對多個零點(diǎn)的情況，只能算出其中一個零點(diǎn)。

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

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

草圖以確定根的大概位置?；蛴盟阉鞒绦?，將[a,b]分為若干小區(qū)間，對每一個滿足f(ak)·f(bk)<0的區(qū)間調(diào)用二分法程序，可找出區(qū)間[a,b]內(nèi)的多個根，且不必要求f(a)·f(b)<0。二分法對多個零點(diǎn)的情況，只能算出其中一個零點(diǎn)。

即使f(x迭代法的基本思想基本思路同解迭代公式給定初值存在等價于迭代函數(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)換方法好轉(zhuǎn)換例子(1)x=1(x)=x3-6x2+10幾何含義xyy=xxyy=xx*x*y=g(x)y=g(x)x0p0x1p1x0p0x1p1幾何含義xyy=xxyy=xx*x*y=g(x)y=幾何含義xyy=xxyy=xx*x*y=(x)y=(x)x0p0x1p1x0p0x1p1幾何含義xyy=xxyy=xx*x*y=(x)y壓縮映像定理定理設(shè)(x)C[a,b]

且可導(dǎo)，若(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]

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

|來控制收斂精度L

越小收斂越快壓縮映像定理定理設(shè)(x)C[a,b]且可導(dǎo)，若(2壓縮映像定理證明(a)由壓縮映像定理可知，不動點(diǎn)x*

存在且唯一。壓縮映像定理證明(a)由壓縮映像定理可知，不動點(diǎn)x*存壓縮映像定理證明(b)又壓縮映像定理證明(b)又全局收斂與局部收斂

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

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

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

在x*

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

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

鄰域

N(x*)

=[x*-,x*+],

使得對

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

<1,則由x0N(x*)開始的迭代都收斂。全局收斂與局部收斂定理的條件保證了不動點(diǎn)迭代的全局收斂性。迭代過程的收斂速度定義則稱該迭代為r階收斂。(1)當(dāng)r=1時稱為線性收斂，此時C<1；(2)當(dāng)r=2時稱為二次收斂，或平方收斂；(3)當(dāng)r>1時稱為超線性收斂。

二分法線性收斂

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

’(x*)0，則取極限得(C為常數(shù))線性收斂迭代過程的收斂速度定義則稱該迭代為r階收斂。(1)當(dāng)P階收斂設(shè)迭代xk+1=(xk)

，若(p)(x)

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

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

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

p0<p，

與迭代p

階收斂矛盾p0=p必要性的證明必要性.設(shè)迭代xk+1=(xk)是迭代過程的加速

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

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

埃特金算法設(shè)：Aitken加速當(dāng)x收斂到x*時，修一點(diǎn)注記一點(diǎn)注記Newton迭代

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

是f(x)=0

的近似根，將f(x)

在

xk

一階Taylor展開:，在xk

和x

之間。xyx*xkxk+1條件：

f’(x)0Newton迭代基本思想：將非線性方程線性化設(shè)xk是Newton迭代

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

設(shè)f(x)

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

x*的某個

鄰域

N(x*)

=[x*-,x*+],

使得對

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

。Newton迭代Newton法可以看作下面的不動點(diǎn)迭代：Newton迭代

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

C2[a,b]，且

f

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

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è)fC2[a,b]，且f滿足全局收斂性定理定理設(shè)f

C2[a,b]，且

f

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

x[a,b]，f’(x