数值计算复习要点

数值分析复习要点引论1数值计算研究的对象与特点计算方法研究的对象是专门研究各种数学问题的计算机解法(数值解法)，包括方法的构造和求解过程的理论分析及软件实现，包括方法的收敛性、稳定性以及误差分析等.计算方法即具有纯数学的抽象性与严密性的特点，又具有应用的广泛性与实验的技术性特占八、、•2误差的概念2.1误差的来源模型误差：数学模型的解与实际问题的解之间出现的误差，称为模型误差.测量误差：在测量具体数据时产生的误差称为测量误差.截断误差：数学模型的准确解与数值方法的准确解之间的误差称为截断误差舍入误差：由于计算机字长的限制而产生的误差，称为舍入误差.2.2误差的度量.绝对误差与绝对误差限.相对误差与相对误差限.有效数字2.3误差的传播和、差的误差限不超过各误差限的和.积、商的相对误差限不超过各相对误差限的和.3数值计算的若干原则避免两相近数相减和绝对值太小的除数、简化计算步骤、使用数值稳定的算法方程求根1二分法用二分法求方程f(x)=0的实根x*的近似值，其主要思想是:将含有根x*的隔离区间二分，通过判断二分点与边界点函数值的符号，逐步对半缩小隔离区间，直到缩小到满足精度要求为止,然后取最后二分区间的中点为根x*的近似值.2迭代法一般地，为了求一元非线性方程f(x)=0的根,可以先将其转换为如下的等价形式x= )然后构造迭代公式.x =^(x)k=0,1,2 k+1 k3收敛性和收敛速度(收敛性基本定理)的条件和结论收敛速度的快慢可用收敛阶来衡量•收敛速度的快慢可用收敛阶来衡量•(收敛阶)设序列匕收敛到x*，并记误差e=1x—x*I.若存在常数p>1和c丰0，使得：lim-krr=ckk 5epk则称序列lx 是p阶收敛的，当p=1时,称为线性收敛，当p>1时,称为超线性收敛,kk=0当p=2时,称为二次收敛或平方收敛.4牛顿迭代公式及其收敛性牛顿迭代公式xk+1=xk一树k=0丄2…牛顿法的收敛性设x*是方程f(x)=0的单根，并且f〃(x)在x*的邻域上连续，则牛顿迭代法(3.4.1)至少平方局部收敛.解线性方程组的直接法1高斯消去法消元过程为：对k=1,2,…,n—1逐次计算:l=a(k—1)/a(k—1),(i=k+1,•…，n)ikik kka(k)=a(k—1)—la(k—1),(i,j=k+1,…，n)ij ij kjb(k)=b(k—1)—lb(k—1),(i=k+1,…，n)i i ikk回代过程：逐步回代求得原方程组的解x=b(n—1)/a(n—1)n n nnx=(b(k—1)一工a(k—1)x)/a(k—1),(k=n一1,n一2,•…,1)kk kjjkkj=k+1高斯消去法的乘除法总计算量为：131261211321

n3+n2—n+n2+n=n3+n2—n3 2 52 23 32高斯一约当消去法约当消去法的计算过程为:对于k=1,2,…,n计算：a(k)=a(k—1)/a(k—i)(j=k+1,•…,n+1)kj kj kka(k)=a(k—1)一a(k—1)xa(k)(i=1,2,…,n且i丰k;j=k+1,k+2,…,n+1)Iij ij ik kj乘除法的总次数为：—n3+—n2.22它比高斯消去法的计算量大，但不需要回代过程3向量和矩阵的范数、条件数

向量范数:1范数 卜II=£|x| 2范数 ||x||=（£|x|）12 3范数 ||x||二max|x1 i 2 i 3 1<i<n'i=1 i=1矩阵的范数设x为n维向量，A为n阶方阵，则算子范数：llAll=max A的行范数。3 1<i<n’ijj=1llAll=max A的列范数。1 1<j<ni=ij设A为n阶可逆矩阵,则称数Cond（A）=||a』・||a||为条件数：Cond(ACond(A)=||a|-||A-i||3 3Cond(A)=IIa!」A-i||1 i iCond(A)=IIaI-I|a-1||2 2 2分别称为A的3-条件数,1-条件数，2-条件数解线性方程组的迭代法1雅克比迭代法的迭代公式:X(k+1)iaX(k+1)iaiiI厶ax(k)+bijJij=1，j主i 丿矩阵形式：X(k+1)=BjX(k)+fBJ=I—D-1A，打=D-1b2高斯一赛德尔迭代法迭代公式为:X(k+1)iX(k+1)i1aiiIy—Jax(k+1)—

ijjv j=1Max(k)+bijjij=i+1 丿G=1,2, ,n)B=(D-AuG-B=(D-AuG-S=(D-L)-1bx(k)—x(k-1)||x(k)-x*||<IIBIkx⑴一x（0）成矩阵形式x(k+1)=B x(k)+fG-S JG-S3迭代法的收敛性判断（迭代法收敛的基本定理）设有n阶方程组x=Bx+f,对于任意初始向量x（0）和右端项f，迭代法收敛的充分必要条件是迭代矩阵的谱半径p（B）<1.（迭代法收敛的充分条件）若IIBII<1，则由迭代公式（5.1.3）所产生的向量序列敛于方程组x=Bx+f的精确解x*,且有误差估计式(充分条件)若线性方程组Ax=b的系数矩阵为严格对角占优或不可约弱对角占优矩阵，则雅克比和高斯一赛德尔迭代法收敛。函数插值1插值的基本概念包括线性插值、抛物插值和多项式插值的存在惟一性。2拉格朗日插值X一Xj)y.X一X一Xj)y.X一X.

iji=0j=0j丰i3插值余项与误差估计若f(X)在［a,b］上的插值多项式为L(X)，则称R(X)=f(x)-L(x)为L(x)的插值余项n n n n(也称误差)。设f(X)在［a,b］上的n+1阶导数连续，记为f(x)eC"+i［a,b］且f(x)在互异节点(z=0,1,2,…，n)a<x0<X1<•••<x<b的函数值为y0,yi(z=0,1,2,…，n)0 1 n 0 1 n nz z的插值多项式为L(x)，则对Vxe[a,b]有：nnnt+f (x-Xj)=fn+f-n+1(x)nnj=0其中a<g<b，w.(x)=A(x一x)n+1 jj=04牛顿插值Nn(x)=f(x0)+f(x0,x1)(x-x0)+…+f(x0,X],…,xn)(x-x0)(x-X]”・(x-xn一])数值积分1代数精度的概念及其求法。若数值求积公式对被积函数f(X)=1,X,…,xm都能精确成立，而对被积函数f(X)=xm+1不能精确成立，则称求积公式具有m次代数精度。2牛顿一柯特斯公式I(f)J"/(x)dx=(b一a)工C〉n)f(x.)a i=0C(n)=(T"Jnn(t-j)dti n-i!(n-i)!0j=0j*i

梯形求积公式I(f)-T=上卫f(a)+f(b)]21抛物线求积公式或辛普生求积公式 I(f)-S=口6梯形公式的截断误差R/f)=f⑴Jb(x-a)(x-b)dx=-f"")(b-a)3，neC,b)2 a 123复合梯形求积公式将la,b〕区间n等分，记分点为x.=a+ih, (h=-~—,i=0,1,—,n)1 n并在每个小区间L,x]上应用梯形公式得:ii+1\bf\bf(x)dx=艺Jxi+if(x)dx〜艺|[f(x)+f(x.書)]i=0i=0f(a)+2灯f(x.)+f(b)i=1复合梯形公式的截断误差 R复合梯形公式的截断误差 R(f)=-nb12ah2广'(1) ，ne(a,b)4复合辛普生求积公式在每个小区间lx,x]上，用辛普生公式得:ii+1S=-f(a)+&f(xJ+2艺f(x.)+f(b)i=0i+i=0i+2i=1其中x 为[x,x]的中点，即x=x+hii+1 .丄 ii+ z+225高斯求积公式若有一组节点xo,再,…,xe[-1,1],使插值型求积公式(8.5.1)具有2n+1次代数精度，则称此组0 1 n节点为高斯点，并称相应的求积公式为高斯型求积公式。常微分方程初值问题的数值解法1欧拉公式包括显式、隐式、两步、改进的欧拉公式和梯形公式。欧拉公式y =y+hf(x,y)n+1n nn隐式欧拉公式yn+1=yn+hf(J，儿+1)为梯形公式yn+1=yn+j[f(xn,儿)+f(i+1,儿+1)]改进的欧拉公式yn+1=yn+2[f(xn'儿)+f(3+1,打+hf(S'打))]

两步欧拉公式y =y +2hf(x,y)n+1 n—1 nn2单步法的局部截断误差和方法的阶设y(x)是微分方程的精确解，则T+1=y(Xn+1)—y(Xn)— (Xn，"n+1，y(Xn)，y(S+1)，h称为单步法的局部截断误差。如果求微分方程数值方法的局部截断误差是T=O(hp+1)，其中p>1为整数，则称该方法n+1是p阶的，或该方法具有p阶精度。p越大，方法的精度越高。含hp+1的项，称为该方法的局部截断误差主项。欧拉公式是一阶方法，其截断误差主项为聖y〃(x)。2n隐式欧拉公式也是一阶方法，它的主项是—竺y〃(x)2n梯形公式是二阶方法，其局部截断误差为—h3y'"(x).12n可以证明，改进的欧拉方法也为二阶方法。3四阶龙格一库塔方法hy=y+-(k+2k+2k+k)

，n+1 ，n6'1 2 3 47k=f(x,y)4阶经典R—K方法形式为:4阶经典R—K方法形式为:k2=f(xn+2,yn+2k1)k=f(x+—,y+—k)3 n2n2 2k4=f(xn+h,yn+hk3)4单步法的收敛性和稳定性若求微分方程的一种数值方法对于任意固定的x=x+nh,当hT0(同时n)时,有n0yTy(x),则称该方法是收敛的。n nEuler方法是收敛的梯形公式是收敛的改进的Euler方法也是收敛的若用某一数值方法计算y时，所得到的实际计算结果为~，且由扰动5=|y—~|引起n n nnn以后各节点y(m>n)的扰动为5，如果总有15|<|5|,则称该方法是稳定的。m m mn单步法的稳定区间方法Euler方法Euler法—2<hX<0改进的Euler法4改进的Euler法4阶R—K法1+”人+血+血+辿2! 3! 4!—2<—0—2.7