萬中-數(shù)值分析綜合復(fù)習(xí)課-modified

數(shù)值分析綜合復(fù)習(xí)萬中教授/博導(dǎo)中南大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院第一章基本概念1誤差的分類2有效數(shù)字有效數(shù)字與相對誤差的關(guān)系4誤差的傳播5向量和矩陣的范數(shù)6算法及其設(shè)計的若干原則1、誤差的分類（絕對誤差，相對誤差）

例1-1

設(shè)x*=2.18是由精確值x

經(jīng)過“四舍五入”得到的近似值。問x的絕對誤差限ε和相對誤差限η各是多少？解：因為x=x*±0.005，

所以絕對誤差限為ε=0.005相對誤差限為：2、有效數(shù)字則稱近似數(shù)

x*

具有n位有效數(shù)字。定義

設(shè)數(shù)x的近似值可以表示為其中m

是整數(shù),αi(i=1,2,…,n)是0到9中的一個數(shù)字，而α1

≠0.如果其絕對誤差限為結(jié)論：通過四舍五入原則求得的近似數(shù)，其有效數(shù)字就是從末尾到第一位非零數(shù)字之間的所有數(shù)字。例1-2

下列近似數(shù)是通過四舍五入的方法得到的，試判定它們各有幾位有效數(shù)字：

解：我們可以直接根據(jù)近似數(shù)來判斷有效數(shù)字的位數(shù)，也可以通過絕對誤差限來判斷。有5位有效數(shù)字。同理可以寫出可以得出

x2

,x3

,x4

各具有4、3、4位有效數(shù)字。

x1*=87540，x2*=8754×10,x3*=0.00345,x4*=0.3450

×10-2已知例1-3

已知e=2.718281828……,試判斷下面兩個近似數(shù)各有幾位有效數(shù)字？解：由于而所以

e1有7位有效數(shù)字。同理：e2

只有6位有效數(shù)字。

定理1

設(shè)（1.2.2）用有效數(shù)字的位數(shù)估計相對誤差限有效數(shù)字的位數(shù)越多，相對誤差限就越小3.有效數(shù)字與相對誤差之間的關(guān)系x的近似值xA有n位有效數(shù)字，則如果（1.2.4）相對誤差限越小，有效數(shù)字的位數(shù)就越多相對誤差限估計有效數(shù)字的位數(shù)則xA有n位有效數(shù)字.

定理2設(shè)4、誤差的傳播(1)

對函數(shù)的計算：

對一元函數(shù)f(x),自變量x的一個近似值為xA，以f(xA)近似f(x),其誤差界記作(f(xA))對多元函數(shù)例1-4設(shè)有三個近似數(shù)它們都有三位有效數(shù)字。試計算p=a+bc的誤差界，并問p的計算結(jié)果能有幾位有效數(shù)字？解相對誤差界所以,pA=6.6332能有兩位有效數(shù)字。于是有誤差界5、向量和矩陣范數(shù)向量的范數(shù)矩陣的相容范數(shù)例1-5計算下列矩陣的范數(shù)：例1-6求矩陣的譜半徑.矩陣A的特征值為所以譜半徑解簡述題：1.敘述在數(shù)值運算中，減少誤差的原則是什么？解：減少誤差的原則：1）要避免除數(shù)絕對值遠(yuǎn)遠(yuǎn)小于被除數(shù)的絕對值2）要避免相近數(shù)相減；3）求和中要防止大數(shù)吃掉小數(shù)；4）簡化計算步驟，減少運算次數(shù)。6、算法設(shè)計的若干原則第二章插值與最優(yōu)逼近1、插值的概念；掌握拉格朗日(Lagrange)插值法及其余項公式；掌握牛頓插值法；掌握差商表的構(gòu)造過程。2、會構(gòu)造埃爾米特(Hermite)插值及其余項公式；掌握差商表的構(gòu)造過程；知道高次插值的病態(tài)性質(zhì)（高次插值的Runge

現(xiàn)象）；會構(gòu)造三次樣條插值。3、最優(yōu)平方逼近Lagrange插值多項式顯然，L(x)是不超過n次多項式。當(dāng)n=1時，稱為線性插值。當(dāng)n=2時，稱為拋物線插值。y0

xxk

xk+1①線性插值：特別地，n=1,2時的插值余項：y0x②拋物線插值：xk-1xk

xk+1例2-1

給定數(shù)據(jù)表

xi0123yi01514求三次(?)拉格朗日插值多項式L3(x).例2-2

要制作三角函數(shù)sinx的值表.要求表值有四位小數(shù)。若用線性插值，則為保證截斷誤差不超過表值的舍入誤差，其最大允許的步長是多少？解f(x)=sinx,設(shè)xi－１,xi為任意兩個插值節(jié)點，最大允許步長記為

h=hi=xi

－xi－１，Newton插值多項式：例2-3：已知f(x)的部分信息：(1,0)、(2,2)、(3,12)、(4,42)、(5,116),（1）求牛頓插值多項式N4(x)；（2）若增加一個節(jié)點(6,282),求N5(x)，（3）估算f(1.5)、f(1.5).解：先由前五組數(shù)據(jù)列差商表10223124425116210307441022240.5628216646810.1如果，再增加一點(6,282),就在上表中增加一行計算差商得到：由Newton公式的遞推式得到：得到：解：典型例題分析例2-4：令x0＝0，x1＝1，寫出y(x)＝e-x的一次插值多項式L1(x),并估計插值誤差．

記x0＝0，x1＝1,y0＝e-0＝1，y1＝e-1;則函數(shù)y＝e-x以x0、x1為節(jié)點的一次插值多項式為因為

y′(x)＝-e-x，y"(x)＝e-x

，所以例2-5推廣：等距節(jié)點(h),二次插值的誤差界是例2-6

：設(shè)f(x)＝x4，試?yán)美窭嗜詹逯涤囗椂ɡ韺懗鲆?1,0,1,2為插值節(jié)點的三次插值多項式．解:

記f(x)以-1，0，1，2為插值節(jié)點的三次插值多項式為L3(x)．由插值余項定理有所以例2-7：證明由下列插值條件所確定的拉格朗日插值多項式是一個二次多項式．該例說明了什么問題?以x0，x2，x4為插值節(jié)點作f(x)的2次插值多項式p(x)，則解:x0x2x4

容易驗證因而6個點(xi,yi)，i＝01,…,5均在二次曲線p(x)＝x2-1上．換句話說，滿足所給插值條件的拉格朗日插值多項式為

p(x)＝x2-1.例2-8：

分析:

這是一個非標(biāo)準(zhǔn)插值問題,我們可以按各種思路去做．可按兩種方法去做:一種是先求牛頓或拉格朗目型插值,再通過待定系數(shù)法求Pn(x)；另一種是先求埃爾米特插值,再通過待定系數(shù)法確定Pn(x)．下面給出三種做法．

例2-9：求一個次數(shù)不高于4的多項式P4(x)，使它滿足P4(0)=P4'(0)=0，P4(1)=P4'(1)=1，P4(2)=1．

解法一先求滿足P4(0)=0，P4(1)=1，P4(2)=1的插值多項式P2(x)，易得顯然P4(x)滿足P2(x)的插植條件，利用兩個導(dǎo)數(shù)條件確定系數(shù)A，B．由P4'(0)=0,P4'(1)=1解得A=1/4,B=-3/4.故設(shè)解法二先作滿足埃爾米特插值多項式H3(x)．解法三構(gòu)造插值基函數(shù)求.記x0=0，x1=1，x2=2，并設(shè)所求多項式為

其中l(wèi)i(x)均為次數(shù)不超過4的多項式且滿足如下條件：易知例2-10例2-11例2-12例2-13例2-14：已知函數(shù)y=f(x)

的如下數(shù)據(jù),試求其在區(qū)間[0,3]上的三次樣條插值函數(shù)S(x)。

解這里邊界條件是設(shè)求得已知由方程組及得到方程組解得這樣便求得代入表達(dá)式便得到所求的三次樣條函數(shù)3、最優(yōu)平方逼近函數(shù)類考慮特殊情形-(1)用多項式｛1,x,x2,…,xn｝作n次最佳平方多項式p*(x)逼近步驟/方法(權(quán)函數(shù)為１時，［a,b］=[0,1])解法方程組Ga=d(2)用正交多項式作最佳平方逼近

方法（步驟）：解法方程組平方誤差其中，例2-16最小二乘逼近步驟：平方誤差有與（2.4.15）相同形式的表達(dá)式。(2)多項式的擬合即在多項式空間中作曲線擬合，稱為多項式擬合。用上面討論的方法求解。子空間的基函數(shù)為

前面討論了子空間中的最小二乘擬合。在離散數(shù)據(jù)的最小二乘擬合中，最簡單、最常用的數(shù)學(xué)模型是多項式（2.5.4）

例2.19用多項式擬合表2-4中的離散數(shù)據(jù)。

yi0.100.350.811.091.96

xi

0.000.250.500.751.00

i12345表2-4解作數(shù)據(jù)點的圖形如圖2-2，從圖形看出用二次多項式擬合比較合適。這時n=2，子空間的基函數(shù)。數(shù)據(jù)中沒有給出權(quán)數(shù)，不妨都取為1，即。oy1.961x****圖2-2例2-17ixiyixi2xi3xi4xiyixi2yi00.000.100.0010.250.350.062520.500.810.2530.751.090.562541.001.961.002.54.311.8751.56251.38283.272.7975構(gòu)造下表按（2.5.4）有

解此方程組得。從而，擬合多項式為其平方誤差。擬合曲線的圖形見圖2-2。oy1.961x****圖2-2正交多項式擬合這時直接可算出，法方程組的矩陣形式為例2-18：

對如下數(shù)據(jù)作形如

y

=aebx

的擬合曲線

解:

由于函數(shù)集合Φ={aebx|a,b∈R}

不成為線性空間，因此直接作擬合曲線是困難的。

在函數(shù)y=aebx

兩端分別取對數(shù)得到這時，需要將原函數(shù)表進(jìn)行轉(zhuǎn)換如下令

z=lny,A=lna,B=b,則

z=A+Bxlny=lna+bxxi12345678yi15.320.527.436.649.165.687.8117.6對z=A+Bx

作線性擬合曲線，取這時xi12345678yi15.320.527.436.649.165.687.8117.6xi12345678zi2.723.023.313.603.894.184.484.77得正則方程組解得

于是有擬合曲線為：第三章數(shù)值積分插值型積分公式了解數(shù)值求積的基本思想、代數(shù)精度的概念、插值型求積公式及其代數(shù)精度、求積公式的收斂性和穩(wěn)定性。掌握牛頓-柯特斯公式及其性質(zhì)和余項。掌握復(fù)化梯形公式和復(fù)化辛普森公式及其余項。掌握龍貝格(Romberg)求積算法，知道外推法。會高斯求積公式,了解高斯-勒讓德求積公式和高斯-切比雪夫求積公式。一、數(shù)值積分

等價定義若求積公式對于1，x,…,xm都精確成立，對xm+1不精確成立，則稱該求積公式的代數(shù)精度為m。(3.1.1)引理：n階Newton-Cotes公式的代數(shù)精度至少是n.結(jié)論：當(dāng)n

為奇數(shù)時，n階Newton-Cotes公式的代數(shù)精度為n；當(dāng)n

為偶數(shù)時，n階Newton-Cotes公式的代數(shù)精度為n+1。2、Cotes系數(shù)特點：梯形公式代數(shù)精度=1Simpson公式代數(shù)精度=3柯特斯公式（Cotes)代數(shù)精度=5,復(fù)化梯形公式復(fù)化梯形公式是2階收斂的復(fù)化Simpson求積公式復(fù)化Simpson公式具有4階收斂龍貝格(Romberg)求積算法

穩(wěn)定性定理若求積公式(3.1.1)中系數(shù)Ak＞0(k＝0，1，…，n)，則此求積公式是穩(wěn)定的．2、求積余項

若,(3.1.5)是插值型求積公式,其中與變量x有關(guān),記作

x

。特別地,如果求積公式是插值型的,按余項式,對于次數(shù)≤

n的多項式f(x)，其余項R[f]等于0，因而這時求積公式至少具有n次代數(shù)精度．則有余項公式Gauss型求積公式當(dāng)求積系數(shù)Ak、求積節(jié)點xk都可以自由選取時,其代數(shù)精確度最高可以達(dá)到2n+1次?

(3.4.1)考慮帶權(quán)求積公式較簡單的方法是：先利用區(qū)間a,b上的n+1次正交多項式確定高斯點xk

∈[a,b],(k=0,1,…n)(2)然后利用高斯點確定求積系數(shù)Ak,(k=0,1,…n)插值求積公式節(jié)點一經(jīng)確定，相應(yīng)的求積系數(shù)就確定了，常用的Gauss求積公式1.Gauss-Legendre求積公式不失一般性，可取a=-1，b=1而考察區(qū)間[-1，1]上的高斯公式在區(qū)間[-1，1]上取權(quán)函數(shù)那么相應(yīng)的正交多項式為Legendre多項式。以Legendre多項式的零點為Gauss點的求積公式為（3.4.8）稱之為Gauss-Legendre求積公式。兩點Gauss—Legendre公式：五次代數(shù)精度的3點Gauss-Legendre求積公式定理

3.4.2設(shè),則Guass公式(3.4.1)的余項是(3.4.10)特別地，對于兩點Gauss-Legendre求積公式有解：所以該求積公式的代數(shù)精度m=3。例3-1例3-2

試構(gòu)造形如f(x)dxA0f(0)+A1f(h)+A2f(2h)的數(shù)值求積公式,使其代數(shù)精度盡可能高,并指出其代數(shù)精度的階數(shù).3h0解:

令公式對

f(x)=1,x,x2

均準(zhǔn)確成立,則有3h=A0+A1+A2h2=0+

A1h+A22h9h3=0+A1h2+A24h229故求積公式的形式為解之得

A0=h,

A1=0,A2=h.9434f(x)dxf(0)+f(2h)3h49h43h0而當(dāng)f(x)=x3時,公式的左邊=81h4/4,右邊=18h4,公式的左邊右邊,說明此公式對f(x)=x3不能準(zhǔn)確成立.因此,公式只具有2次代數(shù)精度.由公式的構(gòu)造知,公式至少具有2次代數(shù)精度;例3-3例3-4例3-5例3-6的近似值，要求誤差例3-8用Romberg求積法計算解：此時積分限為a=0,b=1.而(本例主要說明Romberg過程）

①．

③．④．⑤．⑥．⑦．⑧．⑨．⑩．②．如此繼續(xù)算得：由于例3-9構(gòu)造三個節(jié)點的Gauss-Legendre求積公式，并給出余項估計式。

解：由于三次Legendre多項式為：其三個零點分別為：令它對準(zhǔn)確成立則三點Gauss-Legendre求積公式為：余項為：（節(jié)點數(shù)）例如，若要計算的近似值，則由上積分公式得：上述積分準(zhǔn)確值為：若利用三點Simpson求積公式。則可見在節(jié)點數(shù)目相同的情況下，Gauss求積公式的精度是相當(dāng)高的。例3-10例3-11第4-6章綜合復(fù)習(xí)課

1、線性方程組數(shù)值解法

2、非線性方程求根一、解線性方程組的直接方法基本內(nèi)容及基本要求了解求解方程組的兩類方法,了解矩陣基礎(chǔ)知識。掌握高斯消去法,會矩陣的三角分解。掌握高斯列主元素消去法,了解高斯-若當(dāng)消去法。掌握直接三角分解法,了解平方根法,會追趕法,了解有關(guān)結(jié)論。了解向量和矩陣的幾種范數(shù)。了解矩陣和方程組的性態(tài),會求其條件數(shù)。解線性方程組的直接方法

一般的線性方程組解法：

列（全）主元素Gauss消元法

LU分解（直接三角分解法）

特殊的線性方程組解法：

平方根法（改進(jìn)）對稱正定矩陣

追趕法三對角方程組

矩陣表示與計算量

誤差分析（條件數(shù)）：

向量、矩陣范數(shù)，

誤差分析（條件數(shù)），

病態(tài)方程。右端項b的擾動對解的影響系數(shù)矩陣A的擾動對解的影響例4-1例4-2例4-3例4-4例4-5分別用順序Gauss消去法和直接三角分解法(杜利特分解)求解線性方程組

四、練習(xí)---線性方程組直接解法2.用帶行交換的杜利特分解計算線性代數(shù)方程組AX=b，其中3.用追趕法求解三對角方程組二、線性方程組的迭代解法基本內(nèi)容及基本要求了解迭代法及其收斂性的概念。掌握雅可比(Jacobi)迭代法、高斯-賽德爾(Gauss-Seidel)迭代法和超松弛(SOR)迭代法。3.了解一階定常迭代法的基本定理，掌握特殊方程組迭代法的收斂條件。4.知道分塊迭代法。解線性方程組的迭代法方法

迭代方法：

雅可比（Jacobi）迭代法

高斯－賽德爾(Gauss-Seidel)迭代法

松弛法

迭代矩陣的表示

迭代法的收斂判別：

矩陣的譜半徑

迭代法的收斂定理及推論（迭代矩陣）

對系數(shù)矩陣A的三條判別原則

誤差估計與停機(jī)準(zhǔn)則雅可比迭代法計算公式：對k=0,1,…,高斯—塞德爾迭代法計算公式：對k=0,1,…,SOR迭代法的計算公式:對k=0,1,…,例5-3例5-4.例5-5.三、非線性方程的數(shù)值解法基本內(nèi)容及基本要求

了解求根問題和二分法。了解不動點迭代法,及不動點存在性和迭代收斂性；了解收斂階的概念和有關(guān)結(jié)論。3.了解加速迭代收斂的埃特金方法和斯蒂芬森方法。4.掌握牛頓法及其收斂性、了解簡化牛頓法和牛頓法下山法,了解重根情形。5.掌握弦截法，了解拋物線法。1.設(shè)x*是f(x)=0在[a,b]內(nèi)的唯一根,且f(a)·f(b)<0,則二分法計算過程中,數(shù)列滿足:|xn–x*|≤(b–a)/2n+1

收斂充分性定理

收斂充分性定理(三)重根的情形該迭代至少二階收斂.例1

已知迭代公式

收斂于

證明該迭代公式平方收斂.證:

迭代公式相應(yīng)的迭代函數(shù)為將

代入，根據(jù)定理可知，迭代公式平方收斂。解因,所以迭代公式為例2:用牛頓法求下面方程的根從計算結(jié)果可以看出,牛頓法的收斂速度是很快的,進(jìn)行了四次迭代就得到了較滿意的結(jié)果.計算結(jié)果列于下表選取,例3

計算的近似值。

=10-6

x0=0.88由牛頓迭代公式

xk+1=xk-?(xk)/?'(xk)=xk/2+0.78265/2xk解：令x=問題轉(zhuǎn)化為求?(x)=x2-0.78265=0的正根迭代結(jié)果

k

0

123xk0.8800000.8846880.8846750.884675滿足了精度要求

=0.884675

例4

應(yīng)用牛頓迭代法于方程

x3–a=0,導(dǎo)出求立方根的迭代公式,并討論其收斂性。解：令f(x)=x3–a，則牛頓迭代公式故立方根迭代算法二階收斂例5.設(shè)a

為正實數(shù)，試建立求1/a

的牛頓迭代公式，要求在迭代公式中不含有除法運算，并考慮迭代公式的收斂。xn+1=xn(2–axn)，(n=0，1，2……)所以,當(dāng)|1–ax0|<1時，迭代公式收斂。解:建立方程利用牛頓迭代法，得1–axn+1=(1–axn)2

整理，得例6例7練習(xí)題：第七章矩陣特征值問題計算

了解特征值和特征向量的概念和性質(zhì),

了解圓盤定理、Schur定理和Rayleigh商。2.掌握乘冪法，了解其加速收斂技術(shù),會反冪法。3.了解Jacobi方法。4.了解QR方法?；緝?nèi)容及基本要求

知識結(jié)構(gòu)圖矩陣特征值與特征向量的計算冪法（冪法加速）滿足條件的實矩陣最大特征值及其相應(yīng)的特征向量。反冪法滿足條件的實矩陣