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

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

《数值分析期末复习总结.ppt》由会员分享，可在线阅读，更多相关《数值分析期末复习总结.ppt（130页珍藏版）》请在冰点文库上搜索。

1,期末复习总结,计算方法,董君良北京工业大学/应用数理学院,2,第一章,数值计算的误差,计算方法,3,绝对误差：

绝对误差,x精确值x*近似值,绝对误差可能取正，也可能取负绝对误差越小越具有参考价值但绝对误差却不能很好地表示近似值的精确程度,4,相对误差,相对误差：

若存在正数r*，使得|er*|r*，则称r*为相对误差限,近似值的精确程度取决于相对误差的大小实际计算中我们所能得到的是误差限或相对误差限,5,有效数字,有效数字：

若近似值x*的误差限是某一位的半个单位（即截取按四舍五入规则），且该位到x*的第一位非零数字共有n位，则称x*有n位有效数字,6,有效数字,例：

=3.14159265，近似值x1=3.1415，x2=3.1416问：

x1,x2分别有几位有效数字？

例：

写出下列各数的具有5位有效数字的近似值187.9325，0.03785551，2.7182828，8.000033,187.93，0.037856，2.7183，8.0000,注：

0.2300有4位有效数字，而0.23只有2位有效数字12300如果写成0.123105，则表示只有3位有效数字。

数字末尾的0不可以随意添加或省略！

7,有效数字,定理：

设近似值x*可表示为x*=a1.a2al10m（a10），若x*具有n位有效数字，则其相对误差限满足,1,r*,2a1,10-（n-1）,有效位数越多，相对误差限越小,8,第二章插值法,计算方法,9,插值基本概念,已知函数y=f（x）在a,b上有定义，且已经测得在点ax0x1xnb处的函数值为y0=f（x0），yn=f（xn）,什么是插值,如果存在一个简单易算的函数P（x），使得P（xi）=f（xi），i=1,2,.,n则称P（x）为f（x）的插值函数,求插值函数P（x）的方法就称为插值法,10,基函数插值法,基函数法,通过基函数来构造插值多项式的方法就称为基函数插值法,Zn（x）=次数不超过n的多项式的全体,记,11,Lagrange插值,Lagrange插值基函数,设lk（x）是n次多项式，在插值节点x0,x1,xn上满足,则称lk（x）为节点x0,x1,xn上的拉格朗日插值基函数,单项式基函数,利用线性无关的单项式族：

构造n次多项式：

12,线性与抛物线插值,两种特殊情形,n=1,线性插值多项式（一次插值多项式）,13,插值举例,例：

已知函数y=lnx的函数值如下,解：

试分别用线性插值和抛物线插值计算ln0.54的近似值,为了减小截断误差，通常选取插值点x邻接的插值节点,14,插值举例,抛物线插值：

取x0=0.4,x1=0.5,x2=0.6,可得,ln0.54L2（0.54）=-0.6153,在实际计算中，不需要给出插值多项式的表达式,ex21.m,Lagrange插值多项式简单方便，只要取定节点就可写出基函数，进而得到插值多项式，易于计算机实现。

15,Lagrange插值,lk（x）的表达式,由构造法可得,16,误差估计,如何估计误差,17,插值余项,余项公式只有当f（x）的高阶导数存在时才能使用,几点说明,计算插值点x上的近似值时，应选取与x相近插值节点,18,插值误差举例,例：

已知函数y=lnx的函数值如下,试估计线性插值和抛物线插值计算ln0.54的误差,19,Newton插值,为什么Newton插值,Lagrange插值简单易用，但若要增加一个节点时，全部基函数lk（x）都需重新计算，不太方便。

设计一个可以逐次生成插值多项式的算法，即n次插值多项式可以通过n-1次插值多项式生成Newton插值法,解决办法,20,新的基函数,设插值节点为x0,xn，考虑插值基函数组,当增加一个节点xn+1时，只需加上基函数,21,Newton插值,此时f（x）的n次插值多项式为,问题,如何从pn-1（x）得到pn（x）?

怎样确定参数a0,an?

需要用到差商（均差）,22,差商,什么是差商,设函数f（x），节点x0,xn,f（x）关于点xi,xj的,一阶差商,f（x）关于点xi,xj,xk的,二阶差商,k阶差商,差商的一般定义,23,差商的性质,k阶差商与k阶导数之间的关系：

若f（x）在a,b上具有k阶导数，则至少存在一点（a,b），使得,24,差商的计算,如何巧妙地计算差商,差商表,25,差商举例,例：

已知y=（x）的函数值表，试计算其各阶差商,解：

差商表如下,ex24.m,ex23.m,26,Newton插值公式,Newton插值公式,由差商的定义可得,Nn（x）,Rn（x）,27,Newton插值公式,f（x）=Nn（x）+Rn（x）,Nn（x）是n次多项式,Nn（xi）=f（xi），i=0,1,2,n,重要性质,Nn（x）是f（x）的n次插值多项式,其中,28,Newton/Lagrange,Newton插值多项式与Lagrange插值多项式,f（x）在x0,x1,xn上的n次插值多项式是唯一的！

Nn（x）Ln（x）,余项也相同,将x看作节点,29,插值举例,例：

已知函数y=lnx的函数值如下,解：

取节点0.5,0.6,0.4作差商表,试分别用牛顿线性插值和抛物线插值计算ln0.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,插值节点无需递增排列，但必须确保互不相同！

30,第三章函数逼近与FFT,计算方法,31,函数逼近,三个问题,问题一,已知一个函数的数值表,能否找到一个简单易算的p（x），使得p（xi）=yi。

问题二,函数f（x）的表达式非常复杂，能否找到一个简单易算的p（x），使得p（x）是f（x）的一个合理的逼近。

问题三,问题一的表中的数值带有误差，能否找到一个简单易算的p（x），可以近似地表示这些数据。

32,赋范线性空间,赋范线性空间Ca,b,线性空间Ca,b，f（x）Ca,b,1-范数：

2-范数：

-范数：

33,逼近标准,度量p（x）与f（x）的近似程度的常用两种标准,使尽可能地小。

使尽可能地小。

34,函数逼近,记Hn为所有次数不超过n的多项式组成的集合，给定函数f（x）Ca,b，若P*（x）Hn使得,则称P*（x）为f（x）在Ca,b上的最佳逼近多项式,最佳逼近,最佳一致逼近,35,函数逼近,最小二乘拟合,寻找P*（x），使得下面的离散2-范数最小,给定f（x）Ca,b的数据表,最佳平方逼近,36,正交多项式,定义,设n（x）是首项系数不为0的n次多项式，若,则称为a,b上带权（x）正交,性质1,设是正交多项式族，Hn为所有次数不超过n的多项式组成的线性空间，则,构成Hn的一组基,称n（x）为n次正交多项式,37,Legendre多项式,Pn（x）的首项xn的系数为：

Legendre多项式,在-1,1上带权（x）=1的正交多项式称为勒让德多项式,x-1,1，n=1,2,记号：

P0,P1,P2,.,则是首项系数为1的勒让德多项式,令,38,Legendre多项式,ex31.m,其中P0（x）=1,P1（x）=x，,39,Chebyshev多项式,Chebyshev多项式,在-1,1上带权（x）的正交多项式称为切比雪夫多项式,x-1,1，n=0,1,2,切比雪夫多项式的表达式,令x=cos，则Tn（x）=cos（n），展开后即得,40,Chebyshev多项式,ex32.m,41,Chebyshev零点插值多项式,Chebyshev插值,以Chebyshev多项式的零点作为插值节点进行插值,好处：

误差最小,定理,设f（x）Cn+1-1,1，插值节点x0,x1,xn为Tn+1（x）的n+1个零点，则,且,42,最佳平方逼近,设f（x）Ca,b，0（x）,1（x）,n（x）Ca,b线性无关，令,求S*（x），使得,S*（x）称为f（x）在中的最佳平方逼近函数,其中,43,最佳平方逼近,如何求S*（x）？

44,最佳平方逼近,即,法方程,G,45,求在0,1上的一次最佳平方逼近多项式,举例,例：

（教材68页，例6）,解：

46,最佳平方逼近多项式,f（x）Ca,b在Hn中的最佳平方逼近，记为,n次最佳平方逼近多项式,取Hn的一组基：

1,x,x2,xn，则法方程为,H,Hilbert矩阵,H严重病态只适合求低次最佳逼近,47,正交函数作逼近,若0,1,n正交，则法方程的解为,所以,k=0,1,n,误差,Bessel不等式,48,曲线拟合,能否找到一个简单易算的p（x），使得f（x）p（x）,已知f（x）在某些点的函数值：

49,使最小,使最小,曲线拟合,p（xi）yi总体上尽可能小,使最小,常见做法,50,最小二乘,曲线拟合的最小二乘问题,这个问题实质上是最佳平方逼近问题的离散形式。

可以将求连续函数的最佳平方逼近函数的方法直接用于求解该问题。

已知函数值表（xi,yi），在函数空间中求S*（x），使得,其中i是点xi处的权。

51,最小二乘求解,对任意S（x）=span0,1,n，可设,S（x）=a00+a11+ann（x）,则求S*（x）等价于求下面的多元函数的最小值点,52,最小二乘求解,（k=0,1,n）,这里的内积是离散带权内积，即,，,法方程,G,53,最小二乘求解,54,举例,最小二乘问题中，如何选择数学模型很重要，即如何选取函数空间=span0,1,n，通常需要根据物理意义，或所给数据的分布情况来选取合适的数学模型。

55,多项式拟合,Hn=span1,x,.,xn,即i=xi,则相应的法方程为,此时为f（x）的n次最小二乘拟合多项式,多项式最小二乘曲线拟合,56,举例,例：

求下面数据表的二次最小二乘拟合多项式,得法方程,解得,所以此组数据的二次最小二乘拟合多项式为,

（1）若题目中没有给出各点的权值i，默认为i=1

（2）该方法不适合n较大时的情形（病态问题）,57,第四章数值积分与数值微分,计算方法,58,数值积分,微积分基本公式：

59,几个简单公式,矩形公式,梯形公式,抛物线公式,基本思想：

60,一般形式,数值积分公式的一般形式,将定积分计算转化成被积函数的函数值的计算无需求原函数易于计算机实现,一般地，用f（x）在a,b上的一些离散点ax0x1xnb上的函数值的加权平均作为f（）的近似值，可得,61,代数精度,定义：

如果对于所有次数不超过m的多项式f（x），公式,精确成立，但对某个次数为m+1的多项式不精确成立，则称该求积公式具有m次代数精度,62,举例,例：

试确定系数Ai，使得下面的求积公式具有尽可能高的代数精度，并求出此求积公式的代数精度。

易验证该公式对f（x）x3也精确成立，但对f（x）x4不精确成立，所以此求积公式具有3次代数精度。

63,插值型求积公式,设求积节点为：

ax0x1xnb若f（xi）已知，则可做n次多项式插值：

其中,插值型求积公式,64,Newton-Cotes公式,基于等分点的插值型求积公式,积分区间：

a,b求积节点：

xi=a+ih,求积公式：

Cotes系数,Newton-Cotes求积公式,65,Newton-Cotes公式,n=1:

代数精度=1,梯形公式,n=2:

代数精度=3,抛物线公式Simpson公式,n=4:

科特斯（Cotes）公式,代数精度=5,66,N-C公式余项,梯形公式（n=1）的余项,Simpson公式（n=2）的余项,Cotes公式（n=4）的余项,67,复合求积公式,提高积分计算精度的常用两种方法,用复合公式用非等距节点,将积分区间分割成多个小区间在每个小区间上使用低次牛顿科特斯求积公式,复合求积公式,68,复合梯形公式,将a,b分成n等分xi,xi+1，其中,（i=0,1,n）,复合梯形公式,余项,69,复合Simpson公式,复合Simpson公式,余项,性质：

复合梯形公式和复合Simpson公式都是收敛的，也都是稳定的。

70,举例,解：

例：

设，利用下表中的数据分别用复合梯形公式和复合simpson公式计算定积分，并估计误差。

71,举例,误差估计,72,第五章解线性方程组的直接方法,计算方法,73,Gauss消去法,例：

直接法解线性方程组,74,Gauss消去法,高斯消去法的主要思路：

将系数矩阵A化为上三角矩阵，然后回代求解。

考虑n阶线性方程组：

75,计算LU分解,利用矩阵乘法直接计算LU分解,LU=A,比较等式两边的第一行得：

u1j=a1j,比较等式两边的第一列得：

比较等式两边的第二行得：

比较等式两边的第二列得：

（j=1,n）,（i=2,n）,（j=2,n）,（i=3,n）,76,计算LU分解,第k步：

此时U的前k-1行和L的前k-1列已经求出,比较等式两边的第k行得：

比较等式两边的第k列得：

直到第n步，便可求出矩阵L和U的所有元素。

（j=k,n）,（i=k+1,n）,77,LU分解算法,算法：

（LU分解）,fork=1ton,end,j=k,n,i=k+1,n,Matlab程序参见：

ex51.m,运算量：

（n3-n）/3,为了节省存储空间，通常用A的绝对下三角部分来存放L（对角线元素无需存储），用A的上三角部分来存放U,78,例求下列矩阵的LU分解,解:

设,LU分解算法,79,LU分解算法,80,LU分解算法,81,（i=n,1）,（i=1,n）,两次回代过程求出方程组的解：

运算量:

n2,加LU分解,总运算量：

LU分解求解线性方程组,82,对称正定矩阵的三角分解Cholesky分解,定理：

设A是对称矩阵，若A的所有顺序主子式都不为0，则A可唯一分解为其中L为单位下三角阵，D为对角矩阵,A=LDLT,定理：

（Cholesky分解）若A对称正定，则A可唯一分解为其中L为下三角实矩阵，且对角元素都大于0,A=LLT,对称正定矩阵的Cholesky分解,83,计算Cholesky分解,Cholesky分解的计算,直接比较等式两边的元素,计算公式,84,Cholesky分解算法,forj=1tonend,i=j+1,n,算法：

（Cholesky分解）,运算量:

n3/6+n2/2+n/3,85,Cholesky分解算法,例对矩阵作Cholesky分解,解,86,Cholesky分解算法,87,向量范数,常见的向量范数,无穷范数（最大范数）,2-范数,1-范数,88,范数性质,范数的性质,

（1）连续性,设f是Rn上的任意一个范数，则f关于x的每个分量是连续的,

（2）等价性,设|s和|t是Rn上的任意两个范数，则存在常数c1和c2，使得对任意的xRn有,证明：

板书,89,范数性质,（3）Cauchy-Schwarz不等式,（4）向量序列的收敛性,矩阵的谱：

（A）=A的所有特征值,矩阵的谱半径：

90,矩阵范数,常见的矩阵范数,

（1）F-范数（Frobenious范数）,

（2）算子范数（从属范数、诱导范数）,其中|是Rn上的任意一个范数,91,算子范数,常见的算子范数,无穷范数（行范数）,2-范数（谱范数）,1-范数（列范数）,证明：

板书，为练习,例：

设计算,92,矩阵范数性质,矩阵范数的性质,

（1）连续性：

设f是Rnn上的任一矩阵范数，则f关于A的每个分量是连续的,

（2）等价性：

设|s和|t是Rnn上的任意两个矩阵范数，则存在常数c1和c2，使得对任意的ARnn有,（3）若A是对称矩阵，则,93,定理：

设|是Rn上的任一向量范数，其对应的算子范数也记为|，则有,算子范数性质,算子范数的性质,定理：

设|是任一算子范数，则,定理：

对任意0,总存在一算子范数|，使得|（A）+,94,稳定性理论分析,理论分析：

设,又,

（1）由于右端项的扰动而引起的解的变化,

（2）由于系数矩阵的扰动而引起的解的变化,设,Ax=b的条件数矩阵A的条件数,95,稳定性理论分析,定理：

考虑线性方程组Ax=b，设b是精确的，A有微小的变化A，此时的解为x+x，则,证明：

当A充分小时，不等式右端约为,设,结论,96,矩阵条件数,条件数与范数有关，常用的有无穷范数和2-范数,Cond（A）2称为谱条件数，当A对称时有,97,举例,例：

计算Cond（A）和Cond（A）2,解：

Cond（A）=|A-1|A|4104,Cond（A）2=max/min4104,A对称，且,98,第六章线性方程组的迭代解法,计算方法,99,矩阵分裂迭代法,矩阵分裂迭代法基本思想,Ax=b,100,收敛性分析,定理：

对任意初始向量x（0），上述迭代格式收敛的充要条件是,证明：

板书,例：

考虑迭代法x（k+1）=Bx（k）+f的收敛性，其中,基本收敛定理,充分条件,101,Jacobi迭代,考虑线性方程组,Ax=b,其中A=（aij）nn非奇异，且对角线元素全不为0。

将A分裂成A=D-L-U，其中,102,Jacobi迭代,k=0,1,2,令M=D，N=L+U，可得雅可比（Jacobi）迭代方法,Jacobi迭代,迭代矩阵记为：

103,Gauss-Seidel迭代,在计算时，如果用代替，则可能会得到更好的收敛效果。

104,Gauss-Seidel迭代,写成矩阵形式:

此迭代方法称为高斯-塞德尔（Gauss-Seidel）迭代法,k=0,1,2,可得,迭代矩阵记为：

105,SOR迭代,为了得到更好的收敛效果，可在修正项前乘以一个松弛因子，于是可得迭代格式,在G-S迭代中,106,SOR迭代,写成矩阵形式:

可得,SOR（SuccessiveOver-Relaxation）迭代方法,迭代矩阵记为：

SOR的优点：

通过选取合适的，可获得更快的收敛速度SOR的缺点：

最优参数的选取比较困难,107,Jacobi迭代收敛的充要条件（J）1G-S迭代收敛的充要条件（G）1SOR迭代收敛的充要条件（L）1,收敛性,收敛性定理,Jacobi迭代收敛的充分条件|J|1G-S迭代收敛的充分条件|G|1SOR迭代收敛的充分条件|L|1,108,Jacobi、G-S收敛性,定理：

若A严格对角占优或不可约弱对角占优，则A非奇异,109,SOR收敛性,定理：

若SOR迭代收敛，则02。

SOR收敛的必要条件,110,举例,例：

设，给出Jacobi和G-S收敛的充要条件,111,举例,解法二：

Jacobi的迭代矩阵为,设是J的特征值，则由det（I-J）=0可得,（-a）2（+2a）=0,Jacobi收敛的充要条件是（J）1|1，即-0.5a0.5,112,收敛速度,定义：

迭代格式x（k+1）=Bx（k）+f的平均收敛速度为,渐进收敛速度为,（B）越小，收敛越快,113,第七章非线性方程（组）的数值解法,计算方法,114,不动点迭代,基本思想,构造f（x）=0的一个等价方程：

115,不动点迭代,具体过程,任取一个迭代初始值x0，计算,得到一个迭代序列：

x0，x1，x2，.，xn，.,k=0,1,2,.,几何含义：

求曲线y=（x）与直线y=x的交点,116,连续性分析,设（x）连续，若收敛，即，则,收敛性分析,性质：

若，则不动点迭代收敛，且x*是f（x）=0的解；否则迭代法发散。

117,解的存在唯一性,定理：

设（x）Ca,b且满足,证明：

板书,对任意的xa,b有（x）a,b存在常数0L1，使得任意的x,ya,b有,则（x）在a,b上存在唯一的不动点x*,解的存在唯一性,118,收敛性分析,定理：

设（x）Ca,b且满足,证明：

板书,对任意的xa,b有（x）a,b存在常数0L1，使得任意的x,ya,b有,则对任意初始值x0a,b，不动点迭代xk+1=（xk）收敛，且,不动点迭代的收敛性,119,收敛性分析,不动点迭代的收敛性,若（x）C1a,b且对任意xa,b有|（x）|L1则上述定理中的结论成立。

收敛性结论表明：

收敛性与初始值的选取无关,120,举例,例：

求f（x）=x3x1=0在区间1,2中的根,ex71.m,121,局部收敛,定义：

设x*是（x）的不动点，若存在x*的某个-邻域U（x*）=x*-,x*+，对任意x0U（x*），不动点迭代xk+1=（xk）产生的点列都收敛到x*，则称该迭代局部收敛。

局部收敛,122,收敛速度,定义：

设迭代xk+1=（xk）收敛到（x）的不动点x*，记ek=xkx*，若,其中常数C0，则称该迭代为p阶收敛。

当r=1时称为线性收敛，此时C1时称为超线性收敛,二分法是线性收敛的若（x*）0，则不动点迭代xk+1=（xk）线性收敛,123,收敛速度,定理：

设x*是（x）的不动点，若（p）（x）在x*的某邻域内连续，且,则迭代xk+1=（xk）是p阶收敛的。

证明：

板书,124,举例,例：

求f（x）=x2-3=0的正根,

（1）,ex72.m,

（2）,（3）,二次收敛,局部收敛,125,Newton法,基本思想,将非线性方程线性化,设xk是f（x）=0的近似根，将f（x）在xk处Taylor展开,条件：

f（x）0,126,Newton法,x,y,x*,xk,xk+1,127,Newton法,算法：

（Newton法）,

（1）任取迭代初始值x0,

（2）对k=1,2,.,maxit，计算,判断收敛性，若收敛，则停止计算，输出近似解,128,收敛性,k=0,1,2,.,迭代函数,129,举例,例：

用Newton法求f（x）=x2C=0的正根,并验证这一方法的二阶收敛性,解：

对任意x00，总有|q|1，即牛顿法收敛,130,举例,二阶收敛,关于二次收敛性，事实上,