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

计算方法复习计算方法复习典型概念例题典型概念例题Final Exam Review零零 绪论绪论误误差差及及算算法法误差误差算法算法分类分类度量度量传播传播舍入舍入截断截断绝对绝对相对相对有效数字有效数字一元函数一元函数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次次.因为代数精确度为因为代数精确度为23=5次次,是高斯型求积公式是高斯型求积公式.标准标准Simpson公式公式:复化复化 Simpson 公式公式 将区间将区间0,10,1划分为划分为8 8等分等分,应用应用复化梯形法复化梯形法求得求得 x f(x)0 11/8 0.99739782/8 0.98961583/8 0.97672674/8 0.95885105/8 0.93615566/8 0.90885167/8 0.87719251 0.8414709 =0.9456909 例例1试用数据表计算积分试用数据表计算积分对于函数对于函数解解应用应用复化复化Simpson法法计算计算,得得比比较较上上面面两两个个结结果果 T8和和S4,它它们们都都需需要要提提供供 9个个 点点上上的的函函数数值值工工作作量量基基本本相相同同,然然而而精精度度却却差差别别很很大大.同同积积分分的的 准准确确值值 I(f)=0.9460831比比 较较,复复化化梯梯形形法法的的结结果果 T8=0.9456909只只 有有 两两位位有有效效数数字字,而而复复化化Simpson法的结果法的结果S4=0.9460832却有却有六位有效数字六位有效数字.=0.9456909 三三 线性方程组线性方程组直接法直接法Gauss消去法消去法矩阵三角分解法矩阵三角分解法向量和矩阵范数向量和矩阵范数追赶法追赶法矩阵条件数矩阵条件数三三 线性方程组线性方程组迭代法迭代法基本概念基本概念雅可比迭代雅可比迭代迭代收敛速度迭代收敛速度高斯高斯-塞德尔迭代塞德尔迭代迭代格式迭代格式收敛条件收敛条件SOR迭代迭代常用的算子范数常用的算子范数：（行范数）（行范数）（列范数）（列范数）（谱范数（谱范数(spectral norm)）定义定义7 设设A Rn n的特征值为的特征值为i:(i=1,n)称为称为A的谱半径的谱半径.特殊地：特殊地：Hamilton-Cayley定理定理 设设 A 是一个是一个n阶方阵，特征多项式为阶方阵，特征多项式为则则（的的n次多项式次多项式）当当k 时，时，Bk 0 (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)=0 x=g(x)等价变换等价变换f(x)的的根根g(x)的不动点的不动点2 2 单个方程的迭代法单个方程的迭代法单个方程的迭代法单个方程的迭代法f(x)=0化化为为等等价价方方程程 x=g(x)的的方方式式是是不不唯唯一一的的,有有 的的 收收敛敛,有的发散有的发散 For example：2x3-x-1=0一、不动点迭代一、不动点迭代由此可见，这种迭代格式是发散的由此可见，这种迭代格式是发散的则迭代格式为则迭代格式为(1)(1)(1)(1)如果将原方程化为等价方程如果将原方程化为等价方程取初值取初值(2)(2)(2)(2)如果将原方程化为等价方程如果将原方程化为等价方程仍取初值仍取初值x3=0.9940 x4=0.9990 x5=0.9998x6=1.0000 x7=1.0000已经收敛已经收敛,故原方程的解为故原方程的解为 x=1.0000 同样的方程同样的方程 不同的迭代格式不同的迭代格式 有不同的结果有不同的结果什么形式的什么形式的迭代法能够迭代法能够收敛呢收敛呢?依此类推依此类推,得得局部收敛性定理局部收敛性定理 设设x*为为g的的不不动动点点,g(x)与与g(x)在在包包含含 x*的的 某某邻邻 域域 U(x*)(即即开开区区间间)内内连连续续,且且|g(x*)|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-lnx2在区间在区间(2,)内的根，内的根，要求要求|xk-xk-1|/|xk|=10-8令令f(x)=x-lnx-2f(2)0,故方程在故方程在(2,4)内至少有一个根内至少有一个根又又x(2,)因此因此f(x)=0在在(2,)内仅有一个根内仅有一个根x*将方程化为等价方程：将方程化为等价方程：x2lnxx(2,4)例例5解解因此，因此，x0(2,),xk+12lnxk产生的序列产生的序列 xk 收敛于收敛于x*取初值取初值x x0 03.0,3.0,计算结果如下：计算结果如下：k xi 0 3.000000000 1 3.098612289 2 3.130954362 3 3.141337866 4 3.1446487815 3.1457022096 3.1460371437 3.1461436118 3.1461774529 3.14618820910 3.14619162811 3.14619271412 3.14619306013 3.14619316914 3.146193204另一种迭代格式另一种迭代格式 0 3.000000000 1 3.1479184332 3.1461934413 3.146193221五五 常微分方程数值解常微分方程数值解数值解法数值解法单步法单步法线性多步法线性多步法方程组与高阶方程方程组与高阶方程重要概念重要概念重要构造方法重要构造方法局部截断误差局部截断误差方法精度方法精度差分构造差分构造泰勒展式构造泰勒展式构造积分构造积分构造例例5解解给定求解常微分方程初值问题给定求解常微分方程初值问题 的线性多步公式的线性多步公式 试确定系数试确定系数 并推导其局部截断误差主项。并推导其局部截断误差主项。使它具有尽可能高的精度，使它具有尽可能高的精度，线性多步公式局部截断误差线性多步公式局部截断误差此时此时:令令:得得:所以当所以当:为三阶多步公式为三阶多步公式.局部截断误差主项为局部截断误差主项为:六六 特征值特征向量特征值特征向量特特征征值值及及特特征征向向量量解解法法迭代法迭代法变换法变换法重要概念重要概念特征值特征向量特征值特征向量QR分解分解变换变换正交相似正交相似反射反射平面旋转平面旋转幂法幂法反幂法反幂法雅可比法雅可比法QR法法(1)QR算法的基本思想算法的基本思想记记 AA1且有且有A1Q1R1.将等号右边两个矩阵因子的次序交换，得将等号右边两个矩阵因子的次序交换，得 A2R1Q1且且即即不难证明不难证明:即即矩阵序列矩阵序列Ak有相同的特征值有相同的特征值.因为上因为上Hessenberg矩阵次对角线以下的元素全为矩阵次对角线以下的元素全为0,因此因此,只要证明只要证明,当当k时时,由迭由迭 代格式产生的代格式产生的矩阵矩阵Ak的次对角元趋向于零就可以了的次对角元趋向于零就可以了.记记容易得到容易得到 是是Ak的一个的一个QR分解分解如如 果果 A是是一一个个满满秩秩的的上上 Hessenberg矩矩 阵阵,可可以以证证明明,经经过过一一个个 QR迭迭代代步步得得到到的的 A2Q-11A1Q1仍仍然然是是上上Hessenberg矩阵矩阵.例例4设矩阵设矩阵 试用试用QR算法求它的特征值。算法求它的特征值。乘幂法是适用于求一般矩阵按模最大特征值及相乘幂法是适用于求一般矩阵按模最大特征值及相乘幂法是适用于求一般矩阵按模最大特征值及相乘幂法是适用于求一般矩阵按模最大特征值及相应特征向量的算法应特征向量的算法应特征向量的算法应特征向量的算法.设设A是是n阶矩阵阶矩阵,其其n个特征值按模从大到小排序为个特征值按模从大到小排序为又假设关于又假设关于1,2,n的特征向量的特征向量v1,v2,vn线性无关线性无关一、乘幂法一、乘幂法任意取定初始向量任意取定初始向量x0建立迭代公式建立迭代公式 ：故当故当故当故当k k时，时，时，时，x xk k 1 1k ka a1 1v v1 1.因此，因此，xk可看成是关于特征值可看成是关于特征值1的近似特征向量的近似特征向量 有一严重缺点，当有一严重缺点，当|1|1（或（或|1|0时时按模最大特征值按模最大特征值1及其相应的特征向量及其相应的特征向量v1的乘幂法的乘幂法的计算公式：的计算公式：当当 10时时若若1为为A的实重根的实重根,幂法仍然有效幂法仍然有效.