典型數(shù)值分析模型

1、 在生產(chǎn)和科學(xué)研究中,經(jīng)常出現(xiàn)這樣的問(wèn)題:由實(shí)驗(yàn)或測(cè)量得到的某一函數(shù) 在一系列點(diǎn) 處的值 ,需要構(gòu)造一個(gè)簡(jiǎn)單函數(shù) 作為函數(shù) 的近似表達(dá)式: ,使得 這類問(wèn)題稱為插值問(wèn)題. 稱為被插值函數(shù), 稱為插值函數(shù) 稱為插值節(jié)點(diǎn);式(6-1)稱為插值條件. 常用的插值函數(shù)是多項(xiàng)式與樣條函數(shù).( )yf x01,nx xx01,nyyy( )x( )yf x( )( )yfxx0011(),(),()nnxyxyxy( )f x( )x01,nx xx(6 1)拉格朗日(lagrange)插值取n次多項(xiàng)式pn(x)作為插值函數(shù) pn(x)=a0+a1x+a2x2+anxn 利用插值條件有： 其系數(shù)行列式為n

2、+1階范德蒙行列式，因插值節(jié)點(diǎn) 互不相同，所以方程組的解存在且唯一。nnnnnnnnnnyxaxaxaayxaxaxaayxaxaxaa22101121211000202010(62)(63) 其系數(shù)行列式為范德蒙(Vandermonde)行列式: 由于插值節(jié)點(diǎn) 互不相同,所以上述行列式不等于0,故由克萊姆(Cramer)法則知,方程組(6-3)的解存在而且是唯一的. 實(shí)際上比較簡(jiǎn)單的方法不是解方程組(6-3),而是構(gòu)造一組插值基函數(shù).為此,首先求滿足條件20002111211()1nnjij innnnxxxxxxxxxxxijijxLji10)(（6-4）（j=0n）ix 的n次多項(xiàng)式 因

3、為式（6-4）表明，除 點(diǎn)以外，其他所有的節(jié)點(diǎn)都是n次多項(xiàng)式 的零點(diǎn)，故設(shè) 其中A為待定常數(shù)。由 可得 所以( )(0)iL x inix( )iL x011( )()()()()iiinL xA xxxxxxxx( )1iiL x01100111()()()()()( )()()()()()njiinijiiiiiinijjxxxxxxxxxxL xxxxxxxxxxx(0,1, )in0111()()()()iinAxxxxxxxx(65) 稱之為拉格朗日插值基函數(shù)。 利用插值基函數(shù)（6-5），可以構(gòu)造多項(xiàng)式 就是滿足插值條件 的拉格郎日插值問(wèn)題的解，稱式（6-6）為拉格朗日插值多項(xiàng)式。

4、特別地，當(dāng)n=1時(shí)稱為線性插值，其插值多項(xiàng)式為： 滿足 從幾何上看, 為過(guò)兩點(diǎn) 的直線。00111( )( )( )( )( )nnnniiiP xy L xy L xy L xy L x(66)011010110( )xxxxp xyyxxxx1( )iip xy(0,1)i 1( )yp x0011(,),( ,)xyx y()niiP xy0in 當(dāng)n=2時(shí)，稱為拋物線插值，其插值多項(xiàng)式為： 滿足 從幾何上看 為過(guò)點(diǎn) 和 的一條拋物線。0201122012010210122021()()()()()()( )()()()()()()xxxxxxxxxxxxP xyyyxxxxxxxxxx

5、xx2( )iiP xy(0,1,2)i 2( )yP x0011(,),( ,)xyx y22(,)xy 埃爾米特插值 許多插值問(wèn)題不但要求在節(jié)點(diǎn)上函數(shù)值相等，而且還要求對(duì)應(yīng)的導(dǎo)數(shù)值也相等，甚至要求高階導(dǎo)數(shù)也相等，滿足這種要求的插值多項(xiàng)式被稱為埃爾米特（Hermite）插值多項(xiàng)式設(shè)在節(jié)點(diǎn) 上， 要求插值多項(xiàng)式 ，滿足條件 由于（6-7）式給出了2n+2個(gè)條件，因此可以唯一確定一個(gè)次數(shù)不超過(guò)2n+1的多項(xiàng)式 ，其形式為 根據(jù)（6-7）式來(lái)確定 顯然非常復(fù)雜。01naxxxb(),()(0,1, )jjjjyf xmfxjn( )H x(),()jjjjH xyHxm(0,1, )jn(67)2

6、1( )( )nHxH x21210121( )nnnHxaaax0121,na aa 仿照拉格朗日插值多項(xiàng)式的基函數(shù)方法，可先求插值基函數(shù) ，及 共用2n+2個(gè)，每一個(gè)基函數(shù)都是2n-1次多項(xiàng)式，且滿足條件 于是滿足條件（6-7）的插值多項(xiàng)式 可寫成 由條件（6-8）式顯然有( )(0,1, )jxjn0,(), ()0;1,()0;()( ,0,1,)jkjkjkjkjkjkjkxxjkxxj kn(68)21( )( )nH xHx210( )( )( )nnjjjjjHxyxmx2121();()(0,1, )nkknkkHxy Hxm kn(69)(xj 利用拉格朗日插值基函數(shù) 令

7、其中 為（6-5）式所表示的基函數(shù)。 由條件（6-8）式可得 整理得: 解出 對(duì) 兩邊取對(duì)數(shù)求導(dǎo)可得 于是 ( )jlx2( )() ( )jjxaxb lx( )jlx2()() ()1jjjjjxaxb lx1()()()2() ()0jjjjjjjjjxlxalxaxb lx12 ()0jjjaxbalx2 (),12 ()jjjjjalxbx lx ( )jlx01 ()njjkjkkjlxxx201( )(1 2() ( )njjjkjkkjxxxlxxx 同理 仿照拉格朗日插值余項(xiàng)的證明方法，若 在 內(nèi)的2n+2階導(dǎo)數(shù)存在，則其插值余項(xiàng)為 其中2( )() ( )jjjxxx lx

8、( )f x(22)2211( )( )( )( )( )(22)nnnflR xf xHxxnj( , )a b( , )la b10( )()nnjjxxx 三次樣條插值 分段線性插值，具有良好的穩(wěn)定性和收斂性，但光滑性較差。在數(shù)學(xué)上若函數(shù)（曲線）的k階導(dǎo)數(shù)存在且連續(xù)，則稱該曲線具有k階光滑性。易見(jiàn)，分段線性插值不光滑，這影響了它在某些工程技術(shù)實(shí)際問(wèn)題中的應(yīng)用。例如：在船體、飛機(jī)等外形曲線的設(shè)計(jì)中，不僅要求曲線連續(xù)而且還要求曲線的曲率連續(xù)，這就要求插值函數(shù)具有連續(xù)的二階導(dǎo)數(shù)。為解決這一類問(wèn)題，就產(chǎn)生了三次樣條插值。 所謂樣條（Spline），本來(lái)是指一種繪圖工具，它是一種富有彈性的細(xì)長(zhǎng)木條

9、，在飛機(jī)或輪船制造過(guò)程中，被用于描繪光滑的外形曲線。使用時(shí)，用壓鐵將其固定在一些給定的節(jié)點(diǎn)上，在其他地方任其自然彎曲，然后依樣畫下的光滑曲線，就稱為樣條曲線。它實(shí)際上是由分段三次曲線拼接而成，在連續(xù)點(diǎn)即節(jié)點(diǎn)上，不僅函數(shù)自身是連續(xù)的，而且它的一階和二階導(dǎo)數(shù)也是連續(xù)的。從數(shù)學(xué)上加以概括，可得到樣條函數(shù)的定義如下： 三次樣條函數(shù)記作S（x），axb，滿足： 在每個(gè)小區(qū)間xi，xi+1（i=0,1,n- 1）是三次多項(xiàng)式 在每個(gè)內(nèi)節(jié)點(diǎn)xi（i=1,2,n-1）上具有二次連續(xù)導(dǎo)數(shù) S（xi）=yi，i=0,1,2,n 由三次樣條函數(shù)中的條件知，S（x）有4n個(gè)待定系數(shù)。由條件知，S（x）在n-1個(gè)內(nèi)節(jié)點(diǎn)

10、上具有二階連續(xù)導(dǎo)數(shù)，即滿足條件：(0)(0)(0)(0)(0)(0)iiiiiiS xS xS xS xSxSx(0,1,2,1)in(6 10) 共有3（n-1）個(gè)條件。由條件，知S（xi）=yi（i=0,1,2,n），共有n+1個(gè)條件。因此，要確定一個(gè)三次樣條，還需要外加4n - 3（n - 1）-（n+1）=2個(gè)條件，最常用的三次樣條函數(shù)S（x）的邊界條件有兩類： 第一類邊界條件： 第二類邊界條件： 特別地， ,稱為自然邊界條件 第三類邊界條件： 稱為周期邊界條件。三次樣條插值不僅光滑性好，而且穩(wěn)定性和收斂性都有保證，具有良好的逼近性質(zhì)。 樣條插值函數(shù)的建立nnmxSmxS)( ,)(

11、00nnMxSMxS)( ,)( 000)( , 0)( 0nxSxS),( )( ),()(00nnxSxSxSxS)()(0nxSxS 構(gòu)造滿足條件的三次樣條插值函數(shù) 的表達(dá)式可以有多種方法。下面我們利用 的二階導(dǎo)數(shù)值 表達(dá) ，由于 在區(qū)間 上是三次多項(xiàng)式，故 在 上是線性函數(shù)，可表示為 其中 對(duì) 積分兩次并利用 及 ，可定出積分常數(shù)，于是得三次樣條表達(dá)式( )S x( )S x()(0,1, )jjSxMjn( )S x( )S x1,jjx x1,jjxx( )Sx11( )jjjjjjxxxxSxMMhh(6 11)1jjjhxx( )Sx()jjS xy11()jjS xy3311

12、()()( )66jjjjjjxxxxS xMMhh22111()()(0,1,1)66jjjjjjjjjjM hxxMhxxyyjnhh(6 12) 上式中 是未知的，為確定 對(duì) 求導(dǎo)得 由此可得 類似地可求出 在區(qū)間 上的表達(dá)式，從而得 利用 可得 (0,1, )jMjn,(0,1, )jMjn( )S x2211()()( )22jjjjjjxxxxS xMMhh 116jjjjjjyyMMhh(6 13)( )S x1,jjxx11111(0)63jjjjjjjjhhyyS xMMh(0)(0)jjS xS x112(1,2,1)jjjjjjMMMdjn(6 14)11(0)366jj

13、jjjjjhhyyS xMM 其中 對(duì)第一類邊界條件 ，可導(dǎo)出兩個(gè)方程111,0,1,jjjjjjjjhhjnhhhh11111,66 ,jjjjjjjjjjf xxf xxdf xxxhh11()(),jjjjjf xf xf xxh(6 15)11111,jjjjjjjjf xxf xxf xxxh00() ,()nnS xfS xf01010011162( , )62(,)nnnnnnMMf x xfhMMff xxh(6 16) 如果令 則式（6-14）及其（6-16）可寫出矩陣 通過(guò)求解上述三對(duì)角矩陣可求得 對(duì)于第二類邊界條件，直接得端點(diǎn)方程00010061,( , ),1ndf x

14、 xfh116(,)nnnnndff xxh000111111112222nnnnnnnMdMdMdMd(6 17)01,nMMM00MfnnMf(6 18) 如果令 ，則式（6-14）及式（6-18）也可以寫成矩陣（6-17）的形式 對(duì)于第三類邊界條件，可得 其中 則式（6-14）及式（6-19）可以寫成矩陣形式 求解上述矩陣可得 00000,2 ,2 nndfdf0nMM112nnnnnMMMd011010,1nnnnnnhhhhhh 01101,6nnnnf xxf xxdhh11112222111122222nnnnnnnMdMdMdMd121,nnM MMM(6 19) 曲線擬合 通

15、過(guò)實(shí)驗(yàn)等方法觀測(cè)到反映某個(gè)函數(shù)y = f(x) 的數(shù)據(jù)(xi，yi)（i=1,2,n），要求利用這些數(shù)據(jù)構(gòu)造出y=f（x）的近似表達(dá)式y(tǒng)=P（x），上面介紹的插值法就是尋求近似函數(shù)的方法之一。但由于實(shí)驗(yàn)觀測(cè)數(shù)據(jù)不可避免地帶有誤差，甚至是較大的誤差，所以使用插值法是不合適的，它會(huì)保留數(shù)據(jù)的誤差。因此，不必要求近似函數(shù)y=P（x）滿足 P（xi）=yi（i=1,n），而只要求偏差按某種標(biāo)準(zhǔn)最小，以反映所給數(shù)據(jù)的總體趨勢(shì)，消除局部波動(dòng)的影響，這就是曲線擬合問(wèn)題。這樣的函數(shù)P（x）稱為擬合函數(shù)。 擬合的準(zhǔn)則： 衡量一個(gè)函數(shù)P（x）同所給數(shù)據(jù)（xi，yi）（i=1,n）的偏差 的大小，常用的準(zhǔn)則有如下三

16、種：), 1( , )(nixPyiii(1)最小二乘準(zhǔn)則：使偏差 的平方和最小，即(2)最小一乘準(zhǔn)則：使偏差 的絕對(duì)值之和為最小，即(3)極小極大準(zhǔn)則：使偏差 的最大絕對(duì)值最小，即nii12minnii1miniimaxmin(1,2, )iin(1,2, )iin(1,2, )iin 計(jì)算的方法(1)最小二乘準(zhǔn)則下的計(jì)算方法設(shè) 為m個(gè)線性無(wú)關(guān)的函數(shù)，對(duì)給定的數(shù)據(jù)（xi，yi）（i=1,2,n），求使 最小。利用極值的必要條件 得到關(guān)于 的線性方程組 )(,),(),(21xxxm1122( )( )( )( )mmP xaxaxaxniiiniimxPyaaaQ121221)(),(),

17、2 , 1(0mkaQknimkikkiimnimkikkiinimkikkiixayxxayxxayx111121110) )()(0) )()(0) )()(maaa,21 則方程組可表示為 ，其中 由于 線性無(wú)關(guān)，所以G是列滿秩，GTG是可逆矩陣，方程組的解存在且唯一，并且 常用的擬合曲線: Tmaaaa),(21TnyyyY),(21YGGaGTTmnnmnnmmxxxxxxxxxG)()()()()()()()()(212222111211)(,),(1xxmYGGGaTT1)(a)取 ，得直線擬合(b)取 ，得多項(xiàng)式擬合(c)取 ，得多元線性擬合(d)取 ，則得曲線擬合 xxx)(

18、, 1)(21xaaxP21)(mmxxxxx)(,)(, 1)(21mmxaxaaxP21)(mmxxxxxx)(,)(,)(2211mmmxaxaxaxxxP221121),(xxx1)(, 1)(21xaaxP21)( 還有許多非線性擬合，例如，S曲線 可通過(guò)變量代換，令 ， ，化為對(duì) a1，a2的線性函數(shù) 。 一般地，已知一組數(shù)據(jù)，先畫出數(shù)據(jù)的散點(diǎn) 圖，在直觀判斷的基礎(chǔ)上，選幾種曲線分別作擬 合，選擇偏差平方和Q最小的曲線。xeaay211yY1xeXXaaY21(2)最小一乘準(zhǔn)則下的計(jì)算方法 設(shè) 為m個(gè)線性無(wú)關(guān)的函數(shù)，對(duì)給定的數(shù)據(jù)（xi，yi）（i=1,2,n），求 使 達(dá)到最小。易

19、見(jiàn)式中目標(biāo)函數(shù)含有絕對(duì)值，為了去掉上式中的絕對(duì)值，令)1(2,2niVUiiiiiiniimaaaQ121),()()()()(2211xaxaxaxPmm)(,),(),(21xxxm(620) 則Ui0，Vi0，且 此時(shí)（6-20）式可改寫為相應(yīng)地（6-21）式可改寫為 綜合以上幾個(gè)式子，求得 的問(wèn)題可歸結(jié)為如下線性規(guī)劃問(wèn)題： 為任意常數(shù) niiimVUaaaQ121)(min),(min)1(,niUVVUiiiiiiiiiimmiiyVUxaxaxa)()()(2211maaa,21maaa,21niiiVU1)(minniVUyVUxaxaxat siiiiiimmii1, 0, 0

20、)()()(.2211(621)(622)(3)極小極大準(zhǔn)則下的計(jì)算方法設(shè) 為m個(gè)線性無(wú)關(guān)的函數(shù)， 對(duì)給定的數(shù)據(jù)（xi，yi）（i=1,2,n），求 使 達(dá)到最小。上式可改寫為)(,),(),(21xxxmmiiixaxP1)()(inimaaaQ121maxmin),()(maxmin),(121iinimVUaaaQ(623) 記 ，則求解 的問(wèn)題可 歸結(jié)為如下線性規(guī)劃問(wèn)題： 為任意常數(shù)0, 0)()()()1( , 0min2211iiiiimmiiiiVUVUxaxaxaniVURRmaaa,21)(max1iiniVURmaaa,21 本節(jié)主要討論單變量非線性方程 的求根問(wèn)題，這里

21、。在科學(xué)與工程計(jì)算中有大量方程求根問(wèn)題，其中一類特殊的問(wèn)題是多項(xiàng)式方程 其中系數(shù) 為實(shí)數(shù)。 方程 的根 ，又稱為函數(shù) 的零點(diǎn)， 它使 ，若 可分解為 其中 為正整數(shù)，且 。當(dāng) 時(shí)，則稱 單根，若 稱 為 重根，或 為 的 重零點(diǎn)。若 是 的 重零點(diǎn)，且 充分光滑，則*(1)*()*()()()0,()0mmf xfxfxfx( )g xm( )f x*xm( )f x*xm*x1m *x1m *()0g xm*( )()( )mf xxxg x( )f x*()0f x( )f x*x( )0f x (0,1, )ia in(625)0(0)a 1011( )nnnnf xa xa xaxa,

22、( ) , xR f xC a b(624)( )0f x 當(dāng) 為代數(shù)多項(xiàng)式（6-25）時(shí)，根據(jù)代數(shù)基本定理可知，n次方程在復(fù)數(shù)域中有且只有n個(gè)根（含復(fù)根，m重根為m個(gè)根），n=1，2時(shí)方程的根是大家熟悉的，n=3，4時(shí)雖有求根公式但比較復(fù)雜，可在數(shù)學(xué)手冊(cè)中查到，但已不適合于數(shù)值計(jì)算，而 時(shí)就不能用公式表示方程的根。因此，通常對(duì) 的多項(xiàng)式方程求根與一般連續(xù)函數(shù)方程（6-20）一樣都可采用迭代法求根。迭代發(fā)要求先給出根 的一個(gè)近似， 若 且 ，根據(jù)連續(xù)函數(shù)性質(zhì)可知 在 內(nèi)至少有一個(gè)實(shí)根，這時(shí)稱 為方程（6-20）的有根區(qū)間。通?？赏ㄟ^(guò)逐次搜索法求得方程的有根區(qū)間。 , a b( , )a b(

23、)0f x ( ) ( )0f a f b ( ) , f xC a b*x3n 5n ( )f x 例1.求方程 的有根區(qū)間。 解：f(0)0,f(1)0,f(3)0,f(4)0, f(5)0; 由此可知，方程的有根區(qū)間為1,2,3,4,5,6; 練習(xí):求方程 的有根區(qū)間。077.418 .381 .11)(23xxxxf083682)(2345xxxxxg 1不動(dòng)點(diǎn)迭代法 將方程（6-24）改寫成等價(jià)的形式 若要求 滿足 ，則 ；反之亦然，稱 為函數(shù) 的一個(gè)不動(dòng)點(diǎn)。求 的零點(diǎn)就等價(jià)于求 的不動(dòng)點(diǎn)，選擇一個(gè)初始近似值 ，將它代入（6-26）右端，即可求得 可以如此反復(fù)迭代計(jì)算 稱為迭代函數(shù)。

24、如果對(duì)任何 ，由（6-27）得到的序列 有極限 則稱迭代方程（6-27）收斂，且 為 的不動(dòng)點(diǎn)，故稱（6-27）為不動(dòng)點(diǎn)迭代法。( )x*()xx*limkkxxkx0 , xa b( )x(627)(0,1,)k 1()kkxx10()xx0 x( )x( )f x( )x*x*()xx*()0f x*x(626)( )xx 上述迭代是一種逐次逼近法，其基本思想是將隱式方程（6-26）歸結(jié)為一組顯式的計(jì)算公式（6-27），就是說(shuō)，迭代過(guò)程實(shí)質(zhì)上是一個(gè)逐步顯式化的過(guò)程。 方程 的求根問(wèn)題在xy平面上就是在確定曲線 與直線y=x交點(diǎn) ，對(duì)于 的某個(gè)近似值 ，在曲線 上可確定一點(diǎn) ,它以 為橫坐標(biāo)

25、，而縱坐標(biāo)則等于 。過(guò) 引平行x軸的直線，設(shè)此直線交直線y=x于點(diǎn) ，然后過(guò) 再作平行于y軸的直線，它與曲線 的交點(diǎn)記作 ，則點(diǎn) 的橫坐標(biāo)為 ，縱坐標(biāo)則等于 ，在曲線 上得到點(diǎn)列 ，其橫坐標(biāo)分別為依公式 求得的迭代值 。如果點(diǎn)列 趨向于點(diǎn) ，則相應(yīng)的迭代值 收斂到所求的根 。*xkx*PkP12,x x 1()kkxx12,P P ( )yx12()xx1x1P1P( )yx1Q1Q0P( )yx0 x*x*P( )yx( )xx0 x0P01()xx 2不動(dòng)點(diǎn)的存在性與迭代法的收斂性 首先考察 在 上不動(dòng)點(diǎn)的存在唯一性。 定理1 設(shè) 滿足以下兩個(gè)條件： （1）對(duì)任意的 有 。 （2）存在正常

26、 ，使對(duì)任意 都有 則 在 上存在唯一的不動(dòng)點(diǎn) 。 在 的不動(dòng)點(diǎn)存在唯一的情況下，可得到迭代法（6-27）收斂的一個(gè)充分條件。 定理2 設(shè) 滿足定理1中的兩個(gè)條件，則對(duì)任意 ，由（6-27）得到的迭代序列 收斂到 的不動(dòng)點(diǎn) ，并有誤差估計(jì)( )x*x , a b( )x(628)( )( )xyL xy, , x ya b1L ( )axb , xa b( ) , xC a b , a b( )x*x( )xkx0 , xa b( ) , xa b 迭代過(guò)程是個(gè)極限過(guò)程。在用迭代法進(jìn)行實(shí)際計(jì)算時(shí)，必須按精度要求控制迭代次數(shù)。誤差估計(jì)式（6-29）原則上可用于確定迭代次數(shù)，但它由于含有信息L而不

27、便于實(shí)際應(yīng)用。 根據(jù)式(6-30)，對(duì)任意的正整數(shù)p有 在上式中令 知 由此可見(jiàn)，只要相鄰兩次計(jì)算結(jié)果的偏差 足夠小即可保證近似值 具有足夠的精度。kx1kkxx*111kkkxxxxLp 12111(1)1ppkpkkkkkxxLLxxxxL(629)*101kkLxxxxL 對(duì)定理1和定理2中的條件（2），在使用時(shí)如果 且對(duì)任意 有 則由中值定理可知對(duì) 有 它表明定理中的條件（2）可用（6-30）代替。 3局部收斂性與收斂階 上面給出了迭代序列 在區(qū)間 上的收斂性，通常稱為全局收斂性。有時(shí)不易檢驗(yàn)定理的條件，實(shí)際應(yīng)用時(shí)通常只在不動(dòng)點(diǎn) 的鄰近考察其收斂性，即局部收斂性。*x , a bkx(

28、 )( )( )(),( , )xyxyL xya b , , x ya b(630)( )1xL , xa b1( ) , xC a b 定義1 設(shè) 有不動(dòng)點(diǎn) ，如果存在 的某個(gè)鄰域 ，對(duì)任意 ，迭代（6-26）產(chǎn)生的序列 。且收斂到 ，則稱迭代法（6-26）局部收斂。 定理3 設(shè) 為 的不動(dòng)點(diǎn)， 在 的某個(gè)鄰域連續(xù)，且 ，則迭代法（6-26）局部收斂。 為衡量迭代法收斂速度的快慢，我們給出下列定義。 定義2 設(shè)迭代過(guò)程 收斂于方程 的根 ，如果迭代誤差 當(dāng) 時(shí)成立下列漸進(jìn)關(guān)系式 0C （常數(shù)）1kpkeCex *kkexx*x( )xx1()kkxx*()1x*x( ) x( )x*x*x

29、kxR0 xR*:Rxx*x*x( )x 則稱該迭代過(guò)程是P階收斂的，特別地，P=1時(shí)稱線性收斂，P1時(shí)稱超線性收斂，P=2時(shí)稱平方收斂。 定理4 對(duì)于迭代過(guò)程 ，如果 在所求根 的鄰近連續(xù)，并且 則該迭代過(guò)程在點(diǎn) 鄰近是p階收斂的。 上述定理告訴我們，迭代過(guò)程的收斂速度依賴于迭代函數(shù) 的選取，如果當(dāng) 時(shí) ，則該迭代過(guò)程只可能是線性收斂。( )0 x , xa b( )x*x( )*()0px*(1)*( )( )( ) 0pxxx*x( )( )px1()kkxx 1.牛頓法對(duì)于方程 如果 是線性函數(shù)，則它的求根是容易的，牛頓法實(shí)質(zhì)上是一種線性化方法，其基本思想是將非線性方程 逐步歸結(jié)為某種

30、線性方程來(lái)求解。設(shè)已知方程 有近似根 （假定 ），將函數(shù) 在點(diǎn) 展開(kāi)，有 于是方程 可近似地表示為 (632)()()()0kkkf xfxxx( )0f x ( )()()()kkkf xf xfxxxkx( )f x()0kfxkx( )0f x ( )0f x ( )f x( )0f x 這是個(gè)線性方程，記其根為 ，則 的計(jì)算公式為 這就是牛頓（Newton）法。 牛頓法有明顯的幾何解釋，方程 的根 可解釋為曲線 與x軸的交點(diǎn)的橫坐標(biāo)，設(shè) 是根 的某個(gè)近似值，過(guò)曲線 上橫坐標(biāo)為 的點(diǎn) 引切線，并將該切線與x軸的交點(diǎn)的橫坐標(biāo) 作為 的新的近似值。注意到切線方程為 這樣求得的值 必滿足（6-

31、32）從而就是牛頓公式（6-33）的計(jì)算結(jié)果。由于這種幾何背景，牛頓法亦稱切線法。1kx()()()kkkyf xfxxx*x1kxkPkx( )yf x*xkx( )yf x*x( )0f x (633)1kx1kx), 1 , 0( ,)()(1kxfxfxxkkkk 關(guān)于牛頓法（6-33）的收斂性，可直接由定理4得到，對(duì)（6-33）其迭代函數(shù)為 由于 假定 是 的一個(gè)單根，即 ，則由上式知 ，于是依據(jù)定理4可以斷定，牛頓法在根 的鄰近是平方收斂的。又因 ，可得 (634)*1*()lim()2()kkkxxfxxxfx*()()()fxxfx*x*()0 x*()0,()0f xfx(

32、)f x*x2( ) ( )( )( )f x fxxfx( )( )( )f xxxfx 2.簡(jiǎn)化牛頓法與牛頓下山法 牛頓法的優(yōu)點(diǎn)是收斂快，缺點(diǎn)是每步迭代要計(jì)算 及 ，計(jì)算量較大且有時(shí) 計(jì)算較困難，二是初始近似 只在根 附近才能保證收斂，如 給的不合適可能不收斂。為克服這兩個(gè)缺點(diǎn)，通常可用下述方法。 (1)簡(jiǎn)化牛頓法，也稱平行弦法，其迭代公式為 迭代函數(shù) 若 ，即取 。在根 附近成立，則迭代法（6-35）局部收斂。*x0( )2Cfx( )1( )1xCfx( )( )xxCf x(635)0,0,1,Ck1()kkkxxCf x0 x*x0 x()kfx()kfx()kf x 在（6-35

33、）中取 ，則稱為簡(jiǎn)化牛頓法， 這類方法計(jì)算量省，但只有線性收斂，其幾何意義是用平行弦與x軸交點(diǎn)作為 的近似。（2）牛頓下山法。牛頓法收斂性依賴初值 的選取。如果 偏離所求根 較遠(yuǎn)，則牛頓法可能發(fā)散。 例如，用牛頓法求解方程 此方程在 附近的一個(gè)根 。設(shè)取迭代初值 ，用牛頓法公式(637)312131kkkkkxxxxx01.5x *x(636)310 xx 1.5x *x0 x0 x*x01()Cfx 計(jì)算得 迭代三次得到的結(jié)果 有六位有效數(shù)字。 但是，如果改用 作為迭代初值，則依牛頓法公式（6-37）迭代一次得 這個(gè)結(jié)果反而比 更偏離了所求的根 為了防止迭代發(fā)散，我們對(duì)迭代過(guò)程再附加一項(xiàng)要求

34、，即具有單調(diào)性： 滿足這項(xiàng)要求的算法稱為下山法。(638)1()()kkf xf x*1.32472x 00.6x 117.9x 00.6x 3x1231.34783,1.32520,1.32472xxx 我們將牛頓法和下山法結(jié)合起來(lái)使用，即在下山法保證函數(shù)值穩(wěn)定下降的前提下，用牛頓法加快收斂速度。為此，我們將牛頓法的計(jì)算結(jié)果 與前一步的近似值 適當(dāng)加權(quán)平均作為新的改進(jìn)值 其中 稱為下山因子，（6-39）即為 (640)1()(0,1,)()kkkkf xxxkfx(01)(639)11(1)kkkxxxkx1()()kkkkf xxxfx 稱為牛頓下山法。選擇下山因子時(shí)從 開(kāi)始，逐次將 減半

35、進(jìn)行試算，直到能使下降條件（6-38）成立為止。若用此法解方程（6-36），當(dāng) 時(shí)由（6-37）求得 ，它不滿足條 件（6-38），通過(guò) 逐次取半進(jìn)行試算，當(dāng) 時(shí)可求得 。此時(shí)有 而 ，顯然 。由 計(jì)算 時(shí) ，均能使條件（6-33）成立。計(jì)算結(jié)果如下：221.36181,()0.1866;xf x123,x x 1x10()()f xf x0()1.384f x 1()0.656643f x 11.140625x 13200.6x 1117.9x 即為 的近似。一般情況只要能使條件（6-38）成立，則可得到 ，從而使 收斂。kxlim()0kkf x*x4x441.32472,()0.0000

36、086.xf x331.32628,()0.00667;xf x 用牛頓法求方程（6-24）的根，每步除計(jì)算 外還要算 ，當(dāng)函數(shù) 比較復(fù)雜時(shí)，計(jì)算 往往較困難，為此可以利用已求函數(shù)值 來(lái)回避導(dǎo)數(shù)值 的計(jì)算的計(jì)算，這類方法是建立插值原理基礎(chǔ)上的，下面介紹兩種常用方法。 1弦截法 設(shè) 是 的近似根，我們利用 構(gòu)造一次插值多項(xiàng)式 ，并用 的根作為 的新的近似根 。由于 (641)111()()( )()()kkkkkkf xf xp xf xxxxx1kx( )0f x 1( )0p x 1( )p x1(),()kkf xf x( )0f x 1,kkxx()kfx1(),(),kkf xf x(

37、 )fx( )f x()kfx()kf x 因此有 這樣導(dǎo)出的迭代公式（6-42）雙點(diǎn)弦截法可以看作牛頓公式 中的導(dǎo)數(shù) 用差商 取代的結(jié)果。 現(xiàn)在解釋這種迭代過(guò)程的幾何意義。如圖6-4，曲線 上橫坐標(biāo)為 的點(diǎn)分別記為 ，則弦線 的斜率等于差商值 11()()kkkkf xf xxx1kkP P1,kkP P1,kkxx( )yf x11()()kkkkf xf xxx()kfx1()()kkkkf xxxfx(642)111()()()()kkkkkkkf xxxxxf xf x 其方程是 因此，按（6-42）式求得的 實(shí)際上是弦線 與x軸交點(diǎn)的橫坐標(biāo)。這種算法因此而稱為弦截法。 弦截法與切線

38、法（牛頓法）都是線性化方法，但兩者有本質(zhì)的區(qū)別。切線法在計(jì)算 時(shí)只用到前一步的值 ，而弦截法（6-42），在求 時(shí)要用到前面兩步的結(jié)果 ，因此使用這種方法必須先給出兩個(gè)初始值 。01,xx1,kkxx1kxkx1kx1kx11()()()()kkkkkkf xf xyf xxxxx1kkP P 2拋物線法 設(shè)已知方程 的三個(gè)近似根 ，我們以這三點(diǎn)為節(jié)點(diǎn)構(gòu)造二次插值多項(xiàng)式 。并適當(dāng)選取 的一個(gè)零點(diǎn) 作為新的近似根，這樣確定的迭代過(guò)程稱拋物線法。亦稱密勒（Mller）法。在幾何圖形上，這種方法的基本思想是用拋物線 與x軸交點(diǎn) 作為所求根 的近似位置（圖6-5）。 現(xiàn)在推導(dǎo)拋物線法的計(jì)算公式。插值多

39、項(xiàng)式121,()()kkkkkf xxxxxxx21( )(),()kkkkp xf xf x xxx*x1kx2( )ypx1kx2( )px2( )px12,kkkxxx( )0f x 有兩個(gè)零點(diǎn) 式中 為了從（6-43）中定出一個(gè)值 ，我們需要討論根式前正負(fù)號(hào)的取舍問(wèn)題。 在 三個(gè)近似根中，自然假定 更接近所求的根 ，這時(shí)，為了保證精度，我們選 式（6-43）中較接近 的值作為新的近似根 。為此，只要取根式前的符號(hào)與 的符號(hào)相同。1kxkx*xkx12,kkkxxx1kx1121,()kkkkkkkf xxf xxxxx(643)12122 ()4 () ,kkkkkkkf xxxf x

40、f xxxti（從（從11歲起年齡）歲起年齡）0 0.8 1.4 2.0 2.4 3.2 4.0 增長(zhǎng)高度增長(zhǎng)高度hi（cm） 0 0.74 2.25 5.25 8.25 15.00 21.38 ti（從（從11歲起年齡）歲起年齡） 4.8 5.4 6.0 7.0 8.0 10.0 增長(zhǎng)高度增長(zhǎng)高度hi（cm） 26.25 28.88 30.60 32.25 33 35 u孩子成長(zhǎng)問(wèn)題u一個(gè)男孩在11歲長(zhǎng)到21歲過(guò)程中，身高的變化 如表5-1所示，試找一個(gè)最佳的函數(shù)曲線來(lái)表示這個(gè)男孩的成長(zhǎng)過(guò)程。 智商（Iq） 105 110 120 116 122 130 114 102復(fù)習(xí)時(shí)間（t） 10

41、12 6 13 16 8 20 15 考試成績(jī)（g） 75 79 68 85 91 79 98 76 學(xué)生考試成績(jī)問(wèn)題： 對(duì)8個(gè)學(xué)生測(cè)量其智商Iq和課后復(fù)習(xí)某門課時(shí)間t 及該門課考試成績(jī)g，得表5-2，試研究該門課考試成績(jī)與智商和課后復(fù)習(xí)時(shí)間之間的關(guān)系。 表5-2 Mathematica和MATLAB求解 （1）Mathematica命令利用Mathematica可計(jì)算曲線擬合，命令輸入格式為 例如，可以利用Mathematica中的Fit命令計(jì)算本節(jié)中的實(shí)際問(wèn)題。孩子成長(zhǎng)問(wèn)題的計(jì)算：首先利用表52中的離散數(shù)據(jù)，畫出散點(diǎn)圖。),(,),(),( ,;, ,212211變量xxxdataFity

42、xyxyxdatamnn 孩子成長(zhǎng)問(wèn)題ch531文件名：ch531.mad1=0,0,0.8,0.74,1.4,2.25,2.0,5.25,2.4,8.25,3.2,15.00, 4.0,21.38,4.8,26.25,5.4,28.88, 6.0,30.60,7.0,32.25,8.0,33, 10.0,35 ;gp=ListPlotd1,PlotStyle-PointSize0.01 從圖53可見(jiàn)，取正弦級(jí)數(shù)為擬合曲線較為合適，為此令用Mathematica計(jì)算中的參數(shù)a1,a2,a3。輸入命令：f=Fitd1,SinPi*t/20,Sin3*Pi*t/20,Sin5*Pi*t/20,tf

43、p=Plotf,t,0,10Showgp,fp運(yùn)行后顯示 205sin)(,203sin)(,20sin)(321tttttt)()()()(332211tatatatP435379. 320325799. 1202317.352tPiSintPiSintPiSinout學(xué)生考試成績(jī)問(wèn)題的計(jì)算：1. 最小二乘準(zhǔn)則利用表5-2中的離散數(shù)據(jù)，在Mathematica中輸入：文件名：ch532d1=105,10,75,110,12,79,120,6,68,116,13,85,122,16,91,130,8,79,114,20,98,102,15,76; g=Fitd1,1,iq,t,iq,t執(zhí)行后輸

44、出0.736555 + 0.473084 iq + 2.10344 tv最小一乘準(zhǔn)則取 則線性規(guī)劃問(wèn)題為)()(),()(, 1)(321itxiiqxxiii761510298201147981309116122851311668612079121107510105.8832177321663215532144321333212232111321VUaaaVUaaaVUaaaVUaaaVUaaaVUaaaVUaaaVUaaats81)(miniiiVU 在Mathematica中輸入：學(xué)生成績(jī)問(wèn)題ch533文件名：ch533.ma c=u1+v1+u2+v2+u3+v3+u4+v4+u5+v

45、5+u6+v6+u7+v7+u8+v8;m=a1+105*a2+10*a3-u1+v1=75, a1+110*a2+12*a3-u2+v2=79, a1+120*a2+6*a3-u3+v3=68, a1+116*a2+13*a3-u4+v4=85, a1+122*a2+16*a3-u5+v5=91, a1+130*a2+8*a3-u6+v6=79, a1+114*a2+20*a3-u7+v7=98, a1+102*a2+15*a3-u8+v8=76; ConstrainedMinc,m,u1,v1,u2,v2,u3,v3,u4,v4,u5,v5,u6,v6,u7,v7,u8,v8,a1,a2,

46、a3/N執(zhí)行后輸出13.9318, u1 - 0, v1 - 2.47727, u2 - 0, v2 - 0, u3 - 2.36364, v3 - 0, u4 - 0, v4 - 1.25, u5 - 1.81818, v5 - 0, u6 - 0, v6 - 0, u7 - 0, v7 - 0, u8 - 6.02273, v8 - 0, a1 - 5.59091, a2 - 0.431818, a3 - 2.15909從輸出結(jié)果易見(jiàn)g=5.59091+0.431818iq+2.15909t v極小極大準(zhǔn)則取v 則線性規(guī)劃問(wèn)題為：)81(07615102982011479813091161

47、22851311668612079121107510105.8832177321663215532144321333212232111321iVURVUaaaVUaaaVUaaaVUaaaVUaaaVUaaaVUaaaVUaaatsii)()(),()(, 1)(321itxiiqxxiiiRmin 在Mathematica中輸入：學(xué)生成績(jī)問(wèn)題ch534文件名：ch534.mac=R;m=a1+105*a2+10*a3-u1+v1=75, a1+110*a2+12*a3-u2+v2=79, a1+120*a2+6*a3-u3+v3=68, a1+116*a2+13*a3-u4+v4=85, a

48、1+122*a2+16*a3-u5+v5=91, a1+130*a2+8*a3-u6+v6=79, a1+114*a2+20*a3-u7+v7=98, a1+102*a2+15*a3-u8+v8=76, R-u1-v1=0, R-u2-v2=0, R-u3-v3=0, R-u4-v4=0, R-u5-v5=0, R-u6-v6=0, R-u7-v7=0, R-u8-v8=0; ConstrainedMinc,m,u1,v1,u2,v2,u3,v3,u4,v4,u5,v5,u6,v6,u7,v7,u8,v8,a1,a2,a3,R/N執(zhí)行后輸出3.42529, u1 - 0, v1 - 3.425

49、29, u2 - 1.07854, v2 - 2.34674, u3 - 3.42529, v3 - 0, u4 - 0.469349, v4 - 2.95594, u5 - 1.72222, v5 - 1.70307, u6 - 2.22031, v6 - 1.20498, u7 - 0, v7 - 3.42529, u8 - 3.42529, v8 - 0, a1 - 1.86207, a2 - 0.48659, a3 - 1.86207, R - 3.42529從輸出結(jié)果易見(jiàn)g=1.86207+0.48659iq+1.86207t以上三種準(zhǔn)則的計(jì)算誤差可列表如下：準(zhǔn)則準(zhǔn)則誤差平方和誤差平

50、方和誤差絕對(duì)值之和誤差絕對(duì)值之和最大誤差最大誤差最小二乘最小二乘47.6616.27 4.54最小一乘最小一乘 52.84 13.94 6.02極小極大極小極大 57.90 18.49 3.43 某居民區(qū)的民用自來(lái)水是由一個(gè)圓柱形的水塔提供，一般可以通過(guò)測(cè)量其水位來(lái)估計(jì)水的流量。但 問(wèn)題是，當(dāng) 水塔水位下降到設(shè)定的最低水位時(shí)水泵自動(dòng)啟動(dòng)向水塔供水，到設(shè)定的最高水位時(shí)停止供水，在水泵自動(dòng)加水期間無(wú)法測(cè)量水塔的水位和水泵的供水量。通常水泵每天供水兩次，每次約兩小時(shí)。水塔是一個(gè)高12.2米，直徑17.4米的正圓柱，當(dāng)水塔的水位降至最低水位，約8.2米時(shí)，水泵自動(dòng)啟動(dòng)供水當(dāng)水塔的水位升高到一個(gè)最高水位

51、，約10.8米時(shí)，水泵停止工作。表5-4是某一天的水位測(cè)量記錄數(shù)據(jù)，測(cè)量了28個(gè)時(shí)刻，但是由于其中有4個(gè)時(shí)刻遇到水泵正在向水塔供水，而無(wú)水位記錄，表5-4中用符號(hào)表示。試估計(jì)任何時(shí)刻（包括水泵正供水時(shí)）的用水率，及一天的總用水量。 模型假設(shè)假設(shè)水塔中流出的水流量只受社區(qū)的日常生活需要的影響，水的消耗每天大致差不多。由Torricelli定律知，從水塔流出的最大流速正比于水位高度的平方根，題目中給出水塔的最高和最低水位分別為10.82米和8.22米，所以對(duì)于這兩種高度，最大水流速度的比約為 1. 這表明我們可以假設(shè)水塔中水位對(duì)水流速度影響忽略不計(jì)。15. 122. 8/82.10水泵工作時(shí)單位時(shí)

52、間的供水量大致為常數(shù)，這個(gè)常數(shù)大于單位時(shí)間內(nèi)從水塔中流出的水流的最大流速，這是因?yàn)榫用駞^(qū)內(nèi)一直需要用水，不允許水塔中的水用光。水塔中水流量是時(shí)間的連續(xù)光滑函數(shù)，與水泵工作與否無(wú)關(guān)。這是因?yàn)殡m然就個(gè)別用戶而言可能用水量有較大的變化，但由于個(gè)人的用水量與整個(gè)居民區(qū)用水量相比是非常小的，從統(tǒng)計(jì)意義上來(lái)講，不太可能同時(shí)整個(gè)社區(qū)的用水量增長(zhǎng)或減少。水泵工作與否完全取決于水塔內(nèi)水位的高度，且每次加水的工作時(shí)間為2小時(shí)，根據(jù)表6-1中的數(shù)據(jù)可知，水泵第一次供水時(shí)間段為8.967,10.954，第二次供水時(shí)間段為 20.839, 23.880 符號(hào)說(shuō)明t：測(cè)量的時(shí)刻；h：水位的高度；v：水塔中水的體積；f（t

53、）：水塔中水流速度，即流量；yi（i=13）：第i時(shí)段用水量，即沒(méi)有供水時(shí)間段用水量； y12：第1和第2供水時(shí)間段用水量之和；y：一天中總用水量。 問(wèn)題要求任意時(shí)刻的用水率，即求單位時(shí)間流出的水的體積，一般稱為水流速度或流量。由于水塔是一個(gè)圓柱體，體積 可以很容易地通過(guò)水 位高度h計(jì)算出來(lái)，這樣在水泵不工作的時(shí)間段，水流速度就可以從體積對(duì)時(shí)間的導(dǎo)數(shù)計(jì)算出來(lái)，由于沒(méi)有水的體積關(guān)于時(shí)間的函數(shù)表達(dá)式，而只能利用問(wèn)題中給定的原始數(shù)據(jù)表6-1，通過(guò)公式 ，計(jì)算出離散的在測(cè)量時(shí)刻的 體積V，因此可以考慮用差商代替微商，也就是用離散代替連續(xù)的思想。hdV24hdV24 為提高計(jì)算精度，采用二階差商，即 由

54、于所有數(shù)據(jù)被水泵兩次供水分割成三組數(shù)據(jù)對(duì)每組數(shù)據(jù)的中間數(shù)據(jù)采用中心差商，前后兩個(gè)數(shù)據(jù)不能采用中心差商，改用向前差商、向后差商或用中點(diǎn)公式進(jìn)行差商。 中心差商公式：1.向前差商公式：iiVtf2)()(1288121122iiiiiiittVVVVV)(2341122iiiiiittVVVV向后差商公式：中點(diǎn)公式：以上分析了水泵不工作的時(shí)段，用水率的計(jì)算。對(duì)于水泵供水時(shí)段的用水率，計(jì)算難度較大，我們只好用供水時(shí)間段前后的用水率進(jìn)行插值或擬合而得到。有了任何時(shí)刻的用水率，可以采用數(shù)值積分計(jì)算一天的總用水量。)(2431212iiiiiittVVVV) 1() 1() 1() 1(ititiViVV

55、i通過(guò)以上對(duì)問(wèn)題的分析，現(xiàn)在的問(wèn)題已轉(zhuǎn)化為根據(jù)某一天已測(cè)量的時(shí)刻水塔中水的流速，產(chǎn)生在整個(gè)區(qū)間（24小時(shí)）上的函數(shù)或函數(shù)值，一般來(lái)說(shuō)插值和擬合是兩種最常用的方法。（1）計(jì)算水流速度并畫出散點(diǎn)圖MATLAB程序如下：% 估計(jì)水塔流量ch541% 計(jì)算流速，并畫流速散點(diǎn)圖% 文件名：ch541.mt=0,0.921,1.843,2.949,3.871,4.978,5.900,7.006,7.928,8.967,.10.954,12.032,12.954,13.875,14.982,15.903,16.826,17.931,.19.037,19.959,20.839,23.880,24.986,25

56、.908; h=9.677,9.479,9.308,9.125,8.982,8.814,8.686,8.525,8.388,. 8.220,10.820,10.500,10.210,9.936,9.653,9.409,9.180,.8.921,8.662,8.433,8.220,10.591,10.354,10.180;% 計(jì)算水塔中水的體積v=(pi*17.42/4)*h; % 對(duì)每組數(shù)據(jù)的中間數(shù)據(jù)計(jì)算中心差商 % 對(duì)每組數(shù)據(jù)不能計(jì)算中心差商的計(jì)算向前或向后差商for i=1:2f(i)=-(-v(i+2)+4*v(i+1)-3*v(i)/(2*(t(i+1)-t(i); % 計(jì)算向前差商e

57、nd for i=3:8 f(i)=-(-v(i+2)+8*v(i+1)-8*v(i-1)+v(i-2)/ (12*(t(i+1)-t(i);% 計(jì)算中心差商 end for i=9:10 f(i)=-(3*v(i)-4*v(i-1)+v(i-2)/(2*(t(i)-t(i-1); % 計(jì)算向后差商endfor i=11:12 f(i)=-(-v(i+2)+4*v(i+1)-3*v(i)/(2*(t(i+1)-t(i); % 計(jì)算向前差商endfor i=13:19 f(i)=-(-v(i+2)+8*v(i+1)-8*v(i-1)+ v(i-2)/(12*(t(i+1)-t(i); % 計(jì)算中

58、心差商end for i=20:21 f(i)=-(3*v(i)-4*v(i-1)+v(i-2)/(2*(t(i)-t(i-1); % 計(jì)算向后差商endi=22; f(i)=-(-v(i+2)+4*v(i+1)-3*v(i)/(2*(t(i+1)-t(i); % 計(jì)算向前差商i=23; f(i)=-(v(i+1)-v(i-1)/(t(i+1)-t(i-1); % 用中點(diǎn)方法計(jì)算差商 i=24; f(i)=-(3*v(i)-4*v(i-1)+v(i-2)/(2*(t(i)-t(i-1);%計(jì)算向后差商disp(水塔流速)fplot(t,f,b*)title(流速散點(diǎn)圖);xlabel(時(shí)間（小時(shí)）);ylabel(流速（立方米/小時(shí)）);文件ch541.m執(zhí)行后，可得水塔中水的流速（經(jīng)整理成表65）以及流速散點(diǎn)圖68。 （2）模