第五章-非線性方程求根課件

1、問題驅(qū)動：全球定位系統(tǒng)（GPS） 人類對導(dǎo)航和定位的需求是伴隨著人類整個(gè)文明歷史的進(jìn)步而發(fā)展的，中國古代“四大發(fā)明”之一的指南針是最早的定位儀器和系統(tǒng)，其后還有經(jīng)緯儀以及近代的雷達(dá)。如圖5.1.1所示全球定位系統(tǒng)（GPS）是基于衛(wèi)星的導(dǎo)航系統(tǒng)，最早最早由美國和前蘇聯(lián)分別在80年代研制，并于1993年正式投入使用?，F(xiàn)代社會中全球定位系統(tǒng)越來越深入到人們生活的方方面面。例如市場上出售的手持型GPS,定位的精度可以達(dá)到10米以內(nèi)，這無疑給旅行者提供了方便;安裝有GPS的兒童手表，家長在家里的計(jì)算機(jī)上可以追蹤到孩子的位置，防止兒童走失;安裝有GPS系統(tǒng)的汽車可以幫助新司機(jī)辨識道路等等。 1 引 言圖5

2、.1.1 衛(wèi)星定位示意圖 美國和前蘇聯(lián)的GPS都包括有24顆衛(wèi)星,它們不斷地向地球發(fā)射信號報(bào)告當(dāng)前位置和發(fā)出信號的時(shí)間, 衛(wèi)星分布如圖5.1.2所示。它的基本原理是:在地球的任何一個(gè)位置，至少同時(shí)收到4顆以上衛(wèi)星發(fā)射的信號。發(fā)射的信號， 設(shè)地球上一個(gè)點(diǎn)R，同時(shí)收到衛(wèi)星 假設(shè)接收的信息如表5.1.1所示。請?jiān)O(shè)法確定R點(diǎn)的位置。 圖5.1.2 衛(wèi)星分布圖表9.1.1GPS導(dǎo)航問題可歸結(jié)為求解非線性代數(shù)數(shù)方程組 , 當(dāng) 時(shí)就是單個(gè)方程. .其中 可以是代數(shù)方程，也可以是超越方程。使 成立的x 值稱為方程的根，或稱為 的零點(diǎn)?？茖W(xué)與工程計(jì)算中，如電路和電力系統(tǒng)計(jì)算、非線性力學(xué)、非線性微（積分）方程、非

3、線性規(guī)劃（優(yōu)化）等眾多領(lǐng)域中，問題的求解和模擬最終往往都要解決求根或優(yōu)化問題。前一種情形要求出方程（組）的根；后一種情形則要求找出函數(shù)取最大或最小的點(diǎn)。 即使是對實(shí)驗(yàn)數(shù)據(jù)進(jìn)行擬合或數(shù)值求解微分方程，也總是將問題簡化成上述兩類問題。上述除少數(shù)特殊方程外，大多數(shù)非線性代數(shù)方程（組）很難使用解析法求解精確解，一般需要通過一些數(shù)值方法逼近方程的解。這里主要介紹單個(gè)方程的數(shù)值解法，方程組也可以采用類似的方法，將放在后面討論。1根的存在性。方程有沒有根？如果有，有幾個(gè)根？2根的搜索。這些根大致在哪里？如何把根隔離開？3根的精確化。 f (x) = 0 （5.1.1）1.根的存在性定理1：設(shè)函數(shù) f (x)

4、 在區(qū)間a, b上連續(xù)，如果f (a) f (b) 0打 印結(jié) 束否是繼續(xù)掃描例1：考察方程 x00.51.01.5f (x) 的符號ab或不能保證 x 的精度abx0 x1x*2 二 分 法 執(zhí)行步驟1計(jì)算f (x)在有解區(qū)間a, b端點(diǎn)處的值，f (a)，f (b)。2計(jì)算f (x)在區(qū)間中點(diǎn)處的值f (x0)。3判斷若f (x0) = 0，則x0即是根，否則檢驗(yàn)：（1）若f (x1)與f (a)異號，則知解位于區(qū)間a, x0， b1=x0, a1=a;（2）若f (x0)與f (a)同號，則知解位于區(qū)間x0, b， a1=x0, b1=b。反復(fù)執(zhí)行步驟2、3，便可得到一系列有根區(qū)間：4、

5、當(dāng)時(shí)，停止；即為根的近似。當(dāng) 時(shí)， ，即這些區(qū)間必將收縮于一點(diǎn)，也就是方程的根。在實(shí)際計(jì)算中，只要 的區(qū)間長度小于預(yù)定容許誤差就可以停止搜索，即 然后取其中點(diǎn) 作為方程的一個(gè)根的近似值。 注： 例1 證明方程 存在唯一的實(shí)根 用二分法求出此根，要求誤差不超過 。解：記 ，則對任意 ，因而， 是嚴(yán)格單調(diào)的， 最多有一個(gè)根，所以， 有唯一實(shí)根 又因?yàn)?用二分法求解，要使 ，只要 解得 ，取 。所以只要二等分7次，即可求得滿足精度要求的根。計(jì)算過程如表5.2.1所示 k f(ak)及符號f(xk)及符號f(bk)及符號01234 5670()0()0()0()0.0625()0.0625()0.07

6、8125()0.0859375()0.5(+)0.25(+)0.125(+)0.0625()0.09375(+)0.078125()0.0859375()1( + )0.5( + )0.25( + )0.125( + )0.125( + )0.09375( + )0.09375( + )0.09375( + )表5.2.1所以， 簡單; 對f (x) 要求不高(只要連續(xù)即可) .無法求復(fù)根及偶重根 收斂慢 二分法的優(yōu)缺點(diǎn) 問題 雖然二分法計(jì)算簡單，能夠保證收斂，但是它對于方程單根存在區(qū)域信息要求太高，一般情況下很難實(shí)現(xiàn)，并且不能求重根、復(fù)根和虛根。在實(shí)際應(yīng)用中，用來求解方程根的主要方法是迭代法

7、。使用迭代法求解非線性代數(shù)方程的步驟為：(1) 迭代格式的構(gòu)造；(2) 迭代格式的收斂性分析；(3) 迭代格式的收斂速度與誤差分析。 3 迭 代 法1簡單迭代法f (x) = 0 x = (x)等價(jià)變換其中 (x)是連續(xù)函數(shù)。方程（5.3.1）稱為不動點(diǎn)方程，滿足（5.3.1）式的點(diǎn)稱為不動點(diǎn)，這樣就將求 （5.3.1）的零點(diǎn)問題轉(zhuǎn)化為求的不動點(diǎn)問題。稱這種迭代格式為不動點(diǎn)迭代。以不動點(diǎn)方程為原型構(gòu)造迭代格式例3：求方程的一個(gè)根.構(gòu)造迭代格式x1 = 0.4771x2 = 0.3939x6 = 0.3758x7 =0.3758解：給定初始點(diǎn)xyy = xxyy = xxyy = xxyy =

8、xx*x*x*x*y= (x)y= (x)y= (x)y= (x)x0p0 x1p1x0p0 x1p1x0p0 x1p1x0p0 x1p1 定理2 如果 (x)滿足下列條件 （1）當(dāng)xa, b時(shí)，(x)a, b （2）當(dāng)任意xa, b，存在0 L 1，使 則方程x = (x)在a, b上有唯一的根x*,且對任意初值 x0a, b時(shí)，迭代序列xk+1= (xk) (k = 0, 1, )收斂于 x*，且有如下誤差估計(jì)式：(5.3.2)2迭代過程的收斂性與誤差估計(jì)停機(jī)準(zhǔn)則。（5.3.3） 求方程在內(nèi)的根例：。解：原方程可以等價(jià)變形為下列三個(gè)迭代格式由迭代格式 （1） 取初值得 結(jié)果是發(fā)散的？！由迭

9、代格式 （2） 取初值得 結(jié)果精確到四位有效數(shù)字，迭代到得到收斂結(jié)果。 十步才能得到收斂的結(jié)果！ 由迭代格式（3） 取初值得 結(jié)果精確到四位有效數(shù)字，迭代到得到收斂結(jié)果。四步就能得到收斂的結(jié)果了！迭代格式（1）的迭代函數(shù)為 求導(dǎo)得 當(dāng)時(shí)故迭代格式（1）是發(fā)散的。分析:當(dāng) 時(shí)， 迭代格式（2）的迭代函數(shù)為 由知當(dāng) 時(shí)， 所以迭代格式（2）是收斂的。迭代格式（3）的迭代函數(shù)為當(dāng) 時(shí)，由時(shí)， 知當(dāng)所以迭代格式（3）也是收斂的。結(jié)論: 通過以上算例可以看出對迭代函數(shù)所得到的若小于1，則收斂；且上界越小收斂速度越快。求導(dǎo)，的上界若是大于1，則迭代格式發(fā)散； 3. 加速收斂技術(shù) L越小迭代法的收斂速度越快

10、，因此，可以從尋找較小的L來改進(jìn)迭代格式以加快收斂速度。思路(1) 松弛法引入待定參數(shù) ，將 作等價(jià)變形為 （5.3.4） 將方程右端記為 ，則得到新的迭代格式 由定理2知 為了使新的迭代格式比原來迭代格式收斂得更快，只要滿足且 越小，所獲取的L就越小，迭代法收斂的就越快，因此我們希望 ?？扇?，若記 則（5.3.4）式可改寫為 稱為松弛因子，這種方法稱為松弛法。為使迭代速度加快，需要邊計(jì)算邊調(diào)整松弛因子。由于計(jì)算松弛因子需要用到微商，在實(shí)際應(yīng)用中不便使用，具有一定局限性。若迭代法是線性收斂的，當(dāng)計(jì)算 不方便時(shí)，可以采用埃特金加速公式。 (2) 埃特金加速公式設(shè)迭代法是線性收斂，由定義知成立，

11、故當(dāng) 時(shí)有 由此可得 的近似值 （5.3.5） 由此獲得比 和 更好的近似值 ，利用（5.3.5）序列 的方法稱為(3) Steffensen 加速法 將Aitken加速公式與不動點(diǎn)迭代相結(jié)合，可得（5.3.6） 式構(gòu)造埃特金（Aitken）加速方法。利用（5.3.6）式構(gòu)造序列 的方法稱為Steffensen加速方法。即每進(jìn)行兩次不動點(diǎn)迭代，就執(zhí)行一次Aitken加速。 例2 試用簡單迭代法和Steffensen加速法求方程在 附近的根，精確至四位有效數(shù)。 解：記 ，簡單迭代法公式為： 計(jì)算得kxkkxkkxk00.570.55844140.5671210.6065380.56641150.

12、5671620.5452490.56756160.5671430.57970100.5669140.56006110.5672850.57117120.5670760.56486130.56719Aitken加速公式計(jì)算得所以, 。4迭代過程的局部收斂定義1： 若存在 的某一鄰域 ，迭代過程 對任意初值 均收斂，則 稱迭代過程 在根 鄰近具有局 部收斂性。 定理3 設(shè) 為方程 的根， 在 的鄰近 連續(xù)，且 ，則迭代過程 在 的鄰近具有局部收斂性。5迭代過程的收斂速度 設(shè)由某方法確定的序列xk收斂于方程的根x*，如果存在正實(shí)數(shù)p，使得（C為非零常數(shù)）定義2則稱序列xk收斂于x*的收斂速度是p階的

13、，或稱該方法具有p 階收斂速度。當(dāng)p = 1時(shí)，稱該方法為線性（一次）收斂；當(dāng)p = 2時(shí)，稱方法為平方（二次）收斂；當(dāng)1 p 2或C=0,p=1時(shí)，稱方法為超線性收斂。 定理4 如果 在 附近的某個(gè)領(lǐng)域內(nèi)有 ( )階 連續(xù)導(dǎo)數(shù)，且則迭代格式 在 附近是 階局部收斂的，且有3 牛頓法一、牛頓法的迭代公式 考慮非線性方程 原理：將非線性方程線性化 Taylor 展開取 x0 x*，將 f (x)在 x0 做一階Taylor展開:， 在 x0 和 x 之間。將 (x* x0)2 看成高階小量，則有：只要 f C1，且每步迭代都有 ， 而且則 x*就是 f (x)的根。公式（9.4.1）稱為牛頓迭代

14、公式。(9.4.1)構(gòu)造迭代公式x*x0 x1x2xyf(x)二、牛頓法的幾何意義三、牛頓法的收斂性定理4： 設(shè)f (x)在a, b上存在二階連續(xù)導(dǎo)數(shù)且滿足下列條件：（1）f (a) f (b) 0則由（9.4.1）確定的牛頓迭代序列xk二階收斂于f (x)在a, b上的唯一單根x*。注：Newton法的收斂性依賴于x0 的選取。x*x0 x0 x0四. 牛頓迭代法的局部收斂性與收斂速度 ，,且 設(shè) 在包含 的一個(gè)區(qū)間二階連續(xù)可導(dǎo)，則Newton迭代法至少二階收斂，即 值得注意的是，當(dāng) 充分光滑且 是 的重根時(shí)，牛頓法在的附近是線性收斂的。且Newton迭代法在 上的收斂性依賴于初值的選取。即

15、初值 的選取充分靠近 時(shí)，一般可保證Newton迭代法收斂。 并得出了 是該方程的一個(gè)根，無人知道他用什么方法得出的，在當(dāng)時(shí)這是一個(gè)非常有名的結(jié)果，試用牛頓法求出此結(jié)果。 解： 記則當(dāng) 時(shí)， ，又所以 有唯一實(shí)根 ，并改寫 例3 Leonardo于1225年研究了方程 用牛頓迭代格式所以， 。五、求m重根的牛頓法1、迭代格式(9.4.2)2、重?cái)?shù)m的確定3、迭代格式（9.4.2)的收斂階（至少2階收斂）由于Newton迭代法的收斂性依賴于初值 的選取，如果 離方程的根 較遠(yuǎn)，則Newton迭代法可能發(fā)散。為了防止迭代發(fā)散，可以將Newton迭代法與下山法結(jié)合起來使用，放寬初值的選取范圍，即將（

16、9.4.1）式修改為： 其中， 稱為下山因子，選擇下山因子時(shí)，希望 滿足下山法具有的單調(diào)性，即這種算法稱為Newton下山法。在實(shí)際應(yīng)用中，可選擇 。六、牛頓法的變形1、牛頓下山法牛頓下山法的計(jì)算步驟：（1）選取初始近似值x0；（2）取下山因子 = 1；（3）計(jì)算（4）計(jì)算f (xk+1)，并比較 與 的大小，分以下二種情況1）若 ，則當(dāng) 時(shí)，取x* xk+1，計(jì)算過程結(jié)束；當(dāng) 時(shí)，則把 xk+1 作為新的 近似值，并返回到（3）。 2）若 ，則當(dāng)且|f(xk+1)| ，取x* xk，計(jì)算過程結(jié)束；否則若，而 時(shí)，則把xk+1加上一個(gè)適當(dāng)選定的小正數(shù)，即取xk+1+作為新的xk值，并轉(zhuǎn)向（3）

17、重復(fù)計(jì)算；當(dāng)；且 時(shí)，則將下山因子縮小一半，取/2代入，并轉(zhuǎn)向（3）重復(fù)計(jì)算。 例5：求方程f (x) = x3 x 1 = 0 的根。kxk010.611/251.14063211.36681311.32628411.32472牛頓下山法的計(jì)算結(jié)果：牛頓迭代法每迭代一次都需計(jì)算函數(shù)值 和導(dǎo)數(shù)值 計(jì)算量比較大；且迭代過程中計(jì)算 時(shí)，僅利用了 點(diǎn)的信息，而沒有充分利用已經(jīng)求出的 ；在導(dǎo)數(shù)計(jì)算比較麻煩或難以求出時(shí)， 迭代格式構(gòu)造 (2) 構(gòu)造方法：將Newton迭代格式中的導(dǎo)數(shù)用差商代替。 2、割線法：(1) 構(gòu)造思想：用割線的斜率代替牛頓迭代法中切線的斜率；設(shè)法避開導(dǎo)數(shù)值的計(jì)算，因此可以采用離散

18、牛頓法（割線法）。 一個(gè)自然的想法就是在充分利用“舊信息”的同時(shí)，割線法的幾何意義x0 x1切線 割線 切線斜率割線斜率x2割線法迭代格式：割線法的局部收斂性與收斂速度 設(shè) ，在 ,且 的某一鄰域 內(nèi)二階連續(xù)可微，當(dāng) 時(shí)，由割線法產(chǎn)生的序列 收斂于 ，且收斂階至少為1.618。 3、 雙點(diǎn)弦截法 ：切線斜率割線斜率初值 x0 和 x1。x0 x1x24 非線性方程組的數(shù)值解法(1) 構(gòu)造思想：用線性方程組近似非線性方程組，由線性方程組解得的向量序列，逐步逼近非線性方程組的解向量。 (2) 構(gòu)造方法：若記一、 非線性方程組的牛頓迭代法則非線性方程組其中 ，且 中至少有一個(gè)是 的非線性函數(shù)。類似于

19、的情況，可將單變量方程求根的方法推廣到非線性方程組。若已給出方程組的一個(gè)近似根 。將函數(shù) 的分量 在 用多元函數(shù)泰勒展開，并取其線性部分可表示為 （9.5.1）令上式右端為零，得到線性方程組（9.5.2） 其中稱為 的Jacobi矩陣，求解線性方程組（9.5.2），并記解為 ，則得 這就是解非線性方程組（9.5.1）的Newton迭代法。Newton迭代法具有二階的收斂速度，但對初值的要求很高，即充分靠近解 。圖9.5.1二、全球定位系統(tǒng)的求解:解：衛(wèi)星 的位置如圖9.5.1所示，假設(shè) 表示R的當(dāng)前位置，則它滿足方程組 其中，光速 ，上述方程組無疑是非線性的，但很容易將所有二次項(xiàng)都消去，從而得

20、到 由求解非線性方程組的Newton迭代法知迭代格式為其中， 使用Matlab求解得迭代4次就可以得到相當(dāng)精確的結(jié)果。 nxyzt00.00.00.010010.00716.3687270.374601-2.4039719.98521824.9840633.0182411.04630310000.26635.0001602.9998080.9995859999.99845.0000003.0000001.00000010000.000它的解是：歷史與注記 艾薩克牛頓（Isaac Newton 16421727） 牛頓是英國物理學(xué)家、數(shù)學(xué)家、天文學(xué)家和自然哲學(xué)家。1643年誕生于英格蘭林肯郡烏爾

21、索普鎮(zhèn)。1727年卒于倫敦。1665年他發(fā)現(xiàn)了二項(xiàng)式定理，1669年擔(dān)任盧卡斯講座的教授，1696年牛頓任造幣廠監(jiān)督，1699年升任廠長,1705年因改革幣制有功受封為爵士，1672年起他被接納為皇家學(xué)會會員，1703年被選為皇家學(xué)會主席直到逝世。 牛頓是有史以來最偉大的科學(xué)家之一，他在力學(xué)、數(shù)學(xué)、光學(xué)、熱學(xué)、天文學(xué)和哲學(xué)方面都有突出的貢獻(xiàn)。他在數(shù)學(xué)方面的貢獻(xiàn)為：牛頓將古希臘以來求解無窮小問題的種種特殊方法統(tǒng)一為兩類算法：正流數(shù)術(shù)（微分）和反流數(shù)術(shù)（積分），與此同時(shí)，他還在1676年首次公布了他發(fā)明的二項(xiàng)式展開定理。并和G.W.萊布尼茨幾乎同時(shí)創(chuàng)立了微積分學(xué)。牛頓在數(shù)值計(jì)算上的主要貢獻(xiàn)有：牛頓插值法、牛頓積分法、牛頓迭代法等。 關(guān)于特殊的非線性方程求根問題的迭代法最早出現(xiàn)在古希臘、巴比倫和印第安人的著作中。牛頓法的只有一部分屬于牛頓本人，1669年牛頓第一次提出了與現(xiàn)在牛頓法基本等價(jià)的方法，但令人驚訝的是該方法并沒有使用導(dǎo)數(shù)，而是基于二項(xiàng)展開式，因此只適用于多項(xiàng)式。1690年，拉弗森對牛頓法作了簡化和改進(jìn)，稱為牛頓拉弗森法。在牛頓法中使用導(dǎo)數(shù)是由辛普森1740年首次提出的，并將其從