數(shù)值分析(計(jì)算方法)總結(jié)9頁(yè)

1、第一章 緒論 誤差來源：模型誤差、觀測(cè)誤差、截?cái)嗾`差（方法誤差）、舍入誤差 x=|x-x*|是x*的絕對(duì)誤差，e=x*-x是x*的誤差，x=x-x*，為x*的絕對(duì)誤差限（或誤差限） er=ex=x*-xx為x* 的相對(duì)誤差，當(dāng)|er|較小時(shí)，令 er=ex*=x*-xx*相對(duì)誤差絕對(duì)值得上限稱為相對(duì)誤差限記為：r 即：er=|x*-x|x*x*=r絕對(duì)誤差有量綱，而相對(duì)誤差無量綱若近似值x*的絕對(duì)誤差限為某一位上的半個(gè)單位，且該位直到x*的第一位非零數(shù)字共有n位，則稱近似值 x*有n位有效數(shù)字，或說 x *精確到該位。例：設(shè)x=3.1415926那么x*=3,1x=0.14159260.5&#

2、215;100,則x*有效數(shù)字為1位，即個(gè)位上的3，或說 x *精確到個(gè)位?？茖W(xué)計(jì)數(shù)法：記x*=±0.a1a2an×10m其中a10,若x-x*0.5×10m-n，則x*有n位有效數(shù)字，精確到10m-n。由有效數(shù)字求相對(duì)誤差限：設(shè)近似值x*=±0.a1a2an×10m（a10）有n位有效數(shù)字，則其相對(duì)誤差限為12a1×101-n由相對(duì)誤差限求有效數(shù)字：設(shè)近似值x*=±0.a1a2an×10m（a10）的相對(duì)誤差限為為12（a1+1）×101-n則它有n位有效數(shù)字令x*、y*是x、y的近似值，且|x*-x|

3、x、|y*-y|(y)1. x+y近似值為x*+y*,且x+y=x+（y）和的誤差（限）等于誤差（限）的和2. x-y近似值為x*-y*,且x+y=x+（y）3. xy近似值為x*y*,xyx*y+y*(x)4. (xy)x*y+y*(x)|y*|21避免兩相近數(shù)相減2避免用絕對(duì)值很小的數(shù)作除數(shù)3避免大數(shù)吃小數(shù)4盡量減少計(jì)算工作量第二章 非線性方程求根1.逐步搜索法設(shè)f (a) <0, f (b)> 0，有根區(qū)間為 (a, b)，從x0=a出發(fā)， 按某個(gè)預(yù)定步長(zhǎng)(例如h=(b-a)/N)一步一步向右跨，每跨一步進(jìn)行一次根的搜索，即判別f(xk)=f(a+kh)的符號(hào)，若f(xk)&

4、gt;0(而f(xk-1)<0),則有根區(qū)間縮小為xk-1,xk (若f(xk)=0，xk即為所求根), 然后從xk-1出發(fā)，把搜索步長(zhǎng)再縮小，重復(fù)上面步驟，直到滿足精度：|xk-xk-1|<E為止，此時(shí)取x*(xk+xk-1)/2作為近似根。2.二分法設(shè)f(x)的有根區(qū)間為a,b= a0,b0, f(a)<0, f(b)>0.將a0,b0對(duì)分，中點(diǎn)x0= (a0+b0)/2),計(jì)算f(x0)。對(duì)于給定精度，即b-a2k<，可得所需步數(shù)k，k>lnb-a-ln()ln23.比例法一般地，設(shè) ak,bk為有根區(qū)間，過(ak, f(ak)、 (bk, f(bk)

5、作直線，與x軸交于一點(diǎn)xk,則：x=a-f(a)fb-f(a)*(b-a)1.試位法每次迭代比二分法多算一次乘法，而且不保證收斂。2.比例法不是通過使求根區(qū)間縮小到0來求根，而是在一定條件下直接構(gòu)造出一個(gè)點(diǎn)列（遞推公式），使該點(diǎn)列收斂到方程的根。這正是迭代法的基本思想。 事先估計(jì):|x*-xk|L1-L|x1-x0|事后估計(jì)|x*-xk|11-L|xk+1-xk|局部收斂性判定定理：設(shè)x*為方程x=x的根，(x)'在x*的某一鄰域內(nèi)連續(xù)， 且(x*)'<1，則該迭代局部收斂局部收斂性定理對(duì)迭代函數(shù)的要求較弱，但對(duì)初始點(diǎn)要求較高，即初始點(diǎn)必須選在精確解的附近Steffens

6、en迭代格式：xk+1=(xk)xk+1=(xk+1)xk+1=xk-(xk+1-xk)2xk+1-2xk+1+xkNewton法：xk+1=xk-f(xk)f'(xk)Newton下山法：xk+1=xk-f(xk)f'(xk),是下山因子弦割法：xk+1=xk-fxk*(xk-xk-1)fxk-f(xk-1)拋物線法：令t=x-xk,h0=xk-2-xk,h1=xk-1-xk,可化為yt=at2+bt+c其中：a=fxk-2-c*h1-fxk-1-c*h0h1*h02-h0*h12b=fxk-1-c*h02-fxk-2-c*h12h1*h02-h0*h12c=f(xk)則：x

7、k+1=xk+-2cb+b2-4ac,b>0xk+2cb+b2-4ac ,b0 設(shè)迭代 xk+1 = g(xk) 收斂到g(x) 的不動(dòng)點(diǎn)（根） x* 設(shè) ek = xk - x*若limkek+1ekp=C，則稱該迭代為p （不小于1）階收斂，其中 C (不為0)稱為漸進(jìn)誤差常數(shù)第三章 解線性方程組直接法列主元LU分解法：計(jì)算主元Si=aik-r=1k-1lirurk，i=k,k+1n選主元Sik=maxkinSiu1j=a1j，（j=1,2n)li1=ai1u11，（i=2,3n)ukj=akj-m=1k-1lkmumj，j=k,k+1,n，即為上式主元lik=1ukkaik-m=1

8、k-1limumk，i=k+1,k+2,n 對(duì)于Ax=b，三角分解A=LU，Doolittle分解：L為單位下三角矩陣，U為上三角矩陣；Crout分解：L為下三角矩陣，U為單位上矩陣?？煞纸鉃椋篖y=b，下三角方程組Ux=y，上三角方程組若利用緊湊格式可化為：Ux=yy1=b1yk=bk-m=1k-1lkmym，（k=2,3n） Cholesky平方根法：系數(shù)矩陣A必須對(duì)稱正定AX=bLy=bLTx=y(其中A=LLT)l11=a11，li1=ai1l11(i=2,3n)lkk=akk-m=1k-1lkm2，lik=1lkk(aik-m=1k-1limlkm)(i=k+1,k+2n，k=2,3

9、n) 改進(jìn)Cholesky分解法：A=LDLTL=1l211l31l321ln1ln2ln(n-1)1，D=d1d2dn。由A=L(DLT)A=1l211l31l321ln1ln2ln(n-1)1，D=d1d1l21d1l31d1ln1d2d2l32d2ln2d3ln3dn，逐行相乘lij=1dj(aij-k=1j-1likdkljk)，（j=1,2i-1)di=aii-k=1j-1lik2dk，（i=1,2n)為減少計(jì)算量，令cij=lijdj，可改為：cij=aij-k=1j-1cikljklij=cijdjdj=aii-k=1i-1ciklik(i=2,3n，j=1,2i-1)，等價(jià)于L

10、y=bLTx=D-1y其中：D-1=1d11d21dn 追趕法：Ax=d(A=LU),可化為L(zhǎng)y=d,Ux=yA=a1c1b1a2c2an-1bn-1cn-1anbn=1l21ln-11ln1u1c1u2c2un-1cn-1unu1=b1li=aiui-1ui=bi-lici-1，（i=2,3n) 向量范數(shù)：A1=i=1nxi，1-范數(shù)A2=i=1nxi2，2-范數(shù)或歐氏范數(shù)A=limp+xp=max1inxi，-范數(shù)矩陣范數(shù)：A1=max1jni=1naij，列范數(shù)A2=maxATA，譜范數(shù)A=max1inj=1naij，行范數(shù)譜半徑:A=max1ini為特征值,且AA,若A為對(duì)稱陣則：A=

11、A2收斂條件：譜半徑小于1條件數(shù)：Cond=A-1*A，Cond2A=maxmin第四章 解線性方程組的迭代法Jacobi迭代：xi(k+1)=1aii(bi-j=1i-1aijxjk-j=i+1naijxjk),(i=1,2n;k=0,1,2) 基于Jacobi迭代的Gauss-Seidel迭代:xi(k+1)=1aii(bi-j=1i-1aijxjk+1-j=i+1naijxjk),(i=1,2n;k=0,1,2)迭代收斂：譜半徑小于1，范數(shù)小于1能推出收斂但不能反推 逐次超松弛迭代（SOR）:xi(k+1)=xi(k)-aii(bi-j=1i-1aijxjk+1-j=i+1naijxjk

12、),(i=1,2n;k=0,1,2)或：xi(k+1)=1-xik+aii(bi-j=1i-1aijxjk+1-j=i+1naijxjk),(i=1,2n;k=0,1,2) 當(dāng)=1時(shí)，就是基于Jacobi迭代的Gauss-Seidel迭代（加權(quán)平均）。第五章 插值法 Lagrange插值法：ljxi=0，ij1，i=j，則ljx=i=0nx-xixj-xi構(gòu)造插值函數(shù)：Lnxi=fxi=yi，i=0,1n，令Lx=l0xy0+l1xy1+ln(x)yn 則：y=Lnx=j=0nljxyj=j=0ni=0ijn(x-xi)(xj-xi)yj 若記：wx=x-x0x-x1x-xn=i=0n（x-x

13、i） 則可改為：ljx=wn+1(x)x-xjw'n+1(xj)，則Lnx=j=0ni=0ijn(x-xi)(xj-xi)yj=j=0nw(x)x-xjw'(xj)yj 則插值余項(xiàng)：Rnx=fx-Lnx=fn+1n+1!wn+1(x) 逐次線性插值法Aitken （埃特金法）：L 0,1k,lx=L0,1kx+L0,1k-1x-L0,1kxxl-xkx-xk=1xl-xkf(xl)x-xlf(xk)x-xk Newton插值法： N(x)=a0+a1(x-x0)+a2(x-x0)(x-x1)+an(x-x0)(x-x1)(x-xn)并滿足N(x)=f(x) 差商的函數(shù)值表示：f

14、x0,x1xk=i=0kf(xi)wk+1(xi) 差商與導(dǎo)數(shù)的關(guān)系：fx0,x1xk=fn()n! 則：fx=fx0+fx0,x1w1x+fx0,x1xnwnx+fx,x0,x1xn+1wn+1x 等距節(jié)點(diǎn)Newton插值公式： Newton向前插值：Nna+th=fx+k=1nky0tk，其中tk=tt-1(t-k+1)k! 余項(xiàng)：Rnx=fn+1hn+1tn+1，t=x-x0h Newton向后插值：Nnxn+th=fxn+k=1nkynt+k-1k 余項(xiàng)：Rnx=fn+1hn+1t+nn+1 Hermite插值：Hx=j=0njxyj+j=0njxy'j jx=Ax+Blj2x

15、，jx=Cx+Dlj2(x) 可得：ix=1-2x-xik=0kin1xi-xkli2(x)ix=x-xili2(x) 插值余項(xiàng)：R2n+1x=fx-H2n+1x=f2n+22n+2!wn+12(x) 待定系數(shù)：Hx=L0,1n(Aitken)+x-x1*x-x2*x-xn*(Ax+B) 三次樣條插值：（三彎矩構(gòu)造法） 記s''xi=Mi對(duì)s積分兩次并滿足插值條件，hi=xi-xi-1，i=hihi+hi+1，i=hi+1hi+hi+1 對(duì)于附加彎矩約束條件：2122232n-2n-12M1M2M3Mn-1=6fx0,x1,x2-1M06fx1,x2，x36fx2,x3，x46

16、fxn-2,xn-1,xn-n-1MniMi-1+2Mi+iMi+1=6fxi-1,xi,xi+1 對(duì)于附加轉(zhuǎn)角邊界條件：21121222n-12n-112M0M1M2Mn-1Mn=6fx0,x1-m0h1fx0,x1，x2fx1,x2，x3fxn-2,xn-1,xnmn-fxn-2,xn-1,xnhn 對(duì)于附加周期性邊界條件：200121222n-22n-2n-1n-22M0M1M2Mn-2Mn-1=6fx0,x1-fxn-1,xnh1+hnfx0,x1，x2fx1,x2，x3fxn-3,xn-2,xn-1fxn-2,xn-1,xnsx=Mi-1(xi-x)36hi+Mi(x-xi-1)36

17、hi+fxi-1-Mi-1hi26xi-xhi+fxi-Mihi26x-xi-1hi 上式保證了s(x)在相鄰兩點(diǎn)的連續(xù)性第六章 函數(shù)逼近與曲線擬合 主要求法方程第七章 數(shù)值積分與數(shù)值微分 求積公式具有m次代數(shù)精度的充要條件：abxkdx=i=0nAixik，k=0,1n，abxm+1dxi=0nAixim+1 插值型求積公式abfx=dxi=0nAif(xi)求積系數(shù)公式：Ai=ablixdx，i=0,1n Newton-Cotes（等分） 梯形求積公式（n=1），具有1次代數(shù)收斂精度abfxdxb-a2fa+fb 誤差公式：E1f=-b-a312f''() 拋物型求積公式（

18、Simpson求積公式，n=2），具有3次代數(shù)收斂精度abfxdxb-a6fa+4fa+b2+fb 誤差公式E2f=-b-a52880f（4）() Newton求積公式（Simpon3/8法則） 具有3次代數(shù)收斂精度Nfb-a8fa+3fa+h+3fa+2h+fb，h=b-an Cotes求積公式（n=4），具有5次收斂精度abfxdxb-a907fa+32fa+h+12fa+2h+32fa+3h+7fb，h=b-an 誤差公式E4f=-2（b-a)945(b-a4)6f（6）() 節(jié)點(diǎn)數(shù)為奇數(shù)時(shí)，代數(shù)精度為n;為偶數(shù)時(shí)，代數(shù)精度為n+1。代數(shù)精度都是奇數(shù)。 復(fù)化梯形求積公式：Tnf=h2fa

19、+2i=1n-1fxi+f(b) 截?cái)嗾`差：Ern(f)=-b-a12h2f''() 復(fù)化Simpson公式：Snf=h6fa+2i=1n-1fxi+4i=0n-1fxi+12+f(b) 截?cái)嗾`差：Esnf=-b-a2880h4f4() 復(fù)化Cotes求積： Cnf=h907fa+14i=1n-1fxi+32i=1n-1fxi+h4+12i=1n-1fxi+h2+32i=1n-1fxi+3h4+7fb 截?cái)嗾`差：Ecnf=-2b-a945h46f6() 若一個(gè)復(fù)化積分公式的誤差滿足 limh0Rfhp=C<且C ¹ 0，則稱該公式是 p 階收斂的。 復(fù)化求積公式

20、（需要2n+1個(gè)求積節(jié)點(diǎn)） Romberg求積算法：Sn=43T2n-13TnCn=1615S2n-115SnRn=6463C2n-163Cn 復(fù)化梯形求積公式：T2nf+13T2nf-Tnf=Sn(f) 復(fù)化Cotes求積公式：C2nf+163C2nf-Cnf=Rn(f) Gauss型求積公式： 內(nèi)積公式：p,n+1=abpxn+1xxdx 截?cái)嗾`差：Enf=f2n+1()2n+2!abn+1x2xdx，（a,b） 高斯求積公式代數(shù)精度為2n+1 Gauss-Legendre求積公式（注意區(qū)間（-1,1），變換可得）：形如：-11fxdxi=0nAif(xi)求積系數(shù)可通過代數(shù)精度或插值型求積公式求積系數(shù)公式求出，亦可由下式求得：Ai=21-xi2pn+1'x2，i=0,1n