計算方法-總復(fù)習(xí)

計算方法——總復(fù)習(xí)第1章緒論誤差的概念誤差的傳播注意的問題相對誤差誤差相對誤差限：相對誤差的絕對值的上界有效數(shù)字如果近似值x*的誤差限是某一位的半個單位，該位到x*的第一位非零數(shù)字共有n位,我們稱x*有n位有效數(shù)字。有n位。則其相對誤差限為定理1設(shè)近似值有效數(shù)字定義：用x*表示x的近似值，并將x*表示成若其誤差限,則稱x*具有n位有效數(shù)字,這里m

是整數(shù),a10.絕對誤差限相對誤差限n為有效數(shù)字m為科學(xué)計數(shù)法中的誤差的傳播誤差的傳播注意的問題注意避免兩個相近數(shù)的相減

避免除數(shù)的絕對值遠小于被除數(shù)的絕對值防止大數(shù)“吃掉”小數(shù)第2章方程求根二分法迭代法牛頓切線法割線法將區(qū)間一分為二。若

f(x0)=0,

則

x0就是方程的根,否則判別根

在

x0

的左側(cè)還是右側(cè)。

內(nèi)有方程的根。

設(shè)

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

則[a,b]若

則

∈(a,x0

),令a1=a,b1=x0;若

則

∈(x0,b),令a1=x0

,b1=b。取[a,b]的中點二分法二分法將方程

f(x)=0

化為等價方程然后在隔根區(qū)間內(nèi)取一點

x0

，按下式計算計算結(jié)果生成數(shù)列迭代法定理2

若方程之根的某鄰域0<L<1，使內(nèi)存在,且存在正常數(shù)則迭代過程在

的鄰近為

p階收斂。(1)若為線性收斂；則迭代過程在的鄰近(2)若定理3之根,在

的鄰域

U內(nèi)有連續(xù)的

p階導(dǎo)數(shù)，則

設(shè)

為牛頓切線法1、當(dāng)為單根時，牛頓迭代法在根的附近至少是二階收斂的；2、當(dāng)為m重根時，牛頓迭代法在根的附近是線性

收斂的。定理設(shè)在滿足則方程在上有且只有一個實根，由牛頓法迭代公式計算得到的近似解序列收斂于方程的根雙點割線法或記憶割線法收斂階為單點割線法單點割線法在單根附近是線性收斂的。第3章線性方程組求解高斯消元法高斯主元素消元法高斯——若當(dāng)消元法矩陣分解向量與矩陣的范數(shù)、誤差分析迭代法、雅可比、高斯—塞德爾迭代法高斯消元法其中l(wèi)ik=aik(k)/akk(k),

k=1,2,…,n,i=k+1,k+2,…,n。高斯消元法定理1

如果在消元過程中A的主元素(k=1,2,…,n),則可通過高斯消元法求出Ax=b

的解.定理2

Ax=b

可用高斯消元法求解的充分必要條件是：系數(shù)矩陣A的各階順序主子式均不為零.高斯主元素消元法列主元素消元法第k步先選列主元aik(k),其次將aik(k)（行對換）換到akk(k)的位置上,再消元，其中第k步先選主元aij(k),其次將aij(k)（行、列對換）換到akk(k)的位置上,再消元,其中二完全主元素消元法

P15,2題高斯—若當(dāng)消元法

在高斯消元過程中，先將主元素化為1，而后將主元所在列的其它元素均化為零，最后將系數(shù)矩陣化為單位矩陣I，無需回代就可求得原方程的解，此法稱為高斯—約當(dāng)消元法。高斯-若爾當(dāng)消元法的運算量比高斯消元法大。矩陣分解定理1

若矩陣A非奇異，則A能分解為LU的充分必要條件是A的順序主子式不為0。定理2

若非奇異矩陣A有LU分解,則此分解是唯一的。LU分解法a11a12a1k

a1n

u11u12u1k

u1n

第1框a21a22a2k

a2n

l21u22u2k

u2n第2框

ak1ak2

akk

akn

lk1lk2

ukk

ukn第k框

an1an2ankann

ln1ln2

lnk

unn第n框Ly=b

Ux=y

Ly=bUx=yLDLT

(Cholesky)分解法要求：矩陣A對稱且其順序主子式均不為0。Ly=bLTx=D-1y

Ly=bLTx=D-1y平方根法（LLT

分解法）要求：矩陣A對稱正定,其順序主子式均大于0。Ly=bLTx=y

Ly=b

LTx=y追趕法要求：A為三對角矩陣。交替計算Ly=dUx=y①非負(fù)性

||x||0

，等號僅當(dāng)x=0時成立；②齊次性對任何實數(shù)

,||

x||=||·||x||；③三角不等式

||x+y||||x||+||y||；則稱||x||為向量x的范數(shù)。定義1

對任意n維向量x

Rn，若對應(yīng)非負(fù)實數(shù)

||x||，滿足向量的范數(shù)向量的范數(shù)設(shè)x=(x1

,x2

,…,xn)T

，常用的向量范數(shù)有它們分別叫做向量的-范數(shù)、1-范數(shù)、2-范數(shù)、p-范數(shù)（0<p<+）。-范數(shù)1-范數(shù)2-范數(shù)p-范數(shù)定義2

對任意n階方陣A=(aij)nn，若對應(yīng)一個非負(fù)實數(shù)||A||

，滿足①非負(fù)性

||A||

0

且||A||=0當(dāng)且僅當(dāng)A=0；②齊次性對任意實數(shù)

,||

A||=||

||A||；③三角不等式對任意兩個n階方陣A與B,有||A+B||||A||+||B||；④相容性

||AB||||A||||B||則稱||A||

為矩陣A的范數(shù)。矩陣的范數(shù)常用的矩陣范數(shù)有它們分別叫做矩陣的-范數(shù)、1-范數(shù)、2-范數(shù)。（矩陣的行范數(shù)）（矩陣的列范數(shù)）矩陣的范數(shù)（矩陣的譜范數(shù)）定義3

設(shè)n階方陣A=(aij)nn的特征值為i(i=1,2,…,n),稱為A的譜半徑。定理1(特征值上界)設(shè)n階方陣A=(aij)nn，則有即A的譜半徑不超過A的任何一種范數(shù).定理2

設(shè)為與某種向量范數(shù)相容的特征向量，則定義2設(shè)A是非奇異矩陣,稱數(shù)condv(A)

=||A-1||v||A||v(v=1,2或)為矩陣A的條件數(shù)

.

(1)cond∞(A)=||A-1||||A||;

(2)A的譜條件數(shù)：通常使用的條件數(shù),有

條件數(shù)的性質(zhì):

(1).對任何非奇異矩陣,都有condv(A)

≥1.事實上

condv(cA)

=condv(A).

(2).設(shè)A為非奇異矩陣且c≠0(常數(shù)),則

(3).如果A為正交矩陣,則cond2(A)

=1;如果B為非奇異矩陣,A為正交矩陣,則

cond2(AB)

=cond2(BA)

=cond2(B).迭代法把矩陣A分解成矩陣N和P之差，A=N-P

，其中N為非奇異矩陣，于是，方程組

Ax=b便可以表示成其中建立迭代公式定理11）

迭代格式

x(k+1)=Bx(k)

+f

收斂

limBk=O；2）

迭代格式

x(k+1)=Bx(k)

+f

收斂

(B)<1。雅可比迭代法記矩陣A=D-L-U

，其中于是雅可比迭代法可寫為矩陣形式其Jacobi迭代矩陣為B1=BJ=D-1(L+U)建立迭代格式高斯——塞德爾迭代法其G-S迭代矩陣為B2=BG=(D-L)-1U于是高斯—塞德爾迭代法可寫為矩陣形式定義1

設(shè)n階矩陣A=(aij)n×n，如果

則稱矩陣A為行（或列）嚴(yán)格對角占優(yōu)。或

定理3若矩陣A行（或列）嚴(yán)格對角占優(yōu)，則解線性方程組Ax=b的Jacobi

迭代法和Gauss-Seidel

迭代法均收斂

。

定理4若A為正定矩陣，則方程組Ax=b的Gauss—Seidel迭代法收斂。第4章特征值和特征向量——適用大型稀疏矩陣冪法：求最大特征值及其對應(yīng)特征向量的一種向量迭代法。反冪法：求最小特征值及其對應(yīng)特征向量的一種向量迭代法。原點平移法當(dāng)k充分大時,有其中mk是向量yk中絕對值最大的第一個分量.這時xk分量的模最大為1.冪法收斂速度取決于比值,比值越小,收斂越快.反冪法因為A-1的計算比較困難，所以解方程組先對A進行LU分解A=LU,此時反冪法的迭代公式為當(dāng)k充分大時,有原點平移法引進矩陣B=A-pI.其中p為參數(shù)，設(shè)A的特征值為i，則對矩陣B的特征值為i-p

，而且A,B的特征向量相同.其他步驟同冪法或反冪法。第5章代數(shù)插值拉格朗日插值多項式Newton插值多項式Hermite插值分段低次插值反插值拉格朗日基函數(shù)：拉格朗日插值多項式利用拉格朗日基函數(shù)式li(x),構(gòu)造多項式余項：牛頓插值法為函數(shù)f(x)在點x0,x1,…,xk的k階差商：（列表計算）牛頓插值多形式為：xk函數(shù)值一階差商二階差商三階差商...

x0x1

x2

x3...

f(x0)

f(x1)f(x2)f(x3)...

f[x0,x1]

f[x1,x2]

f[x2,x3]

...

f[x0,x1,x2]

f[x1,x2,x3]

...

f[x0,x1,x2,x3]

......差商表差商的性質(zhì)性質(zhì)2差商與節(jié)點的排列次序無關(guān)，差商的對稱性：

f[x0,x1,x2,...,xn]=f[x1,x0,x2,...,xn]=…=f[x1,x2,...,xn,

x0

]性質(zhì)1

差商可以表示為函數(shù)值的線性組合，即性質(zhì)3

若f(x)在[a,b]上存在n階導(dǎo)數(shù),且節(jié)點x0,x1,…,xn∈[a,b],則至少存在一點[a,b]

滿足下式差分設(shè)插值節(jié)點為等距節(jié)點,即xk=x0+kh(k=0,1,…,n)的情形，這里h稱為步長.一般地，n階差分分別稱為函數(shù)f(x)在點xk處的n階向前差分和n階向后差分.（一般列表計算）

一般來說，如果要計算x0附近的f(x)，用牛頓前插公式；如果要計算xn附近的f(x)，用牛頓后插公式.由給定函數(shù)表計算各階差分可由差分表給出.函數(shù)值一階差分二階差分三階差分四階差分...

f(x0)

f(x1)f(x2)f(x3)f(x4)...

f0

(f1)

f1

(f2)

f2

(f3)f3

(f4)...

2f0

(2f2)

2f1

(2f3)2f2

(2f4)...

3f0

(3f3)

3f1

(3f4)...4f0

(4f4)......牛頓前插公式牛頓后插公式Hermite插值法且與x有關(guān))分段低次線性插值法分別作線性插值得,在每個子區(qū)間[xi,

xi+1]已知則P(x)就是區(qū)間[a,b]上的分段線性插值函數(shù).其中分段低次Hermite插值法[xi,xi+1]作埃爾米特插值，得已知在每個子區(qū)間其中如用拉格朗日插值多項式對上表做反插值有反插值的余項為反插值第6章數(shù)值擬合和數(shù)值逼近最小二乘超定方程組一般最小二乘擬合具體的做法是求p(x)使最小二乘法基本原理最小二乘法這個線性方程組稱為法方程組或正規(guī)方程組.超定方程法定理x*是Ax=b的最小二乘解的充要條件為x*是ATAx=ATb

的解.這里ATAx=ATb是關(guān)于x1,x2,…,xn的線性方程組，稱為正規(guī)方程組或法方程組.一般最小二乘法記即有方程組的矩陣乘法形式為幾類經(jīng)適當(dāng)變換化為線性擬合求解的曲線擬合方程及變換關(guān)系擬合函數(shù)類型變量代換化成線性后函數(shù)y=aeb/x

(a>0)y*=lny,x*=1/xy*=a*+bx*y=1/(a+be-x)x*=e-x,y*=1/yy*=a+bx*

y=1/(ax+b)y*=1/yy*=b+axy=x/(ax+b)y*=1/y,x*=1/xy*=a+bx*y2=ax2+bx+cy*=y2y*=ax2+bx+cy=1/(ax2+bx+c)y*=1/yy*=ax2+bx+cy=x/(ax2+bx+c)y*=x/yy*=ax2+bx+cy=a+b/x+c/x2x*=1/xy*=a+bx*+cx*2還有一些其它的函數(shù)也可以通過變換得到線性函數(shù).第7章數(shù)值積分和數(shù)值微分牛頓—柯特斯復(fù)合求積公式高斯求積公式數(shù)值微分梯形公式(中)矩形公式定義1如果求積公式(1)對所有次數(shù)不超過m的多項式都精確成立；(2)至少對一個m+1次多項式不精確成立，則稱該公式具有m次代數(shù)精度.代數(shù)精度定理7.1一個求積公式具有m次代數(shù)精度的充要條件是該求積公式：(2)對xm+1不精確成立。(1)對xk(k=0,1,…,m)精確成立；牛頓—柯特斯稱為n階牛頓－柯特斯公式,其中稱為柯特斯系數(shù).(k=0,1,…,n)柯特斯系數(shù)表(書p176有n=8的表)定理7.3n階牛頓-柯特斯公式的代數(shù)精度至少為當(dāng)n為偶數(shù)當(dāng)n為奇數(shù)

(2)若

f(x)C4[a,b],則Simpson公式余項為

牛頓-柯特斯公式不穩(wěn)定。定理7.4(1)若

f(x)C2[a,b],梯形公式余項為復(fù)合求積公式1.復(fù)合梯形公式2.復(fù)合辛卜生公式高斯求積公式適當(dāng)選取求積節(jié)點xk,可使其具有2n+1次代數(shù)精度.這種求積公式稱為高斯(Gauss)求積公式,簡稱高斯公式,其求積節(jié)點xk稱為高斯點.高斯求積公式是穩(wěn)定的，也是收斂的.高斯－勒讓德求積公式的節(jié)點和系數(shù)表n節(jié)點數(shù)求積節(jié)點xk求積系數(shù)Ａk