第7章非線性方程得數值解法li

第7章

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

方程求根與二分法

7.1.1

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

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

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

例1求方程的有根區間.

解根據有根區間定義，對的根進行搜索計算，結果如下：

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

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

7.1.2

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

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

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

例2求方程

在區間內的一個實根，要求準確到小數點后第2位.

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

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

步驟1準備計算在有根區間端點處的值

步驟2二分計算在區間中點處的值

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

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

不動點迭代法及其收斂性

7.2.1

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

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

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

例3求方程

（2.3）在附近的根

解設將方程（2.3）改寫成下列形式

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

7.2.2

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

定理1設滿足以下兩個條件：

1.對任意有

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

證明先證不動點存在性.

23再證唯一性.

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

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

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

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

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

7.2.3

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

定義1設有不動點，如果存在的某個鄰域對任意，迭代（2.2）產生的序列且收斂到，則稱迭代法（2.2）局部收斂.通常稱為全局收斂性.

（2.2）29

證明由連續函數的性質，存在的某個鄰域使對于任意成立

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

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

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

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

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

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

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

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

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

37

7.3

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

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

牛頓法

7.4.1

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

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

例7用牛頓法解方程

（4.4）

解這里牛頓公式為

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

步驟1準備選定初始近似值，計算

步驟2迭代按公式

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

步驟4修改如果迭代次數達到預先指定的次數，

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

一般可取或者，則方法失敗；否則以代替轉步驟2繼續迭代.4849

7.4.2

簡化牛頓法與牛頓下山法牛頓法的優點是收斂快，缺點一是每步迭代要計算及，計算量較大且有時計算較困難，為克服這兩個缺點，通常可用下述方法.

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

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

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

，它不滿足條件（4.11）.

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

（4.11）5657587.5

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

7.5.1

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

例10用弦截法解方程

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

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

7.5.2

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

例11用拋物線法求解方程

解設用表7-10的前三個值

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

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

7.6.1

求根問題的敏感性與病態代數方程方程求根的敏感性與函數求值是相反的，若，則由求的病態性與由求的病態性相反，光滑函數在根

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

例12

多項式

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

7.6.2

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

例13

求的全部零點.

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

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

7.7.1

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

例14

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

解

當時無解.當時有唯一解當時有兩個解.及

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

7.7.2

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