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

计算方法复习典型概念例题FinalExamReview零绪论误差及算法误差算法分类度量传播舍入截断绝对相对有效数字一元函数n元函数一插值与逼近插值法工具多项式插值分段多项式插值差商差分插值基函数存在唯一性误差估计插值公式Hermite插值分段线性分段三次Hermite插值三次样条插值函数逼近预备知识函数逼近方法范数内积正交多项式最佳一致逼近最佳平方逼近最小二乘拟合三角函数逼近帕德逼近例1观测物体过原点的直线运动,得到所示数据,求运动方程.时间t/s00.91.93.03.95.0距离s/m010305080110解作直线模型:at+s=0n为观测点数定义残差向量:所以:令:所求运动方程为:二数值积分数值积分基本概念Gauss求积公式代数精度插值型求积公式收敛及稳定性数值求积思想N-C公式Romberg求积公式及外推加速梯形公式辛普森公式例2试确定常数A,B,C及α,使求积公式:解代数精确度尽可能高，并确定上述公式的代数精确度。是否为高斯型求积公式.令:整理得:所以代数精确度为5次.因为代数精确度为2×3=5次,是高斯型求积公式.标准Simpson公式:复化Simpson公式

将区间[0,1]划分为8等分,应用复化梯形法求得x

f(x)011/80.99739782/80.98961583/80.97672674/80.95885105/80.93615566/80.90885167/80.877192510.8414709=0.9456909例1试用数据表计算积分对于函数解应用复化Simpson法计算,得比较上面两个结果T8和S4,它们都需要提供9个点上的函数值工作量基本相同,然而精度却差别很大.同积分的准确值I(f)=0.9460831比较,复化梯形法的结果T8=0.9456909只有两位有效数字,而复化Simpson法的结果S4=0.9460832却有六位有效数字.=0.9456909三线性方程组直接法Gauss消去法矩阵三角分解法向量和矩阵范数追赶法矩阵条件数三线性方程组迭代法基本概念雅可比迭代迭代收敛速度高斯-塞德尔迭代迭代格式收敛条件SOR迭代常用的算子范数：（行范数）（列范数）（谱范数(spectralnorm)）定义7设ARnn的特征值为λi:(i=1,…,n)称为A的谱半径.特殊地：Hamilton-Cayley定理设A是一个n阶方阵，特征多项式为则（λ的n次多项式）当k

时，Bk0(B)<1设线性方程组x=Bx+g有惟一解，那么逐次逼近法对任意初始向量x０收敛的充分必要条件是迭代矩阵B的谱半径(B)<1因此一、逐次逼近法收敛的条件定理2定理3证明例3解设线性方程组的系数矩阵为:(1)写出Jacobi迭代法的迭代格式(2)确定a的取值范围，使方程组对应的Gauss-Seidel迭代收敛。(1)线性方程组Jacobi迭代(2)线性方程组Gauss-Seidel迭代矩阵:令得四非线性方程求根求根法二分法不动点迭代法及收敛性理论牛顿迭代法插值型迭代弦截法抛物线法f(x)=0x=g(x)等价变换f(x)的根g(x)的不动点§2单个方程的迭代法f(x)=0化为等价方程x=g(x)的方式是不唯一的,有的收敛,有的发散Forexample：2x3-x-1=0一、不动点迭代由此可见，这种迭代格式是发散的则迭代格式为(1)

如果将原方程化为等价方程取初值(2)如果将原方程化为等价方程仍取初值x3=0.9940x4=0.9990x5=0.9998x6=1.0000x7=1.0000已经收敛,故原方程的解为x=1.0000同样的方程⇒

不同的迭代格式有不同的结果什么形式的迭代法能够收敛呢?依此类推,得局部收敛性定理设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将方程变形成等价形式：则迭代函数为:因此迭代格式在x*附近收敛例4解用一般迭代法求方程x-lnx＝2在区间(2,)内的根，要求|xk-xk-1|/|xk|<=10-8令f(x)=x-lnx-2f(2)<0,f(4)>0,故方程在(2,4)内至少有一个根又x∈(2,)因此f(x)=0在(2,)内仅有一个根x*将方程化为等价方程：x＝2＋lnxx∈(2,4)例5解因此，x0(2,),xk+1＝2＋lnxk产生的序列xk

收敛于x*取初值x0＝3.0,计算结果如下：

k

xi03.00000000013.09861228923141337866431457022096314614361183146188209103.146191628113.146192714123.146193060133.146193169143.146193204另一种迭代格式03.0000000001314619344133.146193221五常微分方程数值解数值解法单步法线性多步法方程组与高阶方程重要概念重要构造方法局部截断误差方法精度差分构造泰勒展式构造积分构造例5解给定求解常微分方程初值问题的线性多步公式试确定系数并推导其局部截断误差主项。使它具有尽可能高的精度，线性多步公式局部截断误差此时:令:得:所以当:为三阶多步公式.局部截断误差主项为:六特征值特征向量特征值及特征向量解法迭代法变换法重要概念特征值特征向量QR分解变换正交相似反射平面旋转幂法反幂法雅可比法QR法(1)QR算法的基本思想记A＝A1且有A1＝Q1R1.将等号右边两个矩阵因子的次序交换，得

A2＝R1Q1且即不难证明:即矩阵序列{Ak}有相同的特征值.因为上Hessenberg矩阵次对角线以下的元素全为0,因此,只要证明,当k→∞时,由迭代格式产生的矩阵Ak的次对角元趋向于零就可以了.记容易得到是Ak的一个QR分解如果A是一个满秩的上Hessenberg矩阵,可以证明,

经过一个QR迭代步得到的A2＝Q-11A1Q1仍然是上Hessenberg矩阵.例4设矩阵试用QR算法求它的特征值。乘幂法是适用于求一般矩阵按模最大特征值及相应特征向量的算法.设A是n阶矩阵,其n个特征值按模从大到小排序为又假设关于λ1,λ2,…,λn的特征向量v1,v2,…,vn线性无关一、乘幂法任意取定初始向量x0建立迭代公式：故当k→∞时，xk→λ1ka1v1.因此，xk可看成是关于特征值λ1的近似特征向量有一严重缺点，当|1|>1

（或|1|<1时）{