数值计算方法与算法

数值计算方法与算法,教学目标,掌握常用的数值计算方法掌握计算方法的数学原理学会选择恰当的计算方法学会使用流行的计算软件,教学计划,教材及参考,数值计算方法与算法，张韵华、奚梅成、陈效群编，科学出版社，2006。科学计算导论，MichaelT.Heath著，张威、贺华、冷爱萍译，清华大学出版社，2005。数值计算方法解题指导，张韵华编，科学出版社，2003。网络教学资源,联系方式,教师：王新茂xinmao理化大楼16#016，3607565助教：杨荣rongyang136-15607693,第0章绪论,数学建模数值计算,实际问题数学问题近似解,什么是数值计算方法？什么是“好的”数值计算方法？误差小误差分析耗时少复杂度分析抗干扰稳定性分析,误差的类型绝对误差真实值近似值相对误差绝对误差真实值误差的来源原始误差、截断误差、舍入误差,一些例子：计算地球的体积计算计算如何减小计算误差？选择好的算法、提高计算精度范数的定义满足非负性,齐次性,三角不等式的实函数,常用的向量范数常用的矩阵范数矩阵的谱半径例：计算矩阵的范数和谱半径。例：范数在误差估计中的应用,作业一、145页习题6第1,2题.作业二、利用公式编写两个计算ex的C程序(一个用单精度,另一个用双精度).令x=1,5,10,15,20,比较它们和库函数exp(x)之间的运行时间和计算误差.思考如何减小误差？,第1章插值,函数逼近用未知函数f(x)的值构造近似函数(x)。要求误差小、形式简单、容易计算。常用的函数逼近方法插值：(xi)=yi,i=0,1,n.拟合：|(x)-f(x)|尽可能小通常取(x)=a00(x)+ann(x)，其中i(x)为一组基函数。,多项式插值给定平面上n+1个插值点(xi,yi),构造n次多项式(x),满足(xi)=yi,i=0,1,n.,单项式插值,Lagrange插值,Newton插值,k阶差商,差商的性质以x0,xn为节点的n次插值多项式(x)的首项系数等于fx0,xn。证明：分别以x0,xn-1和x1,xn为节点构造n-1次插值多项式1(x)和2(x)，则有对n用归纳法。fx0,xn与x0,xn的顺序无关。,误差估计：证明：设，则有n+2个零点。根据中值定理，存在于是。,Hermite插值给定平面上n+1个插值点(xi,yi,mi),构造2n+1次多项式(x),满足(xi)=yi,(xi)=mi,i=0,1,n.,单项式基函数,Lagrange基函数,误差估计：证明：设，则有2n+3个零点。根据中值定理，存在于是。,Runge现象：并非插值点取得越多越好。解决办法：分段插值,三次样条插值给定平面上n+1个插值点(xi,yi),构造分段三次多项式(x),满足(xi)=yi,(x)可微，”(x)连续。,作业一、习题1第2,4,6,8,10,12,14,16题。作业二、在半圆上随机选取10个点,构造插值多项式,画出函数图像,并比较3种插值方法的计算误差。作业三、思考3种插值系数之间的关系。比较3种插值方法的优缺点和应用范围。,第2章数值微分和数值积分,数值微分差商法向前差商向后差商中心差商,插值法在x附近取点(xi,f(xi)构造插值多项式。样条法在x附近取点(xi,f(xi)构造样条函数。f(x)(x),例：用中心差商公式计算f(xi)。例：用向后差商公式计算f(0.2),f(0.4)。,例：设xi=x0+i*h,i=1,.,n。计算(xk)。解：,误差估计前后差商中心差商插值微分,数值积分插值法,若积分公式对任意m次多项式都取等号，则称积分公式具有至少m阶的代数精度。插值型积分公式的代数精度n。当积分节点x0,.,xn给定时，代数精度n的积分公式唯一。,例：设xi=a+i*h,i=0,.,n,h=(b-a)/n。计算Newton-Cotes积分解：,特别，当n=1,2时，积分公式分别称为梯形公式Simpson公式,误差估计特别，梯形公式和Simpson公式的误差为代数精度1代数精度3,复化数值积分,梯形公式Simpson公式,Richardson外推法我们要计算假设则有比和更高的精度。误差估计,Romberg积分公式等分的梯形公式，瑕积分重积分Gauss-Legendre积分,定理：假设满足则插值积分公式具有2n+1阶的代数精度。证明：课本21页性质1.3：若f(x)为m次多项式，则fx0,.,xn,x为m-n-1次多项式。,求多项式空间在内积下的标准正交基。解法1：对任意基作Gram-Schmidt正交化。解法2：对任意度量方阵作相合对角化。解法3：求解正交关系的线性方程组。解法4：Legendre多项式,作业一、习题2第111题。作业二、使用各种方法计算的值，其中0x1，要求误差1e-9。,第3章曲线拟合的最小二乘法,曲线拟合对区间I上的连续函数f，构造特定类型的函数使f。对离散数据序列(xi,yi),i=1,2,m，构造特定类型的函数使(xi)yi。最小二乘法求使最小。求使最小。,多项式拟合其中是标准正交基，。求使最小。,奇异值分解Moore-Penrose广义逆矛盾方程组的解,其他类型的离散数据拟合,作业一、习题3第15题。作业二、对下列数据，用最小二乘法求形如的经验公式。,第4章非线性方程求根,问题求f(x)=0在区间a,b内的实根求f(x)=0在x0附近的一个实根求f(x)=0在x0附近的一个复根求多项式f(x)=0的所有复根求非线性方程组的根方法用近似函数(x)的根逼近f(x)的根。,二分法已知f(a)f(b)0则根在b,c内。当|f(c)|或|b-a|时，输出c。迭代步数：O(log2),不动点当|(x)|L1时，|xk+1-|L|xk-|。当|xn+1-xn|时，输出xn。迭代步数：O(logL),Lipschitz常数,线性收敛,Newton法（一阶Taylor展开）,当|f(xk)|或|xk+1-xk|时，输出xk+1。迭代步数：O(loglog),二次收敛,Newton法（p重根情形）,用Newton迭代法求f(z)=z32z+2的根。当初值分别位于红、蓝、绿色区域时，迭代收敛到三个根。当初值位于黑色区域时，迭代陷入死循环010。图片引自JohnHubbard,DierkSchleicher,ScottSutherland,Howtofindallrootsofcomplexpolynomials,Inventionesmathematicae146,1-33(2001).,弦截法（线性插值）,当|f(xk)|或|xk+1-xk|时，输出xk+1。迭代步数：O(loglog),弦截法的收敛速度,Newton法解非线性方程组求的所有复根等价于求x1,xn使f(t)=(t-x1)(t-xn)。,其他求根方法Brent（反插值x=(y)）Halley（二阶Taylor展开）Muller（二次插值）有理插值,作业一、习题4第1、3、5、7、8题。作业二、比较各种求根方法的优缺点。,第5章解线性方程组的直接法,问题：求解n元线性方程组AX=B。方法？速度？精度？存储？下三角方程组上三角方程组n(n-1)/2次加减法，n(n+1)/2次乘除法。,Gauss消元法解一般方程组(2n3+3n2-5n)/6次加减法，(n3+3n2-n)/3次乘除法。,追赶法解三对角方程组3n-3次加减法，5n-4次乘除法。,线性方程组解的精度矩阵条件数,Gauss消元法的实质是LU分解存在性？A的顺序主子式0。唯一性？L1U1=L2U2L1-1L2=U1U2-1对角精确度？A-1b的相对误差(L,U,b)的相对误差cond(L)cond(U)。,Dolittle分解Courant分解,全/列/行主元分解LDLT分解、Cholesky分解,QR分解,SVD分解Givens旋转Householder反射,作业一、习题5第1-8题(1)。作业二、计算100阶Hilbert矩阵H的逆矩阵A以及AH-I的元素平方和。,第6章解线性方程组的迭代法,Jacobi迭代Gauss-Seidel迭代,迭代法解线性方程组AX=BAXk+1B=C(AXkB)C称为Conditioner，满足(C)1或|C|1通常取C=IA-1，其中A，于是Xk+1=Xk-1(AXkB),Jacobi迭代：=D定理：A行对角优、或A列对角优Jacobi迭代收敛。Gauss-Seidel迭代：=D+L定理：A行对角优、或A列对角优、或A正定Gauss-Seidel迭代收敛。,松弛迭代：=w-1D+L定理：松弛迭代收敛0w2定理：A正定且0w2松弛迭代收敛Newton迭代求A-1：Xk+1=2XkXkAXk,作业一、145页习题3、6、7。作业二、用迭代法计算10阶Hilbert矩阵H的逆矩阵A以及AH-I的元素平方和。,第7章计算矩阵的特征值和特征向量,问题1：求复方阵的模最大(最小)特征值。方法：幂法、反幂法问题2：求复方阵的所有特征值。方法：QR迭代问题3：求Hermite方阵的所有特征值。方法：Jacobi方法,幂法当A只有一个模最大的特征值max，并且x0与max的特征向量amax不正交时当A的模最大的特征值都相同时，以上迭代仍然收敛。,当A的模最大的特征值各不相同时，可以选取数s使A-sI的模最大的特征值只有一个。当A恰有m个模最大的特征值时，有R的特征值就是A的模最大的特征值。,反幂法当A只有一个模最小的特征值min，并且x0与min的特征向量amin不正交时计算A-sI的模最小的特征值等价于计算A的最接近s的特征值。,QR迭代利用QR分解，酉相似A为上三角。QR迭代的本质是幂法当时，QR迭代收敛。可对A-sI作QR分解，加速收敛。,Jacobi方法通过Givens旋转，逐渐减小非对角元。本质是2阶Hermite方阵的酉相似。Jacobi方法具有2阶收敛速度。,复矩阵的奇异值分解A=UV一般方法AHA=VH2V或AAH=U2UHQR迭代Jacobi方法计算2阶方阵的SVD,作业一、167页习题1(3)、2(2)、3(4)。作业二、计算10阶Hilbert矩阵的正交相似标准形以及过渡矩阵。,第8章常微分方程数值解,问题：求解一阶常微分方程的初值问题：解法：化微分方程为积分方程,Euler折线法向前Euler公式向后Euler公式Picard迭代中心Euler公式梯形公式改进的Euler公式,Runge-Kutta方法选取xi,cij使yr有最高精度p，即,Runge-Kutta方法的误差估计设满足Lipschitz条件设满足初值误差截断误差整体误差,线性多步法(*)其中(t)为f(t,y(t)的q次插值多项式。当xn,xn-q为插值节点时，(*)称为显式Adams公式。当xn+1,xn+1-q为插值节点时，(*)称为隐式Adams公式。,一阶常微分方程组的初值问题：解法：同一阶常微分方程的初值问题。,高阶常微分方程的初值问题解法：令化方程为,单步法(*)收敛性稳定性将(*)应用于方程y=y，得yn+1=E(h)yn。当|E(h)|1时，称(*)绝对稳