计算方法总结

第一章：基本概念1.若，称准确到n位小数，及其以前的非零数字称为准确数字。各位数字都准确的近似数称为有效数，各位准确数字称为有效数字。2.进制：，字长：，阶码：，可表示的总数：3.计算机数字表达式误差来源实数到浮点数的转换，十进制到二进制的转换，结算结果溢出，大数吃小数。4.数据误差影响的估计：，小条件数。解接近于零的都是病态问题，避免相近数相减。避免小除数大乘数。5.算法的稳定性若一个算法在计算过程中舍入误差能得到控制，或者舍入误差的积累不影响产生可靠的计算结果，称算法数值稳定。第二章：解线性代数方程组的直接法1.高斯消去法步骤：消元过程与回代过程。顺利进行的条件：系数矩阵A不为零；A是对称正定矩阵，A是严格对角占优矩阵。2.列主元高斯消去法失真：小主元出现，出现小除数，转化为大系数，引起较大误差。解决：在消去过程的第K步，交换主元。还有行主元法，全主元法。3.三角分解法杜立特尔分解即LU分解。用于解方程；用于求。克罗特分解：，下三角阵和单位上三角阵的乘积。将杜立特尔分解或克罗特分解应用于三对角方程，即为追赶法。对称正定矩阵的乔列斯基分解，，下三角阵及其转置矩阵的乘积；用于求解的平方根法。改进平方根法：利用矩阵的分解。4.舍入误差对解的影响向量范数定义：常用的向量范数：矩阵的范数：常用的矩阵范数：矩阵范数与向量范数的相容性：影响：，其中，k值大，病态问题。第三章：插值法1.定义给定n+1个互不相同的点，xi及在xi处的函数值yi(i=0～n)，构造一个次数不超过n次的多项式：，使满足。取。称为插值多项式，为插值节点，为被插函数。插值问题具有唯一性。2.Lagrange插值多项式表达式：误差估计式：3.Newton插值多项式差商：表达式：误差表达式：差商的性质：1)差商与节点的次序无关；2)K阶差商对应K阶导数；3)4)5)4.埃尔米特（带导数）插值多项式1)Newton法，给定f及f(k)为数字；2)Lagrange法，给定f及f(k)为表达式。5.三次样条插值函数分段三次插值多项式的定义：S(x)在子区间[xi-1,xi]上是三次多项式，S(xi)=yi，s’’(x)在[a,b]上连续。三次样条插值函数的导出：第四章：函数最优逼近法1.最优平方逼近对于广义多项式：，其中线性无关。要求：若f(x)是表格函数，确定P(x)称为最小二乘拟合函数，当，P(x)为最小二乘多项式；若f(x)是连续函数，称P(x)为最优平方逼近函数。2.函数的内积，范数定义及其性质内积的定义：性质：范数的定义：范数的性质：正规方程组或法方程组：3.正交多项式正交函数系的定义：代入正规方程组的系数矩阵，则：几个正交多项式举例：勒让德多项式拉盖尔多项式埃尔米特多项式切比雪夫多项式四种正交多项式均可用于高斯型求积公式；P多项式用于最优平方逼近，T多项式用于最优一致逼近。正交多项式的性质：正交多项式线性无关，推论：与正交。在区间[a,b]或[min(xi),max(xi)]上，n次正交多项式gn(x)有n个不同的零点。设是最高次项系数为1的正交多项式，则：4.最优一致逼近法(1)切比雪夫多项式的性质性质1：是[-1,1]上关于的正交多项式，；性质2：；性质3：是最高次项为的k次多项式，只含x的偶次项，只含x的奇次项；性质4：有k个不同的零点，；性质5：在[-1,1]上，，且在k+1个极值点处依次取得最大值1和-1；性质6：设Pn(x)是任意一个最高次项系数为1的n次多项式，则：

(2)最优一致逼近法的定义设函数f(x)在区间[a,b]连续，若n次多项式使达到最小，则称为在[a,b]上的最优一致逼近函数。切比雪夫定理：n次多项式P(x)成为函数y=f(x)在区间[a,b]上最优一致逼近多项式的充要条件是误差在区间[a,b]上以正负或负正交替的符号依次取得的点（偏差点）的个数不少于n+2。采用如下方程组进行求解：(3)近似最优一致逼近多项式思路：使用T多项式性质6若区间是[-1,1]，取xi(i=0～n)为Tn+1的零点，则～，以此构造插值多项式Pn(x)；若区间是[a,b]，通过转换；方法1：由～，构造Pn(t)，然后将代入Pn(t)，可得Pn(x)。方法2：取，i=0～n；构造Pn(x)。例：(4)截断切比雪夫级数法设f(x)在[-1,1]上连续，，其中；记；应用切比雪夫定理及性质5，取。(5)缩短幂级数法方法1：方法2：第五章：数值微积分第一节牛顿柯特斯公式一．数值算法1.数值积分算法对于复杂函数f(x)，考虑用其近似函数P(x)去逼近，用P(x)的积分值近似代替f(x)积分值。2.插值型数值积分方法对于拉格朗日插值多项式，广义积分中值定理：若f(x)在[a,b]上连续，g(x)在[a,b]上部变号，则，使3.牛顿柯特斯公式梯形公式：辛普森公式：二．复化求积公式1.，把[a,b]分成若干等长的小区间，在每个小区间用简单低次数值积分公式，在将其得到的结果相加。2.复化梯形公式3.复化辛普森公式三．变步长的积分公式1.先取一步长h进行计算，再取较小步长h*计算，若两次结果相差很大，则在取更小步长进行计算，依次进行，直到相邻两次计算结果相差很大，则取较小步长的结果为积分近似值。2.变步长复化梯形公式3.变步长复化辛普森公式四．龙贝格积分法第二节待定系数法1.代数精度定义对于近似公式，如果f(x)是任意不超过m次的多项式，成立，而对于某个m+1多项式，，称代数精度为m次。2.判定方法近似式的代数精度为m次对，近似式精确成立，，时不成立，。梯形公式m=1，辛普森公式m=3。3.Peano定理第三节高斯型积分公式一．定义节点个数一定，具有最高阶代数精度公式的插值型积分公式称为Guass型求积公式。插值型积分公式定义：定理：数值积分公式至少有n次代数精度近似式是插值型积分公式。对于牛顿科特斯公式，若采用等距节点，n分别为奇数和偶数时，代数精度分别为n和n+1。二．最高代数精度定理：So，给定n+1个节点，具有2n+1次代数精度的插值型数值积分公式称为Gauss型求积公式。三．Gauss型积分公式的构造方法方法1：代数精度为2n+1，则时成立，可解出和。方法2：定理：代数精度是[a,b]上关于的正交多项式的零点(高斯点)，其中。四．高斯型求积公式的误差五．常用的高斯型求积公式1.Gauss-Legendre求积公式 ，是的n+1个零点。n=0n=12.Gauss-Laguerre求积公式3.Gauss-Hermite求积公式4.Gauss-Chebyshev求积公式第四节数值微分，h大，不精确，h小，由于小除数引入大误差。近似函数法取等节距节点，(1)一阶导数，n=1，两个节点(2)一阶导数，n=2，三个节点(3)二阶导数，n=2，三个节点实用误差估计例：第六章非线性方程的迭代解法第一节方程求根法根的定义：对于非线性方程组f(x)=0，若存在数使f()=0，称是非线性方程组f(x)=0的根。零点存在定理：若f(x)是闭区间[a,b]上的连续函数，若f(a)f(b)<0，则必然存在，使f()=0。试探法，二分法。一．简单迭代法初值，，产生迭代序列。简单迭代收敛定理（压缩映像原理）对于迭代函数，若满足(1)若；(2)存在正数0<L<1，使，都有。则对任意初值的迭代序列，，收敛于方程的唯一根。局部收敛性：当，若有且连续收敛误差：收敛速度(收敛阶)：若存在实数P和非零常数C，使得，称迭代序列是P阶收敛。P=1，线性收敛；P>1，超线性收敛；P=2，平方收敛。定理：设是方程的根，如果迭代函数满足产生的迭代序列是P阶收敛。二．牛顿迭代法收敛性分析：牛顿迭代法具有局部收敛性，初值，产生迭代序列收敛。收敛定理：设f(x)在[a,b]上二阶导数存在，若，在[a,b]上单调，在[a,b]上凹向不变（即在区间上不变号），初值满足，则任意初值，有牛顿迭代法产生的收敛于方程的唯一根。简化牛顿法：三．弦割法或割线法用差商代替导数第二节线性代数方程组迭代解法Jacobi迭代法，Gauss-Seidel迭代法SOR迭代法（）迭代法的收敛性：将迭代法用矩阵表示：，Jacobi迭代法：G-S迭代法：SOR迭代法：定理：，对产生的迭代序列收敛的充要条件是：或。推论1：若，则收敛；推论2：SOR方法收敛的必要条件是；推论3：设A是严格对角占优矩阵，则Jacobi，G-S，的SOR方法收敛；推论4：1)设A是对称正定矩阵，则G-S方法收敛；2)设A是对称正定矩阵，若2D-A也对称正定，则Jacobi方法收敛；若2D-A不对称正定，则Jacobi方法不收敛；3)设A是对称正定矩阵，，则SOR方法收敛。