第三章 方程(組)的迭代解法

1、3 方程（組）的迭代解法方程（組）的迭代解法 3.1 3.1 引言引言0)(xf（3.1.1） 本章主要討論求解單變量非線性方程本章主要討論求解單變量非線性方程 其中 也可以是無窮區(qū)間. ,)(,RbabaCxfx 如果實(shí)數(shù) 滿足 ，則稱 是方程(3.1.1)的根根，或稱 是 的零點(diǎn)零點(diǎn).*x)(xf0*)(xf*x*x1 1根的存在性。方程有沒有根？如果有，有幾個根？根的存在性。方程有沒有根？如果有，有幾個根？2 2根的搜索。這些根大致在哪里？如何把根隔離開？根的搜索。這些根大致在哪里？如何把根隔離開？3 3根的精確化（誤差）。根的精確化（誤差）。問題問題: : 公元前1700年的古巴比倫人

2、就已有關(guān)于一、二次方程的解法。 九章算術(shù)(公元前50100年)其中“方程術(shù)”有聯(lián)立一次方程組的一般解法。 1535年意大利數(shù)學(xué)家尼柯洛馮塔納找到了一元三次方程一般形式的求根方法。這個成就，使他在幾次公開的數(shù)學(xué)較量中大獲全勝，從此名揚(yáng)歐洲。但是馮塔納不愿意將他的這個重要發(fā)現(xiàn)公之于世. 當(dāng)時的另一位意大利數(shù)學(xué)家兼醫(yī)生卡爾丹諾，對馮塔納的發(fā)現(xiàn)非常感興趣。他幾次誠懇地登門請教，希望獲得馮塔納的求根公式。后來，馮塔納終于用一種隱晦得如同咒語般隱晦得如同咒語般的語言，把三次方程的解法“透露”給了卡爾丹諾。馮塔納認(rèn)為卡爾丹諾很難破解他的“咒語”，可是卡爾丹諾通過解三次方程的對比實(shí)踐，很快就徹底破譯了馮塔納的

3、秘密。 卡爾丹諾把馮塔納的三次方程求根公式，寫進(jìn)了自己的學(xué)術(shù)著作大法大法中，但并未提到馮塔納的名字。 由于第一個發(fā)表三次方程求根公式的人確實(shí)是卡爾丹諾，因此后人就把這種求解方法稱為“卡爾丹諾公式”。 l后來，卡爾丹諾的學(xué)生弗瑞里(Ferrari)又提出了四次方程的解法。l但對于五次方程求根，求索工作始終沒有成效，導(dǎo)致人們對高次代數(shù)方程解的存在性產(chǎn)生了懷疑。l1828年17歲的法國數(shù)學(xué)家伽羅華(EGalois 1811-1832)寫出了劃時代的論文“關(guān)于五次方程的代數(shù)解法問題”，指出即使在公式中容許用n次方根，并用類似算法求五次或更高次代數(shù)方程的根是不可能的l 文章呈交法蘭西科學(xué)院后，因輩份太低

4、遭到冷遇，且文稿丟失。1830年伽羅華再進(jìn)科學(xué)院遞稿，得到泊松院士的判詞“完全不能理解完全不能理解”。l 后來伽羅華命運(yùn)不佳，投考名校巴黎工科大學(xué)落榜，屈就高等師院，并卷入政事兩次入獄，被開除學(xué)籍，又決斗受傷，死于1832年。決斗前，他把關(guān)于五次代數(shù)求解的研究成果寫成長信，留了下來。l 十四年后，法國數(shù)學(xué)家劉維爾(JLiouville)整理并發(fā)表了伽羅華的遺作，人們才意識到這項(xiàng)近代數(shù)學(xué)發(fā)展史上的重要成果的寶貴。l38年后，即1870年，法國數(shù)學(xué)家若當(dāng)(CJordan)在專著論置換與代數(shù)方程中闡發(fā)了伽羅華的思想，一門現(xiàn)代數(shù)學(xué)的分支 群論群論誕生了。l在前幾個世紀(jì)中，曾開發(fā)出一些求解代數(shù)方程的有效

5、算法，它們構(gòu)成了數(shù)值分析中的古典算法。至于超越方程則不存在一般的求根方式。1.1.根的存在性根的存在性定理定理1：設(shè)函數(shù)設(shè)函數(shù) f (x) 在區(qū)間在區(qū)間a, b上連續(xù)上連續(xù)，如果如果f (a) f (b) 0， 則方程則方程 f (x) = 0 在在a, b內(nèi)至少有一實(shí)根內(nèi)至少有一實(shí)根x*。 定義定義：如果存在如果存在 使得使得 ，則稱，則稱 為為方程（方程（3.1.13.1.1）*x0)(*xf的根的根或或函數(shù)函數(shù) 的零點(diǎn)的零點(diǎn)。)(xf*x0)(xf（3.1.1）m m重根重根若若)()()(*xgxxxfm其中，其中，mxg, 0)(*為正整數(shù)，為正整數(shù)，則當(dāng)則當(dāng)m=1m=1時，時，稱稱

6、 為為方程（方程（3.1.13.1.1）*x的的 m m重根重根或或函數(shù)函數(shù) 的的m m重零點(diǎn)。重零點(diǎn)。)(xf2m的單根的單根或或函數(shù)函數(shù) 的單零點(diǎn)的單零點(diǎn)。)(xf稱稱 為為方程（方程（3.1.13.1.1）*x當(dāng)當(dāng) 時時，0)(xf（3.1.1）2. 根的搜索根的搜索(1) 圖解法（利用作圖軟件如圖解法（利用作圖軟件如 Matlab)(2) 掃描法（逐步搜索法）掃描法（逐步搜索法）(3) 二分法二分法* （1） (描描)做圖法做圖法 畫出畫出 y=f(x) 的草圖的草圖, 由由f(x)與橫軸交點(diǎn)的大概位置與橫軸交點(diǎn)的大概位置來確定來確定隔根區(qū)間隔根區(qū)間; 或者利用導(dǎo)函數(shù)或者利用導(dǎo)函數(shù)f

7、(x)的正、負(fù)與函的正、負(fù)與函數(shù)數(shù)f(x)的單調(diào)性的關(guān)系確定根的大概位置的單調(diào)性的關(guān)系確定根的大概位置. 若若f(x)比較復(fù)雜比較復(fù)雜, 還可將方程還可將方程f(x)=0化為一個等價化為一個等價方程方程 (x)= (x), 則曲線則曲線y= (x)與與y= (x)之之交點(diǎn)交點(diǎn)A(x*,y*)的的橫坐標(biāo)橫坐標(biāo) x*即為原方程之根即為原方程之根, 據(jù)此也可通過作圖求得據(jù)此也可通過作圖求得x*的的隔根區(qū)間隔根區(qū)間. 10 xxxyxy1lgxx1lgxy1gxy 023yxabx*f(x)0 x1畫出畫出 f(x) 的略圖，從而看出曲線與的略圖，從而看出曲線與x 軸交點(diǎn)的位置。軸交點(diǎn)的位置。2從左端

8、點(diǎn)從左端點(diǎn)x = a出發(fā)，按某個預(yù)先選定的步長出發(fā)，按某個預(yù)先選定的步長h一步一步地向右跨，每跨一步都檢驗(yàn)每步起點(diǎn)一步一步地向右跨，每跨一步都檢驗(yàn)每步起點(diǎn)x0和終點(diǎn)和終點(diǎn)x0 + h的函數(shù)值，若的函數(shù)值，若0)()(00hxfxf那么所求的根那么所求的根x*必在必在x0與與x0+h之間，這里可取之間，這里可取x0或或x0+h作為根的初始近似。作為根的初始近似。hx 0(2) 掃描法（逐步搜索法）掃描法（逐步搜索法）例例1 1：考察方程：考察方程01)(3xxxfx00.51.01.5f (x) 的符號的符號（3） 二分法二分法*（對分法）（對分法） 設(shè)設(shè)f(x)在區(qū)間在區(qū)間a, b上連續(xù)上連續(xù)

9、, f(a)f(b)0, 則在則在a, b 內(nèi)有方程的根內(nèi)有方程的根. 取取a, b的中點(diǎn)的中點(diǎn) 將區(qū)間一分為二將區(qū)間一分為二. 若若 f (x0)=0, 則則x0就是方程的根就是方程的根, 否則判別根否則判別根 x*在在 x0 的的左側(cè)左側(cè)還是還是右側(cè)右側(cè)., )(210bax 若若f(a) f(x0)0, 則則x*(a, x0), 令令 a1= a, b1=x0;若若f(x0) f(b)0, 則則x*(x0 , b), 令令 a1=x0, b1=b. . 不論出現(xiàn)哪種情況不論出現(xiàn)哪種情況, (a1, b1)均為均為新的有根區(qū)間新的有根區(qū)間, 它它的的長度只有原有根區(qū)間長度的一半長度只有原有

10、根區(qū)間長度的一半, 達(dá)到了達(dá)到了壓縮有根壓縮有根區(qū)間區(qū)間的目的的目的. 對壓縮了的有根區(qū)間對壓縮了的有根區(qū)間, 又可實(shí)行同樣的步驟又可實(shí)行同樣的步驟, 再壓再壓縮縮. 如此反復(fù)進(jìn)行如此反復(fù)進(jìn)行, 即可的一系列即可的一系列有根區(qū)間套有根區(qū)間套 ,11nnbababa 由于每一區(qū)間都是前一區(qū)間的一半，因此區(qū)間由于每一區(qū)間都是前一區(qū)間的一半，因此區(qū)間an , bn的長度為的長度為)(ababnnn 21若每次二分時所取區(qū)間中點(diǎn)都不是根，則上述過程將若每次二分時所取區(qū)間中點(diǎn)都不是根，則上述過程將無限進(jìn)行下去無限進(jìn)行下去. 當(dāng)當(dāng) n 時，區(qū)間必將最終收縮為一時，區(qū)間必將最終收縮為一點(diǎn)點(diǎn)x* ，顯然，顯然

11、x*就是所求的就是所求的根根.誤差誤差 分析：分析：第第1步產(chǎn)生的步產(chǎn)生的21bax 有誤差有誤差21abx*|x 第第 k 步產(chǎn)生的步產(chǎn)生的 xk 有誤差有誤差kkabx*|x2 對于給定的精度對于給定的精度 ,可估計(jì)二分法所需的步數(shù)可估計(jì)二分法所需的步數(shù) k ： 2lnlnln2abkabk 簡單簡單; 對對f (x) 要求不高要求不高(只要連續(xù)即可只要連續(xù)即可) .無法求復(fù)根及偶重根無法求復(fù)根及偶重根 收斂慢收斂慢 2.由于在偶重根附近曲線由于在偶重根附近曲線 y=f(x) 為上凹或下凸為上凹或下凸, 即即 f(a)與與f(b)的符號相同的符號相同, 因此因此不能用二分法求偶重根不能用二

12、分法求偶重根.用二分法求根，最好先給出用二分法求根，最好先給出 f (x) 草圖以確定根草圖以確定根的大概位置?；蛴盟阉鞒绦颍瑢⒌拇蟾盼恢??；蛴盟阉鞒绦?，將a, b分為若干小分為若干小區(qū)間，對每一個滿足區(qū)間，對每一個滿足 f (ak)f (bk) 0 的區(qū)間調(diào)用二的區(qū)間調(diào)用二分法程序，可找出區(qū)間分法程序，可找出區(qū)間a, b內(nèi)的多個根，且不必內(nèi)的多個根，且不必要求要求 f (a)f (b) 0 。 二分法的執(zhí)行步驟二分法的執(zhí)行步驟1計(jì)算計(jì)算f (x)在有解區(qū)間在有解區(qū)間a, b端點(diǎn)處的值端點(diǎn)處的值，f (a)，f (b)。2計(jì)算計(jì)算f (x)在區(qū)間中點(diǎn)處的值在區(qū)間中點(diǎn)處的值f (x1)。3判斷若

13、判斷若f (x1) = 0，則則x1即是根，否則檢驗(yàn)即是根，否則檢驗(yàn)：（1）若若f (x1)與與f (a)異號異號，則知解位于區(qū)間則知解位于區(qū)間a, x1， b1=x1, a1=a;（2）若若f (x1)與與f (a)同號同號，則知解位于區(qū)間則知解位于區(qū)間x1, b， a1=x1, b1=b。反復(fù)執(zhí)行步驟反復(fù)執(zhí)行步驟2、3，便可得到一系列有根區(qū)間便可得到一系列有根區(qū)間：1122 , ,nna ba ba ba b4、當(dāng)當(dāng)11kkab時，停止；時，停止；)(211kkkbax即為根的近似。即為根的近似。當(dāng)當(dāng) n 時，時， 0nnba，即這些區(qū)間必將收縮于一點(diǎn)，也就是，即這些區(qū)間必將收縮于一點(diǎn)，也

14、就是方程的根。在實(shí)際計(jì)算中，只要方程的根。在實(shí)際計(jì)算中，只要 ,nna b的區(qū)間長度小于預(yù)定容的區(qū)間長度小于預(yù)定容許誤差許誤差就可以停止搜索，即就可以停止搜索，即 2nba然后取其中點(diǎn)然后取其中點(diǎn) nx作為方程的一個根的近似值。作為方程的一個根的近似值。 注：注： 例例2 證明方程證明方程 1020 xex存在唯一的實(shí)根存在唯一的實(shí)根 *(0,1)x 用二分法用二分法 求出此根，要求誤差不超過求出此根，要求誤差不超過 20.5 10。解：記解：記 ( )102xf xex，則對任意，則對任意 xR( )100 xfxe ，因而，因而， ( )f x是嚴(yán)格單調(diào)的，是嚴(yán)格單調(diào)的， ( )0f x

15、最多有一個根，最多有一個根，(0)10,(1)80ffe 所以，所以， ( )0f x 有唯一實(shí)根有唯一實(shí)根 *(0,1)x 又因?yàn)橛忠驗(yàn)?用二分法求解，要使用二分法求解，要使 *20.5 10kxx，只要，只要 21100.5 102k解得解得 26.64lg2k ，取，取 7k 。所以只要二等分。所以只要二等分7次，即可求得滿次，即可求得滿足精度要求的根。計(jì)算過程如下表所示足精度要求的根。計(jì)算過程如下表所示 k f(ak)及符號及符號f(xk)及符號及符號f(bk)及符號及符號01234 5670()0()0()0()0.0625()0.0625()0.078125()0.0859375(

16、)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( + )表表3.1所以，所以， *0.5 (0.08593750.09375)0.09x 問題問題 雖然二分法計(jì)算簡單，能夠保證收斂，但是它對于方程雖然二分法計(jì)算簡單，能夠保證收斂，但是它對于方程單根存在區(qū)域信息要求太高，一般情況下很難實(shí)現(xiàn)，并單根存在區(qū)域信息要求太高，一般情況下很難實(shí)現(xiàn)，并且不能求偶重根、復(fù)根和虛根。在實(shí)際應(yīng)

17、用中，用來求且不能求偶重根、復(fù)根和虛根。在實(shí)際應(yīng)用中，用來求解方程根的主要方法是迭代法。解方程根的主要方法是迭代法。使用迭代法求解非線性代數(shù)方程的步驟為：使用迭代法求解非線性代數(shù)方程的步驟為：(1) 迭代格式；迭代格式；(2) 迭代格式的收斂性的構(gòu)造分析；迭代格式的收斂性的構(gòu)造分析；(3) 迭代格式的收斂速度與誤差分析。迭代格式的收斂速度與誤差分析。 3.2 迭代法及其收斂性3.2.1 不動點(diǎn)迭代法不動點(diǎn)迭代法 將方程將方程f(x)=0改寫為等價方程形式改寫為等價方程形式 x= (x). (3.2.1)若要求若要求x*滿足滿足f(x*)=0，則，則x*= (x*)；反之亦然，稱；反之亦然，稱x

18、*為為函數(shù)函數(shù) (x)的一個的一個不動點(diǎn)不動點(diǎn). 求求f(x)的零點(diǎn)就等于求的零點(diǎn)就等于求 (x)的的不動點(diǎn)不動點(diǎn)，選擇一個初始近似值，選擇一個初始近似值x0，將它代入，將它代入(3.2.1)右右端，即可求得端，即可求得 x1= (x0). .lim xxkk可以如此反復(fù)迭代計(jì)算可以如此反復(fù)迭代計(jì)算 xk+1= (xk) (k=0,1,2,). (3.2.2) (x)稱為迭代函數(shù)稱為迭代函數(shù). 如果對任何如果對任何x0a, b，由，由(3.2.2)得得到的序列到的序列xk有極限有極限則稱迭代方程則稱迭代方程(3.2.2)收斂收斂. 且且x*= (x*)為為 (x)的的不動點(diǎn)不動點(diǎn)，故稱故稱(3

19、.2.2)為為不動點(diǎn)迭代法不動點(diǎn)迭代法. 上述迭代法是一種逐次逼近法，其基本思想是將上述迭代法是一種逐次逼近法，其基本思想是將隱式方程隱式方程(3.1.1)歸結(jié)為一組顯式的計(jì)算公式歸結(jié)為一組顯式的計(jì)算公式(3.2.2)，迭代過程實(shí)質(zhì)上是一個逐步顯式化過程迭代過程實(shí)質(zhì)上是一個逐步顯式化過程.當(dāng)當(dāng) (x)連續(xù)時，連續(xù)時，顯然顯然x*就是方程就是方程x= (x)之之根根(不動點(diǎn)不動點(diǎn)). 于是可以從數(shù)列于是可以從數(shù)列xk中求得滿足精度要求的近似根中求得滿足精度要求的近似根. 這種求根方法這種求根方法稱為稱為不動點(diǎn)迭代法不動點(diǎn)迭代法, 1()(0,1,2,)kkxxk 稱為稱為迭代格式迭代格式, (x

20、)稱為稱為迭代函數(shù)迭代函數(shù), x0 稱為稱為迭代初值迭代初值,數(shù)列數(shù)列xk稱為稱為迭代序列迭代序列. 如果迭代序列收斂如果迭代序列收斂, 則稱迭則稱迭代格式代格式收斂收斂,否則稱為否則稱為發(fā)散發(fā)散. 1()(0,1,2,)kkxxk .lim xxkk3.2.2 迭代法的幾何意義迭代法的幾何意義 通常將方程通常將方程f(xf(x)=0)=0化為與它同解的方程化為與它同解的方程的方法不止一種的方法不止一種, ,有的收斂有的收斂, ,有的不收斂有的不收斂, ,這取決于這取決于 的性態(tài)的性態(tài), ,方程方程 的求根問題在幾何上就是確定曲的求根問題在幾何上就是確定曲線線y= 與直線與直線y=x的交點(diǎn)的交

21、點(diǎn)P*的橫坐標(biāo)的橫坐標(biāo))(xx)(x)(xx)(xxyy = xxyy = xxyy = xxyy = xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1例例3：求方程求方程0210)(xxxf的一個根的一個根.210 xxlg(2)xx構(gòu)造迭代格式構(gòu)造迭代格式)2lg(1kkxxx1 = 0.4771x2 = 0.3939x6 = 0.3758x7 =0.3758解：解：1020 xx給定初始點(diǎn)給定初始點(diǎn)10.4771x 03224xxx分別按以上三種形式建立迭代公式，并取分別按以上三種形式建立迭代公

22、式，并取x0=1進(jìn)行進(jìn)行迭代計(jì)算，結(jié)果如下：迭代計(jì)算，結(jié)果如下：14)(2 xxx 32)(243 xxxx 4121)23()(xxxx 解解 對方程進(jìn)行如下三種變形：對方程進(jìn)行如下三種變形： 例例3 用迭代法求方程用迭代法求方程x4+2x2- -x- -3=0 在區(qū)間在區(qū)間1, 1.2內(nèi)的實(shí)根內(nèi)的實(shí)根.準(zhǔn)確根準(zhǔn)確根 x* = 1.124123029, 可見可見迭代公式不同迭代公式不同, 收斂情收斂情況也不同況也不同. 第二種公式比第一種公式收斂快得多第二種公式比第一種公式收斂快得多, 而而第三種公式第三種公式不收斂不收斂.73496,8.49530710 xx12()41kkkxxx 42

23、13()23kkkkxxxx 12411()(32)kkkkxxxx 26271.124123xx671.124123xx 例例3 表明原方程化為表明原方程化為 x= (x) 的形式不同，有的的形式不同，有的收斂，有的不收斂，有的發(fā)散，只有收斂的的迭代收斂，有的不收斂，有的發(fā)散，只有收斂的的迭代過程過程xk+1= (xk) (k=0,1,2,)才有意義，為此我們首先才有意義，為此我們首先要研究要研究 (x)的不定點(diǎn)的存在性及迭代法的不定點(diǎn)的存在性及迭代法xk+1= (xk)的的收斂性收斂性.3.2.3 不動點(diǎn)的存在性與迭代法的收斂性不動點(diǎn)的存在性與迭代法的收斂性 首先考察首先考察 (x)在在a

24、, b上不動點(diǎn)的存在唯一性上不動點(diǎn)的存在唯一性. 定理定理1 設(shè)設(shè) (x)Ca, b滿足以下兩個條件：滿足以下兩個條件：1 對任意對任意xa, b有有a (x)b. .( )( ).(3.2.3)xyL xy2 存在正數(shù)存在正數(shù)La及及 (b)0, f(b)= (b)- -b0, 由連續(xù)函數(shù)性質(zhì)可知存在由連續(xù)函數(shù)性質(zhì)可知存在 x*(a, b) 使使 f(x*)=0，即，即x*= (x*)，x*即為即為 (x)的不動點(diǎn)的不動點(diǎn). 再證不動點(diǎn)的再證不動點(diǎn)的唯一性唯一性. 設(shè)設(shè)x1*, x2*a, b都是都是 (x)的不動點(diǎn)，則由的不動點(diǎn)，則由(3.2.3)得得.)()(21212121 xxxxL

25、xxxx 引出矛盾，故引出矛盾，故 (x)的不動點(diǎn)只能是唯一的的不動點(diǎn)只能是唯一的. .證畢證畢. . 在在 (x)的不動點(diǎn)存在唯一的情況下，可得到迭代的不動點(diǎn)存在唯一的情況下，可得到迭代法法 xk+1= (xk)收斂的一個收斂的一個充分條件充分條件. 定理定理2 設(shè)設(shè) (x)Ca, b滿足定理滿足定理1中的兩個條件，中的兩個條件，則對任意則對任意x0a, b，由，由xk+1= (xk)得到的迭代序列得到的迭代序列xk收斂到的不動點(diǎn)收斂到的不動點(diǎn)x*，并有，并有誤差估計(jì)式誤差估計(jì)式101.(3.2.4)1.(3.2.5)1kkkkkLxxxxLLxxxxL 證明證明 設(shè)設(shè)x*a, b是是 (x

26、)在在a, b上的唯一不動點(diǎn)上的唯一不動點(diǎn), ,由條件由條件1，可知，可知xka, b，再由，再由(3. 2. 3)得得.)()(011xxLxxLxxxxkkkk 因因0L1時稱時稱超線性收斂超線性收斂，p=2時稱時稱平方收斂平方收斂. 定理定理4 對于迭代過程對于迭代過程xk+1= (xk)，如果，如果 ( (p) )(x)在在所求根所求根x*的鄰近連續(xù)，并且的鄰近連續(xù)，并且(1)( )()()()0,()0. (3.2.7)ppxxxx則該迭代過程在則該迭代過程在x*的鄰近是的鄰近是p階收斂的階收斂的. 證明證明 由于由于(x*)=0，根據(jù)定理，根據(jù)定理3立即可以斷定迭立即可以斷定迭代過

27、程代過程xk+1= (xk)具有局部收斂性具有局部收斂性. 再將再將 (xk)在根在根x*處做泰勒展開處做泰勒展開, 利用條件利用條件(3.2.7), 則有則有.,)(!)()()()(之間之間與與在在 xxxxpxxkpkpk 注意到注意到 (xk)=xk+1， (x*)= x*，由上式得，由上式得,)(!)()(1pkpkxxpxx 因此對迭代誤差，令因此對迭代誤差，令k時有時有這表明迭代過程這表明迭代過程xk+1= (xk)確實(shí)為確實(shí)為p階收斂階收斂. 證畢證畢. .!)()(1pxeeppkk 上述定理告訴我們，迭代過程的收斂速度依賴于上述定理告訴我們，迭代過程的收斂速度依賴于迭代函數(shù)

28、迭代函數(shù) (x)的選取的選取. 如果如果x a, b但但 (x)0時，則時，則該迭代過程只可能是線性收斂該迭代過程只可能是線性收斂.)0( aa的三階方法的三階方法. 假設(shè)假設(shè) x0 充分靠近充分靠近 x*, 求求31)(limkkkxaxa 證明證明 首先由泰勒展式可得首先由泰勒展式可得113311limlim()()3!4()kkkkkkaxeaeaax 例子例子 證明迭代公式證明迭代公式 xk+1=xk(xk2+3a)/(3xk2+a)是求是求而而1/4a00，故此故此迭代公式是三階方法迭代公式是三階方法.3.3 迭代收斂的加速方法迭代收斂的加速方法埃特金加速收斂方法埃特金加速收斂方法

29、對于收斂的迭代過程，只要迭代足夠多次，就可對于收斂的迭代過程，只要迭代足夠多次，就可以使結(jié)果達(dá)到任意的精度，但是有時迭代過程收斂較以使結(jié)果達(dá)到任意的精度，但是有時迭代過程收斂較慢，從而使計(jì)算量變得很大，因此迭代過程的加速是慢，從而使計(jì)算量變得很大，因此迭代過程的加速是個重要的課題個重要的課題. 設(shè)設(shè)x0是根是根x*的某個近似值的某個近似值, 用迭代公式校正一次得用迭代公式校正一次得 x1= (x0)而由微分中值定理，有而由微分中值定理，有.),)()()(0001之間之間與與在在xxxxxxxx 假設(shè)假設(shè) (x)改變不大改變不大, 近似地取某個近似值近似地取某個近似值L, 則有則有由于由于 x

30、2- -x*L(x1- -x*).10().(3.3.1)xxL xx 若將校正值若將校正值x1= (x0)再校正一次，又得再校正一次，又得 x2= (x1)將它與將它與(3.3.1)式聯(lián)立，消去未知的式聯(lián)立，消去未知的L，有，有 xxxxxxxx1021由此推知由此推知.2)(201220100122120 xxxxxxxxxxxxx . 0lim1 xxxxkkk在計(jì)算了在計(jì)算了x1及及x2之后，可用上式右端作為之后，可用上式右端作為x*的新近似的新近似,記作記作x1，一般情形是由，一般情形是由xk計(jì)算計(jì)算xk+1, xk+2，記，記它表明序列它表明序列xk的收斂速度比的收斂速度比xk的收

31、斂速度快的收斂速度快.2112122()2()(0,1,).(3.3.2)kkkkkkkkkkxxxxxxxxxkx(3.3.2)式稱為式稱為埃特金埃特金(Aitken) 2加速方法加速方法. 可以證明可以證明也稱為也稱為埃特金埃特金 ( Aitken ) 外推法外推法. 可以證明可以證明:)(1kkxx 為線性收斂為線性收斂,則埃特金法為平方收斂則埃特金法為平方收斂； 這個加速迭代法也可寫成下面格式這個加速迭代法也可寫成下面格式(1)1(2)(1)11(2)(1)2(2)1111(2)(1)11()()()2kkkkkkkkkkkxxxxxxxxxxx 若若)(1kkxx 為為 p ( p

32、1)階收斂，階收斂，)(x 導(dǎo)數(shù)連續(xù)，則埃特金法為導(dǎo)數(shù)連續(xù)，則埃特金法為 2p1 階收斂階收斂.的的 p 階階若若21121()2kkkkkkkxxxxxxx 例題例題 求方程求方程 x = e x 在在 x=0.5 附近的根附近的根. 解解 取取 x0=0.5, 迭代格式迭代格式x25=x26=0.5671433 若對此格式用埃特金法若對此格式用埃特金法, 則則kxkex 1 得得(1)1(1)(2)12(2)(1)2(2)1111(2)(1)11()2kkxxkkkkkkkkkxexexxxxxxx (2)(1)2(2)1111(2)(1)11()2kkkkkkkxxxxxxx 仍取仍取

33、x0=0.5 , 得得5671433. 05671433. 05671433. 05671433. 05672979. 05668708. 05676279. 05452392. 06065307. 03)2(3)1(32)2(2)1(21)2(1)1(1 xxxxxxxxx由此可見由此可見, 埃特金法加速收斂效果是相當(dāng)顯著的埃特金法加速收斂效果是相當(dāng)顯著的.(1)1(1)(2)12kkxxkkxexe 3.4 牛 頓 法3.4.1 牛頓法及其收斂性牛頓法及其收斂性)()()(000 xxxfxfxf 對于方程對于方程f(x)=0，如果，如果f(x)是線性函數(shù)，則它的是線性函數(shù)，則它的求根是容

34、易的求根是容易的. 牛頓法實(shí)質(zhì)上是一種線性化方法，其牛頓法實(shí)質(zhì)上是一種線性化方法，其基本思想是將非線性方程基本思想是將非線性方程f(x)=0逐步歸結(jié)為某種線性逐步歸結(jié)為某種線性方程來求解方程來求解. 設(shè)已知方程設(shè)已知方程f(x)=0有近似根有近似根x0，且在，且在 x0附近附近f(x)可可用一階泰勒多項(xiàng)式近似，表示為用一階泰勒多項(xiàng)式近似，表示為一、牛頓迭代法一、牛頓迭代法當(dāng)當(dāng)f (x0)0時，方程時，方程f(x)=0可用線性方程可用線性方程(切線切線) 近似代近似代替，即替，即 f(x0)+f (x0)(x- -x0)=0. (3.4.1)解此線性方程得解此線性方程得)()(000 xfxfx

35、x 得迭代公式得迭代公式此式稱為此式稱為牛頓牛頓(Newton)迭代公式迭代公式.1()(0,1,),(3.4.2)()kkkkf xxxkfx牛頓法有顯然的牛頓法有顯然的幾何意義幾何意義，方程，方程f(x)=0的根的根x*可可解釋為曲線解釋為曲線y=f(x)與與x軸交點(diǎn)的橫坐標(biāo)軸交點(diǎn)的橫坐標(biāo). 設(shè)設(shè)xk是根是根x*的的某個近似值，過曲線某個近似值，過曲線y=f(x)上橫坐標(biāo)為上橫坐標(biāo)為xk的點(diǎn)的點(diǎn)Pk引切引切線，并將該切線與線，并將該切線與x軸交點(diǎn)的橫坐標(biāo)軸交點(diǎn)的橫坐標(biāo)xk+1作為作為x*的新的的新的近似值近似值. 注意到切線方程為注意到切線方程為這樣求得的值這樣求得的值xk+1必滿足必滿足

36、(3.4.1), 從而就是牛頓公式從而就是牛頓公式(3.4.2)的計(jì)算結(jié)果的計(jì)算結(jié)果. 由于這由于這種幾何背景，所以牛頓迭種幾何背景，所以牛頓迭代法也稱代法也稱切線法切線法.xyx*xky=f(x)xk+1PkPk+1xk+2).)()(kkkxxxfxfy 二、牛頓法的收斂性二、牛頓法的收斂性定理定理4： 設(shè)設(shè)f (x)在在a, b上存在二階連續(xù)導(dǎo)數(shù)且滿足下列條件上存在二階連續(xù)導(dǎo)數(shù)且滿足下列條件：（1）f (a) f (b) 0則由則由（2）（）（3）確定的牛頓迭代序列確定的牛頓迭代序列xk二階收斂于二階收斂于f (x)在在a, b上的唯一單根上的唯一單根x*。牛頓法收斂性依賴初值牛頓法收斂

37、性依賴初值x0的選取的選取, 如果如果x0偏離所求偏離所求根根x*較遠(yuǎn)較遠(yuǎn), 則牛頓法可能發(fā)散則牛頓法可能發(fā)散.x*x0 x0 x0例如例如，用牛頓法求解方程，用牛頓法求解方程 x3- -x- -1=0. 此方程在此方程在x=1.5附近的一個根附近的一個根x*. 設(shè)取迭代初值設(shè)取迭代初值x0=1.5，用牛頓迭代法公式，用牛頓迭代法公式 3121.31kkkkkxxxxx計(jì)算得計(jì)算得 x1=1.34783, x2=1.32520, x3=1.32472.迭代迭代3次得到的結(jié)果次得到的結(jié)果x3有有6位有效數(shù)字位有效數(shù)字.但是，如取但是，如取x0=0.6，用上式迭代，用上式迭代1次得次得 計(jì)算得計(jì)算

38、得 x1=17.9.這個結(jié)果反而比這個結(jié)果反而比x0=0.6更偏離了所求的根更偏離了所求的根x*=1.32472. 由此得到，當(dāng)由此得到，當(dāng)x*為為單根單根時，牛頓迭代法在根時，牛頓迭代法在根x*的的鄰近是鄰近是二階二階(平方平方)收斂收斂的的.定理定理(局部收斂性局部收斂性) 設(shè)設(shè)f C2a, b, 若若x*為為f(x)在在a, b上的根，且上的根，且f (x*) 0，則存在，則存在x*的鄰域的鄰域U, 使得任取初使得任取初值值x0 U，牛頓法產(chǎn)生的序列，牛頓法產(chǎn)生的序列xk收斂到收斂到x*，且滿足，且滿足即有下面的局部收斂性定理即有下面的局部收斂性定理.12()lim.()2()kkkxx

39、fxxxfx)()()(xfxfxx 設(shè)設(shè)x*是是f(x)的一個單根，即的一個單根，即f(x*)=0，f (x*)0, 有有. 0)()()(, 0)()()()(2* xfxfxxfxfxfx 牛頓迭代法的迭代函數(shù)為牛頓迭代法的迭代函數(shù)為2112!22( )()1()limlim()0.()()2!2()kkkkkkxxxxfxxxxxxfx 對于給定的正數(shù)對于給定的正數(shù)C，應(yīng)用牛頓法解二次方程，應(yīng)用牛頓法解二次方程, 02 Cx我們現(xiàn)在證明，這種迭代公式對于任意初值我們現(xiàn)在證明，這種迭代公式對于任意初值x00都是收斂的都是收斂的.可導(dǎo)出求開方值可導(dǎo)出求開方值 的計(jì)算程序的計(jì)算程序C.21)

40、()()(,)(2 xCxxfxfxxCxxf 11.(3.4.3)2kkkCxxx3.4.2 牛頓法應(yīng)用舉例牛頓法應(yīng)用舉例事實(shí)上，對事實(shí)上，對(3.4.3)式施行配方整理，易知式施行配方整理，易知 .2121CxxCxkkk 以上兩式相除得以上兩式相除得.211 CxCxCxCxkkkk據(jù)此反復(fù)遞推有據(jù)此反復(fù)遞推有200.(3.4.4)kkkxCxCxCxC記記.200kCxCxq 整理整理(3.4.4)式，得式，得.1222kkqqCCxk 對任意初值對任意初值x00，總有，總有|q|1，故由上式推知，當(dāng)，故由上式推知，當(dāng)k時時 ，即迭代過程恒收斂，即迭代過程恒收斂.Cxk 解解 將原方程

41、化為將原方程化為xex= 0，則，則牛頓迭代公式為牛頓迭代公式為kkxxkkkeexxx 11取取 x0=0.5，迭代得，迭代得x1=0.566311, x2=0.5671431, x3=0.5671433. f(x)=xex， f (x)=1+ex， 例例7 用牛頓迭代法求方程用牛頓迭代法求方程x=ex在在x=0.5附近的根附近的根.3.4.3 簡化牛頓法與牛頓下山法簡化牛頓法與牛頓下山法牛頓法的牛頓法的優(yōu)點(diǎn)優(yōu)點(diǎn)是收斂快，是收斂快，缺點(diǎn)缺點(diǎn)每步迭代要計(jì)算每步迭代要計(jì)算f(xk)及及f (xk)，計(jì)算量較大，且有時，計(jì)算量較大，且有時f (xk)計(jì)算較困難；計(jì)算較困難；初始近似值初始近似值x0

42、只在根只在根x*附近才能保證收斂，如附近才能保證收斂，如x0給給的不合適可能不收斂的不合適可能不收斂. 為克服這兩個缺點(diǎn)，通?？捎脼榭朔@兩個缺點(diǎn)，通?？捎孟率龇椒ㄏ率龇椒?簡化牛頓法簡化牛頓法，也稱，也稱平行弦法平行弦法，其迭代公式為，其迭代公式為1()0,0,1,.(3.4.5)kkkxxCf xCk迭代函數(shù)為迭代函數(shù)為 (x)=x- -Cf(x). 若若| (xk)|=|1- -Cf (x)|1，即取，即取0Cf (x)2. 在根在根x*附近成立，則迭代法附近成立，則迭代法(3.4.5)局部收斂局部收斂.在在(3.4.5)中取中取C=1/f (x0)，則稱為簡化牛頓法，這，則稱為簡化牛頓

43、法，這類方法計(jì)算量省，但只有線性收斂，其類方法計(jì)算量省，但只有線性收斂，其幾何意義幾何意義是用是用平行弦與平行弦與x軸交點(diǎn)作為軸交點(diǎn)作為x*的近似，見下圖的近似，見下圖.y=f(x)x0 x1x2x*為了防止迭代發(fā)散，我們對迭代過程再附加一項(xiàng)為了防止迭代發(fā)散，我們對迭代過程再附加一項(xiàng)要求，即具有單調(diào)性要求，即具有單調(diào)性.1()() .(3.4.6)kkf xf x滿足這項(xiàng)要求的算法稱為滿足這項(xiàng)要求的算法稱為下山法下山法.我們將牛頓法與下山法結(jié)合起來使用，即在下山我們將牛頓法與下山法結(jié)合起來使用，即在下山法保證函數(shù)值穩(wěn)定下降的前提下，用牛頓法加快收斂法保證函數(shù)值穩(wěn)定下降的前提下，用牛頓法加快收斂

44、速度速度. 為此，我們將牛頓法的結(jié)果為此，我們將牛頓法的結(jié)果)()(1kkkkxfxfxx 與前一項(xiàng)的近似值與前一項(xiàng)的近似值xk適當(dāng)加權(quán)平均作為新的改進(jìn)值適當(dāng)加權(quán)平均作為新的改進(jìn)值11(1),(3.4.7)kkkxxx其中其中(01)稱為稱為下山因子下山因子，(3.4.7)即為即為1()(0,1,).(3.4.8)()kkkkf xxxkfx稱為稱為牛頓下山法牛頓下山法.選擇下山因子時從選擇下山因子時從= =1開始，逐次將開始，逐次將減半進(jìn)行試減半進(jìn)行試算，直到能使下降條件算，直到能使下降條件(3.4.6)成立為止成立為止. 若用此法解方程若用此法解方程x3-x-1=0 ，當(dāng)，當(dāng)x0=0.6時

45、由時由(3.4.8)式式求得求得x1=17.9，它不滿足條件，它不滿足條件(3.4.6)，通過，通過逐次減半逐次減半進(jìn)行試算進(jìn)行試算,當(dāng)當(dāng)=1/32時可求得時可求得x1=1.140625. 有有f(x0)=- -1 1.384, f(x1)=- -0.656643, 顯然顯然|f(x1)|f(x0)|. 計(jì)算計(jì)算x2,x3,時，均能使條件時，均能使條件(3.4.6)成立成立. 得到得到x4=1.32472即為即為x*的的近似近似.3.5 解非線性方程組的牛頓迭代法考察方程組考察方程組111( ,)0,.(3.5.1)( ,)0.nnnf xxfxx其中其中f1,fn均為均為(x1,xn)的多元

46、函數(shù)的多元函數(shù). 若用向量記若用向量記號記號記x=(x1,xn)TRn, F=(f1,fn)T, (3.5.1)就可寫成就可寫成 F(x)=0. (3.5.2)當(dāng)當(dāng)n2，且，且 f1,fn 中至少有一個是自變量中至少有一個是自變量 x1,xn 的的非線性函數(shù)，則稱方程組非線性函數(shù)，則稱方程組(3.5.1)為為非線性方程組非線性方程組. 非非線性方程組求根問題是前面介紹的方程求根的直接推線性方程組求根問題是前面介紹的方程求根的直接推廣，實(shí)際上只要把前面介紹的廣，實(shí)際上只要把前面介紹的單變量函數(shù)單變量函數(shù)f(x)看成看成向向量函數(shù)量函數(shù)F(x) ，則可得，則可得向量方程向量方程(3.5.2)的一個

47、近似根的一個近似根x(k)=(x1(k),xn(k)T，將函數(shù)，將函數(shù)F(x)的分量的分量fi(x)(i=1,n)在在x(k)用多元函數(shù)泰勒展開，并取其線性部分，則可表示用多元函數(shù)泰勒展開，并取其線性部分，則可表示為為. ).)()()()()()(kkkxxxFxFxF 令上式右端為零，得到線性方程組令上式右端為零，得到線性方程組( )( )( )()()().(3.5.3)kkkF xxxF x其中其中11112222121( )( )( )( )( )( )( ).(3.5.4)( )( )( )nnnnnnnf xf xf xxxxf xf xf xxxxF xfxfxfxxxx稱為稱

48、為F(x)的的雅可比雅可比(Jacobi)矩陣矩陣.求解線性方程組求解線性方程組(3.5.3)，并記解為，并記解為x(k+1)，則得，則得(1)( )( )1( )()() (0,1,). (3.5.5)kkkkxxF xF xk這就是這就是解非線性方程組解非線性方程組(3.5.2)的的牛頓迭代法牛頓迭代法.例例12 求解方程組求解方程組 . 052),(, 032),(222121221211xxxxfxxxxf給定初值給定初值x(0)=(1.5, 1.0)T，用牛頓法求解，用牛頓法求解.解解 先求先求Jacobi矩陣矩陣.1422821)(,2421)(1212121 xxxxxFxxxF用牛頓法用牛頓法(3.5.5)得得.5)()( 23214228212)(22)(1)(2)(1)(1)(2)(1)(2)()1( kkkk