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

數值分析

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

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

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

NumericalAnalysis§7.1引言在科學研究和工程設計中,經常會遇到的一大類問題是非線性方程

f(x)=0

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

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

NumericalAnalysis§7.1引言

當f(x)不是x的線性函數時，稱對應的函數方程

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

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

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

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

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

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

ISCM2007,BeijingChina/87鄭州大學研究生2014-2015學年課程數值分析

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

NumericalAnalysis§7.1引言數值解法的三個步驟

①

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

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

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

f(x)=0。定理2

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

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

f(x)=0。定理3

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

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

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

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

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

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

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

適用范圍求有根區(qū)間內的奇數重實根

數學原理：介值定理設

f(x)

在[a,b]

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

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

(a,b)

內至少存在一點

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

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

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

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

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

(1)畫圖法

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

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

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

可以改寫為logx=1/x

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

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

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

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

對于給定的f(x),設有根區(qū)間為[A,B],從x0=A出發(fā),以步長h=(B-A)/n(n是正整數),在[A,B]內取定節(jié)點:xi=x0＋ih(i=0,1,2,…,n),從左至右檢查f(xi)的符號,如發(fā)現xi與端點x0的函數值異號,則得到一個縮小的有根子區(qū)間［xi-1,xi］。確定有根區(qū)間的方法ISCM2007,BeijingChina/87鄭州大學研究生2014-2015學年課程數值分析

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

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

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

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

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

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

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

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

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

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

ISCM2007,BeijingChina/87鄭州大學研究生2014-2015學年課程數值分析

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

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

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

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

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

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

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

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

ISCM2007,BeijingChina/87鄭州大學研究生2014-2015學年課程數值分析

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

NumericalAnalysis

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

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

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

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

ISCM2007,BeijingChina/87鄭州大學研究生2014-2015學年課程數值分析

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

NumericalAnalysis

例7.2.3

求方程f(x)=x

3–e-x=0的一個實根。

因為f(0)<0,f(1)>0。故f(x)在(0,1)內有根用二分法解之，(a,b）=（0,1)’計算結果如表：k

ak

bk

xk

f(xk)符號 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鄭州大學研究生2014-2015學年課程數值分析

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

,則也有,稱為迭代函數，而稱x*

為的不動點。

ISCM2007,BeijingChina/87鄭州大學研究生2014-2015學年課程數值分析

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

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

ISCM2007,BeijingChina/87鄭州大學研究生2014-2015學年課程數值分析

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

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

NumericalAnalysis§7.3迭代法及其加速

實際計算中當然不可能也沒必要無窮多步地做下去,對預先給定的精度要求ε，只要某個k滿足即可結束計算并取ISCM2007,BeijingChina/87鄭州大學研究生2014-2015學年課程數值分析

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

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

相應地可得到兩個迭代公式ISCM2007,BeijingChina/87鄭州大學研究生2014-2015學年課程數值分析

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

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

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

與直線y=x的交點P*的橫坐標。

ISCM2007,BeijingChina/87鄭州大學研究生2014-2015學年課程數值分析

NumericalAnalysis§7.3迭代法及其加速

迭代法的幾何意義

ISCM2007,BeijingChina/87鄭州大學研究生2014-2015學年課程數值分析

NumericalAnalysis§7.3迭代法及其加速

迭代法的幾何意義

ISCM2007,BeijingChina/87鄭州大學研究生2014-2015學年課程數值分析

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

對方程f(x)=0可以構造不同的迭代公式,但迭代公式并非總是收斂。那么,當迭代函數滿足什么條件時，相應的迭代公式才收斂呢？ISCM2007,BeijingChina/87鄭州大學研究生2014-2015學年課程數值分析

NumericalAnalysis定理7.3.1

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

（1）對所有的x∈[a,b]有

∈[a,b](映內)

（2）存在

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

≤

L

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

①

②

ISCM2007,BeijingChina/87鄭州大學研究生2014-2015學年課程數值分析

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

，由微分中值定理有

其中ξ是介于x*和之間的點

從而有ξ∈[a,b]，進而有

由條件(2)有

<1,所以-=0，即=，解唯一。證:構造函數,由條件①對任意的x∈[a,b]

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

NumericalAnalysis按迭代過程,有

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

②ISCM2007,BeijingChina/87鄭州大學研究生2014-2015學年課程數值分析

NumericalAnalysis∵

∴

即

①

得證。

即

②

得證。

ISCM2007,BeijingChina/87鄭州大學研究生2014-2015學年課程數值分析

NumericalAnalysis

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

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

對方程,構造收斂的迭代格式,

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

ISCM2007,BeijingChina/87鄭州大學研究生2014-2015學年課程數值分析

NumericalAnalysis§7.3迭代法及其加速①

,即

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

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

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

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

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

NumericalAnalysis例7.3.3

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

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

所以

ISCM2007,BeijingChina/87鄭州大學研究生2014-2015學年課程數值分析

NumericalAnalysis例7.3.4

已知方程在內有根,且在上滿足,利用構造一個迭代函數,使局部收斂于。解:由可得,

故

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

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

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

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

ISCM2007,BeijingChina/87鄭州大學研究生2014-2015學年課程數值分析

NumericalAnalysis定理7.3.3

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

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

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

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

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

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

NumericalAnalysis§7.4牛頓(Newton)迭代法

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

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

ISCM2007,BeijingChina/87鄭州大學研究生2014-2015學年課程數值分析

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

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

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

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

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

ISCM2007,BeijingChina/87鄭州大學研究生2014-2015學年課程數值分析

NumericalAnalysis§7.4牛頓(Newton)迭代法證:牛頓迭代公式對應的迭代函數為

若是方程的單根,則有,

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

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

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

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

NumericalAnalysis§7.4牛頓(Newton)迭代法

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

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

NumericalAnalysis結論：Newton法的收斂性依賴于x0

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

NumericalAnalysis

牛頓迭代法的算法實現ISCM2007,BeijingChina/87鄭州大學研究生2014-2015學年課程數值分析

NumericalAnalysis

牛頓法的優(yōu)點

牛頓法是目前求解非線性方程(組)的主要方法至少二階局部收斂，收斂速度較快，特別是當迭代點充分靠近精確解時?？汕笾馗蛷透?。

牛頓的缺點

對重根收斂速度較慢（線性收斂）

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

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

NumericalAnalysis§7.5弦截法

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

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

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

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

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

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

ISCM2007,BeijingChina/87鄭州大學研究生2014-2015學年課程數值分析

NumericalAnalysis弦截法算法實現

ISCM2007,BeijingChina/87鄭州大學研究生2014-2015學年課程數值分析

NumericalAnalysis§7.5弦截法例7.5.1

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

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