计算方法总结_部分

数值计算方法内容总结*0总述计算方法是设计求数学问题的数值近似解方法的一门学科.在总述中,约定:设x为准确值,x为x的一个近似值.0.1误差称e=xx为x的绝对误差.若jej,称为x的一个绝对误差限.称如下定义的er为相对误差.若jerjr,称r为x的一个相对误差限er=ex=xxxxxx0.2有效位数如果jej不超过x的某一位的半个单位,从这一位起直到前面第一位非零数字为止所有的数字的个数为n,称x(作为x的近似值)有n位有效数字.0.3计算中应注意的几点1.防止两个相近的数字相减—否则相对误差较大.2.避免很小的数做分母—否则绝对误差较大.3.防止大数‘吃’小数—改进算法,提高精度.4.尽量减少总的运算次数.5.设计稳定的收敛算法.1插值1.1定义f为[a;b]上的函数,x0;x1;


;xn为该区间上互不相同的点.给定函数类,若有ϕ2,满足:ϕ(xi)=f(xi)(0in)则称ϕ(x)为f(x)关于节点x0;x1;


;xn在上的插值函数.1.2多项式插值的基本原理取的一个n+1维子空间,基为:ϕ1;ϕ2;


;ϕn+1.则2.1中ϕ存在唯一的充要条件是:ϕ1(x0)ϕ2(x0)


ϕn+1(x0)ϕ1(x1)ϕ2(x1)


ϕn+1(x1)............ϕ1(xn)ϕ2(xn)


ϕn+1(xn)̸=0*2012级近代物理系罗弋涵,如有错误请联系我,E-mail:[e-mail]显然多项式基满足此条件.1.3Lagrange插值寻找满足li(xj)=ij的基如下形式:li(x)=∏0kn;k̸=ixxkxixk则ϕ(x)=Ln(x)=∑0inf(xi)li(x)li与xi之间的转换矩阵的求法:对f(x)=xk进行Lagrange插值即可.即:0BBBB@1x...xn1CCCCA=0BBBB@11


1x0x1


xn............xn0xn1


xnn1CCCCA0BBBB@l0l1...ln1CCCCA注意:li仅与xi的选取有关.误差:定义为Rn(x)=f(x)Ln(x),若f2Cn+1[a;b],则Rn(x)=f(n+1)()(n+1)!(xx0)(xx1)


(xxn)其中:2[minfx;xig;maxfx;xig],这是因为当x不同时,Rn中的取值亦不同.事后估计:当jfn+1(x)j较大且缓变时,分别以fxig0in;fxig1in+1做插值节点,得到L(1)n;L(2)n,由R1/R2知:f(x)L(1)nxx0xxn+1(L(1)nL(2)n)1.4Newton插值1.4.1插值形式的构造构造插值多项式如下形式:Nn=a0+a1(xx0)+a2(xx0)(xx1)+


+an(xx0)(xx1)


(xxn)系数为ai=f[x0:x1;


;xi]差商:定义一阶差商为f[x0;x1]=f(x1)f(x0)x1x0归纳定义:f[x0;x1;


;xk]=f[x1;


;xk]f[x0;x1;


;xk1]xkx0可利用下表来进行计算误差:Newton插值的误差公式和Lagrange插值等价,但是有另一种表达形式:Rn(x)=f[x0;x1;


;xn;x](xx0)(xx1)


(xxn)由两种插值的余项完全一致,可得差商性质f[x;x0;x1;


;xn]=f(n+1)()(n+1)!其中:2[minfx;xig;maxfx;xig].xif(x1)一阶差商二阶差商三阶差商


n阶差商x0f(x0)x1f(x1)f[x0;x1]x2f(x2)f[x1;x2]f[x0;x1;x2]...............xnf(xn)f[xx1;xn]f[xn2;xn1;xn]f[xn3;xn2;xn1;xn]


f[x0;x1;


;xn]1.4.2差商的性质1,f[x0;x1;


;xn]可表示为f(xi)的线性组合,可由对比n阶Newton插值和Lagrange插值的最高次项系数得到.f[x0;x1;


;xn]=∑0inf(xi)∏j̸=i(xixj)2,差商值与中括号中项的顺序无关.3,若f为n次多项式,则f[x;x0;x1;


;xk1]为nk(kn)次多项式.若kn,此式为0.1.5Hermite插值给定f2C1[a;b],定义f关于节点fxig0in的(二重密切)Hermite插值为H(x),它是一个2n+1次多项式,满足{H(xi)=f(xi)H′(xi)=f′(xi)基函数法:构造基fgi;hig0in满足:{gi(xj)=ijg′i(xj)=0{hi(xj)=0h′i(xj)=ij则:H(x)=∑0inf(xi)gi(x)+∑0inf′(xi)hi(x)差商法:将有直到k阶导数信息的节点当作k+1重节点(离的非常近的k+1个不同节点).误差:其余项为R2n+1=f(2n+2)()(2n+2)!(xx0)2(xx1)2


(xxn)21.6分段低阶插值增加节点数目不一定能够提高插值函数的近似程度,当插值函数阶数较高时,插值函数震荡严重(Runge现象).将区间分割后在每个小区间上分别插值是一个好的解决方法.1.6.1分段线性插值将区间[a;b]做分割:a=x0x1


xn=b,在[xi;xi+1]上线性插值得pi(x)=f(xi)xxi+1xixi+1+f(xi+1)xxixi+1xi则P(x)=pi(x)(xixxi+1)称作f关于上述节点的分段线性插值.误差:每段上的误差即为一阶线性插值的误差,设M2为f′′(x)在[a;b]上的上界,则分段线性插值的误差限为:jf(x)P(x)jM22(xi+1xi2)21.6.2三次样条插值利用不超过三次的多项式,满足全局二阶光滑的一种分段插值.注意到,端点能提供2n个约束条件,段间连接点一二阶导数连续提供了2(n1)个约束条件,但是决定三次样条插值共需要4n个参数,所以需要更多的两个约束,可加入端点处的一阶或二阶导数值来限制.设区间[a;b]的分割为a=x0x1


xn=b,Si(x)为区间[xi;xi+1]上的样条插值函数.M关系式:将样条函数连接处二阶导数值记为Mi(1in1),端点处样条函数二阶导数值设为S′′(a)=M0;S′′(b)=MnM0=Mn=0称作自然边界条件;S′′(a)=f′′(x0);S′′(b)=f′′(xn)称为固支边界条件.对S′′(x)做分段线性插值,两次积分产生2n个系数,利用2n个端点取值约束得到用Mi表示的S(x).此S(x)中含有n1个未知参数,即Mi(1in1),利用n1个连接处一阶导数连续的约束可解出.样条函数如下:Si(x)=(xi+1x)36hiMi+(xxi)36hiMi+1+f(xi)(xi+1x)+f(xi+1)(xxi)hihi6((xi+1x)Mi+(xxi)Mi+1)称下式为M关系式:iMi1+2Mi+iMi+1=di其中hi=xi+1xi;i=hihi+hi1;i=1i;di=6f[xi1;xi;xi+1]m关系式:将样条函数连接处一阶导数值记为mi(1in1),端点处样条函数一阶导数值设为S′′(a)=m0;S′′(b)=mn.与M关系式类似地,利用Hermite插值,得到用m表示的样条函数,利用二阶导数连续定出m(1in1)的值.样条函数如下:Si(x)=(12(xxi)1xixi+1)(xxi+1xixi+1)2f(xi)+(12(xxi+1)1xi+1xi)(xxixi+1xi)2f(xi+1)+(xxi)(xxi+1xixi+1)2mi+(xxi+1)(xxixi+1xi)2mi+1称下式为m关系式:imi1+2mi+imi+1=ci其中hi=xi+1xi;i=hihi+hi1;i=1i;ci=3(if[xi1;xi]+if[xi;xi+1])2数值微分与数值积分2.1数值微分2.1.1差商向前差商:f′(x0)f(x0+h)f(x0)h,其误差为R(x)=h2f′′()O(h).向后差商:f′(x0)f(x0)f(x0h)h,其误差为R(x)=h2f′′()O(h).中心差商:f′(x0)f(x0+h)f(x0h)2h,其误差为R(x)=h26f′′′()O(h2).实际计算时应注意步长的选取,采用事后估计,即:给定精度,分别取h;h/2步长计算差商,若jD(h)D(h/2)j,则h/2为合适步长.2.1.2插值型数值微分以Lagrange插值为例,插值型数值微分即用L(k)n(x)近似f(k)(x).其插值点处一阶导数的误差为:R′n(xi)=f(n+1)()(n+1)!∏j̸=i(xixj)2.2数值积分2.2.1基本概念数值积分,即用一些离散点上函数值的线性组合近似求解积分的方法,如下式,其中i成为积分系数.In(f)≜n∑i=0if(xi)∫baf(x)dx≜I(f)若对于f=xk,k当且仅当满足0km时都有In(f)=I(f)(存在f2P(m+1)使此式不成立),则称积分公式In有m阶代数精度.n+1个积分节点的数值积分公式,通过选取适当的积分系数fig可达到n阶代数精度,积分系数由积分节点fxig的选取唯一确定.2.2.2插值型数值积分利用f关于节点fxig的n阶插值函数Ln所求得的积分近似.积分系数可选为=∫bali(x)dx此积分公式拥有至少n阶代数精度.2.2.3Newton-Cote’s积分选取积分区间上等距点作为积分节点的插值型数值积分称为Newton-Cote’s积分.其积分系数为i=(ba)(1)nii!(ni)!n∫n0t(t1)


(ti+1)(ti1)


(tn)dt其误差为:8:En(f)=Kn(n+2)!f(n+2)();Kn=∫bax!n(x)dx0;n=2kEn(f)=Kn(n+1)!f(n+1)();Kn=∫ba!n(x)dx0;n=2k1可见奇偶性的差别.梯形积分公式:Newton-Cote’s积分中取n=1即可,它有一阶代数精度.T(f)=ba2(f(a)f(b))误差:E1(f)=(ba)312f′′()2[a;b].Simpson积分公式:Newton-Cote’s积分中取n=2即可,它有三阶代数精度.S(f)=ba6(f(a)+4f(a+b2)+f(b))误差:E1(f)=(ba)52880f(4)()2[a;b].2.3复化数值积分复化数值积分即分段插值函数的积分.2.3.1复化梯形积分令h=(ba)/n;xi=a+ih(i=0;1;


;n),其数值积分公式为:Tn(f)=h2(f(a)+2n1∑i=1f(xi)+f(b))误差:En(f)=(ba)312n2f′′().2.3.2复化Simpson积分令h=(ba)/2n;xi=a+ih(i=0;1;


;2n),其数值积分公式为:Sn(f)=h3(f(a)+4n1∑i=0f(x2i+1)+2n1∑i=1f(x2i)+f(b))误差:En(f)=(ba)52880n4f(4)().2.3.3Romberg积分为了进一步地提高积分精度,考察复化梯形积分公式和复化Simpson积分公式的误差项:I(f)T2n13(T2n(f)Tn(f))I(f)S2n115(S2n(f)Sn(f))复化梯形积分公式加其误差项作为新的近似值得到复化Simpson积分公式:I(f)T2n(f)+13(T2n(f)Tn(f))=Sn(f)同理,复化Si