第3章非方程(組)的數值解法

1、第3章 非方程（組）的數值解法3.1 引 言在第2章中，我們已經學過線性方程組的數值解法，但是在實際問題中，常常遇到的是非線性方程（組）的求解問題，而非線性問題比線性問題復雜，因此，非線性模型常常用線性模型來近似代替；然而，在精度要求比較高的情形下，必須直接求解非線性問題。本章首先討論單個方程的求根方法，如二分法，不動點迭代法及其加速方法，牛頓迭代法及其改進方法，并討論迭代序列的收斂性，收斂速度和誤差估計等，最后簡要介紹非線性方程組的一些數值解法。定義3.1.1 對于單變量方程 (3.1.1)如果有(實數或復數)，使，則稱為方程(3.1.1)的根(root)，或函數的零點(zero point

2、). 定義3.1.2 設是整數，若函數可以寫成，且， (3.1.2)則稱為方程(3.1.1)的m重根(root of multiplicity m)或函數的m重零點(zero of multiplicity m). 特別地，當時，稱為方程(3.1.1)的單根(simple root).定理3.1.1 設在處階導數存在，則是函數的重零點的充分必要條件是，. (3.1.3)若為多項式 ,其中，為實數，則稱方程(3.1.1)為n次代數方程(algebraic equation of degree n)。根據代數基本定理，方程(3.1.1)在復數范圍內有且僅有n個根(含復根，m重根為m個根)。理論上已

3、證明，當次數, 方程的根可用求根公式表示；而當時，方程沒有一般的求根公式，通常都要用數值方法求解。若為超越函數(transcendental function)，則稱方程(3.1.1)為超越方程(transcendental equation)；如. 超越方程一般更難求得精確解，都要使用數值方法求解。高次代數方程和超越方程都屬于非線性方程(nonlinear equation)。對于非線性方程根的數值解法，主要解決以下3個問題：(1) 研究根的存在性；(2) 找出有根區(qū)間；(3) 計算根的近似值。根的存在性，主要依據以下零點定理(zero-point theorem): 定理3.1.2 (零點

4、定理) 設為上的連續(xù)函數，若有，則在區(qū)間內至少有一個實根。通常稱為有根區(qū)間。若在上還是單調函數，則在區(qū)間內僅有一個實根。如何找出有根區(qū)間，通?？捎脠D像法或逐次搜索法，具體做法是：從點出發(fā)，以為步長依次取點，如果，則區(qū)間為有根區(qū)間。在有根區(qū)間內，用適當的數值方法求出根的近似值，使其滿足一定的精度要求。3.2 求實根的二分法求根方法中最簡單直觀的方法就是二分法(Bisection Method)。計算過程如下：設為上的連續(xù)函數, 且為有根區(qū)間，取中點，如果，則是方程的根；否則，將它平均分為兩半，檢查與是否同號。若是，則根x*在右側，取, ; 否則取, ，得到新的有根區(qū)間，且 (見圖3.2.1).圖

5、3.2.1重復以上過程，取，若，則是方程的根；否則，將平均分為兩半，確定根在的哪一側，得到新的有根區(qū)間，且；如此反復二分可得一系列有根區(qū)間其中每一個區(qū)間長度都是前一個區(qū)間長度的一半，顯然，的長度為.這時，取最后一個區(qū)間的中點作為根的近似值，其誤差估計為. (3.2.1)當時，即. 對給定的精度，要使，只需令 解得. (3.2.2)由式(3.2.2)可預先確定出二分法的次數.二分法的優(yōu)點是計算過程簡單且收斂性有保證，但收斂的速度較慢，且該方法只能求實根，不能求復根或偶數重根，通?？捎糜谇笃渌玫那蟾ǖ某跏贾?。例3.2.1 求方程的實根，要求精確到小數點后第2位。解 設，則在實數域上均連續(xù)

6、，且，由零點定理知，在內至少有一個實根。又因為，所以在內有且僅有一個實根。下面從區(qū)間-3, 3開始，以1為步長，通過計算的函數值，逐步縮小方程的有根區(qū)間(表3.2.1)表3.2.1-3-2-10123-39-18-9-6-3627由表3.2.1知，方程在區(qū)間內有且僅有一個實根。記 則 取的中點，將區(qū)間二等分，由于，即與同號，此時令，得到新的有根區(qū)間；如此反復二分下去。下面估計二分的次數. 因為題目要求精確到小數點后第2位，所以可取精度，由(3.2.2)得，.取，即至多二分7次即可，計算結果見表3.2.2.表3.2.2符號01.00002.00001.500011.00001.50001.250

7、021.25001.5.001.375031.37501.50001.437541.43751.50001.468851.43751.46881.453161.45311.46881.460971.45311.46091.4570其中為方程精確到小數點后第2位的近似根。3.3 迭代法及其收斂性迭代法(Iterative Method)是用收斂于所給問題的精確解的極限過程，是一種逐步逼近精確解的數值方法。其基本思想是將方程求根問題轉化為某個函數求不動點的問題，利用不動點的迭代法求方程的近似根。3.3.1 不動點的迭代法及其收斂性將方程(3.1.1)改寫成等價形式 (3.3.1)例如，可取.定義3

8、.3.1 若數滿足，則稱為的一個不動點(fixed point).注 的不動點是方程(3.1.1)的一個根，求方程的根等價于求函數的不動點。在根的附近取一點作為的初始近似值，把代到式(3.3.1)的右端，計算得到 . 如果連續(xù)，可構造迭代公式 (3.3.2)并稱之為不動點迭代法(fixed point iterative method)，稱為迭代函數(iterative function). 由式(3.3.2)逐次迭代可得到序列，如果，則由式(3.3.2)兩端取極限，得,即為的不動點。從幾何圖像看，的不動點就是直線與曲線的交點的橫坐標.從它的某個初始近似值出發(fā)，在曲線上確定一點，引平行于軸的直

9、線，與直線交于點，其橫坐標即為，由式(3.3.2)逐次求得的，即為如圖3.3.1所示點的橫坐標。若迭代收斂，則序列將越來越逼近所求的交點的橫坐標(參見圖3.3.1)，如果迭代發(fā)散，則序列將越來越遠離所求的交點的橫坐標(圖3.3.2).圖 3.3.1圖 3.3.2迭代法主要研究以下3個問題：(1) 如何選取合適的迭代函數？(2) 迭代函數滿足什么條件時，序列才收斂？(3) 序列的收斂速度及誤差估計？例3.3.1 用迭代法求方程的實根。解 在例3.2.1中，我們使用搜索法確定有根區(qū)間，也可用圖像法來確定。曲線與直線只有一個交點，其橫坐標介于1與2之間，見圖3.3.3. 故原方程在區(qū)間內有唯一實根，

10、因此有根區(qū)間為. 將方程轉化成等價形式，迭代函數有很多種取法，例如： 圖 3.3.3，, 等等。下面僅取前兩種迭代函數進行計算，其余的讀者可作為練習。對應于迭代函數的迭代公式分別為方法1 ， (3.3.3)方法2 . (3.3.4)取區(qū)間中點作為初值，迭代結果見表3.3.1. 表3.3.1k01234567(方法1)(方法2)1.51.51.44221.31251.46051.86951.4548-0.26701.45663.00951.4560-10.62891.4562603.39401.4562-1.0984×108顯然，方法1收斂，原方程的準確值為；而方法2發(fā)散。例3.3.1

11、表明構造迭代法(3.3.2)的形式有很多種，但有的收斂，有的發(fā)散。那么，迭代函數滿足什么條件以及初值如何選取，才能使迭代序列收斂？  定理3.3.1 設迭代函數，滿足； (1) 當時，；(2) 滿足Lipschitz條件，即存在常數，使，都有, (3.3.5)則在區(qū)間上存在唯一不動點，且由式(4.3.2)生成的迭代序列對任何初值都收斂于，并有誤差估計, (3.3.6). (3.3.7)證明 首先證明不動點存在性。記，由條件(1)，得 及 .若上述2個不等式有一個等號成立，則或，即有不動點；否則必有. 因為在上連續(xù)，所以由零點定理知，必有,使，即 ,亦即是的不動點。其次證明的唯一性。若

12、都是的不動點，即，且，則由條件(3.3.5)得,矛盾！這表明，即不動點是唯一的。然后證明收斂性。即要證由式(3.3.2)生成的迭代序列收斂于的唯一不動點. 因為，所以. 再由條件(3.3.5)，得 (3.3.8)因為，所以，即.最后證明估計式(3.3.6)和(3.3.7). 因為，所以.注意到，利用上式第一個不等式，可得(3.3.6)，再利用最后一個不等式可得式(3.3.7)，證畢!注1 式(3.3.6)稱為事后估計。對給定的精度，由式(3.3.6)解得. (3.3.10)由此可知, 只要相鄰兩次計算結果的偏差足夠小, 那么就可保證近似值具有足夠的精度。實際計算過程中，常用條件來判斷迭代過程是

13、否結束。式(3.3.7)稱為先驗估計，它可用來估計達到精度所需的迭代次數k：由解得迭代次數應滿足. (3.3.11)例如，在例3.2.1中，若要求近似根的誤差不超過，只要使k滿足，將代入，得，即迭代9次即可。注2 從估計式(3.3.8)可以看出，常數L越小，收斂速度越快。 在實際應用中，要驗證函數是否滿足Lipschitz條件比較困難，因此常常采用下面的充分條件代替Lipschitz條件。推論 設 (表示在上具有一階連續(xù)導數)，若， (3.3.9)則定理3.3.1中結論成立。證明 由微分中值定理可得，對任意，有，其中介于與之間，故式(3.3.5)成立，證畢!注 若對任意，都有，只要初值，則由式

14、(3.3.2)生成的迭代序列都是發(fā)散的。事實上，因為，其中介于與之間，所以，故迭代序列發(fā)散。 例3.3.2 討論例3.3.1中，方法1及方法2中迭代序列的斂散性。解 對于方法1, 迭代函數. 在中, ,且. 而,故迭代格式(3.2.3)產生的迭代序列收斂。對于方法2，迭代函數. 在區(qū)間中，故迭代格式(3.3.4)是發(fā)散的。3.3.2 局部收斂性與收斂階很多迭代格式只在根鄰近收斂, 即初值必須取在的鄰近。若離根較遠, 所用迭代格式有可能發(fā)散, 因此有下列局部收斂性的概念：定義3.3.2 設在某區(qū)間 I上有不動點，若存在的一個鄰域，對，迭代法(3.3.2)生成的序列，且收斂于，則稱迭代序列在根附近

15、局部收斂的(locally convergent)。定理3.3.2 設為的不動點，在的鄰域連續(xù)，且，則迭代法(3.3.2)局部收斂。證明 由的連續(xù)性，存在，使，并有.因此對任意，有，故在區(qū)間上滿足定理3.3.1的推論的條件，故由式(3.3.2)生成的序列對均收斂于. 證畢!例3.3.3 構造不同迭代法求的根.解 (1) 構造迭代公式則迭代函數為. 因為,所以不滿足定理3.3.2的條件。(2) 構造迭代公式 則迭代函數為.因為, ，所以由定理3.3.2知，迭代法收斂。(3) 構造迭代公式 則迭代函數為.因為，所以由定理3.3.2知，迭代法收斂。若取，分別用上述三種迭代計算，結果見表3.3.2，.

16、 從表3.3.2看到迭代法(1)不收斂，迭代法(2)和迭代法(3)收斂，且迭代法(3)收斂最快。表 3.3.2k迭代法(1)迭代法(2)迭代法(3)022211.51.751.75221.734 751.732 14331.51.732 3611.732 051 實際應用中，一般事先不知道，故難以驗證，但如果存在在根的鄰域內，可用 來代替.為了描述序列收斂的快慢，引入收斂階的概念。一個具有實用價值的迭代法，不僅要求它收斂，而且還要求它收斂比較快。迭代收斂的速度是指迭代誤差的下降速度。在定理3.3.1中我們知道L越小收斂越快，但要準確反映收斂速度，還需要引進收斂階(order of conver

17、gence)的概念，它是衡量迭代好壞的標志之一。定義3.3.3 設序列收斂到，記誤差，若存在實數及，使, (3.3.10)則稱序列是按漸進誤差常數，階收斂到 (converges to of order p with asymptotic error constant )。特別地，當且，稱為線性收斂 (linearly convergent)。當時，稱為平方收斂 (quadratically convergent)。當時，統(tǒng)稱為超線性收斂 (superlinarly convergent)。顯然，數的大小反映了收斂速度的快慢。越大，則收斂越快。因此迭代法的收斂階是對收斂速度的一種度量。定理3.

18、3.3 設為的不動點，整數p1，在的鄰域連續(xù)，且滿足 而 (3.3.11)則由迭代法(3.3.2)產生的序列在的鄰域是階收斂的，并有. (3.3.12)證明 由于，故, 由定理3.3.3可知局部收斂，對鄰域中的初始近似值，由式(3.3.2)迭代到，將在處按Taylor展開，得,其中，介于與之間。由式(3.3.11)得即.由的連續(xù)性，上式兩邊取極限，即得式(3.3.12).特別地，(1) 當 但時，序列線性收斂；(2) 當, 但時，序列平方收斂。根據定理3.3.3的結論，例3.3.3中迭代法(3)的,而, ，故知，即該迭代序列是平方收斂的。3.3.3 迭代法加速不動點迭代式(3.2.2)通常只有

19、線性收斂，有時甚至不收斂，為了加快迭代法的收斂速度，通?？刹捎盟固胤疑铀俚?Steffensens acceleration)。設是的不動點，記，利用中值定理有介于與之間。通常依賴于，若變化不大，設，于是有 從上兩式消去C，則得 或 .解得.若記 (3.3.13)則用序列作為不動點的新的近似值序列，一般它比迭代法(3.3.2)收斂更快。迭代法(3.3.13)可改寫為下列形式 (3.3.14)稱為Steffensen迭代法(Steffensens iterative method)，它是將原不動點迭代式(3.3.2)的計算兩步合并成一步得到，可改為另一種不動點迭代格式, (3.3.15)其中

20、 (3.3.16)Steffensen迭代法具有比不動點迭代法更高的收斂速度；特別地，這種迭代方法還能使原來發(fā)散的迭代法變?yōu)槭諗康牡?。定?.3.4 若為式(3.3.16)定義的函數的不動點，則為的不動點。反之，若是的不動點，設連續(xù)，且，則是的不動點，且Steffensen迭代法(3.3.14)是平方收斂的。(證明見文獻3)。例3.3.4 試用Steffensen迭代法求方程的根的近似值。解法1 原方程變形為，此時迭代函數為，以該迭代公式形成的Steffensen迭代公式為結果見表3.3.3. 表 3.3.3k01.500001.442249571.4605260011.456132451

21、.456174241.4561611021.456164251.456164241.4561642531.456164251.456164251.45616425比較例3.3.2的結果，可知本方法收斂速度更快。事實上，原迭代法是線性收斂，現在是平方收斂的。解法2 原方程變形為，此時迭代函數為，例3.3.2曾指出，迭代公式是發(fā)散的。以該迭代公式形成的Steffensen迭代公式為結果見表3.3.4. 表 3.3.4k01.500001.312500001.8695068411.452779141.466905961.4217462621.456164291.456224541.455972473

22、1.456164251.456164251.4561642441.45616425 1.456164251.45616425此迭代法是收斂的。這表明，即使不收斂的迭代法，用Steffensen加速迭代后仍可能收斂。3.4 Newton迭代法不動點迭代法求解非線性方程近似根有2個缺點：一是選擇迭代函數，并驗證收斂性比較麻煩；二是這種迭代法一般收斂速度較慢。Newton迭代法(Newtons iterative method)采用另一種迭代格式，其基本思想就是將非線性方程近似轉化為線性方程求解，具有較快的收斂速度。Newton迭代法是求解非線性方程的一種重要而常用的迭代法。3.4.1 Newton

23、迭代法及其收斂性 設是方程的一個初始近似根，如果存在且連續(xù)，那么函數在處的一階Taylor展開式為，介于與之間。忽略余項，則得方程的在附近的線性近似 上式右端是的線性方程，若，解得，記作，即，它可作為新的近似根。重復以上過程，并假設，得 . (3.4.1)稱式(3.4.1)為Newton迭代公式(Newton iterative formula)，其迭代函數為. (3.4.5)幾何意義：求方程的根，幾何上就是求曲線與軸交點的橫坐標. 若已知的一個近似，通過點作曲線的切線，其切線方程為，該切線與x軸交點的橫坐標(令，解出)正好是，記為，即有，這就是Newton迭代公式，如圖3.4.1所示。鑒于此

24、，Newton迭代法也稱為切線法(tangent method)。圖 3.4.1例3.4.1 用Newton迭代法求方程在1.5附近的根。解 ，所以Newton迭代公式為取初值，迭代結果見表3.4.1表3.4.1k012341.51.4571428571428571.4561647462066851.4561642461360391.456164246135909可見，Newton迭代法的收斂速度很快。例3.4.2 用Newton迭代法求在附近的根。解 ，取初值，迭代結果見表3.4.2表3.4.2k012340.50.57102043980.56715556870.56714329050.56

25、71432904若取初值，迭代結果見表3.4.3.表3.4.3 k0123-1.5-13.463378-5.643480×104-Inf顯然，迭代發(fā)散。例3.4.2說明，對Newton迭代法，初值選取非常重要，選擇得好，迭代收斂且迭代速度快；反之，可能迭代發(fā)散。關于Newton迭代法的收斂性有以下的局部收斂定理：定理3.4.1 設函數在附近有二階連續(xù)導數，若是方程的一個單根，即：，但, 則Newton迭代法(3.4.1)至少是平方收斂的。 證明 由式(3.4.1)知，迭代函數. 因為，, (3.4.2)所以由定理3.3.3可知，Newton迭代法(3.4.1)至少是平方收斂的，證畢!

26、注 定理3.4.1表明Newton法收斂很快，但是對初值要求比較高，必須足夠靠近時，才能保證迭代序列局部收斂。下面給出初值在較大范圍內收斂的一個充分條件：定理3.4.2設函數，且滿足條件： (1) ; (2) 當時，； (3) 當時，不變號； (4) 任意初值，使則由Newton迭代格式(3.4.1)確定的序列收斂于在區(qū)間內唯一的根.圖 3.4.2證明 首先證明根的存在性。由條件(1)及連續(xù)，知在內至少有一根，由條件(2)知，是單調函數，因此方程在內有唯一根.然后證明收斂性。不妨設(見圖3.4.2)，由知：，所以，即 .另一方面，.上面兩式相減，得 因此，再以代替繼續(xù)上述過程，有,故序列是單調

27、減少且有下界的數列，故必有極限，記，由，知：當時，可得，由根的唯一性，知.例3.4.3 用Newton迭代法求方程在內的實根，討論收斂性，并要求.解 設，則. 當時，有，.取，有. 由定理3.4.2知：相應的Newton迭代公式,收斂。且為滿足精度要求的近似根(見表3.4.4)。表3.4.4k0123410.75036386780.73911289090.73908513340.7390851332例3.4.4 (1) 設，求平方根的過程可化為解方程. 若用Newton法求解，證明對任何初值，相應的Newton迭代公式都收斂于. (2) 求的近似值。證 (1) 對，Newton迭代公式為. (

28、3.4.3)由此可得.故對任意的，均有. 又因為所以由式(3.4.3)產生的迭代序列單調遞減且有下界，從而迭代序列的極限存在，記其極限為. 對式(3.4.3)兩邊取極限得，解得.這是在計算機上作開方運算的一個實際有效的方法，它每步迭代只做一次除法和一次加法再做一次移位即可，計算量少，收斂速度快。(2) 此時，代人式(3.4.3)， 取初值，得, , ,與的精確值相比較，是具有10位有效數字的近似值。例3.4.5（懸索垂度與張力計算）公路和鐵路設計中常出現高架懸索橋梁，由于橋梁的重量，在設計中需計算各個支撐部件所承受的張力. 設高架懸索系統(tǒng)如圖3.4.3，其中表示懸索的跨度，是懸索的垂度，是懸索

29、承受的質量。圖 3.4.3解 設懸索承受的重量是均勻分布的，表示重力加速度，則懸索承受的負荷密度為 若不計溫度變化的影響，懸索端點的張力由公式確定；為此需計算懸索垂度. 設懸索長度為，垂度近似滿足如下的非線性代數方程不妨設 則懸索的負荷密度。采用Newton迭代法求解非線性方程，取迭代初值，誤差精度開始計算，迭代到第7步，得到結果，懸索端點承受張力。由張力計算公式知：懸索的垂度越大，懸索受到的張力越小，因此可調節(jié)懸索的長度，增加懸索的垂度，減小其承受的張力. 表3.4.5顯示了對于懸索的不同長度，數值計算所得懸索的垂度及其端點所受的張力。表3.4.5L/米125130135140145150x

30、/米15.2721.9427.1931.6335.4538.75T/牛16168.512426.810922.110109.19608.69275.93.4.2 Newton迭代法求重根設為方程的m重根，由定義3.1.2及定理3.1.1知：在的某領域內可表示為 (3.4.4)其中，是正整數。且有，. Newton法的迭代函數. 因為, (3.4.5)且，所以由定理3.3.3知：Newton迭代法求重根時仍收斂，但只是線性收斂的。下面將對Newton迭代法加以改進正，使得改進的Newton迭代法求重根時是平方收斂的。若根的重數m已知，則可將Newton迭代法改寫為, (3.4.6)其迭代函數為.

31、 (3.4.7)由式(3.4.5)得,由定理3.3.3知：迭代公式(3.4.6)至少平方收斂。稱式(3.4.6)為改進的Newton迭代法(modified Newton iterative method).若根的重數m未知，令， (3.4.8)由式(3.4.4)，得, (3.4.9)容易驗證是方程的單根，對它應用Newton法，迭代函數為 (3.4.10)從而可構造迭代格式 (3.4.11)因為Newton迭代法求單根時是至少平方收斂的，所以迭代公式(3.4.11)求也是至少平方收斂的。例3.4.6 已知方程的二重根，試用Newton迭代法及迭代法(3.4.6)、(3.4.11)三種方法求根

32、的近似值。解 ，方法1：Newton迭代法： .方法2：迭代法(3.4.6) .方法3：迭代法(3.4.11) .取初值，結果見表3.4.6.表 3.4.6方法1方法2方法31.77777782.05555561.94117651.89351852.00050061.99940011.94775732.00000012.00000001.97411222.00000002.0000000方法2與方法3均達到精確度，而方法1只有線性收斂，要達到相同精度需迭代16次。3.5 弦 截 法Newton迭代法對于單根的求解具有收斂快、穩(wěn)定性好、精度高等優(yōu)點，它是求解非線性方程的最有效的方法之一。但在應用

33、迭代公式時，每步迭代都要計算函數值與導數值，計算量較大。當導數值計算困難時，Newton迭代法將無法進行。注意到因為Newton迭代序列是收斂的，當充分大時，有，代入式(3.4.1)，則得離散的Newton迭代法.(3.5.1)并稱式(3.5.1)為弦截法(secant method). 幾何意義：通過曲線上兩點作割線，方程為，其割線與x軸交點的橫坐標恰好是式(3.5.1)中的, 如圖3.5.1所示，因而迭代法(3.5.1)又稱為割線法。圖 3.5.1弦截法與Newton迭代法不同，它需要給出兩個初始近似，才能啟動迭代過程，因此稱之為多步迭代法。關于弦截法的收斂性有以下結果：定理3.5.1 設

34、是方程的單根，若在的某個鄰域內有二階連續(xù)導數，且對任意，有，則當鄰域充分小時，對，弦截法按階收斂于根.證明 (1) 首先證明：由弦截法得到的序列.設是過兩點的弦與x軸的交點橫坐標，則差商 因為所以又因為在的某個鄰域內有二階連續(xù)導數，則,其中介于之間，介于和之間，即. 記，.取充分小的，使其滿足：，則有,所以，當，即時， ,即，從而序列.(2) 其次證明：由弦截法得到的序列收斂。由(1)的證明過程容易看出.依次遞推可得.又因為，所以，即.(3) 最后證明：弦截法的收斂階為.記，則. 由的收斂性可知，當k充分大時，.記，則. 將上式兩邊同時乘以得為了討論問題的方便，可將近似式看作等式.令，或，則上

35、式可化為.這是一個二階常系數齊次差分方程，可設，代入差分方程可得.解得故差分方程的通解為令分別等于，解得.由不難驗證：；故. 又因為，所以當時，即，所以有，從而所以弦截法的收斂階為. 證畢！由此可知，弦截法是超線性收斂的，且收斂階, 雖然收斂速度比Newton迭代法低，但是因為不需要計算導數，所以也是工程計算中常用的方法之一。例3.5.1 用弦截法法求方程在1.5附近的根。解 ，所以弦截法迭代公式為取初值，迭代結果見表3.5.1，而方程在1.5附近的根是表 3.5.101234561.00000001.33333331.42553191.45822111.45613111.45616421.4

36、5616423.6 拋物線（Müller）法如果考慮用的二次插值多項式的零點來近似的零點，就導出了拋物線法。設已知方程(3.1.1)的根的3個近似值 以這三點為節(jié)點的的二次插值多項式為 (3.6.1)為簡便起見，令 (3.6.2)則式(3.6.1)可改寫為, (3.6.3)其零點為：. (3.6.4)按式(3.6.4)，的二次插值多項式有兩個零點，取哪個作為新的近似根，考慮到已是方程(3.1.1)的近似根，新的近似根自然應在的鄰近，故選取近似根的原則是使得較小，于是有 (3.6.5)按式(3.6.5)計算方程(3.1.1)的近似根稱為拋物線法(parabolic method)，也稱

37、Müller方法(Müller method)，或二次插值法。如圖3.6.1所示，是過曲線上的三點的拋物線，故拋物線法的幾何意義是以過曲線上的三點的拋物線與軸的交點作為曲線與周軸交點的近似。圖3.6.1拋物線法的計算步驟為：(1) 給定精度，初始值 計算（要求互異）。(2) 計算(3) 若，則；否則再轉步驟(2).例3.6.1 用拋物線法求方程在內的根的近似值，取初值，.解 因為初值，所以.按式(3.6.2)和式(3.6.5)計算，得仿上述過程，繼續(xù)進行下去，計算結果見表3.5.1.表3.5.1k01411.51.754.522513.591831.6666670.0740

38、7415.22223710.33340111.77777341.6729220.00070711.72929510.67917711.79609351.6729822.48×10-7注1 若在其零點鄰近三階連續(xù)可微，且初始值充分接近，則Müller方法是收斂的。若是方程(3.1.1)的單根，則Müller方法的收斂階為1.84. 注2 在收斂性證明中雖然要求初始值充分接近根，但實際計算表明，拋物線法對初始值要求并不苛刻，在初值不太好的情形下常常也能收斂。它的缺點是程序比較復雜，并且在計算過程中，也常常采用復數運算，增加了工作量。因此，拋物線法適用于當初值不太好時求

39、方程(3.1.1)的復根的情況。3.7 非線性方程組的迭代法簡介設非線性方程組(system of nonlinear equations) (3.7.1)其中是變量的元函數，且至少有一個是自變量的非線性函數。若記，則式(3.7.1)可寫成 . (3.7.2)求解非線性方程組，從形式上，只要把單變量函數看成向量函數，就可將前面單個非線性方程的求根方法用于來求非線性方程組。下面主要介紹不動點迭代法、牛頓迭代法及擬牛頓迭代法。但因為非線性方程組(3.7.1)可能無解，有唯一解或無窮多解，所以有關它的求解問題一般要比單個非線性方程困難。3.7.1 解非線性方程組的不動點迭代法首先將式(3.7.2)改

40、寫為, (3.7.3)其中向量函數為連續(xù)函數。如果向量滿足，稱為函數的不動點，也就是方程組(3.7.1)的一個解。由式(3.7.3)可構造不動點迭代法 (3.7.4)如果由它產生的向量序列滿足，則為向量函數的不動點。例3.7.1 用不動點迭代法解下列非線性方程組解 將方程組改寫成等價形式 (3.7.5) 記， ,則式(3.7.5)可寫為.由此構造不動點迭代公式 (3.7.6)即取初始近似 ，按迭代公式(3.7.6)計算得近似值，見表3.7.1.表 3.7.1k012341000.80.92800000.97283170.98936560.999957100.80.93120000.973270

41、00.98943510.9999571 其收斂性類似于單個方程情況。定理3.7.1 設函數的定義域，且(1) 存在閉集，實數，對，有(2) 對，有則在有唯一的不動點，且對任意的，由迭代法(3.7.4)產生的向量序列收斂到，并有誤差估計.例3.7.2 對于例3.7.1中的方程組，設，證明：對任意的初始點，由迭代法(3.7.6)生成的序列均收斂到.證 首先，對任意，可以驗證.因此當，有.其次，對一切，都有 ，.從而有.根據定理3.7.1知，在上有唯一不動點，因此對任意的初始點，由迭代法(3.7.6)生成的序列均收斂到.定理3.7.2 設函數的定義域內有不動點，的分量函數有連續(xù)的偏導數，且譜半徑 (

42、3.7.7)則存在的一個鄰域，對任意的，迭代法(3.7.4)產生的序列收斂到. 其中的導數為Jacobi矩陣(Jacobi matrix).根據矩陣譜半徑與1-范數的關系，可得到如下結論：對于定義在上的函數，若存在常數，使得當時，,則矩陣的譜半徑.例如，對于例3.7.1，由可知，對一切，都有，其中，因此在內有，滿足定理3.7.2的條件，故迭代序列局部收斂。3.7.2 解非線性方程組的Newton迭代法設向量是方程組(3.7.1)的解，向量是方程組的初始近似解，假定在可微，將在處作多元函數的Taylor展開，并取其線性部分：即其中為Jacobi矩陣在處的值.若Jacobi矩陣非奇異，則方程組有唯

43、一解.一般地，當非奇異時，可得Newton迭代法. (3.7.8) 在第k步計算過程中，不僅要算出雅可比矩陣，還要求逆矩陣，計算量較大。因此，通常把第 k 步迭代分成兩步：記，則式(3.7.8)變?yōu)?(3.7.9)解此線性方程組，求出解向量后，再令，避免了求矩陣的逆。定理3.7.3 設的定義域，. 若有的開鄰域，在其上連續(xù)，可逆，則(1) Newton迭代法產生的序列在的某個鄰域上超線性收斂于；(2) 若再加上條件：存在常數，使，,則至少平方收斂。例3.7.3 用Newton迭代法解下列非線性方程組解 記，則.取初值，解方程組 ,即,可求得，然后計算得.類似地，可得，具體結果見表3.7.2.表

44、 3.7.2k0123400.80.99178720.99997521.000000000.80.99171170.99996851.0000000可見，Newton迭代法的收斂速度比不動點迭代法的收斂速度要快。3.7.3 解非線性方程組的擬Newton法 在求解非線性方程組(3.7.2)的Newton法中,是的Jacobi矩陣在處的值。當復雜時，的計算量較大，求解困難。在實際計算中，為減少計算量，避免每步都重新計算，類似于割線法的思想，構造, (3.7.10)新的滿足： . (3.7.11)這表明矩陣關于點及具有差商性質；即當時，即為關于及的差商。但當時，并不確定。為此我們限制是由的一個低秩

45、修正矩陣得到的，即， (3.7.12)其中，是秩為的修正矩陣。對 稱迭代算法 (3.7.13)為擬Newton迭代法(quasi Newton Iterative method)，稱式(3.7.10)為擬Newton方程(quasi Newton equation)。此方法只需對給出的初始近似及矩陣，用迭代格式(3.7.13)逐次計算得到及，從而避免了每步都要計算的Jacobi陣，減少了計算量。根據的不同取法，可得到不同的擬Newton法。在擬Newton法中，若矩陣非奇異，可令，于是能得到與式(3.7.13)互逆的迭代格式：對 (3.7.14)可以看出，迭代格式(3.7.14)不用求逆就能逐

46、次遞推算出，而迭代格式(3.7.8)需要求逆才能算出，因此在實際計算中可根據具體情況選用其中一種迭代格式。使用擬Newton法時，需要確定修正矩陣和;在此只介紹取的方法，稱為秩1擬Newton法(single rank quasi Newton method).設 (3.7.15)待定. 記，則式(3.7.11)變?yōu)? (3.7.16)將式(3.7.15)代入式(3.7.12)，得.將其代入式(3.7.16)，得或.若，則有.將其代入式(3.7.15)，即得 (3.7.17)若取，即，由式(3.7.17)得 (3.7.18)于是得到一個秩1擬Newton法：對 (3.7.19)式(3.7.19

47、)稱為Broyden秩1擬Newton法(single rank Broyden quasi Newton method).與式(3.7.19)互逆的Broyden秩1方法為：對 (3.7.20)其中. 式(3.7.20) 稱為逆Broyden秩1擬Newton法(single rank inverse Broyden quasi Newton method).實際應用式(3.7.19)或(3.7.20)求方程組(3.1.1)的近似解時，只要選擇較好的初始向量和初始矩陣和，一般可得到較好的近似解，迭代序列具有超線性收斂速度。例3.7.4 用逆Broyden秩1擬Newton法(3.7.20)求

48、下列方程組的解，取.解 . 因為，所以.取用式(3.7.20)進行迭代，可求得重復以上步驟，共迭代11次，得解若用Newton法(3.7.8)，取相同的初始近似，達到同一精度只需迭代7次，但它每步計算量比Broyden大得多。3.8 算法程序3.8.1 二分法 % 用二分法求非線性方程f(x)=0的根，fun為函數f(x)的表達式% a, b為左右端點，eps為精度，x為近似根，k為二分次數function Bisection(fun, a, b, eps)if nargin < 4 eps=1e-5; %如果輸入自變量數目<4，默認eps=1e-5end fa=feval(fun,a); fb=feval(fun,b); % fa, fb分別表示a, b兩個端點處的函數值if fa*fb>0 disp('無法判斷a, b內是否有根，請重新調整');returnendk=0;while abs(b-a)/2>eps x = (a+b)/2; fx = feval(fun, x); if fx*fa < 0 b = x; fb = fx; else a = x; fa = fx; end k = k+1;endx = (a+b)/2;disp ( '