数值分析复习

1、数值分析总复习,第三章 线性方程组的直接法,第四章 线性方程组的迭代法,第一章 绪论,第二章 非线性方程求根,第五章 函数插值,第六章 函数逼近,第七章 数值积分数值微分,第八章 常微分方程数值解法,第九章 特征值特征向量,内容提要,第一章 要点回顾,1 误差的概念,绝对误差、相对误差、有效数字定义及相互关系：,2 误差的传播（数值运算的误差估计）,一元函数、多元函数误差的近似泰勒估计：,3 误差定性分析,条件数、算法的数值稳定性。,4 算法设计注意事项,知识结构图,第一章 重点掌握,绝对误差 设x*是准确值x的一个近似，称,为 x* 近似x的绝对误差，简称为误差。,相对误差 设x*是准确值x

2、 的一个近似，称,为x* 近似x的相对误差。,因,第一章 重点掌握,有效数字 设x的近似值x* 有如下标准形式,如果有,则称x* 为x的具有n位有效数字的近似数，,相对误差与有效数字间的关系,定理 设x的近似数x*具有标准形式：, 若x*具有n位有效数字，则相对误差,用Taylor公式分析误差传播规律,用算术运算的误差估计,算术运算的绝对误差传播,算术运算的相对误差传播,算法注意事项,避免相近数相减,第一章 典型例题,例1 已知数 x=2.718281828.,取近似值 x*=2.7182,那麽x具有几位有效数字,解；,故有四位有效数,点评；考查的有效数字的概念。,解：,点评；此题考查相对误差

3、的传播。,例3sin1有2位有效数字的近似值0.84的相对误差限是 .,解法1：根据有效数字与相对误差限的关系,解法2：相对误差限的概念,点评；此题考查相对误差与有效数字关系 第二种按定义得到的结果更好,解：根据误差传播公式,则有,点评；考查一元函数相对误差传播。,第二章 要点回顾,1 二分法,二分法计算过程、二分法先验误差：,2 不动点迭代法（普通迭代法）,不动点格式构造：,3 牛顿迭代法,牛顿迭代公式,不动点收敛性：（局部收敛性、全局收敛性）,不动点加速：Aiteken加速,牛顿迭代的局部收敛性和全局收敛性；,牛顿迭代公式的变形（非重点）,知识结构图,第二章 重点掌握,二分法执行步骤,1计

4、算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), ,先验误差估计：,理论基础：,定理1：设函数 f (x) 在区间a, b上连续，如果f (a) f (b) 0， 则方程 f (x) =

5、0 在a, b内至少有一实根x*。,简单迭代法,构造迭代格式,x = g (x),（1）迭代函数 在 的邻域可导；,定理：如果 (x)满足下列条件 （1）当xa, b时，(x)a, b （2）当任意xa, b，存在0 L 1，使 则方程x = (x)在a, b上有唯一的根x*,且对任意初值 x0a, b时，迭代序列xk+1= (xk) (k = 0, 1, )收敛于x*。,迭代过程的收敛速度,设由某方法确定的序列xk收敛于方程的根x*， 如果存在正实数p，使得,（C为非零常数）,定义：,定理：迭代法xk+1=(xk)的迭代函数在不动点的邻域里的p (p1)阶导函数连续，则当初值x0充分靠近时，

6、迭代法为p 阶收敛的充要条件是,牛顿法,x*,x0,x1,x2,牛顿法的收敛性,定理： 设f (x)在a, b上满足下列条件： （1）f (a) f (b) 0 则由（2.3）确定的牛顿迭代序列xk收敛于f (x) 在a, b上的唯一根x*。,Steffensen迭代格式,Newton法的变形,重根时的牛顿迭代法,Newton下降法,根据牛顿迭代格式,则相应的得到,例2： 求方程,在区间1, 1.5内的实根。要求准确到小数点后第2位。,解：预先估计一下二分的次数：按误差估计式,解得k = 6，即只要二分6次，即达所求精度。计算结果如下表：,解：因为f (0) = 10 f (1) = -7 0

7、，知方程在0, 1中必有一实根， 现将原方程改为同解方程,由于x 0时，f (x) 0，且f (x) 0，根据定理知：,解： 由,可得,由于,第三章 要点回顾,1 Guass消去法,Guass消去法、,2 矩阵三角分解法,LU分解法,平方根法（对称正定矩阵），追赶法（三对角方程）,向量范数和矩阵范数（三个）；,向量范数的连续性和等价性，向量收敛性定义,Guass选主元消去法（列选主元，全选主元）,2 方程组的性态和误差估计,矩阵条件数，病态方程组,知识结构图,第一步：,Gauss消去法,按上述做法，做完n-1步，原方程可化为同解的 上三角方程组。,Gauss列选主元消去法,直接三角分解法,设A

8、=LU 即,第一步：,第二步：,这组公式可用下图记忆:,追赶法,第三章 典型例题,例2：用直接三角分解法解,解：（1）对于r = 1，利用计算公式,（2）对于r = 2，,（4）回代求解：,，,例5 对矩阵A进行LDL分解和LL分解，并求解方程组,第四章 要点回顾,1 简单迭代法,简单迭代法构造,2 G-S迭代法,G-S迭代法的构造思想,G-S迭代法的收敛性分析,Jacobi方法,基于Jacobi方法的G-S迭代法,简单迭代法的收敛性分析,2 常用迭代法,逐次超松弛迭代法,简单迭代法的构造,简单迭代法的收敛性,1.收敛的充要条件,几种常见的迭代法,一.Jacobi迭代法,迭代格式,2.收敛条件

9、,b.充分条件：,或,即,a.充要条件：,二.与Jacobi迭代法相应的Gauss-Seidel法,1.迭代格式.,2.收敛条件.,a.充要条件：,b.充分条件：,SOR方法,第四章 典型例题,例2：用雅克比迭代法和高斯赛得尔迭代法 解线性方程组,解：所给线性方程组的系数矩阵按行严格对角占优， 故雅克比迭代法和高斯赛得尔迭代法都收敛。,雅克比迭代法的迭代公式为：,取X(0) = (0, 0, 0)，由上述公式得逐次近似值如下：,X (i),4,3,2,1,0,k,高斯赛得尔迭代法：,1.当参数a满足什么条件时，雅可比方法对任意的,初始向量都收敛。,2.写出与雅可比方法对应的高斯赛德尔迭代公式。

10、,解：当a不等于零时，雅可比方法的迭代矩阵为,可以解出B的特征值,可知B的谱半径,与雅可比方法对应的方法为,证明该方程组对应雅可比方法发散，而G-S方法收敛。,解：G-S的迭代矩阵为,第五章 要点回顾,1 插值问题与插值多项式的唯一性,2 拉格朗日型插值方法,Lagrange插值法,牛顿插值法 （差商、差分的定义）,完全导数形式的hermite插值（构造方法、余项）,不完全导数形式的hermite插值 （待定系数，重节点差商）,3 Hermite型插值方法,插值误差分析（拉格朗日余项，差商型余项）,4 分段插值和三次样条插值,知识结构图,拉格朗日插值基函数,一、插值基函数,定义：若n次多项式l

11、k(x)(k=0, 1 , n)在n+1个插值节点x0 x1 xn上满足插值条件：,则称这n1个n次多项式l0(x), l1(x) , ln(x)为插值节点x0 ,x1 , , xn上的n次Lagrange插值基函数。,拉格朗日插值公式,将Lagrange插值基函数与函数值线性组合得 可以验证 满足插值条件，即,上式是不超过n次的多项式，称之为Lagrange插值多项式。,的线性组合。故可将满足插值条件（4.1）的n次多项式写成如下形式,牛顿插值的定义,由线性代数可知，任何一个不高于n次的多项式， 都可表示成函数,其中 为待定系数。这种形式的插值多项式称为牛顿Newton插值多项式,牛顿插值,

12、差商的性质,性质1：,设 的n阶导数存在，则有,性质2：,k=1,2,n,性质3：,k阶差商 可以表示为函数值 的线性组合，即,差商具有对称性，与插值节点的排列次序无关。,Hermite 插值多项式,要求函数值重合，而且要求若干阶导数也重合。,即：要求插值函数 P (x) 满足,在实际问题中，对所构造的插值多项式，不仅,把此类插值多项式称为埃米尔特（Hermite）,插值多项式，记为H (x)。,情形1；一阶导数已知,已知函数表,求一个插值多项式H (x)，使其满足如下条件：,插值条件的个数2n+2, H (x) 的次数：不超过2n+1次,i = 0, 1, 2, n,i = 0, 1, 2,

13、 n,Hermite插值多项式构造,对于问题1，取n=2，通过一个例子来讨论建 立Hermite插值的方法,(1),现在需要考虑的问题是这些基函数的构造问题。,则满足插值条件的多项式可以写成如下形式,(2),(3),假设,可验证条件 自动满足,现利用另外的两个条件,求解可得,于是有,同理可得,(4),(5),将函数(2)到(5)代入式(1)，得到插值多项式,上式称为三次Hermite插值多项式，其余项为,情形2；导数值不完全,已知函数表,求一个插值多项式H (x)，使其满足如下条件：,插值条件的个数m+n+2, H (x) 的次数：不超过m+n+1次,i = 0, 1, 2, n,i = 0,

14、 1, 2, m,待定系数法,通过一个简单的例子给出这种问题的解法,例 试确定一个不超过二次的多项式,使其满足如下插值条件,先利用前两个插值条件，构造一个1次 的插值多项式,定义,这里c是一个常数，无论它取何值，插值条件,自然满足，再利用导数条件确定常数c,从上式解出c，回代到 得到,第五章 典型例题,点评；此题考查利用反插值来求根 前提是函数值分布单调,提示：利用插值的拉格朗日余项说明当被插值函数为x的k次方时，误差为零。,往年真题,第六章 要点回顾,1 泛函基础知识,2 连续函数的最佳平方逼近,赋范线形空间、内积空间、正交多项式系,矛盾方程组的解法,一般基函数的曲线最小二乘拟合 基于正交基

15、函数的拟合方法,3 离散函数的最佳平方逼近,基于一般基函数构造方法,基于正交基函数构造方法,赋范线性空间,定义： 设V是实数域R上的线性空间。,最佳平方逼近,正规方程组,内积空间,正交函数系,Legendre 多项系,定义,Legendre多项式系的前六项分别为,Chebyshev 多项式系,定义,第六章 典型例题,(单位：亿）,t表示年份试用下表提供的数据， 确定待定参数a和b, 并预测2000年的世界人口,解 所求拟合函数是一个指数函数，对它两边取 自然对数，得,建立如下新的数据表,据此模型预测2000年的世界人口为63.2377亿,用最小二乘法得法方程组,实际统计人口为60.5726亿,

16、相应的正规方程组为,.,解 构造0,1上首项系数为1的正交多项式,的前三项. 设,第七章 要点回顾,1 数值积分相关概念,2 基于等距节点的Newton-Cotes公式,代数精确度、插值型求积公式、求积稳定性、积分误差,复化梯形，复化Simpson公式,3 复化求积公式,梯形公式及误差分析,Simpson公式及误差分析,4 了解Romberg积分、Guass积分,5 数值微分相关概念及构造,知识结构图,求积公式,其中Rf称为求积公式的余项。,称为求积节点 。,称为求积系数。,代数精（确）度,对于一切不高于m次的代数多项式准确成立。,而对于某个m+1次多项式并不准确成立。,则称上述求积公式具有m

17、次代数精度。,Newtoncotes公式,辛浦生（Simpson）公式或抛物线公式,梯形公式,Simpson公式误差估计,复化Simpson公式误差估计,梯形公式误差估计,复化梯形公式误差估计,Romberg算法,高斯公式和高斯点,第七章 典型例题,1插值型求积公式的求积系数之和为1,解 因为两点Gauss型求积公式的代数精确度为3,解得,从所求方程组看出，该公式至少具有2次代数精确度。,具有3次代数精确度。,的代数精度最高此时代数精度为 ,10 参数 为多少时，求积公式,解：求积公式中含一个待定参数，,将 代入已求得的求积公式，显然,具有三次代数精度。,验证,11 取m=4,即n=8，用复化

18、抛物线求积公式计算积分,第八章 要点回顾,1 几种主要的单步法,2 单步法构造及相关概念,前后欧拉法、梯形公式、改进欧拉法,泰勒公式的方法、数值积分方法,3 Runge-Kutta法构造思想及阶数判断,泰勒公式的方法、数值积分方法,局部误差和整体误差收敛阶、稳定性、预估校正,4 线形多步法构造思想及阶数判断,泰勒公式的方法、数值积分方法,知识结构图,显示欧拉（Euler）法,隐式Euler方法,Enlor法与梯形法相结合:,对单步法，在 假设下,称,Euler预估校正方法,整体截断误差。,若一个方法的局部截断误差为 ，则称,该方法为p阶方法。,一般的显式Runge-Kutta方法,线性多步方法一般形式,基予数值积分的构造方法,基于Taylor 展开的构造方法,例1用欧拉法求初值问题,当h = 0.02时在区间0, 0.10上的数值解。,具体计算结果如下表：,例2取h=0.1, 用改进欧拉