万中-数值分析综合复习课-modified

数值分析综合复习万中教授/博导中南大学数学与统计学院第一章基本概念1误差的分类2有效数字有效数字与相对误差的关系4误差的传播5向量和矩阵的范数6算法及其设计的若干原则1、误差的分类（绝对误差，相对误差）

例1-1

设x*=2.18是由精确值x

经过“四舍五入”得到的近似值。问x的绝对误差限ε和相对误差限η各是多少？解：因为x=x*±0.005，

所以绝对误差限为ε=0.005相对误差限为：2、有效数字则称近似数

x*

具有n位有效数字。定义

设数x的近似值可以表示为其中m

是整数,αi(i=1,2,…,n)是0到9中的一个数字，而α1

≠0.如果其绝对误差限为结论：通过四舍五入原则求得的近似数，其有效数字就是从末尾到第一位非零数字之间的所有数字。例1-2

下列近似数是通过四舍五入的方法得到的，试判定它们各有几位有效数字：

解：我们可以直接根据近似数来判断有效数字的位数，也可以通过绝对误差限来判断。有5位有效数字。同理可以写出可以得出

x2

,x3

,x4

各具有4、3、4位有效数字。

x1*=87540，x2*=8754×10,x3*=0.00345,x4*=0.3450

×10-2已知例1-3

已知e=2.718281828……,试判断下面两个近似数各有几位有效数字？解：由于而所以

e1有7位有效数字。同理：e2

只有6位有效数字。

定理1

设（1.2.2）用有效数字的位数估计相对误差限有效数字的位数越多，相对误差限就越小3.有效数字与相对误差之间的关系x的近似值xA有n位有效数字，则如果（1.2.4）相对误差限越小，有效数字的位数就越多相对误差限估计有效数字的位数则xA有n位有效数字.

定理2设4、误差的传播(1)

对函数的计算：

对一元函数f(x),自变量x的一个近似值为xA，以f(xA)近似f(x),其误差界记作(f(xA))对多元函数例1-4设有三个近似数它们都有三位有效数字。试计算p=a+bc的误差界，并问p的计算结果能有几位有效数字？解相对误差界所以,pA=6.6332能有两位有效数字。于是有误差界5、向量和矩阵范数向量的范数矩阵的相容范数例1-5计算下列矩阵的范数：例1-6求矩阵的谱半径.矩阵A的特征值为所以谱半径解简述题：1.叙述在数值运算中，减少误差的原则是什么？解：减少误差的原则：1）要避免除数绝对值远远小于被除数的绝对值2）要避免相近数相减；3）求和中要防止大数吃掉小数；4）简化计算步骤，减少运算次数。6、算法设计的若干原则第二章插值与最优逼近1、插值的概念；掌握拉格朗日(Lagrange)插值法及其余项公式；掌握牛顿插值法；掌握差商表的构造过程。2、会构造埃尔米特(Hermite)插值及其余项公式；掌握差商表的构造过程；知道高次插值的病态性质（高次插值的Runge

现象）；会构造三次样条插值。3、最优平方逼近Lagrange插值多项式显然，L(x)是不超过n次多项式。当n=1时，称为线性插值。当n=2时，称为抛物线插值。y0

xxk

xk+1①线性插值：特别地，n=1,2时的插值余项：y0x②抛物线插值：xk-1xk

xk+1例2-1

给定数据表

xi0123yi01514求三次(?)拉格朗日插值多项式L3(x).例2-2

要制作三角函数sinx的值表.要求表值有四位小数。若用线性插值，则为保证截断误差不超过表值的舍入误差，其最大允许的步长是多少？解f(x)=sinx,设xi－１,xi为任意两个插值节点，最大允许步长记为

h=hi=xi

－xi－１，Newton插值多项式：例2-3：已知f(x)的部分信息：(1,0)、(2,2)、(3,12)、(4,42)、(5,116),（1）求牛顿插值多项式N4(x)；（2）若增加一个节点(6,282),求N5(x)，（3）估算f(1.5)、f(1.5).解：先由前五组数据列差商表10223124425116210307441022240.5628216646810.1如果，再增加一点(6,282),就在上表中增加一行计算差商得到：由Newton公式的递推式得到：得到：解：典型例题分析例2-4：令x0＝0，x1＝1，写出y(x)＝e-x的一次插值多项式L1(x),并估计插值误差．

记x0＝0，x1＝1,y0＝e-0＝1，y1＝e-1;则函数y＝e-x以x0、x1为节点的一次插值多项式为因为

y′(x)＝-e-x，y"(x)＝e-x

，所以例2-5推广：等距节点(h),二次插值的误差界是例2-6

：设f(x)＝x4，试利用拉格朗日插值余项定理写出以-1,0,1,2为插值节点的三次插值多项式．解:

记f(x)以-1，0，1，2为插值节点的三次插值多项式为L3(x)．由插值余项定理有所以例2-7：证明由下列插值条件所确定的拉格朗日插值多项式是一个二次多项式．该例说明了什么问题?以x0，x2，x4为插值节点作f(x)的2次插值多项式p(x)，则解:x0x2x4

容易验证因而6个点(xi,yi)，i＝01,…,5均在二次曲线p(x)＝x2-1上．换句话说，满足所给插值条件的拉格朗日插值多项式为

p(x)＝x2-1.例2-8：

分析:

这是一个非标准插值问题,我们可以按各种思路去做．可按两种方法去做:一种是先求牛顿或拉格朗目型插值,再通过待定系数法求Pn(x)；另一种是先求埃尔米特插值,再通过待定系数法确定Pn(x)．下面给出三种做法．

例2-9：求一个次数不高于4的多项式P4(x)，使它满足P4(0)=P4'(0)=0，P4(1)=P4'(1)=1，P4(2)=1．

解法一先求满足P4(0)=0，P4(1)=1，P4(2)=1的插值多项式P2(x)，易得显然P4(x)满足P2(x)的插植条件，利用两个导数条件确定系数A，B．由P4'(0)=0,P4'(1)=1解得A=1/4,B=-3/4.故设解法二先作满足埃尔米特插值多项式H3(x)．解法三构造插值基函数求.记x0=0，x1=1，x2=2，并设所求多项式为

其中li(x)均为次数不超过4的多项式且满足如下条件：易知例2-10例2-11例2-12例2-13例2-14：已知函数y=f(x)

的如下数据,试求其在区间[0,3]上的三次样条插值函数S(x)。

解这里边界条件是设求得已知由方程组及得到方程组解得这样便求得代入表达式便得到所求的三次样条函数3、最优平方逼近函数类考虑特殊情形-(1)用多项式｛1,x,x2,…,xn｝作n次最佳平方多项式p*(x)逼近步骤/方法(权函数为１时，［a,b］=[0,1])解法方程组Ga=d(2)用正交多项式作最佳平方逼近

方法（步骤）：解法方程组平方误差其中，例2-16最小二乘逼近步骤：平方误差有与（2.4.15）相同形式的表达式。(2)多项式的拟合即在多项式空间中作曲线拟合，称为多项式拟合。用上面讨论的方法求解。子空间的基函数为

前面讨论了子空间中的最小二乘拟合。在离散数据的最小二乘拟合中，最简单、最常用的数学模型是多项式（2.5.4）

例2.19用多项式拟合表2-4中的离散数据。

yi0.100.350.811.091.96

xi

0.000.250.500.751.00

i12345表2-4解作数据点的图形如图2-2，从图形看出用二次多项式拟合比较合适。这时n=2，子空间的基函数。数据中没有给出权数，不妨都取为1，即。oy1.961x****图2-2例2-17ixiyixi2xi3xi4xiyixi2yi00.000.100.0010.250.350.062520.500.810.2530.751.090.562541.001.961.002.54.311.8751.56251.38283.272.7975构造下表按（2.5.4）有

解此方程组得。从而，拟合多项式为其平方误差。拟合曲线的图形见图2-2。oy1.961x****图2-2正交多项式拟合这时直接可算出，法方程组的矩阵形式为例2-18：

对如下数据作形如

y

=aebx

的拟合曲线

解:

由于函数集合Φ={aebx|a,b∈R}

不成为线性空间，因此直接作拟合曲线是困难的。

在函数y=aebx

两端分别取对数得到这时，需要将原函数表进行转换如下令

z=lny,A=lna,B=b,则

z=A+Bxlny=lna+bxxi12345678yi15.320.527.436.649.165.687.8117.6对z=A+Bx

作线性拟合曲线，取这时xi12345678yi15.320.527.436.649.165.687.8117.6xi12345678zi2.723.023.313.603.894.184.484.77得正则方程组解得

于是有拟合曲线为：第三章数值积分插值型积分公式了解数值求积的基本思想、代数精度的概念、插值型求积公式及其代数精度、求积公式的收敛性和稳定性。掌握牛顿-柯特斯公式及其性质和余项。掌握复化梯形公式和复化辛普森公式及其余项。掌握龙贝格(Romberg)求积算法，知道外推法。会高斯求积公式,了解高斯-勒让德求积公式和高斯-切比雪夫求积公式。一、数值积分

等价定义若求积公式对于1，x,…,xm都精确成立，对xm+1不精确成立，则称该求积公式的代数精度为m。(3.1.1)引理：n阶Newton-Cotes公式的代数精度至少是n.结论：当n

为奇数时，n阶Newton-Cotes公式的代数精度为n；当n

为偶数时，n阶Newton-Cotes公式的代数精度为n+1。2、Cotes系数特点：梯形公式代数精度=1Simpson公式代数精度=3柯特斯公式（Cotes)代数精度=5,复化梯形公式复化梯形公式是2阶收敛的复化Simpson求积公式复化Simpson公式具有4阶收敛龙贝格(Romberg)求积算法

稳定性定理若求积公式(3.1.1)中系数Ak＞0(k＝0，1，…，n)，则此求积公式是稳定的．2、求积余项

若,(3.1.5)是插值型求积公式,其中与变量x有关,记作

x

。特别地,如果求积公式是插值型的,按余项式,对于次数≤

n的多项式f(x)，其余项R[f]等于0，因而这时求积公式至少具有n次代数精度．则有余项公式Gauss型求积公式当求积系数Ak、求积节点xk都可以自由选取时,其代数精确度最高可以达到2n+1次?

(3.4.1)考虑带权求积公式较简单的方法是：先利用区间a,b上的n+1次正交多项式确定高斯点xk

∈[a,b],(k=0,1,…n)(2)然后利用高斯点确定求积系数Ak,(k=0,1,…n)插值求积公式节点一经确定，相应的求积系数就确定了，常用的Gauss求积公式1.Gauss-Legendre求积公式不失一般性，可取a=-1，b=1而考察区间[-1，1]上的高斯公式在区间[-1，1]上取权函数那么相应的正交多项式为Legendre多项式。以Legendre多项式的零点为Gauss点的求积公式为（3.4.8）称之为Gauss-Legendre求积公式。两点Gauss—Legendre公式：五次代数精度的3点Gauss-Legendre求积公式定理

3.4.2设,则Guass公式(3.4.1)的余项是(3.4.10)特别地，对于两点Gauss-Legendre求积公式有解：所以该求积公式的代数精度m=3。例3-1例3-2

试构造形如f(x)dxA0f(0)+A1f(h)+A2f(2h)的数值求积公式,使其代数精度尽可能高,并指出其代数精度的阶数.3h0解:

令公式对

f(x)=1,x,x2

均准确成立,则有3h=A0+A1+A2h2=0+

A1h+A22h9h3=0+A1h2+A24h229故求积公式的形式为解之得

A0=h,

A1=0,A2=h.9434f(x)dxf(0)+f(2h)3h49h43h0而当f(x)=x3时,公式的左边=81h4/4,右边=18h4,公式的左边右边,说明此公式对f(x)=x3不能准确成立.因此,公式只具有2次代数精度.由公式的构造知,公式至少具有2次代数精度;例3-3例3-4例3-5例3-6的近似值，要求误差例3-8用Romberg求积法计算解：此时积分限为a=0,b=1.而(本例主要说明Romberg过程）

①．

③．④．⑤．⑥．⑦．⑧．⑨．⑩．②．如此继续算得：由于例3-9构造三个节点的Gauss-Legendre求积公式，并给出余项估计式。

解：由于三次Legendre多项式为：其三个零点分别为：令它对准确成立则三点Gauss-Legendre求积公式为：余项为：（节点数）例如，若要计算的近似值，则由上积分公式得：上述积分准确值为：若利用三点Simpson求积公式。则可见在节点数目相同的情况下，Gauss求积公式的精度是相当高的。例3-10例3-11第4-6章综合复习课

1、线性方程组数值解法

2、非线性方程求根一、解线性方程组的直接方法基本内容及基本要求了解求解方程组的两类方法,了解矩阵基础知识。掌握高斯消去法,会矩阵的三角分解。掌握高斯列主元素消去法,了解高斯-若当消去法。掌握直接三角分解法,了解平方根法,会追赶法,了解有关结论。了解向量和矩阵的几种范数。了解矩阵和方程组的性态,会求其条件数。解线性方程组的直接方法

一般的线性方程组解法：

列（全）主元素Gauss消元法

LU分解（直接三角分解法）

特殊的线性方程组解法：

平方根法（改进）对称正定矩阵

追赶法三对角方程组

矩阵表示与计算量

误差分析（条件数）：

向量、矩阵范数，

误差分析（条件数），

病态方程。右端项b的扰动对解的影响系数矩阵A的扰动对解的影响例4-1例4-2例4-3例4-4例4-5分别用顺序Gauss消去法和直接三角分解法(杜利特分解)求解线性方程组

四、练习---线性方程组直接解法2.用带行交换的杜利特分解计算线性代数方程组AX=b，其中3.用追赶法求解三对角方程组二、线性方程组的迭代解法基本内容及基本要求了解迭代法及其收敛性的概念。掌握雅可比(Jacobi)迭代法、高斯-赛德尔(Gauss-Seidel)迭代法和超松弛(SOR)迭代法。3.了解一阶定常迭代法的基本定理，掌握特殊方程组迭代法的收敛条件。4.知道分块迭代法。解线性方程组的迭代法方法

迭代方法：

雅可比（Jacobi）迭代法

高斯－赛德尔(Gauss-Seidel)迭代法

松弛法

迭代矩阵的表示

迭代法的收敛判别：

矩阵的谱半径

迭代法的收敛定理及推论（迭代矩阵）

对系数矩阵A的三条判别原则

误差估计与停机准则雅可比迭代法计算公式：对k=0,1,…,高斯—塞德尔迭代法计算公式：对k=0,1,…,SOR迭代法的计算公式:对k=0,1,…,例5-3例5-4.例5-5.三、非线性方程的数值解法基本内容及基本要求

了解求根问题和二分法。了解不动点迭代法,及不动点存在性和迭代收敛性；了解收敛阶的概念和有关结论。3.了解加速迭代收敛的埃特金方法和斯蒂芬森方法。4.掌握牛顿法及其收敛性、了解简化牛顿法和牛顿法下山法,了解重根情形。5.掌握弦截法，了解抛物线法。1.设x*是f(x)=0在[a,b]内的唯一根,且f(a)·f(b)<0,则二分法计算过程中,数列满足:|xn–x*|≤(b–a)/2n+1

收敛充分性定理

收敛充分性定理(三)重根的情形该迭代至少二阶收敛.例1

已知迭代公式

收敛于

证明该迭代公式平方收敛.证:

迭代公式相应的迭代函数为将

代入，根据定理可知，迭代公式平方收敛。解因,所以迭代公式为例2:用牛顿法求下面方程的根从计算结果可以看出,牛顿法的收敛速度是很快的,进行了四次迭代就得到了较满意的结果.计算结果列于下表选取,例3

计算的近似值。

=10-6

x0=0.88由牛顿迭代公式

xk+1=xk-ƒ(xk)/ƒ'(xk)=xk/2+0.78265/2xk解：令x=问题转化为求ƒ(x)=x2-0.78265=0的正根迭代结果

k

0

123xk0.8800000.8846880.8846750.884675满足了精度要求

=0.884675

例4

应用牛顿迭代法于方程

x3–a=0,导出求立方根的迭代公式,并讨论其收敛性。解：令f(x)=x3–a，则牛顿迭代公式故立方根迭代算法二阶收敛例5.设a

为正实数，试建立求1/a

的牛顿迭代公式，要求在迭代公式中不含有除法运算，并考虑迭代公式的收敛。xn+1=xn(2–axn)，(n=0，1，2……)所以,当|1–ax0|<1时，迭代公式收敛。解:建立方程利用牛顿迭代法，得1–axn+1=(1–axn)2

整理，得例6例7练习题：第七章矩阵特征值问题计算

了解特征值和特征向量的概念和性质,

了解圆盘定理、Schur定理和Rayleigh商。2.掌握乘幂法，了解其加速收敛技术,会反幂法。3.了解Jacobi方法。4.了解QR方法。基本内容及基本要求

知识结构图矩阵特征值与特征向量的计算幂法（幂法加速）满足条件的实矩阵最大特征值及其相应的特征向量。反幂法满足条件的实矩阵