数值计算方法总复习

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,二级,三级,四级,五级,*,*,数值计算方法,总复习,第一章,引言,截断误差、舍入误差,误差、误差限,有效数字,误差的传播,如,:,若将前若干项的部分和作为函数值的近似公式,由于以后各项都舍弃了,自然产生了误差。,Taylor,展开,截断误差,舍入误差,绝对误差、绝对误差限,工程上常记为,误差、误差限,例如,相对,误差、相对误差限,例,1,解,:,已知近似值为,:,精确值为,:,求,绝对误差、相对误差,绝对误差,相对误差,或,有效数字,用科学计数法，记,其中,若,则称,有,n,位有效数字，精确到,。,，,的截取按四舍五入规则,有,4,位有效数字,有,6,位有效数字,有,8,位有效数字,例,2,数据误差的传播,绝对误差,为：,相对误差,为：,称为,f,的条件数，其绝对值的大小可反映函数值对数据的敏感程度,误差的传播,利用上面的误差估计公式，可以得到两个数的,和、差、积、商的误差估计,误差的控制、算法的稳定性,第二章,非线性方程求根,基本概念,局部收敛、全局收敛,收敛阶,算法及其收敛性,二分法,简单迭代法,牛顿法及其简单变形,局部收敛与全局收敛,上面定理所涉及的收敛性，即在根邻域的收敛性称为,局部收敛性,，具有局部收敛性质的迭代法通常对初值的要求很高，使用起来不太方便。因而，人们通常希望迭代算法对相对大的范围的初始点具有收敛性，这种收敛性称为,全局收敛性,。,定义,2.2.1,设迭代过程,收敛于,的,根,.,如果迭代误差,满足下列关系,则称该迭代序列是,p,阶收敛的,(,时要求,),。,当,p,=1,时，称为线性收敛；,当,p,1,时，称为超线性收敛；,当,p,=2,时，称为平方收敛或二次收敛。,显然，,迭代序列的收敛阶越高，它的收敛速度就越快,。,收敛阶,补充,定理,算法的基本思想：,将区间对分，保留有根的区间，舍去无根的区间。如此往复，以逐步逼近方程的根。,基本条件：,二分法,算法的步骤,a x,0,b,a,1,b,1,此时有,误差估计,：,常用来估计,k,的值,算法的收敛性,用二分法求方程,在,1,1.5,内的实根,，,要求,解,即可推出所需的迭代次数满足,在区间,1,1.5,上至少存在一个根。,其具体过程如下：,例,由于,因而,由误差估计式,的符号,0,1.0000,1.5000,1.2500,-,1,1.2500,1.5000,1.375,+,2,1.2500,1.375,1.3125,-,3,1.3125,1.375,1.3438,+,4,1.3125,1.3438,1.3281,+,5,1.3125,1.3281,1.3203,-,6,1.3203,1.3281,1.3242,-,等价变换,原理：,简单迭代,迭代格式：,定理,2.2.1,收敛性：,压缩映像,保证迭代不中断,Lipschitz,条件,定理,2.2.1,的条件,(2),不容易得到,由微分中值定理：,推论,不难得到如下推论。,从而，有如下误差估计：,定理,在推论的条件下，有误差估计式,注,由于定理中条件,(1),一般难于验证，而且在大区间上，这些条件也不一定都成立。所以实际使用迭代法总是在根的邻近进行,。,表明收敛性与初值的选择有关！,定理,2.2.2,例,解,也可化为等价方程,.,但此时定理条件不成立，迭代序列不能保证收敛。,将,非线性方程线性化,，以线性方程的解逐步逼近非线性方程的解。,基本思想,Newton,迭代方法,迭代格式,Newton,迭代法的计算步骤,缺点：,对初值要求较高，,计算量较大,。,优点,：,收敛速度快，,精度高，,格式简单，应用广泛。,优点与缺点,局部收敛性,全局收敛性,定理,2.2.3,保证了根的存在性,函数单调，根惟一,函数图形的凸向不变,例,解,简化,Newton,法,迭代格式,进一步简化,收敛性与收敛速度,推广的简化,Newton,法只有,线性收敛速度,。,迭代格式,收敛性与收敛速度,迭代格式,收敛性与收敛速度,Newton,下山法,迭代格式,收敛性与收敛速度,弦割法,迭代格式,收敛性与收敛速度,单点弦割法,单点弦割法的局部收敛性,由简单迭代的一般收敛性理论可以推出：单点弦割法是,局部收敛,的且一般只有,线性收敛速度,。,单点弦割法的全局收敛性,定理,2.3.2,第三章,线性方程组的数值解法,基本概念,向量范数、矩阵范数、条件数,严格对角占优矩阵、对角占优矩阵、不可约矩阵,算法及其收敛性,高斯消元法,矩阵的三角分解及其应用,迭代法,-(1),-(2),-(3),-(4),显然,并且由于,例,求下列向量的各种常用范数,解,根据向量的常用范数可以得到常用的矩阵算子范数,-(10),-(11),-(12),证明见书,P70,例,求矩阵,A,的各种常用范数,解,由于,特征方程为,容易计算,计算较复杂,对矩阵元素的,变化比较敏感,不是从属范数,较少使用,(,理论上,),使用最广泛,性质较好,定义,3.3.5,-(13),矩阵的谱半径,显然，由定义可知,实特征值为绝对值，复特征值为模,定义,3.3.7,矩阵的条件数,矩阵,A,的条件数与所取范数有关。通常记,显然，当,A,对称时，,严格对角占优矩阵,对角占优矩阵,不可约矩阵,容易验证下面矩阵,按行（或列）都不严格对角占优，但它是不可约按行,（或列）对角占优的。,虽然不可约，但不按行（或列）对角占优。,而矩阵,Gauss,消元法,基本思想：,Gauss,消元法的运算量,数级,不必选主元的情况：,当系数矩阵,A,对称正定,或,严格对角占优,或,不可约对角占优,时，可不必选主元。,Gauss,消元法是不稳定的算法,，其中小主元是不稳定的根源。因而在,Gauss,消元法中要避免小主元的出现。这就需要采用,“,选主元,”,的技术。所谓,选主元,，简单地说就是,选取绝对值最大的元素作主元（全选主元或列选主元）,。,算法的稳定性：,矩阵的,LU,分解法,按上图逐框求出矩阵,A,的,LU,分解,紧凑格式法,。,上一页,下一页,返回,定理,若矩阵,A,非奇异,则,A,能分解为,LU,的充分必要条件是,A,的所有顺序主子式 均不为,0.,定理,若非奇异矩阵,A,有,LU,分解,则此分解是唯一的,.,定理,设,n,阶对称正定矩阵,A,，则存在唯一的单位下三角阵,L,及对角阵,D,使得 。,称为矩阵,A,的,乔累斯基分解,上一页,下一页,返回,定理,设矩阵,A,对称正定，则存在唯一的对角元为正的下三角阵,L,，使得 。,称为对称正定矩,阵,A,的,乔累斯基分解,利用,乔累斯基（,Cholesky,）分解,式来求解,Ax,=,b,的方法,也称,Cholesky,方法或,平方根法,例：利用系数矩阵的,LU,分解,求解方程组,解：,LU,分解的紧凑格式为,上一页,下一页,返回,迭代法的一般形式及其收敛性,迭代法,（一） 雅可比,(,Jacobi,),迭代法,几种古典迭代算法,建立迭代格式：,记,Jacobi,迭代的矩阵形式,易知，,Jacobi,迭代,有,（二） 逐次代换法（,Gauss,Seidel,迭代）,Gauss,Seidel,迭代的矩阵形式,（三）,逐次超松弛,迭代（,SOR,迭代）,SOR,迭代的矩阵形式,定理,3.4.1,（一） 收敛性判别定理,定理,3.14,一般迭代算法的收敛性,定理,3.4.2,Jacobi,迭代收敛！,Gauss-Seidel,迭代发散！,古典迭代法的收敛性,第四章,插值方法,基本概念,插值节点、插值多项式、插值基函数,差商及其性质,算法及其收敛性,Lagrange,插值,Newton,插值,分段线性插值,-(1),这就是,插值问题, (1),式为,插值条件,Lagrange,插值,就是选用节点上的函数值作为插值条件，,选用代数多项式作为插值函数。,Lagrange,插值,已知,n,+1,个互异插值节点,(,x,i,f,(,x,i,),i,= 0, 1, 2,n,。,插值基函数：,基函数仅与节点有关,而与被插函数无关！,容易验证，,L,n,(,x,i,) =,f,(,x,i,),i,= 0, 1, 2,n,.,n,次,Lagrange,插值多项式：,因此,n,次,Lagrange,插值多项式还可表示成,例,4.1.4,已知插值点,(,-,2.00,17.00), (0.00,1.00), (1.00,2.00), (2.00,17.00),求三次插值，并计算,f,(0.6),。,解,先计算,4,个节点上的基函数：,三次,Lagrange,插值多项式为：,f,(0.6) ,L,3,(0.6) = -0.472.,n,次插值多项式的误差,定理,4.1.3,设,L,n,(,x,),是,a,b,上过插值点,(,x,i,f,(,x,i,),i,= 0, 1, 2,n,的,n,次,Lagrange,插值多项式，节点,x,i,两两互异，,若,f,(,x,),C,n+,1,a,b,则,x,a,b,存在,=,(,x,),a,b,使得,Lagrange,插值的优缺点,优点：,形式整齐、规范，理论上保证插值的存在唯一性。,缺点：,计算量大，,重复计算多，,不具有承袭性。,Newton,插值,因此，每加一个节点时，只附加一项上去即可,。,有,再继续下去待定系数的形式将更复杂,一阶差商：,f,(,x,),关于点,x,0,，,x,1,的一阶差商记为,f,x,0,x,1,，,差商及其性质,二阶差商：,f,(,x,),关于点,x,0,，,x,1,，,x,2,的二阶差商记为,f,x,0,x,1,x,2,一般地，,k,阶差商,f,x,0,x,1,x,k,定义为：,性质,1,k,阶差商,f,x,0,x,1,x,k,可表成节点上函数值,f,(,x,0,),f,(,x,1,), ,f,(,x,k,),的线性组合，即,例如,，,k,= 2,时，,性质,2,各阶差商具有,对称性,即改变差商中节点的次序不会 改变差商的值。设,i,0,i,1, ,i,k,为,0, 1, ,k,的任一排列,则,由性质,1,知，任意改变节点的次序，只改变公式右端求和的,次序，故其值不变。例如,由定义知，,性质,3,若,f,(,x,),为,n,次多项式，则一阶差商,f,x,x,i,为,n,1,次,多项式。,由定义,性质,4,若,f,(,x,),在,a,b,存在,n +,1,阶导数，,x,i,a,b, ,i,= 0,1,n,固定,x,a,b,则,n+,1,阶,差商,与,导数,存在如下关系：,令,x,=,x,i,则分子为,0,说明分子中含有因子,x,x,i,与分母约去。,解,例,对,f,(,x,) =,x,7,x,4,+3,x,+1,，,求,f,2,0,2,1,，,f,x,2,0,2,1,2,6,和,f,x,2,0,2,1,2,7,。,利用差商与导数的关系（性质,4,）！,显然,，,f,(7),(,x,) = 7!,f,(8),(,x,) = 0,由性质,4,得,由差商的定义,一阶差商是由节点上函数值定义的，二阶差商是由一阶差商定义的，,，依此构造差商表：,i,x,i,f,(,x,i,),一阶差商 二阶差商,三阶差商, n,阶差商,0,x,0,f,(,x,0,),1,x,1,f,(,x,1,),f,x,0,x,1,2,x,2,f,(,x,2,),f,x,1,x,2,f,x,0,x,1,x,2,3,x,3,f,(,x,3,),f,x,2,x,3,f,x,1,x,2,x,3,f,x,0,x,1,x,2,x,3,n,x,n,f,(,x,n,),f,x,n,1,x,n,f,x,n,2,x,n,1,x,n,f,x,n,3,x,n, ,f,x,0,x,1, ,x,n,差商的计算,n,次,Newton,插值公式,插值误差为：,由插值的唯一性，,L,n,(,x,) =,N,n,(,x,),。因此，,Newton,插值是,Lagrange,插值的另一种表示形式。,他们的,误差也相同,，即当,f,(,x,),C,n,+1,a,b,时，有,故得差商的性质,4,例,给定四个插值点,(,2,17), (0,1), (1,2), (2,19),计算,N,2,(0.9),N,3,(0.9),。,解,首先列差商表,i,x,i,f,(,x,i,),f,x,i,1,x,i,f,x,i,2,x,i,1,x,i,f,x,i,3,x,i,2,x,i,1,x,i,0,2,17,1,0 1 -8,2,1 2 1 3,3,2 19 17 8 5/4,所以，,N,2,(0.9) = 17,8(0.9+2)+3(0.9+2)0.9 = 1.63;,N,3,(0.9) =,N,2,(0.9)+1.250.9(0.9+2)(0.9,1)= 1.30375.,差分及其性质,一般地，,m,阶差分,定义为,1.,线性性质，例如,差分的重要性质,2.,若,f,(,x,),是,m,次多项式，则,3.,差分值可由函数值算出，即,函数值可由差分值算出，即,由,R,n,(,x,),的表达式得,4.,各阶差分之间有如下关系,5.,差商和差分有如下关系,函数的差分可以列成如下向前差分、向后差分和中心差分表,向前差分、向后,差分表,中心差分表,等距节点,Newton,插值,1.,Newton,前插公式,Newton,前插公式,插值余项为,2.,Newton,后插公式,插值余项为,插值多项式与被插函数的逼近程度同分点的数目和位置有关。,一般地，分点越多，逼近程度越好，但也有例外。,例4.4.1,分段线性插值,不同次数的,Lagrange,插值多项式的比较图,Runge,现象：,插值多项式在插值区间上发生剧烈的震荡。它揭示了高次插值多项式存在的缺陷。,产生的原因：,误差由,截断误差,和,舍入误差,两部分组成，而在插值的计算过程中，舍入误差可能会扩散或放大。,n,越大，端点附近抖动越大,由于高次多项式插值很可能产生,Runge,现象，在多项式插值中一般不宜选取高次多项式。,分段线性插值,给定,N,+1,个插值点：,(,x,i,，,y,i,),，,i,= 0, 1, 2,N.,过这,N,+1,个点，可作折线函数,P(,x,)=I,N,(,x,)：,称之为函数,f(,x,),的,分段线性插值,。,分段线性插值函数也可以写成基函数的形式：,其中基函数,l,i,(,x,),为非负的且局部非零（称为局部支撑性）的分段线性函数：,可以看出，当节点加密时，分段线性插值函数与被插函数的函数值有很好的近似性。,例,已知函数,在区间,0,5,上取等距插值节点（如下表），求区间上分段线性插值函数，并利用它求出,近似值。,x,i,0,1,2,3,4,5,y,i,1,0.5,0.2,0.1,0.05882,0.03846,解,:,在每个分段区间,上，,于是，,实际值,:,当,n=7,时，,P,(4.5)=0.04762270321996,当,n=10,时，,P,(4.5)=0.04705882352941,由此可见，对于光滑性要求不高的插值问题，,分段线性插值的效果非常好！计算也简单,!,0.04705882352941,定理4.4.1,设函数,f,(,x,),C,a,b,，,则有如下收敛性：,定理4.4.2,设函数,f,(,x,),C,2,a,b,，,则,例,4.4.2,已知计算,f,(1.2),f,(3.3).,解,第五章,函数最佳逼近,基本概念,正规方程组,算法及其收敛性,离散最小二乘逼近,最佳平方逼近,一般最小二乘拟合多项式,对于离散数据,:,(,x,k,y,k,),k,=1,2,m,用,n (nm),次多项式来拟合曲线。设多项式,的系数是下述极小值问题的解：,一阶必要条件,：,直接计算易得,故,或,称为,正规方程组。,可表示为,例,5.1.4,用二次多项式函数拟合如下数据,:,x,i,-3,-2,-1,0,1,2,3,y,i,4,2,3,0,-1,-2,-5,解,设,p,(,x,) =,a,0,+,a,1,x,+,a,2,x,2,形成正规方程组：,m,=7.,约定 直接计算有：,方法一,一般地,，,为定义在,X,上的,广义多项式,，记为,定义残差的平方和：,最小二乘问题为：求解极小值问题,正规方程组便可化为：,将其表示成矩阵形式,例,5.1.6,用给定数据，求经验公式,f,(,x,) =,a,+,bx,3,. x =,-,3,-,2,-,1 2 4 y = 14.3 8.3 4.7 8.3 22.7,解,约定 直接计算得,法方程,于是法方程组为：,所求经验公式为：,f,(,x,) =10.675 + 0.137,x,3,.,函数的最佳平方逼近,上述问题等价于求多元函数,的最小值。,由多元函数取极值的必要条件,得,于是有,上述方程组称为,正规方程组,。也可以写为,例,5.2.1,解,取基函数为,建立正规方程组：,根据内积公式，可得,正规方程组为：,所求拟合函数为：,第六章,数值微积分,基本概念,代数精度,算法及其收敛性,Newton-Cotes,求积公式,复化梯形公式和复化辛普森公式,两点微分公式和三点微分公式,定义,设有近似式,则称该近似式具有,m,次的代数精度。,代数精度也称,代数精确度,代数精度,容易验证：梯形求积公式的代数精度为,1,，,Simpson,求积公式的代数精度为,3.,例,试确定下面积分公式中的参数使其代数精确度尽量高,.,解,因此,所以该积分公式,具有,3,次代数精确度,。,例,求以下微分公式的代数精度,解,故代数精度为,2.,对于一般的,n,阶插值型求积公式,由误差公式,可知，其代数精度至少为,n.,对于,Newton,Cotes,求积公式，我们有：,定理,定理,Newton-Cotes,求积公式,在微积分中，定积分是,Riemann,和的极限，即,数值积分,就是取定积分极限中的有限项的和，即,其中，,x,k,称为积分节点,A,k,称为积分系数。,我们的任务就是确定积分系数,A,k,使,I,f,I,n,f,.,最常用的方法,就是用插值多项式近似代替被积函数,f,(,x,),来确定,A,k,.,得,数值积分公式：,截断误差为：,（,1,）基本求积公式,Newton-Cotes,求积公式是指等距节点下使用,Lagrange,插值多项式建立的数值求积公式。,各节点为：,其中,而,因此有,令,n,阶,Newton-Cotes,求积公式,Newton-Cotes,公式的余项,(,误差,),即有,注意是等距节点,Newton-Cotes,求积公式可化为：,Cotes,系数,与积分区,间无关，,仅与,n,和,k,有关。,表,Cotes,系数,(,n,=1,2,8),下面列出两个低阶,Newton-Cotes,公式及其余项,Cotes,系数为：,求积公式为：,称为,梯形求积公式（,或,两点公式）,梯形求积公式及其余项,积分中值定理：,连续、,可积不变号,故,梯形公式的余项为：,几何意义：,直边梯形代替曲边梯形,Cotes,系数为：,求积公式为：,抛物线（,Simpson,）求积公式及其余项,上式称为,Simpson,求积公式,，也称,三点公式或抛物线公式,即,几何意义：,Simpson,公式的余项为：,例,解,复化梯形求积公式,将,a,b,分成,n,个小区间，在每个区间 上用梯形求积公式，再将,n,个小区间上的数值积分累加起来，就得到区间,a,b,上的数值积分。这种方法称为,复化梯形积分,。,根据梯形求积公式，有,将,n,个小区间上的积分累加起来，得,复化梯形求积公式,截断误差为：,收敛性：,复化梯形公式分解,复化,Simpson,求积公式,将,a,b,分成,2n,个小区间，在每两个相邻小区间,上用,Simpson,求积公式，再将这些小区间上的数值积分累加起来，就得到区间,a,b,上的数值积分。这种方法称为,复化,Simpson,积分,。,根据,Simpson,求积公式，有,将,2n,个小区间上的积分累加起来，得,复化,Simpson,求积公式,截断误差为：,收敛性：,复合,Simpson,公式分解,系数首尾为,1,，奇数点为,4,，偶数点为,2,例,计算 使计算结果有,5,位有效数字。,分别用复化梯形和复化,Simpson,求积公式，求分点,数。,解,由,复化梯形求积公式,得：,由复化,Simpson,求积公式得：,数值微分,x-h x x+h,B,C,A,T,f,(,x,),差商型求导公式,自然，而又简单的方法就是，取极限的近似值，即差商。,导数与差商的关系,x-h x x+h,B,C,A,T,f,(,x,),从截断误差的角度看，步长越小，计算结果越准确；从舍入误差的角度来看，步长不宜太小。下面将介绍具有较高精度的数值微分公式。,差商型求导公式的余项,插值型求导公式,由于采取的是,n,次,Lagrange,插值多项式，而高次插值会产生,Runge,现象，因此实际应用中多采用低次插值型求导公式。,（,1,）两点数值微分公式,(2),三点数值微分公式,同样，针对,m,也可扩展。,第七章,常微分方程数值解初步,欧拉折现公式及其变形,梯形公式,龙格,-,库塔格式,初值问题的,Euler,方法,初值问题的,Euler,方法,初值问题的,Euler,方法,初值问题的,Euler,方法,以上改进的欧拉格式还可以写为,称为龙格,-,库塔公式,