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

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

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

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

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

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

6、，且，由零點(diǎn)定理知，在內(nèi)至少有一個(gè)實(shí)根。又因?yàn)?，所以在?nèi)有且僅有一個(gè)實(shí)根。下面從區(qū)間-3, 3開始，以1為步長(zhǎng)，通過計(jì)算的函數(shù)值，逐步縮小方程的有根區(qū)間(表3.2.1)表3.2.1-3-2-10123-39-18-9-6-3627由表3.2.1知，方程在區(qū)間內(nèi)有且僅有一個(gè)實(shí)根。記 則 取的中點(diǎn)，將區(qū)間二等分，由于，即與同號(hào)，此時(shí)令，得到新的有根區(qū)間；如此反復(fù)二分下去。下面估計(jì)二分的次數(shù). 因?yàn)轭}目要求精確到小數(shù)點(diǎn)后第2位，所以可取精度，由(3.2.2)得，.取，即至多二分7次即可，計(jì)算結(jié)果見表3.2.2.表3.2.2符號(hào)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其中為方程精確到小數(shù)點(diǎn)后第2位的近似根。3.3 迭代法及其收斂性迭代法(Iterative Method)是用收斂于所給問題的精確解的極限過程，是一種逐步逼近精確解的數(shù)值方法。其基本思想是將方程求根問題轉(zhuǎn)化為某個(gè)函數(shù)求不動(dòng)點(diǎn)的問題，利用不動(dòng)點(diǎn)的迭代法求方程的近似根。3.3.1 不動(dòng)點(diǎn)的迭代法及其收斂性將方程(3.1.1)改寫成等價(jià)形式 (3.3.1)例如，可取.定義3

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

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

10、因此有根區(qū)間為. 將方程轉(zhuǎn)化成等價(jià)形式，迭代函數(shù)有很多種取法，例如： 圖 3.3.3，, 等等。下面僅取前兩種迭代函數(shù)進(jìn)行計(jì)算，其余的讀者可作為練習(xí)。對(duì)應(yīng)于迭代函數(shù)的迭代公式分別為方法1 ， (3.3.3)方法2 . (3.3.4)取區(qū)間中點(diǎn)作為初值，迭代結(jié)果見表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.0984108顯然，方法1收斂，原方程的準(zhǔn)確值為；而方法2發(fā)散。例3.3.1表明構(gòu)造迭代

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

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

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

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

15、y convergent)。定理3.3.2 設(shè)為的不動(dòng)點(diǎn)，在的鄰域連續(xù)，且，則迭代法(3.3.2)局部收斂。證明 由的連續(xù)性，存在，使，并有.因此對(duì)任意，有，故在區(qū)間上滿足定理3.3.1的推論的條件，故由式(3.3.2)生成的序列對(duì)均收斂于. 證畢!例3.3.3 構(gòu)造不同迭代法求的根.解 (1) 構(gòu)造迭代公式則迭代函數(shù)為. 因?yàn)?所以不滿足定理3.3.2的條件。(2) 構(gòu)造迭代公式 則迭代函數(shù)為.因?yàn)? ，所以由定理3.3.2知，迭代法收斂。(3) 構(gòu)造迭代公式 則迭代函數(shù)為.因?yàn)椋杂啥ɡ?.3.2知，迭代法收斂。若取，分別用上述三種迭代計(jì)算，結(jié)果見表3.3.2，. 從表3.3.2看到迭代

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

17、衡量迭代好壞的標(biāo)志之一。定義3.3.3 設(shè)序列收斂到，記誤差，若存在實(shí)數(shù)及，使, (3.3.10)則稱序列是按漸進(jìn)誤差常數(shù)，階收斂到 (converges to of order p with asymptotic error constant )。特別地，當(dāng)且，稱為線性收斂 (linearly convergent)。當(dāng)時(shí)，稱為平方收斂 (quadratically convergent)。當(dāng)時(shí)，統(tǒng)稱為超線性收斂 (superlinarly convergent)。顯然，數(shù)的大小反映了收斂速度的快慢。越大，則收斂越快。因此迭代法的收斂階是對(duì)收斂速度的一種度量。定理3.3.3 設(shè)為的不動(dòng)點(diǎn)，整

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

19、，為了加快迭代法的收斂速度，通常可采用斯特芬森加速迭代(Steffensens acceleration)。設(shè)是的不動(dòng)點(diǎn)，記，利用中值定理有介于與之間。通常依賴于，若變化不大，設(shè)，于是有 從上兩式消去C，則得 或 .解得.若記 (3.3.13)則用序列作為不動(dòng)點(diǎn)的新的近似值序列，一般它比迭代法(3.3.2)收斂更快。迭代法(3.3.13)可改寫為下列形式 (3.3.14)稱為Steffensen迭代法(Steffensens iterative method)，它是將原不動(dòng)點(diǎn)迭代式(3.3.2)的計(jì)算兩步合并成一步得到，可改為另一種不動(dòng)點(diǎn)迭代格式, (3.3.15)其中 (3.3.16)Ste

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

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

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

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

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

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

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

27、由，知：當(dāng)時(shí)，可得，由根的唯一性，知.例3.4.3 用Newton迭代法求方程在內(nèi)的實(shí)根，討論收斂性，并要求.解 設(shè)，則. 當(dāng)時(shí)，有，.取，有. 由定理3.4.2知：相應(yīng)的Newton迭代公式,收斂。且為滿足精度要求的近似根(見表3.4.4)。表3.4.4k0123410.75036386780.73911289090.73908513340.7390851332例3.4.4 (1) 設(shè)，求平方根的過程可化為解方程. 若用Newton法求解，證明對(duì)任何初值，相應(yīng)的Newton迭代公式都收斂于. (2) 求的近似值。證 (1) 對(duì)，Newton迭代公式為. (3.4.3)由此可得.故對(duì)任意的，均

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

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

30、1.6335.4538.75T/牛16168.512426.810922.110109.19608.69275.93.4.2 Newton迭代法求重根設(shè)為方程的m重根，由定義3.1.2及定理3.1.1知：在的某領(lǐng)域內(nèi)可表示為 (3.4.4)其中，是正整數(shù)。且有，. Newton法的迭代函數(shù). 因?yàn)? (3.4.5)且，所以由定理3.3.3知：Newton迭代法求重根時(shí)仍收斂，但只是線性收斂的。下面將對(duì)Newton迭代法加以改進(jìn)正，使得改進(jìn)的Newton迭代法求重根時(shí)是平方收斂的。若根的重?cái)?shù)m已知，則可將Newton迭代法改寫為, (3.4.6)其迭代函數(shù)為. (3.4.7)由式(3.4.5)得

31、,由定理3.3.3知：迭代公式(3.4.6)至少平方收斂。稱式(3.4.6)為改進(jìn)的Newton迭代法(modified Newton iterative method).若根的重?cái)?shù)m未知，令， (3.4.8)由式(3.4.4)，得, (3.4.9)容易驗(yàn)證是方程的單根，對(duì)它應(yīng)用Newton法，迭代函數(shù)為 (3.4.10)從而可構(gòu)造迭代格式 (3.4.11)因?yàn)镹ewton迭代法求單根時(shí)是至少平方收斂的，所以迭代公式(3.4.11)求也是至少平方收斂的。例3.4.6 已知方程的二重根，試用Newton迭代法及迭代法(3.4.6)、(3.4.11)三種方法求根的近似值。解 ，方法1：Newton

32、迭代法： .方法2：迭代法(3.4.6) .方法3：迭代法(3.4.11) .取初值，結(jié)果見表3.4.6.表 3.4.6方法1方法2方法31.77777782.05555561.94117651.89351852.00050061.99940011.94775732.00000012.00000001.97411222.00000002.0000000方法2與方法3均達(dá)到精確度，而方法1只有線性收斂，要達(dá)到相同精度需迭代16次。3.5 弦 截 法Newton迭代法對(duì)于單根的求解具有收斂快、穩(wěn)定性好、精度高等優(yōu)點(diǎn)，它是求解非線性方程的最有效的方法之一。但在應(yīng)用迭代公式時(shí)，每步迭代都要計(jì)算函數(shù)值與

33、導(dǎo)數(shù)值，計(jì)算量較大。當(dāng)導(dǎo)數(shù)值計(jì)算困難時(shí)，Newton迭代法將無法進(jìn)行。注意到因?yàn)镹ewton迭代序列是收斂的，當(dāng)充分大時(shí)，有，代入式(3.4.1)，則得離散的Newton迭代法.(3.5.1)并稱式(3.5.1)為弦截法(secant method). 幾何意義：通過曲線上兩點(diǎn)作割線，方程為，其割線與x軸交點(diǎn)的橫坐標(biāo)恰好是式(3.5.1)中的, 如圖3.5.1所示，因而迭代法(3.5.1)又稱為割線法。圖 3.5.1弦截法與Newton迭代法不同，它需要給出兩個(gè)初始近似，才能啟動(dòng)迭代過程，因此稱之為多步迭代法。關(guān)于弦截法的收斂性有以下結(jié)果：定理3.5.1 設(shè)是方程的單根，若在的某個(gè)鄰域內(nèi)有二階

34、連續(xù)導(dǎo)數(shù)，且對(duì)任意，有，則當(dāng)鄰域充分小時(shí)，對(duì)，弦截法按階收斂于根.證明 (1) 首先證明：由弦截法得到的序列.設(shè)是過兩點(diǎn)的弦與x軸的交點(diǎn)橫坐標(biāo)，則差商 因?yàn)樗杂忠驗(yàn)樵诘哪硞€(gè)鄰域內(nèi)有二階連續(xù)導(dǎo)數(shù)，則,其中介于之間，介于和之間，即. 記，.取充分小的，使其滿足：，則有,所以，當(dāng)，即時(shí)， ,即，從而序列.(2) 其次證明：由弦截法得到的序列收斂。由(1)的證明過程容易看出.依次遞推可得.又因?yàn)?，所以，?(3) 最后證明：弦截法的收斂階為.記，則. 由的收斂性可知，當(dāng)k充分大時(shí)，.記，則. 將上式兩邊同時(shí)乘以得為了討論問題的方便，可將近似式看作等式.令，或，則上式可化為.這是一個(gè)二階常系數(shù)齊次差分

35、方程，可設(shè)，代入差分方程可得.解得故差分方程的通解為令分別等于，解得.由不難驗(yàn)證：；故. 又因?yàn)?，所以?dāng)時(shí)，即，所以有，從而所以弦截法的收斂階為. 證畢！由此可知，弦截法是超線性收斂的，且收斂階, 雖然收斂速度比Newton迭代法低，但是因?yàn)椴恍枰?jì)算導(dǎo)數(shù)，所以也是工程計(jì)算中常用的方法之一。例3.5.1 用弦截法法求方程在1.5附近的根。解 ，所以弦截法迭代公式為取初值，迭代結(jié)果見表3.5.1，而方程在1.5附近的根是表 3.5.101234561.00000001.33333331.42553191.45822111.45613111.45616421.45616423.6 拋物線（Mlle

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

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

38、220.00070711.72929510.67917711.79609351.6729822.4810-7注1 若在其零點(diǎn)鄰近三階連續(xù)可微，且初始值充分接近，則Mller方法是收斂的。若是方程(3.1.1)的單根，則Mller方法的收斂階為1.84. 注2 在收斂性證明中雖然要求初始值充分接近根，但實(shí)際計(jì)算表明，拋物線法對(duì)初始值要求并不苛刻，在初值不太好的情形下常常也能收斂。它的缺點(diǎn)是程序比較復(fù)雜，并且在計(jì)算過程中，也常常采用復(fù)數(shù)運(yùn)算，增加了工作量。因此，拋物線法適用于當(dāng)初值不太好時(shí)求方程(3.1.1)的復(fù)根的情況。3.7 非線性方程組的迭代法簡(jiǎn)介設(shè)非線性方程組(system of nonl

39、inear equations) (3.7.1)其中是變量的元函數(shù)，且至少有一個(gè)是自變量的非線性函數(shù)。若記，則式(3.7.1)可寫成 . (3.7.2)求解非線性方程組，從形式上，只要把單變量函數(shù)看成向量函數(shù)，就可將前面單個(gè)非線性方程的求根方法用于來求非線性方程組。下面主要介紹不動(dòng)點(diǎn)迭代法、牛頓迭代法及擬牛頓迭代法。但因?yàn)榉蔷€性方程組(3.7.1)可能無解，有唯一解或無窮多解，所以有關(guān)它的求解問題一般要比單個(gè)非線性方程困難。3.7.1 解非線性方程組的不動(dòng)點(diǎn)迭代法首先將式(3.7.2)改寫為, (3.7.3)其中向量函數(shù)為連續(xù)函數(shù)。如果向量滿足，稱為函數(shù)的不動(dòng)點(diǎn)，也就是方程組(3.7.1)的一

40、個(gè)解。由式(3.7.3)可構(gòu)造不動(dòng)點(diǎn)迭代法 (3.7.4)如果由它產(chǎn)生的向量序列滿足，則為向量函數(shù)的不動(dòng)點(diǎn)。例3.7.1 用不動(dòng)點(diǎn)迭代法解下列非線性方程組解 將方程組改寫成等價(jià)形式 (3.7.5) 記， ,則式(3.7.5)可寫為.由此構(gòu)造不動(dòng)點(diǎn)迭代公式 (3.7.6)即取初始近似 ，按迭代公式(3.7.6)計(jì)算得近似值，見表3.7.1.表 3.7.1k012341000.80.92800000.97283170.98936560.999957100.80.93120000.97327000.98943510.9999571 其收斂性類似于單個(gè)方程情況。定理3.7.1 設(shè)函數(shù)的定義域，且(1)

41、 存在閉集，實(shí)數(shù)，對(duì)，有(2) 對(duì)，有則在有唯一的不動(dòng)點(diǎn)，且對(duì)任意的，由迭代法(3.7.4)產(chǎn)生的向量序列收斂到，并有誤差估計(jì).例3.7.2 對(duì)于例3.7.1中的方程組，設(shè)，證明：對(duì)任意的初始點(diǎn)，由迭代法(3.7.6)生成的序列均收斂到.證 首先，對(duì)任意，可以驗(yàn)證.因此當(dāng)，有.其次，對(duì)一切，都有 ，.從而有.根據(jù)定理3.7.1知，在上有唯一不動(dòng)點(diǎn)，因此對(duì)任意的初始點(diǎn)，由迭代法(3.7.6)生成的序列均收斂到.定理3.7.2 設(shè)函數(shù)的定義域內(nèi)有不動(dòng)點(diǎn)，的分量函數(shù)有連續(xù)的偏導(dǎo)數(shù)，且譜半徑 (3.7.7)則存在的一個(gè)鄰域，對(duì)任意的，迭代法(3.7.4)產(chǎn)生的序列收斂到. 其中的導(dǎo)數(shù)為Jacobi矩陣

42、(Jacobi matrix).根據(jù)矩陣譜半徑與1-范數(shù)的關(guān)系，可得到如下結(jié)論：對(duì)于定義在上的函數(shù)，若存在常數(shù)，使得當(dāng)時(shí)，,則矩陣的譜半徑.例如，對(duì)于例3.7.1，由可知，對(duì)一切，都有，其中，因此在內(nèi)有，滿足定理3.7.2的條件，故迭代序列局部收斂。3.7.2 解非線性方程組的Newton迭代法設(shè)向量是方程組(3.7.1)的解，向量是方程組的初始近似解，假定在可微，將在處作多元函數(shù)的Taylor展開，并取其線性部分：即其中為Jacobi矩陣在處的值.若Jacobi矩陣非奇異，則方程組有唯一解.一般地，當(dāng)非奇異時(shí)，可得Newton迭代法. (3.7.8) 在第k步計(jì)算過程中，不僅要算出雅可比矩陣

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

44、170.99996851.0000000可見，Newton迭代法的收斂速度比不動(dòng)點(diǎn)迭代法的收斂速度要快。3.7.3 解非線性方程組的擬Newton法 在求解非線性方程組(3.7.2)的Newton法中,是的Jacobi矩陣在處的值。當(dāng)復(fù)雜時(shí)，的計(jì)算量較大，求解困難。在實(shí)際計(jì)算中，為減少計(jì)算量，避免每步都重新計(jì)算，類似于割線法的思想，構(gòu)造, (3.7.10)新的滿足： . (3.7.11)這表明矩陣關(guān)于點(diǎn)及具有差商性質(zhì)；即當(dāng)時(shí)，即為關(guān)于及的差商。但當(dāng)時(shí)，并不確定。為此我們限制是由的一個(gè)低秩修正矩陣得到的，即， (3.7.12)其中，是秩為的修正矩陣。對(duì) 稱迭代算法 (3.7.13)為擬Newto

45、n迭代法(quasi Newton Iterative method)，稱式(3.7.10)為擬Newton方程(quasi Newton equation)。此方法只需對(duì)給出的初始近似及矩陣，用迭代格式(3.7.13)逐次計(jì)算得到及，從而避免了每步都要計(jì)算的Jacobi陣，減少了計(jì)算量。根據(jù)的不同取法，可得到不同的擬Newton法。在擬Newton法中，若矩陣非奇異，可令，于是能得到與式(3.7.13)互逆的迭代格式：對(duì) (3.7.14)可以看出，迭代格式(3.7.14)不用求逆就能逐次遞推算出，而迭代格式(3.7.8)需要求逆才能算出，因此在實(shí)際計(jì)算中可根據(jù)具體情況選用其中一種迭代格式。使

46、用擬Newton法時(shí)，需要確定修正矩陣和;在此只介紹取的方法，稱為秩1擬Newton法(single rank quasi Newton method).設(shè) (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)于是得到一個(gè)秩1擬Newton法：對(duì) (3.7.19)式(3.7.19)稱為Broyden秩1擬Newton法(single rank Broyden quasi Newton

47、method).與式(3.7.19)互逆的Broyden秩1方法為：對(duì) (3.7.20)其中. 式(3.7.20) 稱為逆Broyden秩1擬Newton法(single rank inverse Broyden quasi Newton method).實(shí)際應(yīng)用式(3.7.19)或(3.7.20)求方程組(3.1.1)的近似解時(shí)，只要選擇較好的初始向量和初始矩陣和，一般可得到較好的近似解，迭代序列具有超線性收斂速度。例3.7.4 用逆Broyden秩1擬Newton法(3.7.20)求下列方程組的解，取.解 . 因?yàn)椋?取用式(3.7.20)進(jìn)行迭代，可求得重復(fù)以上步驟，共迭代11次，得解若用Newton法(3.7.8)，取相同的初始近似，達(dá)到同一精度只需迭代7次，但它每步計(jì)算量比Broyden大得多。3.8 算法程序3.8.1 二分法 % 用二分法求非線性方程f(x)=0的根，fun為函數(shù)f(x)的表達(dá)式% a, b為左右端點(diǎn)，eps為精度，x為近似根，k為二分次數(shù)function Bisection(fun, a, b, eps)if nargin 4 eps=1e-5; %如果輸入自變量數(shù)目0 disp(無法判斷a, b內(nèi)是否有根，請(qǐng)重新調(diào)整);