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

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

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

f(x0)=0,

則

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

在

x0

的左側還是右側。

內有方程的根。

設

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

則[a,b]若

則

∈(a,x0

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

則

∈(x0,b),令a1=x0

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

f(x)=0

化為等價方程然后在隔根區間內取一點

x0

，按下式計算計算結果生成數列迭代法定理2

若方程之根的某鄰域0<L<1，使內存在,且存在正常數則迭代過程在

的鄰近為

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

的鄰域

U內有連續的

p階導數，則

設

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

收斂的。定理設在滿足則方程在上有且只有一個實根，由牛頓法迭代公式計算得到的近似解序列收斂于方程的根雙點割線法或記憶割線法收斂階為單點割線法單點割線法在單根附近是線性收斂的。第3章線性方程組求解高斯消元法高斯主元素消元法高斯——若當消元法矩陣分解向量與矩陣的范數、誤差分析迭代法、雅可比、高斯—塞德爾迭代法高斯消元法其中lik=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

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

P15,2題高斯—若當消元法

在高斯消元過程中，先將主元素化為1，而后將主元所在列的其它元素均化為零，最后將系數矩陣化為單位矩陣I，無需回代就可求得原方程的解，此法稱為高斯—約當消元法。高斯-若爾當消元法的運算量比高斯消元法大。矩陣分解定理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①非負性

||x||0

，等號僅當x=0時成立；②齊次性對任何實數

,||

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

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

對任意n維向量x

Rn，若對應非負實數

||x||，滿足向量的范數向量的范數設x=(x1

,x2

,…,xn)T

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

對任意n階方陣A=(aij)nn，若對應一個非負實數||A||

，滿足①非負性

||A||

0

且||A||=0當且僅當A=0；②齊次性對任意實數

,||

A||=||

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

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

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

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

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

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

.

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

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

條件數的性質:

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

≥1.事實上

condv(cA)

=condv(A).

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

(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

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

則稱矩陣A為行（或列）嚴格對角占優。或

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

迭代法和Gauss-Seidel

迭代法均收斂

。

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

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

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]

......差商表差商的性質性質2差商與節點的排列次序無關，差商的對稱性：

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

x0

]性質1

差商可以表示為函數值的線性組合，即性質3

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

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

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

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有關)分段低次線性插值法分別作線性插值得,在每個子區間[xi,

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

的解.這里ATAx=ATb是關于x1,x2,…,xn的線性方程組，稱為正規方程組或法方程組.一般最小二乘法記即有方程組的矩陣乘法形式為幾類經適當變換化為線性擬合求解的曲線擬合方程及變換關系擬合函數類型變量代換化成線性后函數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還有一些其它的函數也可以通過變換得到線性函數.第7章數值積分和數值微分牛頓—柯特斯復合求積公式高斯求積公式數值微分梯形公式(中)矩形公式定義1如果求積公式(1)對所有次數不超過m的多項式都精確成立；(2)至少對一個m+1次多項式不精確成立，則稱該公式具有m次代數精度.代數精度定理7.1一個求積公式具有m次代數精度的充要條件是該求積公式：(2)對xm+1不精確成立。(1)對xk(k=0,1,…,m)精確成立；牛頓—柯特斯稱為n階牛頓－柯特斯公式,其中稱為柯特斯系數.(k=0,1,…,n)柯特斯系數表(書p176有n=8的表)定理7.3n階牛頓-柯特斯公式的代數精度至少為當n為偶數當n為奇數

(2)若

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

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

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