數(shù)值計(jì)算方法及算法第1頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月第0章緒論第2頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月

數(shù)學(xué)建模數(shù)值計(jì)算實(shí)際問(wèn)題數(shù)學(xué)問(wèn)題近似解什么是數(shù)值計(jì)算方法？什么是“好的”數(shù)值計(jì)算方法？誤差小─誤差分析耗時(shí)少─復(fù)雜度分析抗干擾─穩(wěn)定性分析第3頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月誤差的類型 絕對(duì)誤差＝真實(shí)值－近似值 相對(duì)誤差＝絕對(duì)誤差／真實(shí)值誤差的來(lái)源 原始誤差、截?cái)嗾`差、舍入誤差輸入計(jì)算輸出真實(shí)值近似值第4頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月一些例子： 計(jì)算地球的體積 計(jì)算 計(jì)算如何減小計(jì)算誤差？

選擇好的算法、提高計(jì)算精度范數(shù)的定義 滿足非負(fù)性,齊次性,三角不等式的實(shí)函數(shù)第5頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月常用的向量范數(shù)常用的矩陣范數(shù)矩陣的譜半徑例：計(jì)算矩陣 的范數(shù)和譜半徑。例：范數(shù)在誤差估計(jì)中的應(yīng)用第6頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月第1章插值第7頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月函數(shù)逼近 用未知函數(shù)f(x)的值構(gòu)造近似函數(shù)φ(x)。要求誤差小、形式簡(jiǎn)單、容易計(jì)算。常用的函數(shù)逼近方法插值：φ(xi)=yi,i=0,1,…,n.擬合：||φ(x)-f(x)||盡可能小通常取

φ(x)=a0φ0(x)+…+anφn(x)，其中{φi(x)}為一組基函數(shù)。第8頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月多項(xiàng)式插值 給定平面上n+1個(gè)插值點(diǎn)(xi,yi),構(gòu)造n次多項(xiàng)式φ(x),滿足φ(xi)=yi,i=0,1,…,n.第9頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月單項(xiàng)式插值第10頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月Lagrange

插值第11頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月Newton

插值第12頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月差商表012…n…0…1…2……......nk階差商第13頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月差商的性質(zhì)以x0,…,xn為節(jié)點(diǎn)的n次插值多項(xiàng)式φ(x)的首項(xiàng)系數(shù)等于f[x0,…,xn]。 證明：分別以x0,…,xn-1和x1,…,xn為節(jié)點(diǎn)構(gòu)造n-1次插值多項(xiàng)式φ1(x)和φ2(x)，則有

對(duì)n用歸納法。f[x0,…,xn]與x0,…,xn的順序無(wú)關(guān)。第14頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月誤差估計(jì)：證明：設(shè) ，則

有n+2個(gè)零點(diǎn)。 根據(jù)中值定理，存在于是 。第15頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月Hermite插值 給定平面上n+1個(gè)插值點(diǎn)(xi,yi,mi),構(gòu)造2n+1次多項(xiàng)式φ(x),滿足φ(xi)=yi,φ’(xi)=mi,i=0,1,…,n.第16頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月單項(xiàng)式

基函數(shù)Lagrange

基函數(shù)第17頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月誤差估計(jì)：證明：設(shè) ，則

有2n+3個(gè)零點(diǎn)。根據(jù)中值定理，存在

于是 。第18頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月Runge現(xiàn)象：并非插值點(diǎn)取得越多越好。解決辦法：分段插值第19頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月三次樣條插值 給定平面上n+1個(gè)插值點(diǎn)(xi,yi),構(gòu)造分段三次多項(xiàng)式φ(x),滿足φ(xi)=yi,φ’(x)可微，φ”(x)連續(xù)。第20頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月第2章數(shù)值微分和數(shù)值積分第21頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月數(shù)值微分差商法 向前差商 向后差商 中心差商第22頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月插值法

在x附近取點(diǎn)(xi,f(xi))構(gòu)造插值多項(xiàng)式φ。樣條法

在x附近取點(diǎn)(xi,f(xi))構(gòu)造樣條函數(shù)φ。

f’(x)≈φ’(x)第23頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月例：用中心差商公式計(jì)算f’(xi)。例：用向后差商公式計(jì)算f’’(0.2),

f’’(0.4)。x0.00.10.20.30.4f(x)1.71.51.62.01.9f’(x)f”(x)x0.00.10.20.30.4f(x)0.8187310.9048371.0000001.1051711.221403f’(x)第24頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月例：設(shè)xi=x0+i*h,i=1,...,n。計(jì)算φ’(xk)。解：第25頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月誤差估計(jì) 前后差商

中心差商

插值微分第26頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月數(shù)值積分插值法第27頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月若積分公式對(duì)任意m次多項(xiàng)式都取等號(hào)，則稱積分公式具有至少m階的代數(shù)精度。插值型積分公式的代數(shù)精度≥n。當(dāng)積分節(jié)點(diǎn)x0,...,xn給定時(shí)，

代數(shù)精度≥n的積分公式唯一。第28頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月例：設(shè)xi=a+i*h,i=0,...,n,h=(b-a)/n。

計(jì)算Newton-Cotes積分解：第29頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月特別，當(dāng)n=1,2時(shí)，積分公式分別稱為梯形公式Simpson公式na1a2a3a4a51??21/64/61/631/83/83/81/847/9032/9012/9032/907/90第30頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月誤差估計(jì)特別，梯形公式和Simpson公式的誤差為 代數(shù)精度＝1

代數(shù)精度＝3第31頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月復(fù)化數(shù)值積分第32頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月梯形公式Simpson公式第33頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月Richardson外推法

我們要計(jì)算 假設(shè) 則 有比和更高的精度。誤差估計(jì)第34頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月Romberg積分公式 等分的梯形公式，瑕積分重積分Gauss-Legendre積分第35頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月定理：假設(shè) 滿足則插值積分公式具有2n+1階的代數(shù)精度。證明：課本21頁(yè)性質(zhì)1.3：若f(x)為m次多項(xiàng)式，則f[x0,...,xn,x]為m-n-1次多項(xiàng)式。第36頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月求多項(xiàng)式空間在內(nèi)積

下的標(biāo)準(zhǔn)正交基。解法1：對(duì)任意基作Gram-Schmidt正交化。解法2：對(duì)任意度量方陣作相合對(duì)角化。解法3：求解正交關(guān)系的線性方程組。解法4：Legendre多項(xiàng)式第37頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月第3章曲線擬合的最小二乘法第38頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月曲線擬合對(duì)區(qū)間I上的連續(xù)函數(shù)

f，

構(gòu)造特定類型的函數(shù)φ

使φ≈f。對(duì)離散數(shù)據(jù)序列(xi,yi),i=1,2,…,m，

構(gòu)造特定類型的函數(shù)φ

使φ(xi)≈yi。最小二乘法求φ

使 最小。求φ

使 最小。第39頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月多項(xiàng)式擬合 其中

是標(biāo)準(zhǔn)正交基， 。

求 使 最小。第40頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月奇異值分解Moore-Penrose廣義逆矛盾方程組的解第41頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月其他類型的離散數(shù)據(jù)擬合

第42頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月第4章非線性方程求根第43頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月問(wèn)題求f(x)=0在區(qū)間[a,b]內(nèi)的實(shí)根求f(x)=0在x0附近的一個(gè)實(shí)根求f(x)=0在x0附近的一個(gè)復(fù)根求多項(xiàng)式f(x)=0的所有復(fù)根求非線性方程組的根方法用近似函數(shù)φ(x)的根逼近f(x)的根。第44頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月二分法已知f(a)f(b)<0，設(shè)c=(a+b)/2。若f(a)f(c)<0則根在[a,c]內(nèi)；若f(a)f(c)>0則根在[b,c]內(nèi)。當(dāng)|f(c)|<ε或|b-a|<ε時(shí)，輸出c。迭代步數(shù)：O(log2ε)第45頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月不動(dòng)點(diǎn)

當(dāng)|φ’(x)|≤L<1時(shí)，|xk+1-α|≤L|xk-α|。當(dāng)|xn+1-xn|<ε時(shí)，輸出xn。迭代步數(shù)：O(logLε)Lipschitz常數(shù)線性收斂第46頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月Newton法（一階Taylor展開(kāi)） 當(dāng)|f(xk)|<ε或|xk+1-xk|<ε時(shí)，輸出xk+1。 迭代步數(shù)：O(loglogε)二次收斂第47頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月Newton法（p重根情形）第48頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月用Newton迭代法求f(z)=z3?2z+2的根。當(dāng)初值分別位于紅、藍(lán)、綠色區(qū)域時(shí)，迭代收斂到三個(gè)根。當(dāng)初值位于黑色區(qū)域時(shí)，迭代陷入死循環(huán)0→1→0。圖片引自JohnHubbard,DierkSchleicher,ScottSutherland,Howtofindallrootsofcomplexpolynomials,Inventionesmathematicae146,1-33(2001).第49頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月弦截法（線性插值） 當(dāng)|f(xk)|<ε或|xk+1-xk|<ε時(shí)，輸出xk+1。 迭代步數(shù)：O(loglogε)第50頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月弦截法的收斂速度第51頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月Newton法解非線性方程組求 的所有復(fù)根

等價(jià)于求x1,…,xn使f(t)=(t-x1)…(t-xn)。第52頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月其他求根方法 Brent （反插值x=φ(y)）

Halley （二階Taylor展開(kāi)）

Muller （二次插值）

有理插值……第53頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月第5章解線性方程組的直接法第54頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月問(wèn)題：求解n元線性方程組AX=B。方法？速度？精度？存儲(chǔ)？下三角方程組上三角方程組

n(n-1)/2次加減法，n(n+1)/2次乘除法。第55頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月Gauss消元法解一般方程組

(2n3+3n2-5n)/6次加減法，

(n3+3n2-n)/3次乘除法。第56頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月追趕法解三對(duì)角方程組

3n-3次加減法，5n-4次乘除法。第57頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月線性方程組解的精度矩陣條件數(shù)第58頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月Gauss消元法的實(shí)質(zhì)是LU分解存在性？A的順序主子式≠0。唯一性？L1U1=L2U2L1-1L2=U1U2-1對(duì)角精確度？A-1b的相對(duì)誤差≈(L,U,b)的相對(duì)誤差×cond(L)×cond(U)。第59頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月Dolittle分解Courant分解第60頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月全/列/行主元分解LDLT分解、Cholesky分解第61頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月QR分解第62頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月SVD分解Givens旋轉(zhuǎn) Householder反射第63頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月第6章解線性方程組的迭代法第64頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月Jacobi迭代Gauss-Seidel迭代第65頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月迭代法解線性方程組AX=B AXk+1–B=C(AXk–B) C稱為Conditioner，滿足ρ

(C)<1或||C||<1 通常取C=I–A?-1，其中?≈A，于是Xk+1=Xk–?-1(AXk–B)第66頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月Jacobi迭代：?=D定理：A行對(duì)角優(yōu)、或A列對(duì)角優(yōu)

Jacobi迭代收斂。Gauss-Seidel迭代：?=D+L定理：A行對(duì)角優(yōu)、或A列對(duì)角優(yōu)、或A正定

Gauss-Seidel迭代收斂。第67頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月松弛迭代：?=w-1D+L定理：松弛迭代收斂0<w<2定理：A正定且0<w<2

松弛迭代收斂Newton迭代求A-1：Xk+1=2Xk–XkAXk第68頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月第7章計(jì)算矩陣的特征值

和特征向量第69頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月問(wèn)題1：求復(fù)方陣的模最大(最小)特征值。方法：冪法、反冪法問(wèn)題2：求復(fù)方陣的所有特征值。方法：QR迭代問(wèn)題3：求Hermite方陣的所有特征值。方法：Jacobi方法第70頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月冪法當(dāng)A只有一個(gè)模最大的特征值λmax，并且x0與λmax的特征向量amax不正交時(shí)當(dāng)A的模最大的特征值都相同時(shí)，以上迭代仍然收斂。第71頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月當(dāng)A的模最大的特征值各不相同時(shí)，可以選取數(shù)s使A-sI的模最大的特征值只有一個(gè)。當(dāng)A恰有m個(gè)模最大的特征值時(shí)，有 R的特征值就是A的模最大的特征值。第72頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月反冪法當(dāng)A只有一個(gè)模最小的特征值λmin，并且x0與λmin的特征向量amin不正交時(shí)計(jì)算A-sI的模最小的特征值等價(jià)于計(jì)算A的最接近s的特征值。第73頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月QR迭代利用QR分解，酉相似A為上三角。QR迭代的本質(zhì)是冪法當(dāng) 時(shí)，QR迭代收斂。可對(duì)A-sI作QR分解，加速收斂。第74頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月Jacobi方法通過(guò)Givens旋轉(zhuǎn)，逐漸減小非對(duì)角元。本質(zhì)是2階Hermite方陣的酉相似。Jacobi方法具有2階收斂速度。第75頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月復(fù)矩陣的奇異值分解A=UΣV一般方法AHA=VHΣ2V或AAH=UΣ2UHQR迭代Jacobi方法

計(jì)算2階方陣的SVD第76頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月第8章常微分方程數(shù)值解第77頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月問(wèn)題：求解一階常微分方程的初值問(wèn)題：解法：化微分方程為積分方程第78頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月Euler折線法向前Euler公式向后Euler公式 Picard迭代中心Euler公式梯形公式 改進(jìn)的 Euler公式第79頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月Runge-Kutta方法選取{xi,cij}使yr

有最高精度p，即r1,2,3,45,6,78,910,11,...pp=rp=r-1p=r-2p≤r-2第80頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月Runge-Kutta方法的誤差估計(jì)設(shè)滿足Lipschitz條件設(shè)滿足初值誤差截?cái)嗾`差整體誤差第81頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月線性多步法(*)

其中φ(t)為f(t,y(t))的q次插值多項(xiàng)式。當(dāng)xn,…,xn-q為插值節(jié)點(diǎn)時(shí)，(*)稱為顯式Adams公式。當(dāng)xn+1,…,xn+1-q為插值節(jié)點(diǎn)時(shí)，(*)稱為隱式Adams公式。第82頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月一階常微分方程組的初值問(wèn)題：解法：同一階常微分方程的初值問(wèn)題。第83頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月高階常微分方程的初值問(wèn)題解法：令化方程為第84頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月單步法 (*)收斂性穩(wěn)定性

將(*)應(yīng)用于方程y’=y，得yn+1=E(h)yn。

當(dāng)|E(h)|<1時(shí)，稱(*)絕對(duì)穩(wěn)定的。

稱{復(fù)數(shù)h:|E(h)|<1}為絕對(duì)穩(wěn)定區(qū)域。稱{實(shí)數(shù)h:|E(h)|<1}為絕對(duì)穩(wěn)定區(qū)間。第85頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月復(fù) 習(xí)第86頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月第0章緒論誤差的定義向量的范數(shù)矩陣的范數(shù)、條件數(shù)、譜半徑第87頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月第1章插值Lagrange插值差商、Newton插值Hermite插值插值公式的截?cái)嗾`差Runge現(xiàn)象樣條函數(shù)第88頁(yè)，課件共98頁(yè)，創(chuàng)作于2023年2月第2章數(shù)值微分和數(shù)值積分