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

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

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

避免除數(shù)的絕對(duì)值遠(yuǎn)小于被除數(shù)的絕對(duì)值防止大數(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]的中點(diǎn)二分法二分法將方程

f(x)=0

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

x0

，按下式計(jì)算計(jì)算結(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)為單根時(shí)，牛頓迭代法在根的附近至少是二階收斂的；2、當(dāng)為m重根時(shí)，牛頓迭代法在根的附近是線性

收斂的。定理設(shè)在滿足則方程在上有且只有一個(gè)實(shí)根，由牛頓法迭代公式計(jì)算得到的近似解序列收斂于方程的根雙點(diǎn)割線法或記憶割線法收斂階為單點(diǎn)割線法單點(diǎn)割線法在單根附近是線性收斂的。第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)（行對(duì)換）換到akk(k)的位置上,再消元，其中第k步先選主元aij(k),其次將aij(k)（行、列對(duì)換）換到akk(k)的位置上,再消元,其中二完全主元素消元法

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

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

若矩陣A非奇異，則A能分解為L(zhǎng)U的充分必要條件是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對(duì)稱且其順序主子式均不為0。Ly=bLTx=D-1y

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

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

Ly=b

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

||x||0

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

,||

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

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

對(duì)任意n維向量x

Rn，若對(duì)應(yīng)非負(fù)實(shí)數(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

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

，滿足①非負(fù)性

||A||

0

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

,||

A||=||

||A||；③三角不等式對(duì)任意兩個(gè)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).對(duì)任何非奇異矩陣,都有condv(A)

≥1.事實(shí)上

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)格對(duì)角占優(yōu)?；?/p>

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

迭代法和Gauss-Seidel

迭代法均收斂

。

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

，而且A,B的特征向量相同.其他步驟同冪法或反冪法。第5章代數(shù)插值拉格朗日插值多項(xiàng)式Newton插值多項(xiàng)式Hermite插值分段低次插值反插值拉格朗日基函數(shù)：拉格朗日插值多項(xiàng)式利用拉格朗日基函數(shù)式li(x),構(gòu)造多項(xiàng)式余項(xiàng)：牛頓插值法為函數(shù)f(x)在點(diǎn)x0,x1,…,xk的k階差商：（列表計(jì)算）牛頓插值多形式為：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é)點(diǎn)的排列次序無關(guān)，差商的對(duì)稱性：

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é)點(diǎn)x0,x1,…,xn∈[a,b],則至少存在一點(diǎn)[a,b]

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

一般來說，如果要計(jì)算x0附近的f(x)，用牛頓前插公式；如果要計(jì)算xn附近的f(x)，用牛頓后插公式.由給定函數(shù)表計(jì)算各階差分可由差分表給出.函數(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))分段低次線性插值法分別作線性插值得,在每個(gè)子區(qū)間[xi,

xi+1]已知?jiǎng)tP(x)就是區(qū)間[a,b]上的分段線性插值函數(shù).其中分段低次Hermite插值法[xi,xi+1]作埃爾米特插值，得已知在每個(gè)子區(qū)間其中如用拉格朗日插值多項(xiàng)式對(duì)上表做反插值有反插值的余項(xiàng)為反插值第6章數(shù)值擬合和數(shù)值逼近最小二乘超定方程組一般最小二乘擬合具體的做法是求p(x)使最小二乘法基本原理最小二乘法這個(gè)線性方程組稱為法方程組或正規(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)對(duì)所有次數(shù)不超過m的多項(xiàng)式都精確成立；(2)至少對(duì)一個(gè)m+1次多項(xiàng)式不精確成立，則稱該公式具有m次代數(shù)精度.代數(shù)精度定理7.1一個(gè)求積公式具有m次代數(shù)精度的充要條件是該求積公式：(2)對(duì)xm+1不精確成立。(1)對(duì)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公式余項(xiàng)為

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

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