数值分析复习

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

2、为,如果存在着的正数,使得有绝对误差,相对误差 设x*是准确值x 的一个近似，称,为x* 近似x的相对误差。,因,称数值 的上界为相对误差限，记为,第一章 重点掌握,有效数字 设x的近似值x* 有如下标准形式,如果有,则称x* 为x的具有n位有效数字的近似数，,相对误差与有效数字间的关系,定理 设x的近似数x*具有标准形式：, 若x*具有n位有效数字，则相对误差,用Taylor公式分析误差传播规律,当 ， ， 很好地近似了相应的真值时，利用多元函数的一阶Taylor公式可求得y* 的绝对误差和相对误差分别为,设可微函数中 的自变x1、x2、xn是相互独立的。函数值y的近似值为,用算术运算的误差

3、估计,算术运算的绝对误差传播,算术运算的相对误差传播,算法注意事项,避免相近数相减,第一章 典型例题,例1 已知数 x=2.718281828.,取近似值 x*=2.7182,那麽x具有几位有效数字,解；,故有四位有效数,点评；考查的有效数字的概念。,解：,点评；此题考查相对误差的传播。,例3sin1有2位有效数字的近似值0.84的相对误差限是 .,解法1：根据有效数字与相对误差限的关系,解法2：相对误差限的概念,点评；此题考查相对误差与有效数字关系 第二种按定义得到的结果更好,解：根据误差传播公式,则有,点评；考查一元函数相对误差传播。,第二章 要点回顾,1 二分法,二分法计算过程、二分法先

4、验误差：,2 不动点迭代法（普通迭代法）,不动点格式构造：,3 牛顿迭代法,牛顿迭代公式,不动点收敛性：（局部收敛性、全局收敛性）,不动点加速：Aiteken加速,牛顿迭代的局部收敛性和全局收敛性；,牛顿迭代公式的变形（非重点）,知识结构图,方程 的解 称为方程 的根或 称为 的零点，若 其中 m为正整数， 满足 ，则显然 这时称 为 的m重零点，或称 为 的m重根。,定理：若 只有m阶连续导数，则 是 的m重零点的充要条件为： ，,第二章 重点掌握,二分法执行步骤,1计算f (x)在有解区间a, b端点处的值，f (a)，f (b)。,2计算f (x)在区间中点处的值f (x1)。,3判断若

5、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) = 0 在a, b内至少有一实根x*。,简单迭代法,构造迭代格式,x = g (x),则对于任意的初值x0S，迭代公式 产生的序

6、列 必收敛于方程的根 。,（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充分靠近时，迭代法为p 阶收敛的充要条件是,牛顿法,x*,

7、x0,x1,x2,牛顿法的收敛性,定理： 设f (x)在a, b上满足下列条件： （1）f (a) f (b) 0 则由（2.3）确定的牛顿迭代序列xk收敛于f (x) 在a, b上的唯一根x*。,定理（Newton迭代法局部收敛性）：设 为 的根，如果：（1）函数f(x)在 的邻域具有连续的二阶导数；（2）在 的邻域 。,则存在 的某个邻域 ，对于任意的初始值x0S，由Newton迭代公式产生的数列收敛于根 。,Steffensen迭代格式,Newton法的变形,重根时的牛顿迭代法,Newton下降法,解；化简得到,根据牛顿迭代格式,则相应的得到,例2： 求方程,在区间1, 1.5内的实根。

8、要求准确到小数点后第2位。,解：预先估计一下二分的次数：按误差估计式,解得k = 6，即只要二分6次，即达所求精度。计算结果如下表：,解：因为f (0) = 10 f (1) = -7 0，知方程在0, 1中必有一实根， 现将原方程改为同解方程,由此得迭代格式,且由于,由为f (x) = 2x，所以得迭代公式,由于x 0时，f (x) 0，且f (x) 0，根据定理知：,故可取,解： 由,可得,由于,第三章 要点回顾,1 Guass消去法,Guass消去法、,2 矩阵三角分解法,LU分解法,平方根法（对称正定矩阵），追赶法（三对角方程）,向量范数和矩阵范数（三个）；,向量范数的连续性和等价性，

9、向量收敛性定义,Guass选主元消去法（列选主元，全选主元）,2 方程组的性态和误差估计,矩阵条件数，病态方程组,知识结构图,第一步：,若 令 ,用 乘 第一个方程加到第 个方程 ，并保留第一式，则得,Gauss消去法,其中,其中,按上述做法，做完n-1步，原方程可化为同解的 上三角方程组。,最后，设 ，逐步回代为原方程组的解：,定理：用高斯顺序消去法能够求解方程组 A 的解之 充要条件为A的各项顺序主子式均不为零。,再考虑 右下角矩阵，选取绝对值最大的元素作为主元素,经过行的对换和列的对换把主元素移到，,再按消元公式计算 （i,j=3,n）。,Gauss列选主元消去法,直接三角分解法,设A=

10、LU 即,第一步：,比较第一行元素：,第二步：,比较第二行元素：,算出：,比较第二列的元素：,得出：,算出：,算出:,算出:,这组公式可用下图记忆:,的求y过程为:,追赶法,设,即,由 得,由 得,第三章 典型例题,例2：用直接三角分解法解,解：（1）对于r = 1，利用计算公式,（2）对于r = 2，,（2）对于r = 3，,于是,（4）回代求解：,，,例5 对矩阵A进行LDL分解和LL分解，并求解方程组,解 对A进行LL分解,对A进行LDL分解,回代解方程组,得,再解,得,第四章 要点回顾,1 简单迭代法,简单迭代法构造,2 G-S迭代法,G-S迭代法的构造思想,G-S迭代法的收敛性分析,

11、Jacobi方法,基于Jacobi方法的G-S迭代法,简单迭代法的收敛性分析,2 常用迭代法,逐次超松弛迭代法,简单迭代法的构造,将该方程组等价变形为 构造简单迭代格 式 ， 。若 收敛于确定的向量 ，则 就是方程组的解。此时称简单迭代法 ， 关于初始向量 收敛。,设要求解的线性方程组为 ，其中 为非奇异矩阵， 为向量。,简单迭代法的收敛性,a.,b. 迭代矩阵的谱半径,1.收敛的充要条件,定理1.简单迭代法 ， ，对 任意初始向量 都收敛的充要条件是：,简单迭代法为 .,故,设 有唯一解 ，,几种常见的迭代法,一.Jacobi迭代法,设 , i=1,2,n,迭代格式,2.收敛条件,b.充分条

12、件：,（j=1,2,n）(按列),（II）设系数矩阵 严格对角占优，,或,则Jacobi迭代法关于任意初始向量 收敛,（I）若 则Jacobi方法关于任意初始向量 都 收敛。,即,a.充要条件：,二.与Jacobi迭代法相应的Gauss-Seidel法,1.迭代格式.,2.收敛条件.,G-S法关于任意初始向量 都 收敛的充要条件是 .,a.充要条件：,b.充分条件：,若 则G-S方法关于任意初始向量 都收敛.,SOR方法,第四章 典型例题,例2：用雅克比迭代法和高斯赛得尔迭代法 解线性方程组,解：所给线性方程组的系数矩阵按行严格对角占优， 故雅克比迭代法和高斯赛得尔迭代法都收敛。,雅克比迭代法

13、的迭代公式为：,取X(0) = (0, 0, 0)，由上述公式得逐次近似值如下：,X (i),4,3,2,1,0,k,高斯赛得尔迭代法：,例3设有方程组,1.当参数a满足什么条件时，雅可比方法对任意的,初始向量都收敛。,2.写出与雅可比方法对应的高斯赛德尔迭代公式。,解：当a不等于零时，雅可比方法的迭代矩阵为,可以解出B的特征值,可知B的谱半径,由此得出 时，雅可比方法收敛。,与雅可比方法对应的方法为,例设有方程组,证明该方程组对应雅可比方法发散，而G-S方法收敛。,解：雅可比方法的迭代矩阵为,设其特征值为 ，则,解：G-S的迭代矩阵为,第五章 要点回顾,1 插值问题与插值多项式的唯一性,2

14、拉格朗日型插值方法,Lagrange插值法,牛顿插值法 （差商、差分的定义）,完全导数形式的hermite插值（构造方法、余项）,不完全导数形式的hermite插值 （待定系数，重节点差商）,3 Hermite型插值方法,插值误差分析（拉格朗日余项，差商型余项）,4 分段插值和三次样条插值,知识结构图,拉格朗日插值基函数,一、插值基函数,定义：若n次多项式lk(x)(k=0, 1 , n)在n+1个插值节点x0 x1 xn上满足插值条件：,则称这n1个n次多项式l0(x), l1(x) , ln(x)为插值节点x0 ,x1 , , xn上的n次Lagrange插值基函数。,拉格朗日插值公式,将

15、Lagrange插值基函数与函数值线性组合得 可以验证 满足插值条件，即,i = 0, 1, 2, n,上式是不超过n次的多项式，称之为Lagrange插值多项式。,的线性组合。故可将满足插值条件（4.1）的n次多项式写成如下形式,牛顿插值的定义,由线性代数可知，任何一个不高于n次的多项式， 都可表示成函数,其中 为待定系数。这种形式的插值多项式称为牛顿Newton插值多项式,牛顿插值,差商的性质,性质1：,设 的n阶导数存在，则有,性质2：,k=1,2,n,性质3：,k阶差商 可以表示为函数值 的线性组合，即,差商具有对称性，与插值节点的排列次序无关。,Hermite 插值多项式,要求函数值

16、重合，而且要求若干阶导数也重合。,即：要求插值函数 P (x) 满足,在实际问题中，对所构造的插值多项式，不仅,把此类插值多项式称为埃米尔特（Hermite）,插值多项式，记为H (x)。,情形1；一阶导数已知,已知函数表,求一个插值多项式H (x)，使其满足如下条件：,插值条件的个数2n+2, H (x) 的次数：不超过2n+1次,i = 0, 1, 2, n,i = 0, 1, 2, n,Hermite插值多项式构造,对于问题1，取n=2，通过一个例子来讨论建 立Hermite插值的方法,例：求一个三次多项式 使其满足插值条件,(1),现在需要考虑的问题是这些基函数的构造问题。,则满足插值

17、条件的多项式可以写成如下形式,(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, 1, 2, m,待定系数法,通过一个简单的例子给出这种问题的解法,例 试确定一个不超过二次的多项式,使其满足如下插值条件,先利用前两个插值条件，构造一个1次 的插值多项

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

19、性空间。,函数,最佳平方逼近,正规方程组,最佳平方逼近的解函数：,内积空间,正交函数系,Legendre 多项系,定义,Legendre多项式系的前六项分别为,Chebyshev 多项式系,定义,第六章 典型例题,由此解得,所以,(单位：亿）,t表示年份试用下表提供的数据， 确定待定参数a和b, 并预测2000年的世界人口,解 所求拟合函数是一个指数函数，对它两边取 自然对数，得,建立如下新的数据表,进而有，人口模型的最小二乘拟合曲线为,据此模型预测2000年的世界人口为63.2377亿,用最小二乘法得法方程组,实际统计人口为60.5726亿,解 使用线性无关函数族,相应的正规方程组为,即,解

20、得,所求最佳平方逼近多项式为,平方逼近误差为,.,解 构造0,1上首项系数为1的正交多项式,的前三项. 设,由正交性,可解出,正规方程组为,计算可得,于是解得,的最佳二次平方逼近多项式为,平方逼近误差为,第七章 要点回顾,1 数值积分相关概念,2 基于等距节点的Newton-Cotes公式,代数精确度、插值型求积公式、求积稳定性、积分误差,复化梯形，复化Simpson公式,3 复化求积公式,梯形公式及误差分析,Simpson公式及误差分析,4 了解Romberg积分、Guass积分,5 数值微分相关概念及构造,知识结构图,求积公式,其中Rf称为求积公式的余项。,称为求积节点 。,称为求积系数。

21、,代数精（确）度,定义：如果,对于一切不高于m次的代数多项式准确成立。,而对于某个m+1次多项式并不准确成立。,则称上述求积公式具有m次代数精度。,Newtoncotes公式,将a，b分为n等份， ， 选取节点 ，,辛浦生（Simpson）公式或抛物线公式,梯形公式,Simpson公式误差估计,复化Simpson公式误差估计,梯形公式误差估计,复化梯形公式误差估计,Romberg算法,高斯公式和高斯点,定义若 是 上的一组互异节点，且求积公式,具有2n+1次代数精度，则称该求积公式为guass型求积公式，其求积节点 （k=0，1，n）称为高斯点，系数 称为高斯系数。,第七章 典型例题,1插值型求积公式的求积系数之和为1,解 因为两点Gauss型求积公式的代数精确度为3,解此非线性方程组得,所求Gauss型求积公式为,例6 建立两点Gauss型求积公式,的零点就是所求Gauss点,求Gauss系数,解得,故所求Gauss型求积公式为,解得,从所求方程组看出，该公式至少具有2次代数精确度。,又由于,求积公式,具有3次代数精确度。,其中,的代数精度最高此时代数精度为 ,10 参数 为多少时，求积公式,解：求积公式中含一个待定参数，,当f(x)=1,x时,有,令求积公式对 成立,即,解得,将 代入已求得的求积公式，显然,故,具有三次代数精度。,验证,11 取m=4,