方程解數(shù)值法

1、計(jì)計(jì)算算方方法法第二章第二章 非線性方程的數(shù)值解法非線性方程的數(shù)值解法 王新年王新年大連海事大學(xué)信息工程學(xué)院大連海事大學(xué)信息工程學(xué)院信號(hào)與圖像處理研究所信號(hào)與圖像處理研究所 計(jì)計(jì)算算方方法法簡(jiǎn)介（Introduction）我們知道在實(shí)際應(yīng)用中有許多非線性方程的例子，例如（1）在光的衍射理論（the theory of diffraction of light)中,我們需要求x-tanx=0的根（2）在行星軌道（ planetary orbits）的計(jì)算中,對(duì)任意的a和b，我們需要求x-asinx=b的根（3） 在數(shù)學(xué)中，需要求n次多項(xiàng)式xn + a1 xn-1+.+an-1 x + an 0的

2、根求求f(xf(x)=0)=0的根的根計(jì)計(jì)算算方方法法 滿足方程的滿足方程的x值通常叫做值通常叫做方程的根或解方程的根或解，也叫函數(shù)也叫函數(shù)f( (x)=0)=0的零點(diǎn)。的零點(diǎn)。非線性方程的一般形式非線性方程的一般形式 f(x)=0 這里這里f( (x) )是單變量是單變量x 的函數(shù)，它可以是的函數(shù)，它可以是代數(shù)多項(xiàng)式代數(shù)多項(xiàng)式 f( (x)=)=a0+a1x+anxn (an0)也可以是也可以是超越函數(shù)超越函數(shù)，即不能表示為上述形式的函數(shù)。，即不能表示為上述形式的函數(shù)。計(jì)計(jì)算算方方法法方程根的數(shù)值計(jì)算步驟判斷根的存在確定根的分布范圍根的精確化計(jì)計(jì)算算方方法法 根的存在定理根的存在定理( (零

3、點(diǎn)定理零點(diǎn)定理) )： f(x)為為 a,b 上的連續(xù)函數(shù)，若上的連續(xù)函數(shù)，若 f(a)f(b)eps) x=(a+b)/2 計(jì)算f(x) 若(|f(x)|eps) x為解 若f(x)*f(b)0 修正區(qū)間為x,b,即a=x 若f(a)*f(x)0 修正區(qū)間為a,x,即b=xEnd while計(jì)計(jì)算算方方法法誤差誤差 分析：分析：第第1步產(chǎn)生的步產(chǎn)生的21bax 有誤差有誤差21abx*|x 第第 k 步產(chǎn)生的步產(chǎn)生的 xk 有誤差有誤差kkabx*|x2 對(duì)于給定的精度對(duì)于給定的精度 ,可估計(jì)二分法所需的步可估計(jì)二分法所需的步數(shù)數(shù) k ： 2lnlnln2abkabk 計(jì)計(jì)算算方方法法 用二

4、分法求用二分法求 在在(1,2)(1,2)內(nèi)的根，要求絕對(duì)誤差不超過(guò)內(nèi)的根，要求絕對(duì)誤差不超過(guò) ： f(1)=-50 -(1,2)+ f(1.25)0 (1.25,1.375) f(1.313)0 (1.313,1.375) f(1.344)0 (1.344,1.375) f(1.360)0 (1.360,1.368) 010423 xx21021 f(1.5)0 (1,1.5) nx 1.51 x364. 1368. 1360. 1344. 1313. 1375. 125. 18765432 xxxxxxx計(jì)計(jì)算算方方法法12 例例2，求方程f(x)= x 3 e-x =0的一個(gè)實(shí)根。 因?yàn)?/p>

5、 f(0)0。 故f(x)在(0,1)內(nèi)有根用二分法解之，(a,b）=（0,1)計(jì)算結(jié)果如表：ka bk xk f(xk)符號(hào)00 1 0.5000 10.5000 0.7500 20.7500 0.8750 3 0.87500.8125 4 0.81250.7812 5 0.7812 0.7656 60.7656 0.7734 7 0.7734 0.7695 8 0.7695 0.7714 90.7714 0.7724 100.7724 0.7729 取x10=0.7729，誤差為| x* -x10|=1/211 。 計(jì)計(jì)算算方方法法f (x) = 0 x = g (x)等價(jià)變換等價(jià)變換f

6、(x) 的根的根g (x) 的不動(dòng)點(diǎn)的不動(dòng)點(diǎn)Fixed-PointPicard Iteration2.2單個(gè)方程的迭代法計(jì)計(jì)算算方方法法Iteration:The act or an instance of iterating; repetition.Mathematics: A computational procedure in which the desired result is approached through a repeated cycle of operations, each of which more closely approximates the desired r

7、esult.Computer Science: The process of repeating a set of instructions a specified number of times or until a specific result is achieved.計(jì)計(jì)算算方方法法迭代法流圖計(jì)計(jì)算算方方法法幾何意義:( )yxyg x和的交點(diǎn)xyy = xx*y=g(x)x0p0 x1p1 xyy = xx*y=g(x)x0p0 x1p1計(jì)計(jì)算算方方法法xyy = xxyy = xxyy = xxyy = xx*x*x*x*y=g(x)y=g(x)y=g(x)y=(x)x0p0 x1

8、p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1計(jì)計(jì)算算方方法法 For example For example：2x2x3 3-x-1=0-x-1=0計(jì)計(jì)算算方方法法321xx 如果將原方程化為等價(jià)方程如果將原方程化為等價(jià)方程由此可見(jiàn)，這種迭代格式是發(fā)散的由此可見(jiàn)，這種迭代格式是發(fā)散的 取初值取初值00 x310211xx 321213xx 3322155xx 3121kkxx則迭代格式為：計(jì)計(jì)算算方方法法321xx 如果將原方程化為等價(jià)方程如果將原方程化為等價(jià)方程00 x21031 xx3217937.031221xx327937.19644.0仍取初值仍取初值依此類推依此類

9、推, ,得得 x x3 3 = 0.9940 = 0.9940 x x4 4 = 0.9990 = 0.9990 x x5 5 = 0.9998 = 0.9998 x x6 6 = 1.0000 = 1.0000 x x7 7 = 1.0000 = 1.0000已經(jīng)收斂已經(jīng)收斂, ,故原方程的解為故原方程的解為 x = 1.0000 x = 1.0000 同樣的方程同樣的方程不同的迭代格式不同的迭代格式 有不同的結(jié)果有不同的結(jié)果什么形式的迭代什么形式的迭代法能夠收斂呢法能夠收斂呢? ?如何構(gòu)造迭代函如何構(gòu)造迭代函數(shù)呢?cái)?shù)呢? ?計(jì)計(jì)算算方方法法 若從任何可取的初值出發(fā)都能保證收斂，則若從任何可取

10、的初值出發(fā)都能保證收斂，則稱它為稱它為大范圍收斂大范圍收斂。如若為了保證收斂性必須選。如若為了保證收斂性必須選取初值充分接近于所要求的根，則稱它為取初值充分接近于所要求的根，則稱它為局部收局部收斂斂。 通常局部收斂方法比大范圍收斂方法收斂得通常局部收斂方法比大范圍收斂方法收斂得快。因此，一個(gè)合理的算法是先用一種大范圍收快。因此，一個(gè)合理的算法是先用一種大范圍收斂方法求得接近于根的近似值（如對(duì)分法），再斂方法求得接近于根的近似值（如對(duì)分法），再以其作為新的初值使用局部收斂法（如迭代法）以其作為新的初值使用局部收斂法（如迭代法）。 這里討論迭代法的收斂性時(shí)，均指的是局部這里討論迭代法的收斂性時(shí)，均

11、指的是局部收斂性。收斂性。計(jì)計(jì)算算方方法法定義定義 若存在常數(shù)若存在常數(shù) (0 1),使得對(duì)一使得對(duì)一切切x x1 1,x,x2 2a,ba,b, , 成立不等式成立不等式|g(x|g(x1 1)-g(x)-g(x2 2)| )| |x |x1 1-x-x2 2| |，則稱則稱g(x)g(x)是是a,ba,b上的一個(gè)壓縮映射上的一個(gè)壓縮映射， 稱為壓縮系數(shù)稱為壓縮系數(shù)收斂性分析P32xyy=g(x)x1g(x1)x2g(x2)xyy=g(x)x2x1g(x2)g(x1)g(x1)李普希茨李普希茨(Lipschitz)條件條件arctan( )/4api計(jì)計(jì)算算方方法法 考慮方程考慮方程 x =

12、 g(x), g(x) Ca, b, 若若( I ) 當(dāng)當(dāng) x a, b 時(shí)，時(shí)， g(x) a, b；( II )在在a,ba,b上成立不等式：上成立不等式：|g(x|g(x1 1)-g(x)-g(x2 2)| )| |x |x1 1-x-x2 2| | 。則（則（1）g g在在a,ba,b上存在惟一不動(dòng)點(diǎn)上存在惟一不動(dòng)點(diǎn)x x* *（2）任取）任取 x0 a, b，由由 xk+1 = g(xk) 得到的序列得到的序列 x xk k （ a,ba,b ） 收斂于收斂于x x* * 。（3）k k次迭代所得到的近似不動(dòng)次迭代所得到的近似不動(dòng)點(diǎn)點(diǎn)x xk k與精確不動(dòng)點(diǎn)與精確不動(dòng)點(diǎn)x x* *有

13、有有誤差估有誤差估計(jì)式：計(jì)式：收斂定理收斂定理*11kkkxxxx*101kkxxxx計(jì)計(jì)算算方方法法證明：證明： g(x) 在在a, b上存在不動(dòng)點(diǎn)？上存在不動(dòng)點(diǎn)？ 不動(dòng)點(diǎn)唯一？不動(dòng)點(diǎn)唯一？ 當(dāng)當(dāng)k 時(shí)，時(shí)， xk 收斂到收斂到 x* ？ | |x x* *-x|=|g(x-x|=|g(x* *)-g(x)| )-g(x)| | |x x* *-x|. -x|. 因因0 0 1 1，故必有，故必有 x=xx=x* *若有若有xxa,ba,b, ,滿足滿足g(x)=xg(x)=x，則則| |x xk k-x-x* *|=|g(x|=|g(xk-1k-1)-g(x)-g(x* *)| )| |

14、|x k-1k-1-x-x* *| | 2 2|x|xk-2k-2-x-x* *| | k k|x|x0 0-x-x* *| |0 0, ,令令G(x)=g(x)-x, xG(x)=g(x)-x, xa,ba,b，由條件知由條件知G(a)=g(a)-a0, G(b)=g(b)-b0.G(a)=g(a)-a0, G(b)=g(b)-b0.由條件知由條件知G(x)G(x)在在a,ba,b上連續(xù)，又由零點(diǎn)定理知上連續(xù)，又由零點(diǎn)定理知存在存在x x* *a,ba,b，使使G(xG(x* *)=0)=0，即即x x* *=g(x=g(x* *).).計(jì)計(jì)算算方方法法 可用可用 來(lái)來(lái)控制收斂精度控制收斂精

15、度|1kkxx 越小，收斂越快越小，收斂越快(4) |(4) |x xk k-x-x* *|=|g(x|=|g(xk-1k-1)-g(x)-g(x* *)| )| | |x k-1k-1-x-x* *| | （|x|xk k-x-xk-1k-1|+|x|+|xk k-x-x* *| |）, ,故有故有 | |x xk k-x-x* *| | /(1-/(1- ) )|x|xk k-x-xk-1k-1|.|.(5) (5) |x|xk k-x-xk-1k-1| | = |g(x= |g(xk-1k-1)-g(x)-g(xk-2k-2)|)| | |x k-1k-1-x-xk-2k-2| k-1k

16、-1|x|x1 1-x-x0 0| | | |x xk k-x-x* *| | k k/(1-/(1- ) )|x|x1 1-x-x0 0|.|.計(jì)計(jì)算算方方法法（迭代法的局部收斂定理）（迭代法的局部收斂定理）定理?xiàng)l件非必要條件，而且定理中的壓縮定理?xiàng)l件非必要條件，而且定理中的壓縮條件不好驗(yàn)證，一般來(lái)講條件不好驗(yàn)證，一般來(lái)講， 若知道迭代函數(shù)若知道迭代函數(shù)g(x)Cg(x)C1 1a,ba,b(1),(1),并并且滿足且滿足|g(x)| |g(x)| 1(2),1(2),對(duì)任對(duì)任意的意的xxa,ba,b(1),(1),則則g g（x)x)是是a,ba,b上的壓縮映射上的壓縮映射計(jì)計(jì)算算方方法法

17、| |x x* *-y|=|g(x-y|=|g(x* *)-)-g(yg(y)|=)|=|g(x)(x*-y)|(微分中值定理微分中值定理) | |x x* *-y|.-y|.因因0 0 1 1，故必有，故必有 y=xy=x* *證明：證明： g(x) 在在a, b上存在不動(dòng)點(diǎn)？上存在不動(dòng)點(diǎn)？ 不動(dòng)點(diǎn)唯一？不動(dòng)點(diǎn)唯一？ 當(dāng)當(dāng)k 時(shí)，時(shí)， xk 收斂到收斂到 x* ？ 若有若有yya,ba,b, ,滿足滿足g(yg(y)=y)=y，則則| |x xk k-x-x* *|=|g(x|=|g(xk-1k-1)-g(x)-g(x* *)| )| | |x k-1k-1-x-x* *| | 2 2|x|

18、xk-2k-2-x-x* *| | k k|x|x0 0-x-x* *| |0 0, ,令令G(x)=g(x)-x, xG(x)=g(x)-x, xa,ba,b，由條件知由條件知G(a)=g(a)-a0, G(b)=g(b)-b0.G(a)=g(a)-a0, G(b)=g(b)-b0.由條件知由條件知G(x)G(x)在在a,ba,b上連續(xù)，又由介值定理知上連續(xù)，又由介值定理知存在存在x x* *a,ba,b，使使G(xG(x* *)=0)=0，即即x x* *=g(x=g(x* *).).計(jì)計(jì)算算方方法法例題已知方程2x-7-lgx0，求方程的含根區(qū)間，考查用迭代法解此方程的收斂性。計(jì)計(jì)算算方

19、方法法計(jì)計(jì)算算方方法法在這里我們考查在區(qū)間3.5,4的迭代法的收斂性很容易驗(yàn)證：f(3.5)0將方程變形成等價(jià)形式：x(lgx+7)/2(lg( )7)11( )2ln10 xg xx1g(x)=23.54max |( )| 0.0631xg x 由定理知，迭代格式由定理知，迭代格式x xk+1k+1(lgx(lgxk k+7)/2+7)/2在在3.5,43.5,4內(nèi)收斂?jī)?nèi)收斂計(jì)計(jì)算算方方法法舉例用一般迭代法求x3-x-1=0的正實(shí)根x*3x= x+1將方程改寫(xiě)成：3x)= x+1則迭代函數(shù)為：g(231x)=3x+1 g (（）容易得到：容易得到：g(x)g(x)在包含在包含x x* *的某

20、鄰域的某鄰域U(xU(x* *) ) 內(nèi)內(nèi)連續(xù)，且連續(xù)，且| |g(xg(x* *)|1)|1*3kx= x +1xk+1因此迭代格式在 附件收斂計(jì)計(jì)算算方方法法例題用一般迭代法求方程x-lnx2在區(qū)間（2，）內(nèi)的根，要求|xk-xk-1|/|xk|=10-8解：令f(x)=x-lnx-2f(2)0,故方程在（2,4）內(nèi)至少有一個(gè)根12f (x)=10 xx又 （ ， ）,f (x)=02,2*因此方程 在（ ， ）內(nèi)僅有一個(gè)根x且x（ ， ）計(jì)計(jì)算算方方法法將方程化為等價(jià)方程：x2lnx1g(x)2lnx (x)|=| 0.51,2 4xx ， |g（ ， ）因此， x0（2，），xk+12

21、lnxk產(chǎn)生的序列 xk 收斂于X*取初值x03.0,計(jì)算結(jié)果如下：計(jì)計(jì)算算方方法法7 3.1461436118 3.146177452 9 333333.146193204k xi0 3.000000000 1 3.098612289 2 3.130954362 3 3.141337866 4 3.144648781 5 3.145702209 6 3.146037143計(jì)計(jì)算算方方法法另一種迭代格式： 1(1 ln)1kkkkxxxx 0 3.000000000

22、 1 3.147918433 2 3.146193441 3 3.146193221計(jì)計(jì)算算方方法法 定義定義. :設(shè)設(shè)序列序列xk收斂于收斂于x*，若存在若存在p1和正數(shù)和正數(shù)c，使得成立使得成立則稱則稱xk為為 p 階收斂的階收斂的特別特別, p = 1，要求要求c1, 稱線性收斂稱線性收斂; 1p 0，當(dāng)，當(dāng)x x0 0 x x* * - - ，x x* *+ + (x(x0 0 xx* *) )時(shí)，由迭代法產(chǎn)生的序列時(shí)，由迭代法產(chǎn)生的序列x xk k以以p p階收斂速度收斂于階收斂速度收斂于x x* *. .計(jì)計(jì)算算方方法法Prove:(1)(1)由由g(g(x x* *)=0)=0必

23、存在必存在 0，當(dāng)，當(dāng)x x0 0 x x* * - - ，x x* *+ + U(x)U(x)時(shí)，由時(shí)，由PicardPicard迭代產(chǎn)生的序列迭代產(chǎn)生的序列 x xk k 收收斂于斂于x x* *, ,并有并有x xk k x x* * - - ，x x* *+ + (2)(2)由泰勒公式有由泰勒公式有x xk+1k+1= =g(xg(xk k)=g(x)=g(x* * ）g(xg(x* *)()(x xk k- - x x* *)+)+g +g (p-1)(p-1) (x (x* *)()(x xk k-x-x* *) ) p-1p-1/(p-1)! + /(p-1)! + g g (p

24、)(p)(x(x* *+ + ( (x xk k-x-x* *)()(x xk k-x-x* *) ) p / p /p! p! ，00 1. 利用利用g g在在x x* *的各階導(dǎo)數(shù)條件及的各階導(dǎo)數(shù)條件及g(xg(x* *)=x)=x* *, ,上式可改寫(xiě)成上式可改寫(xiě)成( )*1()()!ppkkkgxxxxxxxp計(jì)計(jì)算算方方法法(3)(3)由于由于g g在在x x* *處處p p階連續(xù)可微且階連續(xù)可微且g g(p)(p)(x(x* *)0)0，知必存在知必存在x x* *的的某鄰域某鄰域( (x x* *) )，當(dāng)當(dāng)xU(xxU(x* *) )時(shí)，有時(shí)，有g(shù) g (p)(p) (x)0.

25、 (x)0.由于由于x x* *+ + ( (x xk k-x-x* *) ) x x* * - - ，x x* *+ + U(xU(x* *) )，故故g g (p)(p)(x(x* *+ + ( (x xk k-x-x* *) 0) 0，k=0k=0，1,2,1,2,. .可見(jiàn)，當(dāng)初值可見(jiàn)，當(dāng)初值x x0 0 xx* *時(shí)，由上式可推出諸時(shí)，由上式可推出諸x xk kxx* *于是由上式有于是由上式有*()*1*()!pkkpkxxgxxxpxx 上式令上式令kk取極限取極限. .*()*1*()lim0!pkpkkxxgxpxx 即即 x xk k 有有p p階收斂速度階收斂速度. .計(jì)

26、計(jì)算算方方法法取取x0 0作為初始近似值作為初始近似值，將將f(x)在在x x0 0做做TaylorTaylor展開(kāi)展開(kāi): :20000( )( )()()()()2!ff xf xfxxxxx0000( *)()()( *)f xf xfxxx000()*()f xxxfx1()()kkkkf xxxfx重復(fù)上述過(guò)程重復(fù)上述過(guò)程 0100()()fxxxfx作為第一次近似值作為第一次近似值Newton迭代公式迭代公式基本思路：基本思路：將非線性方程將非線性方程f(x)=0 線性化線性化2.3 Newton-Raphson迭代法迭代法計(jì)計(jì)算算方方法法牛頓法的幾何意義牛頓法的幾何意義xyx*x0

27、0100()()fxxxfxx 1x 2000:()()()Tangent line yf xfxxx1211()()fxxxfx牛頓法也稱為切線法牛頓法也稱為切線法計(jì)計(jì)算算方方法法這樣一直下去，我們可以得到迭代序列)( )(1kkkkxfxfxxNewton迭代的等價(jià)方程為：)( )()(0)(xfxfxxxxf所以2)( )( )()( )()( xfxfxfxfxfxx若f(x)在a處為單根，則0)( , 0)( , 0)(aafaf所以，迭代格式收斂計(jì)計(jì)算算方方法法Newtons Method 收斂性依賴于收斂性依賴于x0 的選取。的選取。x*x0 x0 x0計(jì)計(jì)算算方方法法 (1)

28、(1) 選定初值選定初值x0 ,計(jì)算計(jì)算f (x0) , f (x0) 計(jì)算步驟計(jì)算步驟(2) (2) 按公式按公式 迭代迭代 得新的近似值得新的近似值xk+1 1()()kkkkf xxxfx(3) (3) 對(duì)于給定的允許精度對(duì)于給定的允許精度 ，如果如果 則終止迭代，取則終止迭代，取 ; ;否則否則k=k+1，再轉(zhuǎn)再轉(zhuǎn) 步驟步驟(2)(2)計(jì)算計(jì)算*1kxx1|kkxx允許精度允許精度最大迭代最大迭代次數(shù)次數(shù)迭代信息迭代信息1()()kkkkfxxxfx計(jì)計(jì)算算方方法法 例例 用Newton迭代法求方程xex-1=0在0.5附近的根,精度要求=10-5. 解解 Newton迭代格式為, 2

29、 , 1 , 0,111kxexxexeexxxkxkkxkxxkkkkkkkkxk(xk)|xk-xk-1|012340.50.571020440.567155570.567143290.56714329-0.175639360.010747510.000033930.00000000030.00000000030.071020440.003864870.000012280.00000000計(jì)計(jì)算算方方法法用迭代法求方程在，1.5處的解220 xx計(jì)計(jì)算算方方法法收斂速度收斂速度21()()( )() ( )( )2nnnnxaxaxaxaa 22()()( )( )22nnxaxaa 函數(shù)

30、在a處作Taylor展開(kāi)若a為p重根，取迭代格式為：)( )(1kkkkxfxfpxx即Meenn21Newton迭代收斂速度快，格式簡(jiǎn)單，應(yīng)用廣泛誤差誤差 分析：分析：計(jì)計(jì)算算方方法法1( )0(),()(0).():kkkkf xma mZf xxxmkfx 若若方方程程有有重重根根試試證證明明牛牛頓頓迭迭代代法法是是線線性性收收斂斂的的 而而改改用用修修改改的的格格式式才才是是局局部部平平方方收收斂斂的的例例1( )(1)( )( )0( )()( ),( )0.( )()( )()( )() ( )( )( ):)mmmf xxxfxf xmf xxah xh afxm xah xxa

31、h xxa h xxxmh xxah x 對(duì)對(duì)牛牛頓頓格格式式, , 迭迭代代函函數(shù)數(shù) ( (因因有有重重根根, ,故故有有且且代代入入迭迭代代函函數(shù)數(shù)式式( (證證明明計(jì)計(jì)算算方方法法( )1( )()( )( )()()( )()( )h xxmh xxa h xdh xxadx mh xxa h x ( (111,( )10.,( )()( ()( )( )()()|1( )10lim|.kkkkkkkkxaamaxaxxaaxao xaaxCaaxm 代代入入有有于于是是 由由得得到到故故這這種種牛牛頓頓迭迭代代法法只只有有線線性性收收斂斂速速度度計(jì)計(jì)算算方方法法 212( )(2)(

32、 )() ( )( )()( )( )1( )()( )( )()()( )()( ),)01)21)2kkkkkkf xxxmfxxa h xxxmmh xxa h xmh xxmh xxa h xdh xm xadx mh xxa h xaaxaxaxaax 對(duì)對(duì)修修改改的的牛牛頓頓格格式式, , 迭迭代代函函數(shù)數(shù) ( ( ( (此此時(shí)時(shí)( (再再由由( ( ( (計(jì)計(jì)算算方方法法12|11|)|)|0|22.kkkaxCaax 得得到到( ( (因因此此修修改改后后的的牛牛頓頓格格式式是是平平方方收收斂斂的的計(jì)計(jì)算算方方法法1 1、優(yōu)點(diǎn)：牛頓迭代法具有平方收斂的速度，所以、優(yōu)點(diǎn)：牛頓迭代

33、法具有平方收斂的速度，所以在迭代過(guò)程中只要迭代幾次就會(huì)得到很精確的解。在迭代過(guò)程中只要迭代幾次就會(huì)得到很精確的解。這是牛頓迭代法比簡(jiǎn)單迭代法優(yōu)越的地方。這是牛頓迭代法比簡(jiǎn)單迭代法優(yōu)越的地方。2 2、缺點(diǎn)：選定的初值要接近方程的解，否則有可、缺點(diǎn)：選定的初值要接近方程的解，否則有可能得不到收斂的結(jié)果。再者，牛頓迭代法計(jì)算量比能得不到收斂的結(jié)果。再者，牛頓迭代法計(jì)算量比較大。因每次迭代除計(jì)算函數(shù)值外還要計(jì)算微商值較大。因每次迭代除計(jì)算函數(shù)值外還要計(jì)算微商值。1()()kkkkf xxxpfx計(jì)計(jì)算算方方法法牛頓法主要有兩個(gè)缺點(diǎn)：局部收斂，計(jì)算量大。牛頓法主要有兩個(gè)缺點(diǎn)：局部收斂，計(jì)算量大。1111

34、11(1)Newton()(0,1,2,)(2)()(0,1,2,)()()(3)()(0,1,2,)()(01),()| |()|kkkkkkkkkkkkkkkkf xxxkMxxxxf xkf xf xf xxxkfxf xf x 簡(jiǎn)簡(jiǎn)易易法法割割線線法法牛牛頓頓下下山山法法可可引引入入一一個(gè)個(gè)下下山山因因子子使使每每一一步步有有| |計(jì)計(jì)算算方方法法2.4 弦截法弦截法將Newton迭代中的導(dǎo)數(shù)，用差商代替，有格式111()()()kkkkkkkf xxxf xf xxx是2步格式。收斂速度比Newton迭代慢Meenn618. 11x0 x1切線切線 割線割線 計(jì)計(jì)算算方方法法1121

35、2()0(1)()0nnnfxxxfxxx 非非線線性性方方程程組組的的一一般般形形式式， ， ， ， ，11( )()0( )()0 (2),:nnnnxfxXF XxfxF XFDRR令令則則方方程程(1)(1)可可改改寫(xiě)寫(xiě)為為(2)( )0 xDxF x 若若存存在在，使使方方程程組組精精確確成成立立，則則稱稱 為為方方程程組組的的解解。非線性方程組的迭代法非線性方程組的迭代法計(jì)計(jì)算算方方法法)()()( )(11kkkkkkkXFXJXxFxFXX直接推廣Newton迭代為：nnnnxfxfxfxfXJ1111)(1()()kkkkfxxxfx單個(gè)方程的牛頓迭代形式:雅可比矩陣(Jac

36、obi)()()kkkJ XXF X計(jì)計(jì)算算方方法法 (1) (1) 選定初值選定初值x0 ,計(jì)算計(jì)算f (x0) , f (x0) 計(jì)算步驟計(jì)算步驟:單個(gè)方程單個(gè)方程?(2) (2) 按公式按公式 迭代迭代 得新的近似值得新的近似值xk+1 1()()kkkkf xxxfx(3) (3) 對(duì)于給定的允許精度對(duì)于給定的允許精度 ，如果如果 則終止迭代，取則終止迭代，取 ; ;否則否則k=k+1，再轉(zhuǎn)再轉(zhuǎn) 步驟步驟(2)(2)計(jì)算計(jì)算*1kxx1|kkxx允許精度允許精度最大迭代最大迭代次數(shù)次數(shù)迭代信息迭代信息1()()kkkkfxxxfx11( ( ) ( )kkkkXXJXFX 方程組呢方程

37、組呢?(1) (1) 選定初值選定初值X X0 ,計(jì)算計(jì)算F(X0) , J(X0) ( (2) 2) 按公式計(jì)算按公式計(jì)算X Xk+1k+11|kkXX1*kXX計(jì)計(jì)算算方方法法22200112233020.5044xxyxyxyx yxyxy設(shè)有非線性方程組初始值（,)=(2.00,0.25）,用牛頓法計(jì)算( , )(,)( ,)1.96251.9006911.9006770.31250.3112130.311219221()28xJXxy計(jì)計(jì)算算方方法法112102211212log02510 xxxxx xx 2112111 32ln10()45xxJ Xxxx022X 計(jì)計(jì)算算方方法

38、法112212(,)0( )0(,)0fxxF xfxx 以以兩兩個(gè)個(gè)方方程程為為例例推推導(dǎo)導(dǎo)( )( )( )( )12( )( )( )( )11112112112212112( )( )( )( )22212212112212212(,)(,)(,)()()(,)(,)(,)()()(,)kkkTkkkkkkkkkkxxxxfffxxfxxxxxxxxlxxfffxxfxxxxxxxxlxx 已已知知第第 次次近近似似值值，在在作作泰泰勞勞展展開(kāi)開(kāi)Newton-Newton-RaphsonRaphson方法的迭代格式的推導(dǎo)方法的迭代格式的推導(dǎo)計(jì)計(jì)算算方方法法11(1)( )12( )(1

39、)( )( )11(1)( )222212,()kkkkkkkkffxxxxxxxJ xffxxxx 記記11(1)( )( )( )1211112(1)( )( )( )222221212(,)(,)kkkkkkkkffxxxxfxxffxxfxxxx 112(1)212(,)( ),()0(,)klxxL xL xlxx 令令，得得到到( )( )( )(1)( )( )()()kkkkkkNewtonJ xxF xxxx 得得迭迭代代格格式式( )(1)1max()kkii nxF x 迭迭代代終終止止標(biāo)標(biāo)準(zhǔn)準(zhǔn)為為或或計(jì)計(jì)算算方方法法( )( )( )( )( )( )( )( )( )

40、1111( )()(,)(,),1,.,kijkkkkkkkkijjjjninkjf xxf xxxhxxf xxhi jn ( )()12kJ xJacobi計(jì)計(jì)算算的的方方法法（ ）解解系系數(shù)數(shù)法法：直直接接計(jì)計(jì)算算出出矩矩陣陣（ ）數(shù)數(shù)值值法法( )( )( )(1)( )( )1( )(1)( )( )1()()()()Newton( )( ( )( )kkkkkkkkkkJ xxF xxxJ xF xxxxg xxJ xF x 的的迭迭代代函函數(shù)數(shù)是是計(jì)計(jì)算算方方法法()()(1)(0)24()()()()46(0)3()(0)()(1()1010(1,2,., )00(1,2,.,

41、 )1010101min,max10(1(1)(2),2,.3).)(,kkkjjjjkkjjkjkjjkkkkjjiijhxxhjncxxhcxjnchhhxxhjn 可可按按以以下下幾幾種種方方案案選選取取取取一一般般計(jì)計(jì)算算方方法法()()()()()()()()()1111()()()()()()()()()1111()()(,)(,),1,.,1(,)(,)kijkkkkkkkkijjjjninkjkkkkkkkkijjjjninkfxxfxxxhxxfxxhi jnfxxxhxxfxxh ( )kjh若取相同的值，則有( (, , )( , , )( ( , ,)( , , )1

42、11 11 11 11( )( (, , )( , , )( ( , ,)( , , )1111kkkkkkkkkkf xhxf xxf xxhf xxnnnnkJ Xkhkkkkkkkkkkf xhxf xxf xxhf xxnnnnnnnn計(jì)計(jì)算算方方法法(,)(,)11111()(,)(,)11(,)(,)1111)(,)(,)11kkkkkkfxhxfxxhnnkJXkhkkkkkkfxhxfxxhnnnnkkkkfxxfxxnnkkkkfxxfxxnnnn ()()kkkJ xxF x 計(jì)計(jì)算算方方法法11(1)11(1)1(,)(,)1111(,)(,)11kkfzkkzfnnkxjkhzkjnxihikkkhzixxniikzjjkkkkkkfxhxfxxhnnkkkkkkfxhxfxxhnnnn 擬牛頓法計(jì)計(jì)算算方方法法111(,)(,)1111(,)(,)11(,)(,)1111(,)(11(1)kniikkfxkkxfnnkkkkkkfxhxfxxhnnkkkkkkfxhxfxxhnnnnkkkkkkfxhxfxxhnnkkkkfxhxfxnnnxh 11111,)(,)(,)1111(,)(,)