1、计算方法复习计算方法复习典型概念例题典型概念例题Final Exam Review零零 绪论绪论误误差差及及算算法法误差误差算法算法分类分类度量度量传播传播舍入舍入截断截断绝对绝对相对相对有效数字有效数字一元函数一元函数n元函数元函数一一 插值与逼近插值与逼近插值法插值法工具工具多项式插值多项式插值分段多项式分段多项式插值插值差商差商差分差分插值基函数插值基函数存在唯一性存在唯一性误差估计误差估计插值公式插值公式Hermite插值插值分段线性分段线性分段三次分段三次Hermite插值插值三次样条插值三次样条插值函数逼近函数逼近预备知识预备知识函数逼近方法函数逼近方法范数范数内积内积正交多项式正
2、交多项式最佳一致逼近最佳一致逼近最佳平方逼近最佳平方逼近最小二乘拟合最小二乘拟合三角函数逼近三角函数逼近帕德逼近帕德逼近例例1观测物体过原点的直线运动观测物体过原点的直线运动,得到所示数据得到所示数据,求运动方程求运动方程.时间t/s00.91.93.03.95.0距离s/m010305080110解解作直线模型作直线模型: at+s=0n为观测点数为观测点数定义残差向量定义残差向量:T1122(,)nnVats atsats22( )I aV21()niiiats21122nnii iiiatt s12()niiiidIats tda所以所以:2 53.632 1078dIada 令令:2
3、53.632 10780dIada 20.1007a 所求运动方程为所求运动方程为:20.10070ts二二 数值积分数值积分数数值值积积分分基本概念基本概念Gauss求积公式求积公式代数精度代数精度插值型求积公式插值型求积公式收敛及稳定性收敛及稳定性数值求积思想数值求积思想N-C公式公式Romberg求积公式及外推加速求积公式及外推加速梯形公式梯形公式辛普森公式辛普森公式例例2试确定常数试确定常数A,B,C及及,使求积公式使求积公式:解解22( )()(0)( )f x dxAfBfCf代数精确度尽可能高，并确定上述公式的代数精代数精确度尽可能高，并确定上述公式的代数精确度。是否为高斯型求积
4、公式确度。是否为高斯型求积公式. 1xf令令:224dxABC xxf220 xdxAC 2xxf22222163x dxAC 3f xx233320 x dxAC 整理得整理得:AC24AB283A 4xxf24442645x dxAC4325A283235125 109A169B 109C 5f xx255520 x dxAC 6f xx22666221288122735x dxAC所以代数精确度为所以代数精确度为5次次.因为代数精确度为因为代数精确度为23=5次次,是高斯型求积公式是高斯型求积公式.标准标准Simpson公式公式:11141( )( )d( )2( 1)(0)( 1)66
5、6I ff ttS ffff ( )( )dbaI ff xx22abbaxt141( )()( )()( )6626baS fbaf aff b)2 , 1 , 0(,2njjhaxnabhj22 jx12 jxjx2njjjjxfxfxfhfI121222)()(4)(3)(njjjjnxfxfxfhfS121222)()(4)(3)()()(2)(4)(3)(112112bfxfxfafhdxxfnjjnjjba复化复化 Simpson 公式公式 将区间将区间0,10,1划分为划分为8 8等分等分, ,应用应用复化梯形法复化梯形法求得求得 x f (x)0 11/8 0.99739782
6、/8 0.98961583/8 0.97672674/8 0.95885105/8 0.93615566/8 0.90885167/8 0.87719251 0.8414709 718)()(2)(2kkbfxfafhT71) 1 (82)0(281kfkff=0.9456909 例例1试用数据表计算积分试用数据表计算积分xxxfsin)(10sin)(dxxxfI对于函数对于函数解解应用应用复化复化Simpson法法计算计算,得得比较上面两个结果比较上面两个结果T8和和S4,它们都需要提供它们都需要提供9个点个点上的函数值工作量基本相同上的函数值工作量基本相同,然而精度却差别很然而精度却差别
7、很大大.同积分的同积分的准确值准确值I(f)=0.9460831比较比较,复化梯形法复化梯形法的结果的结果T8=0.9456909只有只有两位有效数字两位有效数字, 而复化而复化Simpson法的结果法的结果S4=0.9460832却有却有六位有效数字六位有效数字.41312124)()(2)(4)(3jjjjbfxfxfafhS4131) 1 (8228124)0(381kkfkfkff=0.9456909 三三 线性方程组线性方程组直接法直接法Gauss消去法消去法矩阵三角分解法矩阵三角分解法向量和矩阵范数向量和矩阵范数追赶法追赶法矩阵条件数矩阵条件数三三 线性方程组线性方程组迭代法迭代法
8、基本概念基本概念雅可比迭代雅可比迭代迭代收敛速度迭代收敛速度高斯高斯-塞德尔迭代塞德尔迭代迭代格式迭代格式收敛条件收敛条件SOR迭代迭代常用的算子范数常用的算子范数：njijamaxAni1|1（行范数）（行范数） niijamaxAnj11|1（列范数）（列范数） )(|2AAATmax（谱范数（谱范数(spectral norm)） 定义定义7 设设A Rn n的特征值为的特征值为i: (i=1,n) iimaxA称为称为A的谱半径的谱半径.特殊地：特殊地： 00(1,2, )iiiAmaxinHamilton-Cayley定理定理 设设 A 是一个是一个n阶方阵，特征多项式为阶方阵，特征
9、多项式为 fIA则则（的的n次多项式）次多项式） fA0 当当k 时，时，Bk 0 ( B ) 1 设线性方程组设线性方程组x=Bx+g有惟一解，那么逐次逼有惟一解，那么逐次逼近法对任意初始向量近法对任意初始向量x收敛的充分必要条件是收敛的充分必要条件是迭代矩阵迭代矩阵B的谱半径的谱半径 ( B ) 1*1*1*10()().kkkkkxBxgxBxgxxB xxBxx*11lim()0lim0( )1.kkkkxxBB因此因此一、逐次逼近法收敛的条件一、逐次逼近法收敛的条件定理定理2定理定理3证明证明例例3解解设线性方程组设线性方程组 的系数矩阵为的系数矩阵为:Axb(1)写出写出Jacob
10、i 迭代法的迭代格式迭代法的迭代格式 (2)确定确定a的取值范围，使方程组对的取值范围，使方程组对应的应的Gauss-Seidel迭代收敛。迭代收敛。 (1) 线性方程组线性方程组Jacobi 迭代迭代211 1 211aa12311232123322xaxxbxxxbxaxxb(2) 线性方程组线性方程组Gauss-Seidel迭代矩阵迭代矩阵: 31( )( )1121( )21321( )312312222kkkkkkkkkbaxxxxxxbxxaxb 211 1 211aa2 0 0011 1 00 0 2110 0 0aa12 0 0011 1 00 0 2110 0 0G SaBa
11、 G SIB12 0 0011 1 00 0 2110 0 0aa 20110 0 220 0 0aa 21122aa 令令0G SIB得得1021232a21a 1122a四四 非线性方程求根非线性方程求根求根法求根法二分法二分法不动点迭代法及收敛性理论不动点迭代法及收敛性理论牛顿迭代法牛顿迭代法插值型迭代插值型迭代弦截法弦截法抛物线法抛物线法f (x) = 0 x = g (x)等价变换等价变换f (x) 的的根根g (x) 的不动点的不动点2 单个方程的迭代法单个方程的迭代法f(x)=0化为等价方程化为等价方程x=g(x)的方式是不唯一的的方式是不唯一的,有的收有的收敛敛,有的发散有的发
12、散 For example：2x3-x-1=0一、不动点迭代一、不动点迭代由此可见，这种迭代格式是发散的由此可见，这种迭代格式是发散的则迭代格式为则迭代格式为1231kkxx 如果将原方程化为等价方程如果将原方程化为等价方程123xx取初值取初值00 x112301xx312312xx5512323xx 如果将原方程化为等价方程如果将原方程化为等价方程321xx仍取初值仍取初值00 x7937. 021213301xxx3 = 0.9940 x4 = 0.9990 x5 = 0.9998x6 = 1.0000 x7 = 1.0000已经收敛已经收敛,故原方程的解为故原方程的解为 x = 1.0
13、000 同样的方程同样的方程不同的迭代格式不同的迭代格式 有不同的结果有不同的结果什么形式的什么形式的迭代法能够迭代法能够收敛呢收敛呢? ?9644. 027937. 1213312xx依此类推依此类推,得得局部收敛性定理局部收敛性定理 设设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*容易得到容易得
14、到: g(x)在包含在包含x*的某邻域的某邻域U(x*) 内连续，内连续，且且|g(x*)|1将方程变形成等价形式：将方程变形成等价形式：31xx则迭代函数为则迭代函数为:31)(xxg32) 1(31)(xxg因此迭代格式因此迭代格式 在在x*附近收敛附近收敛311kkxx例例4解解用一般迭代法求方程用一般迭代法求方程x-lnx2在区间在区间(2, )内的根，内的根，要求要求|xk-xk-1|/|xk|=10-8令令f(x)=x-lnx-2f(2)0,故方程在故方程在(2,4)内至少有一个根内至少有一个根又又011)(xxfx (2, )因此因此f(x)=0在在(2, )内仅有一个根内仅有一
15、个根x*将方程化为等价方程：将方程化为等价方程：x2lnxxxgln2)(5 . 0|1| )(|xxgx (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.14619162
16、811 3.14619271412 3.14619306013 3.14619316914 3.146193204另一种迭代格式另一种迭代格式1)1 (1kkkkxlnxxx 0 3.000000000 1 3.1479184332 3.1461934413 3.146193221五五 常微分方程数值解常微分方程数值解数值解法数值解法单步法单步法线性多步法线性多步法方程组与高阶方程方程组与高阶方程重要概念重要概念重要构造方法重要构造方法局部截断误差局部截断误差方法精度方法精度差分构造差分构造泰勒展式构造泰勒展式构造积分构造积分构造例例5解解给定求解常微分方程初值问题给定求解常微分方程初值问题
17、的线性多步公式的线性多步公式 00( , )()yf x yy xy 试确定系数试确定系数 并推导其局部截断误差主项。并推导其局部截断误差主项。 使它具有尽可能高的精度，使它具有尽可能高的精度，1()()nny xy xh111111()()nnnnnnyyyhfff11, 234(4)5()()()()()()2624nnnnnhhhy xhy xy xyxyxO h1()()nny xy xh111(, ()()()nnnnf xy xy xy xh111(, ()()()nnnnf xy xy xy xh234(4)5()()()()()()2624nnnnnhhhy xhy xy xy
18、xyxO h23(4)4()()()()()26nnnnhhy xhyxyxyxO h23(4)4()()()()()26nnnnhhy xhyxyxyxO h线性多步公式局部截断误差线性多步公式局部截断误差1nR x11()( ()()nnny xy xy x11()( ()()nnny xy xy x111111(, ()(, ()(, ()nnnnnnhf xy xf xy xf xy x1111()()()nnnhy xy xy x()ny x()nhy x234(4)5()()()()()()2624nnnnnhhhy xhy xy xyxyxO h234(4)5 ()()()()(
19、)()2624nnnnnhhhy xhy xy xyxyxO h23(4)41()()()()()26nnnnhhhy xhyxyxyxO h23(4)41()()()()()26nnnnhhhy xhyxyxyxO h(1 2 ) ()ny x11(11)()nhy x 2111()()22nh yx3111()()6622nh yx4(4)111()()242466nh yx5()O h此时此时:令令:111112001022得得:12138118111066221111024246648 所以当所以当:121381181111131()()288nnnnnnyyyhfff为三阶多步公式为
20、三阶多步公式.局部截断误差主项为局部截断误差主项为:4(4)1()48nh yx六六 特征值特征向量特征值特征向量特特征征值值及及特特征征向向量量解解法法迭代法迭代法变换法变换法重要概念重要概念特征值特征向量特征值特征向量QR分解分解变换变换正交相似正交相似反射反射平面旋转平面旋转幂法幂法反幂法反幂法雅可比法雅可比法QR法法(1)QR算法的基本思想算法的基本思想记记 AA1且有且有A1Q1R1.将等号右边两个矩阵因子的次序交换，得将等号右边两个矩阵因子的次序交换，得 A2R1Q1且且11112QAQA即即12 AA不难证明不难证明:kkkkkkQQAQQQAQA1111111即即11AAAkk
21、矩阵序列矩阵序列Ak有相同的特征值有相同的特征值.因为上因为上Hessenberg矩阵次对角线以下的元素全为矩阵次对角线以下的元素全为0, 因此因此, 只要证明只要证明, 当当k时时, 由迭由迭 代格式产生的矩代格式产生的矩阵阵Ak的次对角元趋向于零就可以了的次对角元趋向于零就可以了. 记记kkQQQ1kkRRR1容易得到容易得到 是是Ak的一个的一个QR分解分解kkkRQA如果如果A是一个满秩的上是一个满秩的上Hessenberg矩阵矩阵, 可以证明可以证明, 经过一个经过一个QR迭代步得到的迭代步得到的A2Q-11A1Q1仍然是上仍然是上Hessenberg矩阵矩阵. 例例4设矩阵设矩阵
22、4 1 01 2 10 1 2A试用试用QR算法求它的特征值。算法求它的特征值。 从10A可 以 看 出 ， 已 近 似 接 近 对 角 矩 阵 ， 即 有 特 征 值,2680. 1,0035. 3,7282. 4321与矩阵 A 的三个精确解 2679. 133, 3,7321. 433321 相比，已有良好精确度。随着迭代次数增加，nA将收敛到矩阵A 的三个精确特征值。 设设A是是n阶矩阵阶矩阵, 其其n个特征值按模从大到小排序为个特征值按模从大到小排序为|21n又假设关于又假设关于1, 2, , n的特征向量的特征向量v1, v2, ,vn线性无关线性无关一、乘幂法一、乘幂法任意取定初
23、始向量任意取定初始向量x0建立迭代公式建立迭代公式 ：)0(122110avavavaxnn1kkAxxnnAvaAvaAvaAxx221101nnnvavava222111nnnvavavaxAAxx2222212110212nknnkkkkkvavavaxAAxx22211101nknnkkvavava)()(12122111因此，因此，xk可看成是关于特征值可看成是关于特征值1的近似特征向量的近似特征向量 有一严重缺点，当有一严重缺点，当| 1|1 （或（或| 1 |0时时1|11kk|1111vbvbzk按模最大特征值按模最大特征值1及其相应的特征向量及其相应的特征向量v1的乘幂的乘幂法的计算公式：法的计算公式： 当当 10时时1|11kk|1111vbvbzkkkkxxzkkAzx1, 2 , 1 , 0kkTkkTkkTkkTkkzzAzzzzxz111若若1为为A的实重根的实重根, 幂法仍然有效幂法仍然有效.
