数值分析课件2015xin王兵团-数值分析整理

1、数值分析1 .数值分析的病态性是指因初始数据的微小变化，导致计算结果的剧烈变化。病态问题：因初始数据微小变化，导致计算结果剧烈变化的问题良态问题：初始数据微小变化，只引起计算结果微小变化的计算问题。数值不稳定算法：指算法进行计算的初始数据有误差，而计算过程中产生的舍入误差不断增长。例子2 .误差的来源：模型误差：在数学建模时，由于忽略了某些次要因素而产生的误差；观测误差：在采集原始数据时，由仪器的精度或其他客观因素产生的误差；截断误差：对产与计算的数学公式做简化处理后所产生的误差；舍入误差：计算机因数系不全，由接受和运算数据的舍入引起的误差。科学计算中值得注意的地方：避免两个相近的数相减；合理

2、安排量级相差很大的数之间的运算次序，防止大数吃小数；避免绝对值很小的数做分母；简化运算步骤，减少运算次数。3 .用计算机做科学计算时的溢出错误。机器数系是有限的离散集，机器数系中有绝对值最大和最小的非零数 M 和 m,若一个非零实数的绝对值大于 M,则计算机产生上溢错误，若其绝对值小于 m,则计算机产生下溢错误。上溢错误时，计算机中断程序处理；下溢错误时，计算机将此数用零表示并继续执行程序。4 .解非线性万程f(x)=0单根的牛顿法具有二阶收敛。简单迭代法具有一阶收敛性。当f(X)10且有 2 阶导数时，Newton 迭代法才有二阶敛速。5 .又 t(n+1)个节点的 Newton-cotes

3、 求积公式，在n7时，Cotes 系数大于 0,而在n7时，考虑到公式的稳定性不实用该公式。6 .当系数矩阵 A 是严格对角占优矩阵，Jacobi 格式、Seidel 格式都收敛。7 .用高斯消元法求解线性方程组，一般使用选主元的技术是因为要减少舍入误差。8 .解非线性方程组迭代法的整体收敛和局部收敛的主要区别是局部收敛在较小邻域内取初值，有初值限制。9 .二分法是全部收敛，简单迭代法是局部收敛。10 .四种插值方法：Lagrange 插值、Newton 插值、Hermite 插值、分段多项式插值。11 .截断误差是对参与计算的数学公式作简化处理后所产生的误差，在所学的数值方法中插值和数值积分

4、都涉及截断误差处理的内容，分别为插值余项和积分余项。例：ex=1+*+无穷项相加我们用ex=1+x+L+匕近似计算ex就产生截断误差。2!n!2!n!12 .线性方程组迭代解法的基本思想是将现行方程组作等价变形，得到同解的易于作迭代计算的线性方程组，用计算出的迭代序列来逼近解。考虑线性方程组Ax=b及由次方程组构造的迭代格式x(k+1)=Bx(k)+g,判断此迭代格式的收敛方法有：(1)若r(B)1,则迭代格式收敛；(2)若|B|1,则迭代格式收敛，IB|是矩阵 B 的某种算子范数；(3)若矩阵 A 是严格对角占优矩阵，则线性方程组Ax=b的 Jacobi 迭代和 Seidel 迭代对任意初值

5、都收敛；(4)若矩阵 A 是对称正定矩阵，则线性方程组Ax=b的 Seidel 迭代对任意初值都收敛；(5)Sor 法收敛的必要条件是松弛因子w满足0w2。13.Newton 迭代公式的收敛条件：(1)f(a)Xf(b)0,则迭代公式产生的数列 14.引入分段插值的原因及目的。Runge 现象：随着节点 n 的增加，误差不但没减小，反而不断增大。原因是当节点 n 较大时，对应的是高次插值多项式，而高次多项式的舍入误差是随次数的增加而不断变大的，用高次多项式插值作数值计算时舍入误差将淹没”了增加节点提高的精度。Runge 现象否认了用高次插值公式提高逼近精度的做法，因此引入了分段插值法。定义如下

6、：町x?a,b?定收敛于阴,b?上的为一根x18.2 点 Newton-Cotes 公式【梯形公式】bb-a0f(xx?丁尹(a)+f(b)?b-a6,?a+b?，、立丁”)+4f?+f(b)?取华,b?上的n+1个节点xk：a=x0 x1Vx2V卜？为力?复化 Simpson 公式:Sf(xx?b6a；f(a)+f(b)+4?/:?+2?f(xk6n?、，k=0e2?k=1，？44余项：R(f,Sn)二-?h?f(4)(h)=-(一a)f(4)(h),h?a,b?()180?2?()2880()?19.插值与拟合的区别。插值与拟合都是有一组数据点构造一个近似函数，但他们的近似要求不同。二者都

7、属于函数逼近范畴。插值函数在几何上的描述为过所有给定数据点集散点图的任何一条曲线。插值是对个互异的点x0,x1,x2，xn及各个点对应的函数f(x0),f(x,),f(x2)；,f(xn)f区间？a,b?上的 n+1找出f(x)的一个近似函数P(x),使得P(xi)=f(xi),P(x)即为插值函数。拟合函数在几何上的描述为穿越所有给定数据点集散点图的任何一条曲线。拟合是对f(x,区间?a,b?kb的 n+1个点x0,x1,x2，xn(不一定互异)，根据各个点对应的函数f(x0),f(x1),f(x2,.，f(xny出的点图来选择用什么类型的函数做逼近函数j(x),逼近函数j(x)通过件获得，

8、则这样求出的j(x)称为拟合函数。min|d|,d=&Jdj,di=f(x)j0)的拟合条20.Lagrange 插值步骤：利用互异插值节点x0,x1,x2，xn,算出插值基函数lin(x),i=0,11，n；利用插值基函数构造插值多项式Ln(x)o优点：利用插值基函数很容易得到 Lagrange 插值多项式，公身构紧凑，在理论分析中很方便。3 点 Newton-Cotes 公式【Simpson 公式】：b0f(xx?n次Lagrange插值多项式至少需要n+1个插值节点数据。 与其相比，Newton插值具有承袭性和易于变动节点的特点。21 .L-插值和 N-插值的异同。/、n?x-x

9、k?/、nn?x-xk?FWlin(x)=?-Ln(x)=?V?一k=0,k1iCxi-xk?i=0k=0,k1iCxi-xk?nwn+1(x)=?(x-xk)，xk?a,b?kk=0、N- 插 值f?x0,x1,x2；,xn?=?fd)=f(n)(x)余 项 ：E 二f?x0,x1；L,xn,x?wn+1(x)-i=0Wn+1(x)n!f(x)=f(%)+f?x0,x1?(x-x0)+f?x0,x1，x2?(x-x0)(x-x1)+f?x0,x1，x2；,Xn%X-4系-%)(x-Xn-1)同:Ln(x)=Nn(x余项 R，6)=En(x);表达式均为基函数的线性组合。异：L-基与 N-基不

10、同；计算 L-插值主要计算基函数，计算 N-插值主要计算组合系数或各阶商差;高次 N-插值包含低次 N-插值，而 L-插值不然。22 .数值分析中，线性方程组的数值解法主要分为直接法和迭代法两大类。直接法使用有限次计算就能求出线性方程组“准确解”的方法，这里的“准确解”是指在求解过程中不考虑舍入误差影响得出的解。迭代法是由线性方程组构造出迭代计算公式，然后以一个猜测的向量作为迭代计算的初始向量，逐步迭代计算,来获得满足精度要求的近似解，是一种逐次逼近的方法。23 .三对角线性方程组用追赶法计算求解效果最好，对称线性方程组用LDLT法。24 .若 n 点的求积公式具有 2n-1 次的代数精度，则

11、称该求积公式为 Gauss 型求积公式。n 点插值型求积公式的代数精度至少是 n-1,至多为 2n-1。【注意：若下标从 1 开始，则代数精度为 2n-1,若下标从 0 开始，则代数精度应为 2n+125 .刿断迭代的收敛险二.写出迭代方程计算各阶导数，判断各阶导数在根处是否为 0,若j(n)(x)10,则最高为 n 阶收敛。判断求积公式的代数精度：取f(x)=xk，k=0,1，代入R(xk)=f(x,x-V,验证R(xk)=0是否成立,R(x0)=R(x1)=R(x2)=-L=0,第一个使R(xk)10的 k 值，则对应的代数精度为 k-1。26 .求微分方程初值问题的 Euler 方法的绝

12、对稳定域是1+lh1,绝对稳定区间是f2,0?。lin(x产部要随之变化，在实际计算中很不方便。缺点：当插值节点增减时,余项：Rn(x)=f+1(x)Wn+1(xYx?,b中:(n+1)第一章绪论.*i,绝对误差e:e=x-x绝对误差限e:e=x-xe.*相对误差er：*一*ee=r岂相对误差限2,绝对误差计算公式:*er:一*ee(xy)=e(x)e(y)e(x内)*?y*?y?笠户即汽方?ye(x)-,*xe(y3,相对误差计算公式:er*.*yxe(x)ye(y)xxy.，*、4,绝对误差：e(x)=dx相对误差:e(V)=e(abc)=?V?ae(a)+?V?b&(y)*?x?

13、*4(xy)?er(x)+(y)er?T?er(x)*e(x)dx/=dInxxx(b)+?c?V?V(c)e(/)=e(abc)=e(a)+瓦e*er(y)?V(b)+?ce(c)5,有效数字:0.510mhn,则称x*有 n 位有效数字。若x*有 n 个有效数字，则*.x的相对误差为:12a11-n10；若x的相对误差为:eg)1，101-n，贝1x*有n2(ai+1)个有效数字。第二章非线性方程的球根方法i.二分法：精度 e,X-xke,1/、ln(b-a)-Ine产(b-a)1nj-1xk-xk-1e2,简单迭代法：将f(x)=0转化为不动点方程x=j(K),构造迭代公式xk+1=j公

14、式求的：=j(%),x2二je)，？收敛判别一:一当x?a,b?f寸，有j(x)?a,b?；任取x1,x2?a,b尹在与(xk),取定一个初值x1,x2无关的正常数x0,由迭代L1,满足j(X)-j(x2)Lxx2，则j(x户？a,b?中有唯一的不动点x*,且迭代公式xk+1=j1寸任取的_一*x0?a,b夕产生的数列都收敛于x。可替换为:j(x)L1,x?a,b夕定理同样成立x*是j(x)的不动点，j(x)在x*处连续,j(x)1时，xk+i误差估计式:精度e,Xr-xkLk-xke,1-xi-x01Ht,xk+i=j(xk)0?InLxk-xk-ief(a)X(b)0,f(xp再b?上不变

15、号;x?a,b0j(x)?%,b夕j(x)L1；迭代求解，用xk-xk_1e判断。收敛判别：f(x)?C2?a,b?x满足下列三个条件：当f(a)X(b)0,则迭代公式产生的数列xk，一定收敛于?a,b?止的唯一根第三章线性方程组的解法1.数值分析中，线性方程组的数值解法主要分为直接法和.迭代法的人类直接法使用有限次计算就能求出线性方程组“准确解”的方法，这里的“准确解”是指在求解过程中不考虑舍入误差影响得出的解。?xn(k+1)=1为1，1)-f/)?ann步骤：说明方程在所取区间内有唯一解:证明采取的迭代公式具有收敛性:3.判断迭代的收敛阶：写出迭代方程计算各阶导数,判断各阶导数在根处是否

16、为 0,若j(n)(x)l0,则最高为 n 阶收敛。步骤：确定迭代格式：xk+1=j(xk)；据已知条件建立方程组：f(x)=0,f求出未知系数，建立迭代公式，计算f(n)*1(x)=0,?；(x*)10,则迭代收敛阶最高为4.Newton 迭代法：xk+1=xk-frXkf(Xk)当f(x)10时，且有二阶导数，则至少是平方收敛,否则为线性收敛。(x)存在且在?a,b?上不变号;迭代法是由线性方程组构造出迭代计算公式,然后以一个猜测的向量作为迭代计算的初始向量,逐步迭代计算,来获得满足精度要求的近似解，是一种逐次逼近的方法。2.迭代法：i(k+1)?x()(k)(k)(k)x-42x()-a

17、13x()-amxi)?xT1)?x2Jacobi 迭代法：(2-通炉一a23镇-也即)x)?b-?ajx%=1,2,，naii6j=1,j1i?-an*)-42婷-ann-1淄)Ax=b(D-L-U)x=bx(k+1)=D-1(L+U)x(k)+D-1bBJ=D1x(k+1)-工加 ax(k)x)aX、?x1-b1-a12x2-a13x3-anxnI?a11()(L+U)gj=D-1bSeidel 迭代法:?(k+1)1(k+1)().)?=就2-ML.-a2n巧(k+1).1?i-1aH?-?j=1n，adj。)-?axf)j=i+1(D-L)x(k+1)Sor 迭代法：以=Ux(k)+b

18、x(k+1)=(D-L)1Ux(k)+(D-L)1bBs=(D-Seidel 迭代法为基础，可以改变收敛速度。-1L)Ug-1S=(D-L)bX”)-x=x+1)i-1x(k+1)=(1-w)x(+1)+w?bi-?a*aaiiej=1A)？?2凶，+1=1,2,nj=i+1?(k)-1=(D-WL)於u+(1-w)D?x，+(D-WL)WbBw=(D-WL)?Wu+(1-w)D?gw=(D-wL)wb3.判断收敛性：当不能用范数或者矩阵本身性质判定时:Grout 分解:LDU 分解:37 .LDLT法：专用于对称线性方程组，计算量为n。4A=AT,A=LDU,AT=(LDU)=UTDLT=L

19、DU=A,由矩阵 A 的 LDU 分解的唯一性可得U=LT，Ly=b,Dz=y,L,x=z,fAie其中：A=D-L-UD=1a22ann00an20口60a12ain立nueu0%=_00a2n口ue；:口ue,u0?000?r(BJ)I,则 Jacobi 迭代收敛对 Seidel,求特征值,det(I-BS)=0,即det(D-L)-U)=0,r(BJ)=林家k,若r(BJ)1,贝u迭代收敛。4.范数：列范数:nnlAli=max?%I；行范数:|AY=max?ai=ij=i2 范数：|A2=、：max,lmax是ATA最大特征值。特征值:5.Gauss 消元法：消元过程一一回代过程，计算

20、量为+n2-33适用条件：Ax=b的系数矩阵 A 的顺序主子式都不为 0。ml-A=0求得的 m 即为 A 的特征值。消=3(|2-i)+2(n-1)；N回=(n+i)列主消元法和全主消元法(首选)6.LU 分解法：Ax=b，将系数矩阵分解为下三角矩阵 L 和上三角矩阵 U 的乘积。LUx=b,Ly=b,Ux=yDoolittle 分解：非奇异矩阵A 的 Doolittle 分解是唯一的、u,u,u,u,u,u?加：uau2222MU2U2Mo,He;?16see?-、u,u,uuu,u,u?nd d+2 2d d1d d对 Jacobi,对其求特征值,r(BJ尸段axlk，若;F 范数:22

21、22n2n2、u,u,u,u,u,u,u,u?nnn1ZTU2U21、u,u,u,u,u,u,u,u?8 .追赶法：求解三对角方程组的专用方法，计算量仅为个互异的点x01x11x2；,L,xn及各个点对应的函数f(x0),f(x),f住户，f(xn),找出f(x)的一个近似函数P),(Ki)=f(Ki),P(x)即为插值函数。个点毛凶42，xn(不一定互异)，根据各个点对应的函数f(x0),f(x1),f(x2)J,f(xny出的点图来选择用什么类型的函数做逼近函数j(x)，逼近函数j0)件获得，则这样求出的2. Lagrange 插值。/、n?x-xk?/、nn?x-xk?Iin(x)=?L

22、jn(x)=?yi?一k=0,k1iexi-xk?i=0k=0,k1iexi-xk?3. 商差表:xy一阶商差二阶商差?n 阶商差x0Nof?x0,X1?f?x0,X1,X2?f亦0,人，x2?x1y1f?X1,x2?f?x1,x2,x3?5n-4ebe1ea：三对角方程组的系数矩阵A:A=6eCib2c2UUUUU1P2an-1bn-1anCn-1bnu-eueu?u-eq11胫晔?jriq2r2qn-1JiqnUUUUUUUU4=6，rk=ck，Pk-ak/qk-1，qk-bk-pkc-19.条件数：设A?Rnn为非奇异矩阵，称Condp(A)=|A|p机为矩阵A 的条件数。矩阵的条件数可

23、反映系数的敏感性，其值越大，解对系数越敏感，因而方程组越病态。第五章插值与拟合方法1.插值与拟合的区别。插值与拟合都是有一组数据点构造一个近似函数，但他们的近似要求不同。二者都属于函数逼近范畴。插值函数在几何上的描述为过所有给定数据点集散点图的任何一条曲线。插值是对n+1使得P拟合函数在几何上的描述为穿越所有给定数据点集散点图的任何一条曲线。拟合是对f(x)在区间？a,b?止的 n+1过min|d|,d=&d)，di=f(xi)-j(xi)的拟合条j(x)秒为拟合函数余项：Rn(x)=fJ(，n+1/、-JLn+1)Wn+1(x)，x?(a,by中:nWn+1(x)=?(x-xk)，x

24、k?a,b?区间？a,b科的?Xn-2yn-2f?Xn-2,Xn-1?f?Xn-2,Xn-1,Xn?Xn-1yn-1f?xn-1,Xn?Xnyn4. Newton 插值7 .曲线拟合法一一最小二乘曲线拟合方法:步舞根据题意取基函数：屋的二xk，kWE建立 m 次曲线拟合函数：，j(x)=a0+aix+a2x2amxm;求建立法方程组：若题中有 c 组数据，则 n=c-i,法方程组如下:8 .最佳平方逼近：曲线拟合是用已知离散数据点来求拟合函数，若用已知连续函数取代离散数据去求拟合函数，则为nff?x0,Xi,X2,Xn?=?i=0Wn+1(x)n!余项：En(X)=f夕0,Xi；、Xn，X?W

25、n+l(X)f(X)=f(%)+f?X0,Xi?(X-X0)+f?X0,Xi，X2?(X-X0)(X-Xi)+f夕0,Xi，X2，,Xn5.Newton 前插公式：Dfi=f(Xi+h)-f(为)Dm:二口：Ifi+i-D一1f?(X-x0)(X-Xl)(x-xn-l)Nn(X)=Nnt(t-1)2t(t-1)(t-n+1)n(%+th)=f(XO)+tDf。+-D2f。+n1DDnf0 x=x0+tht?0,n?Newton 后插公式：？=f0)-f(-h)?mfi=?m-1fi-?m-1fi+1Nn(X)=Nn(A+th)=f(Xn)+t?fn+等?2t(t+1)(t+n-1)nfn+Ln

26、?fnX=Xn+tht?-n,0?当X值靠近X0时，用 Newton 前插公式,5.Hermite 插值：有(2n+2)个条件，所以有而当 X 靠近 4 时，用Newt0n后插公式。(2n+1)次多项式。2n+1 次 Hermite 插值多项式是唯一的2n+1 次 Hermite 插值多项式的余项为:(2n+2)f()(X)R2n+1(X)=工A/Wn+I(X)X?(a,b)Wn+i(X)=?(X-Xk)6.分段多项式插值：Runge 现象：随着节点 n 的增加，误差不但没减小，反而不断增大。原因是当节点 n 较大时，对应的是高次插值多项式，而高次多项式的舍入误差是随次数的增加而不断变大的，用

27、高次多项式插值作数值计算时舍入误差将淹没”了增加节点提高的精度。Runge 现象否认了用高次插值公式提高逼近精度的做法，因此引入了分段插值法。定义如下：取？a,b时的 n+i 个节点xk：a=x0 x1Vx2Vx?Af(xi),则称为一个数值求积,i=1公式。A称为求积系数，xi称为求积节点。bbnbf(n)仪.、求积系数：A=6lin-1(xx求积公式：6f(xx?Af(x)求积余项：R(f)?(n(wn(x)dx4.Newton-Cotes 求积公式：当求积节点个数为奇数时，Newton-Cotes求积公式代数精度至少为n；为偶数时，代数精度至少为n-1442.评价一个求积公式的优劣可以用

28、求积余项来说明，通常用与求积余项有关的代数精度来评价求积公式。判断求积公式的代数精度：取f(x)=xk，k=0,1，一，代入R(xk)=f(x,x-V,验证R(xk)=0是否成立,)二於下照=0，第个使R(xk)10的 k 值，则对应的代数精度为 k-1o3.插值型求积公式：当f(x)为次数小于 n 的多项式时，f(n)(x)o0,R(f)=0,插值型求积公式的代数精度至少为n-1为使求积系数A计算简单，将求积节点xi取为夕,b?上的等距节点,b-ah=n-1i=1,2,nn 点的 Newton-Cotes 求积公式:nnb(n)(n)1n-1?fx/？/GW、i口k+1?_dt2点Newto

29、n-Cotes公式【梯形公式】卜声？与夕(a)+f(b,余项:4)=-哈飞)，h3点Newton-Cotes公式【Simpson公式】：b.xb-a6/、?a+b?立人,、6f(xx?-6-ef(a)+4f?於f(b);,余项:R(f)=%对n个节点的Newton-cotes求积公式，在n8时，Cotes系数大于0,而在n8时，考虑到公式的稳定性不实用该公式。5.Gauss 型求积公式：Gauss 型求积公式是稳定的一?若 n 点的求积公式具有 2n-1 次的代数精度，则称该求积公式为 Gauss 型求积公式。【注意：若下标从 1 开始】Gauss 型求积公式的求积余项:R(f)=(2n)!b

30、26r(x)w(x)dxh?a,b?6.复化求积公式xi=a+ih,h=bz-a5i=0,1,2：,n，将积分区间？a,b我等分，有 n+1 个节点nb复化梯形公式(代数精度为 1)：备f(xx?n-1、b-ae/、-u17y(a)+f(b)+2?1f(Xk),，余项:b-a2R(f,Tn)=-1Th2f(h)若f(x)M2,对于给定精度e，令R(f,Tn)-bM2e,得出h;(b-a)M2复化 Simpson 公式(代数精度为 3):b6f(x)dxob-ae.、:1?xk+1+xk?:117?f(a)+f(b)+4?0f?-?+2?1fu仅k)u，?b-a?h?,(4),、h(b-a),(4),、示项：VW户=?i/S=-8fO,3御婚第七章常微分方程初值问题数值解法yk+1=yk+hf(Xk,yk)k=0,1,2n-1，h=xk+1-xyk)-hy(xk)后退Euler方法：Tk+1=y(xk+1)-y(xk)-hf(xk+1,y(xk+1)=y(x