数值计算方法及算法学习教案.pptx

《数值计算方法及算法学习教案.pptx》由会员分享，可在线阅读，更多相关《数值计算方法及算法学习教案.pptx（98页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1数值数值(shz)计算方法及算法计算方法及算法第一页，共98页。数学建模 数值(shz)计算实际(shj)问题数学问题近似解什么(shn me)是数值计算方法？什么(shn me)是“好的”数值计算方法？误差小 误差分析耗时少 复杂度分析抗干扰 稳定性分析第2页/共98页第二页，共98页。n n误差的类型n n绝对误差真实值近似值n n相对误差(xin du w ch)绝对误差真实值n n误差的来源n n原始误差、截断误差、舍入误差输入计算输出真实值近似值第3页/共98页第三页，共98页。n n一些例子(l zi)：n n计算地球的体积n n计算n n计算n n如何减小计算误差？n n

2、选择好的算法、提高计算精度n n范数的定义n n满足非负性,齐次性,三角不等式的实函数第4页/共98页第四页，共98页。n n常用的向量(xingling)范数n n常用的矩阵范数n n矩阵的谱半径n n例：计算矩阵 的范数和谱半径。n n例：范数在误差估计中的应用第5页/共98页第五页，共98页。第第1 1章章 插值插值第6页/共98页第六页，共98页。函数逼近用未知函数f(x)的值构造近似函数(x)。要求误差小、形式简单、容易(rngy)计算。常用的函数逼近方法插值：(xi)=yi,i=0,1,n.拟合：|(x)-f(x)|尽可能小通常取(x)=a00(x)+ann(x)，其中i(x)为一

3、组基函数。第7页/共98页第七页，共98页。多项式插值 给定平面上n+1个插值点(xi,yi),构造(guzo)n次多项式(x),满足(xi)=yi,i=0,1,n.第8页/共98页第八页，共98页。单项式插值第9页/共98页第九页，共98页。Lagrange插值第10页/共98页第十页，共98页。Newton插值第11页/共98页第十一页，共98页。差商表012n012.nk阶差商第12页/共98页第十二页，共98页。差商的性质(xngzh)以x0,xn为节点的n次插值多项式(x)的首项系数等于fx0,xn。证明：分别以x0,xn-1和x1,xn为节点构造n-1次插值多项式1(x)和 2(x

4、)，则有对n用归纳法。fx0,xn与x0,xn的顺序无关。第13页/共98页第十三页，共98页。误差估计(gj)：证明：设，则有n+2个零点。根据中值定理，存在于是。第14页/共98页第十四页，共98页。Hermite插值 给定平面(pngmin)上n+1个插值点(xi,yi,mi),构造2n+1次多项式(x),满足(xi)=yi,(xi)=mi,i=0,1,n.第15页/共98页第十五页，共98页。单项式基函数(hnsh)Lagrange基函数(hnsh)第16页/共98页第十六页，共98页。误差估计：证明：设 ，则有2n+3个零点(ln din)。根据中值定理，存在于是。第17页/共98页

5、第十七页，共98页。Runge现象：并非插值点取得(qd)越多越好。解决办法：分段插值第18页/共98页第十八页，共98页。三次(sn c)样条插值 给定平面上n+1个插值点(xi,yi),构造分段三次(sn c)多项式(x),满足(xi)=yi,(x)可微，”(x)连续。第19页/共98页第十九页，共98页。第第2 2章章 数值数值(shz)(shz)微分和数值微分和数值(shz)(shz)积分积分第20页/共98页第二十页，共98页。数值微分差商法向前(xin qin)差商向后差商中心差商第21页/共98页第二十一页，共98页。n n插值法在 x 附近取点(xi,f(xi)构造(guzo)

6、插值多项式。n n样条法在 x 附近取点(xi,f(xi)构造(guzo)样条函数。n n f(x)(x)第22页/共98页第二十二页，共98页。例：用中心差商公式(gngsh)计算f(xi)。例：用向后差商公式(gngsh)计算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)第23页/共98页第二十三页，共98页。例：设xi=x0+i*h,i=1,.,n。计算(j sun)(xk)。解：第24页/共

7、98页第二十四页，共98页。n n误差估计n n前后(qinhu)差商中心差商插值微分第25页/共98页第二十五页，共98页。数值积分n n插值法第26页/共98页第二十六页，共98页。n n若积分公式对任意m次多项式都取等号，则称积分公式具有(jyu)至少m阶的代数精度。n n插值型积分公式的代数精度n。n n当积分节点 x0,.,xn 给定时，代数精度n的积分公式唯一。第27页/共98页第二十七页，共98页。例：设xi=a+i*h,i=0,.,n,h=(b-a)/n。计算(j sun)Newton-Cotes积分解：第28页/共98页第二十八页，共98页。特别，当n=1,2时，积分公式分别

8、(fnbi)称为梯形公式Simpson公式na1a2a3a4a5121/64/61/631/83/83/81/847/9032/9012/9032/907/90第29页/共98页第二十九页，共98页。n n误差估计n n特别，梯形公式(gngsh)和Simpson公式(gngsh)的误差为n n代数精度1n n代数精度3第30页/共98页第三十页，共98页。复化数值积分第31页/共98页第三十一页，共98页。n n梯形(txng)公式n nSimpson公式第32页/共98页第三十二页，共98页。n nRichardson外推法n n我们要计算n n假设(jish)n n则n n有比 和 更高

9、的精度。n n误差估计第33页/共98页第三十三页，共98页。n nRomberg积分(jfn)公式n n 等分的梯形公式，n n瑕积分(jfn)n n重积分(jfn)n nGauss-Legendre积分(jfn)第34页/共98页第三十四页，共98页。定理：假设 满足则插值积分公式具有2n+1阶的代数精度。证明：课本(kbn)21页性质1.3：若f(x)为m次多项式，则fx0,.,xn,x为m-n-1次多项式。第35页/共98页第三十五页，共98页。n n求多项式空间在内积下的标准正交基。n n解法1：对任意(rny)基作Gram-Schmidt正交化。n n解法2：对任意(rny)度量方

10、阵作相合对角化。n n解法3：求解正交关系的线性方程组。n n解法4：Legendre多项式第36页/共98页第三十六页，共98页。第第3 3章章 曲线拟合的最小二乘法曲线拟合的最小二乘法(chngf)(chngf)第37页/共98页第三十七页，共98页。曲线拟合对区间(q jin)I 上的连续函数 f，构造特定类型的函数 使 f。对离散数据序列(xi,yi),i=1,2,m，构造特定类型的函数 使(xi)yi。最小二乘法求 使最小。求 使最小。第38页/共98页第三十八页，共98页。多项式拟合(n h)其中 是标准正交基，。求使 最小。第39页/共98页第三十九页，共98页。奇异值分解(fn

11、ji)Moore-Penrose广义逆矛盾方程组的解第40页/共98页第四十页，共98页。其他类型的离散数据(shj)拟合 第41页/共98页第四十一页，共98页。第第4 4章章 非线性方程非线性方程(fngchng)(fngchng)求求根根第42页/共98页第四十二页，共98页。问题求f(x)=0在区间a,b内的实根求f(x)=0在x0附近的一个(y)实根求f(x)=0在x0附近的一个(y)复根求多项式f(x)=0的所有复根求非线性方程组的根方法用近似函数(x)的根逼近f(x)的根。第43页/共98页第四十三页，共98页。二分法已知f(a)f(b)0，设c=(a+b)/2。若f(a)f(c

12、)0则根在b,c内。当|f(c)|或|b-a|时，输出(shch)c。迭代步数：O(log2)第44页/共98页第四十四页，共98页。不动点当|(x)|L1时，|xk+1-|L|xk-|。当|xn+1-xn|时，输出(shch)xn。迭代步数：O(logL)Lipschitz常数(chngsh)线性收敛(shulin)第45页/共98页第四十五页，共98页。Newton法（一阶Taylor展开(zhn ki)）当|f(xk)|或|xk+1-xk|时，输出(shch)xk+1。迭代步数：O(loglog)二次收敛(shulin)第46页/共98页第四十六页，共98页。Newton法（p重根情形(

13、qng xing)）第47页/共98页第四十七页，共98页。用Newton迭代法求 f(z)=z32z+2 的根。当初值分别位于红、蓝、绿色区域时，迭代收敛(shulin)到三个根。当初值位于黑色区域时，迭代陷入死循环 010。图片引自John Hubbard,Dierk Schleicher,Scott Sutherland,How to find all roots of complex polynomials,Inventiones mathematicae 146,1-33(2001).第48页/共98页第四十八页，共98页。弦截法（线性插值）当|f(xk)|或|xk+1-xk|时，输

14、出(shch)xk+1。迭代步数：O(loglog)第49页/共98页第四十九页，共98页。弦截法的收敛(shulin)速度第50页/共98页第五十页，共98页。Newton法解非线性方程组求的所有复根(f n)等价于求 x1,xn 使 f(t)=(t-x1)(t-xn)。第51页/共98页第五十一页，共98页。其他求根方法(fngf)Brent（反插值 x=(y)）Halley（二阶Taylor展开）Muller（二次插值）有理插值第52页/共98页第五十二页，共98页。第第5 5章章 解线性方程组的直接解线性方程组的直接(zhji)(zhji)法法第53页/共98页第五十三页，共98页。问

15、题：求解n元线性方程组AX=B。方法(fngf)？速度？精度？存储？下三角方程组上三角方程组 n(n-1)/2次加减法，n(n+1)/2次乘除法。第54页/共98页第五十四页，共98页。Gauss消元法解一般(ybn)方程组 (2n3+3n2-5n)/6次加减法，(n3+3n2-n)/3次乘除法。第55页/共98页第五十五页，共98页。追赶(zhugn)法解三对角方程组 3n-3次加减法，5n-4次乘除法。第56页/共98页第五十六页，共98页。线性方程组解的精度(jn d)矩阵条件数第57页/共98页第五十七页，共98页。Gauss消元法的实质是LU分解存在性？A的顺序主子(zh zi)式0

16、。唯一性？L1U1=L2U2 L1-1L2=U1U2-1 对角精确度？A-1b的相对误差(L,U,b)的相对误差cond(L)cond(U)。第58页/共98页第五十八页，共98页。Dolittle分解(fnji)Courant分解(fnji)第59页/共98页第五十九页，共98页。全/列/行主元分解(fnji)LDLT分解(fnji)、Cholesky分解(fnji)第60页/共98页第六十页，共98页。QR分解(fnji)第61页/共98页第六十一页，共98页。SVD分解Givens旋转(xunzhun)Householder反射第62页/共98页第六十二页，共98页。第第6 6章章 解线

17、性方程组的迭代法解线性方程组的迭代法第63页/共98页第六十三页，共98页。Jacobi迭代(di di)Gauss-Seidel迭代(di di)第64页/共98页第六十四页，共98页。迭代法解线性方程组 A X=BA Xk+1 B=C(A Xk B)C 称为 Conditioner，满足(C)1或|C|1通常(tngchng)取 C=I A-1，其中 A，于是Xk+1=Xk -1(A Xk B)第65页/共98页第六十五页，共98页。Jacobi迭代(di di)：=D定理：A行对角优、或A列对角优 Jacobi迭代(di di)收敛。Gauss-Seidel迭代(di di)：=D+L定

18、理：A行对角优、或A列对角优、或A正定 Gauss-Seidel迭代(di di)收敛。第66页/共98页第六十六页，共98页。松弛迭代：=w-1D+L定理：松弛迭代收敛(shulin)0w2定理：A正定且0w2 松弛迭代收敛(shulin)Newton迭代求 A-1：Xk+1=2 Xk Xk A Xk第67页/共98页第六十七页，共98页。第第7 7章章 计算计算(j sun)(j sun)矩阵的特征矩阵的特征值值和特征向量和特征向量第68页/共98页第六十八页，共98页。问题1：求复方阵的模最大(最小)特征值。方法(fngf)：幂法、反幂法问题2：求复方阵的所有特征值。方法(fngf)：Q

19、R 迭代问题3：求Hermite方阵的所有特征值。方法(fngf)：Jacobi 方法(fngf)第69页/共98页第六十九页，共98页。幂法当 A 只有一个模最大的特征值max，并且 x0 与max 的特征向量 amax 不正交时当 A 的模最大的特征值都相同时，以上迭代仍然(rngrn)收敛。第70页/共98页第七十页，共98页。当 A 的模最大的特征值各不相同时，可以(ky)选取数 s 使 A-s I 的模最大的特征值只有一个。当 A 恰有 m 个模最大的特征值时，有 R 的特征值就是 A 的模最大的特征值。第71页/共98页第七十一页，共98页。反幂法当 A 只有一个模最小的特征值mi

20、n，并且 x0 与min 的特征向量 amin 不正交时计算(j sun)A-s I 的模最小的特征值等价于计算(j sun)A 的最接近 s 的特征值。第72页/共98页第七十二页，共98页。QR 迭代利用(lyng)QR 分解，酉相似 A 为上三角。QR 迭代的本质是幂法当 时，QR 迭代收敛。可对 A-s I 作 QR 分解，加速收敛。第73页/共98页第七十三页，共98页。Jacobi 方法通过 Givens 旋转，逐渐减小非对角(du jio)元。本质是 2 阶 Hermite 方阵的酉相似。Jacobi 方法具有 2 阶收敛速度。第74页/共98页第七十四页，共98页。复矩阵的奇异

21、值分解 A=UV一般方法AH A=VH2 V 或 A AH=U2 UHQR 迭代Jacobi 方法计算(j sun)2 阶方阵的 SVD第75页/共98页第七十五页，共98页。第第8 8章章 常微分方程常微分方程(wi fn fn(wi fn fn chn)chn)数值解数值解第76页/共98页第七十六页，共98页。问题：求解一阶常微分方程(wi fn fn chn)的初值问题：解法：化微分方程(wi fn fn chn)为积分方程第77页/共98页第七十七页，共98页。Euler折线法向前(xin qin)Euler公式向后Euler公式Picard迭代中心Euler公式梯形公式改进的Eul

22、er公式第78页/共98页第七十八页，共98页。Runge-Kutta方法选取(xunq)xi,cij 使 yr 有最高精度 p，即r1,2,3,45,6,78,910,11,.pp=rp=r-1p=r-2p r-2第79页/共98页第七十九页，共98页。Runge-Kutta方法的误差(wch)估计设满足Lipschitz条件设满足初值误差(wch)截断误差(wch)整体误差(wch)第80页/共98页第八十页，共98页。线性多步法(*)其中(qzhng)(t)为 f(t,y(t)的 q 次插值多项式。当 xn,xn-q 为插值节点时，(*)称为显式Adams公式。当 xn+1,xn+1-q

23、 为插值节点时，(*)称为隐式Adams公式。第81页/共98页第八十一页，共98页。一阶常微分方程组的初值问题：解法(ji f)：同一阶常微分方程的初值问题。第82页/共98页第八十二页，共98页。高阶常微分方程的初值问题解法(ji f)：令化方程为第83页/共98页第八十三页，共98页。单步法(*)收敛性稳定性将(*)应用于方程y=y，得 yn+1=E(h)yn。当|E(h)|1时，称(*)绝对稳定的。称复数 h:|E(h)|1为绝对稳定区域。称实数(shsh)h:|E(h)|1为绝对稳定区间。第84页/共98页第八十四页，共98页。复习第85页/共98页第八十五页，共98页。第第第第0

24、0章绪论章绪论章绪论章绪论(xln)(xln)n n误差的定义误差的定义n n向量向量(xingling)(xingling)的范数的范数n n矩阵的范数、条件数、谱半径矩阵的范数、条件数、谱半径第86页/共98页第八十六页，共98页。第第第第1章插值章插值章插值章插值n nLagrangeLagrange插值插值n n差商、差商、NewtonNewton插值插值n nHermiteHermite插值插值n n插值公式的截断误差插值公式的截断误差n nRungeRunge现象现象(xinxing)(xinxing)n n样条函数样条函数第87页/共98页第八十七页，共98页。第第2章数值章数值

25、(shz)微分和数值微分和数值(shz)积分积分n n差商型数值微分、插值型数值微分、微分公式的截差商型数值微分、插值型数值微分、微分公式的截断误差断误差n n插值型数值积分插值型数值积分(jfn)(jfn)、复化数值积分、复化数值积分(jfn)(jfn)、积分积分(jfn)(jfn)公式的截断误差、代数精度公式的截断误差、代数精度n n外推法、外推法、RombergRomberg积分积分(jfn)(jfn)、Gauss-LegendreGauss-Legendre积积分分(jfn)(jfn)n n矩形域上的二重积分矩形域上的二重积分(jfn)(jfn)第88页/共98页第八十八页，共98页。

26、第第第第3 3章最小二乘拟合章最小二乘拟合章最小二乘拟合章最小二乘拟合(n h)(n h)n n参数拟合参数拟合(n h)(n h)问题问题 矛盾线性方程组的最小二矛盾线性方程组的最小二乘解乘解第89页/共98页第八十九页，共98页。第第4章非线性方程章非线性方程(fngchng)求根求根n n对分法对分法n n迭代法迭代法n nNewtonNewton法法n n弦截法弦截法n n收敛收敛(shulin)(shulin)条件、收敛条件、收敛(shulin)(shulin)阶数、计算阶数、计算复杂度复杂度n nNewtonNewton法解非线性方程组法解非线性方程组第90页/共98页第九十页，共

27、98页。第第第第5 5章直接章直接章直接章直接(zhji)(zhji)法解线性方程组法解线性方程组法解线性方程组法解线性方程组n n消元法消元法GaussGauss消元、列主元消元、全主元消元、追赶消元、列主元消元、全主元消元、追赶(zhugn)(zhugn)法法n n分解法分解法LULU分解、分解、PLUPLU分解、分解、PLUQ PLUQ分解、分解、DolittleDolittle分解、分解、CourantCourant分解、分解、LDLTLDLT分解、分解、QRQR分解分解n n计算复杂度计算复杂度第91页/共98页第九十一页，共98页。第第6 6章迭代法解线性方程组章迭代法解线性方程组

28、n n迭代格式迭代格式n n迭代矩阵迭代矩阵(j zhn)(j zhn)n n收敛条件收敛条件n nJacobiJacobi迭代迭代n nGauss-SeidelGauss-Seidel迭代迭代n n松弛迭代松弛迭代第92页/共98页第九十二页，共98页。第第第第7 7章矩阵章矩阵章矩阵章矩阵(j zhn)(j zhn)的特征值和特征向量的特征值和特征向量的特征值和特征向量的特征值和特征向量n n利用利用(lyng)(lyng)幂法计算模最大特征值及其特征向量幂法计算模最大特征值及其特征向量n n利用利用(lyng)(lyng)反幂法计算模最小特征值及其特征向反幂法计算模最小特征值及其特征向量

29、量n n利用利用(lyng)QR(lyng)QR方法计算所有特征值方法计算所有特征值n n利用利用(lyng)Jacobi(lyng)Jacobi方法计算实对称阵的所有特征方法计算实对称阵的所有特征值及其特征向量值及其特征向量第93页/共98页第九十三页，共98页。n n幂法幂法n n反幂法反幂法n nQRQR方法方法(fngf)(fngf)n nJacobiJacobi方法方法(fngf)(fngf)第94页/共98页第九十四页，共98页。第第8章常微分方程章常微分方程(wi fn fn chn)数值解数值解常微分方程常微分方程(fngchng)(fngchng)初值问题初值问题化为积分方程

30、化为积分方程(fngchng)(fngchng)利用利用EulerEuler公式求解公式求解利用利用Runge-KuttaRunge-Kutta公式求解公式求解利用利用AdamsAdams公式求解公式求解第95页/共98页第九十五页，共98页。n n向前向前EulerEuler公式公式n n向后向后EulerEuler公式公式n nPicardPicard迭代迭代n n中心中心(zhngxn)Euler(zhngxn)Euler公式公式n n梯形公式梯形公式n n改进的改进的n nEulerEuler公式公式n nAdamsAdams公式公式第96页/共98页第九十六页，共98页。结束第97页/共98页第九十七页，共98页。感谢您的观看感谢您的观看(gunkn)！第98页/共98页第九十八页，共98页。