數(shù)值計算方法總結(jié)ppt課件

1、數(shù)值計算方法總結(jié)數(shù)值計算方法總結(jié) 數(shù)值計算方法的普通概念數(shù)值計算方法的普通概念 解線性代數(shù)方程組的直接法解線性代數(shù)方程組的直接法 插值法與最小二乘法插值法與最小二乘法 數(shù)值微積分?jǐn)?shù)值微積分 方程與方程組的迭代解法方程與方程組的迭代解法第第1章章 數(shù)值計算方法的普通概念數(shù)值計算方法的普通概念n定義定義 算法是指由根本算術(shù)運算及運算順序的規(guī)定構(gòu)成算法是指由根本算術(shù)運算及運算順序的規(guī)定構(gòu)成的完好的解題步驟的完好的解題步驟. .1.1 1.1 算法算法n描畫描畫 算法可以運用框圖、算法言語、數(shù)學(xué)言語、自然算法可以運用框圖、算法言語、數(shù)學(xué)言語、自然言語來進(jìn)展描畫。言語來進(jìn)展描畫。n具有的特征具有的特征

2、正確性、有窮性、適用范圍廣、運算任務(wù)量少、正確性、有窮性、適用范圍廣、運算任務(wù)量少、n 運用資源少、邏輯構(gòu)造簡單、便于實現(xiàn)運用資源少、邏輯構(gòu)造簡單、便于實現(xiàn)n 計算結(jié)果可靠計算結(jié)果可靠第第1章章 數(shù)值計算方法的普通概念數(shù)值計算方法的普通概念l 穩(wěn)定性穩(wěn)定性 計算過程中的誤差能得到控制，各步誤差對計算計算過程中的誤差能得到控制，各步誤差對計算結(jié)果不致產(chǎn)生過大的影響結(jié)果不致產(chǎn)生過大的影響1.1 1.1 算法算法 計算機的計算結(jié)果通常是近似的，因此算法必有誤差，并且計算機的計算結(jié)果通常是近似的，因此算法必有誤差，并且應(yīng)能估計誤差。應(yīng)能估計誤差。l 收斂性收斂性 經(jīng)過添加計算量，能使近似計算解充分接近

3、實際經(jīng)過添加計算量，能使近似計算解充分接近實際解解第第1章章 數(shù)值計算方法的普通概念數(shù)值計算方法的普通概念1.2 1.2 誤差誤差n定義定義 誤差是指近似值與真正值之差誤差是指近似值與真正值之差 誤差分類誤差分類模型誤差模型誤差在建立數(shù)學(xué)模型時，忽略次要因素而造成的在建立數(shù)學(xué)模型時，忽略次要因素而造成的數(shù)據(jù)誤差數(shù)據(jù)誤差由于問題中的值通過觀察得到的，從而產(chǎn)生誤差由于問題中的值通過觀察得到的，從而產(chǎn)生誤差截斷誤差截斷誤差通過近似替代，簡化為較易求解的問題通過近似替代，簡化為較易求解的問題計算誤差計算誤差由于計算機中數(shù)的位數(shù)限制而造成的由于計算機中數(shù)的位數(shù)限制而造成的第第1章章 數(shù)值計算方法的普通概

4、念數(shù)值計算方法的普通概念1.2 1.2 誤差誤差n絕對誤差絕對誤差 絕對誤差：是指近似值與真正值之差或差的絕對值，絕對誤差：是指近似值與真正值之差或差的絕對值，即即x設(shè)設(shè)x為真值為真值, ,為真值的近似值為真值的近似值xx xx ,或 絕對誤差界：用一個滿足絕對誤差界：用一個滿足 的數(shù)的數(shù) , ,來表示來表示絕對誤差的大小，并記為絕對誤差的大小，并記為 第第1章章 數(shù)值計算方法的普通概念數(shù)值計算方法的普通概念1.2 1.2 誤差誤差n相對誤差相對誤差 相對誤差：是指近似值與真正值之比或比的絕對相對誤差：是指近似值與真正值之比或比的絕對值，即值，即 相對誤差界：用一個滿足相對誤差界：用一個滿足

5、的數(shù)的數(shù) , ,來表示來表示相對誤差的大小，并記為相對誤差的大小，并記為 相對誤差界常用百分?jǐn)?shù)表示相對誤差界常用百分?jǐn)?shù)表示第第1章章 數(shù)值計算方法的普通概念數(shù)值計算方法的普通概念1.2 1.2 誤差誤差n準(zhǔn)確數(shù)字準(zhǔn)確數(shù)字 各位數(shù)字皆準(zhǔn)確的近似數(shù)稱為有效數(shù).此時各準(zhǔn)確數(shù)字也稱為有效數(shù)字第第1章章 數(shù)值計算方法的普通概念數(shù)值計算方法的普通概念1.2.3 1.2.3 數(shù)據(jù)誤差影響的估計數(shù)據(jù)誤差影響的估計第第1章章 數(shù)值計算方法的普通概念數(shù)值計算方法的普通概念1.2.3 1.2.3 數(shù)據(jù)誤差影響的估計數(shù)據(jù)誤差影響的估計12n12n (xxx (xxxy iiiiiiiiixxxxxxxxxni=1ni

6、=1在誤差估計式(1-1),(1-2)中,.,) y ,.,) 或表示解的誤差相對參量 的誤差的放大或縮小倍數(shù) 這些系數(shù)的絕對值稱為求y問題的條件數(shù)，其值很大時的問題稱為壞條件問題或病態(tài)問題 凡是計算結(jié)果接近于零的問題往往是病態(tài)問題。 應(yīng)防止相近數(shù)相減應(yīng)防止相近數(shù)相減, ,小除數(shù)和大乘數(shù)小除數(shù)和大乘數(shù)第第1章章 數(shù)值計算方法的普通概念數(shù)值計算方法的普通概念1.2.3 1.2.3 數(shù)據(jù)誤差影響的估計數(shù)據(jù)誤差影響的估計212212122212122222(1 1)xxxxxxxxxxxxxxxxx112112112112112112由誤差估計式可知(xxx(xxx(xxx(xxxxx(xx(xx

7、1)21)2xxx(x(x第第2章章 解線性代數(shù)方程的直接法解線性代數(shù)方程的直接法求解求解n n階線性代數(shù)方程組階線性代數(shù)方程組11 11221121 1222221 122 (2-1)nnnnnnnnnna xa xa xba xa xa xba xa xa xb寫成矩陣方式為寫成矩陣方式為 (0)AxbA111212122212 nnnnnnaaaaaaAaaa其中12 nxxxx12 nbbbb直接法指的是不計舍入誤差時直接法指的是不計舍入誤差時, ,經(jīng)過有限次算術(shù)運算能求得準(zhǔn)確解的方法經(jīng)過有限次算術(shù)運算能求得準(zhǔn)確解的方法 第第2章章 解線性代數(shù)方程的直接法解線性代數(shù)方程的直接法2.1

8、2.1 高斯消去法高斯消去法2.1.1 2.1.1 根本步驟根本步驟高斯消去法步驟高斯消去法步驟1.1.消去消去 經(jīng)過經(jīng)過n-1n-1步將方程組化為同解的上三角形方程組步將方程組化為同解的上三角形方程組11221,1 nnaaa第一步消去下方元素,第二步消去下方元素,.,第n-1步消去下方元素2.2.回代回代 按相反順序求解上三角形方程組按相反順序求解上三角形方程組, ,得到方程組的解得到方程組的解11 nnxxx第一步得到 ,第二步得到,.,第n步得到將方程組寫成增廣矩陣的方式將方程組寫成增廣矩陣的方式, ,將有利于計算機實現(xiàn)將有利于計算機實現(xiàn) AA b第第2章章 解線性代數(shù)方程的直接法解線

9、性代數(shù)方程的直接法2.1 2.1 高斯消去法高斯消去法2.1.2 2.1.2 運算量估計運算量估計高斯消去法運算量估計高斯消去法運算量估計1.1.消去算法運算量消去算法運算量3211 -1,-:,1-,5()(11)326nknkn knkknnnNnk nk 分為步 第 步變換行 求倍數(shù) 再從個元素中減去第 行對應(yīng)列的倍數(shù) 因此所需乘除次數(shù): 2.2.回代運算量回代運算量-112 1,11,.,-11,(1)12.2nnxxxnn nNn 求 需做 次除法 求需做 次乘法和 次除法求 需次乘法和 次除法 因此所需乘除次數(shù): 3212 33nnNNNn因此,3 ()o n即,運算量為第第2章章

10、 解線性代數(shù)方程的直接法解線性代數(shù)方程的直接法2.1 2.1 高斯消去法高斯消去法2.1.3 2.1.3 選主元技術(shù)選主元技術(shù)1,.,kkkknkpkkkaaaapk 為避免出現(xiàn)小主元 在第 步的第 列的元素中選出絕對值最大的元素然后交換第 行和第 行 繼續(xù)進(jìn)行消去過程 這種消去法稱為列主元消去法 選主元方法分為行主元法與全主元法第第2章章 解線性代數(shù)方程的直接法解線性代數(shù)方程的直接法2.2 2.2 三角分解法三角分解法2.2.1 2.2.1 杜里特爾分解法杜里特爾分解法 高斯消去法的消去過程高斯消去法的消去過程, ,本質(zhì)上是把系數(shù)矩陣本質(zhì)上是把系數(shù)矩陣A A分解為單位下三角矩分解為單位下三角

11、矩陣陣L L與上三角矩陣與上三角矩陣R R的乘積的乘積, ,并且求解方程組并且求解方程組Ly=bLy=b的過程的過程, ,回代過程是求解回代過程是求解上三角形方程組上三角形方程組Rx=yRx=y11,1,.,1iijijikkjkral rji jn11()/,1,.,ijijijk kiiiklal rrjin 111112121313111121212212232322223131323233333333112233,()()()()( )()()()()()()()()()() ()()()()()nnnnnnnnnnnnnnnnnnLRArarararay blarararay bla

12、lararay blalalaray b實際計算時 可以將 和 共同存放到增廣矩陣 的位置上第第2章章 解線性代數(shù)方程的直接法解線性代數(shù)方程的直接法2.2 2.2 三角分解法三角分解法2.2.1 2.2.1 杜里特爾分解法杜里特爾分解法 分解分解A=LR,A=LR,且且L L為單位下三角陣為單位下三角陣,R,R為上三角陣為上三角陣, ,稱為杜里特爾稱為杜里特爾(Dollittlse)(Dollittlse)分解分解. . 運用杜里特爾分解求解方程組運用杜里特爾分解求解方程組Ax=bAx=b或或L(Rx)=b,L(Rx)=b,相當(dāng)于求兩個方程組相當(dāng)于求兩個方程組 Ly=b, Rx=yLy=b,

13、Rx=y運算量運算量3232211 (),(),321(),233ALRnnLybnnnnRxynnNn分解需次 解需次解需次 共第第2章章 解線性代數(shù)方程的直接法解線性代數(shù)方程的直接法2.2 2.2 三角分解法三角分解法2.2.2 2.2.2 克洛特分解法克洛特分解法此分解稱為克洛特此分解稱為克洛特(Crout)(Crout)分解分解 AAR,RL對 進(jìn)行杜里特爾分解時, =L為單位下三角陣, 為上三角陣1122 DR(,.,)nnDdiag rrr令 為 的對角元所構(gòu)成的對角陣 -1 ()()ALRLD D R11111122 (,.,)nnDdiag rrr則 計算公式計算公式1111

14、,1,., ()/ 1,2,.,1ijijijk kikiijijikkjiiklal rji inral rljiin 第第2章章 解線性代數(shù)方程的直接法解線性代數(shù)方程的直接法2.2 2.2 三角分解法三角分解法2.2.3 2.2.3 追逐法追逐法111122223331111 nnnnnnnbcdabcdabcdAA babcdabd11122223333111111111nnnnnnnlryalryalryAalryaly 作克洛特分解第第2章章 解線性代數(shù)方程的直接法解線性代數(shù)方程的直接法2.2 2.2 三角分解法三角分解法2.2.3 2.2.3 追逐法追逐法1111 ,/b ydl1

15、因此,可得 l11111/, ()/ , 2,3,.,iiiiii iiiiiircllba ryda ylin1 ,1,.,1nniiiixyxyrxin回代得到, ,iiir l y 按以上公式求解Ax=b的方法稱為追趕法其中計算的過程稱為追 回代和過程稱為趕 計算量估計:共需要的乘除法次數(shù)為5n-4.第第2章章 解線性代數(shù)方程的直接法解線性代數(shù)方程的直接法2.2 2.2 三角分解法三角分解法2.2.4 2.2.4 平方根法平方根法 AAxb對于求解 為正定矩陣的方程組121/2111() ()/, 1,., ,1,.,iiiiiikkijijijk ikiiklallal iljin i

16、n 計算公式A即 可分解為下三角陣及其轉(zhuǎn)置矩陣的乘積()TALD L則由于A的各階順序主子式大于0,則A可作克洛特分解 且L的對角元全為正數(shù)121211112222(,.,)()()()nTTTDdiagdddALD DLLDLDLL令則 第第2章章 解線性代數(shù)方程的直接法解線性代數(shù)方程的直接法2.3 2.3 舍入誤差對解的影響舍入誤差對解的影響2.3.1 2.3.1 向量和矩陣的范數(shù)向量和矩陣的范數(shù)121222 1/21221 () maxnnii nxxxxxxxxxx 常用的向量的范數(shù)有三種:1212 ( ,.,) ,( )( ,.,)Tnnxx xxxxxx xx對向量具有如下類似性質(zhì)

17、的函數(shù) 向量 的范數(shù)或 稱為?；蜷L度 (1) =0, ,0 (2) , (3) : xxxxxyxy 性質(zhì): 非負(fù)性:齊次性:對任意實數(shù)三角不等式第第2章章 解線性代數(shù)方程的直接法解線性代數(shù)方程的直接法2.3 2.3 舍入誤差對解的影響舍入誤差對解的影響2.3.1 2.3.1 向量和矩陣的范數(shù)向量和矩陣的范數(shù) ( )AA對n階矩陣A,具有如下4種性質(zhì)的函數(shù) 稱為矩陣A的范數(shù) (1) 0 =0, 0,0 (2) , (3) : (4) AAAAABABABA B 性質(zhì): 非負(fù)性:齊次性:對任意實數(shù)三角不等式111112 max,1 max, (),nijjninijinjTAaAaAA A 常

18、用 矩 陣 范 數(shù) :稱 為 范 數(shù)稱 為 無 窮 大 范 數(shù)稱 為 譜 范 數(shù)第第2章章 解線性代數(shù)方程的直接法解線性代數(shù)方程的直接法2.3 2.3 舍入誤差對解的影響舍入誤差對解的影響2.3.1 2.3.1 向量和矩陣的范數(shù)向量和矩陣的范數(shù)21/ 211 ()nnijFijAa 矩 陣 的 F范 數(shù) (Frobenius):1 (1) (2) I11 (3) 1, ()1AxA xIBIBIBB矩陣范數(shù)還具有以下性質(zhì): 單位矩陣 的范數(shù)當(dāng)時可逆 且第第2章章 解線性代數(shù)方程的直接法解線性代數(shù)方程的直接法2.3 2.3 舍入誤差對解的影響舍入誤差對解的影響2.3.2 2.3.2 舍入誤差對解

19、的影響舍入誤差對解的影響,Axbxxb 直 接 法 解 線 性 方 程 組由 于 舍 入 誤 差 的 存 在 ,只 能得 到 近 似 解,或 者 是 A的 精 確 解1-, 1(),AbAAAbbbxbAkAxbAkAkcond AAAAxb近 似 矩 陣和 近 似 向 量的 誤 差 為 則 可 以 得 到其 中稱 為 方 程 組的 條 件 數(shù)k條 件 數(shù)很 大 的 方 程 稱 為 病 態(tài) 方 程 組k值 比 較 小 的 方 程 組 稱 為 良 態(tài) 方 程 組第第3章章 插值法與最小二乘法插值法與最小二乘法( ) 0,1,.,iiyf xin數(shù)個點處數(shù) 已知函y =f(x)在n+1互不相同的的

20、函值3.1 3.1 拉格朗日插值法拉格朗日插值法3.1.1 3.1.1 插值多項式的概念插值多項式的概念2012( ) ( ) (3-2)nnnyf xp xaa xa xa x為數(shù)選項求函的近似值,用n次多式( ) ( ) 0,1,., (3-3)nniip xp xyin滿條使足件 運用以上方法求函數(shù)近似式的方法稱為插值法運用以上方法求函數(shù)近似式的方法稱為插值法 滿足條件滿足條件(3-3)(3-3)的插值多項式是存在且獨一的的插值多項式是存在且獨一的第第3章章 插值法與最小二乘法插值法與最小二乘法01(1)( ),.,1,( )( )( ) ( )( )( )( )(1)!nnnnnyf

21、xx xxa bna bxf xpxfR xf xpxxn 如果被插函數(shù)在包含節(jié)點的區(qū)間上存在階導(dǎo)數(shù),則在區(qū)間上的任意點 處,被插函數(shù)與插值多項式的誤差3.1 3.1 拉格朗日插值法拉格朗日插值法3.1.2 3.1.2 插值多項式的截斷誤差插值多項式的截斷誤差0101 ( )()()() ,.,nnxxxxxxxxx xx 其中為介于 與節(jié)點之間 這種誤差不思索舍入誤差，稱為截斷誤差這種誤差不思索舍入誤差，稱為截斷誤差第第3章章 插值法與最小二乘法插值法與最小二乘法3.1 3.1 拉格朗日插值法拉格朗日插值法3.1.3 3.1.3 拉格朗日插值多項式拉格朗日插值多項式000( )( )nnnj

22、niiiiijijj ixxL xl x yyxx ( ),( ) ( )( -)( )iiiinl xxl xx xx 這里 次式稱為拉格朗日插值基函數(shù) 簡寫為01011( )()()(), ( )()()()()niiiiiiinxxxxxxxxxxxxxxxx其中第第3章章 插值法與最小二乘法插值法與最小二乘法3.1 3.1 拉格朗日插值法拉格朗日插值法3.1.3 3.1.3 拉格朗日插值多項式拉格朗日插值多項式0110101101,-( )( )nx xx xf xL xyyxxxx特例 當(dāng)時 有 1011( )( )( -)( -)2R xfx xx x 02122010102101

23、201220212,( -)( -)( -)( -)( )( )()()()()( -)( -) +()()nx xx xx xx xf xL xyyxxxxxxxxx xx xyxxxx 當(dāng)時 有 20121( )( )( -)( -)( -)6R xfx xx xx x 第第3章章 插值法與最小二乘法插值法與最小二乘法3.1 3.1 拉格朗日插值法拉格朗日插值法3.1.3 3.1.3 拉格朗日插值多項式拉格朗日插值多項式計算插值多項式的值計算插值多項式的值 假設(shè)計算的插值點在節(jié)點之外假設(shè)計算的插值點在節(jié)點之外, ,那么稱為外推或外插那么稱為外推或外插 假設(shè)計算的插值點在節(jié)點之間假設(shè)計算的插

24、值點在節(jié)點之間, ,那么稱為內(nèi)插那么稱為內(nèi)插內(nèi)插的誤差較小內(nèi)插的誤差較小, ,外插的誤差較大外插的誤差較大, ,誤差公式由誤差公式由R(x)R(x)得到得到第第3章章 插值法與最小二乘法插值法與最小二乘法3.2 3.2 添節(jié)點與導(dǎo)數(shù)的插值法添節(jié)點與導(dǎo)數(shù)的插值法3.2.1 3.2.1 牛頓插值多項式牛頓插值多項式為使其滿足插值條件為使其滿足插值條件(3-3),(3-3),只需滿足方程組只需滿足方程組00011011022012022021010201011()( )(-)()(-)(-)(-)()(-)(-)(-) (-)(-)(-)nnnnnnnnnnnnnnyNxcyNxcc xxyNxcc

25、 xxc xxxxyNxcc xxc xxxxc xxxxxx因此因此, ,可得可得000()cyf x 第第3章章 插值法與最小二乘法插值法與最小二乘法3.2 3.2 添節(jié)點與導(dǎo)數(shù)的插值法添節(jié)點與導(dǎo)數(shù)的插值法3.2.1 3.2.1 牛頓插值多項式牛頓插值多項式012120110012012(,.,)( ,.,)(,.,) (,.,)( ),.,iiiiiiicf x x xxf x xxf x xxxxf x x xxyf xx x xxi 同理可得 稱為在處的 階差商001010120101011( )()(,)()(,)()() (,.,)()()()nnnNxf xf x xxxf x

26、 x xxxxxf x xxxxxxxx 于是得到 稱為牛頓(Newton)插值多項式第第3章章 插值法與最小二乘法插值法與最小二乘法3.2 3.2 添節(jié)點與導(dǎo)數(shù)的插值法添節(jié)點與導(dǎo)數(shù)的插值法3.2.1 3.2.1 牛頓插值多項式牛頓插值多項式01( )( )( ) (,., ) ( )nnnR xf xNxf x xxxx 011(,.,) ( ) nnf x xxxx01011(,., )(,.,)nnnf x xxxf x xxx假定1( )( )nnNxNx1( )1( )nnNxnNx 因此,牛頓插值多項式的截斷誤差約等于牛頓插值次式增加的項0011012212012332312301

27、23()()(,)()( ,)(,)()(,)( ,)(,)xf xxf xf x xxf xf x xf x x xxf xf x xf x x xf x x x x差商表差商表第第3章章 插值法與最小二乘法插值法與最小二乘法3.2 3.2 添節(jié)點與導(dǎo)數(shù)的插值法添節(jié)點與導(dǎo)數(shù)的插值法3.2.2 3.2.2 逐次線性插值法逐次線性插值法(1)( )( )( ) ( )( )( )( )(1)!nnnxf xfRxf xpxxnn 多項式插值式項式p與被插函數(shù)的誤差為0,1*121,( ),.,( ),.,nnnnpxx xxpxx xx假設(shè)是以為節(jié)點的插值多項式 是以為節(jié)點的插值多項式*001*

28、110( )( ) ( )( )()( )( ) ( )( )() (3-5)nnnnnnnnnpxpxf xpxxxxxpxpxf xpxxxxx因此得到估計式*001( )( )( ) ( )( )() nnnnpxpxf xf xpxxxxx因此得到更好的近似式第第3章章 插值法與最小二乘法插值法與最小二乘法3.2 3.2 添節(jié)點與導(dǎo)數(shù)的插值法添節(jié)點與導(dǎo)數(shù)的插值法3.2.2 3.2.2 逐次線性插值法逐次線性插值法111-1-1-1,.,( ),( )( ) ( )( )()iiiikkiiiikkkkikikixxxNxNxNxNxNxxxxx 假設(shè)節(jié)點為的插值多項式為則此方法稱為列維

29、爾(Neville)逐次線性插值法0000101011210202123210303123( )( )( )( )( )( )( )( )( )( )xNxyxNxyNxxNxyNxNxxNxyNxNxNx列維爾算法表列維爾算法表第第3章章 插值法與最小二乘法插值法與最小二乘法3.2 3.2 添節(jié)點與導(dǎo)數(shù)的插值法添節(jié)點與導(dǎo)數(shù)的插值法3.2.3 3.2.3 帶導(dǎo)數(shù)的插值多項式帶導(dǎo)數(shù)的插值多項式( )1,( ),( )()nyf xnnHxf xHermite 如果已知被插函數(shù)在節(jié)點處的函數(shù)值和導(dǎo)數(shù)值共個值則在這些節(jié)點處函數(shù)值和導(dǎo)數(shù)值等于已知值的 次多項式稱為的帶導(dǎo)數(shù)插值多項式或埃爾米特插值多項式

30、()( )1),.,1,.,.()1(,.,)!iriiiiiiiiiiikiiiixyyyyxrxxxxfxkkf xxxk求解方法有兩種( 已知節(jié)點 處函數(shù)值與導(dǎo)數(shù)值時 把視為重節(jié) 點直接應(yīng)用牛頓插值法 此時個重節(jié)點的 階差商應(yīng)為(2)仿效拉格朗插值多項式的導(dǎo)出法第第3章章 插值法與最小二乘法插值法與最小二乘法3.3 3.3 分段插值與樣條函數(shù)插值法分段插值與樣條函數(shù)插值法3.3.1 3.3.1 高次插值多項式的缺陷高次插值多項式的缺陷(1)( ) ( )( )( )( )(1)!nnnfR xf xpxxn 插值多項式的誤差公式(1)( )( ),nfx由于與與有關(guān) 因此,其絕對值不一定

31、隨次數(shù)n的增大而減小插值多項式的與原函數(shù)在插值點處誤差較小,但在其它點處誤差很大,出現(xiàn)龍格現(xiàn)象第第3章章 插值法與最小二乘法插值法與最小二乘法3.3 3.3 分段插值與樣條函數(shù)插值法分段插值與樣條函數(shù)插值法3.3.2 3.3.2 分段低次插值法分段低次插值法012-1*11-1-11., , ,( )( )( -)niiiiiiiiaxxxxba bnxixxyyf xp xyx xxx 設(shè)則節(jié)點把分成 個小區(qū)間當(dāng)插值點在第 個小區(qū)間上時 采用一次插值分式 此方法稱為分段線性插值法*1-11( )( )( )( -)( -)2iif xpxfx xx x其截斷誤差為 22-1-1*21( )1

32、1( -)( -)(-)441( )( )8iiiiiixx xx xxxhf xp xh2i-1i設(shè)a,b上 fM ,則在x,x 上 則 *11max0,( )( )ii nhhp xf x 當(dāng)收斂于被插函數(shù)第第3章章 插值法與最小二乘法插值法與最小二乘法3.3 3.3 分段插值與樣條函數(shù)插值法分段插值與樣條函數(shù)插值法3.3.3 3.3.3 三次樣條函數(shù)插值法三次樣條函數(shù)插值法 為保證插值函數(shù)及其導(dǎo)數(shù)在插值區(qū)間內(nèi)處處充分接近被插函數(shù),需要使用樣條函數(shù)作插值函數(shù)01-1( ),(.), , -1iniimS xx axxxbxxma bm 次樣條函數(shù)是一種分段函數(shù) 在節(jié)點分成的每個小區(qū)間上是

33、次多項式 而在整個區(qū)間上為階導(dǎo)數(shù)連續(xù)-1,iixx 常用的樣條函數(shù)為三次樣條函數(shù),在區(qū)間上是3次多項式m (1) 表達(dá)式12211122111( ),( ),( )(12)()(12)() ()()()()iiiiiiiiiiiiiiiiiiiiiiiiS xy S xm hxxxxxxxxxxS xyyhhhhxxxxxxmxxmhh設(shè)則有第第3章章 插值法與最小二乘法插值法與最小二乘法3.3 3.3 分段插值與樣條函數(shù)插值法分段插值與樣條函數(shù)插值法3.3.3 3.3.3 三次樣條函數(shù)插值法三次樣條函數(shù)插值法 (2)M表達(dá)式33112211111 ( )()()6 ()() ,66iiiii

34、iiiiiiiiiiiiS xxxMxxMhhxxhxxyMyMxxxhh1( ),( ),iiiiiiS xy SxM hxx 設(shè)( )iS xM 利用的導(dǎo)數(shù)的連續(xù)性推出滿足的方程11111111162iiiiiiiiiiiiiiiiihhyyyyMMMhhhhhhhh1111111116,1,6 (,)iiiiiiiiiiiiiiiiiiihhyyyydf xx xhhhhhhhh ii記 11-1 2 1,., -1iiiiiiMnMMMdini則滿足個方程 此方程組稱為三彎矩方程組第第3章章 插值法與最小二乘法插值法與最小二乘法3.3 3.3 分段插值與樣條函數(shù)插值法分段插值與樣條函數(shù)

35、插值法3.3.3 3.3.3 三次樣條函數(shù)插值法三次樣條函數(shù)插值法樣條插值函數(shù)樣條插值函數(shù)優(yōu)點優(yōu)點: :在節(jié)點加密時在節(jié)點加密時, ,它和它的導(dǎo)函數(shù)能在整個插值區(qū)間上它和它的導(dǎo)函數(shù)能在整個插值區(qū)間上 充分接近被插函數(shù)充分接近被插函數(shù)缺陷缺陷: :為求為求M M或或m m表達(dá)式表達(dá)式, ,需構(gòu)成方程組并進(jìn)展求解需構(gòu)成方程組并進(jìn)展求解第第3章章 插值法與最小二乘法插值法與最小二乘法3.4 3.4 最小二乘法最小二乘法2211( )( ),1,2,.,( )( ),( )( ),1,2,.,( )iiiiiimmiiiiiyf xmyf ximf xp xp xyp xy imSp xy 假定觀測得

36、到的函數(shù)的 個函數(shù)值 求的簡單近似式使與 的差的平方和最小 即 使最小( ) ( ), ( )p xmyp xxyf x 稱為 個數(shù)據(jù)的最小二乘擬合函數(shù)近似反映變量 與 之間的關(guān)系 稱為經(jīng)驗公式稱為被擬合的函數(shù)001122( )( )( )( )( )( ),( )nniip xp xcxcxcxcx nmxcS 最小二乘擬合函數(shù)可寫為 其中 應(yīng)適當(dāng)選取且線性無關(guān)在此表示式中,求系數(shù) 使殘差平方和 最小第第3章章 插值法與最小二乘法插值法與最小二乘法3.4 3.4 最小二乘法最小二乘法01111102122201()()()()()(),()()(), nnmmnmnTTTTxxxyxxxyy

37、xxxyAbycy 若記 由于則正規(guī)方程組可寫為 說明A為對稱陣,且為正定陣,正規(guī)方程組必有唯一解01021112( )(0,., ),( )., iiiiiiiiijnjnniniinnnnnixxjnp xcc xc xmxxycxxxx yccxxxx y 當(dāng)最小二乘擬合函數(shù)稱為最小二乘擬合多項式 正規(guī)方程組為第第3章章 插值法與最小二乘法插值法與最小二乘法拉格朗日插值多式項牛頓插值多項式高次多項式插值逐次線性插值多項式擬合法埃爾米特插值多項式插值法 三次樣條函數(shù)插值法低次多項式插值B樣條函數(shù)插值法逼近法 最小二乘法第第4章章 數(shù)值微積分?jǐn)?shù)值微積分( )( ) ( ):( )( ) ,

38、,( ),( )0,( )1( ),baI fx f x dxxf xa bxxxf x 討論以下積分的方法 其中和是區(qū)間上的已知函數(shù) 稱為權(quán)函數(shù)通常 積分被積函數(shù) 假定充分可導(dǎo)4.1 4.1 數(shù)值積分法數(shù)值積分法第第4章章 數(shù)值微積分?jǐn)?shù)值微積分4.1 4.1 數(shù)值積分法數(shù)值積分法4.1.1 4.1.1 近似函數(shù)積分法近似函數(shù)積分法1 ( )( )( )()( ),nniiif xLxl x f xx 由拉格朗日插值法兩邊同乘然后積分 得到插值型求積公式1()( )( )() (4-2),( ) ( )nbiiaiiibiiaIfx f x dxA f xQ fxAAx lx dx 其中稱求積

39、節(jié)點稱為求積系數(shù) (1)(4 - 2) -( )( ) -( )1 ( )( )( )(1)!bnabnaR fI fQ fxf xLxdxxfx dxn 求積公式的截斷誤差第第4章章 數(shù)值微積分?jǐn)?shù)值微積分4.1 4.1 數(shù)值積分法數(shù)值積分法4.1.1 4.1.1 近似函數(shù)積分法近似函數(shù)積分法( )1,x 常 用 數(shù) 值 積 分 公 式 是 權(quán) 函 數(shù)等 矩 節(jié) 點 時 的 求 積 公 式-,0,1,., ,ibaxaih in hhn 稱為步長301(1)1,-()(),( )212nhbahhI ff xf xR ff 梯形求積公式 公式(4-2)稱為牛頓-柯特斯(Newton-cotes

40、)求積公式0125(4)(2)2,(-) / 2()4()()3 ( )90nhbahI ffxfxfxhR ff 辛浦生(Simpson)或拋物線求積公式 第第4章章 數(shù)值微積分?jǐn)?shù)值微積分4.1 4.1 數(shù)值積分法數(shù)值積分法4.1.1 4.1.1 近似函數(shù)積分法近似函數(shù)積分法01235(4)(3)3,(-) / 33()3()3()()83 ( )80nhbahI ff xf xf xf xhR ff 牛頓求積公式 012347(6)(4)4,(-) / 427()32()12()32()7()458 ( )945nhbahI ff xf xf xf xf xhR ff 柯特斯求積公式 第第

41、4章章 數(shù)值微積分?jǐn)?shù)值微積分4.1 4.1 數(shù)值積分法數(shù)值積分法1212114(4)( ) ( )4()2()( )3 ( ) ()( )180nniiiiI fS hhf af xf xf bR fI fS hhba f 復(fù)化復(fù)辛浦生求積公式 以上方法是取定步長以上方法是取定步長h h算積分的方法算積分的方法, ,稱為定步長積分法稱為定步長積分法4.1.2 4.1.2 復(fù)化求積公式復(fù)化求積公式第第4章章 數(shù)值微積分?jǐn)?shù)值微積分4.1 4.1 數(shù)值積分法數(shù)值積分法4.1.3 4.1.3 變步長積分法變步長積分法*,.hh 為使計算精度增高,可知當(dāng)h充分小時,必會使誤差滿足要求. 因此 先任取步長

42、為 進(jìn)行計算 然后取較小步長進(jìn)行計算如果兩次計算結(jié)果相差較大 則取更小步長進(jìn)行計算 如此繼續(xù)下去 直到相鄰兩次計算結(jié)果相差不大為止 取最小步長算出的結(jié)果作為積分值 此方法稱為變步長積分法.* ,2hh 在進(jìn)行實際計算時 一般可取進(jìn)行計算第第4章章 數(shù)值微積分?jǐn)?shù)值微積分4.1 4.1 數(shù)值積分法數(shù)值積分法4.1.4 4.1.4 龍貝格積分法龍貝格積分法( )(2 )( )( )3T hThS hT h23( )(2 )( )( ) 41( )(2 )( )( ) 41S hShC hS hC hChR hC h 復(fù)化柯特斯求積公式 龍貝格積分法011222333301()()()()()()()

43、()()(),/ 2,1,2.iiT hT hS hT hS hC hT hS hC hR hhba hhi龍貝格積分法計算過程 其中第第4章章 數(shù)值微積分?jǐn)?shù)值微積分4.1 4.1 數(shù)值積分法數(shù)值積分法4.1.5 4.1.5 待定系數(shù)法與高斯型求積公式待定系數(shù)法與高斯型求積公式1 ()( )( )() (4-2),( ) ( )nbiiaiiibiiaIfxfx dxA fxQfxAAx lx dx 在 以 下 的 插 值 型 求 積 公 式 中 其 中稱 求 積 節(jié) 點稱 為 求 積 系 數(shù) (1) -()() -()1 ()()()(1)!bnabnaRfIfQfxfxLxdxxfx dx

44、n 其 截 斷 誤 差(1)(1),(),0,0;1,(1)!, ()()0,(4 - 2)nnbafxrrnfRfrnfnRfxx dxcn因 此 若是次 多 項 式 則則 必 有而 當(dāng)時則 有所 以 稱 插 值 型 求 積 公 式的 代 數(shù) 精 度 為第第4章章 數(shù)值微積分?jǐn)?shù)值微積分4.1 4.1 數(shù)值積分法數(shù)值積分法4.1.5 4.1.5 待定系數(shù)法與高斯型求積公式待定系數(shù)法與高斯型求積公式121211221122,1( )( ) ( )0,( )1,0,R ffccmfxfxR c fc fc R fc R fmf xR ff xmR fm 假定某個近似公式兩邊之差是 的線性式 即對任

45、意常數(shù)和對任意兩個階導(dǎo)數(shù)存在的函數(shù)和滿足條件如果對任意次數(shù)不超過次的多項式有但當(dāng)是某個次的多項式時則稱該近似式代數(shù)精度的為定義定義第第4章章 數(shù)值微積分?jǐn)?shù)值微積分4.1 4.1 數(shù)值積分法數(shù)值積分法4.1.5 4.1.5 待定系數(shù)法與高斯型求積公式待定系數(shù)法與高斯型求積公式(1)010101 , 1,( ) ( )( )( )( ,.,)( )( )(1)! ( )()()(),., , 1,.,mmmmR fa bmmR f xR e xfe xf x xxxxxmxxxxxxxa bmx xxxx01m 設(shè)近似式兩邊之差是區(qū)間上階導(dǎo)數(shù)連續(xù)的線性表示式 且代數(shù)精度為則其中 xxx而是區(qū)間上的

46、個任意點是在之間且與01,.,mxxx 有關(guān)的數(shù)廣義皮亞諾定理廣義皮亞諾定理01:( )( ),.,( )( )( ), mp xf xxxxf xp xe xR fR peR pR eR e證明 設(shè)是以為節(jié)點的插值多項式 則則有 第第4章章 數(shù)值微積分?jǐn)?shù)值微積分4.2 4.2 數(shù)值微分法數(shù)值微分法4.2.1 4.2.1 近似函數(shù)求導(dǎo)法近似函數(shù)求導(dǎo)法()()()0( )( ),( )( )( )()nnkkkniiif xLxfxLxlx f x 函數(shù)的拉格朗日插值多項式既是其近似式 其導(dǎo)數(shù)也可以用來近似求其導(dǎo)數(shù) 即有 ()(1)()011 ( )( )(1)!,.,knkndR ffxdxn

47、x xxx 其截斷誤差為 其中 與有關(guān)(2)*(1)11 ()( )( )( )(2)!(1)!nnR ffxfxnn 因此第第4章章 數(shù)值微積分?jǐn)?shù)值微積分4.2 4.2 數(shù)值微分法數(shù)值微分法4.2.1 4.2.1 近似函數(shù)求導(dǎo)法近似函數(shù)求導(dǎo)法0101102001221201()(),( )21()(),( )21()( 34),( )231()(),26hfxyyR ffhhfxyyR ffhhfxyyyR ffhhfxyyR fh 常 用 的 數(shù) 值 微 分 公 式 是 公 式 (4-23)中 節(jié) 點 等 矩 且 x為節(jié) 點 的 特 殊 情 形(1)兩 點 數(shù) 值 微 分 公 式 (2)三

48、 點 數(shù) 值 微 分 公 式 22012( )1()(43),( )23fhfxyyyR ffh 第第4章章 數(shù)值微積分?jǐn)?shù)值微積分4.2 4.2 數(shù)值微分法數(shù)值微分法4.2.1 4.2.1 近似函數(shù)求導(dǎo)法近似函數(shù)求導(dǎo)法*21*22*2*21*22*2()( )( )() ()( )(/)1()( )()( ) ()()(/)1T hT hT hT hfxT hhhhhhT hT hT hT hfxT hhhhh h 實用的截斷誤差估計式為第第5章章 方程和方程組的迭代解法方程和方程組的迭代解法( )0(5-1)f x 討論以下方程的根 5.1 5.1 方程求根法方程求根法5.1.1 5.1.1

49、 試探法與二分法試探法與二分法( ) , ,( ) ( )0,( , ),( )0.( )( )0yf xa bf a f ba bff xf x 如果函數(shù)在區(qū)間上連續(xù) 且那么在區(qū)間內(nèi)必定存在使 稱為函數(shù)的零零點定理點或方程的根第第5章章 方程和方程組的迭代解法方程和方程組的迭代解法 (1)試探法5.1 5.1 方程求根法方程求根法5.1.1 5.1.1 試探法與二分法試探法與二分法01-1-1-,(0,1,. ), (),(),.,()()0,;() ()0,.2.inkkkkkkb anhxaih innf xf xf xf xxxxf xf xh 任取正整數(shù)令順次計算 若發(fā)現(xiàn)則取 為 若

50、發(fā)現(xiàn)則取為在此方法中所得的根的誤差不超過第第5章章 方程和方程組的迭代解法方程和方程組的迭代解法 (2)二分法5.1 5.1 方程求根法方程求根法5.1.1 5.1.1 試探法與二分法試探法與二分法1,( ),( )0,2,2( )( )0,( )( )0,3-,abcf cf ccf a f cbcf c f bachb a步驟 取區(qū)間中點計算若發(fā)現(xiàn)則取 為結(jié)束 若則令 若則令 若區(qū)間長度充分小 則取中點為結(jié)束 否則,轉(zhuǎn)(1) 此方法的近似值誤差不超過h/2第第5章章 方程和方程組的迭代解法方程和方程組的迭代解法5.1 5.1 方程求根法方程求根法5.1.2 5.1.2 簡單迭代法簡單迭代法

51、0121 , ,.,(),0,1,2,.(5-3)kka bcxx xxxk 已知根 的存在區(qū)間可取中點 為根 的粗略近似值為求逐次逼近 的近似值 希望使用相同的公式 利用此式求根近似值的方法稱為簡單迭代法( ), (5-3)kxx 稱為迭代序列 為迭代函數(shù)稱為迭代格式第第5章章 方程和方程組的迭代解法方程和方程組的迭代解法5.1 5.1 方程求根法方程求根法5.1.2 5.1.2 簡單迭代法簡單迭代法1()().()(,(),(),().kkkkkkxxyxyxxxxxyxxxx 方 程的 根可 看 作 是 直 線與的交 點 的 橫 坐 標(biāo) 迭 代 公 式相 當(dāng) 于 過 曲 線 上 的 點作

52、 水 平 線 與 直 線相 交 過 交 點 作軸 的 垂 線 此 時 垂 足至 原 點 的 距 離 等 于 垂 線 長即 垂 足 的 橫 坐 標(biāo) 為幾何意義幾何意義01():(1),(),;(2)1,()1,()(),kkxxa bxa bLxa bxLxa bxxxxa b 設(shè) 迭 代 函 數(shù) 方 程滿 足 條 件 當(dāng)時 存 在 正 數(shù)使 對 任 意有則 對 任 意 初 值迭 代 序 列收 斂 于 方 程在上 唯 一 根簡單迭代收斂定理簡單迭代收斂定理第第5章章 方程和方程組的迭代解法方程和方程組的迭代解法5.1 5.1 方程求根法方程求根法5.1.2 5.1.2 簡單迭代法簡單迭代法1,lim0.1,12kkpkkkxxcxxpppp 序 列收 斂 于如 果 則 稱是階 收 斂 的當(dāng)時 稱 為 線 性 收 斂稱 為 超 線 性 收 斂稱 為 平 方 收 斂12()()xx 是 線 性 收 斂 ,是 超 線 性 收 斂第第5章章 方程和方程組的迭代解法方程和方程組的迭代解法5.1 5.1 方程求根法方程求根法5.1.4 5.1.4 牛頓迭代法牛頓迭代法21()()()()(