數(shù)值分析(例題)

1、2 Error and Significant Digits 例例：為使：為使 的相對(duì)誤差小于的相對(duì)誤差小于0.001%, ,至少應(yīng)取幾位有效數(shù)字？至少應(yīng)取幾位有效數(shù)字？*解解：假設(shè)：假設(shè) * 取到取到 n 位有效數(shù)字，則其相對(duì)誤差上限為位有效數(shù)字，則其相對(duì)誤差上限為111021* nra要保證其相對(duì)誤差小于要保證其相對(duì)誤差小于0.001%，只要保證其上限滿足，只要保證其上限滿足%001.01021*11 nra已知已知 a1 = 3，則從以上不等式可解得，則從以上不等式可解得 n 6 log6，即，即 n 6，應(yīng)取，應(yīng)取 * = 3.14159。3 Error Estimation for

2、Functions例：例：計(jì)算計(jì)算 y = ln x。若。若 x 20，則取，則取 x 的幾位有效數(shù)字可保的幾位有效數(shù)字可保證證 y 的相對(duì)誤差的相對(duì)誤差 0.1% ?*ln| )(*| )(*|*)(*)(*| )(|xxexexyxyxy*errr 解解：設(shè)截?。涸O(shè)截取 n 位有效數(shù)字后得位有效數(shù)字后得 x* x，則，則估計(jì)估計(jì) x 和和 y 的相對(duì)誤差上限滿足近似關(guān)系的相對(duì)誤差上限滿足近似關(guān)系)(*ln)(*yxxrr %1 . 0*ln102111 xan不知道怎么辦?。坎恢涝趺崔k??？x 可能是可能是20 ，也可能，也可能是是19，取最壞情況，取最壞情況，即即a1 = 1。 n 4例

3、例：計(jì)算：計(jì)算 ，取，取 4 位有效數(shù)字，即位有效數(shù)字，即 , 則相對(duì)誤差則相對(duì)誤差8ln 209 )8920ln(. %.1010029820ln9820ln8920ln5 1 Introduction定理定理 (唯一性唯一性) 滿足滿足 次數(shù)不超過次數(shù)不超過 n的插值多項(xiàng)式是唯一存在的。的插值多項(xiàng)式是唯一存在的。niyxPii,., 0,)( 證明：證明： (另一證法）另一證法）反證：若不唯一，則除了反證：若不唯一，則除了pn(x) 外還有另一外還有另一 n 階多項(xiàng)階多項(xiàng)式式 Ln(x) 滿足滿足 Ln(xi) = yi 。考察考察 則則 Qn 的次數(shù)的次數(shù), )()()(xLxPxQnn

4、n nn + 1x0 xn而而 Qn 有有 個(gè)不同的零點(diǎn)個(gè)不同的零點(diǎn)注：注：若不將多項(xiàng)式次數(shù)限制為若不將多項(xiàng)式次數(shù)限制為 n ，則插值多項(xiàng)式，則插值多項(xiàng)式不唯一不唯一。例如例如 也是一個(gè)插值也是一個(gè)插值多項(xiàng)式，其中多項(xiàng)式，其中 可以是任意多項(xiàng)式?？梢允侨我舛囗?xiàng)式。0( )( )( )()nniiP xPxk xxx )(xp3 Newtons Interpolation三階差商三階差商二階差商二階差商一階差商一階差商ix0 x1x2x3x( )if x0( )f x1( )f x2( )f x3( )f x01,f xx12,f x x23,f xx123,f x xx012,f xx x01

5、23,f xx xx 12301230,f x xxf xx xxx 021021,xxxxfxxf 132132,xxxxfxxf 差商計(jì)算可列差商表如下差商計(jì)算可列差商表如下2323)()(xxxfxf 0101)()(xxxfxf 1212)()(xxxfxf 3 Newtons Interpolation,)()()(000 xxfxxxfxf ,)(,101100 xxxfxxxxfxxf ,.,)(,.,.,0010nnnnxxxfxxxxfxxxf )()()()()(10102010 nnnxxxxcxxxxcxxccxN12 n 11+ (x x0) 2+ + (x x0)(

6、x xn 1) n 1.)(,)(,)()(102100100 xxxxxxxfxxxxfxfxf).(,.,100 nnxxxxxxf)().(,.,100nnnxxxxxxxxxf Nn(x)Rn(x)ci = f x0, , xi 插值余項(xiàng)插值余項(xiàng) /* Remainder */注：注： 由由唯一性可知唯一性可知 Nn(x) Ln(x)， 只是算法不同，故其只是算法不同，故其余項(xiàng)也相同，即余項(xiàng)也相同，即)(!)1()()(,.,1)1(10 xnfxxxxfnxnnn ),(,!)(,.,maxmin)(0 xxkfxxfkk HW p.50 #6,#8,#9kx)(kxf0.41075

7、 0.57815 0.69675 0.888110.40 0.55 0.65 0.80例例 已知函數(shù)已知函數(shù))(xf在各節(jié)點(diǎn)處的函數(shù)值如下在各節(jié)點(diǎn)處的函數(shù)值如下,用用Newton插值插值)596. 0(f的值的值.法求法求3 Newtons Interpolation例例 已知數(shù)值表如下，分別用向前、向后已知數(shù)值表如下，分別用向前、向后Newton插值公式插值公式求求sin0.57891的近似值。的近似值。x0.40.50.60.7sinx0.389420.479430.564640.64422解解：作差分表作差分表-0.00083-0.00480-0.005630.090010.079580

8、.389420.479430.564640.644220.40.50.60.7sinxx 2 3 3 Newtons Interpolation使用向前插公式，取使用向前插公式，取x0=0.5，x1=0.6, x2=0.7, x=x0+th, h=0.1,t=(x-x0)/h=0.7891,于是于是200563. 0)17894. 0(7891. 008521. 07891. 047943. 02)1()57891. 0(02002 fttftfN誤差誤差)7 . 05 . 0)cos)(27891. 0)(17891. 0(7891. 0! 31 . 0)(32 ( xR故故5521095.

9、 25 . 0cos1036. 3)( xR若用向后插公式，則可取若用向后插公式，則可取x0=0.6，x-1=0.5, x-2=0.4, x=x0+th, t=-0.2109,于是于是 0.54714 3 Newtons Interpolation誤差誤差)6 . 04 . 0( ),cos)(22109. 0)(12109. 0)(2109. 0(! 31 . 0)(32 xR故故521057. 4)( xR0.54707 3 Newtons Interpolation)00480. 0(2)12109. 0)(2109. 0(08521. 0)2109. 0(56464. 0! 2)1()

10、57891. 0(02020 fttftfN例例. . 已知數(shù)據(jù)表已知數(shù)據(jù)表ixiy11234452求滿足自然邊界條件求滿足自然邊界條件 的三次樣條函數(shù)的三次樣條函數(shù) 并計(jì)算并計(jì)算 的近似值。的近似值。0)5()1( SS),(xS)3(f解：解：作差商表作差商表iixiy,1 iixxf,21 iiixxxf01231245134225 . 025 . 083333. 06 Cubic Spline由自然邊界條件得，由自然邊界條件得， 故有故有 , 030 MM99998. 43222121 MMu 25000.4)3()3( Sf在上式中，令在上式中，令 , ,得得3 x750001.01

11、 M249999.02 M解此方程組得解此方程組得22499999.524500001.312)2(249999.212)4(750001.0)(33 xxxxxS可以求得可以求得其中其中 66666. 02122121hhh66666. 01223222 hhhuHW: p.50 #15, #166 Cubic Spline這里實(shí)際上要求的是這里實(shí)際上要求的是(0, 1)(0, 1)上的一次最佳平方逼近多上的一次最佳平方逼近多項(xiàng)式項(xiàng)式于是于是法方程法方程組組的系數(shù)矩陣的系數(shù)矩陣為為 121211121312111211Hnnnnn Hilbert陣！陣！記記 , , 則則TnTnaaaddd

12、),(a,),(d1010 da H的解的解 即為所求即為所求. .), 1, 0(*nkaakk 例例 定義內(nèi)積定義內(nèi)積 ，試在，試在 中尋求中尋求對(duì)于對(duì)于 的最佳平方逼近元素的最佳平方逼近元素 。 10)()(),(dxxgxfgf, 11xspanH xxf )()(xP解解 10101052),(,32)1,(dxxxxfddxxfd2 2 Least_Squares ApproximationD. Hilbert(1862-1943)德國數(shù)學(xué)家德國數(shù)學(xué)家19世紀(jì)、世紀(jì)、20世紀(jì)初最著名世紀(jì)初最著名的數(shù)學(xué)家之一的數(shù)學(xué)家之一Hilbert空間、著名的空間、著名的23個(gè)個(gè)數(shù)學(xué)問題數(shù)學(xué)問題H

13、ilbert矩陣矩陣(1894) 5232312121110aa解得解得 ，所求的最佳平方逼近元素為，所求的最佳平方逼近元素為1512,154*1*0 aa101512154)( xxxP 101010*22),(),(kkkkkkdaxdxfaff 002222. 05215123215421 平方誤差平方誤差 對(duì)于一般的基底對(duì)于一般的基底 ，當(dāng)，當(dāng) 稍大稍大時(shí)，計(jì)算法方程組中的時(shí)，計(jì)算法方程組中的 以及求解法方程以及求解法方程組的計(jì)算量都是很大的，若采用組的計(jì)算量都是很大的，若采用 作基作基底，當(dāng)?shù)?，?dāng) 時(shí)，雖然時(shí)，雖然 容易計(jì)算，容易計(jì)算，但由此形成的法方程組系數(shù)矩陣當(dāng)?shù)纱诵纬傻姆ǚ匠?/p>

14、組系數(shù)矩陣當(dāng) 時(shí)是病時(shí)是病態(tài)矩陣，用單字長在計(jì)算機(jī)上求解法方程組，態(tài)矩陣，用單字長在計(jì)算機(jī)上求解法方程組，其結(jié)果往往不太可靠，如何解決？。其結(jié)果往往不太可靠，如何解決？。n ,10n),(jk nxx, 11)( x 4 n),(),(jkjkxx ),(),(),(),(),(),(),(),(),(),(),(),(1010101110101000yyyaaannnnnnnn 注意看法方程組注意看法方程組若要法方程非對(duì)角線上元素為零，若要法方程非對(duì)角線上元素為零，), 1 , 0(nkk 應(yīng)怎么??？應(yīng)怎么取？為此，我們先介紹正交多項(xiàng)式為此，我們先介紹正交多項(xiàng)式可采用正交基底可采用正交基底. .得法方程組為得法方程組為2 2 Least_Squares Approximation3 收斂性與穩(wěn)定性收斂性與穩(wěn)定性 /* Convergency and Stability */ 收斂性收斂性 /* Convergency */定義定義 若某算法對(duì)于任意固定的若某算法對(duì)于任意固定的 x = xn= x0 + n h，當(dāng)，當(dāng) h0 ( 同時(shí)同時(shí) n ) 時(shí)有時(shí)有 yn y( xn )，則稱該算法是，則稱該算法是收斂收