《数值分析习题课》PPT课件.ppt

数值分析 复习,第一章 绪论,1 绪论：数值分析的研究内容2 误差的来源和分类3 误差的表示4 误差的传播5 算法设计的若干原则,一、误差的分类（绝对误差，相对误差）,例1-1 设 x*=2.18是由精确值x 经过四舍五入得到的近似值。问 x的绝对误差限和相对误差限各是多少？,相对误差限为,二、有效数字,则称近似数 x* 具有 n 位有效数字。,定义 设数 x 的近似值可以表示为,其中 m 是整数,i (i=1,2, , n) 是0到9 中的一个数字，而1 0. 如果其绝对误差限为,结论：通过四舍五入原则求得的近似数，其有效数字就是从末尾到第一位非零数字之间的所有数字。,例1-2 下列近似数是通过四舍五入的方法得到的，试判定它们各有几位有效数字：,解：我们可以直接根据近似数来判断有效数字的位数，也可以通过绝对误差限来判断。,有5位有效数字。同理可以写出,可以得出 x2 , x3 , x4 各具有4、3、4 位有效数字。,x1* =87540，x2*=875410, x3*=0.00345, x4*= 0.3450 10-2,已知,例1-3 已知 e =2.718281828, 试判断下面两个近似数各有几位有效数字？,解：由于,而,所以,e1有7位有效数字。同理：,e2 只有6位有效数字。,三、算法设计的若干原则,1：两个很接近的数字不做减法: 2: 不用很小得数做分母(不用很大的数做分子),练习： 求方程 x2-56x+1=0 的两个根，使它们至少具有四位有效数字,第二章 插值与拟合,1、Lagrange插值多项式,Newton插值多项式的构造与插值余项估计，及证明过程。,2、 Hermite插值多项式的构造与插值余项估计， 带导数条件的插值多项式的构造方法，基于承袭性的算法，基函数法， 重节点差商表的构造； 3、分段插值及三次样条插值的构造,4、最小二乘拟合,掌握Lagrange 插值多项式的构造方法及具体结构掌握Lagrange插值多项式误差分析方法和证明方法掌握Newton插值多项式的形式及误差掌握差商表的构造过程,Newton插值多项式：,例1-3 已知f(x) 的五组数据(1,0)、(2,2)、(3,12)、(4,42)、(5,116),求 N4 (x)。如果再增加一个节点(6,282),求出N5(x)，并计算 N4(1.5)、N5(1.5).,解：先由前五组数据列差商表,1 02 23 124 425 116,2103074,41022,24,0.5,6 282,166,46,8,1,0.1,得到：,如果，再增加一点(6, 282),就在上表中增加一行计算差商,由Newton公式的递推式得到：,得到：,2.分段性插值有何优缺点？误差估计？（插值节点的选择）,1. 高次插值的Runge 现象，应如何避免？,3. Hermite插值的构造, 误差估计,4.三次样条函数的定义、构造过程,5.数据拟合的最小二乘法（可化为直线拟合的非线性拟合的处理方法）,解：,二、典型例题分析,例1. 令x00， x11，写出y(x)e-x的一次插值多项式L1(x) ,并估计插值误差（P55,t14题）,记x00， x11 , y0e-01，y1e-1;则函数ye-x以x0、 x1为节点的一次插值多项式为,因为 y(x)-e-x，y(x) e-x ，所以,推广：等距节点(h),二次插值的误差界是,例3 设f(x)x4，试利用拉格朗日插值余项定理写出以-1, 0, 1, 2为插值节点的三次插值多项式,解: 记f(x)以-1，0，1，2为插值节点的三次插值多项式为L3(x)由插值余项定理有,所以,例4证明由下列插值条件 所确定的拉格朗日插值多项式是一个二次多项式该例说明了什么问题?( t8),以x0，x2，x4为插值节点作f(x)的2次插值多项式p(x)，则,解:,x0 x2 x4,容易验证因而6个点(xi, yi)，i0 1,5均在二次曲线p(x)x2-1 上 换句话说，满足所给插值条件的拉格朗日插值多项式为 p(x)x2-1.,分析: 这是一个非标准插值问题,我们可以按各种思路去做可按两种方法去做:一种是先求牛顿或拉格朗目型插值,再通过待定系数法求Pn(x)；另一种是先求埃尔米特插值,再通过待定系数法确定Pn(x) 下面给出三种做法,例6 求一个次数不高于4的多项式P4(x)，使它满足P4(0)= P4(0)=0， P4(1)= P4(1)=1，P4(2)=1,解法一 先求满足P4(0)=0， P4(1)=1，P4(2)=1 的插值多项式P2(x)，易得,显然P4(x)满足P2(x)的插植条件，利用两个导数条件确定系数A，B由P4(0)=0, P4(1)=1解得A=1/4,B=-3/4. 故,设,解法二 先作满足埃尔米特插值多项式 H3(x),解法三 构造插值基函数求. 记x0=0，x1=1，x2=2，并设所求多项式为,其中li(x)均为次数不超过4的多项式且满足如下条件：,易知,例11 已知函数y=f(x) 的如下数据,试求其在区间0,3上的三次样条插值函数S(x)。,解 这里边界条件是,设,求得,已知,由方程组,及,得到方程组,解得,这样便求得,代入表达式,便得到所求的三次样条函数,例12 对如下数据作形如 y = a eb x 的拟合曲线,解: 由于函数集合=a eb x | a,b R 不成为线性空间，因此直接作拟合曲线是困难的。,在函数 y = a eb x 两端分别取对数得到,这时，需要将原函数表进行转换如下,令 z= ln y , A = ln a , B=b,则 z=A+Bx,ln y = ln a+bx,对 z=A+Bx 作线性拟合曲线，取,这时,得正则方程组,解得,于是有,拟合曲线为：,第三章数值积分,插值型积分公式Newton-Cotes 型求积公式复化求积公式Romberg算法Gauss积分数值微分,Simpson公式n=2,梯形公式 n=1,(1 ,2)需要掌握：,1. 等距节点(Newton-Cotes)的积分公式是如何构造的？,2. N点等距节点的积分公式及其误差式怎么表示？,3. 如何由上式给出梯形公式、Simpson公式及其误差？,复化梯形公式及其误差,例 3-1 用复化梯形公式计算积分 ，应将区间0,1多少等分，才可以使其截断误差不超过,解：复化梯形公式的误差为,而,从而,令,于是，只要将区间至少68等分,就可以达到需要的精度要求。,复化Simpson公式及其误差为：,要求：了解各种积分公式的原理，构造方法,会利用公式计算积分， （复化）梯形公式，(复化)Simpson公式及余项表达式，求解代数精度会利用代数精度构造积分公式，并用构造的积分公式计算相应积分值,Romberg算法的实现原理，计算，外推加速技术；数值微分公式的构造方法,一、确定数值积分公式或数值微分公式，并推出余项,根据代数精度的概念对Guass型求积公式，可借助Guass点与求积系数的关系确定参数推导余项时，可设 对于数值微分公式，可构造适当的插值多项式或应用Taylor展开式推导,p72,方法二、p87例2,利用变量替换,将a,b转化为-1,1区间,余项表达式,二、计算定积分和函数的导数的近似值,对于给定的被积函数与求导函数，应用指定的数值积分公式或数值微分公式计算，,t9,t12,t13,t18,t19，t25，t26等,明确积分公式与微分公式,三、确定复化求积公式和数值微分公式的步长或节点数，使计算结果满足所给精度要求,根据复化求积公式和数值微分公式的余项或截断误差表达式，对满足精度要求解一个相应的不等式，即可确定所需的步长或节点数,n=213,n=4,N169.2,n=170,n=4,常微分方程数值解 复习,常微分方程初值问题Euler法（显式Euler公式，隐式Euler公式，梯形公式，改进Euler公式，变形Euler公式）基本公式Runge-Kutta方法（四阶和二阶）线性多步法Adams预报校正系统收敛性和稳定性的定义局部截断误差的定义，计算及确定公式的阶数值方法的稳定性区域常微分方程组，高阶常微分方程初值问题的计算,一、对于给定数值方法求解常微分方程初值问题对于显式单步方法，直接代入相应计算公式计算对于隐式方法，若f(x,y)关于y是线性的，可从隐式公式中解出yn+1,使公式显式化，不需要迭代，否则，需要用迭代法计算对于多步方法，需要用同阶的单步法提供多步法所需要的值对于高阶或方程组的初值问题，需要进行转化,二、对于给定的常微分方程初值问题的某种数值方法，证明其阶次,三、确定某些方法中的参数主要用Taylor展开将方法的局部截断误差的各项在xn处进行Taylor展开并比较h同幂项的系数，得到待定参数满足的方程组，求解方程组即可,四、收敛性和稳定性,基本要求会利用相应方法计算一阶常微分方程的初值问题数值方法阶的确定(局部截断误差)含参公式的参数的确定（三）数值方法稳定性的判定,非线性方程求根,选择合适的的迭代法确定非线性方程的根二分法根据精度要求确定区间对分次数简单迭代法的构造及其加速,课后习题t10,课后习题t7,t8,根据给定方程求根的迭代格式，判断迭代法是否收敛，如果收敛确定其收敛阶次根据定义判断迭代是否收敛利用数列收敛判据确定迭代序列的极限是否存在,收敛阶的确定利用函数Taylor展开式，根据迭代格式收敛阶的定义判断根据迭代格式收敛阶定理例如证明Newton迭代是二阶收敛,确定给定迭代格式的系数，使其具有尽可能高的收敛阶次,要求,简单迭代法的构造，收敛性判断或证明（压缩映射原理）选用合适的迭代法求解方程收敛阶的确定（或证明）含待定参数的迭代格式的参数确定及应用Newton法、弦截法的应用,