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

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,如果近似值,准确到小数点后第n位

2、,并从第一个非零数字到这一位的所有数字均称为有效数字.,有效数字,的误差限是,则称,取前八位数得近似值,例如，,取前四位数得,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)的插值函数,求插值函数 P(x)的方法就称为插值法,15,基函数法,通过基函数来构造

5、插值多项式的方法就称为基函数插值法,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 的近似值,为了减小截断误差，通常选取插值点 x 邻接的插值节点,19,抛物线插值：取 x0=0.4,x1=0.5,x2=0.6,可得,ln 0

6、.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)的高阶导数存在时才能使用,几点说明,计算插值点 x 上的近似值时，应选取与 x 相近插值节点,23,插值误差举例,例：已知函数 y=lnx 的函数值如下,试估计线性插值和抛物线插值

7、计算 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,xk 的,二阶差商,k 阶差商,差商的一般定义,26,差商的性质,k 阶差商与 k 阶导数之间的关系：若 f(x)在 a,b 上 具有 k 阶导数，则至少存在一点(

8、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 插值多项式与 Lagrange 插值多项式,f(x)在 x0,x1,xn 上的 n 次插值多项式是唯一的！,Nn(x)Ln(x),余项也相同,将 x 看作节点,31,插值举例,例：已知函数 y=lnx 的函数值如下,解

9、：取节点 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,ex25.m,插值节点无需递增排列，但必须确保互不相同！,32,数值积分,微积分基本公式：,33,数值积分公式的一般形式,将定积分计算转化成被积函数的函数值的计算 无需求原函数 易于计算机实现,一般地，用 f(x)在 a,b 上的一些离散点 a x0 x1 xn b 上

10、的函数值的加权平均作为 f()的近似值，可得,34,定义：如果对于所有次数不超过 m 的多项式 f(x)，公式,精确成立，但对某个次数为 m+1 的多项式不精确成立，则称该求积公式具有 m 次代数精度,35,例：试确定系数 Ai，使得下面的求积公式具有尽可能高的代数精度，并求出此求积公式的代数精度。,易验证该公式对 f(x)x3 也精确成立，但对 f(x)x4 不精确成立，所以此求积公式具有 3 次代数精度。,36,设求积节点为：a x0 x1 xn b 若 f(xi)已知，则可做 n 次多项式插值：,其中,插值型求积公式,37,基于等分点的插值型求积公式,积分区间：a,b 求积节点：xi=a

11、+i h,求积公式：,Cotes 系数,Newton-Cotes 求积公式,(1),(2),38,n=1:,代数精度=1,梯形公式,n=2:,代数精度=3,抛物线公式Simpson公式,n=4:,科特斯(Cotes)公式,代数精度=5,39,梯形公式(n=1)的余项,Simpson公式(n=2)的余项,Cotes 公式(n=4)的余项,40,提高积分计算精度的常用两种方法,用 复合公式 用 非等距节点,将积分区间分割成多个小区间 在每个小区间上使用低次牛顿科特斯求积公式,复合求积公式,41,将 a,b 分成 n 等分 xi,xi+1，其中,(i=0,1,n),复合梯形公式,余项,42,复合 S

12、impson 公式,余项,性质：复合梯形公式和复合Simpson 公式都是收敛的，也都是稳定的。,43,例2 分别用复化梯形公式与复化Simpson公式计算积分,解(1)用复化梯形公式,截断误差为,的近似值，为使截断误差的绝对值不超过,至少应将0,1的多少等份.,故取 n=68,11,44,(2)若用复化Simpson公式，截断误差为,故取 n=6,12,45,例5 试确定求积公式,具有 2n+1次代数精确度，,Gauss型求积公式.,公式（7-42）称为带权函数,为Gauss点，,则称这组节点,定义7.2,如果一组节点,能使求积公式,（7-42）,的,代数精确度，,Gauss型求积公式.,它

13、是否是,18,46,解,19,由于当,分别取,有,即求积公式精确成立.,而当,因此,求积公式的代数精度为3.,它不是Gauss型求积公式.,p22,47,1计算f(x)在有解区间a,b端点处的值，f(a)，f(b)。,2计算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,先验误差估计：,理论基础：,定

14、理1：设函数 f(x)在区间a,b上连续，如果f(a)f(b)0，则方程 f(x)=0 在a,b内至少有一实根x*。,49,在0,0.5内的根,要求误差不超过,例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,0

15、0.250.250.31250.31250.3281250.328125,0123456,n,故,即为符合精度要求的解.,21,51,不动点迭代,基本思想,构造 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存在常数 0

16、L1，使得任意的 x,ya,b 有,则(x)在 a,b 上存在唯一的不动点 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*的某个-邻域

17、U(x*)=x*-,x*+，对任意 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)的不动点，若(p)(x)在 x*的某

18、邻域内连续，且,则迭代 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,x*,xk,xk+1,66,因为,得牛顿迭代公式为,例

19、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方法是一阶方法.,第九章 常微分方程数值解法,30,74,(9-9),这就是求解初值问题式（9-1）的梯形公式

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

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