数值分析期末复习要点总结ppt课件.ppt

《数值分析期末复习要点总结ppt课件.ppt》由会员分享，可在线阅读，更多相关《数值分析期末复习要点总结ppt课件.ppt（87页珍藏版）》请在三一办公上搜索。

1、1,期末复习要点总结,数值分析,2,2,第一章 误差,第一章 误差,一. 误差的来源:,1.模型误差,2.观测误差,3.截断误差,4.舍入误差,二. 绝对误差、相对误差和有效数字,3,3,为准确值x的一个近似值，称,若,的绝对误差限，简称误差限.,通常称,为近似值,定义2 设,(1-3),记为,即,准确值之比为近似值,为近似值,的绝对误差，简称误差.,(1-1),称绝对误差与,为准确值 x 的近似值，,的相对误差，,(1-2),定义1 设,4,由于在计算过程中准确值 x 总是未知的，,故一般取相对误差为,则称 为 的相对误差限.,使得,(1-4),如果存在正数,5,如果近似值,准确到小数点后第

2、n位,并从第一个非零数字到这一位的所有数字均称为有效数字.,有效数字,的误差限是,则称,取前八位数得近似值,例如，,取前四位数得,1.414有4位有效数字.,1.4142136有8位有效数字.,6,6,(1-5),一般地，如果近似值,其中m为整数，,为0到9之间的整数.,如果,(1-6),则称近似值,有n位有效数字.,例如,有4位有效数字.,故,的规格化形式为,7,7,若x的近似值,至少具有n位有效数字.,有n位有效数字，,则,误差限.,反之，,的相对误差,定理1.1,为其相对,满足,若,则,8,8,(1-12),(1-11),(1-13),9,例,设近似数,是某真值 x 经四舍五入,所得,试

3、求其绝对误差限和相对误差限.,解,由于a经四舍五入得到,故,9,10,10,例1:,2, 求,1.经四舍五入得,试问它们有几位有效数字？,的绝对误差限.,解,故,分别具有5位有效数字,11,11,例2:,要使,的近似值的相对误差限小于0.1%,应取,取几位有效数字,解:,的首位数是2,设近似数,有n位有效数字,只须取n使,即,取n=4,即取4位有效数字,近似值的相对误差限小于0.1%.,12,数值计算中的一些原则,1.避免两个相近的数相减,2.避免大数“吃”小数的现象,3.避免除数的绝对值远小于被除数的绝对值,4.要简化计算，减少运算次数，提高效率,5. 要有数值稳定性,即能控制舍入误差的传播

4、,例如 为提高数值计算精度, 当正数x充分大时,应将,改写为,12,13,例 如何计算下列函数值才比较精确,(1),对,解 (1) 要使计算准确, 应避免两个相近的数相减,(2),对,(2) 要使计算准确, 应避免两个相近的数相减,故变换所给公式,故变换所给公式,12,14,第二章插值,已知函数 y = f(x) 在 a, b 上有定义，且已经测得在点 a x0 x1 xn b 处的函数值为 y0 = f(x0)， ，yn = f(xn),如果存在一个简单易算的函数 P(x)，使得 P(xi) = f(xi)，i = 1, 2, . , n则称 P(x) 为 f(x) 的插值函数,求插值函数

5、P(x) 的方法就称为插值法,15,基函数法,通过基函数来构造插值多项式的方法就称为基函数插值法,Zn(x) = 次数不超过 n 的多项式的全体,记,16,Lagrange插值,Lagrange插值基函数,设 lk(x) 是 n 次多项式，在插值节点 x0 , x1 , , xn 上满足,则称 lk(x) 为节点 x0 , x1 , , xn 上的拉格朗日插值基函数,17,线性与抛物线插值,两种特殊情形,n=1,线性插值多项式（一次插值多项式）,18,例：已知函数 y = lnx 的函数值如下,解：,试分别用线性插值和抛物线插值计算 ln 0.54 的近似值,为了减小截断误差，通常选取插值点

6、x 邻接的插值节点,19,抛物线插值：取 x0=0.4, x1=0.5, x2=0.6, 可得,ln 0.54 L2(0.54) =-0.6153,Lagrange插值多项式简单方便，只要取定节点就可写出基函数，进而得到插值多项式，易于计算机实现。,20,Lagrange插值,lk(x) 的表达式,由构造法可得,21,误差估计,如何估计误差,定理,设 f(x) Cna, b ( n 阶连续可微 )，且 f (n+1)(x)在 (a, b) 内存在，则对 xa,b，有,其中 x(a, b) 且与 x 有关,22,插值余项,余项公式只有当 f(x) 的高阶导数存在时才能使用,几点说明,计算插值点

7、x 上的近似值时，应选取与 x 相近插值节点,23,插值误差举例,例：已知函数 y = lnx 的函数值如下,试估计线性插值和抛物线插值计算 ln 0.54 的误差,24,Newton 插值,为什么 Newton 插值,Lagrange 插值简单易用，但若要增加一个节点时，全部基函数 lk(x) 都需重新计算，不太方便。,设计一个可以逐次生成插值多项式的算法，即 n 次插值多项式可以通过 n-1 次插值多项式生成 Newton 插值法,解决办法,25,什么是差商,设函数 f(x)，节点 x0 , , xn,f(x) 关于点 xi , xj 的,一阶差商,f(x) 关于点 xi , xj , x

8、k 的,二阶差商,k 阶差商,差商的一般定义,26,差商的性质,k 阶差商与 k 阶导数之间的关系：若 f (x) 在 a,b 上 具有 k 阶导数，则至少存在一点 (a, b)，使得,27,如何巧妙地计算差商,差商表,28,差商举例,例：已知 y = (x) 的函数值表，试计算其各阶差商,解：差商表如下,29,Newton 插值公式,f (x) = Nn(x) + Rn(x),Nn(x) 是 n 次多项式,Nn(xi) = f (xi)，i = 0, 1, 2, , n,重要性质,Nn(x) 是 f (x) 的 n 次插值多项式,其中,30,Newton / Lagrange,Newton

9、插值多项式与 Lagrange 插值多项式,f (x) 在 x0 , x1 , , xn 上的 n 次插值多项式是唯一的！,Nn(x) Ln(x),余项也相同,将 x 看作节点,31,插值举例,例：已知函数 y = lnx 的函数值如下,解：取节点 0.5, 0.6, 0.4 作差商表,试分别用牛顿线性插值和抛物线插值计算 ln 0.54 的近似值,N1(x) = -0.6931 + 1.8230(x-0.5),N1(0.54) = -0.6202,N2(x) = -0.6931 + 1.8230(x-0.5) - 2.0450(x-0.5)(x-0.6),N2(0.54) = -0.6153

10、,ex25.m,插值节点无需递增排列，但必须确保互不相同！,32,数值积分,微积分基本公式：,33,数值积分公式的一般形式,将定积分计算转化成被积函数的函数值的计算 无需求原函数 易于计算机实现,一般地，用 f(x) 在 a, b 上的一些离散点 a x0 x1 xn b 上的函数值的加权平均作为 f () 的近似值，可得,34,定义：如果对于所有次数不超过 m 的多项式 f (x) ，公式,精确成立，但对某个次数为 m +1 的多项式不精确成立，则称该求积公式具有 m 次代数精度,35,例：试确定系数 Ai ，使得下面的求积公式具有尽可能高的代数精度，并求出此求积公式的代数精度。,易验证该公

11、式对 f (x)x3 也精确成立，但对 f (x)x4 不精确成立，所以此求积公式具有 3 次代数精度。,36,设求积节点为：a x0 x1 xn b 若 f (xi) 已知，则可做 n 次多项式插值：,其中,插值型求积公式,37,基于等分点的插值型求积公式,积分区间：a, b 求积节点： xi = a + i h,求积公式：,Cotes 系数,Newton-Cotes 求积公式,(1),(2),38,n = 1:,代数精度 = 1,梯形公式,n = 2:,代数精度 = 3,抛物线公式Simpson公式,n = 4:,科特斯 (Cotes) 公式,代数精度 = 5,39,梯形公式 (n=1)

12、的余项,Simpson公式 (n=2) 的余项,Cotes 公式 (n=4) 的余项,40,提高积分计算精度的常用两种方法,用 复合公式 用 非等距节点,将积分区间分割成多个小区间 在每个小区间上使用低次牛顿科特斯求积公式,复合求积公式,41,将 a, b 分成 n 等分 xi , xi+1 ，其中,(i = 0, 1, , n),复合梯形公式,余项,42,复合 Simpson 公式,余项,性质：复合梯形公式和复合Simpson 公式都是收敛的，也都是稳定的。,43,例2 分别用复化梯形公式与复化Simpson公式计算积分,解 (1)用复化梯形公式, 截断误差为,的近似值，为使截断误差的绝对值

13、不超过,至少应将0,1的多少等份.,故取 n=68,11,44,(2)若用复化Simpson公式，截断误差为,故取 n=6,12,45,例5 试确定求积公式,具有 2n+1次代数精确度，,Gauss型求积公式.,公式（7-42）称为带权函数,为Gauss点，,则称这组节点,定义7.2,如果一组节点,能使求积公式,（7-42）,的,代数精确度，,Gauss型求积公式.,它是否是,18,46,解,19,由于当,分别取,有,即求积公式精确成立.,而当,因此,求积公式的代数精度为3.,它不是Gauss型求积公式.,p22,47,1计算f (x)在有解区间a, b端点处的值，f (a)，f (b)。,2

14、计算f (x)在区间中点处的值f (x1)。,3判断若f (x1) = 0，则x1即是根，否则检验：,（1）若f (x1)与f (a)异号，则知解位于区间a, x1， b1=x1, a1=a;,（2）若f (x1)与f (a)同号，则知解位于区间x1, b， a1=x1, b1=b。,反复执行步骤2、3，便可得到一系列有根区间：(a, b), (a1, b1), , (ak, bk), ,48,先验误差估计：,理论基础：,定理1：设函数 f (x) 在区间a, b上连续，如果f (a) f (b) 0， 则方程 f (x) = 0 在a, b内至少有一实根x*。,49,在0, 0.5内的根,要

15、求误差不超过,例6 试用对分区间法求方程,解 令,则,故在0,0.5内,有唯一实根.,为达到要求,即,取,计算结果见下表。,20,50,-0.2490230.1324158-0.05951970.0360497-0.01182140.012091010.00012923,0.250.3750.31250.343750.3281250.33593750.33203125,0.50.50.3750.3750.343750.343750.3359375,00.250.250.31250.31250.3281250.328125,0123456,n,故,即为符合精度要求的解.,21,51,不动点迭代,

16、基本思想,构造 f (x) = 0 的一个等价方程：,52,不动点迭代,具体过程,任取一个迭代初始值 x0 ，计算,得到一个迭代序列： x0，x1，x2，. . . ，xn，. . .,k = 0, 1, 2, . .,几何含义：求曲线 y = (x) 与直线 y = x 的交点,53,设 (x) 连续，若 收敛，即 ，则,收敛性分析,性质：若 ，则不动点迭代收敛，且 x* 是 f(x)=0 的解；否则迭代法发散。,54,定理：设 (x) Ca,b 且满足,证明：板书,对任意的 xa,b 有 (x)a,b存在常数 0L1，使得任意的 x, ya,b 有,则(x) 在 a,b 上存在唯一的不动点

17、 x*,解的存在唯一性,55,定理：设 (x) Ca,b 且满足,对任意的 xa,b 有 (x)a,b存在常数 0L1，使得任意的 x, ya,b 有,则对任意初始值 x0a,b，不动点迭代 xk+1=(xk) 收敛，且,不动点迭代的收敛性,56,不动点迭代的收敛性,若 (x)C1a,b 且对任意 xa,b 有 |(x)|L1则上述定理中的结论成立。,收敛性结论表明：收敛性与初始值的选取无关,57,例：求 f(x) = x3 x 1=0 在区间 1, 2 中的根,ex71.m,58,定义：设 x* 是 (x) 的不动点，若存在 x* 的某个 -邻域 U(x*) =x*- , x* + ，对任意

18、 x0U(x*)，不动点迭代 xk+1 = (xk) 产生的点列都收敛到 x*，则称该迭代局部收敛。,定理：设 x* 是 (x) 的不动点，若 (x) 在 x* 的某个邻域内连续，且 |(x*)| 1则不动点迭代 xk+1 = (xk) 局部收敛,局部收敛,59,定义：设迭代 xk+1 = (xk) 收敛到 (x) 的不动点 x*，记 ek = xk x*，若,其中常数 C0，则称该迭代为 p 阶收敛。,当 r =1 时称为线性收敛，此时 C 1 时称为超线性收敛,二分法是线性收敛的 若 (x*) 0，则不动点迭代 xk+1 = (xk) 线性收敛,60,定理：设 x* 是 (x) 的不动点，

19、若 (p)(x) 在 x* 的某邻域内连续，且,则迭代 xk+1 = (xk) 是 p 阶收敛的。,61,例：求 f(x) = x2 - 3=0 的正根,(1),ex72.m,(2),(3),二次收敛,局部收敛,62,计算得,例9 用简单迭代法求方程,精确到3位有效数字.,解,在0,1内的根,在0,1内连续,在0,1内有唯一,实根.,的等价方程为,又当,故,对,均收敛.取,故,26,63,故，,27,64,Newton 法,基本思想,将非线性方程线性化,设 xk 是 f (x)=0 的近似根，将 f(x) 在 xk 处 Taylor 展开,条件： f(x) 0,65,Newton 法,x,y,

20、x*,xk,xk+1,66,因为,得牛顿迭代公式为,例7,用Newton法求方程,在(1,2)的根，取初值,解,根据 Newton迭代,故在1,2内方程有唯一实根,取初值,得,22,67,代入初值得,故取,23,68,k = 0, 1, 2, . . .,迭代函数,69,例：用 Newton 法求 f(x) = x2 C=0 的正根, 并验证这一方法的二阶收敛性,解：,对任意 x00，总有 |q|1，即牛顿法收敛,70,二阶收敛,关于二次收敛性，事实上,71,72,73,(9-2),公式(9-2)称为显式欧拉公式.,Euler法的局部截断误差也可表示为,Euler方法是一阶方法.,第九章 常微

21、分方程数值解法,30,74,(9-9),这就是求解初值问题式（9-1）的梯形公式.,梯形公式（9-9）的局部截断误差为,故梯形公式为二阶方法.,31,75,一般地,RK方法设近似公式为,(9-13),确定它们的原则是使近似,公式在 处的Taylor展开式与 在 处的,Taylor展开式的前面的项尽可能多地重合,这样就使近,似公式有尽可能高的精度。,32,76,这就是改进Euler公式,它是一种二阶龙格-库塔公式。,33,77,(9-11),式（9-11）称为由Euler公式和梯形公式得到的预测,校正系统，也叫改进Euler法，它是显式单步法。,预测,校正,改进Euler法的局部截断误差为,故它

22、是二阶方法。,34,78,例1用欧拉法求初值问题,当h = 0.02时在区间0, 0.10上的数值解。,具体计算结果如下表：,79,例 用改进的Euler法求初值问题,的数值解, 取 .,解 改进的Euler公式为,所以,35,80,将,代入上式得,将,代入上式得,将,代入上式得,36,81,例12 用二阶方程初值问题,化为一阶方程组初值问题,并写出欧拉方法求解的,解 令,计算公式.,可得,计算公式为,41,82,一般分析时为简单起见，只考虑试验方程,常数，可以是复数,83,例4.3 对初值问题,证明用梯形公式求得的近似解为 ,并证明当步长h0时,yn 收敛于精确解 证明: 解初值问题的梯形公式为:,整理成显式,反复迭代,得到:,84,整理成显式,反复迭代,得到:,例 对初值问题,证明用梯形公式求得的近似解为 ,并证明当步长h0时,yn 收敛于精确解,85,由于 ，有:,证毕,86,例：考察隐式欧拉法,可见绝对稳定区域为：,注：一般来说，隐式欧拉法的绝对稳定性比同阶的显式法的好。,87,是二阶方法。,