數(shù)值計(jì)算方法與算法

教學(xué)目標(biāo)掌握常用的數(shù)值計(jì)算方法掌握計(jì)算方法的數(shù)學(xué)原理學(xué)會(huì)選擇恰當(dāng)?shù)挠?jì)算方法學(xué)會(huì)使用流行的計(jì)算軟件第一頁，共99頁。教學(xué)計(jì)劃時(shí)間：7:50-8:35地點(diǎn)：21062-27緒論3-06多項(xiàng)式插值3-13多項(xiàng)式插值3-20分段和樣條插值3-27數(shù)值微分4-03數(shù)值積分4-10數(shù)值積分4-17最小二乘法4-24方程求根5-01五一放假5-08方程求根5-15求解線性方程組5-22求解線性方程組5-29計(jì)算矩陣特征值6-05計(jì)算矩陣特征值6-12微分方程數(shù)值解6-19微分方程數(shù)值解6-26復(fù)習(xí)7-04期末考試7-13報(bào)送成績第二頁，共99頁。教材及參考數(shù)值計(jì)算方法與算法，張韻華、奚梅成、陳效群編，科學(xué)出版社，2006?？茖W(xué)計(jì)算導(dǎo)論，MichaelT.Heath著，張威、賀華、冷愛萍譯，清華大學(xué)出版社，2005。數(shù)值計(jì)算方法解題指導(dǎo)，張韻華編，科學(xué)出版社，2003。網(wǎng)絡(luò)教學(xué)資源第三頁，共99頁。聯(lián)系方式教師：王新茂

xinmao@ 理化大樓16#016，3607565助教：楊榮 136-15607693第四頁，共99頁。第0章緒論第五頁，共99頁。

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

選擇好的算法、提高計(jì)算精度范數(shù)的定義 滿足非負(fù)性,齊次性,三角不等式的實(shí)函數(shù)第八頁，共99頁。常用的向量范數(shù)常用的矩陣范數(shù)矩陣的譜半徑例：計(jì)算矩陣 的范數(shù)和譜半徑。例：范數(shù)在誤差估計(jì)中的應(yīng)用第九頁，共99頁。作業(yè)一、145頁習(xí)題6第1,2題.作業(yè)二、利用公式編寫兩個(gè)計(jì)算ex

的C程序(一個(gè)用單精度,另一個(gè)用雙精度).令x=±1,±5,±10,±15,±20,比較它們和庫函數(shù)exp(x)之間的運(yùn)行時(shí)間和計(jì)算誤差.思考如何減小誤差？第十頁，共99頁。第1章插值第十一頁，共99頁。函數(shù)逼近 用未知函數(shù)f(x)的值構(gòu)造近似函數(shù)φ(x)。要求誤差小、形式簡單、容易計(jì)算。常用的函數(shù)逼近方法插值：φ(xi)=yi,i=0,1,…,n.擬合：||φ(x)-f(x)||盡可能小通常取

φ(x)=a0φ0(x)+…+anφn(x)，其中{φi(x)}為一組基函數(shù)。第十二頁，共99頁。多項(xiàng)式插值 給定平面上n+1個(gè)插值點(diǎn)(xi,yi),構(gòu)造n次多項(xiàng)式φ(x),滿足φ(xi)=yi,i=0,1,…,n.第十三頁，共99頁。單項(xiàng)式插值第十四頁，共99頁。Lagrange

插值第十五頁，共99頁。Newton

插值第十六頁，共99頁。差商表012…n…0…1…2……......nk階差商第十七頁，共99頁。差商的性質(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)，則有

對n用歸納法。f[x0,…,xn]與x0,…,xn的順序無關(guān)。第十八頁，共99頁。誤差估計(jì)：證明：設(shè) ，則

有n+2個(gè)零點(diǎn)。 根據(jù)中值定理，存在于是 。第十九頁，共99頁。Hermite插值 給定平面上n+1個(gè)插值點(diǎn)(xi,yi,mi),構(gòu)造2n+1次多項(xiàng)式φ(x),滿足φ(xi)=yi,φ’(xi)=mi,i=0,1,…,n.第二十頁，共99頁。單項(xiàng)式

基函數(shù)Lagrange

基函數(shù)第二十一頁，共99頁。誤差估計(jì)：證明：設(shè) ，則

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

于是 。第二十二頁，共99頁。Runge現(xiàn)象：并非插值點(diǎn)取得越多越好。解決辦法：分段插值第二十三頁，共99頁。三次樣條插值 給定平面上n+1個(gè)插值點(diǎn)(xi,yi),構(gòu)造分段三次多項(xiàng)式φ(x),滿足φ(xi)=yi,φ’(x)可微，φ”(x)連續(xù)。第二十四頁，共99頁。作業(yè)一、習(xí)題1第2,4,6,8,10,12,14,16題。作業(yè)二、在半圓 上隨機(jī)選取10個(gè)點(diǎn),構(gòu)造插值多項(xiàng)式,畫出函數(shù)圖像,并比較3種插值方法的計(jì)算誤差。作業(yè)三、思考3種插值系數(shù)之間的關(guān)系。

比較3種插值方法的優(yōu)缺點(diǎn)和應(yīng)用范圍。第二十五頁，共99頁。第2章數(shù)值微分和數(shù)值積分第二十六頁，共99頁。數(shù)值微分差商法 向前差商 向后差商 中心差商第二十七頁，共99頁。插值法

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

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

f’(x)≈φ’(x)第二十八頁，共99頁。例：用中心差商公式計(jì)算f’(xi)。例：用向后差商公式計(jì)算f’’(0.2),

f’’(0.4)。x0.00.4f(x)2.01.9f’(x)f”(x)x0.00.4f(x)0.8187310.9048371.0000001.1051711.221403f’(x)第二十九頁，共99頁。例：設(shè)xi=x0+i*h,i=1,...,n。計(jì)算φ’(xk)。解：第三十頁，共99頁。誤差估計(jì) 前后差商

中心差商

插值微分第三十一頁，共99頁。數(shù)值積分插值法第三十二頁，共99頁。若積分公式對任意m次多項(xiàng)式都取等號，則稱積分公式具有至少m階的代數(shù)精度。插值型積分公式的代數(shù)精度≥n。當(dāng)積分節(jié)點(diǎn)x0,...,xn給定時(shí)，

代數(shù)精度≥n的積分公式唯一。第三十三頁，共99頁。例：設(shè)xi=a+i*h,i=0,...,n,h=(b-a)/n。

計(jì)算Newton-Cotes積分解：第三十四頁，共99頁。特別，當(dāng)n=1,2時(shí)，積分公式分別稱為梯形公式Simpson公式na1a2a3a4a51??21/64/61/631/83/83/81/847/9032/9012/9032/907/90第三十五頁，共99頁。誤差估計(jì)特別，梯形公式和Simpson公式的誤差為 代數(shù)精度＝1

代數(shù)精度＝3第三十六頁，共99頁。復(fù)化數(shù)值積分第三十七頁，共99頁。梯形公式Simpson公式第三十八頁，共99頁。Richardson外推法

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

下的標(biāo)準(zhǔn)正交基。解法1：對任意基作Gram-Schmidt正交化。解法2：對任意度量方陣作相合對角化。解法3：求解正交關(guān)系的線性方程組。解法4：Legendre多項(xiàng)式第四十二頁，共99頁。作業(yè)一、習(xí)題2第1~11題。作業(yè)二、使用各種方法計(jì)算

的值，其中0<x<1，要求誤差<1e-9。第四十三頁，共99頁。第3章曲線擬合的最小二乘法第四十四頁，共99頁。曲線擬合對區(qū)間I上的連續(xù)函數(shù)

f，

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

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

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

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

使 最小。求φ

使 最小。第四十五頁，共99頁。多項(xiàng)式擬合 其中

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

求 使 最小。第四十六頁，共99頁。奇異值分解Moore-Penrose廣義逆矛盾方程組的解第四十七頁，共99頁。其他類型的離散數(shù)據(jù)擬合

第四十八頁，共99頁。作業(yè)一、習(xí)題3第1~5題。作業(yè)二、對下列數(shù)據(jù)，用最小二乘法求形如 的經(jīng)驗(yàn)公式。x0.40.5y0.90590.56320.38350.42440.6730x0.91.0y1.04901.43151.69731.76081.6016第四十九頁，共99頁。第4章非線性方程求根第五十頁，共99頁。問題求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)的根。第五十一頁，共99頁。二分法已知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ε)第五十二頁，共99頁。不動(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ù)線性收斂第五十三頁，共99頁。Newton法（一階Taylor展開） 當(dāng)|f(xk)|<ε或|xk+1-xk|<ε時(shí)，輸出xk+1。 迭代步數(shù)：O(loglogε)二次收斂第五十四頁，共99頁。Newton法（p重根情形）第五十五頁，共99頁。用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).第五十六頁，共99頁。弦截法（線性插值） 當(dāng)|f(xk)|<ε或|xk+1-xk|<ε時(shí)，輸出xk+1。 迭代步數(shù)：O(loglogε)第五十七頁，共99頁。弦截法的收斂速度第五十八頁，共99頁。Newton法解非線性方程組求 的所有復(fù)根

等價(jià)于求x1,…,xn使f(t)=(t-x1)…(t-xn)。第五十九頁，共99頁。其他求根方法 Brent （反插值x=φ(y)）

Halley （二階Taylor展開）

Muller （二次插值）

有理插值……第六十頁，共99頁。作業(yè)一、習(xí)題4第1、3、5、7、8題。作業(yè)二、比較各種求根方法的優(yōu)缺點(diǎn)。第六十一頁，共99頁。第5章解線性方程組的直接法第六十二頁，共99頁。問題：求解n元線性方程組AX=B。方法？速度？精度？存儲(chǔ)？下三角方程組上三角方程組

n(n-1)/2次加減法，n(n+1)/2次乘除法。第六十三頁，共99頁。Gauss消元法解一般方程組

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

(n3+3n2-n)/3次乘除法。第六十四頁，共99頁。追趕法解三對角方程組

3n-3次加減法，5n-4次乘除法。第六十五頁，共99頁。線性方程組解的精度矩陣條件數(shù)第六十六頁，共99頁。Gauss消元法的實(shí)質(zhì)是LU分解存在性？A的順序主子式≠0。唯一性？L1U1=L2U2L1-1L2=U1U2-1對角精確度？A-1b的相對誤差≈(L,U,b)的相對誤差×cond(L)×cond(U)。第六十七頁，共99頁。Dolittle分解Courant分解第六十八頁，共99頁。全/列/行主元分解LDLT分解、Cholesky分解第六十九頁，共99頁。QR分解第七十頁，共99頁。SVD分解Givens旋轉(zhuǎn) Householder反射第七十一頁，共99頁。作業(yè)一、習(xí)題5第1--8題(1)。作業(yè)二、計(jì)算100階Hilbert矩陣H的逆矩陣A以及AH-I的元素平方和。第七十二頁，共99頁。第6章解線性方程組的迭代法第七十三頁，共99頁。Jacobi迭代Gauss-Seidel迭代第七十四頁，共99頁。迭代法解線性方程組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)第七十五頁，共99頁。Jacobi迭代：?=D定理：A行對角優(yōu)、或A列對角優(yōu)

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

Gauss-Seidel迭代收斂。第七十六頁，共99頁。松弛迭代：?=w-1D+L定理：松弛迭代收斂0<w<2定理：A正定且0<w<2

松弛迭代收斂Newton迭代求A-1：Xk+1=2Xk–XkAXk第七十七頁，共99頁。作業(yè)一、145頁習(xí)題3、6、7。作業(yè)二、用迭代法計(jì)算10階Hilbert矩陣H的逆矩陣A以及AH-I的元素平方和。第七十八頁，共99頁。第7章計(jì)算矩陣的特征值

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

計(jì)算2階方陣的SVD第八十六頁，共99頁。作業(yè)一、167頁習(xí)題1(3)、2(2)、3(4)。作業(yè)二、計(jì)算10階Hilbert矩陣的正交相似標(biāo)準(zhǔn)形以及過渡矩陣。第八十七頁，共99頁。第8章常微分方程數(shù)值解第八十八頁，共99頁。問題：求解一階常微分方程的初值問題：解法：化微分方程為積分方程第八十九頁，共99頁。Euler折線法向前Euler公式向后Euler公式 Picard迭代中心Euler公式梯形公式 改進(jìn)的 Euler公式第九十頁，共99頁