数值计算方法与算法

数值计算方法与算法教学目标掌握常用的数值计算方法掌握计算方法的数学原理学会选择恰当的计算方法学会使用流行的计算软件教学计划时间：7:50-8:35地点：21062-27绪论3-06多项式插值3-13多项式插值3-20分段和样条插值3-27数值微分4-03数值积分4-10数值积分4-17最小二乘法4-24方程求根5-01五一放假5-08方程求根5-15求解线性方程组5-22求解线性方程组5-29计算矩阵特征值6-05计算矩阵特征值6-12微分方程数值解6-19微分方程数值解6-26复习7-04期末考试7-13报送成绩教材及参考•数值计算方法与算法，张韵华、奚梅成、陈效群编，科学出版社，2006。•科学计算导论，MichaelT.Heath著，张威、贺华、冷爱萍译，清华大学出版社，2005。•数值计算方法解题指导，张韵华编，科学出版社，2003。•网络教学资源联系方式教师：王新茂[e-mail]理化大楼16#016，3607565助教：杨荣[e-mail]136-15607693第0章绪论数学建模数值计算实际问题数学问题近似解•什么是数值计算方法？•什么是“好的”数值计算方法？误差小─误差分析耗时少─复杂度分析抗干扰─稳定性分析•误差的类型绝对误差＝真实值－近似值相对误差＝绝对误差／真实值•误差的来源原始误差、截断误差、舍入误差输入计算输出真实值近似值xxxx~f)(xfyfff~yxfy)~(~~•一些例子：计算地球的体积计算计算•如何减小计算误差？选择好的算法、提高计算精度•范数的定义满足非负性,齐次性,三角不等式的实函数3π34RV71513114π3223333)(),(yxyyxxyxyxf•常用的向量范数•常用的矩阵范数•矩阵的谱半径•例：计算矩阵的范数和谱半径。•例：范数在误差估计中的应用pxxxppnpp111，　pxAxAppp1sup，　nA,,max)(14321A作业一、145页习题6第1,2题.作业二、利用公式编写两个计算ex的C程序(一个用单精度,另一个用双精度).令x=±1,±5,±10,±15,±20,比较它们和库函数exp(x)之间的运行时间和计算误差.思考如何减小误差？0!nnxnxe第1章插值函数逼近用未知函数f(x)的值构造近似函数φ(x)。要求误差小、形式简单、容易计算。常用的函数逼近方法•插值：φ(xi)=yi,i=0,1,…,n.•拟合：||φ(x)-f(x)||尽可能小通常取φ(x)=a0φ0(x)+…+anφn(x)，其中{φi(x)}为一组基函数。多项式插值给定平面上n+1个插值点(xi,yi),构造n次多项式φ(x),满足φ(xi)=yi,i=0,1,…,n.nhxnhxnnaaaxxaxaax)()()(1010，或01110101100)))((()(111axaxxaxaxyyyaaaxxxxxxnnnnnnnnn单项式插值)()())(()(),()()()(101100ininnxxxxxxxxxLxLbxLbxLbxLagrange插值nnnniiiiiiiinnnnxxbxxbxxxxxxxxxxxxxybyyybbbxLxLxL00011010101100)()()()())(()()()()(001111010111))())()((()()()(1)(11cxxxxcxxcxyyycccxNxNxNnnnnnnnnn)())(()(),()()(110110iinnxxxxxxxNxNcxNccxNewton插值差商表012…n…0…1…2……......n0x1x2xnx0101xxyy1212xxyy11nnnnxxyy01,1,1xxnnnnn021,12,1xx21,1,1nnnnxx],,[jijijxxfk阶差商0110110],,[],,,[],,[xxxxxfxxxfxxfkkkkk　ny2y1y0y差商的性质•以x0,…,xn为节点的n次插值多项式φ(x)的首项系数等于f[x0,…,xn]。证明：分别以x0,…,xn-1和x1,…,xn为节点构造n-1次插值多项式φ1(x)和φ2(x)，则有对n用归纳法。•f[x0,…,xn]与x0,…,xn的顺序无关。)()()(20010xxxxxxxxxxxnnn误差估计：证明：设，则有n+2个零点。根据中值定理，存在于是。)()()!1()()()()(0)1(nnxxxxnfxxfxR)())(()(0nxxxxxKxR)())(()()(0nxtxtxKtftgbagn，0)()1()!1()()()1(nfxKnHermite插值给定平面上n+1个插值点(xi,yi,mi),构造2n+1次多项式φ(x),满足φ(xi)=yi,φ’(xi)=mi,i=0,1,…,n.nnnnnnnnnnnnnnmmyyaaaaxnxxnxxxxxxxxaxaax0012210220012212020012110)12(210)12(21011)(单项式基函数Lagrange基函数)(,)(2)()()()(2302iiiiiiiiiiiniiiiixLycxLyxLmbxLcxxbx误差估计：证明：设，则有2n+3个零点。根据中值定理，存在于是。220)22()()()!22()()()()(nnxxxxnfxxfxR220)())(()(nxxxxxKxR220)())(()()(nxtxtxKtftgbagn，0)()22()!22()()()22(nfxKnRunge现象：并非插值点取得越多越好。解决办法：分段插值-1-0.50.510.511.52三次样条插值给定平面上n+1个插值点(xi,yi),构造分段三次多项式φ(x),满足φ(xi)=yi,φ’(x)可微，φ”(x)连续。作业一、习题1第2,4,6,8,10,12,14,16题。作业二、在半圆上随机选取10个点,构造插值多项式,画出函数图像,并比较3种插值方法的计算误差。作业三、思考3种插值系数之间的关系。比较3种插值方法的优缺点和应用范围。21xy第2章数值微分和数值积分数值微分•差商法向前差商向后差商中心差商1212)()()(xxxfxfxfhxfhxf)()(hhxfxf)()(hhxfhxf2)()(•插值法在x附近取点(xi,f(xi))构造插值多项式φ。•样条法在x附近取点(xi,f(xi))构造样条函数φ。f’(x)≈φ’(x)niijjijjijiniijjijixxxxxxxfxxxxxxfx001)()()()(例：用中心差商公式计算f’(xi)。例：用向后差商公式计算f’’(0.2),f’’(0.4)。x0.00.10.20.30.4f(x)1.71.51.62.01.9f’(x)f”(x)x0.00.10.20.30.4f(x)0.8187310.9048371.0000001.1051711.221403f’(x)例：设xi=x0+i*h,i=1,...,n。计算φ’(xk)。解：kiikikjkkiijjikjijjkikjjkkkniijjijjijiiniknkikhxfjkhxfxxxxxfxxxfxxxxxxxxfx)!(!)!(!)1()(1)()()()(1)()(1)()(,0•误差估计前后差商中心差商插值微分26)()(2)()(hfxfhhxfhxfhfxfhxfhxf2)()()()(ijjiniinxxnfxfxxxxxxKxfx)()!1()()()()())(()()()1(0数值积分•插值法niibaijjijbaniiijjijxfdxxxxxdxxxfxxxxx00)()()()()()()(00nnbaxfxfdxxf•若积分公式对任意m次多项式都取等号，则称积分公式具有至少m阶的代数精度。•插值型积分公式的代数精度≥n。•当积分节点x0,...,xn给定时，代数精度≥n的积分公式唯一。mnmnmncccxxxx1000011例：设xi=a+i*h,i=0,...,n,h=(b-a)/n。计算Newton-Cotes积分解：nhnnnnnhnhnhnhhnhhnnnnnnnnnn11211101112211011010111)()()(00111badxx)(特别，当n=1,2时，积分公式分别称为梯形公式Simpson公式2)()()(1bfafabI6)()(4)()(22bffafabIbana1a2a3a4a51½½21/64/61/631/83/83/81/847/9032/9012/9032/907/90•误差估计特别，梯形公式和Simpson公式的误差为代数精度＝1代数精度＝3evenis)()()!2()(oddis)()()!1()()())(()()(0)2(0)1(0nxdxxxxxnfndxxxxxnfdxxxxxxKdxxdxxfbannbannbanbaba5)4(231)(2880)()(12)(abfEabfE复化数值积分mIIbadxxfdxxfdxxf)()()(1•梯形公式•Simpson公式32101)(12)(2)()()(abnfxfxfnabdxxfniiiba54)4(1022122)(2880)(6)()(4)(2)(abnfxfxfxfnabdxxfniiiiba•Richardson外推法我们要计算假设则有比和更高的精度。•误差估计)(lim0hFah)()(qphOhbahF)(1)()(qpphOahFhF)(hF)()()(1)(qpphOhFhFahF)(hF•Romberg积分公式等分的梯形公式，•瑕积分•重积