数值分析第二章2

1、数值分析,1 误差来源与种类,上节知识要点回顾:,(1) 模型误差,(2) 参数误差,(3) 截断误差,(4) 舍入误差,2 绝对误差和相对误差,定义,设某量的准确值为x, 是x的近似值，,如果 称 为 的绝对误差限.,显然,常记为,定义,设某量的准确值为x, 是x的近似值，,如果 称 为 的相对误差限.,3 有效数字,定义:,设x为准确值， 是x的近似值，且,为0,1,9中一个数字. 如果,误差满足 即 误差不超过,某位的半个单位. 称该位到 的第一位非零数字为 的有效数字，即 有n位有效数字.,注,当 是x的 按四舍五入原则得到的近似,数，则 具有n位有效数字 .,4.有效数字和相对误差之

2、间的关系:,定理1,设x的近似数为,如果 具有n位有效数字,则 的相对误差限为,其中 ；反之，,如果 的相对误差满足,则 至少具有n位有效数字.,5. 条件数与病态问题,定义,对于前向误差和后向误差，其相对误差,之比的绝对值称为计算函数f(x)的条件数,近似计算公式为,当条件数较大时，可能会出现前向误差很大的情况，通常称这类问题为病态问题.,6. 数值计算中需要注意的问题,(1) 避免两个相近的数相减,(2) 防止大数“吃掉”小数,(3) 简化计算步骤，减少运算次数,(4) 避免误差的积累与传播,误差呈递增形式,称这类算法是不稳定的;,误差逐步递减，这样的算法称为稳定的算法,7. 二分法,令

3、取区间中点,问题：,为一非线性方程，,为有根区间，求,基本思想：,如此下去,不断缩小有根区间,直到达到给定,精度.,因此有,那么令,即,并且序列 的收敛性与初始区间无关.,所以二分法是大范围收敛的.,则,预先给定误差精度,算法步骤,(1) 取初始有根区间a,b,和精度要求 ；,(2) 若 则停止计算；,否则a=x；,(4) 转(2).,例 用二分法计算方程 在0, 0.5内具有5位有效数字的根，它的绝对误差限是多少？至少需要对分多少次才能达到精度？,解,由有效数字定义可知，绝对误差限是,要使,例 用二分法计算方程 在1, 2内具有4位有效数字的根，它的绝对误差限是多少？至少需要对分多少次才能达

4、到精度？,解,由有效数字定义可知，绝对误差限是,要使,二分法的优缺点,(1) 简单易用，大范围收敛,优点：,(2) 对 f (x) 要求不高，只要连续即可,缺点：,(1) 无法求复根及重根,(2) 收敛速度太慢,第二章 解非线性方程的数值方法,一、 二分法,二、 迭代法,三、 Newton法,将给定方程f(x)=0转化成等价方程,二、 迭代法,1 迭代法的基本思想:,若x*是f(x)的根, 即 ,则有,称x*为函数 的一个不动点.,设x0是一个近似解，可以构造序列,迭代法(2.2)称为简单迭代法或单点迭代法.,称函数 为迭代函数.,简单迭代法(2.2), 若迭代序列xk保持有界,全在 定义域内

5、;且有,称迭代法是收敛的. 此时,由的连续性可得,即 x* = (x*)， 即x*是的不动点，也就是f (x)的零点。,，建立迭代格式,解：改写方程为,求方程x3-2x-3=0在1,2内的根.,例,取初值x0=1.9 ,计算得：,由计算结果有|x10 x9|10-8, 因此可取 x* x10 1.89328920 。,方程也可改写成x=(x3-3)/2, 建立迭代格式 xk+1=(xk3-3)/2 , k=0,1,2,仍取初值x0=1.9, 则有,x1=1.9295, x2=2.0917, x3=3.0760, x4=13.0529,xk, 此迭代格式是发散的。,例 求x3-x-1=0在1.5

6、附近的根x*,解,x2,不动点迭代法的几何解释,2 收敛定理和误差估计,定理1 设 在a, b上有连续的一阶导数,且,(1) 有,(2),则有,(1) 函数 在a ,b上存在唯一的不动点x*,(3),(4),证明:,(1) 先证明存在性, 令,由条件(1)可知,由连续函数根的存在定理,必,h(x*)=0，即,再证明唯一性,设 也是一个解,即,那么,因为L1, 所以有,(2) 由条件(2)和Lagrange中值定理得,因为L1, 所以当 时, 有,(3)和(4) 利用(2)的方法,令 即分别得,定理1的几点说明,(i) 通常将条件(1)称为映内性；,(ii) 条件(2)也可以改为：存在常数L且0

7、L1,使得,结论仍然成立, 这个条件通常称为压缩性；,(iii) 结论(3)说明 的误差大概是常数,乘上Lk, 但是一般L未知;,(iv) 结论(4)说明 与 有关,因此得到迭代法的终止条件,3 一般迭代法的算法,算法：,(1) 取初始点x0,最大迭代次数N和精度要求,并置k=0；,(2) 计算,(3) 若 则停止计算；,(4) 若k=N, 则停止计算；否则k=k+1, 转(2).,求方程xex-1=0在0.5附近的根,精度要求=10-3。,解 可以验证方程xex-1=0在区间0.5,0.61内仅有一个根。,例,改写方程为x=e-x ,建立迭代格式,由于(x)=e-x ,在0.5,0.61上有

8、|(x)|e-0.50.6 1，且(x)0.5,0.61，所以迭代法收敛。,取x0=0.5,得,所以,取近似根x*x10=0.56691满足精度要求。,如果精度要求为=10-5, 则由,可知,需要迭代20次。,实际上,方程在0.55,0.6上有唯一根，而此时|(x)|e-0.550.581. 若取L=0.58，则有,注意：这里迭代次数20是充分的但不是必要的。,可知, 只需迭代19次。,4 局部收敛定理,迭代序列xk在区间a,b上的收敛性通常称为全局收敛性. 实际应用只在不动点x*的邻近考察收敛性，称为局部收敛性.,定义 设 有不动点x*,如果存在x*的某个邻域,对任意的 迭代(2.2)产生的

9、,序列 且收敛到x*,则称(2.2)局部收敛.,证明 由连续函数的性质,存在x*的某个邻域,对任意的 有,而,根据定理1可以断定迭代过程(2.2)对任意初值 均收敛.,定理2 若x*为迭代函数 的不动点, 在x*,的某个邻域内有连续导数,且 则,迭代法(2.2)局部收敛.,例 只用四则运算不用开方求方程x2-3=0的根,解,(1)和(2)发散， (3)和(4)收敛.,使迭代公式(2.2)局部收敛到,解,因为,所以 由定理2可知只需,即,所以当 时,迭代公式收敛.,5 迭代收敛的阶,则称该迭代为p 阶收敛. (C为常数),(1) 当p =1时称为线性收敛，此时0C 1；,(2) 当p =2 时称

10、为二次收敛，或平方收敛；,(3) 当p 1和p =1且C=0时称为超线性收敛.,定义 设迭代 收敛到 的不动点x*. 记ek = xk x*，若,例: (1) 二分法线性收敛;,(2)不动点迭代中，若 则线性收敛,解: (2) 不动点迭代中第k+1步的误差为：,则,定理3 设迭代 若 在x*的某,邻域内连续并满足,即该迭代法是p阶收敛的。,证明：,根据泰勒展开有,6 迭代加速,若 则迭代公式(2.2)只是线性收敛。,迭代加速方法可对线性收敛的简单迭代法起到加速作用。,取初始点x0,令 那么,由此得加速迭代公式,此加速法的优点：,迭代速度快；,此加速法的缺点：,迭代公式中有待定的L,使用不方便。

11、,令 得到,Steffensen迭代加速法,由此得Steffensen加速法,Steffensen加速法是平方收敛的.,注：果第k步发生zk-2yk+xk=0, 就终止计算, 取x*xk 。,分别用简单迭代法和Steffensen加速算法,例,求方程 在 附近的根。,解：,简单迭代法迭代公式,Steffensen迭代公式：,取x0= /2, 计算结果如下:,Newton迭代法是求方程根的重要方法之一,其最大优点是在方程的单根附近具有平方收敛,而且Newton迭代法还可用来求方程的重根、复根及非线性方程组。,三、 Newton法,1 Newton法基本思想,当 f (x) 0时, ,于是,即为N

12、ewton迭代公式.,Newton法的几何意义,Newton法的本质就是不断用切线来近似曲线，因此Newton法也成为切线法.,2 Newton法的算法,(1) 取初始点x0,最大迭代次数N和精度要求,置k=0;,(2) 计算,(3) 若 则停止计算;,(4) 若k=N则停止计算;否则置k=k+1,转(2).,Newton 法可以看作下面的不动点迭代：,其中,(x*) = 0 (若f(x*)=0,f(x*)0，即x*是单根）,Newton 法至少二阶局部收敛,3 Newton法收敛性,定理4 设f(x)在其零点x*的某个邻域内二阶连续可导且f(x) 0，则存在x*的某个 邻域N(x*) =x*

13、- , x* + , 使得对 x0 N(x*)，Newton法产生的序列以不低于二阶的收敛速度收敛到 x* .,证明 (略),Newton 法也可以看作一类特殊的加速迭代,（ (x) = x -f (x)）,取x0=0.5,计算结果如下:,例4 用Newton迭代法求方程xex-1=0在0.5附近的根,精度要求=10-5.,解 Newton迭代格式为,从结果可见 ,Newton迭代法迭代3次已获得精确到小数点后五位的近似解,迭代4次已获得精确到小数点后八位的近似解.与一般迭代法比较可见Newton迭代法收敛的确实快.,例 设计一个二阶收敛算法计算 (a 0).,解：转化为求 x2-a = 0

14、的正根,Newton 迭代：,二阶收敛,取x0=1.7，计算得：,所以取x3=1.732050808,例 用Newton迭代法求,解 对方程x2-3=0应用Newton迭代法：,的近似值,要求=10-7。,设x*是f(x)的m(m2)重根, Newton法是否收敛？,Taylor 展式,4 重根情况,所以Newton 迭代：,线性收敛, 且重数m越高, 收敛越慢.,提高收敛速度,但m通常无法预先知道！,法一：取,注: 推导过程与前面类似.,法二：将求f(x)的重根转化为求另一个函数 的单根.,构造针对(x) 的具有二阶收敛的Newton迭代：,令 ，则x*是(x)的单重根.,例 取初始点x0=

15、1.5, 分别用Newton法和求重根的两种方法计算 f(x)=(x+1)(x-1)2=0,解,(1) Newton法迭代公式,(2) 方法一：取 , m=2,迭代公式为,方法二:,迭代公式为,取,两种改进方法的结果比较,用Newton迭代公式求解, 只能是线性收敛, 而改进的两种方法都具有二阶收敛, 所以计算速度要快得多. 但是很多问题实际不知道根的重数，所以方法一有时并不实用.,Newton 法的收敛依赖于初始点的选取.,5 Newton下山法,如果x0偏离所求根x*较远,则Newton法可能发散,为防止迭代发散,我们对迭代过程再附加一项要求,即具有单调性:,满足这项要求的算法称为下山法,k为数列 中满足 的最大数.