《计算方法》定理公式总结归纳

第一章1.设某量的准确值为x，近似值为x*，则称e(x*)=x-x*为近似值x*的绝对误差；|e(x*)|=|x-x*|≤ε,称ε为x*的绝对误差限；称为x*的相对误差；εr为x*的相对误差限。2.对数学问题而言，如果输入数据有微小扰动，引起输出数据（即数学问题的解）有很大扰动，则称数学问题是病态问题，否则称为良态问题。3.4.定义：一个算法如果输入数据有扰动（即有误差），而计算过程中舍入误差不增长，则称此算法是数值稳定的，否则称此算法为不稳定的。（误差的定性分析法：即研究算法的数值稳定性）5.数值计算中值得注意的问题：（1）防止相近的两数相减(2)防止大数吃小数(3)防止接近零的数做除数(4)注意计算步骤的简化,减小运算次数6.误差的来源：1、模型误差2、观测误差3、截断误差4、舍入误差实际问题的真解与数学模型之间有误差，这种误差称为模型误差(描述误差)由于测量工具的精度、观测方法或客观条件的限制,使数据含有测量误差,这类误差叫做观测误差或数据误差在数值求解数学问题时，常常用有限过程逼近无限过程，用能计算的问题代替不能计算的问题。这种精确公式用近似公式代替时,所产生的误差叫截断误差。由于计算机字长有限，一般实数不能精确存储，于是产生舍入误差。第二章6.如果在区间[a,b]内方程f(x)=0只有一个根，称[a,b]为隔根区间。求隔根区间有两种方法有描图法和逐步搜索法。7.二分法就是将方程的有根区间对分，然后再选择比原来区间缩小一半的有根区间，如此继续下去，直到得到满足精度要求的根为止的一种简单的区间方法。定理2.1：f(x)在[a,b]内连续，α是方程f(x)在隔根区间[a,b]内的根，则由二分法产生的数列{xn}收敛于方程的根α,且有误差估计式二分法控制误差ε常用的方法有(1)先计算对分次数再对分。由计算得得到满足误差要求的最少对分次数。(2)事后误差估计法,先对分再判断所得中点是否满足误差要求(3)由于故可用来判断误差。8.迭代法的求解步骤(1)建立迭代公式。由公式f(x)=0出发将其分解为等价形式x=φ(x),式中φ(x)叫做方程的迭代函数.(2)进行迭代计算。由初值x0出发，按迭代函数进行计算称为迭代公式。数列{xn},称为迭代序列。该过程称为迭代过程.9若从任何可取的初值出发都能保证收敛，则称它为大范围收敛。如若为了保证收敛性必须选取初值充分接近于所要求的根，则称它为局部收敛。定理2.2（收敛定理）：设方程x=φ(x)，如果设方程x=φ(x)，如果(1)迭代函数φ(x)在区间[a,b]可导；(2)当xÎ[a,b]时，φ(x)Î[a,b]；(3)对于任意的xÎ[a,b]，有。则有=1\*GB3①方程x=φ(x)在区间[a,b]上有唯一的根α；=2\*GB3②对于任意的初值x0Î[a,b]，由迭代公式产生的数列{xn}收敛于方程的根α。=3\*GB3③=4\*GB3④误差估计定理2.3（迭代法的局部收敛定理）：设α是方程x=φ(x)的根，如果(1)迭代函数φ(x)在α的邻域可导；(2)在α的某个邻域S={x:|x-α|≤δ},对于任意的xÎS有则对于任意的初值x0ÎS，迭代公式xn+1=φ(xn)产生的数列{xn}，收敛于方程的根α。（这时称α的S领域具有局部收敛性。）收敛法控制误差ε的方法有：(1)先计算满足误差要求的迭代次数n，再迭代。由可得(2)事后误差估计法。由于因而可用|xn-xn-1|≤ε来控制迭代过程。10.迭代-加速公式：埃特金加速公式:定理2.4：如果由迭代公式xn+1=φ(xn)产生的数列{xn}满足(1)收敛于根α；(2)则由埃特金加速公式产生的数列{xn}比数列较快地收敛于根α，即11.牛顿迭代公式：定理2.5（牛顿迭代法的局部收敛定理）设α是方程f(x)=0的根，如果(1)函数f(x)=0在α的邻域有连续的二阶导数(2)在α的邻域f’(x)≠0则存在α的某个邻域，对于任意的初始值，由牛顿迭代公式产生的数列收敛于根α。定理2.6（牛顿迭代法收敛定理）设α是方程f(x)=0在隔根区间[a,b]内的根，且满足,连续且不变号；(2)选取初始值使。则由牛顿迭代公式产生的数列收敛于根α。12.定义:设数列收敛于α,令误差,如果存在某个实数及正常数C，使则称数列p阶收敛，也称相应的迭代法为p阶方法。当且时，称数列为线性收敛.当p=2时，称数列平方收敛（或二阶收敛）.当p>1时，称数列为超线性收敛。定理2.7:（1）在定理2.3的条件下，且在根α的某个邻域内有，则迭代法是线性收敛的。（2）在定理2.6的条件下，牛顿迭代法是平方收敛的。13.单点弦截法迭代公式:；双点弦截法迭代公式：定理2.8:设α是方程f(x)=0在隔根区间[a,b]内的根，且满足(1)连续且不变号；(2)选取初始值，使。选定a，b中的一个，则x1为另一个。则有单点弦截迭代法公式产生的数列收敛于根α。（单点弦截法的收敛阶为1）。定理2.9:设方程f(x)=0，如果(1)f(x)在根α的某个邻域具有连续的二阶导数，且f’(x)≠0;(2)任取x0,x1属于该邻域。则由双点弦截迭代法公式产生的数列收敛于根α。（双点弦截法是超线性收敛，收敛阶为(1+5第三章14.高斯消元法的求解过程可大致分为两个阶段:(1)把原方程组化为上三角形方程组,称之为“消元”过程;(2)用逆次序逐一求出上三角方程组(原方程组的等价方程组)的解,称之为“回代”过程.15.定义3.1:设A为n阶矩阵，L为n阶下三角阵，U为n阶上三角阵。如果A=LU，则说明矩阵A实行了三角分解或LU分解。16.定义3.2:如果L为单位下三角阵，U为上三角阵，则称该三角分解为杜里特（Doolittle）分解；如果L为下三角阵，U为单位上三角阵，则称A=LU为克劳特（Crout）分解。定理3.1：n阶（n≥2）矩阵A有唯一杜里特分解（或克劳特分解）的充要条件是A的前n-1个顺序主子式都不为零。定理3.2:设A为对称正定矩阵，则有非奇异下三角阵L，使A=LLT;当限定L的对角元全为正时，这种分解是唯一的。17.直接三角分解法公式（Doolittle）：18.平方根法求解公式：19.追赶法的分解形式及公式：20.定义3.3设迭代矩阵B为n阶矩阵，为矩阵B的特征值，称为矩阵B的谱半径。定理3.3：设简单迭代公式为对于任意的初始向量和g，该简单迭代法都收敛的充要条件是：定理3.4：设简单迭代公式为如果或，则简单迭代法对任意初始向量和g都收敛。21.定义3.4设，如果矩阵A满足条件或者即A的每一行（列）对角线上的元素的绝对值都严格大于同行（列）其它元素绝对值之和，则称A为严格对角占优矩阵。定理3.5：如果线性方程组的系数矩阵A是严格对角占优矩阵，则雅克比迭代法对任意的初始向量和g都收敛。定理3.6：设有赛德尔迭代公式记矩阵。如果或，则简单迭代法对任意初始向量和g都收敛。22.定义：设V是数域F上的线性空间，，若存在唯一实数与其对应，且满足以下三条公理，(1)正定性：(2)齐次性：(3)三角不等式：则实数称为向量x的范数。把定义了范数的线性空间称为赋范线性空间。23.（1）向量的1-范数：;(2)向量的2-范数：;(3)向量的∞范数：。均可表示为p范数的形式：。（定理：有限维空间中的范数等价。）24.定义：设向量序列，若存在，使得称向量序列收敛于25.定义：基本迭代法产生的迭代序列，如果对任取初始向量都有，则称此迭代法是收敛的，否则是发散的。（在Rn中，点列的收敛等价于每个分量的收敛。即。）26.迭代终止标准：(1)绝对误差标准。给出容许误差界ε，当时,p=1,2,∞,终止迭代，解取为。常取p=∞，(2)相对误差标准。给出容许误差界ε，(3)给出最大迭代次数，当迭代终止，给出失败信息。特征值上界定理：设A∈Rn×n,对于定理：如果迭代格式的迭代矩阵B满足，则有以下的误差估计式：，27.估计迭代次数的方法：28.Jacobi迭代的矩阵格式：；分量形式：29.Gauss-Seidel迭代的矩阵形式：；分量形式：30.收敛准则：一般收敛原则:，实用准则：由A来直接判断（充分准则）{准则1：A严格对角占优Jacobi迭代法，Gauss-Seidel迭代法收敛；准则2：Jacobi迭代法，Gauss-Seidel迭代法收敛。准则3：A对称正定Gauss-Seidel迭代法收敛；准则4：若A对称正定，则2D-A是对称正定Jacobi迭代法收敛。}注意：对一个任意给定的系数矩阵1.Jacobi迭代法和Gaussss-Seidel迭代法可能同时收敛，或同时不收敛，或者一个收敛而另一个不收敛。2在都收敛的情况下，其收敛的速度也不一定是哪一种一定快。3.A对称正定，Gauss-Seidel一定收敛，但2D-A不一定也是对称正定，所以Jacobi法未必收敛。31.SOR迭代的矩阵形式分量形式：w=1，为Gauss-seidel迭代法；w>1，超松弛迭代法；w<1低松弛迭代法。32.SOR迭代收敛准则{一般准则：，实用准则：用w加速，收敛性于w直接有关。定理：SOR方法收敛的必要条件是0<w<2。}33.SOR法收敛性的结论：(1)SOR方法收敛的必要条件是0<w<2;(2)若系数阵A对称正定，则当0<w<2时，SOR方法收敛;(3)若系数阵A严格对角占优，则当0<w≤时，SOR方法收敛。第五章定理5.1：在n+1个互异节点处满足插值条件的次数不高于n的多项式存在且唯一。33.定义5.1：若n次多项式在n+1个插值节点上满足插值条件：则称这n+1个n次多项式为插值节点上的n次插值基函数。34.插值基函数的性质：性质一：；性质二：是由插值节点唯一确定的n次函数；性质三：插值基函数与插值节点个数相同。35．Language插值：定理5.2：若f(n)(x)在区间[a,b]上连续，f(n+1)(x)在(a,b)存在，Ln(x)为在节点a£x0<x1<……<xn£b上满足插值条件的插值多项式，则对于任意的xÎ(a,b),其插值余项为其中。36.定义5.2：给定函数f(x)在互异节点x0<x1<……<xn处的函数值分别f(x0),f(x1),……,f(xn),称为在处的一阶差商。称为在处的二阶差商。一般地，称为在上的k阶差商。即的k-1阶差商的差商称为k阶差商（差商也常称为均差）。37.差商的性质：1.2.差商与插值节点的排列顺序无关，即，一般地，在k阶差商中，任意调换节点的次序，其值不变。3.差商与导数的关系：38.差商表：39．牛顿插值：40.定义5.3：设，为等距节点上的函数值，其中称为步长，则称为在处以h为步长的一阶向前差分。称为在处以h为步长的二阶向前差分。一般地，称为在处以h为步长的m阶向前差分。41.差分的性质：性质1：各阶差分可用函数值线性表示，其计算公式为：其中：；性质2：差分与差商满足下述关系；性质3:差分与导数满足关系：。42.等距节点插值：43.埃尔米特插值：定理5.3：若在上存在2n+2阶导数，则其插值余项，式中44.定义5.4：设在区间上取n+1个节点若函数S(x)满足(1)在整个区间上具有二阶连续导数；(2)在每个小区间上是x的三次多项式；(3)。则称为的三次样条插值函数。45.用节点处一阶导数表示的三次样条插值函数的构造步骤：用公式计算出。由公式：，以及第一类边界条件：或第二类边界条件：计算出。计算公式如下：（第一类边界条件）或（第二类边界条件）最后将代入，。46.用节点处二阶导数表示的三次样条插值函数的构造步骤：用公式计算出。由公式：以及第一类边界条件：或第二类边界条件：计算出。计算公式如下：（第一类边界条件）或（第二类边界条件）最后将代入，。第六章47.定义：当线性方程组的系数矩阵的秩与增广矩阵的秩不等时，方程组无解，这时次方程组称为矛盾方程组。称为偏差。定理6.1：设n元实函数在点的某个邻域内连续，且有一阶二阶连续的偏导数，如果(1)(2)矩阵是正（负）定矩阵，则是n元实函数的极小（大）值。定理6.2：设非齐次线性方程组的系数矩阵，若，则：(1)矩阵是对称正定矩阵；(2)n阶线性方程组有唯一的解。定理6.3：设矛盾方程组的系数矩阵A的秩为n，则二次函数一定存在最小值。48.定义：线性方程组称为正则方程组。定理6.4：设互异，且，则正则方程组有唯一的解。49.通常用均方差与最大偏差来判断拟合曲线的优劣。第七章50.定义：在积分区间上取一系列的点，设，用被积函数在这些点上的函数值的线性组合来作为积分的近似值：，此式称为数值求积公式，其中的个点称为节点，称为求积系数。称为求积公式的截断误差。51．牛顿科-特斯求积公式：，称为科特斯系数。称为牛顿-科特斯公式的截断误差。52.梯形公式（n=1）：53.辛浦生公式（n=2）：54.科特斯公式（n=4）：55.科特斯系数表：k=0K=1K=2K=3K=4n=11/21/2n=21/64/61/6n=31/83/83/81/8n=47/9032/9012/9032/907/9056.定义7.1：如果求积公式对于任何不高于m次的代数多项式都准确成立（即），而对某个m+1次的代数多项式不准确成立（即）,则称该求积公式具有m次代数精确度，简称代数精度。定理：n为偶数的牛顿-科特斯求积公式具有n+1次代数精度，n为奇数的牛顿-科特斯求积公式具有n次代数精度。定理7.1：设在区间上具有连续的二阶导数，则梯形公式的截断误差为：。定理7.2:设在区间上具有连续的四阶导数，则辛浦生公式的截断误差为：。57.科特斯公式的截断误差为：58.待定系数法：给定n+1个节点，如果要构造至少具有n次代数精度的求积公式，只要对于都准确成立，则可得到含求积系数的代数方程组：方程组的系数行列式是范德蒙行列式，其值不为零，因而可求得唯一解。59.复化求积公式的基本思想：把积分区间分成若干小区间，在每个小区间上采用次数不高的插值公式，如梯形公式或抛物线公式，构造出相应的求积公式，然后再把它们加起来得到整个区间上的求积公式。复化求积公式克服了高次Newton-Cotes公式计算不稳定的问题，其运算简单且易于在计算机上实现。常用的复化求积公式是复化梯形公式和复化抛物线公式。60.复化梯形公式：61.复化辛浦生公式：式中62.复化科特斯公式：式中定理7.3：设在区间上具有连续的二阶导数，则复化梯形公式的截断误差为：。（若，则有误差估计式：。）63.复化辛浦生公式的截断误差：，若则有误差估计式：。64.复化柯特斯公式的截断误差：，若，则有误差估计式：。65.区间逐次半分求积法：(1)对于梯形公式：假定在区间上变化不大，则有。递推公式为：(2)对于辛浦生公式，假定在区间上变化不大，则有。(3)对于科特斯公式，假定在区间变化不大，则有66.外推法的几个公式：，67.龙贝格求积公式：68.结论：由梯形序列外推得到辛浦生序列、由辛浦生序列外推得到科特斯序列以及由科特斯序列外推得到龙贝格序列，每次外推都可以使误差阶提高二阶。69.龙贝格求积算法的计算步骤：(1)算出，，根据公式计算；(2)将分半，算出后，根据公式计算，再根据公式计算；(3)再将区间对分，算出以及，并根据和算出，再由公式计算；(4)将区间再次分半，计算，并由公式计算；(5)将区间再次分半，类似上述过程计算。重复上述过程可计算得到一直算到龙贝格序列中前后两项之差的绝对值不超过给定的误差限为止。70.定义7.2：把具有个节点的具有次代数精确度的插值型求积公式称为高斯型求积公式，节点称为高斯点，称为高斯系数。定理7.4：对于插值型求积公式，其节点为高斯点的充要条件是以这些点为零点的多项式与任意的次数不超过n的多项式在区间上正交，即。71.n次勒让德多项式：其性质有：(1)次勒让德多项式与任意的次数不超过次的多项式在区间上正交；(2)次勒让德多项式的个零点都在区间内。72.结论：当积分区间为时，插值型求积公式的代数精确度为的充要条件是与任意次数不超过的多项式在区间上正交。73.高斯-勒让德求积公式：（为次勒让德多项式的零点。求积系数可用待定系数法或按求出：）74.对于积分，可通过变量代换将积分转化为上的积分，，然后用高斯