1、计算方法复习计算方法复习典型概念例题典型概念例题零零 绪论绪论误误差差及及算算法法误差误差算法算法分类分类度量度量传播传播舍入舍入截断截断绝对绝对相对相对有效数字有效数字一元函数一元函数n元函数元函数一一 插值与逼近插值与逼近插值法插值法工具工具多项式插值多项式插值分段多项式分段多项式插值插值差商差商差分差分插值基函数插值基函数存在唯一性存在唯一性误差估计误差估计插值公式插值公式Hermite插值插值分段线性分段线性分段三次分段三次Hermite插值插值三次样条插值三次样条插值函数逼近函数逼近预备知识预备知识函数逼近方法函数逼近方法范数范数内积内积正交多项式正交多项式最佳一致逼近最佳一致逼近最
2、佳平方逼近最佳平方逼近最小二乘拟合最小二乘拟合三角函数逼近三角函数逼近帕德逼近帕德逼近所以，关于所以，关于a，a为未知数的法方程组为为未知数的法方程组为求求g(x)=x 在在P10,1中的最佳平方逼近元中的最佳平方逼近元解法一解法一这是这是C0,1上的最佳平方逼近问题上的最佳平方逼近问题. 取取 , x, P10,1span1,x记记 p1(x)=aax( , 0)=1，( , 1)=1/2，( 1, 1)=1/3 ，( ,g)=2/3， ( 1,g)=2/5.例例1解得解得a=4/15，a4/5为为P10,1中对中对g(x)= x的最佳平方逼近元的最佳平方逼近元.52312132211010
3、aaaa即即p1(x)=4/5x+4/15例例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 53.632 10780dIada 20.1007a 所求运动方程为所求运动方
4、程为:20.10070ts二二 数值积分数值积分数数值值积积分分基本概念基本概念Gauss求积公式求积公式代数精度代数精度插值型求积公式插值型求积公式收敛及稳定性收敛及稳定性数值求积思想数值求积思想N-C公式公式Romberg求积公式及外推加速求积公式及外推加速梯形公式梯形公式辛普森公式辛普森公式例例2试确定常数试确定常数A,B,C及及,使求积公式使求积公式:解解22( )()(0)( )f x dxAfBfCf代数精确度尽可能高，并确定上述公式的代数精代数精确度尽可能高，并确定上述公式的代数精确度。是否为高斯型求积公式确度。是否为高斯型求积公式. 1xf令令:224dxABC xxf220
5、xdxAC 2xxf22222163x dxAC 3f xx233320 x dxAC 整理得整理得:AC24AB283A 4xxf24442645x dxAC4325A283235125 109A169B 109C 5f xx255520 x dxAC 6f xx22666221288122735x dxAC所以代数精确度为所以代数精确度为5次次.因为代数精确度为因为代数精确度为23=5次次,是高斯型求积公式是高斯型求积公式.三三 线性方程组线性方程组直接法直接法Gauss消去法消去法矩阵三角分解法矩阵三角分解法向量和矩阵范数向量和矩阵范数追赶法追赶法矩阵条件数矩阵条件数三三 线性方程组线性
6、方程组迭代法迭代法基本概念基本概念雅可比迭代雅可比迭代迭代收敛速度迭代收敛速度高斯高斯-塞德尔迭代塞德尔迭代迭代格式迭代格式收敛条件收敛条件SOR迭代迭代例例3解解设线性方程组设线性方程组 的系数矩阵为的系数矩阵为:Axb(1)写出写出Jacobi 迭代法的迭代格式迭代法的迭代格式 (2)确定确定a的取值范围，使方程组对的取值范围，使方程组对应的应的Gauss-Seidel迭代收敛。迭代收敛。 (1) 线性方程组线性方程组Jacobi 迭代迭代211 1 211aa12311232123322xaxxbxxxbxaxxb(2) 线性方程组线性方程组Gauss-Seidel迭代矩阵迭代矩阵: 3
7、1( )( )1121( )21321( )312312222kkkkkkkkkbaxxxxxxbxxaxb 211 1 211aa2 0 0011 1 00 0 2110 0 0aa12 0 0011 1 00 0 2110 0 0G SaBa G SIB12 0 0011 1 00 0 2110 0 0aa 20110 0 220 0 0aa 21122aa 令令0G SIB得得1021232a21a 1122a四四 非线性方程求根非线性方程求根求根法求根法二分法二分法不动点迭代法及收敛性理论不动点迭代法及收敛性理论牛顿迭代法牛顿迭代法插值型迭代插值型迭代弦截法弦截法抛物线法抛物线法用一般
8、迭代法求方程用一般迭代法求方程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, )内仅有一个根内仅有一个根x*将方程化为等价方程：将方程化为等价方程：x2lnxxxgln2)(5 . 0|1| )(|xxgx (2, 4)例例5解解因此，因此， x0 (2, ), xk+12lnxk产生的序列产生的序列 xk 收敛于收敛于x*取初值取初值x x0 03.0,3.0,计算结果如下：计算结果如下
9、： 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另一种迭代格式另一种迭代格式1)1 (1kkkkxlnxxx 0 3.000000000 1 3.1479184332 3.1461934413 3.146193221五五 常微
10、分方程数值解常微分方程数值解数值解法数值解法单步法单步法线性多步法线性多步法方程组与高阶方程方程组与高阶方程重要概念重要概念重要构造方法重要构造方法局部截断误差局部截断误差方法精度方法精度差分构造差分构造泰勒展式构造泰勒展式构造积分构造积分构造例例5解解给定求解常微分方程初值问题给定求解常微分方程初值问题 的线性多步公式的线性多步公式 00( , )()yf x yy xy 试确定系数试确定系数 并推导其局部截断误差主项。并推导其局部截断误差主项。 使它具有尽可能高的精度，使它具有尽可能高的精度，1()()nny xy xh111111()()nnnnnnyyyhfff11, 234(4)5(
11、)()()()()()2624nnnnnhhhy xhy xy xyxyxO h1()()nny xy xh111(, ()()()nnnnf xy xy xy xh111(, ()()()nnnnf xy xy xy xh234(4)5()()()()()()2624nnnnnhhhy xhy xy xyxyxO h23(4)4()()()()()26nnnnhhy xhyxyxyxO h23(4)4()()()()()26nnnnhhy xhyxyxyxO h线性多步公式局部截断误差线性多步公式局部截断误差1nR x11()( ()()nnny xy xy x11()( ()()nnny
12、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 ()()()()()()2624nnnnnhhhy xhy xy xyxyxO h23(4)41()()()()()26nnnnhhhy xhyxyxyxO h23(4)41()()()()()26nnnnhhhy xhyxyxyxO h(1 2 ) ()ny x11(11)()nhy x 2111()()2
13、2nh yx3111()()6622nh yx4(4)111()()242466nh yx5()O h此时此时:令令:111112001022得得:12138118111066221111024246648 所以当所以当:121381181111131()()288nnnnnnyyyhfff为三阶多步公式为三阶多步公式.局部截断误差主项为局部截断误差主项为:4(4)1()48nh yx六六 特征值特征向量特征值特征向量特特征征值值及及特特征征向向量量解解法法迭代法迭代法变换法变换法重要概念重要概念特征值特征向量特征值特征向量QR分解分解变换变换正交相似正交相似反射反射平面旋转平面旋转幂法幂法反
14、幂法反幂法雅可比法雅可比法QR法法22111112222212212211122222111222cos2sincossin()sincos(cossin)sin2sincoscosbaaabbaaabaaa先看一个简单的例子先看一个简单的例子. . 设设 是二阶实对称矩阵是二阶实对称矩阵, 即即a21=a12, 其特其特征值为征值为1, 2.22211211aaaaA22211211bbbbARRBT21ARRT容易验证容易验证BT=B, 且且cossinsincosR令令使得使得当当 时时1122aa12112221arctan2aaa为使为使RTAR为对角阵，要求为对角阵，要求b12=b
15、21=0解之得解之得:当当 时时1122aa4可选取可选取一般一般的的n阶平面旋转矩阵阶平面旋转矩阵qqpppqaaa2arctan214|例例3设矩阵设矩阵 5 4 21 1 21 1 1-A试作矩阵试作矩阵A=QR分解。分解。 设设A是是n阶矩阵阶矩阵, 其其n个特征值按模从大到小排序为个特征值按模从大到小排序为|21n又假设关于又假设关于1, 2, , n的特征向量的特征向量v1, v2, ,vn线性无关线性无关一、乘幂法一、乘幂法任意取定初始向量任意取定初始向量x0建立迭代公式建立迭代公式 ：)0(122110avavavaxnn1kkAxxnnAvaAvaAvaAxx221101nn
16、nvavava222111nnnvavavaxAAxx2222212110212nknnkkkkkvavavaxAAxx22211101nknnkkvavava)()(12122111因此，因此，xk可看成是关于特征值可看成是关于特征值1的近似特征向量的近似特征向量 有一严重缺点，当有一严重缺点，当| 1|1 （或（或| 1 |1时）时）vk中不中不为零的分量将随为零的分量将随k的增大而无限增大，计算机就可的增大而无限增大，计算机就可能出现上溢（或随能出现上溢（或随k的增大而很快出现下溢）的增大而很快出现下溢）因此，在实际计算时，须按规范法计算，每步先因此，在实际计算时，须按规范法计算，每步先对向量对向量xk进行进行“规范化规范化”。迭代格式改为迭代格式改为:kkkxxzkkAzx1, 2 , 1 , 0k11ini, 2 因为因为
