数值计算方法及算法幻灯片.ppt

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

1、数值计算方法及算法第1页，共98页，编辑于2022年，星期六第0章 绪论第2页，共98页，编辑于2022年，星期六 数学建模 数值计算实际问题数学问题近似解什么是数值计算方法？什么是“好的”数值计算方法？误差小 误差分析耗时少 复杂度分析抗干扰 稳定性分析第3页，共98页，编辑于2022年，星期六误差的类型绝对误差真实值近似值相对误差绝对误差真实值误差的来源原始误差、截断误差、舍入误差输入计算输出真实值近似值第4页，共98页，编辑于2022年，星期六一些例子：计算地球的体积计算计算如何减小计算误差？选择好的算法、提高计算精度范数的定义满足非负性,齐次性,三角不等式的实函数第5页，共98页，编辑

2、于2022年，星期六常用的向量范数常用的矩阵范数矩阵的谱半径例：计算矩阵 的范数和谱半径。例：范数在误差估计中的应用第6页，共98页，编辑于2022年，星期六第1章 插值第7页，共98页，编辑于2022年，星期六函数逼近用未知函数f(x)的值构造近似函数(x)。要求误差小、形式简单、容易计算。常用的函数逼近方法插值：(xi)=yi,i=0,1,n.拟合：|(x)-f(x)|尽可能小通常取(x)=a00(x)+ann(x)，其中i(x)为一组基函数。第8页，共98页，编辑于2022年，星期六多项式插值 给定平面上n+1个插值点(xi,yi),构造n次多项式(x),满足(xi)=yi,i=0,1,

3、n.第9页，共98页，编辑于2022年，星期六单项式插值第10页，共98页，编辑于2022年，星期六Lagrange插值第11页，共98页，编辑于2022年，星期六Newton插值第12页，共98页，编辑于2022年，星期六差商表012n012.nk阶差商第13页，共98页，编辑于2022年，星期六差商的性质以x0,xn为节点的n次插值多项式(x)的首项系数等于fx0,xn。证明：分别以x0,xn-1和x1,xn为节点构造n-1次插值多项式1(x)和2(x)，则有对n用归纳法。fx0,xn与x0,xn的顺序无关。第14页，共98页，编辑于2022年，星期六误差估计：证明：设，则有n+2个零点。

4、根据中值定理，存在于是。第15页，共98页，编辑于2022年，星期六Hermite插值给定平面上n+1个插值点(xi,yi,mi),构造2n+1次多项式(x),满足(xi)=yi,(xi)=mi,i=0,1,n.第16页，共98页，编辑于2022年，星期六单项式基函数Lagrange基函数第17页，共98页，编辑于2022年，星期六误差估计：证明：设，则有2n+3个零点。根据中值定理，存在于是。第18页，共98页，编辑于2022年，星期六Runge现象：并非插值点取得越多越好。解决办法：分段插值第19页，共98页，编辑于2022年，星期六三次样条插值给定平面上n+1个插值点(xi,yi),构造

5、分段三次多项式(x),满足(xi)=yi,(x)可微，”(x)连续。第20页，共98页，编辑于2022年，星期六第2章 数值微分和数值积分第21页，共98页，编辑于2022年，星期六数值微分差商法向前差商向后差商中心差商第22页，共98页，编辑于2022年，星期六插值法在x附近取点(xi,f(xi)构造插值多项式。样条法在x附近取点(xi,f(xi)构造样条函数。f(x)(x)第23页，共98页，编辑于2022年，星期六例：用中心差商公式计算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

6、.00.10.20.30.4f(x)0.8187310.9048371.0000001.1051711.221403f(x)第24页，共98页，编辑于2022年，星期六例：设xi=x0+i*h,i=1,.,n。计算(xk)。解：第25页，共98页，编辑于2022年，星期六误差估计前后差商中心差商插值微分第26页，共98页，编辑于2022年，星期六数值积分插值法第27页，共98页，编辑于2022年，星期六若积分公式对任意m次多项式都取等号，则称积分公式具有至少m阶的代数精度。插值型积分公式的代数精度n。当积分节点x0,.,xn给定时，代数精度n的积分公式唯一。第28页，共98页，编辑于2022年

7、，星期六例：设xi=a+i*h,i=0,.,n,h=(b-a)/n。计算Newton-Cotes积分解：第29页，共98页，编辑于2022年，星期六特别，当n=1,2时，积分公式分别称为梯形公式Simpson公式na1a2a3a4a5121/64/61/631/83/83/81/847/9032/9012/9032/907/90第30页，共98页，编辑于2022年，星期六误差估计特别，梯形公式和Simpson公式的误差为代数精度1代数精度3第31页，共98页，编辑于2022年，星期六复化数值积分第32页，共98页，编辑于2022年，星期六梯形公式Simpson公式第33页，共98页，编辑于20

8、22年，星期六Richardson外推法我们要计算假设则有比和更高的精度。误差估计第34页，共98页，编辑于2022年，星期六Romberg积分公式等分的梯形公式，瑕积分重积分Gauss-Legendre积分第35页，共98页，编辑于2022年，星期六定理：假设满足则插值积分公式具有2n+1阶的代数精度。证明：课本21页性质1.3：若f(x)为m次多项式，则fx0,.,xn,x为m-n-1次多项式。第36页，共98页，编辑于2022年，星期六求多项式空间在内积下的标准正交基。解法1：对任意基作Gram-Schmidt正交化。解法2：对任意度量方阵作相合对角化。解法3：求解正交关系的线性方程组。

9、解法4：Legendre多项式第37页，共98页，编辑于2022年，星期六第3章 曲线拟合的最小二乘法第38页，共98页，编辑于2022年，星期六曲线拟合对区间I上的连续函数f，构造特定类型的函数 使f。对离散数据序列(xi,yi),i=1,2,m，构造特定类型的函数 使(xi)yi。最小二乘法求使最小。求使最小。第39页，共98页，编辑于2022年，星期六多项式拟合其中是标准正交基，。求使最小。第40页，共98页，编辑于2022年，星期六奇异值分解Moore-Penrose广义逆矛盾方程组的解第41页，共98页，编辑于2022年，星期六其他类型的离散数据拟合第42页，共98页，编辑于2022

10、年，星期六第4章 非线性方程求根第43页，共98页，编辑于2022年，星期六问题求f(x)=0在区间a,b内的实根求f(x)=0在x0附近的一个实根求f(x)=0在x0附近的一个复根求多项式f(x)=0的所有复根求非线性方程组的根方法用近似函数(x)的根逼近f(x)的根。第44页，共98页，编辑于2022年，星期六二分法已知f(a)f(b)0，设c=(a+b)/2。若f(a)f(c)0则根在b,c内。当|f(c)|或|b-a|时，输出c。迭代步数：O(log2)第45页，共98页，编辑于2022年，星期六不动点当|(x)|L1时，|xk+1-|L|xk-|。当|xn+1-xn|时，输出xn。迭

11、代步数：O(logL)Lipschitz常数线性收敛第46页，共98页，编辑于2022年，星期六Newton法（一阶Taylor展开）当|f(xk)|或|xk+1-xk|时，输出xk+1。迭代步数：O(loglog)二次收敛第47页，共98页，编辑于2022年，星期六Newton法（p重根情形）第48页，共98页，编辑于2022年，星期六用Newton迭代法求f(z)=z32z+2的根。当初值分别位于红、蓝、绿色区域时，迭代收敛到三个根。当初值位于黑色区域时，迭代陷入死循环010。图片引自JohnHubbard,DierkSchleicher,ScottSutherland,Howtofind

12、allrootsofcomplexpolynomials,Inventionesmathematicae146,1-33(2001).第49页，共98页，编辑于2022年，星期六弦截法（线性插值）当|f(xk)|或|xk+1-xk|时，输出xk+1。迭代步数：O(loglog)第50页，共98页，编辑于2022年，星期六弦截法的收敛速度第51页，共98页，编辑于2022年，星期六Newton法解非线性方程组求的所有复根等价于求x1,xn使f(t)=(t-x1)(t-xn)。第52页，共98页，编辑于2022年，星期六其他求根方法Brent（反插值x=(y)）Halley（二阶Taylor展开）

13、Muller（二次插值）有理插值第53页，共98页，编辑于2022年，星期六第5章 解线性方程组的直接法第54页，共98页，编辑于2022年，星期六问题：求解n元线性方程组AX=B。方法？速度？精度？存储？下三角方程组上三角方程组n(n-1)/2次加减法，n(n+1)/2次乘除法。第55页，共98页，编辑于2022年，星期六Gauss消元法解一般方程组(2n3+3n2-5n)/6次加减法，(n3+3n2-n)/3次乘除法。第56页，共98页，编辑于2022年，星期六追赶法解三对角方程组3n-3次加减法，5n-4次乘除法。第57页，共98页，编辑于2022年，星期六线性方程组解的精度矩阵条件数第

14、58页，共98页，编辑于2022年，星期六Gauss消元法的实质是LU分解存在性？A的顺序主子式0。唯一性？L1U1=L2U2L1-1L2=U1U2-1对角精确度？A-1b的相对误差(L,U,b)的相对误差cond(L)cond(U)。第59页，共98页，编辑于2022年，星期六Dolittle分解Courant分解第60页，共98页，编辑于2022年，星期六全/列/行主元分解LDLT分解、Cholesky分解第61页，共98页，编辑于2022年，星期六QR分解第62页，共98页，编辑于2022年，星期六SVD分解Givens旋转Householder反射第63页，共98页，编辑于2022年，

15、星期六第6章 解线性方程组的迭代法第64页，共98页，编辑于2022年，星期六Jacobi迭代Gauss-Seidel迭代第65页，共98页，编辑于2022年，星期六迭代法解线性方程组 A X=BA Xk+1 B=C(A Xk B)C 称为 Conditioner，满足(C)1或|C|1通常取 C=I A-1，其中 A，于是Xk+1=Xk -1(A Xk B)第66页，共98页，编辑于2022年，星期六Jacobi迭代：=D定理：A行对角优、或A列对角优 Jacobi迭代收敛。Gauss-Seidel迭代：=D+L定理：A行对角优、或A列对角优、或A正定 Gauss-Seidel迭代收敛。第6

16、7页，共98页，编辑于2022年，星期六松弛迭代：=w-1D+L定理：松弛迭代收敛 0w2定理：A正定且0w2 松弛迭代收敛Newton迭代求 A-1：Xk+1=2 Xk Xk A Xk第68页，共98页，编辑于2022年，星期六第7章 计算矩阵的特征值和特征向量第69页，共98页，编辑于2022年，星期六问题1：求复方阵的模最大(最小)特征值。方法：幂法、反幂法问题2：求复方阵的所有特征值。方法：QR迭代问题3：求Hermite方阵的所有特征值。方法：Jacobi方法第70页，共98页，编辑于2022年，星期六幂法当 A 只有一个模最大的特征值max，并且 x0 与max 的特征向量 ama

17、x 不正交时当 A 的模最大的特征值都相同时，以上迭代仍然收敛。第71页，共98页，编辑于2022年，星期六当 A 的模最大的特征值各不相同时，可以选取数 s 使 A-s I 的模最大的特征值只有一个。当 A 恰有 m 个模最大的特征值时，有 R 的特征值就是 A 的模最大的特征值。第72页，共98页，编辑于2022年，星期六反幂法当 A 只有一个模最小的特征值min，并且 x0 与min 的特征向量 amin 不正交时计算 A-s I 的模最小的特征值等价于计算 A 的最接近 s 的特征值。第73页，共98页，编辑于2022年，星期六QR 迭代利用 QR 分解，酉相似 A 为上三角。QR 迭

18、代的本质是幂法当 时，QR 迭代收敛。可对 A-s I 作 QR 分解，加速收敛。第74页，共98页，编辑于2022年，星期六Jacobi 方法通过 Givens 旋转，逐渐减小非对角元。本质是 2 阶 Hermite 方阵的酉相似。Jacobi 方法具有 2 阶收敛速度。第75页，共98页，编辑于2022年，星期六复矩阵的奇异值分解 A=UV一般方法AH A=VH2 V 或 A AH=U2 UHQR 迭代Jacobi 方法计算 2 阶方阵的 SVD第76页，共98页，编辑于2022年，星期六第8章 常微分方程数值解第77页，共98页，编辑于2022年，星期六问题：求解一阶常微分方程的初值问题

19、：解法：化微分方程为积分方程第78页，共98页，编辑于2022年，星期六Euler折线法向前Euler公式向后Euler公式Picard迭代中心Euler公式梯形公式改进的Euler公式第79页，共98页，编辑于2022年，星期六Runge-Kutta方法选取xi,cij使yr有最高精度p，即r1,2,3,45,6,78,910,11,.pp=rp=r-1p=r-2p r-2第80页，共98页，编辑于2022年，星期六Runge-Kutta方法的误差估计设满足Lipschitz条件设满足初值误差截断误差整体误差第81页，共98页，编辑于2022年，星期六线性多步法(*)其中(t)为 f(t,y

20、(t)的 q 次插值多项式。当 xn,xn-q 为插值节点时，(*)称为显式Adams公式。当 xn+1,xn+1-q 为插值节点时，(*)称为隐式Adams公式。第82页，共98页，编辑于2022年，星期六一阶常微分方程组的初值问题：解法：同一阶常微分方程的初值问题。第83页，共98页，编辑于2022年，星期六高阶常微分方程的初值问题解法：令化方程为第84页，共98页，编辑于2022年，星期六单步法(*)收敛性稳定性将(*)应用于方程y=y，得 yn+1=E(h)yn。当|E(h)|1时，称(*)绝对稳定的。称复数 h:|E(h)|1为绝对稳定区域。称实数 h:|E(h)|1为绝对稳定区间。

21、第85页，共98页，编辑于2022年，星期六复 习第86页，共98页，编辑于2022年，星期六第0章绪论误差的定义向量的范数矩阵的范数、条件数、谱半径第87页，共98页，编辑于2022年，星期六第1章插值Lagrange插值差商、Newton插值Hermite插值插值公式的截断误差Runge现象样条函数第88页，共98页，编辑于2022年，星期六第2章数值微分和数值积分差商型数值微分、插值型数值微分、微分公式的截断误差插值型数值积分、复化数值积分、积分公式的截断误差、代数精度外推法、Romberg积分、Gauss-Legendre积分矩形域上的二重积分第89页，共98页，编辑于2022年，星期

22、六第3章最小二乘拟合参数拟合问题 矛盾线性方程组的最小二乘解第90页，共98页，编辑于2022年，星期六第4章非线性方程求根对分法迭代法Newton法弦截法收敛条件、收敛阶数、计算复杂度Newton法解非线性方程组第91页，共98页，编辑于2022年，星期六第5章直接法解线性方程组消元法Gauss消元、列主元消元、全主元消元、追赶法分解法LU分解、PLU分解、PLUQ分解、Dolittle分解、Courant分解、LDLT分解、QR分解计算复杂度第92页，共98页，编辑于2022年，星期六第6章迭代法解线性方程组迭代格式迭代矩阵收敛条件Jacobi迭代Gauss-Seidel迭代松弛迭代第93

23、页，共98页，编辑于2022年，星期六第7章矩阵的特征值和特征向量利用幂法计算模最大特征值及其特征向量利用反幂法计算模最小特征值及其特征向量利用QR方法计算所有特征值利用Jacobi方法计算实对称阵的所有特征值及其特征向量第94页，共98页，编辑于2022年，星期六幂法反幂法QR方法Jacobi方法第95页，共98页，编辑于2022年，星期六第8章常微分方程数值解常微分方程初值问题化为积分方程利用Euler公式求解利用Runge-Kutta公式求解利用Adams公式求解第96页，共98页，编辑于2022年，星期六向前Euler公式向后Euler公式Picard迭代中心Euler公式梯形公式改进的Euler公式Adams公式第97页，共98页，编辑于2022年，星期六结 束第98页，共98页，编辑于2022年，星期六