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

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

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

3、為式（6-4）表明，除 點以外，其他所有的節(jié)點都是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)造多項式 就是滿足插值條件 的拉格郎日插值問題的解，稱式（6-6）為拉格朗日插值多項式。

4、特別地，當(dāng)n=1時稱為線性插值，其插值多項式為： 滿足 從幾何上看, 為過兩點 的直線。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時，稱為拋物線插值，其插值多項式為： 滿足 從幾何上看 為過點 和 的一條拋物線。0201122012010210122021()()()()()()( )()()()()()()xxxxxxxxxxxxP xyyyxxxxxxxxxx

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

6、1( )( )nHxH x21210121( )nnnHxaaax0121,na aa 仿照拉格朗日插值多項式的基函數(shù)方法，可先求插值基函數(shù) ，及 共用2n+2個，每一個基函數(shù)都是2n-1次多項式，且滿足條件 于是滿足條件（6-7）的插值多項式 可寫成 由條件（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）式可得 整理得: 解出 對 兩邊取對數(shù)求導(dǎo)可得 于是 ( )jlx2( )() ( )jjxaxb lx( )jlx2()() ()1jjjjjxaxb lx1()()()2() ()0jjjjjjjjjxlxalxaxb lx12 ()0jjjaxbalx2 (),12 ()jjjjjalxbx lx ( )jlx01 ()njjkjkkjlxxx201( )(1 2() ( )njjjkjkkjxxxlxxx 同理 仿照拉格朗日插值余項的證明方法，若 在 內(nèi)的2n+2階導(dǎo)數(shù)存在，則其插值余項為 其中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階光滑性。易見，分段線性插值不光滑，這影響了它在某些工程技術(shù)實際問題中的應(yīng)用。例如：在船體、飛機(jī)等外形曲線的設(shè)計中，不僅要求曲線連續(xù)而且還要求曲線的曲率連續(xù)，這就要求插值函數(shù)具有連續(xù)的二階導(dǎo)數(shù)。為解決這一類問題，就產(chǎn)生了三次樣條插值。 所謂樣條（Spline），本來是指一種繪圖工具，它是一種富有彈性的細(xì)長木條

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

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）個條件。由條件，知S（xi）=yi（i=0,1,2,n），共有n+1個條件。因此，要確定一個三次樣條，還需要外加4n - 3（n - 1）-（n+1）=2個條件，最常用的三次樣條函數(shù)S（x）的邊界條件有兩類： 第一類邊界條件： 第二類邊界條件： 特別地， ,稱為自然邊界條件 第三類邊界條件： 稱為周期邊界條件。三次樣條插值不僅光滑性好，而且穩(wěn)定性和收斂性都有保證，具有良好的逼近性質(zhì)。 樣條插值函數(shù)的建立nnmxSmxS)( ,)(

11、00nnMxSMxS)( ,)( 000)( , 0)( 0nxSxS),( )( ),()(00nnxSxSxSxS)()(0nxSxS 構(gòu)造滿足條件的三次樣條插值函數(shù) 的表達(dá)式可以有多種方法。下面我們利用 的二階導(dǎo)數(shù)值 表達(dá) ，由于 在區(qū)間 上是三次多項式，故 在 上是線性函數(shù)，可表示為 其中 對 積分兩次并利用 及 ，可定出積分常數(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) 上式中 是未知的，為確定 對 求導(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 其中 對第一類邊界條件 ，可導(dǎo)出兩個方程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）可寫出矩陣 通過求解上述三對角矩陣可求得 對于第二類邊界條件，直接得端點方程00010061,( , ),1ndf x

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

15、過實驗等方法觀測到反映某個函數(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ù)據(jù)不可避免地帶有誤差，甚至是較大的誤差，所以使用插值法是不合適的，它會保留數(shù)據(jù)的誤差。因此，不必要求近似函數(shù)y=P（x）滿足 P（xi）=yi（i=1,n），而只要求偏差按某種標(biāo)準(zhǔn)最小，以反映所給數(shù)據(jù)的總體趨勢，消除局部波動的影響，這就是曲線擬合問題。這樣的函數(shù)P（x）稱為擬合函數(shù)。 擬合的準(zhǔn)則： 衡量一個函數(shù)P（x）同所給數(shù)據(jù)（xi，yi）（i=1,n）的偏差 的大小，常用的準(zhǔn)則有如下三

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

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

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

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

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

21、。在科學(xué)與工程計算中有大量方程求根問題，其中一類特殊的問題是多項式方程 其中系數(shù) 為實數(shù)。 方程 的根 ，又稱為函數(shù) 的零點， 它使 ，若 可分解為 其中 為正整數(shù)，且 。當(dāng) 時，則稱 單根，若 稱 為 重根，或 為 的 重零點。若 是 的 重零點，且 充分光滑，則*(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ù)多項式（6-25）時，根據(jù)代數(shù)基本定理可知，n次方程在復(fù)數(shù)域中有且只有n個根（含復(fù)根，m重根為m個根），n=1，2時方程的根是大家熟悉的，n=3，4時雖有求根公式但比較復(fù)雜，可在數(shù)學(xué)手冊中查到，但已不適合于數(shù)值計算，而 時就不能用公式表示方程的根。因此，通常對 的多項式方程求根與一般連續(xù)函數(shù)方程（6-20）一樣都可采用迭代法求根。迭代發(fā)要求先給出根 的一個近似， 若 且 ，根據(jù)連續(xù)函數(shù)性質(zhì)可知 在 內(nèi)至少有一個實根，這時稱 為方程（6-20）的有根區(qū)間。通?？赏ㄟ^逐次搜索法求得方程的有根區(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不動點迭代法 將方程（6-24）改寫成等價的形式 若要求 滿足 ，則 ；反之亦然，稱 為函數(shù) 的一個不動點。求 的零點就等價于求 的不動點，選擇一個初始近似值 ，將它代入（6-26）右端，即可求得 可以如此反復(fù)迭代計算 稱為迭代函數(shù)。

24、如果對任何 ，由（6-27）得到的序列 有極限 則稱迭代方程（6-27）收斂，且 為 的不動點，故稱（6-27）為不動點迭代法。( )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é)為一組顯式的計算公式（6-27），就是說，迭代過程實質(zhì)上是一個逐步顯式化的過程。 方程 的求根問題在xy平面上就是在確定曲線 與直線y=x交點 ，對于 的某個近似值 ，在曲線 上可確定一點 ,它以 為橫坐標(biāo)

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

26、 ，使對任意 都有 則 在 上存在唯一的不動點 。 在 的不動點存在唯一的情況下，可得到迭代法（6-27）收斂的一個充分條件。 定理2 設(shè) 滿足定理1中的兩個條件，則對任意 ，由（6-27）得到的迭代序列 收斂到 的不動點 ，并有誤差估計( )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 迭代過程是個極限過程。在用迭代法進(jìn)行實際計算時，必須按精度要求控制迭代次數(shù)。誤差估計式（6-29）原則上可用于確定迭代次數(shù)，但它由于含有信息L而不

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

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

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

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

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

32、)f x*x2( ) ( )( )( )f x fxxfx( )( )( )f xxxfx 2.簡化牛頓法與牛頓下山法 牛頓法的優(yōu)點是收斂快，缺點是每步迭代要計算 及 ，計算量較大且有時 計算較困難，二是初始近似 只在根 附近才能保證收斂，如 給的不合適可能不收斂。為克服這兩個缺點，通?？捎孟率龇椒?。 (1)簡化牛頓法，也稱平行弦法，其迭代公式為 迭代函數(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、）中取 ，則稱為簡化牛頓法， 這類方法計算量省，但只有線性收斂，其幾何意義是用平行弦與x軸交點作為 的近似。（2）牛頓下山法。牛頓法收斂性依賴初值 的選取。如果 偏離所求根 較遠(yuǎn)，則牛頓法可能發(fā)散。 例如，用牛頓法求解方程 此方程在 附近的一個根 。設(shè)取迭代初值 ，用牛頓法公式(637)312131kkkkkxxxxx01.5x *x(636)310 xx 1.5x *x0 x0 x*x01()Cfx 計算得 迭代三次得到的結(jié)果 有六位有效數(shù)字。 但是，如果改用 作為迭代初值，則依牛頓法公式（6-37）迭代一次得 這個結(jié)果反而比 更偏離了所求的根 為了防止迭代發(fā)散，我們對迭代過程再附加一項要求

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

35、進(jìn)行試算，直到能使下降條件（6-38）成立為止。若用此法解方程（6-36），當(dāng) 時由（6-37）求得 ，它不滿足條 件（6-38），通過 逐次取半進(jìn)行試算，當(dāng) 時可求得 。此時有 而 ，顯然 。由 計算 時 ，均能使條件（6-33）成立。計算結(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）的根，每步除計算 外還要算 ，當(dāng)函數(shù) 比較復(fù)雜時，計算 往往較困難，為此可以利用已求函數(shù)值 來回避導(dǎo)數(shù)值 的計算的計算，這類方法是建立插值原理基礎(chǔ)上的，下面介紹兩種常用方法。 1弦截法 設(shè) 是 的近似根，我們利用 構(gòu)造一次插值多項式 ，并用 的根作為 的新的近似根 。由于 (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）雙點弦截法可以看作牛頓公式 中的導(dǎo)數(shù) 用差商 取代的結(jié)果。 現(xiàn)在解釋這種迭代過程的幾何意義。如圖6-4，曲線 上橫坐標(biāo)為 的點分別記為 ，則弦線 的斜率等于差商值 11()()kkkkf xf xxx1kkP P1,kkP P1,kkxx( )yf x11()()kkkkf xf xxx()kfx1()()kkkkf xxxfx(642)111()()()()kkkkkkkf xxxxxf xf x 其方程是 因此，按（6-42）式求得的 實際上是弦線 與x軸交點的橫坐標(biāo)。這種算法因此而稱為弦截法。 弦截法與切線

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

39、項式121,()()kkkkkf xxxxxxx21( )(),()kkkkp xf xf x xxx*x1kx2( )ypx1kx2( )px2( )px12,kkkxxx( )0f x 有兩個零點 式中 為了從（6-43）中定出一個值 ，我們需要討論根式前正負(fù)號的取舍問題。 在 三個近似根中，自然假定 更接近所求的根 ，這時，為了保證精度，我們選 式（6-43）中較接近 的值作為新的近似根 。為此，只要取根式前的符號與 的符號相同。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 增長高度增長高度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 增長高度增長高度hi（cm） 26.25 28.88 30.60 32.25 33 35 u孩子成長問題u一個男孩在11歲長到21歲過程中，身高的變化 如表5-1所示，試找一個最佳的函數(shù)曲線來表示這個男孩的成長過程。 智商（Iq） 105 110 120 116 122 130 114 102復(fù)習(xí)時間（t） 10

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

42、xyxyxdatamnn 孩子成長問題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可見，取正弦級數(shù)為擬合曲線較為合適，為此令用Mathematica計算中的參數(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é)生考試成績問題的計算：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ī)劃問題為)()(),()(, 1)(321itxiiqxxiii761510298201147981309116122851311668612079121107510105.8832177321663215532144321333212232111321VUaaaVUaaaVUaaaVUaaaVUaaaVUaaaVUaaaVUaaats81)(miniiiVU 在Mathematica中輸入：學(xué)生成績問題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é)果易見g=5.59091+0.431818iq+2.15909t v極小極大準(zhǔn)則取v 則線性規(guī)劃問題為：)81(07615102982011479813091161

47、22851311668612079121107510105.8832177321663215532144321333212232111321iVURVUaaaVUaaaVUaaaVUaaaVUaaaVUaaaVUaaaVUaaatsii)()(),()(, 1)(321itxiiqxxiiiRmin 在Mathematica中輸入：學(xué)生成績問題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é)果易見g=1.86207+0.48659iq+1.86207t以上三種準(zhǔn)則的計算誤差可列表如下：準(zhǔn)則準(zhǔn)則誤差平方和誤差平

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

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

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

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

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

55、i通過以上對問題的分析，現(xiàn)在的問題已轉(zhuǎn)化為根據(jù)某一天已測量的時刻水塔中水的流速，產(chǎn)生在整個區(qū)間（24小時）上的函數(shù)或函數(shù)值，一般來說插值和擬合是兩種最常用的方法。（1）計算水流速度并畫出散點圖MATLAB程序如下：% 估計水塔流量ch541% 計算流速，并畫流速散點圖% 文件名：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;% 計算水塔中水的體積v=(pi*17.42/4)*h; % 對每組數(shù)據(jù)的中間數(shù)據(jù)計算中心差商 % 對每組數(shù)據(jù)不能計算中心差商的計算向前或向后差商for i=1:2f(i)=-(-v(i+2)+4*v(i+1)-3*v(i)/(2*(t(i+1)-t(i); % 計算向前差商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);% 計算中心差商 end for i=9:10 f(i)=-(3*v(i)-4*v(i-1)+v(i-2)/(2*(t(i)-t(i-1); % 計算向后差商endfor i=11:12 f(i)=-(-v(i+2)+4*v(i+1)-3*v(i)/(2*(t(i+1)-t(i); % 計算向前差商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); % 計算中

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