数值分析计算方法复习(典型例题)

计算方法复习典型概念例题FinalExamReview零绪论误差及算法误差算法分类度量传播舍入截断绝对相对有效数字一元函数n元函数一插值与逼近插值法工具多项式插值分段多项式插值差商差分插值基函数存在唯一性误差估计插值公式Hermite插值分段线性分段三次Hermite插值三次样条插值函数逼近预备知识函数逼近方法范数内积正交多项式最佳一致逼近最佳平方逼近最小二乘拟合三角函数逼近帕德逼近例1观测物体过原点的直线运动,得到所示数据,求运动方程.时间t/s00.91.93.03.95.0距离s/m010305080110解作直线模型:at+s=0n为观测点数定义残差向量:T1122(,,,)nnVatsatsats22()IaV21()niiiats21122nniiiiiatts12()niiiidIatstda所以:253.6321078dIada令:253.63210780dIada20.1007a所求运动方程为:20.10070ts二数值积分数值积分基本概念Gauss求积公式代数精度插值型求积公式收敛及稳定性数值求积思想N-C公式Romberg求积公式及外推加速梯形公式辛普森公式例2试确定常数A,B,C及α,使求积公式:解22()()(0)()fxdxAfBfCf代数精确度尽可能高，并确定上述公式的代数精确度。是否为高斯型求积公式.1xf令:224dxABCxxf220xdxAC2xxf22222163xdxAC3fxx233320xdxAC整理得:AC24AB283A4xxf24442645xdxAC4325A283235125109A169B109C5fxx255520xdxAC6fxx22666221288122735xdxAC所以代数精确度为5次.因为代数精确度为2×3=5次,是高斯型求积公式.标准Simpson公式:11141()()d()2[(1)(0)(1)]666IffttSffff()()dbaIffxx22abbaxt141()()[(()()())]6626baSfbafaffb)2,,1,0(,2njjhaxnabhj22jx12jxjx2njjjjxfxfxfhfI121222)]()(4)([3)(njjjjnxfxfxfhfS121222)]()(4)([3)()]()(2)(4)([3)(112112bfxfxfafhdxxfnjjnjjba复化Simpson公式将区间[0,1]划分为8等分,应用复化梯形法求得xf(x)011/80.99739782/80.98961583/80.97672674/80.95885105/80.93615566/80.90885167/80.877192510.8414709718)()(2)(2kkbfxfafhT71)1(82)0(281kfkff=0.9456909例1试用数据表计算积分xxxfsin)(10sin)(dxxxfI对于函数解应用复化Simpson法计算,得比较上面两个结果T8和S4,它们都需要提供9个点上的函数值工作量基本相同,然而精度却差别很大.同积分的准确值I(f)=0.9460831比较,复化梯形法的结果T8=0.9456909只有两位有效数字,而复化Simpson法的结果S4=0.9460832却有六位有效数字.41312124)()(2)(4)(3jjjjbfxfxfafhS4131)1(8228124)0(381kkfkfkff=0.9456909三线性方程组直接法Gauss消去法矩阵三角分解法向量和矩阵范数追赶法矩阵条件数三线性方程组迭代法基本概念雅可比迭代迭代收敛速度高斯-塞德尔迭代迭代格式收敛条件SOR迭代常用的算子范数：njijamaxAni1||||||1（行范数）niijamaxAnj11||||||1（列范数）)(||||2AAATmax（谱范数(spectralnorm)）定义7设ARnn的特征值为λi:(i=1,…,n)iimaxA称为A的谱半径.特殊地：00(1,2,,)iiiAmaxinHamilton-Cayley定理设A是一个n阶方阵，特征多项式为fIA则（λ的n次多项式）fA0当k时，Bk0(B)1设线性方程组x=Bx+g有惟一解，那么逐次逼近法对任意初始向量x０收敛的充分必要条件是迭代矩阵B的谱半径(B)1**1**1*10()().kkkkkxBxgxBxgxxBxxBxx*11lim()0lim0()1.kkkkxxBB因此一、逐次逼近法收敛的条件定理2定理3证明例3解设线性方程组的系数矩阵为:Axb(1)写出Jacobi迭代法的迭代格式(2)确定a的取值范围，使方程组对应的Gauss-Seidel迭代收敛。(1)线性方程组Jacobi迭代2111211aa12311232123322xaxxbxxxbxaxxb(2)线性方程组Gauss-Seidel迭代矩阵:31()()1121()21321()312312222kkkkkkkkkbaxxxxxxbxxaxb2111211aa2000111000211000aa12000111000211000GSaBaGSIB12000111000211000aa20110022000aa21122aa令0GSIB得1021232a21a1122a四非线性方程求根求根法二分法不动点迭代法及收敛性理论牛顿迭代法插值型迭代弦截法抛物线法f(x)=0x=g(x)等价变换f(x)的根g(x)的不动点§2单个方程的迭代法f(x)=0化为等价方程x=g(x)的方式是不唯一的,有的收敛,有的发散Forexample：2x3-x-1=0一、不动点迭代由此可见，这种迭代格式是发散的则迭代格式为1231kkxx(1)如果将原方程化为等价方程123xx取初值00x112301xx312312xx5512323xx(2)如果将原方程化为等价方程321xx仍取初值00x7937.021213301xxx3=0.9940x4=0.9990x5=0.9998x6=1.0000x7=1.0000已经收敛,故原方程的解为x=1.0000同样的方程⇒不同的迭代格式有不同的结果什么形式的迭代法能够收敛呢?9644.027937.1213312xx依此类推,得局部收敛性定理设x*为g的不动点,g(x)与g’(x)在包含x*的某邻域U(x*)(即开区间)内连续,且|g’(x*)|1,则存在0,当x0∈[x*-,x*+]时,迭代法产生的序列{xk}[x*-,x*+]且收敛于x*.定理2用一般迭代法求x3-x-1=0的正实根x*容易得到:g’(x)在包含x*的某邻域U(x*)内连续，且|g’(x*)|1将方程变形成等价形式：31xx则迭代函数为:31)(xxg32)1(31)(xxg因此迭代格式在x*附近收敛311kkxx例4解用一般迭代法求方程x-lnx＝2在区间(2,)内的根，要求|xk-xk-1|/|xk|=10-8令f(x)=x-lnx-2f(2)0,f(4)0,故方程在(2,4)内至少有一个根又011)(xxfx∈(2,)因此f(x)=0在(2,)内仅有一个根x*将方程化为等价方程：x＝2＋lnxxxgln2)(5.0|1||)(|xxgx∈(2,4)例5解因此，x0(2,),xk+1＝2＋lnxk产生的序列xk收敛于x*取初值x0＝3.0,计算结果如下：kxi03.00000000013.09861228923.13095436233.14133786643.14464878153.14570220963.14603714373.14614361183.14617745293.146188209103.146191628113.146192714123.146193060133.146193169143.146193204另一种迭代格式1)1(1kkkkxlnxxx03.00000000013.14791843323.14619344133.146193221五常微分方程数值解数值解法单步法线性多步法方程组与高阶方程重要概念重要构造方法局部截断误差方法精度差分构造泰勒展式构造积分构造例5解给定求解常微分方程初值问题的线性多步公式00(,)()yfxyyxy试确定系数并推导其局部截断误差主项。使它具有尽可能高的精度，1()()nnyxyxh111111()()nnnnnnyyyhfff11,,,234(4)5()()()()()()2624nnnnnhhhyxhyxyxyxyxOh1()()nnyxyxh111(,())()()nnnnfxyxyxyxh111(,())()()nnnnfxyxyxyxh234(4)5()()()()()()2624nnnnnhhhyxhyxyxyxyxOh23(4)4()()()()()26nnnnhhyxhyxyxyxOh23(4)4()()()()()26nnnnhhyxhyxyxyxOh线性多步公式局部截断误差1nRx11()(()())nnnyxyxyx11()(()())nnnyxyxyx111111((,())(,())(,()))nnnnnnhfxyxfxyxfxyx1111(()()())nnnhyxyxyx()nyx()nhyx234(4)5()()()()()()2624nnnnnhhhyxhyxyxyxyxOh234(4)5[()()()()()()]2624nnnnnhhhyxhyxyxyxyxOh23(4)41[()()()()()]26nnnnhhhyxhyxyxyxOh23(4)41[()()()()()]26nnnnhhhyxhyxyxyxOh(12)()nyx11(11)()nhyx2111()()22nhyx3111()()6622nhyx4(4)111()()242466nhyx5()Oh此时:令:111112001022得:12138118111066221111024246648所以当:12138