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

2、.1.1 衛星定位示意圖 美國和前蘇聯的GPS都包括有24顆衛星,它們不斷地向地球發射信號報告當前位置和發出信號的時間, 衛星分布如圖5.1.2所示。它的基本原理是:在地球的任何一個位置，至少同時收到4顆以上衛星發射的信號。發射的信號， 設地球上一個點R，同時收到衛星 假設接收的信息如表5.1.1所示。請設法確定R點的位置。 圖5.1.2 衛星分布圖表9.1.1GPS導航問題可歸結為求解非線性代數數方程組 , 當 時就是單個方程. .其中 可以是代數方程，也可以是超越方程。使 成立的x 值稱為方程的根，或稱為 的零點。科學與工程計算中，如電路和電力系統計算、非線性力學、非線性微（積分）方程、非

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

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

5、當時，停止；即為根的近似。當 時， ，即這些區間必將收縮于一點，也就是方程的根。在實際計算中，只要 的區間長度小于預定容許誤差就可以停止搜索，即 然后取其中點 作為方程的一個根的近似值。 注： 例1 證明方程 存在唯一的實根 用二分法求出此根，要求誤差不超過 。解：記 ，則對任意 ，因而， 是嚴格單調的， 最多有一個根，所以， 有唯一實根 又因為 用二分法求解，要使 ，只要 解得 ，取 。所以只要二等分7次，即可求得滿足精度要求的根。計算過程如表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) 要求不高(只要連續即可) .無法求復根及偶重根 收斂慢 二分法的優缺點 問題 雖然二分法計算簡單，能夠保證收斂，但是它對于方程單根存在區域信息要求太高，一般情況下很難實現，并且不能求重根、復根和虛根。在實際應用中，用來求解方程根的主要方法是迭代法

7、。使用迭代法求解非線性代數方程的步驟為：(1) 迭代格式的構造；(2) 迭代格式的收斂性分析；(3) 迭代格式的收斂速度與誤差分析。 3 迭 代 法1簡單迭代法f (x) = 0 x = (x)等價變換其中 (x)是連續函數。方程（5.3.1）稱為不動點方程，滿足（5.3.1）式的點稱為不動點，這樣就將求 （5.3.1）的零點問題轉化為求的不動點問題。稱這種迭代格式為不動點迭代。以不動點方程為原型構造迭代格式例3：求方程的一個根.構造迭代格式x1 = 0.4771x2 = 0.3939x6 = 0.3758x7 =0.3758解：給定初始點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）當xa, b時，(x)a, b （2）當任意xa, b，存在0 L 1，使 則方程x = (x)在a, b上有唯一的根x*,且對任意初值 x0a, b時，迭代序列xk+1= (xk) (k = 0, 1, )收斂于 x*，且有如下誤差估計式：(5.3.2)2迭代過程的收斂性與誤差估計停機準則。（5.3.3） 求方程在內的根例：。解：原方程可以等價變形為下列三個迭代格式由迭代格式 （1） 取初值得 結果是發散的？！由迭

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

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

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

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

13、，或稱該方法具有p 階收斂速度。當p = 1時，稱該方法為線性（一次）收斂；當p = 2時，稱方法為平方（二次）收斂；當1 p 2或C=0,p=1時，稱方法為超線性收斂。 定理4 如果 在 附近的某個領域內有 ( )階 連續導數，且則迭代格式 在 附近是 階局部收斂的，且有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)構造迭代公式x*x0 x1x2xyf(x)二、牛頓法的幾何意義三、牛頓法的收斂性定理4： 設f (x)在a, b上存在二階連續導數且滿足下列條件：（1）f (a) f (b) 0則由（9.4.1）確定的牛頓迭代序列xk二階收斂于f (x)在a, b上的唯一單根x*。注：Newton法的收斂性依賴于x0 的選取。x*x0 x0 x0四. 牛頓迭代法的局部收斂性與收斂速度 ，,且 設 在包含 的一個區間二階連續可導，則Newton迭代法至少二階收斂，即 值得注意的是，當 充分光滑且 是 的重根時，牛頓法在的附近是線性收斂的。且Newton迭代法在 上的收斂性依賴于初值的選取。即

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

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

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

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

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

20、到 由求解非線性方程組的Newton迭代法知迭代格式為其中， 使用Matlab求解得迭代4次就可以得到相當精確的結果。 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） 牛頓是英國物理學家、數學家、天文學家和自然哲學家。1643年誕生于英格蘭林肯郡烏爾

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