華科數(shù)值分析期末復習總結

1、1期末復習總結期末復習總結2第一章數(shù)值計算的誤差3絕對誤差：絕對誤差：絕對誤差絕對誤差*exxx 精確值精確值x* 近似值近似值則稱則稱 * 為為 絕對誤差限絕對誤差限/誤差限誤差限l 若存在一個正數(shù)若存在一個正數(shù) *，使得，使得工程上通常記為：工程上通常記為：x = x* *|e*| = |x* - x| *l 絕對誤差絕對誤差 可能取正，也可能取負可能取正，也可能取負l 絕對誤差絕對誤差 越小越具有參考價值越小越具有參考價值l 但但 絕對誤差絕對誤差 卻不能很好地表示近似值的精確程度卻不能很好地表示近似值的精確程度4相對誤差相對誤差相對誤差：相對誤差： x* - x er* = x l 若

2、存在正數(shù)若存在正數(shù) r*，使得，使得 |er*| r*， 則稱則稱 r*為為相對誤差限相對誤差限l 由于真值難以求出，通常也使用下面的定義作為相對誤差由于真值難以求出，通常也使用下面的定義作為相對誤差 x* - x er* = x* l 近似值的精確程度取決于近似值的精確程度取決于 相對誤差相對誤差 的大小的大小l 實際計算中我們所能得到的是實際計算中我們所能得到的是 誤差限誤差限 或或 相對誤差限相對誤差限5有效數(shù)字有效數(shù)字有效數(shù)字：有效數(shù)字：若近似值若近似值 x* 的誤差限是某一位的半個單的誤差限是某一位的半個單位位（即截取按四舍五入規(guī)則）（即截取按四舍五入規(guī)則） ，且該位到，且該位到 x

3、* 的第一位非的第一位非零數(shù)字共有零數(shù)字共有 n 位，則稱位，則稱 x* 有有 n 位有效數(shù)字位有效數(shù)字x* = a1.a2an 10m (a1 0)且有且有|x - x*| 0.5 10m-n+1則則 x* 有有 n 位有效數(shù)字位有效數(shù)字 設設 x*為為 x 的近似值，若的近似值，若 x* 可表示為可表示為l 等價描述等價描述 6有效數(shù)字有效數(shù)字例：例： = 3.14159265 ，近似值，近似值 x1 = 3.1415，x2 = 3.1416問：問：x1, x2 分別有幾位有效數(shù)字？分別有幾位有效數(shù)字？例：例：寫出下列各數(shù)的具有寫出下列各數(shù)的具有 5 位有效數(shù)字的近似值位有效數(shù)字的近似值

4、187.9325，0.03785551 ， 2.7182828 ，8.000033187.93，0.037856 ，2.7183 ，8.0000數(shù)字末尾的數(shù)字末尾的0 0不可以隨意添加或省略！不可以隨意添加或省略！7有效數(shù)字有效數(shù)字定理：定理：設近似值設近似值 x* 可表示為可表示為 x* = a1.a2al 10m (a1 0)，若若 x* 具有具有 n 位有效數(shù)字，則其相對誤差限滿足位有效數(shù)字，則其相對誤差限滿足 1 r* 2a1 10-(n-1)反之，若反之，若 x* 的的相對誤差限相對誤差限滿足滿足 則則 x* 至少有至少有 n 位有效數(shù)字。位有效數(shù)字。 1 r* 2(a1+1) 10

5、-(n-1)有效位數(shù)越多，有效位數(shù)越多，相對誤差限越小相對誤差限越小8第二章插值法9插值基本概念插值基本概念已知函數(shù)已知函數(shù) y = f(x) 在在 a, b 上有定義，且已經(jīng)測得在點上有定義，且已經(jīng)測得在點 a x0 x1 xn b 處的函數(shù)值為處的函數(shù)值為 y0 = f(x0)， ，yn = f(xn)什么是插值如果存在一個如果存在一個簡單易算簡單易算的函數(shù)的函數(shù) P(x)，使得，使得 P(xi) = f(xi)，i = 1, 2, . , n則稱則稱 P(x) 為為 f(x) 的的插值函數(shù)插值函數(shù)插值區(qū)間插值區(qū)間插值節(jié)點插值節(jié)點求插值函數(shù)求插值函數(shù) P(x) 的方法就稱為的方法就稱為插值

6、法插值法插值節(jié)點插值節(jié)點無需遞無需遞增排列增排列，但必須，但必須確保確保互不相同互不相同！插值條件插值條件10基函數(shù)插值法基函數(shù)插值法基函數(shù)法通過基通過基函數(shù)來構造函數(shù)來構造插值多項式的方法插值多項式的方法就就稱為稱為基函數(shù)基函數(shù)插值插值法法Zn(x) = 次數(shù)不超過次數(shù)不超過 n 的多項式的全體的多項式的全體記記n+1 維線性空間維線性空間設設 z0(x), z1(x), . , zn(x) 構成構成 Zn(x) 的一組基，則插值多項式的一組基，則插值多項式P(x) = a0z0(x) + a1z1(x) + + anzn(x) 尋找合適的基函數(shù)尋找合適的基函數(shù) 確定插值多項式在這組基下的表

7、示系數(shù)確定插值多項式在這組基下的表示系數(shù)基函數(shù)法基本步驟基函數(shù)法基本步驟11Lagrange插值插值Lagrange插值基函數(shù)設設 lk(x) 是是 n 次多項式，在插值節(jié)點次多項式，在插值節(jié)點 x0 , x1 , , xn 上滿足上滿足1,()0,kjjklxjk 則稱則稱 lk(x) 為節(jié)點為節(jié)點 x0 , x1 , , xn 上的上的拉格朗日插值基函數(shù)拉格朗日插值基函數(shù)單項式單項式基函數(shù)利用線性無關的單項式族：利用線性無關的單項式族：21,nxxx構造構造 n 次多項式：次多項式：2012( )nnf xaa xa xa x 12線性與拋物線插值線性與拋物線插值兩種特殊情形 n=1011

8、0 01 1010110( )( )( )xxxxL xy lxy l xyyxxxx 線性插值多項式（一次插值多項式）線性插值多項式（一次插值多項式）n=2020112012010210122021()()()()()()()()()()()()xxxxxxxxxxxxyyyxxxxxxxxxxxx 拋物線插值多項式（二次插值多項式）拋物線插值多項式（二次插值多項式）2( )Lx13插值舉例插值舉例例：例：已知函數(shù)已知函數(shù) y = lnx 的函數(shù)值如下的函數(shù)值如下解解：x0.40.50.60.70.8lnx-0.9163-0.6931-0.5108-0.3567-0.2231試分別用試分別用

9、線性插值線性插值和和拋物線插值拋物線插值計算計算 ln 0.54 的近似值的近似值線性插值線性插值：取取 x0=0.5, x1=0.6 得得將將 x=0.54 代入可得：代入可得：011010110( )0.18231.6046xxxxL xyyxxxxx ln 0.54 L1(0.54) =-0.6202為了減小截斷誤差，通常選取插值點為了減小截斷誤差，通常選取插值點 x 鄰接的插值節(jié)點鄰接的插值節(jié)點14插值舉例插值舉例拋物線插值拋物線插值：取取 x0=0.4, x1=0.5, x2=0.6, 可得可得ln 0.54 L2(0.54) =-0.6153在實際計算中，不需要給出插值多項式的表達

10、式在實際計算中，不需要給出插值多項式的表達式ex21.m ln 0.54 的精確值為：的精確值為：-0.616186可見，拋物線插值的精度比線性插值要高可見，拋物線插值的精度比線性插值要高Lagrange插值多項式簡單方便，只要取定節(jié)點就可寫插值多項式簡單方便，只要取定節(jié)點就可寫出基函數(shù)，進而得到插值多項式，易于計算機實現(xiàn)。出基函數(shù)，進而得到插值多項式，易于計算機實現(xiàn)。15Lagrange插值插值l0(x) , l1(x) , , ln(x) 構成構成 Zn(x) 的一組的一組基基性質(zhì)性質(zhì)注意注意l0(x) , l1(x) , , ln(x) 與插值節(jié)點有關，與插值節(jié)點有關，但與函數(shù)但與函數(shù)

11、f(x) 無關無關lk(x) 的表達式的表達式0110111,()()( ) ()()()()()()kknkkkknjjj kkknjkkxxxxxlxxxxxxxxxxxxxxxx 由構造法可得由構造法可得16誤差估計誤差估計如何估計誤差 )()()(xLxfxRnn 插值余項插值余項定理定理設設 f(x) Cna, b ( n 階連續(xù)可微階連續(xù)可微 )，且，且 f (n+1)(x)在在 (a, b) 內(nèi)存在，則對內(nèi)存在，則對 x a,b，有，有(1)1()( )( )( )( )(1)!nxnnnfRxf xLxxn 其中其中 x (a, b) 且與且與 x 有關有關,101( )()(

12、)()nnxxxxxxx 證明：證明：（板書）（板書）17插值余項插值余項l 余項公式只有當余項公式只有當 f(x) 的高階導數(shù)存在時才能使用的高階導數(shù)存在時才能使用幾點說明 l 計算插值點計算插值點 x 上的近似值時，應選取與上的近似值時，應選取與 x 相近插值節(jié)點相近插值節(jié)點10( ) (1)!nnniiMRxxxn 如果如果 ，則，則(1)1( )nnfxM l x 與與 x 有關，通常無法確定有關，通常無法確定, 實際使用中通常是估計其上界實際使用中通常是估計其上界18插值誤差舉例插值誤差舉例例：例：已知函數(shù)已知函數(shù) y = lnx 的函數(shù)值如下的函數(shù)值如下x0.40.50.60.70

13、.8lnx-0.9163-0.6931-0.5108-0.3567-0.2231試估計試估計線性插值線性插值和和拋物線插值拋物線插值計算計算 ln 0.54 的誤差的誤差解解線性插值線性插值 (2)2( )4f (2)101( )( )()()2fR xxxxx 1(0.54)2(0.540.5)(0.540.6)0.0048R x0=0.5, x1=0.6, (0.5, 0.6)19Newton 插值插值為什么 Newton 插值Lagrange 插值簡單易用，但若要增加一個節(jié)點時，全部基函插值簡單易用，但若要增加一個節(jié)點時，全部基函數(shù)數(shù) lk(x) 都需重新計算，不太方便。都需重新計算，不

14、太方便。設計一個可以逐次生成插值多項式的算法，即設計一個可以逐次生成插值多項式的算法，即 n 次插值多項式次插值多項式可以通過可以通過 n-1 次插值多項式生成次插值多項式生成 Newton 插值法插值法解決辦法解決辦法20新的基函數(shù)新的基函數(shù)n 設插值節(jié)點為設插值節(jié)點為 x0 , , xn ，考慮插值基函數(shù)組，考慮插值基函數(shù)組010201011( )1( )( )()()( )()()()nnxxxxxxxxxxxxxxxx l 當增加一個節(jié)點當增加一個節(jié)點 xn+1 時，只需加上基函數(shù)時，只需加上基函數(shù) 10()nniixx 21Newton 插值插值n 此時此時 f(x) 的的 n 次插

15、值多項式為次插值多項式為10102010( )()()()()nnnkkpxaa xxaxxxxaxx 問題問題l 如何從如何從 pn-1(x) 得到得到 pn(x) ?l 怎樣確定參數(shù)怎樣確定參數(shù) a0 , , an ? 需要用到需要用到 差商差商（均差）（均差）22差商差商什么是差商設函數(shù)設函數(shù) f(x)，節(jié)點，節(jié)點 x0 , , xn ()(),jiijjif xf xf x xxx f(x) 關于點關于點 xi , xj 的的一階差商一階差商,jkijijkkif xxf x xf x xxxx f(x) 關于點關于點 xi , xj , xk 的的二階差商二階差商101010,kkk

16、kf xxf xxf xxxxx k 階差商階差商差商的一般定義差商的一般定義23差商的性質(zhì)差商的性質(zhì)l k 階差商與階差商與 k 階導數(shù)之間的關系：階導數(shù)之間的關系：若若 f (x) 在在 a,b 上上 具有具有 k 階導數(shù)，則至少存在一點階導數(shù)，則至少存在一點 (a, b)，使得使得( )01( ),!kkff xxxk 24差商的計算差商的計算如何巧妙地計算差商差商表差商表xi(xi)一階一階差商差商二階差商二階差商三階差商三階差商n 階差商階差商x0 x1x2x3 xn(x0)(x1)(x2)(x3) (xn)x0, x1x1, x2x2, x3 xn-1, xnx0, x1, x2x

17、1, x2, x3 xn-2, xn-1, xnx0, x1, x2, x3 xn-3, xn-2, xn-1, xnx0, x1, xn25差商舉例差商舉例例：例：已知已知 y = (x) 的函數(shù)值表，的函數(shù)值表，試計算其各階差商試計算其各階差商i0123xi-2-112f(xi)531721解：解：差商表如下差商表如下xi(xi)一階差商一階差商二階差商二階差商三階差商三階差商-2-112531721-2743-1-1ex24.mex23.m26Newton 插值插值公式公式Newton 插值公式由差商的定義可得由差商的定義可得000( )() () ,f xf xxx f x x 1,)

18、(,101100 xxxfxxxxfxxf 2 ,.,)(,.,.,0010nnnnxxxfxxxxfxxxf n 11+ (x x0) 2+ + (x x0)(x xn 1) n 1.)(,)(,)()(102100100 xxxxxxxfxxxxfxfxf).(,.,100 nnxxxxxxf)().(,.,100nnnxxxxxxxxxf Nn(x)Rn(x)27Newton 插值插值公式公式 f (x) = Nn(x) + Rn(x) 10102011()()()( )()nniinaa xxaxxxxaxNxx 001 , . ,().()( )nnnnf x xxxRxxxxxx

19、Nn(x) 是是 n 次多項式次多項式Nn(xi) = f (xi)，i = 0, 1, 2, , n重要性質(zhì)重要性質(zhì)Nn(x) 是是 f (x) 的的 n 次插值多項式次插值多項式nixxfaxfaii, 2 , 1 , ),(000 其中其中28Newton / LagrangeNewton 插值多項式與 Lagrange 插值多項式f (x) 在在 x0 , x1 , , xn 上上的的 n 次插值多項式是唯一的！次插值多項式是唯一的！Nn(x) Ln(x)余項也相同余項也相同(1)000()()()(1)!nnnxniiiiff x,x , .,xxxxxn (1)0()(1) !nx

20、nff x,x , . ,xn !)()(0kfx,.,xfkk 將將 x 看作節(jié)點看作節(jié)點29插值舉例插值舉例例：例：已知函數(shù)已知函數(shù) y = lnx 的函數(shù)值如下的函數(shù)值如下解解：取節(jié)點取節(jié)點 0.5, 0.6, 0.4 作差商表作差商表試分別用試分別用牛頓牛頓線性插值和拋物線插值計算線性插值和拋物線插值計算 ln 0.54 的近似值的近似值x0.40.50.60.70.8lnx-0.9163-0.6931-0.5108-0.3567-0.2231xi(xi)一階差商一階差商 二階差商二階差商0.50.60.4-0.6931-0.5108-0.91631.82302.0275-2.0450

21、N1(x) = -0.6931 + 1.8230(x-0.5)N1(0.54) = -0.6202N2(x) = -0.6931 + 1.8230(x-0.5) - 2.0450(x-0.5)(x-0.6)N2(0.54) = -0.6153ex25.m插值節(jié)點無需遞插值節(jié)點無需遞增排列，但必須增排列，但必須確保互不相同！確?；ゲ幌嗤?！30第三章函數(shù)逼近31 函數(shù)逼近函數(shù)逼近q 三個問題三個問題問題一問題一已知一個函數(shù)的數(shù)值表已知一個函數(shù)的數(shù)值表xx1x2xnyy1y2yn能否找到一個能否找到一個簡單易算簡單易算的的 p(x) ，使得使得 p(xi) = yi 。問題二問題二 函數(shù)函數(shù) f(x

22、) 的表達式非常復雜，能否找到一個的表達式非常復雜，能否找到一個簡簡單易算單易算的的 p(x) ，使得使得p(x) 是是 f(x) 的一個的一個合理的逼近合理的逼近。問題三問題三 問題一的表中的數(shù)值帶有誤差，能否找到一問題一的表中的數(shù)值帶有誤差，能否找到一個個簡單易算簡單易算的的 p(x) ，可以可以近似地表示這些數(shù)據(jù)近似地表示這些數(shù)據(jù)。插值插值數(shù)值逼近數(shù)值逼近32賦范線性空間賦范線性空間賦范線性空間賦范線性空間 Ca, b線性空間線性空間 Ca, b ，f(x) Ca, b 1-范數(shù)范數(shù)：1 ( )( ) dbaf xf xx 22 ( )( ) dbaf xfxx ( )max( ) a

23、x bf xf x 2-范數(shù)：范數(shù)： -范數(shù)：范數(shù)：33逼近標準逼近標準q 度量度量 p(x) 與與 f(x) 的近似程度的常用兩種標準的近似程度的常用兩種標準使使 盡可能地小盡可能地小。| )()(|maxxfxpfpbxa使使 盡可能地小盡可能地小。2122)()(badxxfxpfp一致逼近一致逼近平方逼近平方逼近34函數(shù)逼近函數(shù)逼近 記記 Hn 為所有次數(shù)不超過為所有次數(shù)不超過 n 的多項式組的多項式組成的集合，給定函數(shù)成的集合，給定函數(shù) f(x) Ca, b，若，若 P*(x) Hn 使得使得( )*( )min( )( )nP Hf xPxf xP x 則稱則稱 P*(x) 為為

24、f(x) 在在 Ca, b 上的上的 最佳逼近多項式最佳逼近多項式最佳逼近最佳逼近最佳一致逼近最佳一致逼近( )*( )min( )( )nP Hf xPxf xP x 35函數(shù)逼近函數(shù)逼近最小二乘擬合最小二乘擬合21()()niiif xP x 尋找尋找 P*(x) ，使得下面的離散，使得下面的離散 2-范數(shù)最小范數(shù)最小給定給定 f(x) Ca, b 的數(shù)據(jù)表的數(shù)據(jù)表xx0 x1xnyy0y1yn最佳平方逼近最佳平方逼近22( )*( )min( )( )nP Hf xPxf xP x 36正交多項式正交多項式定義定義設設 n(x) 是是首項系數(shù)不為首項系數(shù)不為 0 的的 n 次多項式次多項

25、式，若，若則稱則稱 為為 a, b 上帶權上帶權 (x) 正交正交性質(zhì)性質(zhì) 1設設 是正交多項式族，是正交多項式族，Hn 為所有次數(shù)不超過為所有次數(shù)不超過 n 的多項式組成的線性空間，則的多項式組成的線性空間，則0, (,)( )( )( )0, bjkjkakjkxxx dxAjk 構成構成 Hn 的一組基的一組基 0nn 0kk 稱稱 n(x) 為為 n 次正交多項式次正交多項式 012 ( ), ( ), ( ) , , ( ) nxxxx 37Legendre 多項式多項式201dP ( )1, P ( )(1)2! dnnnnnxxxnx l Pn (x) 的首項的首項 xn 的系數(shù)

26、為：的系數(shù)為：22 (21)(1)(2 )!2!2 ( !)nnnnnnnn Legendre 多項式多項式在在 -1, 1 上帶權上帶權 (x)=1 的正交多項式稱為的正交多項式稱為 勒讓德多項式勒讓德多項式x -1, 1，n = 1, 2, 記號：記號：P0 , P1 , P2 , . 則則 是是首項系數(shù)為首項系數(shù)為 1 的勒讓德多項式的勒讓德多項式 2!P ( )(1)(2 )!nnnnndxxndx P ( )nx l 令令38Legendre多項式多項式1)(0 xPxxP)(12/ )13()(22xxP2/ )35()(33xxxP8/ )33035()(244xxxP8/ )1

27、57063()(355xxxxPex31.m11(1)P ( )(21) P ( )P ( )nnnnxnxxnx 其中其中P0(x) = 1, P1(x) = x，39Chebyshev 多項式多項式Chebyshev 多項式多項式在在 -1, 1 上帶權上帶權 (x) 的正交多項式稱為的正交多項式稱為切比雪夫多項式切比雪夫多項式x -1, 1，n = 0, 1, 2, 21 1 ( )xx xnxTnarccoscos)(l 切比雪夫多項式的表達式切比雪夫多項式的表達式l 令令 x = cos ，則，則 Tn (x) = cos(n ) ，展開后即得，展開后即得2224442224422(

28、 )coscossincossin (1)(1)nnnnnnnnnnnTxCCxC xxC xx 40Chebyshev多項式多項式1)(0 xTxxT)(112)(22xxTxxxT34)(33188)(244xxxTxxxxT52016)(355ex32.m)()(2)(11xTxxTxTnnn41Chebyshev 零點插值多項式零點插值多項式Chebyshev 插值插值以以 Chebyshev 多項式的多項式的零點零點作為作為插值節(jié)點插值節(jié)點進行插值進行插值好處：好處：誤差最小誤差最小定理定理設設 f(x) Cn+1-1, 1，插值節(jié)點，插值節(jié)點 x0 , x1 , , xn 為為 T

29、n+1 (x) 的的 n+1 個零點，則個零點，則()( )( )min( )( )nnp Hxf xLxf xp x (1)1( )( )( )2 (1)!nnnf xL xfxn 且且21cos2(1)kkxn 42最佳平方逼近最佳平方逼近設設 f(x) Ca, b， 0(x), 1(x), , n(x) Ca, b 線性線性無關，令無關，令 01span,n 求求 S*(x) ，使得使得2222( )*( )min( )( )sf xSxf xS x S*(x) 稱為稱為 f(x) 在在 中的中的 最佳平方逼近函數(shù)最佳平方逼近函數(shù) 其中其中 222( )( ), ( )( )( )dba

30、f xS xfSxffSxS xx 43最佳平方逼近最佳平方逼近如何求如何求 S*(x) ？對任意對任意 S(x) ，可設可設 S(x) = a0 0 + a1 1 + + an n(x)則求則求 S*(x) 等價于求下面的多元函數(shù)的最小值點等價于求下面的多元函數(shù)的最小值點2010(,)( )( )( )dnbnjjajI a aaxf xaxx 0kIa k = 0, 1, , n44最佳平方逼近最佳平方逼近02( )( )( )( )d0nbjjkajkIxf xaxxxa 即即1( )( )( )d( ) ( )( )dnbbjjkkaajaxxxxx f xxx k = 0, 1, ,

31、 n 0,njkjkjaf 000100010111110(,)(,)(,)(,)(,)(,)(,)(,)(,)nnnnnnnnnadadad ,kkdf 法方程法方程G45求求 在在0, 1上的一次最佳平方逼近多項式上的一次最佳平方逼近多項式舉例舉例例：例：(教材教材68頁，例頁，例 6)2( )1f xx 解：解： 12000,1,1 d1.147dffxx 12110,1 d0.609dfx fxxx 001111/ 21/ 21/ 3adad 010.934, 0.426aa S*(x) = 0.934 + 0.426 x 22220( )( ),0.0026njjjxf xaf (

32、)0.066x 46最佳平方逼近多項式最佳平方逼近多項式f(x) Ca, b 在在 Hn 中的最佳平方逼近，記為中的最佳平方逼近，記為n 次最佳平方逼近多項式次最佳平方逼近多項式l 取取 Hn 的一組基：的一組基：1, x, x2, , xn ，則法方程為，則法方程為111211123111112nnnnn 0011nnadadad HHilbert 矩陣矩陣H 嚴重病態(tài)嚴重病態(tài)只適合求低只適合求低次最佳逼近次最佳逼近nS 47正交函數(shù)作逼近正交函數(shù)作逼近若若 0, 1, , n 正交，則法方程的解為正交，則法方程的解為 ,kkkkfa 所以所以k = 0, 1, , n 01010011,*

33、( )( )( )( ),nnnnfffSxxxx l 誤差誤差 222220,( )( ),nkkkkfxf x 2220,( ),nkkkkff x Bessel 不等式不等式48曲線擬合曲線擬合能否找到一個簡單易算的能否找到一個簡單易算的 p(x) ，使得，使得 f(x) p(x)已知已知 f(x) 在某些點的函數(shù)值：在某些點的函數(shù)值：xx0 x1xm f(x)y0y1ym但是但是 m 通常很大通常很大 yi 本身是測量值，不準確，即本身是測量值，不準確，即 yi f (xi) 這時不要求這時不要求 p(xi) = yi , 而只要而只要 p(xi) yi 總體上盡可能小總體上盡可能小

34、49l 使使 最小最小l 使使 最小最小曲線擬合曲線擬合 p(xi) yi 總體上盡可能小總體上盡可能小 l 使使 最小最小|)(|max1iimiyxpmiiiyxp1|)(|miiiyxp12|)(|q 常見做法常見做法太復雜太復雜 不可導，求不可導，求解困難解困難 最小二乘法：最小二乘法：目前最好的多項式曲線擬合算法目前最好的多項式曲線擬合算法50最小二乘最小二乘曲線擬合的最小二乘問題曲線擬合的最小二乘問題l 這個問題實質(zhì)上是最佳平方逼近問題的這個問題實質(zhì)上是最佳平方逼近問題的離散形式離散形式?？梢詫⑶筮B續(xù)函數(shù)的最佳平方逼近函數(shù)的方法直接用可以將求連續(xù)函數(shù)的最佳平方逼近函數(shù)的方法直接用于

35、求解該問題。于求解該問題。已知函數(shù)值表已知函數(shù)值表 ( xi , yi )，在函數(shù)空間在函數(shù)空間 中求中求 S*(x) ，使得，使得 22( )00()min ()mmiiiiiis xiiSxyS xy 其中其中 i 是點是點 xi 處的權。處的權。51最小二乘求解最小二乘求解對任意對任意 S(x) = span 0, 1, , n，可設可設 S(x) = a0 0 + a1 1 + + an n(x)則求則求 S*(x) 等價于求下面的多元函數(shù)的最小值點等價于求下面的多元函數(shù)的最小值點 2010(,)()mniiiiI a aaS xy 200()mnijjiiijaxy0kIa k =

36、0, 1, , n最小值點最小值點52最小二乘求解最小二乘求解njkkkjfa0),(),( ( k = 0, 1, , n )這里的內(nèi)積是這里的內(nèi)積是離散帶權內(nèi)積離散帶權內(nèi)積，即，即0(,)()()mjkijikiixx 0( ,)()()mkiikiiff xx ，000100010111110(,)(,)(,)(,)(,)(,)(,)(,)(,)nnnnnnnnnadadad ,kkdf 法方程法方程G法方程法方程53最小二乘求解最小二乘求解設法方程的解為：設法方程的解為： a0* , a1*, , an* , 則則 S*(x) = a0* 0 + a1* 1 + + an* n(x)結

37、論結論S*(x) 是是 f(x) 在在 中的中的 最小二乘解最小二乘解54舉例舉例最小二乘問題中，如何選擇最小二乘問題中，如何選擇數(shù)學模型數(shù)學模型很重要，即如何選取很重要，即如何選取函數(shù)空間函數(shù)空間 = span 0, 1, , n ，通常需要根據(jù)物理，通常需要根據(jù)物理意義，或所給數(shù)據(jù)的分布情況來選取合適的數(shù)學模型。意義，或所給數(shù)據(jù)的分布情況來選取合適的數(shù)學模型。55多項式擬合多項式擬合 Hn= span1, x, ., xn, 即即 i = xi, 則相應的法方程為則相應的法方程為miiniimiiiimiiinminiiminiiminiiminiimiiimiiiminiimiiimii

38、fxfxfaaaxxxxxxxx000100201001020000 此時此時 為為 f(x) 的的 n 次最小二乘次最小二乘擬合多項式擬合多項式0( )nkkkSxa x 多項式最小二乘曲線擬合多項式最小二乘曲線擬合56舉例舉例例：例：求下面數(shù)據(jù)表的二次最小二乘擬合多項式求下面數(shù)據(jù)表的二次最小二乘擬合多項式 得法方程得法方程4015. 44514. 57680. 83828. 15625. 1875. 15625. 1875. 15 . 2875. 15 . 25210aaaxi00.250.500.751.00f (xi )1.00001.28401.64872.11702.7183解：解

39、：設二次擬合多項式為設二次擬合多項式為22102)(xaxaaxp解得解得8437. 0,8641. 0,0052. 1210aaa所以此組數(shù)據(jù)的二次最小二乘擬合多項式為所以此組數(shù)據(jù)的二次最小二乘擬合多項式為228437. 08641. 00052. 1)(xxxp(1) 若題目中沒有給出各點的權值若題目中沒有給出各點的權值 i ，默認為默認為 i = 1 (2) 該方法不適合該方法不適合 n 較大時的情形較大時的情形 （病態(tài)問題）（病態(tài)問題）57第四章數(shù)值積分與數(shù)值微分58數(shù)值積分數(shù)值積分( )( ) dbaI ff xx l 微積分基本公式：微積分基本公式：baaFbFxxf)()(d)(

40、3) f (x) 表達式未知表達式未知，只有通過測量或?qū)嶒灥脕淼臄?shù)據(jù)表，只有通過測量或?qū)嶒灥脕淼臄?shù)據(jù)表l 但是在許多實際計算問題中但是在許多實際計算問題中(2) F(x) 難求！難求！甚至有時不能用初等函數(shù)表示。甚至有時不能用初等函數(shù)表示。 如如21( )sin , xf xxex (1) F(x) 表達式較復雜表達式較復雜時，計算較困難。如時，計算較困難。如61( )1f xx 59幾個簡單公式幾個簡單公式l 矩形公式矩形公式( )d() ( )baf xxba f a ( )d()2baabf xxba f ( )d() ( )baf xxba f b l 梯形公式梯形公式 1( )d()

41、( )( )2baf xxbaf af b l 拋物線公式拋物線公式1( )d()( )4( )62baabf xxbaf aff b ( )d() ( )baf xxba f q 基本思想：基本思想：( , )a b 60一般形式一般形式數(shù)值積分公式的一般形式數(shù)值積分公式的一般形式0( )d()nbiiaif xxA f x 求積節(jié)點求積節(jié)點求積系數(shù)求積系數(shù)機械求積方法機械求積方法l 將定積分計算轉化成被積函數(shù)的將定積分計算轉化成被積函數(shù)的函數(shù)值函數(shù)值的計算的計算l 無需求原函數(shù)無需求原函數(shù)l 易于計算機實現(xiàn)易于計算機實現(xiàn)一般地，用一般地，用 f(x) 在在 a, b 上的一些離散點上的一些

42、離散點 a x0 x1 xn b 上的函數(shù)值的加權平均作為上的函數(shù)值的加權平均作為 f ( ) 的近似值，可得的近似值，可得61代數(shù)精度代數(shù)精度定義定義：如果對于所有次數(shù)不超過：如果對于所有次數(shù)不超過 m 的多項式的多項式 f (x) ，公式，公式精確成立，但對某個次數(shù)為精確成立，但對某個次數(shù)為 m +1 的多項式不精確成立，則稱的多項式不精確成立，則稱該求積公式具有該求積公式具有 m 次代數(shù)精度次代數(shù)精度0( )d()nbiiaif xxA f x l 將將 f (x) = 1, x, x2, , xm 依次代入，公式精確成立依次代入，公式精確成立;l 但對但對 f (x) = xm+1 不

43、精確成立。即：不精確成立。即：22110 d2mmnbmmiiaibaA xxxm ( k = 0, 1, , m )代數(shù)精度的驗證方法代數(shù)精度的驗證方法110 d1kknbkkiiaibaA xxxk 62舉例舉例例：例：試確定系數(shù)試確定系數(shù) Ai ，使得下面的求積公式具有盡可能高的使得下面的求積公式具有盡可能高的代數(shù)精度，并求出此求積公式的代數(shù)精度。代數(shù)精度，并求出此求積公式的代數(shù)精度。10121( )d ( 1)(0)(1)f xxA fA fA f 解：解：將將 f (x)1, x, x2 代入求積公式，使其精確成立，可得代入求積公式，使其精確成立，可得 1101222023302()

44、 /12 () / 20 () / 32/ 3AAAbaAAbaAAba 解得解得 A0 =1/3, A1 =4/3, A2 =1/3。所以求積公式為。所以求積公式為3 )1()0(4)1( d)(11fffxxf 易驗證該公式對易驗證該公式對 f (x)x3 也精確成立，但對也精確成立，但對 f (x)x4 不精不精確成立，所以此求積公式具有確成立，所以此求積公式具有 3 次代數(shù)精度。次代數(shù)精度。63插值型求積公式插值型求積公式設求積節(jié)點為：設求積節(jié)點為：a x0 x1 0, 總存在一算子范數(shù)總存在一算子范數(shù) | | ，使得，使得 | | (A) + 94穩(wěn)定性理論分析穩(wěn)定性理論分析q 理論

45、分析：理論分析：bbxxA設設|1bAxbAx1又又|xAb| |1bbAAxx(1)(1)由于右端項的擾動而引起的解的變化由于右端項的擾動而引起的解的變化(2)(2)由于系數(shù)矩陣的擾動而引起的解的變化由于系數(shù)矩陣的擾動而引起的解的變化 bxxAA設設|1xxAAx)(1xxAAx| | |1AAAAxxxAx = b 的的條件數(shù)矩陣矩陣A 的的條件數(shù)95穩(wěn)定性理論分析穩(wěn)定性理論分析定理：定理：考慮線性方程組考慮線性方程組 Ax=b，設，設 b 是精確的，是精確的，A 有有微小微小的變化的變化 A，此時的解為，此時的解為 x + x ，則，則111AxAAAAxAAA 證明：證明：l 當當 A

46、 充分小時，不等式右端約為充分小時，不等式右端約為1AAAA bxxAA設設11| | | | | | ()xAAxxAAxx)(1xxAAx結論結論96矩陣條件數(shù)矩陣條件數(shù)n 條件數(shù)與范數(shù)有關，常用的有條件數(shù)與范數(shù)有關，常用的有無窮范數(shù)無窮范數(shù)和和2-范數(shù)范數(shù)l Cond(A)2 稱為稱為譜條件數(shù)譜條件數(shù)，當，當 A 對稱時有對稱時有1Cond( )AAA 1222Cond( )AAA 112221maxCond( )minii nii nAAA 1( ) | | Cond AAA97舉例舉例例：例： 計算計算 Cond(A) 和和 Cond(A)21111.0001A 解：解：Cond(A

47、) =|A-1| |A| 4 104110001100001000010000A 22.00012.00010.0004( )02A Cond(A)2= max / min 4 104A 對稱，且對稱，且98第六章線性方程組的迭代解法99矩陣分裂迭代法矩陣分裂迭代法矩陣分裂迭代法基本思想矩陣分裂迭代法基本思想Ax = b(1)( )kkxBxf k = 0, 1, 2, 給定一個初始向量給定一個初始向量 x(0)，可得，可得 迭代格式迭代格式其中其中 B = M-1N 稱為稱為迭代矩陣迭代矩陣 11xM NxM bA = M - NMx = Nx + bM 非奇異非奇異A 的一個的一個矩陣分裂

48、矩陣分裂100收斂性分析收斂性分析(1)( )kkxBxf 定理定理：對任意初始向量對任意初始向量 x(0)，上述迭代格式收斂的充要條件是，上述迭代格式收斂的充要條件是( )1B 證明：板書證明：板書定理定理：若存在算子范數(shù)若存在算子范數(shù) | |，使得，使得 |B| 1，對任意的初始向量，對任意的初始向量 x(0)，上述迭代格式收斂。，上述迭代格式收斂。例例：考慮迭代法考慮迭代法 x(k+1) = Bx(k) + f 的收斂性，其中的收斂性，其中0.900.30.8B 基本收基本收斂定理斂定理充分條件充分條件101Jacobi 迭代迭代考慮線性方程組考慮線性方程組Ax = b其中其中 A=(a

49、ij)n n 非奇異，且對角線元素全不為非奇異，且對角線元素全不為 0。1122diag(,)nnDaaa 211,10 0,0nn naLaa l 將將 A 分裂成分裂成 A = D - L- U， 其中其中1211,000nnnaaUa 102Jacobi 迭代迭代(1)1( )1()kkxDLU xD b k = 0, 1, 2, 令令 M = D，N = L + U，可得，可得 雅可比雅可比 (Jacobi) 迭代方法迭代方法 Jacobi 迭代迭代l 迭代矩陣記為：迭代矩陣記為：1()JDLU l 分量形式：分量形式：1(1)11inkiiijjijjiijj ixba xa xa

50、i = 1, 2, , n， k = 0, 1, 2, 103Gauss-Seidel 迭代迭代l 在計算在計算 時，如果用時，如果用 代替代替 ，則可能會得到更好的收斂效果。則可能會得到更好的收斂效果。(1)kix (1)(1)11,kkixx( )( )11,kkixx (1)( )( )( )11122133111(1)( )( )( )22211233222(1)( )( )( )1122,11 kkkknnkkkknnkkkknnnnn nnnnxba xa xa xaxba xa xa xaxba xa xaxa (1)( )( )( )11122133111(1)(1)( )(

51、)22211233222(1)(1)(1)(1)1122,11 kkkknnkkkknnkkkknnnnn nnnnxba xa xa xaxba xa xa xaxba xa xaxa 104Gauss-Seidel 迭代迭代 (1)1(1)( )kkkxDbLxUx 寫成矩陣形式寫成矩陣形式:此迭代方法稱為此迭代方法稱為 高斯高斯-塞德爾塞德爾 (Gauss-Seidel) 迭代法迭代法k = 0, 1, 2, 11(1)( )kkxDLUxDLb 可得可得1GDLUl 迭代矩陣記為：迭代矩陣記為： 11(1)( )111( )( )( )kkkkkxDLDLA xDLbIDLA xDLb

52、xDLbAx105SOR 迭代迭代l 為了得到更好的收斂效果，可在修正項前乘以一個為了得到更好的收斂效果，可在修正項前乘以一個 松弛因子松弛因子 ，于是可得迭代格式，于是可得迭代格式在在 G-S 迭代中迭代中 (1)(1)(1)( )( )11,11,11,kkkkkiiii iii iii nniixba xaxaxa xa 1(1)( )1( )inkkiijjijjiijj ikiba xa xax (1)1(1)()1()inkkiijjijjiijkiij ikba xaaxxx 1(1)(1)(11)(1)inkkiijjijjiijjkikiiba xaxa xx 106SOR

53、迭代迭代 (1)( )1(1)( )( )kkkkkxxDbLxUxDx 11(1)( )(1)kkxDLDU xDLb 寫成矩陣形式寫成矩陣形式:可得可得 SOR (Successive Over-Relaxation) 迭代方法迭代方法 1(1)LDLDU l 迭代矩陣記為：迭代矩陣記為：l SOR 的優(yōu)點的優(yōu)點：通過選取合適的：通過選取合適的 ，可獲得更快的收斂速度，可獲得更快的收斂速度l SOR 的缺點的缺點：最優(yōu)參數(shù)最優(yōu)參數(shù) 的的選取比較困難選取比較困難107l Jacobi 迭代收斂的迭代收斂的充要充要條件條件 (J)1l G-S 迭代收斂的迭代收斂的充要充要條件條件 (G)1l

54、SOR 迭代收斂的迭代收斂的充要充要條件條件 (L )1收斂性收斂性收斂性定理收斂性定理l Jacobi 迭代收斂的迭代收斂的充分充分條件條件 |J| 1l G-S 迭代收斂的迭代收斂的充分充分條件條件 |G| 1l SOR 迭代收斂的迭代收斂的充分充分條件條件 |L | 1108Jacobi、G-S 收斂性收斂性定理定理：若若 A 嚴格對角占優(yōu)嚴格對角占優(yōu)或或不可約弱對角占優(yōu)不可約弱對角占優(yōu)，則，則 A 非奇異非奇異定理定理：若若 A 嚴格對角占優(yōu)嚴格對角占優(yōu)或或不可約弱對角占優(yōu)不可約弱對角占優(yōu)，則，則 Jacobi 迭迭代和代和 G-S 迭代均收斂迭代均收斂 定理定理：若若 A 對稱，且對

55、角線元素均大于對稱，且對角線元素均大于 0，則，則Jacobi 迭代收斂的充要條件是迭代收斂的充要條件是 A 與與 2D-A 均正定；均正定；(1) G-S 迭代收斂的充要條件是迭代收斂的充要條件是 A 正定。正定。109SOR 收斂性收斂性定理定理：若若 SOR 迭代收斂，則迭代收斂，則 0 2。l SOR 收斂的必要條件收斂的必要條件定理定理：若若 A 對稱正定，且對稱正定，且 0 2，則則 SOR 迭代收斂。迭代收斂。l SOR 收斂的充分條件收斂的充分條件定理定理：若若 A 嚴格對角占優(yōu)或不可弱約對角占優(yōu)，且嚴格對角占優(yōu)或不可弱約對角占優(yōu)，且 0 1，則則 SOR 迭代收斂。迭代收斂。

56、110舉例舉例例例：設設 ，給出，給出 Jacobi 和和 G-S 收斂的充要條件收斂的充要條件 111aaAaaaa 解：解：A 對稱，且對角線元素均大于對稱，且對角線元素均大于 0，故，故 (1) Jacobi 收斂的充要條件是收斂的充要條件是 A 和和 2D-A 均正定均正定(2) G-S 收斂的充要條件是收斂的充要條件是 A 正定正定A 正定正定2212310,10,(1) (12 )0DDaDaa 0.51a 2D-A 正定正定2212310,10,(1) (12 )0DDaDaa 0.50.5aJacobi 收斂的充要條件是：收斂的充要條件是：-0.5a0.5G-S 收斂的充要條件

57、是：收斂的充要條件是：-0.5a1111舉例舉例解法二：解法二：Jacobi 的迭代矩陣為的迭代矩陣為設設 是是 J 的特征值，則由的特征值，則由 det( I - J) = 0 可得可得000aaJaaaa ( - a)2 ( +2a) = 0Jacobi 收斂的充要條件是收斂的充要條件是 (J)1 | |1，即即 -0.5a0.5112收斂速度收斂速度定義定義：迭代格式迭代格式 x(k+1) = Bx(k) + f 的平均收斂速度為的平均收斂速度為1( )lnkkkR BB 漸進收斂速度為漸進收斂速度為( )ln( )R BB l (B) 越小，收斂越快越小，收斂越快113第七章非線性方程

58、(組)的數(shù)值解法114不動點迭代不動點迭代q 基本思想基本思想l 構造構造 f (x) = 0 的一個等價方程：的一個等價方程： ( )xx (x) 的不動點的不動點f (x) = 0 x = (x)等價變換等價變換f (x) 的零點的零點115不動點迭代不動點迭代q 具體過程具體過程l 任取一個迭代初始值任取一個迭代初始值 x0 ，計算，計算得到一個迭代序列：得到一個迭代序列： x0，x1，x2，. . . ，xn，. . . 1()kkxx k = 0, 1, 2, . . 幾何含義：幾何含義：求曲線求曲線 y = (x) 與直線與直線 y = x 的交點的交點116連續(xù)性分析連續(xù)性分析設

59、設 (x) 連續(xù)，若連續(xù)，若 收斂，即收斂，即 ，則，則 1limlim ()limkkkkkkxxx lim*kkxx 0kkx *( *)xx ( *)0f x 即即q 收斂性分析收斂性分析性質(zhì)：性質(zhì)：若若 ，則不動點迭代，則不動點迭代收斂收斂，且，且 x* 是是 f(x)=0 的解；否則迭代法的解；否則迭代法發(fā)散發(fā)散。lim*kkxx 117解的存在唯一性解的存在唯一性定理定理：設設 (x) Ca,b 且滿足且滿足證明：板書證明：板書對任意的對任意的 x a,b 有有 (x) a,b存在常數(shù)存在常數(shù) 0L1，使得任意的，使得任意的 x, y a,b 有有( )( )xyL xy 則則 (

60、x) 在在 a,b 上存在上存在唯一的不動點唯一的不動點 x*解的存在唯一性解的存在唯一性118收斂性分析收斂性分析定理定理：設設 (x) Ca,b 且滿足且滿足證明：板書證明：板書對任意的對任意的 x a,b 有有 (x) a,b存在常數(shù)存在常數(shù) 0L1，使得任意的，使得任意的 x, y a,b 有有( )( )xyL xy 則對任意初始值則對任意初始值 x0 a,b，不動點迭代，不動點迭代 xk+1= (xk) 收斂，且收斂，且不動點迭代的收斂性不動點迭代的收斂性11011kkkkLLxxxxxxLL 119收斂性分析收斂性分析不動點迭代的收斂性不動點迭代的收斂性若若 (x) C1a,b