1、2020/8/25,1,第二章 非線性方程(組)求根方法,若 n=1, 稱為非線性方程求根問題； n1，稱為非線性方程組求解問題。,理論問題： （1）解的存在性。即有解還是無解，有多少解。 （2）解的性態(tài)。即孤立解的區(qū)域，解的重?cái)?shù)，光滑性。,關(guān)于解的存在性及其性態(tài)，不是數(shù)值分析所討論的問題。我們總認(rèn)為：,我們的任務(wù)是用數(shù)值方法求滿足一定精度要求的近似解！,通常求其精確解是困難的,2020/8/25,2, 二分法,內(nèi)容:, 一般迭代法, 牛頓迭代法, 迭代法的加速, 非線性方程組的牛頓迭代法*,2020/8/25,3,1、二分法,設(shè) 在區(qū)間 上連續(xù)且有 ，則 在區(qū)間 內(nèi)有解，不妨設(shè)解唯一！,算法

2、構(gòu)造原理:,有根區(qū)間,2020/8/25,4,x1,a,x2,b,什么時(shí)候停止？,或,x*,算法停止的條件,x,2020/8/25,5,綜合上述，得到如下算法，,(1),(2),(3),否則,(4),否則，轉(zhuǎn)(2)；,例1,可得,共計(jì)算21次！,注：,其中 為精度控制參數(shù)!,2020/8/25,6,二分法只能求有根區(qū)間中的奇數(shù)重的實(shí)根;,關(guān)于二分法的討論,(1),二分法線性收斂;,(2),二分法可用來細(xì)化有根區(qū)間，這是它的一大優(yōu)點(diǎn)!,(3),故二分法可以用來確定迭代法的迭代初值!,返回主目錄,2020/8/25,7,2、一般迭代法,(1),(2),(3),(一) 構(gòu)造方法,(1),2020/8

3、/25,8,例2,2020/8/25,9,1.5000 -0.8750 6.7324 -69.7200 1.0275e+8 不收斂,1.5000 1.2870 1.4025 1.3455 1.3752 1.3601 1.3678 1.3639 1.3659 1.3649 1.3654 1.3651 1.3653 1.3652 1.3652,1.5000 0.8165 2.9969 0-2.9412i 不收斂,1.5000 1.3484 1.3674 1.3650 1.3653 1.3652 1.3652,方法1,方法2,方法3,方法4,*收斂與否，以及收斂快慢，取決于迭代函數(shù),15次,6次,*

4、精度控制的表達(dá)式？,2020/8/25,10,(二) 大范圍收斂定理,(1),(2),則,(1),(2),(3),下面看證明過程，,即 是自映射；,2020/8/25,11,(1),由條件(1)可得解的存在性；,由條件(2)可證解的唯一性！,(2),由條件(1)可知,(3),得證；,進(jìn)而可證!,2020/8/25,12,(三) 局部收斂定理,若,由迭代(1)產(chǎn)生的序列 ,證明:略!,注：,當(dāng)定理?xiàng)l件成立時(shí)，,只要x0充分接近x*，就能保證迭代序列xn收斂于x*！,且有與前一定理完全相同的不等式成立！,2020/8/25,13,分析例2四種迭代格式的收斂性，,一般迭代法只有理論上的意義，因?yàn)闃?gòu)造

5、保證收斂的迭代函數(shù)比較困難。,注:,方法1的收斂性分析,方法2的收斂性分析,方法3的收斂性分析,方法4的收斂性分析,四種迭代格式的計(jì)算結(jié)果見本課件P9!,取定初值x0=1.5，=1e-4,2020/8/25,14,（四） 收斂階（速度）的討論,定義:,p=1 線性收斂；,p=2 平方收斂；,2p1 超線性收斂；,注：,1、 p=1時(shí)，c1; 2、滿足局部收斂定理的簡(jiǎn)單迭代算法至少具有一階收斂速度。,2020/8/25,15,定理（簡(jiǎn)單迭代算法m階收斂的充分條件）,設(shè),在包含x*某個(gè)開區(qū)間內(nèi)連續(xù)，,若,使得,則,注: 1、給出了由迭代函數(shù)判斷收斂速度的方法； 2、給出了提高收斂速度的方法!,由迭

6、代 產(chǎn)生的序列 xn 以m階收斂速度收斂到x* 。,證明：由泰勒公式和收斂階定義可證！,2020/8/25,16,例3,解：,迭代函數(shù)為,2020/8/25,17,迭代函數(shù)為,解：,#,返回主目錄,2020/8/25,18,3、簡(jiǎn)單迭代法加速,如何對(duì)其加速?,由微分中值定理得,事實(shí)上，設(shè)迭代算法 產(chǎn)生的序列 ，,其中 介于 和 之間。,2020/8/25,19,(一) 埃特金(Aitken)加速方法,令,作為 的校正值！,2020/8/25,20,(二) steffensen加速算法,設(shè)迭代算法 ，,對(duì)其應(yīng)用Aitken加速方法，得到如下Steffensen算法:,若 在 附近變化不大，,20

7、20/8/25,21,Steffensen算法的收斂性,注:,（1）可以用Steffensen算法對(duì)收斂緩慢的簡(jiǎn)單迭代算法加速！,可以證明：,（2）對(duì)于至少平方收斂的算法，用Steffensen算法進(jìn)行加速， 意義不大！,返回主目錄,2020/8/25,22,4、牛頓迭代算法,將f(x)在初值x0處做Taylor展開,取其線性部分做為f(x)的近似，有：,若,則有,記為,同理，我們可以得到,2020/8/25,23,這樣一直下去，我們可以得到迭代序列,Newton迭代的迭代函數(shù),(2), 牛頓迭代算法(切線法),其它構(gòu)造方法,(1) 待定函數(shù)法:,(2) 數(shù)值積分法:,2020/8/25,24

8、,收斂定理（單根的情形）,2020/8/25,25,證明：,由已知可得 ，,所以至少平方收斂！,#,利用收斂階的定義來證明！,注：也可以由收斂階的判定定理來證！,2020/8/25,26,應(yīng)用舉例,（1）,對(duì)于給定的正數(shù)C，應(yīng)用牛頓法解二次方程 x2-C=0。,可得,證明上述迭代算法 收斂，并求收斂階！,1）當(dāng)x00時(shí)，收斂于 ；2）當(dāng)x00時(shí)，收斂于 ；,（*）,1)得證!,2）,事實(shí)上，對(duì)（*）式進(jìn)行配方可得,下面證明1），,2020/8/25,27,（2）,對(duì)于給定的正數(shù)C，應(yīng)用牛頓法求解方程 。,可得,可以證明上述迭代算法對(duì)任意初值 都收斂于 ！,事實(shí)上，,從而,#,2020/8/25

9、,28,牛頓迭代法的幾點(diǎn)說明,牛頓迭代法算法簡(jiǎn)單，且局部收斂，但初值x0的選擇困難！,(1),(2),牛頓迭代每步都要計(jì)算導(dǎo)數(shù) ，增加了計(jì)算量！,(3),定理表明牛頓迭代求單根有效且平方收斂（能求重根嗎？）。,(一),一般來說采用試探法，可以結(jié)合二分法或通過做出函數(shù)圖形來幫助選擇初值！,關(guān)于初值,(二),導(dǎo)數(shù)的計(jì)算,(1),利用牛頓迭代法先計(jì)算幾步，比如計(jì)算到了第k步，得到近似值xk，接下來用 來代替導(dǎo)數(shù)，該算法通常是線性收斂的！,2020/8/25,29,(2),一個(gè)實(shí)用的方法是用差分代替微分，即,此迭代法稱為割線法！它是超線性收斂的！,(三),關(guān)于重根的問題,2020/8/25,30,可見

10、，當(dāng)x*為重根時(shí)，牛頓迭代線性收斂，且隨著m的增加，收斂性變差！,計(jì)算重根的改進(jìn)算法,(1),至少平方收斂。(證明略!),設(shè)重?cái)?shù)m已知， 應(yīng)用牛頓迭代法得,2020/8/25,31,返回主目錄,(2),重?cái)?shù)不知道時(shí)，一個(gè)實(shí)用的方法是，令,則,直接對(duì) 應(yīng)用牛頓迭代法求解:,至少平方收斂！,2020/8/25,32,解非線性方程組的牛頓迭代法,2020/8/25,33,Jacobi矩陣,2020/8/25,34,注意事項(xiàng)：,為了解決上述問題，提出擬牛頓法。,2020/8/25,35,2020/8/25,36,2020/8/25,37,Broyden秩1方法,2020/8/25,38,2020/8/25,39,綜合上述，得到Broyden秩1方法：,2020/8/25,40,2020/8/25,41,返回主目錄,2020/8/25,42,1、數(shù)值分析. 顏慶津. 修訂版. 北京航空航天大學(xué)出版社，2000 2、李慶揚(yáng). 非線性方程組的數(shù)值解法. 科學(xué)出版社, 1987,參考書目：,2020/8/25,43,例2,返回,不