數(shù)值分析 第七章 非線性方程(組)的數(shù)值解法

數(shù)值分析

NumericalAnalysis第七章非線性方程（組）的數(shù)值解法鄭州大學(xué)研究生課程（2014-2015學(xué)年第一學(xué)期）

ISCM2007,BeijingChina1第七章非線性方程（組）的數(shù)值解法

§7.1引言§7.2二分區(qū)間法§7.3迭代法及其加速§7.4牛頓迭代法§7.5弦截法§7.6解非線性方程組的迭代解法ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.1引言在科學(xué)研究和工程設(shè)計(jì)中,經(jīng)常會(huì)遇到的一大類問題是非線性方程

f(x)=0

的求根問題，其中f(x)為非線性函數(shù)。方程f(x)=0的根,亦稱為函數(shù)f(x)的零點(diǎn)。

非線性方程的例子（1）在光的衍射理論中,需要求x-tanx=0的根（2）在行星軌道的計(jì)算中,需要求x-asinx=b的根ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.1引言

當(dāng)f(x)不是x的線性函數(shù)時(shí)，稱對(duì)應(yīng)的函數(shù)方程

f(x)=0為非線性方程?！锶绻鹒(x)是多項(xiàng)式函數(shù)，則稱為代數(shù)方程?！锓駝t為超越方程（三角方程，指數(shù)、對(duì)數(shù)方程等）。一般稱n次多項(xiàng)式構(gòu)成的方程為n次代數(shù)方程,當(dāng)n＞1時(shí),方程顯然是非線性的ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.1引言如果f(x)可以分解成,其中m為正整數(shù)且,則稱x*是f(x)的m重零點(diǎn),或稱方程f(x)=0的m重根。當(dāng)m=1時(shí)稱x*為單根。

求方程根的問題，就幾何上講,是求曲線y=f(x)與x軸交點(diǎn)的橫坐標(biāo)。ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.1引言公元前1700年的古巴比倫人有關(guān)于一、二次代數(shù)方程的解法?！毒耪滤阈g(shù)》(公元前50~100年)其中“方程術(shù)”有聯(lián)立一次方程組的一般解法。1535年意大利數(shù)學(xué)家坦特格里亞(TorTaglia)發(fā)現(xiàn)了三次代數(shù)方程的解法，卡當(dāng)(H·Cardano)從他那里得到了這種解法，于1545年在其名著《大法》中公布了三次方程的公式解，稱為卡當(dāng)算法。后來卡當(dāng)?shù)膶W(xué)生弗瑞里(Ferrari)又提出了四次代數(shù)方程的解法。此成果更激發(fā)了數(shù)學(xué)家們的情緒，但在以后的二個(gè)世紀(jì)中，求索工作始終沒有成效，導(dǎo)致人們對(duì)高次代數(shù)方程解的存在性產(chǎn)生了懷疑。代數(shù)方程求根的歷史ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.1引言代數(shù)方程求根的歷史1799年，高斯證明了代數(shù)方程必有一個(gè)實(shí)根或復(fù)根的定理，稱此為代數(shù)基本定理，并由此可以立刻推理n次代數(shù)方程必有n個(gè)實(shí)根或復(fù)根。但在以后的幾十年中仍然沒有找出高次代數(shù)方程的公式解。一直到18世紀(jì)，法國數(shù)學(xué)家拉格朗日用根置換方法統(tǒng)一了二、三、四次方程的解法。在繼續(xù)探索5次以上方程解的艱難歷程中，第一個(gè)重大突破的是挪威數(shù)學(xué)家阿貝爾(N·Abel1802-1829)1824年阿貝爾發(fā)表了“五次方程的代數(shù)解法不可能存在”的論文，但并未受到重視，連數(shù)學(xué)大師高斯也未理解這項(xiàng)成果的重要意義。ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.1引言代數(shù)方程求根的歷史1828年17歲的法國數(shù)學(xué)家伽羅華(E·Galois1811-1832)寫出了劃時(shí)代的論文“關(guān)于五次方程的代數(shù)解法問題”，指出即使在公式中容許用n次方根，并用類似算法求五次或更高次代數(shù)方程的根是不可能的?！?，“他一勞永逸地發(fā)現(xiàn)了一個(gè)折磨了數(shù)學(xué)家?guī)讉€(gè)世紀(jì)的謎團(tuán)的答案：在什么條件下一個(gè)方程有解？”

ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.1引言理論上已證明，對(duì)于次數(shù)n<=4的多項(xiàng)式方程,它的根可以用公式表示,而次數(shù)大于5的多項(xiàng)式方程,它的根一般不能用解析表達(dá)式表示.因此對(duì)于f(x)=0的函數(shù)方程,一般來說,不存在根的解析表達(dá)式,而實(shí)際應(yīng)用中,也不一定必需得到求根的解析表達(dá)式,只要得到滿足精度要求的根的近似值就可以了。常用的求根方法分為區(qū)間法和迭代法兩大類。求根問題包括：根的存在性、根的范圍和根的精確化。ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.1引言數(shù)值解法的三個(gè)步驟

①

判定根的存在性。即方程有沒有根？如果有根，有幾個(gè)根？②確定根的分布范圍。即將每一個(gè)根用區(qū)間隔離開來，這個(gè)過程實(shí)際上是獲得方程各根的初始近似值。（隔離根）③根的精確化。將根的初始近似值按某種格式逐步精確化，直到滿足預(yù)先要求的精度為止。ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis定理1(根的存在定理，介值定理)

假設(shè)函數(shù)y=f(x)Ca,b,且f(a)·f(b)<0,則至少存在一點(diǎn)x(a,b)使得

f(x)=0。定理2

假設(shè)函數(shù)y=f(x)在a,b上單調(diào)連續(xù),且f(a)·f(b)<0,

則恰好只存在一點(diǎn)x(a,b)使得

f(x)=0。定理3

假設(shè)函數(shù)y=f(x)在x=s的某一鄰域內(nèi)充分可微，則s是方程f(x)=0的m重根的充分必要條件是

§7.1引言y=f(x)abyxISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.2二分區(qū)間法設(shè)函數(shù)f(x)在閉區(qū)間[a,b]上連續(xù),且f

(a)·f(b)<0,根據(jù)連續(xù)函數(shù)的性質(zhì)可知,f(x)=0在(a,b)內(nèi)必有實(shí)根,稱區(qū)間[a,b]為有根區(qū)間。假定方程f(x)=

0在區(qū)間[a,b]內(nèi)有惟一實(shí)根x*。

二分法的基本思想是:首先確定一個(gè)有根區(qū)間,將區(qū)間二等分,通過判斷f(x)在區(qū)間端點(diǎn)的符號(hào),逐步將有根區(qū)間縮小,直至有根區(qū)間足夠地小,便可求出滿足精度要求的近似根。ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.2二分法基本思想將有根區(qū)間進(jìn)行對(duì)分，判斷出解在某個(gè)分段內(nèi)，然后再對(duì)該段對(duì)分，依次類推，直到滿足給定的精度為止

適用范圍求有根區(qū)間內(nèi)的奇數(shù)重實(shí)根

數(shù)學(xué)原理：介值定理設(shè)

f(x)

在[a,b]

上連續(xù)，且f(a)

f(b)<0，則由介值定理可得，在

(a,b)

內(nèi)至少存在一點(diǎn)

使得f()=0ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis二分法是一種確定有根區(qū)間的方法為了確定根的初值，首先必須圈定根所在的范圍，稱為圈定根或根的隔離。在上述基礎(chǔ)上，采取適當(dāng)?shù)臄?shù)值方法確定具有一定精度要求的初值。

對(duì)于代數(shù)方程，其根的個(gè)數(shù)（實(shí)或復(fù)的）與其次數(shù)相同。至于超越方程，其根可能是一個(gè)、幾個(gè)或無解，并沒有什么固定的圈根方法ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.2區(qū)間法設(shè)f(x)為區(qū)間[a,b]上的連續(xù)函數(shù),如果f(a)·f(b)<0,則[a,b]中至少有一個(gè)實(shí)根。如果f(x)在[a,b]上還是單調(diào)地遞增或遞減，則僅有一個(gè)實(shí)根。y=f(x)abyxISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.2區(qū)間法由此可大體確定根所在子區(qū)間，方法有：

(1)畫圖法

(2)逐步搜索法確定有根區(qū)間的方法ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.2區(qū)間法(1)畫圖法畫出y=f(x)的略圖，從而看出曲線與x軸交點(diǎn)的大致位置。也可將f(x)=0分解為1(x)=2(x)的形式，1(x)

與2(x)兩曲線交點(diǎn)的橫坐標(biāo)所在的子區(qū)間即為含根區(qū)間。 例如xlogx-1=0

可以改寫為logx=1/x

畫出對(duì)數(shù)曲線y=logx,與雙曲線y=1/x,它們交點(diǎn)的橫坐標(biāo)位于區(qū)間[2,3]內(nèi)確定有根區(qū)間的方法ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.2區(qū)間法(1)畫圖法023yx確定有根區(qū)間的方法ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.2區(qū)間法(1)畫圖法y0xy=f(x)y=kf(x)確定有根區(qū)間的方法ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.2區(qū)間法y0xABa1b1a2b2(2)搜索法

對(duì)于給定的f(x),設(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),從左至右檢查f(xi)的符號(hào),如發(fā)現(xiàn)xi與端點(diǎn)x0的函數(shù)值異號(hào),則得到一個(gè)縮小的有根子區(qū)間［xi-1,xi］。確定有根區(qū)間的方法ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.2區(qū)間法例7.2.1

方程f(x)=x3-x-1=0確定其有根區(qū)間解：用試湊的方法，不難發(fā)現(xiàn)

f(0)<0f(2)>0

在區(qū)間（0，2）內(nèi)至少有一個(gè)實(shí)根設(shè)從x=0出發(fā),取h=0.5為步長向右進(jìn)行根的搜索,列表如下確定有根區(qū)間的方法ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.2區(qū)間法xf(x)00.51.01.52

–––++可以看出，在[1.0,1.5]內(nèi)必有一根確定有根區(qū)間的方法ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.2二分區(qū)間法二分法求根過程①取有根區(qū)間[a,b]之中點(diǎn),將它分為兩半,分點(diǎn)

,這樣就可得縮小有根區(qū)間ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.2二分區(qū)間法②對(duì)壓縮了的有根區(qū)間施行同樣的手法,

即取中點(diǎn),將區(qū)間再分為兩半,然后再確定有根區(qū)間,其長度是的二分之一。

ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.2二分區(qū)間法

③如此反復(fù)下去,若不出現(xiàn),即可得出一系列有根區(qū)間序列：上述每個(gè)區(qū)間都是前一個(gè)區(qū)間的一半,因此的長度

當(dāng)k→∞時(shí)趨于零,這些區(qū)間最終收斂于一點(diǎn)x*即為所求的根。ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.2二分區(qū)間法

每次二分后,取有根區(qū)間的中點(diǎn)作為根的近似值，得到一個(gè)近似根的序列該序列以根x*為極限只要二分足夠多次(即k足夠大),便有這里ε為給定精度,由于,則ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.2二分區(qū)間法ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.2二分區(qū)間法當(dāng)給定精度ε＞0后,要想成立,只要取k滿足即可，亦即當(dāng):

時(shí),做到第K+1次二分,計(jì)算得到的就是滿足精度要求的近似根。

ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis二分區(qū)間法算法實(shí)現(xiàn)ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis

例7.2.2證明方程在區(qū)間[2,3]內(nèi)有一個(gè)根,使用二分法求誤差不超過0.5×10-3的根要二分多少次？證明令且f(x)在[2,3]上連續(xù),故方程f(x)=0在[2,3]內(nèi)至少有一個(gè)根。又當(dāng)時(shí)時(shí)，,故f(x)在[2,3]上是單調(diào)遞增函數(shù),從而f(x)在[2,3]上有且僅有一根。

給定誤差限＝0.5×10-3,使用二分法時(shí)ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.2二分區(qū)間法誤差限為只要取k滿足

即可，亦即所以需二分10次便可達(dá)到要求。

ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.2二分區(qū)間法二分法的優(yōu)點(diǎn)不管有根區(qū)間多大,總能求出滿足精度要求的根,且對(duì)函數(shù)f(x)的要求不高,只要連續(xù)即可,計(jì)算亦簡(jiǎn)單;二分法的局限性只能用于求函數(shù)的實(shí)根,不能用于求復(fù)根及偶數(shù)重根,它的收斂速度與比值為的等比級(jí)數(shù)相同。ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis

例7.2.3

求方程f(x)=x

3–e-x=0的一個(gè)實(shí)根。

因?yàn)閒(0)<0,f(1)>0。故f(x)在(0,1)內(nèi)有根用二分法解之，(a,b）=（0,1)’計(jì)算結(jié)果如表：k

ak

bk

xk

f(xk)符號(hào) 0 0 1 0.5000 － 1 0.5000 － 0.7500－ 2 0.7500 － 0.8750 ＋ 3 － 0.8750 0.8125 ＋ 4 － 0.8125 0.7812 ＋ 5 － 0.7812 0.7656 － 6 0.7656 － 0.7734 ＋ 7 － 0.7734 0.7695 － 80.7695－ 0.7714 － 9 0.7714 － 0.7724 － 10 0.7724 － 0.7729 ＋

取x10=0.7729，誤差為|x*-x10|<=1/211。ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.3迭代法及其加速為求解非線性方程f(x)=0的根，先將其寫成便于迭代的等價(jià)方程其中為x的連續(xù)函數(shù)迭代法的基本思想如果數(shù)使f(x*)=0,則也有,反之,若

,則也有,稱為迭代函數(shù)，而稱x*

為的不動(dòng)點(diǎn)。

ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.3迭代法及其加速任取一個(gè)初值,代入式的右端,得到

再將代入式的右端,得到,依此類推,得到一個(gè)數(shù)列…，其一般表示稱為求解非線性方程的簡(jiǎn)單迭代法。

ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.3迭代法及其加速如果由迭代格式產(chǎn)生的序列收斂,即

則稱迭代法收斂。ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.3迭代法及其加速

實(shí)際計(jì)算中當(dāng)然不可能也沒必要無窮多步地做下去,對(duì)預(yù)先給定的精度要求ε，只要某個(gè)k滿足即可結(jié)束計(jì)算并取ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.3迭代法及其加速例7.3.1

用迭代法求方程在x=1.5附近的一個(gè)根解將方程改寫成如下兩種等價(jià)形式

相應(yīng)地可得到兩個(gè)迭代公式ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.3迭代法及其加速如果取初始值＝1.5，用上述兩個(gè)迭代公式分別迭代，計(jì)算結(jié)果為ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.3迭代法及其加速迭代法的幾何意義

通常將方程f(x)=0化為與它同解的方程的方法不止一種,有的收斂,有的不收斂,這取決于的性態(tài)。方程的求根問題在幾何上就是確定曲線

與直線y=x的交點(diǎn)P*的橫坐標(biāo)。

ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.3迭代法及其加速

迭代法的幾何意義

ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.3迭代法及其加速

迭代法的幾何意義

ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.3迭代法及其加速迭代法的收斂性

對(duì)方程f(x)=0可以構(gòu)造不同的迭代公式,但迭代公式并非總是收斂。那么,當(dāng)?shù)瘮?shù)滿足什么條件時(shí)，相應(yīng)的迭代公式才收斂呢？ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis定理7.3.1

設(shè)函數(shù)在[a,b]上有連續(xù)的一階導(dǎo)數(shù),且滿足

（1）對(duì)所有的x∈[a,b]有

∈[a,b](映內(nèi))

（2）存在

0<L<1,使所有的x∈[a,b]有

≤

L

（壓縮性）則方程在[a,b]上的解存在且唯一，對(duì)任意的初值∈[a,b]，迭代過程均收斂于。并有誤差估計(jì)式

①

②

ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis由連續(xù)函數(shù)介值定理知,必有∈[a,b],使所以有解存在,即假設(shè)有兩個(gè)解和,,∈[a,b]，則

，由微分中值定理有

其中ξ是介于x*和之間的點(diǎn)

從而有ξ∈[a,b]，進(jìn)而有

由條件(2)有

<1,所以-=0，即=，解唯一。證:構(gòu)造函數(shù),由條件①對(duì)任意的x∈[a,b]

∈[a,b]有ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis按迭代過程,有

由于L<1,所以有,可見L越小,收斂越快再證誤差估計(jì)式①

②ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis∵

∴

即

①

得證。

即

②

得證。

ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis

迭代法的算法框圖ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.3迭代法及其加速例7.3.2

對(duì)方程,構(gòu)造收斂的迭代格式,

求其最小正根。解容易判斷[1,2]是方程的有根區(qū)間,且在此區(qū)間內(nèi),所以此方程在區(qū)間[1,2]有且僅有一根。將原方程改寫成以下兩種等價(jià)形式

ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.3迭代法及其加速①

,即

不滿足收斂條件。②,即此時(shí)迭代公式滿足迭代收斂條件。ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.3迭代法及其加速迭代法的局部收斂性定理7.3.2

設(shè)在的根的鄰域中有連續(xù)的一階導(dǎo)數(shù),且則迭代過程具有局部收斂性。定義（局部收斂性）

如果存在x*的某個(gè)鄰域，當(dāng)初值x0屬于此鄰域時(shí)，迭代過程收斂，則稱此迭代過程具有局部收斂性。ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.3迭代法及其加速證明:由于,存在充分小鄰域△:,使成立這里L(fēng)為某個(gè)定數(shù),根據(jù)微分中值定理由于,又當(dāng)時(shí),故有由定理7.3.1知對(duì)于任意的都收斂ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis例7.3.3

設(shè),要使迭代過程局部收斂到,求的取值范圍。解：

由在根鄰域具有局部收斂性時(shí),收斂條件

所以

ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis例7.3.4

已知方程在內(nèi)有根,且在上滿足,利用構(gòu)造一個(gè)迭代函數(shù),使局部收斂于。解:由可得,

故

,迭代公式局部收斂ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.3迭代法及其加速定義設(shè)迭代過程收斂于的根,記迭代誤差若存在常數(shù)p（p≥1）和c（c>0），使

迭代法的收斂速度則稱序列是p階收斂的,c稱漸近誤差常數(shù)。特別地,p=1時(shí)稱為線性收斂,p=2時(shí)稱為平方收斂。1<p<2時(shí)稱為超線性收斂。ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.3迭代法及其加速數(shù)p的大小反映了迭代法收斂的速度的快慢，p愈大，則收斂的速度愈快，故迭代法的收斂階是對(duì)迭代法收斂速度的一種度量。

ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis定理7.3.3

設(shè)迭代過程,若在所求根的鄰域連續(xù)且

則迭代過程在鄰域是p階收斂的。證:由于即在鄰域

,所以有局部收斂性,將在處泰勒展開

根據(jù)已知條件得由迭代公式及有ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.3迭代法及其加速例7.3.5

已知迭代公式收斂于證明該迭代公式平方收斂。證:迭代公式相應(yīng)的迭代函數(shù)為根據(jù)定理7.3.3可知，迭代公式平方收斂。ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.4牛頓(Newton)迭代法

用迭代法可逐步精確方程根的近似值，但必須要找到的等價(jià)方程,如果選得不合適,不僅影響收斂速度,而且有可能造成迭代格式發(fā)散。能否找到一種迭代格式,既結(jié)構(gòu)簡(jiǎn)單,收斂速度快,又不存在發(fā)散的問題。這就是本節(jié)要介紹的牛頓迭代法.ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.4牛頓(Newton)迭代法牛頓迭代法的基本思想牛頓迭代法一種重要和常用的迭代法,它的基本思想是將非線性函數(shù)f(x)逐步線性化,從而將非線性方程f(x)=0近似地轉(zhuǎn)化為線性方程求解。對(duì)于方程,設(shè)其近似根為,函數(shù)f(x)可在附近作泰勒展開

ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.4牛頓(Newton)迭代法忽略高次項(xiàng),用其線性部分作為函數(shù)f(x)的近似，設(shè)的根,則有,即可得牛頓迭代公式ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.4牛頓(Newton)迭代法牛頓迭代法的幾何意義

方程f(x)=0的根x*是曲線y=f(x)與x軸交點(diǎn)的橫坐標(biāo),設(shè)xk是根x*的某個(gè)近似值,過曲線y=f(x)的橫坐標(biāo)為xk的點(diǎn)Pk=(xk,f(xk))引切線交x軸于xk+1,并將其作為x*新的近似值,重復(fù)上述過程,可見一次次用切線方程來求解方程f(x)=0的根,所以亦稱為牛頓切線法。ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.4牛頓(Newton)迭代法牛頓迭代法的收斂性定理7.4.1

設(shè)是方程的單根,且f(x)在的某鄰域內(nèi)有連續(xù)的二階導(dǎo)數(shù),則牛頓法在附近局部收斂,且至少二階收斂,有

ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.4牛頓(Newton)迭代法證:牛頓迭代公式對(duì)應(yīng)的迭代函數(shù)為

若是方程的單根,則有,

從而由定理7.3.2知,牛頓迭代法在附近局部收斂。又由定理7.3.3知,迭代公式至少具有二階收斂速度。ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.4牛頓(Newton)迭代法利用泰勒公式ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.4牛頓(Newton)迭代法所以證畢ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysisyx0B=x0f′′(x)>0xn+1X*ayx0Bf′′(x)>0a=x0yx0B=x0f′′(x)<0ayx0Bf′′(x)<0a=x0牛頓迭代法的收斂性ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.4牛頓(Newton)迭代法

牛頓迭代法對(duì)初值x0的選取要求比較高。x0必須充分靠近x*才能保證局部收斂。定理7.4.2

如果在有根區(qū)間［a,b］上連續(xù)且不變號(hào)，在［a,b］上取初始近似根x0滿足，則牛頓迭代法產(chǎn)生的迭代序列單調(diào)收斂于方程f(x)=0在該區(qū)間上的唯一解。ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis結(jié)論：Newton法的收斂性依賴于x0

的選取。x*x0x0x0不滿足迭代條件時(shí)，可能導(dǎo)致迭代值遠(yuǎn)離根的情況而找不到根或死循環(huán)的情況ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis

牛頓迭代法的算法實(shí)現(xiàn)ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis

牛頓法的優(yōu)點(diǎn)

牛頓法是目前求解非線性方程(組)的主要方法至少二階局部收斂，收斂速度較快，特別是當(dāng)?shù)c(diǎn)充分靠近精確解時(shí)?？汕笾馗蛷?fù)根。

牛頓的缺點(diǎn)

對(duì)重根收斂速度較慢（線性收斂）

對(duì)初值的選取很敏感，要求初值相當(dāng)接近真解在實(shí)際計(jì)算中，可以先用其它方法獲得真解的一個(gè)粗糙近似，然后再用牛頓法求解。ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.5弦截法牛頓迭代法雖然具有收斂速度快的優(yōu)點(diǎn)，但每迭代一次都要計(jì)算導(dǎo)數(shù),當(dāng)比較復(fù)雜時(shí),不僅每次計(jì)算帶來很多不便，而且還可能十分麻煩，如果用不計(jì)算導(dǎo)數(shù)的迭代方法，往往只有線性收斂的速度。本節(jié)介紹的弦截法便是一種不必進(jìn)行導(dǎo)數(shù)運(yùn)算的求根方法。ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.5弦截法

弦截法在迭代過程中不僅用到前一步處的函數(shù)值，而且還使用處的函數(shù)值來構(gòu)造迭代函數(shù)，這樣做能提高迭代的收斂速度。稱之為多點(diǎn)迭代法。ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.5弦截法弦截法的基本思想為避免計(jì)算函數(shù)的導(dǎo)數(shù)，使用差商替代牛頓公式中的導(dǎo)數(shù),便得到迭代公式

稱為弦截迭代公式，相應(yīng)的迭代法稱為弦截法。ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.5弦截法弦截法的幾何意義

弦截法也稱割線法,其幾何意義是用過曲線上兩點(diǎn)、的割線來代替曲線,用割線與x軸交點(diǎn)的橫座標(biāo)作為方程的近似根再過P1點(diǎn)和點(diǎn)作割線求出,再過P2點(diǎn)和點(diǎn)作割線求出,余此類推，當(dāng)收斂時(shí)可求出滿足精度要求的ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.5弦截法可以證明，弦截法具有超線性收斂，收斂的階約為1.618，它與前面介紹的一般迭代法一樣都是線性化方法，但也有區(qū)別。即一般迭代法在計(jì)算時(shí)只用到前一步的值，故稱之為單點(diǎn)迭代法；而弦截法在求時(shí)要用到前兩步的結(jié)果和，使用這種方法必須給出兩個(gè)初始近似根，這種方法稱為多點(diǎn)迭代法。

ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis弦截法算法實(shí)現(xiàn)

ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.5弦截法例7.5.1

用弦截法求方程在初始值鄰近的一個(gè)根。要求解：取,,令利用弦截迭代公式易見取近似根可滿足精度要求。ISCM2007,BeijingChina/87鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§7.5解非線性方程組的迭代解法考慮非線性方程組在點(diǎn)(x0,y0)作二元Taylor展開，并取線性部分ISCM2007,BeijingChina