數(shù)值分析課件非線性方程組的求解

數(shù)值分析課件非線性方程組的求解第一頁，共六十四頁，2022年，8月28日預(yù)備知識

滿足函數(shù)方程f(x)=0的x稱為方程(1)的根，或稱為函數(shù)f(x)的零點。如果函數(shù)(x)可分解為

(x)=(xs)mg(x)且g(s)0,則稱s是(x)的m重零點或(x)=0的m重根。當(dāng)m=1時，稱s是(x)的單根或單零點。定理假設(shè)函數(shù)y=f(x)在x=s的某一鄰域內(nèi)充分可微，則s是方程f(x)=0的m重根的充分必要條件是第二頁，共六十四頁，2022年，8月28日求解非線性方程的根的問題可分為下面幾個方面：

根的存在性根的隔離根的精確化

非線性方程根的存在性非常復(fù)雜。

對于代數(shù)方程即多項式方程，其根的個數(shù)與代數(shù)方程的次數(shù)相同。而且理論上已證明，對于次數(shù)n<=4的多項式方程,它的根可以用公式表示,而次數(shù)大于5的多項式方程,它的根一般不能用解析表達(dá)式表達(dá)。示.

對于超越方程或其他非線性方程，可能沒有零點，也可能有一個或若干個零點，甚至無窮多個零點。第三頁，共六十四頁，2022年，8月28日根的存在性定理

定理1.(根的存在定理)假設(shè)函數(shù)y=f(x)Ca,b,且f(a)·f(b)<0,則至少存在一點x(a,b)使得f(x)=0.

(并稱區(qū)間(a,b)為有根區(qū)間).

定理2.（根的唯一性）

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

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

f(x)=0

第四頁，共六十四頁，2022年，8月28日根的隔離求根的隔離區(qū)間的兩種方法

畫圖法

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

例如xlgx–1=0可以改寫為lgx=1/x畫出對數(shù)曲線y=lgx,與雙曲線y=1/x,它們交點的橫坐標(biāo)位于區(qū)間[2,3]內(nèi)第五頁，共六十四頁，2022年，8月28日023yx畫圖法第六頁，共六十四頁，2022年，8月28日逐步搜索法

對于給定的f(x)，設(shè)有根區(qū)間為[A,B]，從x0=A

出發(fā)，以步長h=(B-A)/n(n是正整數(shù))，在[A,B]內(nèi)取定節(jié)點：xi=x0＋ih(i=0，1，2，…，n)，從左至右檢查f(xi)的符號，如發(fā)現(xiàn)xi與端點x0

的函數(shù)值異號，則得到一個縮小的有根子區(qū)間［xi-1,xi］。用逐步搜索法進(jìn)行實根隔離的關(guān)鍵是選取步長h要選擇適當(dāng)h，使之既能把根隔離開來，工作量又不太大。

逐步搜索法第七頁，共六十四頁，2022年，8月28日二分法Bisection

在方程求根的方法中，最直觀、最簡單的方法就是二分法。

給定方程f(x)=0,設(shè)f(x)在區(qū)間[a,b]連續(xù),且f(a)f(b)<0,則方程f(x)在(a,b)內(nèi)至少有一根,為便于討論,不妨設(shè)方程f(x)=0在(a,b)內(nèi)只有一個(重根視為一個)實根。

二分法的基本思想

用對分區(qū)間的方法，通過判別函數(shù)f(x)在每個對分區(qū)間中點的符號，逐步將有根區(qū)間縮小，最終求得一個具有相當(dāng)精確程度的近似根第八頁，共六十四頁，2022年，8月28日二分法詳細(xì)步驟

第九頁，共六十四頁，2022年，8月28日第十頁，共六十四頁，2022年，8月28日二分法終止的條件如下條件終止，可否？這不能保證精確值的精度！xx*第十一頁，共六十四頁，2022年，8月28日有如下估計因此終止的條件為

二分法終止的條件對于給定的精度,可估計二分法所需的步數(shù)k：第十二頁，共六十四頁，2022年，8月28日二分法的優(yōu)缺點

優(yōu)點

計算簡單，方法可靠，并保證收斂

對函數(shù)要求不高，只要連續(xù)即可。

缺點

無法求復(fù)根和偶重根收斂慢調(diào)用一次求解一個[a,b]間的多個根無法求得

一般求方程的近似根，不大單獨使用，常用來為其它方法求方程近似根提供好的初值。方程求根最常用的方法是迭代法。第十三頁，共六十四頁，2022年，8月28日functiony=erfen(fun,a,b,esp)Matlabprogramiffeval(fun,a)*feval(fun,b)<0n=1;c=(a+b)/2;while(b-a)>espiffeval(fun,a)*feval(fun,c)<0b=c;c=(a+b)/2;elseiffeval(fun,c)*feval(fun,b)<0a=c;c=(a+b)/2;elsey=c;endn=n+1;endy=c;elseiffeval(fun,a)==0y=a;elseiffeval(fun,b)==0y=b;end第十四頁，共六十四頁，2022年，8月28日第十五頁，共六十四頁，2022年，8月28日不動點迭代法

迭代法的基本思想是一種逐次逼近的方法，首先給定一個粗糙的初值，然后用同一個迭代公式，反復(fù)校正這個初值，直到滿足預(yù)先給出的精度要求。迭代法的基本步驟f(x)=0等價變換f(x)的根x=(x)(x)的不動點第十六頁，共六十四頁，2022年，8月28日從一個初值

x0出發(fā)，計算

x1=

(x0),x2=(x1),…,xk+1=(xk),…

若收斂，即存在x*使得

，且連續(xù)，則由可知

x*=(x*)，即x*是的不動點，也就是f

的根。不動點迭代法定義：迭代公式xk+1=

(xk)(k=0,1,…)被稱為求解方程f(x)=0的不動點迭代法，其中

(x)稱為迭代函數(shù)。

第十七頁，共六十四頁，2022年，8月28日迭代法的幾何含義yxyy=xsy=g(x)x0p0x1p1第十八頁，共六十四頁，2022年，8月28日需要討論的問題

首先期望每個xk都在(x)的定義域上,保持有界而且收斂到精確解;如何選取適合的迭代函數(shù)(x);迭代函數(shù)(x)迭代滿足什么條件,迭代序列收斂到精確解,收斂速度如何;

H

第十九頁，共六十四頁，2022年，8月28日

設(shè)將原方程改寫成下列形式據(jù)此建立迭代公式

但若采用方程另一種等價形式建立迭代公式第二十頁，共六十四頁，2022年，8月28日第二種方法仍取迭代初值，則有結(jié)果會越來越大，不可能趨于某個極限.第二十一頁，共六十四頁，2022年，8月28日

迭代法的收斂條件定理第二十二頁，共六十四頁，2022年，8月28日

注

條件(2)可用更強(qiáng)更便于應(yīng)用的條件代替:

由誤差估計可以得到迭代終止的條件

由誤差估計可以知道L越小，收斂越快以及迭代最少次數(shù)

第二十三頁，共六十四頁，2022年，8月28日

局部收斂性

前述定理條件為充分條件，非必要條件。在實際應(yīng)用當(dāng)中條件并不易檢驗。

定義（局部收斂性）設(shè)有不動點，如果存在的某個鄰域?qū)θ我?，迭代產(chǎn)生的序列且收斂到，則稱迭代法局部收斂.定理設(shè)s為(x)的不動點,'(x)在s的某個鄰域內(nèi)連續(xù),且|'(x*)|<1,則迭代法是局部收斂的.

本定理給出的就是局部收斂性條件。具體解題時，雖然無法判別隔根區(qū)間是否為以x*為中心的鄰域，但只要它足夠小，且在鄰域中滿足：第二十四頁，共六十四頁，2022年，8月28日xyy=xsy=g(x)x0p0x1p1xyy=xsy=g(x)x0p0x1p1xyy=xsy=g(x)x0p0x1p1xyy=xsy=g(x)x0p0x1p1

收斂性圖像說明第二十五頁，共六十四頁，2022年，8月28日用不同方法求方程的根

例這里其不動點為由此構(gòu)造不同的迭代法：可改寫為各種不同的等價形式第二十六頁，共六十四頁，2022年，8月28日

從計算結(jié)果看到迭代法（1）及（2）均不收斂，且它們均不滿足定理3中的局部收斂條件.

迭代法（3）和（4）均滿足局部收斂條件，且迭代法（4）比（3）收斂快，因在迭代法（4）中.第二十七頁，共六十四頁，2022年，8月28日functiony=iterate(x)x1=g(x);n=1;while(abs(x1–x)>=1.0e–6)&(n<=1000)x=x1;x1=g(x);

n=n+1;endx1nmatlabprogram

第二十八頁，共六十四頁，2022年，8月28日收斂階(描述收斂速度)

收斂速度（收斂速度的階）

設(shè)迭代過程收斂于方程

的根

，如果迭代誤差當(dāng)時成立下列漸近關(guān)系式則稱{xn}是p階收斂若p=1

,稱{xk}為線性收斂,這時0<C≤1。

p>1,稱{xk}為超線性收斂;

p=2,稱其為平方收斂.第二十九頁，共六十四頁，2022年，8月28日收斂階定理

數(shù)p的大小反映了迭代法的收斂速度的快慢，P越大，收斂越快，所以說收斂階是對迭代法收斂速度的一種度量。

（收斂階定理）

對于迭代過程，如果在所求根的鄰近連續(xù)，并且:則該迭代過程在點鄰近是P階收斂的。

上述定理說明，迭代過程的收斂速度依賴于迭代函數(shù)的選取.第三十頁，共六十四頁，2022年，8月28日Newton迭代法

Newton法的基本思想

將非線性方程線性化，以線性方程的解逐步逼近非線性方程的解

具體而言：

設(shè)xk是非線性方程f(x)=0的一個近似根，把f(x)在xk處作一階泰勒展開，即用前兩項近似代替則近似方程轉(zhuǎn)化為

設(shè)，上式解為第三十一頁，共六十四頁，2022年，8月28日Newton迭代法

于是方程f(x)=0的新的近似根xk+1，可得牛頓迭代公式

牛頓迭代公式為特殊的不動點迭代。

其迭代函數(shù)為

第三十二頁，共六十四頁，2022年，8月28日Newton迭代法幾何解釋

設(shè)是根的某個近似值，過曲線上橫坐標(biāo)為的點引切線，并將該切線與軸的交點的橫坐標(biāo)作為的新的近似值.

注意到切線方程為

第三十三頁，共六十四頁，2022年，8月28日牛頓法的收斂性

定理設(shè)f(x*)=0,,且在x*的鄰域上存在,連續(xù),則可得(1)Newton迭代公式在單根情況下至少2階局部收斂.(2)

定理表明，當(dāng)初值x0充分接近x*時，Newton法的收斂速度較快，但當(dāng)初值不夠好時，可能會不收斂或收斂于別的根，這可從Newton法的幾何意義看到：

第三十四頁，共六十四頁，2022年，8月28日牛頓法的計算步驟：

步驟1準(zhǔn)備選定初始近似值，計算步驟2迭代按公式迭代一次，得新的近似值

，計算步驟3控制如果滿足或，則終止迭代，以作為所求的根；否則轉(zhuǎn)步驟4.

此處是允許誤差，而

第三十五頁，共六十四頁，2022年，8月28日牛頓法的計算步驟：

其中是取絕對誤差或相對誤差的控制常數(shù)，步驟4修改或者，則方法失??；

否則以代替轉(zhuǎn)步驟2繼續(xù)迭代.如果迭代次數(shù)達(dá)到預(yù)先指定的次數(shù)，第三十六頁，共六十四頁，2022年，8月28日functiony=newton(x0)x1=x0–fc(x0)/df(x0);n=1;while(abs(x1–x0)>=1.0e–6)&(n<=100000000)x0=x1;x1=x0–fc(x0)/df(x0);n=n+1;endx1nmatlabprogram

第三十七頁，共六十四頁，2022年，8月28日計算重根的牛頓迭代法

Newton法在重根情形下的收斂階為線性階

若是方程的重根，即此時有第三十八頁，共六十四頁，2022年，8月28日牛頓法應(yīng)用舉例可導(dǎo)出求開方值的計算程序

：開方公式對于任意給定的正初值均為平方收斂。求無理數(shù)的近似值可導(dǎo)出求開方值的計算程序

第三十九頁，共六十四頁，2022年，8月28日求.取初值，對

按公式迭代3次便得到精度為的結(jié)果第四十頁，共六十四頁，2022年，8月28日牛頓迭代法的優(yōu)缺點

優(yōu)點在單根附近,牛頓迭代法具有平方收斂的速度，所以在迭代過程中只要迭代幾次就會得到很精確的解。而且能計算復(fù)根。缺點

重根情形下為局部線性收斂;

牛頓迭代法計算量比較大:因每次迭代除計算函數(shù)值外還要計算導(dǎo)數(shù)值;選定的初值要接近方程的解，否則有可能得不到收斂的結(jié)果;第四十一頁，共六十四頁，2022年，8月28日牛頓迭代法的改進(jìn)

重根情形下為局部線性收斂--------

改進(jìn)公式或加速每步都要計算導(dǎo)數(shù)值-----------簡化Newton迭代法或弦截法初值近似問題-------二分法求初值或”下山算法”重根情形的加速提速方案1:

迭代函數(shù)使用重數(shù).將迭代函數(shù)改為則迭代法為可以證明它是求m重根x*的具平方收斂的迭代格式。

第四十二頁，共六十四頁，2022年，8月28日牛頓迭代法的改進(jìn)問題是一般情況下并未知重數(shù)m.如何確定m?

令則因此可用下式估計m

第四十三頁，共六十四頁，2022年，8月28日提速方案2:將求f的重根轉(zhuǎn)化為求另一函數(shù)的單根。

構(gòu)造函數(shù)牛頓迭代法的改進(jìn)對它用牛頓法，其迭代函數(shù)為第四十四頁，共六十四頁，2022年，8月28日避免導(dǎo)數(shù)值的計算牛頓迭代法的改進(jìn)

簡化Newton迭代法第四十五頁，共六十四頁，2022年，8月28日

弦截法牛頓迭代法的改進(jìn)導(dǎo)數(shù)用差商取代，則：導(dǎo)數(shù)用差商取代，則1弦截法與牛頓法都是線性化方法，但兩者有本質(zhì)的區(qū)別.

2弦截法具有超線性的收斂性.第四十六頁，共六十四頁，2022年，8月28日

牛頓下山法牛頓迭代法的改進(jìn)

如果偏離所求根較遠(yuǎn)，則牛頓法可能發(fā)散.

為了防止迭代發(fā)散，對迭代過程再附加一項要求，即具有單調(diào)性：滿足這項要求的算法稱下山法.

將牛頓法與下山法結(jié)合起來使用，即在下山法保證函數(shù)值穩(wěn)定下降的前提下，用牛頓法加快收斂速度.

第四十七頁，共六十四頁，2022年，8月28日牛頓迭代法的改進(jìn)牛頓下山法采用以下迭代公式：其中稱為下山因子，

選擇下山因子時從開始，逐次將減半進(jìn)行試算，直到能使下降條件成立為止.

牛頓下山法只有線性收斂第四十八頁，共六十四頁，2022年，8月28日迭代過程的加速

對于收斂的迭代過程，從理論上說，只要迭代足夠多次，總可得到滿意的精度，但有時迭代過程過于緩慢，計算量極大，實際上得不到滿意的結(jié)果。因此，迭代過程的加速便成了一個重要的研究課題.加速方案一

當(dāng)?shù)瘮?shù)

(x)在不動點x*處導(dǎo)數(shù)不為零,迭代

xk+1=

(xk)僅是線性收斂.

設(shè)由迭代公式計算出迭代值，若x在x*附近變化,'(x)連續(xù),則'(x)變化不大,近似地記為常數(shù)L，則用微分中值定理，可以得到第四十九頁，共六十四頁，2022年，8月28日迭代過程的加速解出x*：

具體算法如下：把它作為xk的一種補(bǔ)償?shù)谖迨摚擦捻摚?022年，8月28日加速方案二：Atiken加速法迭代過程的加速

設(shè)由基本迭代公式計算出3個迭代值xk,xk+1,xk+2

,則把它作為xk的一種補(bǔ)償?shù)谖迨豁?，共六十四頁?022年，8月28日迭代過程的加速定理

設(shè)序列線性收斂于x*,則的Aitken序列存在,且即比更快收斂于x*.

Atiken加速法與基本迭代公式結(jié)合，即為Steffensen迭代法第五十二頁，共六十四頁，2022年，8月28日迭代過程的加速

Steffensen迭代法具體算法如下：或?qū)懗刹粍狱c迭代形式第五十三頁，共六十四頁，2022年，8月28日幾何解釋xyy=xy=g(x)sx0P(x0,x1)x1x2P(x1,x2)比x2更接近s!第五十四頁，共六十四頁，2022年，8月28日例

求方程x3

-x-1=0在區(qū)間(1,2)內(nèi)的根s.發(fā)散第五十五頁，共六十四頁，2022年，8月28日kykzkxk01.512.3750012.39651.4162921.840925.238881.3556531.491402.317281.3289541.347101.444351.3248051.325181.327141.32472計算結(jié)果

Steffensen迭代法將原不收斂的迭代法變成收斂第五十六頁，共六十四頁，2022年，8月28日解非線性方程組的牛頓迭代法

考慮方程組其中均為的多元函數(shù).令第五十七頁，共六十四頁，2022年，8月28日解非線性方程組的牛頓迭代法方程組可以表示為向量形式

F(x)=0.

只要把前面介紹的單變量函數(shù)看成向量函數(shù)

則可將單變量方程求根方法推廣到方程組.

將函數(shù)的分量在用多元函數(shù)泰勒展開，并取其線性部分，則可表示為第五十八頁，共六十四頁，2022年，8月28日解非線性方程組的牛頓迭代法令上式右端為零，得到線性方程組其中

求解線性方程組，并記解為，則得這就是解非線性方程組的牛頓迭代法.

第五十九頁，共六十四頁，2022年，