第7章非線性方程得數(shù)值解法li

第7章

非線性方程與方程組的數(shù)值解法7.1方程求根與二分法7.2不動點迭代法及其收斂性7.3迭代收斂的加速方法7.4牛頓法7.5弦截法與拋物線法7.6求根問題的敏感性與多項式的零點7.7非線性方程組的數(shù)值解法17.1

方程求根與二分法

7.1.1

引言（1.1）本章主要討論求解單變量非線性方程其中也可以是無窮區(qū)間.如果實數(shù)滿足，則稱是方程(1.1)的根，或稱是的零點.2若可分解為其中為正整數(shù)，且則稱為方程(1.1)的重根，或為的重零點，時為單根.若是的重零點，且充分光滑，則如果函數(shù)是多項式函數(shù)，即（1.2）其中為實數(shù)，則稱方程(1.1)為次代數(shù)方程.3它在整個軸上有無窮多個解，若取值范圍不同，解也不同，因此討論非線性方程(1.1)的求解必須強調(diào)的定義域，即的求解區(qū)間

時的求根公式是熟知的，時的求根公式可在數(shù)學(xué)手冊中查到，但比較復(fù)雜不適合數(shù)值計算，當(dāng)時就不能用公式表示方程的根，所以時求根仍用一般的數(shù)值方法根據(jù)代數(shù)基本定理可知,次方程在復(fù)數(shù)域有且只有個根（含重根，重根為個根）.

另一類是超越方程(變量之間的關(guān)系不能用有限次加、乘、除、開方運算表示的函數(shù))，例如4迭代法要求先給出根的一個近似，若且，根據(jù)連續(xù)函數(shù)性質(zhì)可知在內(nèi)至少有一個實根，這時稱為方程(1.1)的有根區(qū)間.非線性問題一般不存在直接的求解公式，故沒有直接方法求解，都要使用迭代法.通?？赏ㄟ^逐次搜索法求得方程的有根區(qū)間.5

例1求方程的有根區(qū)間.

解根據(jù)有根區(qū)間定義，對的根進行搜索計算，結(jié)果如下：

由此可知方程的有根區(qū)間為6檢查與是否同號，如果同號，說明所求的根在的右側(cè),這時令否則必在的左側(cè)，這時令見圖7-1.

考察有根區(qū)間，取中點將它分為兩半，

7.1.2

二分法假設(shè)中點不是的零點，然后進行根的搜索.圖7-1不管出現(xiàn)哪一種情況，新的有根區(qū)間的長度僅為的一半.7對壓縮了的有根區(qū)間又可施行同樣的手續(xù)，即用中點將區(qū)間再分為兩半，然后通過根的搜索判定所求的根在的哪一側(cè)，從而又確定一個新的有根區(qū)間，其長度是的一半.如此反復(fù)二分下去，即可得出一系列有根區(qū)間其中每個區(qū)間都是前一個區(qū)間的一半，因此的長度

當(dāng)時趨于零.8就是說，如果二分過程無限地繼續(xù)下去，這些區(qū)間最終必收縮于一點，該點顯然就是所求的根.作為根的近似，則在二分過程中可以獲得一個近似根的序列

該序列必以根為極限.每次二分后，設(shè)取有根區(qū)間的中點9由于只要二分足夠多次（即充分大），便有這里為預(yù)定的精度.（1.3）10

例2求方程

在區(qū)間內(nèi)的一個實根，要求準(zhǔn)確到小數(shù)點后第2位.

解這里，而取的中點，將區(qū)間二等分，由于，即與同號，故所求的根必在右側(cè)，這時應(yīng)令，而得到新的有根區(qū)間如此反復(fù)二分下去,按誤差估計（1.3）式,欲使（1.3）只需，即只要二分6次，便能達到預(yù)定的精度.

11計算結(jié)果如表7-2.12二分法是計算機上的一種常用算法，計算步驟為：

步驟1準(zhǔn)備計算在有根區(qū)間端點處的值

步驟2二分計算在區(qū)間中點處的值

步驟3判斷若，則即是根，計算過程結(jié)束，否則檢驗.

若，則以代替，否則以代替.13此時中點即為所求近似根.誤差，反復(fù)執(zhí)行步驟2和步驟3，直到區(qū)間長度小于允許147.2

不動點迭代法及其收斂性

7.2.1

不動點與不動點迭代法(簡單迭代法)將方程f(x)=0（1.1）改寫成等價的形式（2.1）若滿足，則；反之亦然，稱為函數(shù)的一個不動點.

求的零點就等價于求的不動點.選擇一個初始近似值，將它代入(2.1)右端，即可求得（1.1）15如此反復(fù)迭代計算（2.2）稱為迭代函數(shù).如果對任何，由（2.2）得到的序列有極限則稱迭代方程(2.2)收斂，且為的不動點，故稱（2.2）為不動點迭代法.16方程的求根問題在平面上就是要確定曲線與直線的交點對于的某個近似值，在曲線上可確定一點，它以為橫坐標(biāo)，而縱坐標(biāo)則等于

就是說，迭代過程實質(zhì)上是一個逐步顯示化的過程.過引平行軸的直線，設(shè)此直線交直線于點，然后過再作平行于軸的直線，與曲線的交點上述迭代法是一種逐次逼近法，其基本思想是將隱式方程歸結(jié)為一組顯式的計算公式.17則點的橫坐標(biāo)為，圖7-2記作，縱坐標(biāo)則等于按圖7-2中箭頭所示的路徑繼續(xù)做下去.在曲線上得到點列，其橫坐標(biāo)分別為18

例3求方程

（2.3）在附近的根

解設(shè)將方程（2.3）改寫成下列形式

依公式求得的迭代值如果點列趨向于點，則相應(yīng)的迭代值收斂到所求的根據(jù)此建立迭代公式19各步迭代的結(jié)果見表7-3.這時可以認為實際上已滿足方程(2.3)，即為所求的根.如果僅取6位數(shù)字，那么結(jié)果與完全相同，（2.3）20但若采用方程（2.3）的另一種等價形式建立迭代公式仍取迭代初值，則有結(jié)果會越來越大，不可能趨于某個極限.這種不收斂的迭代過程稱作是發(fā)散的.如圖7-3.一個發(fā)散的迭代過程，縱使進行了千百次迭代，其結(jié)果也是毫無價值的.圖7-321

7.2.2

不動點的存在性與迭代法的收斂性考察在上不動點的存在唯一性.

定理1設(shè)滿足以下兩個條件：

1.對任意有

2.存在正常數(shù)，使對任意都有（2.4）則在上存在唯一的不動點從前兩圖可以發(fā)現(xiàn),曲線y=φ(x)的陡度(斜率)對迭代收斂的好壞有很大影響.22因，以下設(shè)及，若或，則不動點為或，存在性得證.定義函數(shù)顯然，由連續(xù)函數(shù)性質(zhì)可知存在,且滿足使,即即為的不動點.

證明先證不動點存在性.

23再證唯一性.

設(shè)都是的不動點，引出矛盾.故的不動點只能是唯一的.

則由(2.4)得（2.4）24（2.5）

定理2設(shè)滿足定理1中的兩個條件，則對任意，由（2.2）得到的迭代序列收斂到的不動點，并有誤差估計

證明設(shè)是在上的唯一不動點，由條件1，可知，再由（2.4）式得因，故當(dāng)時序列收斂到.（2.4）（2.2）25再證明估計式（2.5），由（2.4）有（2.6）反復(fù)遞推得于是對任意正整數(shù)有（2.5）（2.4）26在上式令，注意到即得式（2.5）.迭代過程是個極限過程.

在用迭代法實際計算時，必須按精度要求控制迭代次數(shù).原則上可以用誤差估計式（2.5）確定迭代次數(shù)，但由于它含有信息而不便于實際應(yīng)用.根據(jù)式（2.6），對任意正整數(shù)有在上式中令知（2.6）（2.5）27由此可見，只要相鄰兩次計算結(jié)果的偏差足夠小即可保證近似值具有足夠精度.28

7.2.3

局部收斂性與收斂階上面給出了迭代序列在區(qū)間上的收斂性，定理的條件有時不易檢驗，實際應(yīng)用時通常只在不動點的鄰近考察其收斂性，即局部收斂性.

定義1設(shè)有不動點，如果存在的某個鄰域?qū)θ我?，迭代?.2）產(chǎn)生的序列且收斂到，則稱迭代法（2.2）局部收斂.通常稱為全局收斂性.

（2.2）29

證明由連續(xù)函數(shù)的性質(zhì)，存在的某個鄰域使對于任意成立

定理3設(shè)為的不動點，在的某個鄰域連續(xù)，且，則迭代法（2.2）局部收斂.此外，對于任意，總有，于是依據(jù)定理2可以斷定迭代過程對于任意初值均收斂.這是因為（2.2）30討論迭代序列的收斂速度.

例4用不同方法求方程的根

解這里，可改寫為各種不同的等價形式其不動點為由此構(gòu)造不同的迭代法：31取，對上述4種迭代法，計算三步所得的結(jié)果如下表.

32從計算結(jié)果看到迭代法（1）及（2）均不收斂，且它們均不滿足定理3中的局部收斂條件.注意.迭代法（3）和（4）均滿足局部收斂條件，且迭代法（4）比（3）收斂快，因在迭代法（4）中.33

定義2設(shè)迭代過程收斂于方程的根，如果迭代誤差當(dāng)時成立下列漸近關(guān)系式則稱該迭代過程是階收斂的.特別地,時稱線性收斂，時稱超線性收斂，時稱平方收斂.34

定理4對于迭代過程，如果在所求根的鄰近連續(xù)，并且

則該迭代過程在點鄰近是階收斂的.（2.8）

證明由于，據(jù)定理3立即可以斷定迭代過程具有局部收斂性.

再將在根處做泰勒展開，利用條件（2.8），則有35注意到，因此對迭代誤差，當(dāng)時有（2.9）這表明迭代過程確實為階收斂.由上式得上述定理說明，迭代過程的收斂速度依賴于迭代函數(shù)的選取.如果當(dāng)時，則該迭代過程只可能是線性收斂.36在例4中，迭代法（3）的，故它只是線性收斂.而迭代法（4）的，而由定理4知，該迭代過程為2階收斂.

37

7.3

埃特金加速收斂方法設(shè)是根的某個近似值，用迭代公式迭代一次得

由微分中值定理，有其中介于與之間.假定改變不大，近似地取某個近似值，（3.1）則有38由于將它與（3.1）式聯(lián)立，消去未知的，由此推知在計算了及之后，可用上式右端作為的新近似，記作.若將校正值再迭代一次，又得有（3.1）39一般情形是由計算，(3.2)稱為埃特金（Aitken）(二階差分)加速方法.（3.2）記步驟如下：40可以證明它表明序列的收斂速度比的收斂速度快.參考《數(shù)值計算方法》,關(guān)治編，清華大學(xué)出版社,P529417.4

牛頓法

7.4.1

牛頓法及其收斂性設(shè)已知方程有近似根（假定)，將函數(shù)在點一階泰勒公式展開，有于是方程可近似地表示為（4.1）牛頓法是一種線性化方法，其基本思想是將非線性方程逐步歸結(jié)為某種線性方程來求解.42這是個線性方程，記其根為，則的計算公式為（4.2）這就是牛頓(Newton)法.牛頓法的幾何解釋.方程的根可解釋為曲線與的交點的橫坐標(biāo)圖7-4（圖7-4).43設(shè)是根的某個近似值，過曲線上橫坐標(biāo)為的點引切線，并將該切線與軸的交點的橫坐標(biāo)作為的新的近似值.注意到切線方程為這樣求得的值必滿足（4.1），從而就是牛頓公式（4.2）的計算結(jié)果.由于這種幾何背景，牛頓法亦稱切線法.由定理4，可以直接得到牛頓法的收斂性，（4.2）（4.1）44由于假定是的一個單根，即，則由上式知于是依據(jù)定理4可以斷定，牛頓法在根的鄰近至少是平方收斂的.

(4.2)的迭代函數(shù)為又因（4.2）45故由（2.9）可得（4.3）

例7用牛頓法解方程

（4.4）

解這里牛頓公式為

取迭代初值，迭代結(jié)果列于表7-6中.所給方程（4.4）實際上是方程的等價形式.（2.9）46牛頓法的計算步驟：

步驟1準(zhǔn)備選定初始近似值，計算

步驟2迭代按公式

迭代一次，得新的近似值，若用不動點迭代到同一精度可見牛頓法的收斂速度是很快的.要迭代17次.計算47此處是允許誤差，而其中是取絕對誤差或相對誤差的控制常數(shù)，

步驟4修改如果迭代次數(shù)達到預(yù)先指定的次數(shù)，

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

一般可取或者，則方法失??；否則以代替轉(zhuǎn)步驟2繼續(xù)迭代.4849

7.4.2

簡化牛頓法與牛頓下山法牛頓法的優(yōu)點是收斂快，缺點一是每步迭代要計算及，計算量較大且有時計算較困難，為克服這兩個缺點，通?？捎孟率龇椒?

（1）簡化牛頓法，也稱平行弦法.其迭代公式為

（4.7）迭代函數(shù)二是初始近似只在根附近才能保證收斂，如給的不合適可能不收斂.50若在根附近成立，即取則迭代法（4.7）局部收斂.在（4.7）中取，則稱為簡化牛頓法，這類方法計算量省，但只有線性收斂，其幾何意義是用平行弦與軸交點作為的近似.如圖7-5所示.圖7-5即51（2）牛頓下山法.問題的提出:牛頓法收斂性依賴初值的選取,

如果偏離所求根較遠，則牛頓法可能發(fā)散.例如，用牛頓法求方程（4.8）在附近的一個根.設(shè)取迭代初值，用牛頓法公式（4.9）計算得52迭代3次得到的結(jié)果有6位有效數(shù)字.但如果改用作為迭代初值，則依牛頓法公式（4.9）迭代一次得這個結(jié)果反而比更偏離了所求的根.問題的解決:為了防止迭代發(fā)散，對迭代過程再附加一項要求，即具有單調(diào)性：（4.10）滿足這項要求的算法稱下山法.（4.9）53將牛頓法與下山法結(jié)合起來使用，即在下山法保證函數(shù)值穩(wěn)定下降的前提下，用牛頓法加快收斂速度.具體做法：為擴大初值的選取范圍,把迭代格式寫出對的選取使得滿足迭代過程附加要求,保證函數(shù)值單調(diào)下降,即（4.11）（4.12）---(4.12)牛頓法與下山法結(jié)合稱為牛頓下山法.54下山因子的選取:從開始，逐次將減半進行試算，若用此法解方程（4.8），當(dāng)時由（4.9）求得直到能使下降條件（4.11）成立為止.

，它不滿足條件（4.11）.

通過逐次取半進行試算，當(dāng)時可求得此時有，顯然.而由計算時,均能使條件（4.11）成立.計算結(jié)果如下：（4.11）（4.9）（4.8）55即為的近似.一般情況只要能使條件（4.11）成立，則可得到，從而使收斂.

（4.11）5657587.5

弦截法與拋物線法當(dāng)函數(shù)比較復(fù)雜時，計算往往較困難，值的計算.為此可以利用已求函數(shù)值來回避導(dǎo)數(shù)還要算.用牛頓法求方程的根，每步除計算外，59

7.5.1

弦截法設(shè)是的近似根，利用構(gòu)造一次插值多項式，并用的根作為新的近似根.（5.1）由于因此有（5.2）60（5.2）可以看做將牛頓公式中的導(dǎo)數(shù)用差商取代的結(jié)果.接著討論幾何意義.曲線上橫坐標(biāo)為的點分別記為，則弦線的斜率等于差商值,（5.2）61按（5.2)式求得的實際上是弦線與軸交點的橫坐標(biāo).表7-6這種算法因此而稱為弦截法.其方程為（5.2）62而弦截法（5.2），在求時要用到前面兩步的結(jié)果，弦截法與切線法（牛頓法）都是線性化方法，但兩者有本質(zhì)的區(qū)別.切線法在計算時只用到前一步的值.因此使用這種方法必須先給出兩個開始值.

例10用弦截法解方程

解設(shè)取作為開始值，用弦截法求得的結(jié)果見表7-10，（5.2）63實際上，弦截法具有超線性的收斂性.比較例7牛頓法的計算結(jié)果可以看出，弦截法的收斂速度也是相當(dāng)快的.

定理6假設(shè)在根的鄰域內(nèi)具有二階連續(xù)導(dǎo)數(shù)，且對任意有，又初值那么當(dāng)鄰域Δ充分小時，弦截法（5.2）將按階收斂到根.這里是方程的正根.（5.2）64

7.5.2

拋物線法設(shè)已知方程的三個近似根，幾何上，這種方法的基本思想是用拋物線與軸的交點作為所求根的近似位置（圖7-7).圖7-7以這三點為節(jié)點構(gòu)造二次插值多項式，的一個零點作為新的近似根，并適當(dāng)選取這樣確定的迭代過程稱為拋物線法，亦稱密勒（Müller）法.65插值多項式有兩個零點：（5.3）式中問題是該如何確定.假定在三個近似根中，更接近所求的根.66為了保證精度，選（5.3）中較接近的一個值作為新的近似根.為此，只要取根式前的符號與的符號相同.

例11用拋物線法求解方程

解設(shè)用表7-10的前三個值

作為開始值，計算得（5.3）67故代入（5.3）式求得以上計算表明，拋物線法比弦截法收斂得更快.在一定條件下可以證明，對于拋物線法，迭代誤差有下列漸近關(guān)系式（5.3）68可見拋物線法也是超線性收斂的，其收斂的階,從（5.3）看到，即使均為實數(shù)，也可以是復(fù)數(shù)，所以拋物線法適用于求多項式的實根和復(fù)根.收斂速度比弦截法更接近于牛頓法.（5.3）697.6

求根問題的敏感性與多項式的零點70

7.6.1

求根問題的敏感性與病態(tài)代數(shù)方程方程求根的敏感性與函數(shù)求值是相反的，若，則由求的病態(tài)性與由求的病態(tài)性相反，光滑函數(shù)在根

附近函數(shù)絕對誤差與自變量誤差之比若，則求根為反問題，即輸入滿足若找到一個使,則解的誤差與之比為，即誤差將達到，如果非常小，這個值就非常大，直觀的可用圖7-8表示.71圖7-872對多項式方程若系數(shù)有微小擾動其根變化很大，這種根對系數(shù)變化的敏感性成為病態(tài)的代數(shù)方程.若多項式的系數(shù)有微小變化，可表示為其中是一個多項式，次數(shù)不大于的零點表示為，令為的零點，即，將（6.2）對求導(dǎo)，可得（6.1）（6.2）73于是當(dāng)時有當(dāng)充分小時，利用在處的泰勒展開得它表明系數(shù)有微小變化時引起根變化的情況.當(dāng)很大時代數(shù)方程（6.1）就是病態(tài)的.（6.3）（6.4）74

例12

多項式

解取的根由（6.4）可得實際上，方程的根分別為這說明方程是嚴重病態(tài)的.75

7.6.2

多項式的零點很多問題要求多項式的全部零點，即方程（6.1）的全部根，它等價于求的全部根.前面討論的任一種方法都可用于求出一個根，但通常使用牛頓法最好，可利用秦九韶算法計算及的值.（6.5）76再求的一個根，,如此反復(fù)直到求出全部個根.由牛頓法計算到，則得到.由于，即，將的次數(shù)降低一階.一般地，，這里為二次多項式，在此過程中當(dāng)增加時不精確性也增加，為了解決此困難可通過原方程的牛頓法改進的結(jié)果.77由于可能是復(fù)根，因此使用拋物線法對求復(fù)根更有利.若為復(fù)根，記，則也是一個根，于是是的一個二次因子，于是是階多項式，可降低二階.即使不是復(fù)根，也可通過拋物線法求出兩個實根，它比牛頓法更優(yōu)越.78

例13

求的全部零點.

解先用拋物線法求方程的根，取計算到為止.結(jié)果見表7-11.79求得根為，從而可得再由可求得另外兩根為可對原方程，以此兩根為初值，用牛頓法迭代一次可得到更精確的根80令一種求多項式零點的方法是將其轉(zhuǎn)化為求矩陣的特征值問題.由于方程（6.5）是矩陣的特征多項式，利用計算矩陣特征值方法求矩陣的全部特征值，則可得到方程（6.5)的全部根，MATLAB中的roots函數(shù)使用的就是這種方法.此外還有專門針對求多項式全部零點的專門方法.817.7

非線性方程組的數(shù)值解法82考慮方程組（7.1）其中均為的多元函數(shù).用向量記號記,（7.2）(7.1）就可寫成

7.7.1

非線性方程組83的非線性函數(shù)時，稱方程組（7.1）為非線性方程組.當(dāng)，且中至少有一個是自變量

例14

求平面上兩條拋物線及的交點，這就是方程組（7.1)中的情形.

解

當(dāng)時無解.當(dāng)時有唯一解當(dāng)時有兩個解.及

當(dāng)時有4個解84求方程組（7.1）的根可直接將單個方程的求根方法加以推廣，實際上只要把單變量函數(shù)看成向量函數(shù)，將方程(7.1）改寫為方程組(7.2)，就可將前面討論的求根方法用于求方程組（7.2）的根.為此設(shè)向量函數(shù)定義在區(qū)域若，則稱在連續(xù)，這意味著對任意實數(shù)，存在實數(shù)，使得對滿足的，有如果在上每點都連續(xù)，則稱在域上連續(xù).85向量函數(shù)的導(dǎo)數(shù)稱為的雅可比矩陣，它表示為（7.3）86

7.7.2

多變量方程的不動點迭代法為了求解方程組（7.2），可將它改寫為便于迭代的形式（7.4）其中向量函數(shù)，且在定義域上連續(xù)，如果，滿足，稱為函數(shù)的不動點，也就是方程組（7.2）的一個解.根據(jù)（7.4）構(gòu)造的迭代法稱為不動點迭代法，稱為迭代函數(shù).（7.5）87如果由它產(chǎn)生的向量序列滿足，對（7.5）取極限，由的連續(xù)性可得，故是的不動點，也就是方程組（7.2）