數(shù)值計算方法-全套課件

——數(shù)值計算方法數(shù)值計算方法Numerical

Method數(shù)值計算方法1第一章

緒論數(shù)值計算方法4課程簡介什么是數(shù)值計算方法？為什么學習數(shù)值計算方法？數(shù)值計算方法的主要內(nèi)容數(shù)值計算中的誤差誤差的種類及其來源絕對誤差與相對誤差有效數(shù)字與誤差舍入誤差與截斷誤差誤差的傳播與估計算法的數(shù)值穩(wěn)定性非計算機方法數(shù)值計算方法5解析方法簡單問題實際價值有限圖解法結(jié)果準確？三維及以下手工方法計算器速度慢，很容易出現(xiàn)低級錯誤數(shù)值計算方法6工程問題求解的三個階段公式化簡潔表示的基本定律解釋深入分析受限于耗時的求解過程求解用詳細、通常也是復(fù)雜的方法來求解問題計算機時代到來之前公式化深入分析問題與基本定律的關(guān)系解釋易于計算使得能夠進行整體思考和直觀研究，可以對系統(tǒng)的靈敏性和特性進行研究求解易于使用的計算機方法計算機時代學習數(shù)值計算方法的意義數(shù)值計算方法7增強求解問題的技能在理解的基礎(chǔ)上使用一些商品化軟件解決一些軟件所不能解決的問題學習使用計算機的一個有效載體加深對數(shù)學的理解數(shù)值計算方法的內(nèi)容（一）數(shù)值計算方法8方程求根（Roots

of

Equation）f(x)

0xf(x)根數(shù)值計算方法的內(nèi)容（二）數(shù)值計算方法9線性代數(shù)方程組（System

of

LinearAlgebraic

Equations）a11x1

a12

x2

c1a21x1

a22

x2

c2x1x2解數(shù)值計算方法的內(nèi)容（三）數(shù)值計算方法10xx插值（Interpolation）和曲線擬合（CurveFitting）f(x) f(x)數(shù)值計算方法的內(nèi)容（四）數(shù)值計算方法11數(shù)值微分（numerical

differentiation）和數(shù)值積分（numerical

integration）xf(x)baf

(x)dxI

ab面積數(shù)值計算方法的內(nèi)容（五）數(shù)值計算方法12常微分方程（Ordinary

DifferentialEquation

）tydy

y

f(t,

y)dt

t求關(guān)于自變量t的函數(shù)yyi

1

yi

f(ti,yi

)

ttiti+1

t斜率=f(ti

,yi)課堂教學內(nèi)容緒論

(1周)非線性方程求根

(1周)求解線性方程組的數(shù)值方法

(2周)插值和曲線擬合

(1周)數(shù)值微分和數(shù)值積分

(1周)常微分方程數(shù)值解

(1周)19數(shù)值計算方法教學安排理論13：15～15：40上機（助教負責）四次海洋大樓機房刷校園卡20數(shù)值計算方法考核方式平時成績（70%）課堂（10%）

+上機（10%）上機作業(yè)提交時間 當天24:00每周作業(yè)（50%）提交時間：每次布置作業(yè)后一周內(nèi)，注意截止時間提交到課程網(wǎng)站，程序+報告文檔，一個壓縮文件期末作業(yè)（30%）自選題目 截止提交時間

6月26日24:00利用數(shù)值方法解決問題專業(yè)領(lǐng)域、以往課程、社會生活解析解？數(shù)值解？分析212016/5/1數(shù)值計算方法考核方式必須遵守學術(shù)道德規(guī)范，鼓勵相互之間進行討論，但提交的作業(yè)必須獨立完成。杜絕抄襲！23數(shù)值計算方法作業(yè)要求完整性程序+文檔報告要求問題分析程序（算法、必要的注釋）結(jié)果分析排版、格式（清晰、美觀）22數(shù)值計算方法作業(yè)題例數(shù)值計算方法19在對汽車、機器人以及其他運動器械的控制時，

經(jīng)常需要獲得其移動距離的數(shù)據(jù)通過對于一連串采樣點（

即時速度）

的插值，

得到速度關(guān)于時間的函數(shù)，

再對于速度進行積分，

即可得到對象所運動的距離總長度為5451.24米作業(yè)題例——西湖面積數(shù)值計算方法20作業(yè)題例——上海世博會參觀人數(shù)過千萬時間點數(shù)值計算方法21作業(yè)題例——手數(shù)值計算方法22作業(yè)題例——任意球數(shù)值計算方法23數(shù)學建模與工程問題求解數(shù)值計算方法24問題定義數(shù)學模型數(shù)值或圖形結(jié)果實現(xiàn)理論數(shù)據(jù)問題求解工具：計算機、統(tǒng)計學、數(shù)值方法、圖解法等社會應(yīng)用：調(diào)度、最優(yōu)化、通信等等數(shù)學模型（Mathematical

Model）數(shù)值計算方法25用數(shù)學語言來表達物理系統(tǒng)或過程本質(zhì)特征的公式或方程。因變量=f(自變量，參數(shù)，強制函數(shù))因變量（dependent

variable）：用來刻畫系統(tǒng)行為或狀態(tài)的特征量；自變量（independent

variable）：通常為維度，如時間和空間，系統(tǒng)的行為是用自變量來確定的；參數(shù)（parameter）：反映系統(tǒng)的性質(zhì)或組成；強制函數(shù)（forcing

function）：外部對系統(tǒng)施加的影響。一個簡單的數(shù)學模型——牛頓第二定律數(shù)值計算方法26F=ma

a=F/ma為因變量，表示了系統(tǒng)的行為；F為強制函數(shù)；m為表示系統(tǒng)性質(zhì)的參數(shù)；在這種簡單的情況下，沒有自變量，沒有涉及到加速度a在隨時間或空間的變化。物理世界中數(shù)學模型的幾個典型特點：用數(shù)學語言描述自然過程或系統(tǒng)；代表了一種理想情況，或是對現(xiàn)實的簡化。即忽略了自然過程的不重要的細節(jié)，而集中于自然過程的本質(zhì)特征；得到的是一個可以重現(xiàn)的結(jié)果，可以用來做預(yù)測。降落傘問題（Falling

ParachutistProblem）數(shù)值計算方法27確定降落傘的最后速度加速度表示為速度的變化率FUFDdv

Fdt m如果凈受力為正，物體加速運動；如果為負，物體減速運動；如果為0，物體速度不變。假定向下的力為正，F(xiàn)D

mg FU

cvc為比例系數(shù)，稱為阻力系數(shù)（dragcoefficient(kg/s)）。參數(shù)c說明了下降物體的特征，如形狀或表面的粗糙程度。降落傘問題（Falling

ParachutistProblem）數(shù)值計算方法28模型——微分方程（differential

equation）dv

mg

cv

g

cvdt m m若初始時處于靜止狀態(tài)（t=0時，v=0），可得gmcv(t)

1

e

(c

/

m)t

v(t)為因變量；t為自變量；c和m為參數(shù)；g為強制函數(shù)。問題：從靜止熱氣球中彈出一個質(zhì)量為68.1kg的降落傘，阻力系數(shù)等于12.5kg/sv(t)

9.8

68.1

1

e

(12.5

/

68.1)t

53.39

1

e

0.18355t

12.5降落傘問題（Falling

ParachutistProblem）數(shù)值計算方法29t(s)v(m/s)00.00216.40427.77635.64841.091044.871247.48

53.39246810121400504030201060t(s)解析解或精確解但許多模型不能精確地求解數(shù)值方法——對數(shù)學問題進行變換，使得它可以用算術(shù)運算來求解v(m/s)終速數(shù)值計算方法30降落傘問題（Falling

ParachutistProblem）數(shù)值方法：在時刻ti處導(dǎo)數(shù)的有限差商近似dv

v

v(ti

1)

v(ti

)dt

tti

1

tidtdv

lim

v

t

0

t

iv(t

) tcmi

1 ii

1 i

v(t )

v(t

)

g

t

t(s)v(m/s)00.00219.6432.00639.86844.821047.971249.96

/1053.39歐拉法024681012140102030405060t(s)v(m/s)數(shù)值解解析解終速用直線段來近似表示連續(xù)的曲線函數(shù)，因此兩者之間存在一定差異?？梢杂酶〉牟介L使誤差減小——計算量與精度之間的權(quán)衡數(shù)值計算方法數(shù)值計算方法31數(shù)值計算方法是一門根據(jù)計算機特點，研究通過計算機求工程問題滿足精度要求的近似解的學科。將所欲求解的數(shù)學模型（數(shù)學問題）簡化成一系列算術(shù)運算和邏輯運算，以便在計算機上求出問題的數(shù)值解，并對算法的收斂性、穩(wěn)定性和誤差進行分析、計算。算法數(shù)值計算方法32基本運算和運算順序的規(guī)定所組成的整個解題方案和步驟。一般可以通過框圖（流程圖）來較直觀地描述算法的全貌。選擇合適的算法是整個數(shù)值計算中非常重要的一個環(huán)節(jié)。算法的選擇數(shù)值計算方法33例：計算多項式的值直接計算，再逐次相加，共需只要n次乘法和n次加法即可。（霍納Horner1819年）P(x)

axn

a xn

1

ax

an n

1 1 0iiax(i

0,1,2,

,

n)1

2

(n

1)

n

n(n

1)2次乘法和n次加法。秦九韶（我國宋朝數(shù)學家）算法（1247年）P(x)

((

((an

x

an

1

)x

an

2

)x

a2

)x

a1

)x

a0算法數(shù)值計算方法34算法的優(yōu)劣直接影響計算的速度和效率對于小型問題，計算速度和占用計算機內(nèi)存的多寡似乎意義不大，但對復(fù)雜的大型問題卻起著決定性作用。不合適的算法還會由于計算機計算的近似性和誤差的傳播、積累直接影響到計算結(jié)果的精度，甚至影響到計算的成敗?！惴ǖ臄?shù)值穩(wěn)定性第一章

緒論數(shù)值計算方法35課程簡介什么是數(shù)值計算方法？為什么學習數(shù)值計算方法？數(shù)值計算方法的主要內(nèi)容數(shù)值計算中的誤差誤差的種類及其來源絕對誤差與相對誤差有效數(shù)字與誤差舍入誤差與截斷誤差誤差的傳播與估計算法的數(shù)值穩(wěn)定性誤差的種類數(shù)值計算方法36舍入誤差（round-off

error）由于計算機只能表示有限位數(shù)的量而引起的截斷誤差（truncation

error）由于數(shù)值方法可能運用近似方法表示準確數(shù)值運算或數(shù)量而引起的不與數(shù)值方法本身直接相關(guān)的誤差粗差形式化或模型誤差數(shù)據(jù)不確定性誤差有效數(shù)字（significant

digit）數(shù)值計算方法37為了正式規(guī)定數(shù)值的可靠程度一個數(shù)的有效數(shù)字是指可以放心使用的那些數(shù)字有效數(shù)字對應(yīng)于確定數(shù)字和一個估計數(shù)字的總位數(shù)數(shù)值方法得到的是近似解，所以必須建立準則來規(guī)定近似結(jié)果的可信度。建立準則的一種方法是基于有效數(shù)字實現(xiàn)的，例如：如果有4位有效數(shù)字是正確的，可能就認定得到的近似結(jié)果是可以接受的。計算機只能保留有限個有效數(shù)字。保留有效數(shù)字后被省略的部分稱為舍入誤差。如：

3.141592653589793238462643

準確度（accuracy）與精確度（precision）數(shù)值計算方法38準確度計算值或測量值與真值接近的程度精度或精確度各計算值或測量值相互之間的集中程度準確度（accuracy）與精確度（precision）——射擊的例子數(shù)值計算方法39準確度增加精確度增加(a)

既不準確也不精確(b)

準確但不精確(c)

不準確但精確(d)

既準確也精確數(shù)值計算方法40誤差的定義數(shù)值誤差源于用近似方法表示準確的數(shù)學運算和準確的數(shù)量數(shù)值誤差包括截斷誤差和舍入誤差當用近似方法表示準確數(shù)學過程時會出現(xiàn)截斷誤差當用有限個有效數(shù)字表示準確的數(shù)時會引起舍入誤差絕對誤差真值=近似值+誤差 誤差=真值-近似值相對誤差E

x

x*rx

E

100%絕對誤差可正可負，一般E的準確值很難求出?？捎谜嬷档淖顑?yōu)估計值代替真值，或者給出誤差的一個上界

(x*)（誤差限）。當x=0時，相對誤差無意義，準確值x往往未知，故常用x*代替x，相對誤差限為

(x*)/|

x*

|。誤差計算——例1數(shù)值計算方法41問題：假設(shè)對一座橋梁和一個鉚釘?shù)拈L度進行了測量，測量的結(jié)果分別為9999cm和9cm。如果真值分別為10000cm和10cm，計算兩種情況下的真誤差和真相對誤差解：(a)橋梁的真誤差為鉚釘?shù)恼嬲`差為(b)橋梁的相對誤差為鉚釘?shù)南鄬φ`差為Et

10000

9999

1cmEt

10

9

1cm10000r

1

100%

0.01%10r

1

100%

10%盡管兩個絕對誤差都是1cm，但測量鉚釘?shù)南鄬φ`差要大得多，因此，我們對橋梁的測量已經(jīng)夠準確了，但對鉚釘?shù)墓烙嬙谀撤N程度上偏離了希望值。誤差——例2數(shù)值計算方法42已知

=3.1415926

，若取近似數(shù)為

x*

3.14

，則E

x*

0.0015926

，E

0.002

(x*

)

為

x*

的誤差限，相*rx*

(x*)對誤差限為

(x)

0.0007通常在x有多位數(shù)字時，若取前有限位數(shù)的數(shù)字作為近似值，都采用四舍五入原則，他們的誤差限都不超過近似數(shù)x*末位數(shù)的半個單位，即

3.14

1

10

2

3.1416

1

10

42 2有效數(shù)字與誤差的關(guān)系數(shù)值計算方法43,其中每個ai（i=1，2，

，n）均為0，1，2，

，9中的一個數(shù)字，且a1≠0，如果則稱x*近似x有n位有效數(shù)字。如果x*具有n位有效數(shù)字，則其相對誤差限為定義：設(shè)x*是x的一個近似數(shù)，表示為x*

10k

0.a1a2

an2x

x*

1

10k

n近似數(shù)的有效數(shù)字越多，相對誤差限就越小，反之亦然。*11r2a

(x)

10

(n

1)迭代方法的誤差估計數(shù)值計算方法44當前迭代結(jié)果的誤差：

當前近似值

前一近似值

100%當前近似值a

采用絕對值是否小于預(yù)先設(shè)定好的容限

s

a

s如果下面的準則成立，則一般可以保證至少n位有效數(shù)字是正確的：

(0.5

102

n

)%s數(shù)值計算方法迭代方法的誤差估計——例45問題：指數(shù)函數(shù)可以用下式表示（麥克勞林級數(shù)展開）計算的值，每加入一個新項后計算真誤差和近似百分比相對誤差。真值為，直到近似誤差小于2 3!xx2 x3xnn!e

1

x

e0.5e0.5

1.648721

s，

s

必須符合3位有效數(shù)字的要求。項數(shù)結(jié)果

t(%)

a(%)1139.321.59.0233.331.6251.447.6941.6458333330.1751.2751.6484375000.01720.15861.6486979170.001420.0158

(0.5

102

3)%

0.05%解：誤差準則：

s第一章

緒論數(shù)值計算方法46課程簡介什么是數(shù)值計算方法？為什么學習數(shù)值計算方法？數(shù)值計算方法的主要內(nèi)容數(shù)值計算中的誤差誤差的種類及其來源絕對誤差與相對誤差有效數(shù)字與誤差舍入誤差與截斷誤差誤差的傳播與估計算法的數(shù)值穩(wěn)定性舍入誤差數(shù)值計算方法47數(shù)的計算機表示計算機中的算術(shù)運算數(shù)的計算機表示數(shù)值計算方法48浮點表示例：1/34=0.029411765

以十進制浮點形式存儲，并且只準許4個十進制為可用。 0.0294

1000.2941

10-1可以多保存一個有效數(shù)字尾數(shù) 基數(shù)r

m

be指數(shù)b1

m

1尾數(shù)符號有符號指數(shù)尾數(shù)僅保存了有限的有效數(shù)字，因此，會引入舍入誤差。歸一化2015/5/10數(shù)的計算機表示數(shù)值計算方法49例：對于一個用7位的字存儲信息的計算機，建立一個假定的浮點數(shù)集合。用數(shù)的第一位表示符號位，接著的3位表示指數(shù)的符號和大小，最后的3位存放尾數(shù)。最小可能的正數(shù)為0111100數(shù)的符號指數(shù)的符號指數(shù)的大小尾數(shù)的大小最小可能的正浮點數(shù)100.5

2

3

(0.0625)增大100111101

(1

2

1

0

2

2

1

2

3

)

2

3

(0.078125)100111110

(1

2

1

1

2

2

0

2

3

)

2

3

(0.093750)100111111

(1

2

1

1

2

2

1

2

3

)

2

3

(0.109375)相鄰兩數(shù)間隔為0.015625100110100

(1

2

1

0

2

2

0

2

3

)

2

2

(0.125000)100110101

(1

2

1

0

2

2

1

2

3

)

2

2

(0.156250)100110110

(1

2

1

1

2

2

0

2

3

)

2

2

(0.187500)100110111

(1

2

1

1

2

2

1

2

3

)

2

2

(0.218750)相鄰兩數(shù)2015/5/10間隔為0.03125100011111

(1

2

1

1

2

2

1

2

3

)

23

(7)最大的數(shù)21 20 2-1 2-2 2-3數(shù)的計算機表示數(shù)值計算方法50溢出 070在0值附近的一個“洞”處會下溢x-

xx+

x

x/2

x/2舍入x-

x

x舍去2015/5/102015/5/10數(shù)值計算方法51數(shù)的計算機表示僅能表示有限范圍內(nèi)的數(shù)使用可接受范圍以外的數(shù)會導(dǎo)致溢出。不能表示非常小的數(shù)，在0與第一個正數(shù)之間存在一個“洞”。在可接受數(shù)的范圍內(nèi)也只能表示有限個數(shù)無理數(shù)以及不與該集合中的數(shù)對應(yīng)的有理數(shù)都不可能準確地表示——量化誤差舍入（rounded

floating-point

representation）和舍去（choppedfloating-point

representation）有效數(shù)字足夠多的情況下，總的舍入誤差通?？梢院雎圆挥?。數(shù)之間的間隔隨著數(shù)大小的增加而增大量化誤差與數(shù)的大小成比例相對量化誤差：舍去的情況 舍入的情況

為機器精度x

x

x

x 2

b1

t尾數(shù)有效數(shù)字個數(shù)數(shù)的計算機表示數(shù)值計算方法52機器精度：采用上例中的浮點系統(tǒng)，b=2，t=3，則

=21-3=0.25。對于舍去方法，量化誤差小于0.25。最大相對誤差2015/5/10誤差幅度與量化誤差的相關(guān)性有很多實際的應(yīng)用：測試兩個數(shù)是否相等在迭代過程中，當對一個量的收斂性或迭代過程是否中止，測試它們的差是否小于某個可接受的容限。用相對誤差?？捎脵C器精度作為停止或收斂準則。數(shù)的計算機表示數(shù)值計算方法532015/5/10測試機器精度的偽代碼Epsilon=1DOif(epsilon+1<=1)

EXITepsilon=epsilon/2ENDDOepsilon=epsilon*2數(shù)的計算機表示數(shù)值計算方法542015/5/10多數(shù)計算機上的有效數(shù)字數(shù)目足夠滿足大多數(shù)工程計算的需要擴展精度雙精度消除舍入誤差的影響代價：更多的內(nèi)存和計算時間計算機中的算術(shù)運算數(shù)值計算方法55通用算術(shù)運算（加、減、乘、除）——有效數(shù)字丟失當兩個浮點數(shù)相加時，需要對較小的數(shù)的尾數(shù)進行調(diào)整，使兩個數(shù)

0.0001

103=0.1000

100，之后的計算會把后面的3個0都作為有效數(shù)字當兩個數(shù)非常接近時，會產(chǎn)生非常大的計算誤差。乘法：指數(shù)相加，尾數(shù)相乘。兩個n位尾數(shù)相乘得到2n位計算結(jié)果。0.1363

103

0.6423

10-1=0.08754549

102

0.8754

101除法：尾數(shù)相除，指數(shù)相減。然后對結(jié)果進行歸一化和舍去處理。的指數(shù)相同0.1557.101例：0.1557

101+0.4381

10-10.004381.101將結(jié)果舍去處理后得0.1600

101 0.160081.101減法的執(zhí)行過程類似，

0.0995

102=0.9950

1010.7642.1030.3641.102-0.7641.103-0.2686.1020.0001.1030.0955.1022015/5/10計算機中的算術(shù)運算數(shù)值計算方法562015/5/10大規(guī)模計算即使單個計算的舍入誤差可能很小，但在大量計算過程中的累積效應(yīng)可能非常嚴重。問題：對一個數(shù)求和100000次，對數(shù)1以單精度方式求和，對數(shù)0.00001分別以單精度和雙精度方式求和。結(jié)果：對1進行單精度求和得到期望的結(jié)果，但對0.00001進行單精度求和的結(jié)果卻具有較大的偏差，但當對0.00001進行雙精度求和時，計算誤差顯著減小。根源：量化誤差。因為整數(shù)1可以在計算機中準確地表示，所以對1可以精確地求和運算。0.00001不能在計算機中準確地表示，只能對其進行量化處理時，得到一個與真值略微不同的值，盡管這是一個非常微小的差異，對于小量計算可以忽略，但在重復(fù)進行大量計算后，這個誤差會不斷累積。在雙精度情況下，量化誤差要小得多，可以得到改善。在上述迭代操作中，所有誤差具有相同的正負號。很多情況下，誤差的符號

以隨機模式不斷交替的，經(jīng)常相互抵銷了，但有些情況下，這些誤差沒有被抵銷掉，就會得到誤差較大的結(jié)果。計算機中的算術(shù)運算數(shù)值計算方法57大數(shù)和小數(shù)相加例：一個小數(shù)0.0010和一個大數(shù)4000相加，使用一個假想的計算機，具有4位尾數(shù)和1位指數(shù)，對較小的數(shù)進行調(diào)整，使其指數(shù)與較大的數(shù)相匹配。將結(jié)果進行舍去處理得0.4000.104可以不執(zhí)行這個加法！無窮級數(shù)求和：初始項通常大于后面的項反向求和：以升序而不是降序?qū)墧?shù)求和當n趨于無窮時，無窮級數(shù)收斂于

4/90。采用單精度表示，編寫一個程序計算n=10000時f(n)的值，分別按從i=1到10000和i=10000到1的順序計算，對比誤差并分析結(jié)果。0.4000.1040.0000001.1040.4000001.10412015/5/10i

1i4nf(n)

∑計算機中的算術(shù)運算數(shù)值計算方法58減性抵銷——兩個幾乎相等的浮點數(shù)相減時所引起的舍入誤差例：二次求根公式當時，分子可能非常小?？梢杂秒p精度或變換公式或先計算較大的根，再根據(jù)計算較小的根。

b

b2

4acx1,2

2ab2

4ac1,22x

2c b

b

4ac1

22015/5/10axx

c問題：當a=1，b=3000.001，c=3時，分別以單精度和雙精度計算方程的根。（真實根為x1=-0.001，x2=-3000）計算機中的算術(shù)運算數(shù)值計算方法59拖尾效應(yīng)（smearing）在求和過程中，如果某一項的值大于和值本身時，就會出現(xiàn)拖尾效應(yīng)。在符號交替的級數(shù)中會出現(xiàn)這種現(xiàn)象。問題：指數(shù)函數(shù)以下面無窮級數(shù)的形式給出：分別計算x=10和x=-10時的函數(shù)值，研究其舍入誤差。在不斷地進行加減運算時，抵銷了大量的有效數(shù)字。其他計算策略或擴展精度。內(nèi)積使用擴展精度y

ex2 3!x2 x3y

1

x

n2015/5/10

xiyi

x1y1

x2y2

xn

yni

1指數(shù)函數(shù)運行結(jié)果數(shù)值計算方法602015/5/10x=10x=-10itermsumitermsum011011110111-10-925061250413166.6667227.66667183-166.6667-125.66667184416.6667644.3333744416.66672915833.33341477.6667485-833.3334-542.333374

270.091836922026.417968841280.032798922026.451171942290.0113122026.462890643-1.6552107e-0101.1033645569114e-04300.0037722026.4667969443.7618422e-0111.1033649207093e-04310.001216122026.4687545-8.3596498e-0121.1033648479497e-04Exact

value22026.465794806718Exact

value0.000045399929762截斷誤差與泰勒級數(shù)數(shù)值計算方法61截斷誤差是由于用近似過程代替準確過程而產(chǎn)生的誤差。利用泰勒級數(shù)了解截斷誤差dv

v

v(ti

1)

v(ti

)dt

tti

1

ti近似真導(dǎo)數(shù)值2015/5/10泰勒定理數(shù)值計算方法62在包含a和x的區(qū)間上，如果一個函數(shù)f及其直至n+1階導(dǎo)數(shù)都是連續(xù)的，那么該函數(shù)在x處的值可以表示為：n

(x

a)

Rnf

(a)2!f(x)

f(a)

f(a)(x

a)

f(n)

(a)n!2(x

a)

f (t)dtn!n

1x

x

t

nRn

a泰勒定理表明：任何光滑的函數(shù)都可以用多項式來逼近積分形式的余項n

1Rn

x

a

f

n

1

(

)

n

1

!應(yīng)用中值定理，可以得到余項的拉格朗日形式：a和x之間的一個點2015/5/10泰勒級數(shù)數(shù)值計算方法630階近似(zero-order

approximation)一階近似(first-order

approximation)完整的泰勒展開f(xi

1)

f(xi

)f(xi

1)

f(xi)

f

(xi)(xi

1

xi

)ii

f

2!)

f

(x )

f(x)

f

(x

)(x

xf

(n)2 n(xi

1

xi

1 i i i

1)

(xi

1

xi

)

Rnn!f

n

1

(

)n

1Rn

n

1

!

xi

1

xi

存在一個值可以給出準確的誤差表示定義步長h

xi

1

xinhn

Rf

(n)n!f

2f(xi

1)

f(xi)

f

(xi)h

2!

h

f

n

1

(

)2015/5/10n

1Rn

n

1

!

h泰勒級數(shù)展開的余項數(shù)值計算方法642015/5/10泰勒級數(shù)的多項式逼近數(shù)值計算方法65

2015/5/10例：當

xi

0,

h

1時，用零階到四階泰勒級數(shù)展開預(yù)測函數(shù)f

(x)

0.1x4

0.15x3

0.5x2

0.25x

1.2在xi

1

1處的函數(shù)值：解：

f

(0)

1.2n=0，

f

(xi

1

)

1.2Et

0.2

1.2

1.0

n=1，

f

(0)

0.25f

(xi

1

)

1.2

0.25hf(1)

0.95Et

0.2

0.95

0.75n=2，

f

(0)

1.0i

1f

(x )

1.2

0.25h

0.5h2f(1)

0.45tE

0.2

0.45

0.25泰勒級數(shù)的多項式逼近數(shù)值計算方法66四階級數(shù)的泰勒級數(shù)展開將得到一個準確的估計結(jié)果：f

(x)

1.2

0.25h

0.5h2

0.15h3

0.1h452015/5/10f(5)(

)5!R4

h

0通常，n階多項式的n階泰勒級數(shù)展開得到的結(jié)果是準確的。對于其他連續(xù)可微函數(shù)，如指數(shù)函數(shù)和正弦函數(shù)，有限級數(shù)項是不可能得到準確結(jié)果的。每增加一項將使近似結(jié)果得到一定的改進，但改進程度不顯著。多數(shù)情況下，泰勒級數(shù)展開的實際值只需要包含少數(shù)幾項就可以得到非常接近真值的近似結(jié)果，對于實際應(yīng)用來說足夠了。泰勒級數(shù)展開的逼近誤差數(shù)值計算方法67利用余項估計需要多少項及步長才能得到足夠接近真值的近似值？

nhf

n

1

(

)n

1R

n

1!n2015/5/10R

O(hn

1

)誤差與步長的n+1次方成比例。如果誤差的量級為

O(h)，那么步長減半就會使誤差也減半。如果誤差的量級為

O(h2

)，那么步長減半就會使誤差變?yōu)樵瓉淼乃姆种?。一般地，假定截斷誤差隨泰勒級數(shù)項數(shù)的增加而減小。在許多情況下，如果h足夠小，一階、二階以及其他低階項通常不成比例地占估計值的絕大部分。因此，只需要少數(shù)項就可以獲得一個足夠精確的估計值。2015/5/10數(shù)值計算方法68泰勒級數(shù)展開的逼近誤差例：利用泰勒級數(shù)展開，基于f(x)=cos(x)在

xi

/4

處的函數(shù)值和導(dǎo)數(shù)值，用n=0~6共7項來逼近

xi

1

/3

的值。解：

h

/

3

/

4

/12階數(shù)nf(n)

x

f

/

3

百分比相對誤差0cosx0.707106781-41.41-sinx0.512986659-4.42-cosx0.4977544910.4493sinx0.4998691472.62

10-24cosx0.500007551-1.51

10-35-sinx0.500000304-6.08

10-56-cosx0.4999999882.44

10-6f

/3

0.5增加更多的項，誤差的改進可以忽略不計。利用泰勒級數(shù)估計截斷誤差數(shù)值計算方法69降落傘問題：將v(t)展開成泰勒級數(shù)截去一階導(dǎo)數(shù)項以后的各項可得：ni

i

1 i(t

t)2

Ri2!v(t

)v(ti

1

)

v(ti

)

v

(ti

)(ti

1

t

)

v(ti

1

)

v(ti

)

v

(ti

)(ti

1

ti

)

R1v

(t)

v(ti

1 )

v(ti )

R1 i t

t t

ti

1 i i

1 i一階逼近 截斷誤差f

n

1

(

)n

1Rn

n

1

!

ht

i

1 ii

1 iR1t

t2!

v

(

)

t

O

t

t

2015/5/10i

1 ii

1 iR1t

t導(dǎo)數(shù)的近似誤差與步長成比例。如果將步長減半，則導(dǎo)數(shù)值的誤差也減半。0.5122.502468101214161.5xf(x)m=4m=3m=2m=1非線性與步長對泰勒級數(shù)逼近的影響數(shù)值計算方法70

一階泰勒級數(shù)展開：問題：

f

(x)

xm

,

m

1,

2,

3,4

x

[1,

2]ii

1 if

(x )

f(x)

mxm

1h22015/5/10341

i

2!

i

3!

i

4!f(3)(x

)f(4)(x

)R

f

(x

)h

h

h

隨著函數(shù)非線性程度的增大，一階泰勒級數(shù)逼近的誤差增大。隨著步長的減小，一階泰勒級數(shù)逼近的誤差減小。第一章

緒論數(shù)值計算方法712015/5/10課程簡介什么是數(shù)值計算方法？為什么學習數(shù)值計算方法？數(shù)值計算方法的主要內(nèi)容數(shù)值計算中的誤差誤差的種類及其來源絕對誤差與相對誤差有效數(shù)字與誤差舍入誤差與截斷誤差誤差的傳播與估計算法的數(shù)值穩(wěn)定性誤差傳播——單變量函數(shù)數(shù)值計算方法72假設(shè)一個函數(shù)f(x)，設(shè)

x

是x的近似值，估計x和

x

的差異對函數(shù)值的影響，即

f

x

f

x

f

x

如果f(x)連續(xù)可微，用泰勒級數(shù)計算逼近

f

x

的

f

x

2舍去二階及二階以上的項，并重新整理：f

x

f

x

f

x

x

x

f

x

x

x

2

f

x

f

x

f

x

x

x

或函數(shù)值的誤差估計函數(shù)的導(dǎo)數(shù)自變量的誤差估計值

f

(x

)

f

(x

) x

x

2015/5/10一階誤差傳播的圖形描述數(shù)值計算方法73xf(x)xx

真誤差估計誤差

x

x

x

2015/5/10單變量函數(shù)的誤差傳播數(shù)值計算方法74解：問題：給定一個值

x

2.5 ，其誤差為

x

0.01

，估計由此導(dǎo)致的函數(shù)值

f

(x)

x3

的誤差。

f

x

f

x

x

x

3(2.5)2

(0.01)

0.1875由于2015/5/10f(2.5)

15.625可以預(yù)測：

f

(2.5)

15.625

0.1875誤差傳播——多變量函數(shù)數(shù)值計算方法75一個具有兩個變量u和v的函數(shù)，泰勒級數(shù)可以寫為舍去二階和高階項多變量函數(shù)22iiui

1 i

1 i ii

1i

1f

(u ,

v )

f(u,v)

f

(u

u)

f

(v

v

)

u

v

2

f

2

f 2

1

2

f

2!

(ui

1

ui

)

2

u

v(ui

1

ui)(vi

1

vi)

v2(vi

1

vi)

f(u

,v

)

f

u

f

v

u

v12015/5/102121 2 nnn

x

x

x

f(x

,x

,

,x

)

f

x

f

x

f

x

一般數(shù)學運算的誤差傳播關(guān)系數(shù)值計算方法76運算估計誤差加法

(u

v

)

u

v

減法

(u

v

)

u

v

乘法

(u

v

)u

v

v

u

除法

u

v

u

v

v

u

v

22015/5/10誤差傳播——例數(shù)值計算方法77初始誤差可穩(wěn)定傳播或不穩(wěn)定傳播例：用無限精度算法結(jié)合下列3個方案可遞歸生成序列中的各項值。

1/

3n

n

002015/5/100 10 13(2)3 333 3nnnn

1n

1n

2n

1n

2(1) r

1,r

1

rp

1,

p

1

,

p

4

p(3) q

1,

q

1

,

q

10

q,

n

1,

2,

1

p ,

n

2,

3,

q ,

n

2,

3,

誤差傳播——例數(shù)值計算方法78(2)差分方程的通解是pn

A(1/3)

Bn驗證如下：3 32015/5/103 33 33 3n n3nn

1 n

2n

1An

21

p4

p

4

A

B

1

B

4

3

A

4

1

B

A1

B

3 3

pn設(shè)A=1且B=0，可得到期望的序列。誤差傳播——例數(shù)值計算方法79(3)差分方程的通解是pn

A(1/3)

B3n n驗證如下：3 3 32015/5/1033 3n n3nAn

1n

2n

1 n

2n

1n

2

10

p

10

Ap

B3

B3

10

9

A

10

1

3n

2

B

A

1

B

3n

pn設(shè)A=1且B=0，可得到期望的序列。誤差傳播——例數(shù)值計算方法80

試研究每個算法的誤差傳播情況。例：用下列方法求出序列

xn

13n

的近似值。02015/5/103333n0 1 nn

1n

1n

20 1 n n

1 n

2(1) r

0.99996,r

1

r(2) p

1,

p

0.33332,

p

4

p(3) q

1,

q

0.33332,

q

10

q,

n

1,

2,

1

p ,

n

2,

3,

q ,

n

2,

3,

r0初始誤差為0.00004，p1,

q1

初始誤差為0.00001333，誤差傳播——例數(shù)值計算方法81nxnrnxn

–rn(10-4)pnxn

–pn(10-4)qnxn

–qn01.00000000000.99996000000.4000001.00000000000.0000001.00000000000.000000000010.33333333330.33332000000.1333330.33332000000.1333330.33332000000.000013333320.11111111110.11110666670.0444440.11109333330.1777780.11106666670.000044444430.03703703700.03703555560.0148150.03701777780.1925930.03690222220.000134814840.01234567900.01234518520.0049380.01232592590.1975310.01194074070.000404938350.00411522630.00411506170.0016460.00409530860.1991770.00290024690.001214979460.00137174210.00137168720.0005490.00135176950.199726-0.00227325100.003644993170.00045724740.00045722910.0001830.00043725650.199909-0.01047775030.010934997780.00015241580.00015240970.0000610.00013241880.199970-0.03265258340.032804999290.00005080530.00005080320.0000200.00003080630.199990-0.09836419450.0984149997100.00001693510.00001693440.000007-0.00000306460.199997-0.29522806480.29524499992015/5/10012345678910012x10-5x-r123456789100012x10-5x-p12345678910000.20.4x-q誤差傳播——例數(shù)值計算方法82誤差是穩(wěn)定的，且按指數(shù)級遞減誤差是穩(wěn)定的，但誤差占支配地位誤差是不穩(wěn)定的，按指數(shù)級增長2015/5/10第一章

緒論數(shù)值計算方法832015/5/10課程簡介什么是數(shù)值計算方法？為什么學習數(shù)值計算方法？數(shù)值計算方法的主要內(nèi)容數(shù)值計算中的誤差誤差的種類及其來源絕對誤差與相對誤差有效數(shù)字與誤差舍入誤差與截斷誤差誤差的傳播與估計算法的數(shù)值穩(wěn)定性穩(wěn)定性與條件數(shù)數(shù)值計算方法84f

x

f

x

f

x

x

xxPf

x

K

xf

x

f

x

f

x

f

x

x x

xKP

1病態(tài)問題y=f(x)2015/5/10xx

yy

x

x(1

)y

y(1

)穩(wěn)定性與條件數(shù)數(shù)值計算方法85一個算法如果原始數(shù)據(jù)有誤差，而計算過程舍入誤差不增長，則稱此算法是數(shù)值穩(wěn)定的，否則，若誤差增長，則稱算法是不穩(wěn)定的（numerically

unstable）。（輸入值的不確定性通過數(shù)值方法在總體上是放大的）條件數(shù)（condition

number）定義為相對誤差之比：f(x)與x的相對誤差分別為條件數(shù)為條件數(shù)體現(xiàn)了x的不確定性被f(x)放大程度。如果條件數(shù)等于1，表示函數(shù)的相對誤差等于x的相對誤差，如果條件數(shù)大于1，表示相對誤差被放大了，而條件數(shù)小于1，表示相對誤差減小了。條件數(shù)非常大(大于等于10)的函數(shù)稱為病態(tài)（ill-conditioned）函數(shù)。f(x)

f(x

)

f

x

x

x

f

(x

) f

(x

)x

x

x

x

f

x

f

(x

)2015/5/10問題條件數(shù)與算法條件數(shù)數(shù)值計算方法86例：問題條件數(shù)f

(x)

x2

1

xx

100

f

(x)

0.5

10

2xf

(x)

1x2

1f

x

f

x

f

x

1

0.1

103

0算法A：4位有效數(shù)字x

0.1

103

f

(x

)

(0.1000

0.00001)

105

x

x

1101

t

110

3x 2 2KP

1

KA

2000算法條件數(shù)，改善方法：提高精度，重寫算法算法B：f

(x)

1 x2

1

x

0.5

10

210.1

103

0.1

103f(x

)

0

KA

0

12015/5/10(當x>>1時)總的數(shù)值誤差數(shù)值計算方法872015/5/10截斷誤差和舍入誤差之和通常，最小化舍入誤差的方法是增加計算機的有效數(shù)字個數(shù)縮短步長使截斷誤差減小但縮短步長可能導(dǎo)致減性抵銷或增加計算量，使舍入誤差增大大多數(shù)計算機可以表示足夠多的有效數(shù)字，因此舍入誤差不會占主導(dǎo)地位避免誤差危害的原則數(shù)值計算方法882015/5/10選擇數(shù)值穩(wěn)定的計算方法，避開不穩(wěn)定的算式。注意簡化計算步驟及公式，設(shè)法減少運算次數(shù)；選用運算次數(shù)少的算式，尤其是乘方冪次要低，以減少舍入誤差，同時可節(jié)約計算機的機時。合理安排計算順序，防止大數(shù)“淹沒”小數(shù)。多個數(shù)相加時，最好從絕對值最小的數(shù)到絕對值最大的數(shù)依次相加；多個數(shù)相乘時，最好從有效位數(shù)最多的數(shù)到有效位數(shù)最少的數(shù)依次相乘。避免兩相近數(shù)相減。避免用絕對值很小的數(shù)作為除數(shù)。第一部分

總結(jié)（一）數(shù)值計算方法892015/5/10數(shù)學問題的類型數(shù)值方法的特點穩(wěn)定性準確性與精確性收斂速度第一部分

重要關(guān)系數(shù)值計算方法902015/5/10誤差真誤差真百分比相對誤差近似百分比相對誤差停止準則泰勒級數(shù)泰勒級數(shù)展開余項誤差傳播Matlab基礎(chǔ)數(shù)值計算方法912015/5/10Arithmetic

Operations

（算術(shù)符號）Built-in

Functions（內(nèi)建函數(shù)）Assignment

Statements（賦值語句）DefiningFunction（函數(shù)定義）Matrices（矩陣）Matrix

Operations（矩陣運算）Array

Operations（數(shù)組運算）Graphics（圖形）Loops

and

Conditionals（循環(huán)和條件）Programs（程序）插值和擬合數(shù)值計算方法1舉例數(shù)值計算方法2t(s)v(t)(m/s)0010227.0415362.7820517.3522.5602.9730901.672016/6/12已知火箭在幾個不同時刻的速度如下表所示，求t=16時的速度？插值和擬合數(shù)值計算方法3(a)

用直線段連接這些點數(shù)據(jù)點分布接近線性或彼此距離很近(b)

用曲線描述了數(shù)據(jù)所具有的局部變化趨勢(c)

體現(xiàn)了數(shù)據(jù)總體的趨勢最小二乘回歸線性插值非線性插值2016/6/12插值和擬合——概述數(shù)值計算方法4x0x1x2x3x4x問題：有的函數(shù)雖有表達式，但較復(fù)雜，也可用簡單的函數(shù)g(x)來逼近它某些變量之間的函數(shù)關(guān)系y=f(x)存在，但沒有f(x)的解析式，y=f(x)以函數(shù)表格或曲線形式給出要求：根據(jù)函數(shù)表推算該函數(shù)在某些點上的函數(shù)值。解決與該函數(shù)有關(guān)的一些問題，如分析函數(shù)的性態(tài)，研究y=f(x)的變化規(guī)律，求導(dǎo)數(shù)、積分、零點與極值點等。g(x)

f(x)xx0x1…xnf(x)y0y1…yn2016/6/12插值和擬合——概述數(shù)值計算方法52016/6/12數(shù)學函數(shù)的逼近問題高精度快速計算建立實驗數(shù)據(jù)的數(shù)學模型只要求適度的精度插值擬合不要求過所有的點（可以消除誤差影響）盡可能表現(xiàn)數(shù)據(jù)的趨勢，靠近這些點用某個簡單函數(shù)在滿足一定條件下在某個范圍內(nèi)近似代替另一個較為復(fù)雜或者解析表達式未給出的函數(shù)，以便于簡化對后者的各種計算或揭示后者的某些性質(zhì)。本章內(nèi)容數(shù)值計算方法62016/6/12插值插值問題Lagrange插值多項式Newton插值多項式分段低次插值樣條插值擬合最小二乘方法插值問題數(shù)值計算方法7插值函數(shù)y=f(x)

在區(qū)間[a,b]上連續(xù)，

x0,x1,…,xn是[a,b]上的n+1個互異的點，且在這些點處函數(shù)值yi=f(xi)已知

為給定的某一函數(shù)類（性質(zhì)優(yōu)良、便于計算）g(xi)

=yi (i=0,1,…,n)插值節(jié)點插值區(qū)間插值條件插值函數(shù)類插值函數(shù)基本問題是否存在唯一如何構(gòu)造誤差估計插值函數(shù)類代數(shù)多項式有理函數(shù)三角函數(shù)ninia

xg(x)

i

0

1n,m

m 0mPn

x

x

0 1 n p

px

p

xnQ

x

q

qx

q

xm多項式插值被插函數(shù)2016/6/12有理函數(shù)：選取有理函數(shù)（多項式的商）作為插值函數(shù)。i

ina

xi

0P(x)

mnQm

x

x q0

q1x

qmx

P

x

p

px

p

xn0 1 nn,m有理插值可使區(qū)間內(nèi)插值誤差分布較為均勻，特別適用于某些被插函數(shù)具有無窮大間斷點的附近，這種情況下若用多項式逼近效果很差。三角函數(shù)：選取正弦和余弦等三角函數(shù)作為插值函數(shù)。=> 選擇不同的函數(shù)類作為插值函數(shù)逼近f(x)，其效果是不同的，因此需要根據(jù)實際問題選擇合適的插值函數(shù)。插值問題插值函數(shù)類代數(shù)多項式：選取多項式Pn(x)作為插值函數(shù)，Pn(x)稱為插值多項式。n插值函數(shù)存在唯一定理數(shù)值計算方法9特點：與插值節(jié)點有關(guān)與原函數(shù)f(x)無關(guān)基函數(shù)個數(shù)與點個數(shù)相同g(x)

a0

0

(x)

an

n

(x)g(xi

)

f

(xi

)

a0

0

(xi

)

an

n

(xi

)

f(x0

)

0(x0

)

0(xn)

n(xn)

an

f(xn

)

n(x0)

a0

a0

an

有唯一解0 n2016/6/12n n

(x

)

(x

)

0

(x0

)

n(x0

)

0

設(shè)則則

定理：為n＋1個節(jié)點，n+1維空間，則插值函數(shù)存在唯一，當且僅當

nixi

0

span{

0

,

1

,

n

}

0(x0

)

0(xn

)插值函數(shù)存在唯一定理數(shù)值計算方法102016/6/12

n(x0

)

0

n(xn

)插值多項式存在唯一性數(shù)值計算方法11若插值節(jié)點互異，則存在唯一的多項式Pn(x)使f(xi)=Pn(xi) i=0,1,…,nn

P

(x)

span{1,

x,

x2

,

xn

}02016/6/1200i jn n n1 xx2 xnx2xnx2xnn i

1i

1 j

0V

(x

x

)

1 x1 1

1

1 x

n+1階范德蒙(Vandermonde)行列式本章內(nèi)容數(shù)值計算方法122016/6/12插值插值問題Lagrange插值多項式Newton插值多項式分段低次插