第一章 绪 论 本章以误差为主线，介绍了计算方法课程的特点，并概略描述了与算法相关的基本概 念，如收敛性、稳定性，其次给出了误差的度量方法以及误差的传播规律，最后，结合数值实验指出了算法设计时应注意的问题． §1.1 引 言 计算方法以科学与工程等领域所建立的数学模型为求解对象，目的是在有限的时间段内 利用有限的计算工具计算出模型的有效解答。 由于科学与工程问题的多样性和复杂性，所建立的数学模型也是各种各样的、复杂的. 复杂性表现在如下几个方面：求解系统的规模很大，多种因素之间的非线性耦合，海量的数据处理等等，这样就使得在其它课程中学到的分析求解方法因计算量庞大而不能得到计算结果，且更多的复杂数学模型没有分析求解方法． 这门课程则是针对从各种各样的数学模型中抽象出或转化出的典型问题，介绍有效的串行求解算法，它们包括 (1) 非线性方程的近似求解方法； (2) 线性代数方程组的求解方法； (3) 函数的插值近似和数据的拟合近似； (4) 积分和微分的近似计算方法； (5) 常微分方程初值问题的数值解法； (6) 优化问题的近似解法；等等 从如上内容可以看出，计算方法的显著特点之一是“近似”． 之所以要进行近似计算，这与我们使用的工具、追求的目标、以及参与计算的数据来源等因素有关． 计算机只能处理有限数据，只能区分、存储有限信息，而实数包含有无穷多个数据，这样，当把原始数据、中间数据、以及最终计算结果用机器数表示时就不可避免的引入了误差，称之为舍入误差． 我们需要在有限的时间段内得到运算结果，就需要将无穷的计算过程截断，从而产生截 断误差． 如 +++ =!21!111e 的计算是无穷过程，当用! 1 !21!111n e n ++++= 作为e 的近似时，则需要进行有限过程的计算，但产生了截断误差e e n -． 当用计算机计算n e 时，因为舍入误差的存在，我们也只能得到n e 的近似值* e ，也就是说最终用* e 近似e ，该近似值既包含有舍入误差，也包含有截断误差． 当参与计算的原始数据是从仪器中观测得来时，也不可避免得有观测误差． 由于这些误差的大量存在，我们得到的只能是近似结果，进而对这些结果的“可靠性”进行分析就是必须的，它成为计算方法的第二个显著特点． 可靠性分析包括原问题的适定性和算法的收敛性、稳定性． 所谓适定性问题是指解存在、惟一，且解对原始数据具有连续依赖性的问题． 对于非适定问题的求解，通常需要作特殊的预处理，然后才能做数值计算． 在这里，如无特殊说明，都是对适定的问题进行求解． 对于给定的算法，若有限步内得不到精确解，则需研究其收敛性． 收敛性是研究当允许计算时间越来越长时，是否能够得到越来越可靠的结果，也就是研究截断误差是否能够趋于零．
数值分析 1. 数值分析的病态性是指因初始数据的微小变化，导致计算结果的剧烈变化。 病态问题：因初始数据微小变化，导致计算结果剧烈变化的问题 良态问题：初始数据微小变化，只引起计算结果微小变化的计算问题。 数值不稳定算法：指算法进行计算的初始数据有误差，而计算过程中产生的舍入误差不断增长。例子 2. 误差的来源：①模型误差：在数学建模时，由于忽略了某些次要因素而产生的误差；②观测误差：在采集原始数 据时，由仪器的精度或其他客观因素产生的误差；③截断误差：对产与计算的数学公式做简化处理后所产生的误差；④舍入误差：计算机因数系不全，由接受和运算数据的舍入引起的误差。 科学计算中值得注意的地方：①避免两个相近的数相减；②合理安排量级相差很大的数之间的运算次序，防止大数吃小数；③避免绝对值很小的数做分母；④简化运算步骤，减少运算次数。 3. 用计算机做科学计算时的溢出错误。 机器数系是有限的离散集，机器数系中有绝对值最大和最小的非零数M 和m ，若一个非零实数的绝对值大于M ，则计算机产生上溢错误，若其绝对值小于m ，则计算机产生下溢错误。上溢错误时，计算机中断程序处理；下溢错误时，计算机将此数用零表示并继续执行程序。 4. 解非线性方程f x () =0单根的牛顿法具有二阶收敛。简单迭代法具有一阶收敛性。当f ' x * ()10且有2阶导数时， Newton 迭代法才有二阶敛速。 5. 对(n+1)个节点的Newton-cotes 求积公式，在n ￡7时，Cotes 系数大于0，而在n >7时，考虑到公式的稳定性不实用该公式。 6. 当系数矩阵A 是严格对角占优矩阵，Jacobi 格式、Seidel 格式都收敛。 7. 用高斯消元法求解线性方程组，一般使用选主元的技术是因为要减少舍入误差。 8. 解非线性方程组迭代法的整体收敛和局部收敛的主要区别是局部收敛在较小邻域内取初值，有初值限制。 9. 二分法是全部收敛，简单迭代法是局部收敛。 10. 四种插值方法：Lagrange 插值、Newton 插值、Hermite 插值、分段多项式插值。 11. 截断误差是对参与计算的数学公式作简化处理后所产生的误差，在所学的数值方法中插值和数值积分都涉及截断误差处理的内容，分别为插值余项和积分余项。 例：e x =1+x +x 2 2! + +x n n!+无穷项相加，我们用e x =1+x +x 2 2! + +x n n! 近似计算e x 就产生截断误差。 12. 线性方程组迭代解法的基本思想是将现行方程组作等价变形，得到同解的易于作迭代计算的线性方程组，用计算出的迭代序列来逼近解。考虑线性方程组Ax =b 及由次方程组构造的迭代格式x k +1() =Bx k ()+g ，判断此迭代格 式的收敛方法有： (1) 若r B () <1，则迭代格式收敛； (2)若B <1，则迭代格式收敛，B 是矩阵B 的某种算子范数； (3) 若矩阵A 是严格对角占优矩阵，则线性方程组Ax =b 的Jacobi 迭代和Seidel 迭代对任意初值都收敛； (4)若矩阵A 是对称正定矩阵，则线性方程组Ax =b 的Seidel 迭代对任意初值都收敛； (5) Sor 法收敛的必要条件是松弛因子w 满足0