数值计算方法复习要点

1、.第一章 引论计算方法解决问题的主要思想计算方法的精髓：以直代曲、化繁为简1、采用“构造性”方法构造性方法是指具体地把问题的计算公式构造出来。这种方法不但证明了问题的存在性，而且有了具体的计算公式，就便于编制程序上机计算。2、采用“离散化”方法把连续变量问题转为求离散变量问题。例：把定积分离散成求和，把微分方程离散成差分方程。3、采用“递推化”方法将复杂的计算过程归结为简单过程的多次重复。由于递推算法便于编写程序，所以数值计算中常采用“递推化”方法。4、采用“近似代替”方法计算机运算必须在有限次停止，所以数值方法常表现为一个无穷过程的截断，把一个无限过程的数学问题，转化为满足一定误差要求的有限

2、步来近似替代。算法的可行性分析时间复杂度、空间复杂度分析算法的复杂性（包含时间复杂性和空间复杂性）。时间复杂度是算法耗费时间的度量。算法的空间复杂度是指算法需占用存储空间的量度算法的可靠性分析良态算法、病态算法一个算法若运算过程中舍入误差的积累对最后计算结果影响很大，则称该算法是不稳定的或病态算法，反之称为稳定算法或良态算法。误差的来源1、模型误差我们所建立的数学模型是对实际问题进行抽象简化而得到的。因而总是近似的，这就产生了误差。这种数学模型解与实际问题的解之间出现的误差，称为模型误差。2、观测误差观测到的数据与实际数据之差。3、截断误差数学模型的准确解与计算方法的准确解之间的误差。4、舍入

3、误差由于计算机字长有限，原始数据在计算机上表示会产生误差，每次计算又会产生新的误差，这种误差称为舍入误差。绝对误差、相对误差定义2 记x*为x的近似数，称E(x)=x-x*为近似数x*的绝对误差，|E(x)|为绝对误差限。定义3 称Er(x)=(x-x*)/x为近似数x*的相对误差。实际运算时也将Er*(x)=(x-x*)/x*称为近似数x*的相对误差。“四舍五入”：即尾数是4或以下则舍去，尾数是6或以上则进1，如果尾数是5，则规定：前面一位数字是偶数则舍去，奇数则进1。定义4 将近似数x*写为十进制形式若其中x*的最末一位数an是经过“四舍五入”得到的，即（最后一位是因为进1，实际上只进0.

4、5或舍去最多0.5。）则称近似数x*具有n位有效数字。近似数x*的有效数字位数n越大，则近似数的绝对误差限便越小，若近似数具有n位有效数字，则相对误差限为第二章 一元非线性代数方程的求解对半分法适用条件：假设函数f在a,b上连续(记为fCa,b)，f在区间端点异号，即f(a)*f(b)0。求解方法：1、将区间a,b分半，取中点(a+b)/2给x*，求f(x*)。若| f(x*) |1 ，则x*是f(x)=0的近似解，输出x* ，停止计算，否则作下一步。2、计算f(a)*f(x*)，若f(a)*f(x*)0，则b= x* ，否则a= x* ，形成一个有f(x)=0的解的新的区间，其长度比原区间少

5、一半。3、对新的含根区间重复上述步骤直到区间长度|a-b|2或| f(x*) |1 。一般迭代法如何得到迭代格式；将方程f(x)=0化为一个等价同解方程。例f(x)=(x)-x可化为x=(x)，且(x)是连续函数。因此求f的解变为求曲线y=(x)与直线y=x交点的横坐标。解曲线y=(x)与直线y=x交点的横坐标。给定一个初值x0(x的初始近似值)。由曲线y=(x)得xn+1=(xn)，n=0，1，2，。把初始值x0代入上式的右端得到x1 ，再将x1代入右端得到x2 ，如此重复，得到迭代数列xn ，其中xn+1=(xn) ，n=0，1，2，称为解方程f(x)=0的一个迭代格式，x0称为迭代初值。

6、如何判断是否压缩映射；收敛阶；压缩映射定理定理2 迭代收敛定理或压缩映射定理、不动点定理设迭代函数(x)在a,b上具有连续的一阶导数，且(1)当xa,b时，(x)a,b(2)存在正数L1，使对任意xa,b有|(x)| L1成立，则(1)方程x=(x)在a,b上有唯一不动点(根)x，且对任取初始近似值x0a,b ，迭代方法xn+1=(xn) (n=0,1,2, )产生的序列xn均收敛，且收敛于这个不动点x，即(2)误差估计式成立：(3)误差估计式成立：加速收敛的埃特金法迭代格式；收敛阶埃特金算法为平方收敛牛顿法迭代格式；收敛条件；收敛阶牛顿迭代格式的收敛阶是2，即平方收敛。弦截法双点弦截法；单点

7、弦截法；收敛条件；与牛顿法一样，当在根的领域内有直至二阶的连续导数且 时，弦截法具有局部收敛性收敛阶弦截法的收敛速度比牛顿法稍慢，但也是超线性收敛，其收敛阶为1.618。第三章 解线性代数方程组的直接法高斯消元法消元步骤：（这里只是简述，具体请参看ppt）第一步：消元过程，即把原方程组变为上三角方程组的过程第二步：把已求得的x回代到方程组的其他方程中，从而求得另外的x，此过程称为回代过程，从而得出方程组的解公式适用条件列主元消元法步骤矩阵的Lu分解法能否作Lu分解的定理（定理2、3）；Lu分解法解方程组第k步，在前k-1步已经求出了uij；i=1，2，k-1；j=1，2，n，lij； i=1，

8、2，n；j=1，2，k-1各元素。向量和矩阵的范数定义；对于向量：对于矩阵：常用范数第四章 解线性代数方程组的迭代法迭代的基本理论如何建立迭代格式；迭代矩阵；迭代收敛定理；谱半径矩阵B的特征值为1， 2， ，n，它们之中的绝对值最大者称为矩阵的谱半径，记为(B)。雅可比迭代迭代格式收敛定理高斯-赛德尔迭代迭代格式收敛定理定理5（收敛定理） 若A是严格对角占优矩阵，则对任意初始迭代向量x(0)，由高斯-塞德尔迭代法产生的向量序列x(k)收敛于方程组Ax=b的解x。超松弛迭代法上面就是超松弛迭代格式的推导第五章 插值方法引论基本定义；插值条件；截断误差代数插值的拉格朗日公式线性插值；抛物插值；一般

9、的拉格朗日插值法其截断误差分析：代数插值的埃特金公式计算公式差商的定义及递推公式代数插值的牛顿公式三次埃尔米特插值基本思想不但要求插值函数在各节点上与f(x)的函数值相同，而且还要求插值函数在某些节点或全部节点上与f(x)的导数值也相等，甚至要求高阶导数值也相等，这样的插值函数一定能更好地逼近函数f(x) ，我们称满足这类要求的插值问题为埃尔米特插值问题。即：三次样条插值基本思想（这个书本解释得很清楚，这里我就不打了，看书本的35页吧）第六章 在计算机上计算积分和导数中矩形、梯形和辛浦生公式公式；代数精度，各种关系式中矩形公式：梯形公式：辛浦生公式：代数精度各种关系式 复化求积公式各种关系式龙贝格积分方法外推算法；龙贝格公式（最好看看例题）高斯型求积公式的思路（这里的ppt好乱，还是要看看例题为妙）正交多项式在计算机上求导：显格式方法推导显格式方法求一阶导数 第七章 最小二乘法解矛盾方程组矛盾方程组的定义在实际问题中所归结出来的数学模型，往往是一个“没有解”的含n个未知数，m个方程的线性代数方程组，其中方程的个数m大大超过未知数的数目n，称这样的方程组为矛盾方程组。求解方法数据拟合的