第一章 科学计算与数学建模绪论.docVIP

第一章 绪论 1.1 数学与科学计算 数学是科学之母，科学技术离不开数学，它通过建立数学模型与数学产生紧密联系，数学又以各种形式应用于科学技术各领域。数学擅长处理各种复杂的依赖关系，精细刻画量的变化以及可能性的评估。它可以帮助人们探讨原因、量化过程、控制风险、优化管理、合理预测。科学计算是指利用计算机来完成科学研究和工程技术中提出的数学问题的计算是一种使用计算机解释和预测实验中难以验证的、复杂现象的方法随着计算机技术的飞速发展科学计算在工程技术中发挥着愈来愈大的作用,已成为继科学实验和理论之后科学研究的第三种方法。1.2 数学建模及其重要意义 数学，作为一门研究现实世界数量关系和空间形式的科学，在它产生和发展的历史长河中，一直是和人们生活的实际需要密切相关。用数学方法解决工程实际和科学技术中的具体技术问题时，首先必须将具体问题抽象为数学问题，即建立起能描述并等价代替该实际问题的数学模型，然后将建立起的数学模型，利用数学理论和计算技术进行推演、论证和计算，得到1.3 数值方法与算法稳定性 数值计算已成为科学研究的第三种基本手段。所谓数值方法，是指将欲求解的数学模型（数学问题）简化成一系列算术运算和逻辑运算，以便在计算机上求出问题的数值解，并对算法的收敛性和误差进行分析、计算。这里所说的“算法”，不只是单纯的数学公式，而且是指由基本的运算和运算顺序的规定所组成的整个解题方案和步骤。一般可以通过框图（流程图）来直观地描述算法的全貌。 选定适合的算法是整个数值计算中非常重要的一环。例如，当计算多项式 的值时，若直接计算再逐项相加，共需做 次乘法和次加法。时需做55次乘法和10次加法。若用著名秦九韶（我国宋朝数学家）算法，将多项式改成 来计算时，只要做次乘法和次加法即可。 对于小型问题，计算速度的快慢和占用计算机内存的多寡似乎意义不大。但对于复杂的大型问题而言，却是起着决定性作用。算法取得不恰当，不仅影响到计算的速度和效率，还会由于计算机计算的近似性和误差的传播、积累直接影响到计算结果的精度，甚至直接影响到计算的成败。不合适的算法会导致计算误差达到不能容许的地步，而使计算最终失败，这就是算法的数值稳定性问题。 数值计算过程中会出现各种误差，它们可分为两大类：一类是由于算题者在工作中的粗心大意而产生的，例如笔误以及误用公式等，这类误差称为“过失误差”或“疏忽误差”。它完全是人为造成的，只要工作中仔细、谨慎，是完全可以避免的；而另一类为“非过失误差”，在数值计算中这往往是无法避免的，例如近似带来的误差、模型误差、观测误差、截断误差和舍入误差等。对于“非过失误差”，应该设法尽量降低其数值，尤其要控制住经多次运算后误差的积累，以确保计算结果的精度。 下面是一个简单的例算，可以看出近似值带来的误差和算法的选择对计算结果所产生的巨大影响。 例1.3.1计算 可用下面四种算式算出： ，，，。 如果不取近似，且计算过程没有误差，则上列四个算式的计算结果是相等的；但是如果分别用近似值和按上列四种算式计算值，其结果如表1.3.1所示。 表1.3.1 四个算式的计算结果 序号 算式 计算结果 1 2 3 4 由表1.3.1可见，按不同算式和近似值计算出的结果各不相同，有的甚至出现了负值，这真是差之毫厘，谬以千里。可见近似值和算法的选定对计算结果的精确度影响很大。因此，在研究算法的同时，还必须正确掌握误差的基本概念、误差在数值运算中的传播规律、误差分析的基本方法和算法的数值稳定性。否则，一个合理的算法也可能会得出一个错误的结果。 衡量一个算法的好坏时，计算时间的多少是非常重要的一个标志。由于实际的执行时间依赖于计算机的性能，因此所谓算法所花时间是用它执行的所有基本运算的总次数来衡量的。这样时间与运算的次数直接联系起来了。当然，即使用一个算法计算同一类型的问题时，由于各问题的数据不同，计算快慢也会不同，一般是用最坏情况下所花的时间来作讨论。设输入数据的规模是(在网络问题中，一般与节点数及弧数有关，而对一般极值问题，往往与变量数及约束数有关)。设在最坏情况下运算次数是，则称为算法的计算复杂性。 具有什么样的计算复杂性的算法被认为是好的呢？目前计算机科学中广为接受的观点是：多项式时间算法，即是关于的一个多项式，或者以一个多项式为上界的。例如，等是好的算法；而指数时间算法，即是关于的指数式或以一个指数式为下界的，例如等情况，则是坏的。这个看法的依据是很明白的，因为当增大时，指数函数比多项式函数增长快。 注意：在理论上证明是好的算法不一定在实际中有效，在理论上证明不是多项式时间的算法也不一定就在实际中效果不好。如关于线性规划问题的算法有如下的特殊性： （1）单纯形法是以时间复杂性为指数阶的，但却是非常