非線性方程和方程組的數(shù)值解法

1、第四章 非線性方程和方程組的數(shù)值解法教學(xué)目標(biāo)：1.了解并掌握非線性方程的根的相關(guān)概念，如m重根、有根區(qū)間等概念；2.掌握逐步搜索法和二分法（區(qū)間對分法）的基本思想及步驟，了解這兩種方法的適用性及缺點，能應(yīng)用其求解簡單的非線性方程；3.了解迭代法的分類，理解并掌握不動點迭代法的概念及相關(guān)收斂性定理，掌握全局收斂性及局部收斂性聯(lián)系及區(qū)別，理解收斂階和計算效率的相關(guān)概念的來歷及含義；4.了解迭代加速的思想，掌握加權(quán)法（松弛法）、Aitken以及Steffensen加速方法的思想及相關(guān)理論、計算公式；5.理解并掌握Newton迭代法及求重根的修正Newton迭代法的思想、實現(xiàn)步驟以及相關(guān)理論；6.理解

2、Newton迭代法的相關(guān)變形方法的提出及實現(xiàn)步驟，如簡化Newton法（平行弦法）、Newton下山法、擬Newton法和Steffensen方法；7、理解割線法和Muller法提出的背景及實現(xiàn)步驟，掌握相關(guān)的理論。教學(xué)重點：1.逐步搜索法和二分法（區(qū)間對分法）的基本思想及步驟；2.不動點迭代法的概念及相關(guān)收斂性定理；3.迭代加速的思想及三種實現(xiàn)方式；4. Newton迭代法及相關(guān)變形或改進的迭代法的思想及步驟。教學(xué)難點：1.不動點迭代法的概念及相關(guān)收斂性定理；2.迭代加速的思想及三種實現(xiàn)方式；3. Newton迭代法及相關(guān)變形或改進的迭代法的思想及步驟。教學(xué)方法：教具：§4.1 問

3、題的提出非線性科學(xué)是當(dāng)今科學(xué)發(fā)展的一個重要研究方向，而非線性方程的求根也成了一個不可缺的內(nèi)容。但是，非線性方程的求根非常復(fù)雜。本章重點討論單個方程的求根方法，對于非線性方程組的解法僅作一些簡單的介紹。這是因為單個方程的求根問題比非線性方程組更普遍。另外非線性方程組的求解是個難度比較大的問題，許多近代研究集中在這個問題上。非線性方程和方程組的數(shù)值解法主要是迭代法。一般的非線性方程組可以寫成，其中和都是維向量。當(dāng)時就是單個的方程。為了敘述方便，首先引入下述定義：定義4.1 對于一元非線性方程，若為代數(shù)多項式，即則稱為代數(shù)（多項式）方程，否則稱為超越方程。例如，為代數(shù)方程，而則為超越方程。定義4.2

4、 （1）若存在使，則稱是方程的解或根，也稱是函數(shù)的零點。（2）若函數(shù)可分解為 ，其中為正整數(shù)，則稱是方程的重根，或稱是函數(shù)的重零點。當(dāng)時，稱是的單根或的單重零點。零點可能是實數(shù)，也可能是復(fù)數(shù)。定理4.1 對于充分可微的函數(shù)，是函數(shù)的重零點的充分必要條件是：，定義4.3 若方程在區(qū)間內(nèi)至少有一個根，則稱為方程的有根區(qū)間。通常可用逐步（次）搜索法求方程的有根區(qū)間。定理4.2 若函數(shù)在區(qū)間上連續(xù)（即），且，則方程在內(nèi)至少有一個根。定義4.4 若在區(qū)間上只有方程的一個根，則稱為方程的隔根區(qū)間。定理4.3 若函數(shù)在區(qū)間上單調(diào)連續(xù)，且，則方程在內(nèi)有且僅有一個根。關(guān)于根的個數(shù)，由代數(shù)學(xué)基本定理知，高次代數(shù)方

5、程的根（包括實根和復(fù)根）的個數(shù)與代數(shù)方程的次數(shù)相同；對于超越方程，可能沒有根，也可能有一個或若干個根，甚至無窮多個根。理論上已經(jīng)證明，對于次數(shù)的代數(shù)方程，它的根可以用根式表示，而次數(shù)的代數(shù)方程，它的根一般不能用根式表示，亦即不能用解析表達式來表示。因此對于一般的函數(shù)方程，一般來說，更不存在根的解析表達式，而在實際應(yīng)用中，也不一定需要得到求根的解析表達式，只要得到滿足精度要求的根的近似值就可以了。求解非線性方程的根的問題大致可分為下面三個方面：（1）根的存在性。即方程有沒有根？如果有根，有幾個根？（2）根的分布，即求出有根區(qū)間。（3）根的精確化。即在已知一個根的近似值后，設(shè)法逐步把根精確化，直到

6、滿足精度為止。§4.2 逐步搜索法和二分法4.2.1 逐步搜索法假設(shè)是定義在某區(qū)域內(nèi)的連續(xù)函數(shù)，在區(qū)間有且僅有一個單根，則逐步搜索法的步驟如下：（1）判斷的符號：若，則；若，則不妨設(shè)。（2）選擇適當(dāng)?shù)牟介L，搜索一步，看的符號，若，則已找到。若則可知，這時可取或作為的近似值。若，則繼續(xù)往前搜索一步，看的符號，直到與異號，則可知，其中，這時可取或作為的近似值。逐步搜索法的步長的選擇很難恰到好處，若取得較大，則精度較差；若取得足夠小，精度提高了，但計算量增加了許多。因此，如果精度要求較高的話，該方法不太經(jīng)濟。例4.1 求方程的有根區(qū)間。解：根據(jù)有根區(qū)間的定義，對方程的根進行搜索計算，結(jié)果如

7、下表0123456符號從上表可以得出方程的三個有根區(qū)間為，和。4.2.2 二分法二分法（對分法）是逐步搜索法的改進。它的基本思想是逐步將非線性方程的有根區(qū)間（或隔根區(qū)間）二分，通過判斷函數(shù)值的符號，逐步對半縮小有根區(qū)間（或隔根區(qū)間），直到區(qū)間縮小到容許誤差范圍之內(nèi)，然后取區(qū)間的中點為根的近似值。（基本思想：通過計算隔根區(qū)間的中點，逐步縮小隔根區(qū)間，從而得到方程的近似根）設(shè)，且，則在內(nèi)有根。為明確起見，再設(shè)在內(nèi)僅有一個根。令，計算和。若，則，結(jié)束計算。若，則令，否則令，這樣得到新的隔根區(qū)間。，。再令，若，則，否則類似可得新的隔根區(qū)間。這個過程可一直進行下去，僅當(dāng)出現(xiàn)時過程中斷（其中）。記第次過程

8、得到的隔根區(qū)間為，則， （4.1）故有 ，因此當(dāng)充分大時，可作為方程的根的近似值，且有誤差估計式 對于預(yù)先給定的精度，只要，即 （4.2）便有，這時就是滿足精度要求的近似值。（實際中常用來代替，其中為預(yù)先給定的小量）分析以上過程不難發(fā)現(xiàn)，二分法的收斂速度與公比為的等比級數(shù)相同。由于，可知大約二分10次，近似根的精度可提高三位小數(shù)位。二分法的思想方法還可以用于搜索一個較大區(qū)間內(nèi)實根的分布情況（不包括偶重實根），實際做法是：取適當(dāng)?shù)牟介L，逐一檢驗小區(qū)間（）兩端的函數(shù)值是否異號，若異號，則按以上二分法求出其中的根；若同號則不作求根運算而轉(zhuǎn)入檢查下一個區(qū)間，只要選得適當(dāng)小，則可求出內(nèi)的所有奇重實根（包

9、括單實根）。選得過大，可能漏掉某些根；選得過小，則計算量增大。二分法的優(yōu)點是程序簡單、方法可靠、易于在計算機上實現(xiàn)，事先估計計算次數(shù)容易，收斂速度恒定，對函數(shù)的性質(zhì)要求低，只要連續(xù)就可以了；它的局限性是不能求偶數(shù)重根，也不能求復(fù)根和虛根。另外，二分法在求根過程中，只用到了函數(shù)的符號，而未用到計算出的函數(shù)值，這總有點浪費。實際應(yīng)用中這個方法可用于求根的初始近似值，以便使用其它的求根高速迭代法，有時也用來試探實根的分布區(qū)間。例4.2 用二分法求方程在區(qū)間內(nèi)的一個實根，要求精確到小數(shù)點后第二位（即誤差不超過0.005）。解：這里，而，故在區(qū)間內(nèi)有根。由（4.2）式可得故只要二分6次便能達到所要求的精

10、度，具體計算結(jié)果見下表：的符號01.01.51.2511.251.37521.3751.312531.31251.343841.34381.328151.32811.320361.32031.3242故為方程的近似根，誤差不超過0.005。§4.3 迭代法4.3.1 迭代法分類迭代法是一種逐步逼近根的方法，已知方程的一個近似根后，通常使用某個固定公式反復(fù)校正根的近似值，使之逐步精確化，一直到滿足給定的精度要求為止。迭代法可分為單點迭代法和多點迭代法。設(shè)一元函數(shù)是連續(xù)的，將方程變換為如下的等價形式 （4.3）其中是一個連續(xù)函數(shù)，這樣就得到單點迭代公式， （4.4）給定初值，可得序列。此

11、時稱為迭代函數(shù)，其只依賴于及上以及的各階導(dǎo)數(shù)值，并稱為迭代序列，有時也稱（4.4）為迭代方程（過程，格式）。例如，著名的Newton迭代法，就是單點迭代法的一個具體例子。而多點迭代法的一般形式為， （4.5）為產(chǎn)生迭代序列，需要個初始值，。其中迭代函數(shù)依賴于及這些點上及其各階導(dǎo)數(shù)值。割線法 ，是多點迭代法的一個最簡單的例子。在實踐中，有些迭代法其迭代函數(shù)是隨迭代次數(shù)發(fā)生改變的，一般稱這樣的迭代法為非定常迭代。而對應(yīng)地，上述單點和多點迭代法稱為定常迭代。因此，迭代法的最一般形式為 （4.6）我們將要考慮的求的根的方法都屬于這種形式。對于定常迭代，而對于單點迭代。 4.3.2 不動點迭代法與全局收

12、斂性定義4.5 若滿足，則稱為的不動點（或固定點）。此時，我們稱（4.4）式為不動點迭代法。顯然，若等價于，則的不動點也是方程的根。定義4.6 如果對于任意的，由（4.4）式產(chǎn)生的序列有極限，即，則稱迭代方程（4.4）收斂。下面先討論一般的不動點和不動點迭代法的一些性質(zhì)。定義4.7 若存在常數(shù)，使對任何有則稱在上滿足Lipschitz（利普希茨）條件，稱為Lipschitz常數(shù)。 顯然，若在上滿足Lipschitz條件，則在上連續(xù)。若在上一階導(dǎo)數(shù)存在且有界，則在上滿足Lipschitz條件。定理4.4（不動點存在性定理） 設(shè)滿足以下兩個條件：（1）對任意，有；（2）在上滿足Lipschitz條

13、件，且Lipschitz常數(shù)；則在上存在唯一的不動點。證明：先證明不動點的存在性，記，由定理條件有及，若有一等號成立，則或，即有不動點，否則必有，因，則必有使，即為的不動點。再證明唯一性，設(shè)都是的不動點，且，則與假設(shè)矛盾，這表明，即不動點是唯一的。證畢推論1 若定理4.4中的條件（2）改為，且，則定理結(jié)論依然成立。證明：這只要利用下式即可證明，其中，定理4.5（不動點迭代法的全局收斂性定理） 設(shè)滿足定理4.4中的兩個條件，則對任意的，由（4.4）式生成的迭代序列收斂到在上的不動點，且對整數(shù)有 （4.7） （4.8） （4.9） （4.10）證明：由定理4.4知在上存在唯一的不動點，下面先證明由

14、（4.4）式生成的迭代序列收斂到的唯一不動點。由于，故，再由Lipschitz條件得因為，故，即。由Lipschitz條件及遞推關(guān)系得即證得（4.7），再由 及遞推可得（4.8），在（4.7）中令即得（4.9），在（4.8）中令即得（4.10）。證畢 推論2 若定理4.5中的條件（2）改為，且，則定理結(jié)論依然成立，且有 （4.11）證明：只需證明（4.11）。由微分中值定理及迭代公式有其中介于和之間。從而有，對上式兩端取極限，并注意到即得（4.11）式。證畢估計式（4.7），（4.8）和式（4.11），分別被稱為誤差后驗估計式（誤差事后估計式）、誤差先驗估計式（誤差事前估計式）和誤差漸進估計式

15、。由定理4.5可以看出，的大小與迭代的收斂速度有關(guān)。越小，收斂速度越快；若很接近于1，則收斂可能很慢。在實際計算中，對于給定的容許誤差，當(dāng)較小時，常以前后兩次迭代值與滿足來終止迭代，并取；也可以采用，從而可確定迭代次數(shù)應(yīng)取 （4.12）定理4.6 設(shè)在上有不動點，且當(dāng)時，有，則對任意初值且，迭代公式發(fā)散。證明：由且知如果，則有 如此繼續(xù)下去，或者不屬于，或者，因而迭代序列不可能收斂于。證畢例4.3解方程。解：不難驗證方程在有一個根。用不同的方法構(gòu)造形式的等價方程，從而就有不同的迭代公式。方法1：方程變換為，迭代公式為。設(shè)，則，。由定理4.6知迭代式發(fā)散的。方法2：方程變換為，迭代公式為。設(shè)，可

16、以驗證，對所有成立。取，有，。方法3：取，對所有，有，取，有，。4.3.3 局部收斂性和收斂階定理4.5和4.6討論了迭代法在區(qū)間上的收斂性，我們稱之為全局收斂性，全局收斂性也包括在無窮區(qū)間上收斂的情形。但是很多情況下全局收斂的情形不容易檢驗，為此我們通?？疾煸诟浇氖諗啃詥栴}。定義4.8 設(shè)在區(qū)間內(nèi)有不動點，若存在的某個鄰域，對任意初值，迭代公式產(chǎn)生的迭代序列，且收斂到，則稱迭代法局部收斂。定理4.7（不動點迭代法的局部收斂性定理） 設(shè)為的不動點，且在的某個鄰域內(nèi)，存在一階連續(xù)的導(dǎo)數(shù)，則（1）當(dāng)時，迭代法局部收斂；（2）當(dāng)時，迭代法發(fā)散。證明：（1）設(shè)，由于在附近是連續(xù)的，對于，存在適當(dāng)小

17、的，當(dāng)時，有由上式得 又對如上選擇的，對一切有 因而在區(qū)間內(nèi)定理4.4的兩個條件滿足，因而迭代法是局部收斂的。（2）設(shè)，則在的某個鄰域內(nèi)有，由定理4.6知迭代法發(fā)散。證畢定理4.7對初值的要求較高。如果已知的大概位置，為的一個較好的近似值，則可用代替，用代替，然后應(yīng)用定理4.7判斷迭代法的局部斂散性。迭代法產(chǎn)生的迭代序列的收斂速度是衡量方法好壞的重要標(biāo)志之一，為此我們引入收斂階的概念。定義4.9 設(shè)序列收斂到，記誤差（1）若存在常數(shù)和，使得 （4.13）則稱為階收斂，稱為漸進誤差常數(shù)。當(dāng)時分別稱線性收斂和平方收斂，當(dāng)時稱為超線性收斂。如果由迭代函數(shù)產(chǎn)生的序列是階收斂，則稱為階迭代函數(shù)，并稱迭代

18、法是階收斂。（2）若存在常數(shù)和（當(dāng)時規(guī)定），及正整數(shù)，當(dāng)時有 （4.14）則稱至少階收斂。（3）若存在實數(shù)及正整數(shù)，當(dāng)時有，或者 （4.15）則稱為超階收斂。定義中的漸進誤差常數(shù)與有關(guān)。的要求是指對一般的函數(shù)，保證了的唯一性。若迭代法階收斂，則時必有，但時并不要求小于1；若，則可以肯定方法具有局部收斂性，對于卻并不如此。若階收斂，則它顯然是至少階收斂和超階收斂的。需要指出的是，收斂階的概念仍是一個局部性質(zhì)，它刻畫了方法接近于收斂時的誤差下降的快慢。一般來說，越大，收斂就越快。定理4.8（收斂階定理） 設(shè)為的不動點，整數(shù)，在的某鄰域上連續(xù)，其滿足， （4.16）則由產(chǎn)生的序列在的某鄰域內(nèi)是階收斂

19、，且有 （4.17）如果，要求。證明：由及定理4.7可知迭代法是局部收斂的。將在處作泰勒（Taylor）展開，并利用（4.16）得 亦即 其中在和之間。由于，于是由此得（）由收斂階的定義即得定理結(jié)論。證畢例4.4 考察例4.3的方法二和方法三的收斂階。解：（1）方法二中，則，所以它是一階收斂的。（2）方法三中，解得，所以它也是一階收斂的。4.3.4 計算效率利用收斂階的概念，可以比較不同迭代法的收斂速度，但不能說明方法的計算效率，即達到根的指定精度所需要計算量的大小。為此，需要給出刻畫方法計算效率高低的概念。設(shè)用兩個不同的迭代法求解的根，并假設(shè)兩種方法都從相同的初始近似值出發(fā)。又設(shè)兩種方法分別

20、是階與階，漸進誤差常數(shù)為與，則當(dāng)接近于收斂時，有近似關(guān)系式， （4.18）其中分別表示兩種迭代法的迭代誤差，且。由（4.18）式得 ，記， （4.19）于是得差分方程 ， （4.20）這兩個差分方程的解分別為 ， （4.21）其中初始值。設(shè)兩個迭代法達到同一收斂程度所需的步數(shù)分別為和，則有，即。于是由（4.21）式得 （4.22）若記和分別為兩個迭代法每次迭代所需的計算量，則這兩個迭代法的總計算量分別為和。于是比較這兩個方法的計算效率，也就是比較和。量和都能由迭代函數(shù)估計出來，但（4.22）式并未給出和以明顯的關(guān)系。但是，若假設(shè)（4.22）式中的第二項與第一項相比為?。ɡ绠?dāng)與都接近于1時），

21、這往往是一個好的假設(shè)，此時有 （4.23）亦即 （4.24）于是，可以定義效率指數(shù)為或更普遍定義為。于是，在比較不同的迭代法的計算效率時，就可以考慮這些方法的效率指數(shù)，越大，方法的計算效率就越高（在特殊情況下（4.22）式能直接用來估計）。由于上述推導(dǎo)過程中的方法的階是局限于根的鄰域的一個性質(zhì)，所以效率指數(shù)只表示當(dāng)方法接近于收斂時它有多好，在根的鄰域外確定方法的效率一般是困難的。對于一般的，比較不同迭代法的計算效率時，每次迭代的計算量主要依賴于每次迭代所需及其導(dǎo)數(shù)的計算次數(shù)，而不依賴于迭代函數(shù)組合這些量時所需的算術(shù)運算。§4.4 迭代加速收斂的方法由收斂階定理4.8，我們可以看到，迭

22、代法的收斂速度和迭代函數(shù)有關(guān)。在很多情況下，可由構(gòu)造出一個新的迭代函數(shù)，使（1）方程和具有相同的根；（2）由迭代公式產(chǎn)生的迭代序列收斂于的階高于由產(chǎn)生的迭代序列收斂于的階。上述由一個迭代公式產(chǎn)生一個收斂較快的迭代公式的方法通常稱為加速法。另一方面，對于收斂的迭代法，理論上只要迭代足夠多次，總可以得到滿意的精度；但是有時迭代過程過于緩慢，計算量極大，實際上得不到滿意的計算結(jié)果。因此，對一個迭代法進行加速就成為一個很有必要的研究課題。4.4.1 加權(quán)法（松弛法）設(shè)是精確解的某個預(yù)測值，用迭代公式校正一次，得到。假設(shè)，則在求根范圍內(nèi)改變不大，可近似記為，則有解出： 由此可見，若把誤差值作為計算結(jié)果的

23、一種補充，即記 那么，應(yīng)比近似得更好。這樣，對于每一步的加速迭代方案可以表述如下：迭代：改進：上面的改進可以看作是迭代值和的加權(quán)平均。從下面例子可以看出，這種加速過程，效果是比較明顯的。例4.5 求方程在附近的一個根。解：過以為步長搜索一次，可發(fā)現(xiàn)所求根在區(qū)間內(nèi)。迭代函數(shù)，因為，所以由定理4.7知局部收斂。迭代18次，可得。另一方面，因為，取，則加速公式可表述為迭代過程如下表：01230.500000.566580.567120.56714即此時只要迭代三次便可得到前一種迭代方法的結(jié)果，加速效果是明顯的。4.4.2 艾特肯（Aitken）加速方法在前面的加速方案中，要用到，而在實際應(yīng)用中常常會

24、遇到導(dǎo)數(shù)估計不太容易等困難，因此，要設(shè)法把這個“L”去掉。仍設(shè)是的某個預(yù)測值，校正一次，得，再校正一次得。由于兩式相除得 解出： 這就是說，把誤差值作為的一種補償，補償后的結(jié)果應(yīng)比近似得更好些。作為一般步驟，它的具體方案如下：迭代： ；再迭代：改進： 這種方法稱為Aitken加速方法。設(shè)為的精確解，依然記，利用微分中值定理可得其中在和之間，通常依賴于。若變化不大，設(shè)，于是有 ，從上面兩式消去，則有 或解得 引入差分記號，記 ， （4.25）則是新的一個近似值，利用（4.25）構(gòu)造的方法稱為Aitken加速方法。定理4.9 設(shè)有序列，存在滿足，即，且，則由（4.25）確定的對充分大的都存在，且有

25、。證明：其中，因，所以當(dāng)充分大時，故由（4.25）產(chǎn)生的序列是完全確定的，且 對充分大的成立，所以有 推論：設(shè)有序列，且有，則由（4.25）確定的對充分大的都存在，且有。證明：這只要注意到：由可得，即可。上述定理及推論說明了序列比收斂更快，通常用Aitken加速方法來加速具有線性收斂序列的收斂速度。4.4.3 斯蒂芬森（Steffensen）迭代法Aitken加速方法不管原序列是怎樣產(chǎn)生的，對進行加速計算得到序列。如果我們把關(guān)于函數(shù)的不動點迭代和加速技巧結(jié)合起來，就可以得到如下的Steffensen迭代法：， （4.26）從（4.26）式可以看到，Steffensen迭代法實際上是將原不動點迭

26、代計算兩次合并成一步得到的，因此我們可將Steffensen迭代法寫成另一種不動點迭代法：， （4.27）其中 （4.28）定理4.10 若為（4.28）所定義的函數(shù)的不動點，則為的不動點；反之，若為的不動點，設(shè)存在且連續(xù)，則為的不動點。證明：設(shè)為的不動點，將代入，若分母，則有。若，則有，代入（4.28）的分子得，所以為的不動點。設(shè)為的不動點，以代入（4.28）右端是一個不定式，利用條件及LHospital法則有若定理4.10中的條件不滿足，即是方程的重根，也可以證明。定理4.11 對迭代法，是的不動點，在的鄰域內(nèi)有次導(dǎo)數(shù)存在。對，若，則Steffensen方法是二階的。若是階收斂的，則Ste

27、ffensen方法是階收斂的。證明：（略）若且，即是方程的重根，則可證明Steffensen方法是一階的，漸近常數(shù)。在定理4.11中，當(dāng)，且時表示，若收斂只能是一階收斂的；若，則一定發(fā)散。但這兩種情形下，Steffensen方法都是二階收斂的。這也就是說Steffensen方法不但可以提高收斂速度，有時也能把不收斂的方法改進為收斂的方法。也可以證明，對于的情形，Steffensen方法一般好處不大，所以它主要用于加速線性收斂的方法。例4.6 關(guān)于方程，例4.3給出了三種迭代法。（其中方法一發(fā)散，方法三是一階收斂的）對方法一，對它用Steffensen方法加速，計算得（，），。對方法三，也對它用

28、Steffensen方法加速得021.751.897959211.84294871.83703291.840679621.8392889這里用同樣的初值，迭代2次就得到例4.3迭代20次才得到的結(jié)果。§4.5 Newton迭代法用迭代法求方程的根時，首先要把它寫成等價形式，而迭代函數(shù)構(gòu)造的好壞，不僅影響收斂速度，而且迭代過程也有可能發(fā)散。那么怎樣選擇一個迭代函數(shù)才能夠保證迭代序列一定收斂呢？構(gòu)造迭代函數(shù)的一條重要途徑是用近似方程來代替原方程求根。因此如果能將非線性方程用線性方程來代替，那么求近似根問題就容易解決了。Newton迭代法就是把非線性方程線性化的一種方法。4.5.1 New

29、ton迭代法及其收斂性Newton迭代法的基本思路是將非線性方程逐步線性化而形成的迭代公式。設(shè)是的一個近似根，將函數(shù)在處作一階Taylor展開，即若上式右端最后一項忽略不計，則得到如下近似方程 設(shè)，則可解得取作為原方程新的近似根，即令， （4.29）稱（4.29）為Newton迭代過程（方程或格式），用Newton迭代過程求方程根的方法稱為Newton迭代法，簡稱為Newton法。Newton迭代法有時也稱為Newton-Raphson(牛頓-拉夫申)迭代法。Newton迭代法的另一種來歷：用簡單迭代法求方程的根，特別重要的是構(gòu)造迭代函數(shù)。為了使收斂速度的階高一些，應(yīng)盡可能使在處有更多階導(dǎo)數(shù)等

30、于零?，F(xiàn)在令，為待定函數(shù)，但，則方程與方程有共同的根?，F(xiàn)用來確定，由可知，必須滿足。顯然，取就具備這個條件，并且也滿足。Newton迭代法的幾何意義是作曲線在點的切線方程該方程與軸交點的橫坐標(biāo)就是方程根的新的近似值，所以Newton法又常稱為（Newton）切線法。將Newton迭代法寫成一般的不動點迭代的形式，有 （4.30） （4.31）從而有，即Newton迭代法是超線性收斂的。一般地，關(guān)于Newton法的收斂性有以下的局部收斂定理定理4.12 設(shè)，在附近二階導(dǎo)數(shù)連續(xù)，則Newton迭代法至少是二階收斂的，且有 （4.32）證明：由（4.31）式可知，而，由收斂階定理4.8可知，Newt

31、on迭代法至少二階收斂，由（4.17）式立即可得（4.32）式。證畢一般來說，Newton法對初值的要求較高，初值足夠靠近時才能保證收斂。若要保證初值在較大范圍內(nèi)收斂，還需對加一些條件。例如下面的定理就給出了一個充分條件。定理4.13 設(shè)函數(shù)在區(qū)間內(nèi)存在二階連續(xù)導(dǎo)數(shù)，且滿足條件：（1）；（2）當(dāng)時，；（3）當(dāng)時，不變號；（4），；則對任意的初值，由Newton迭代法（4.29）式產(chǎn)生的迭代序列二階收斂到方程在內(nèi)的唯一的單根。證明：由條件（1）（2）知方程在內(nèi)存在唯一的根。根據(jù)條件（2）（3）可將函數(shù)分為如下四種情況：（1）；（2）；（3）；（4）下面僅對情況（1）分3步進行證明，其它情況可類似

32、證明。第1步 當(dāng)時，由（4.29）式知（），則序列為常數(shù)序列，收斂性是顯然的。第2步 當(dāng)時，；另一方面又有其中。由于，所以，由上式得，從而有。類似地，若，同理可得，因而序列單調(diào)下降并以為下界，故序列收斂。記，則，在（4.29）兩邊取極限得，解得，又方程只有一個根，所以，即。第3步 當(dāng)時，由得，即。另一方面，由及，有其中。由，及條件（4），得，從而有，把看作新的迭代初值就歸結(jié)為前兩步證明的情況。證畢例4.7 用Newton法求方程的根。解：，Newton迭代為，取，得，即為根的近似，與例4.5相比，它表明Newton法收斂很快。例4.8 用Newton迭代法建立求平方根的迭代式并分析收斂性。解：

33、作函數(shù)，則的正根就是，由（4.29）式得 （4.33）這是在計算機上做開方運算的一個實際有效的方法，它每步迭代只作一次除法和一次加法在做一次移位即可，計算量少，收斂又快。當(dāng)時有，故由定理4.12知，對任意的初值，迭代（4.33）均收斂于。事實上，若，則不難驗證有，即，一般地可證明，即從起是一個單調(diào)遞減有下屆的數(shù)列，從而必有極限，在（4.33）中令可得。另一方面，由（4.33）右端進行配方可得，兩式相除得 由此反復(fù)遞推有 令，則有上式得，對任意的，總有，故有。 4.5.2 求重根的修正Newton法設(shè)是的重根，即，其中，有二階導(dǎo)數(shù)，計算的導(dǎo)數(shù)可得從而有。當(dāng)時，這樣Newton法只是線性收斂的。若

34、重數(shù)已知，將迭代函數(shù)改為，則，故迭代法， （4.33）至少二階收斂。在實際使用中，由于根的重數(shù)一般是未知的。令，可以證明若為的重根，則為的單根。對用Newton法，迭代函數(shù)為 （4.34）從而可構(gòu)造迭代法 ， （4.35）可證明上述方法至少二階收斂。下面簡要敘述根的重數(shù)的計算。設(shè)為的重根，則，于是記 則 令，得到 令，得到 例4.9 方程的根是二重根，使用Newton法及（4.33）、（4.35）各計算三步。解：，（1）Newton法：，（2）迭代法（4.33）：，（3）迭代法（4.35）：，三種方法均取，計算結(jié)果如下表：方法（1）方法（2）方法（3）1.4583333331.41666666

35、71.4147647061.4366071431.4142156861.4142114381.4254976191.4142135621.414213562方法（2）和（3）都是二階方法，都達到了的精確度，而普通的Newton法（方法（1）是一階的，要達到相同精度需要迭代30次。4.5.3 簡化Newton法應(yīng)用Newton迭代過程（4.29）時需要計算，如果遇到的問題很難計算，有時改用下面修正的迭代過程：， （4.36）其中是某一常數(shù)。過程（4.36）稱為簡化Newton法。由收斂階定理4.8可知，除非，這時（）簡化Newton法是二階收斂的，否則（4.36）是線性收斂的，但若能取的較好近似

36、值，則收斂還是較快的。的一種選取是取，此時（4.36）化為， （4.37）這個公式的幾何意義是用過點且斜率為的直線 來代替曲線，取該直線與軸交點的橫坐標(biāo)作為根新的近似值，因此該方法有時也稱為平行弦法。 4.5.4 Newton下山法Newton迭代法是一種局部收斂方法，通常要求初值在解的附近才能保證迭代序列收斂。為了擴大收斂范圍，使對任意的初值迭代序列都收斂（即放寬初值的選擇范圍），通常可引入?yún)?shù)，并將Newton迭代法改為， （4.38）其中，稱為下山因子，（4.38）式稱為Newton下山法。通?？蛇x擇使，計算時可取直到滿足要求為止。由此得到的序列由于滿足下山條件，故它總是收斂的，但它只是

37、線性收斂的。Newton下山法可以看成是由Newton法的計算結(jié)果與前一步的計算結(jié)果作加權(quán)平均后再作為新的近似值而得到，即 （4.39） Newton下山法計算步驟：（1）選取初值；（2）去下山因子；（3）計算及；（4）比較與1）若，則當(dāng)，取，終止迭代；當(dāng)， 增加1，轉(zhuǎn)（3）。2）若，則當(dāng)，而，取，終止迭代；當(dāng)，而，取代轉(zhuǎn)（3）（為一小正數(shù)）；當(dāng)，而，取代替，轉(zhuǎn)（3）。例4.10 用Newton下山法求的解，取，計算精確到。解：由于，從而Newton下山法為，若用Newton法（）迭代3次則求得解的近似值?，F(xiàn)取，則得，不滿足下山條件。通過試算，當(dāng)時，滿足，以下計算時參數(shù)，且4.5.5 擬Newton法和Steffensen方法在Newton法中，如果用代替就得到擬Newton法： ，如果用代替就得到Steffensen方法：，可以證明擬Newton法和Steffe