计算方法简明教程

　　《计算方法简明教程》力图改革计算方法课程的教学体系。新的体系立足于数学思维而面向科学计算的实际需要，内容处理上突出数值算法的基本设计技术。《计算方法简明教程》分上、下两篇：上篇“计算方法讲义”运用算法设计技术设计了科学计算中的一些常用算法，下篇“高效算法讲座”着重推荐高效算法设计的二分技术。计算机科学在某种意义上就是算法学。数学思维的化归策略贯穿于数值算法设计的全过程。数值算法设计的基本技术包括化大为小的缩减技术，化难为易的校正技术以及化粗为精的松弛技术等。《计算方法简明教程》上篇基于这些技术设计并剖析了一些常用的数值算法，其内容涵盖插值方法、数值积分与数值微分、常微分方程的数值解法、方程求根以及线性方程的解法等有关知识。计算方法是一门开拓性很强的学科。随着计算机体系结构的更新，计算机上的数值算法也正从串行算法向并行算法转变。《计算方法简明教程》下篇侧重于介绍实现这种转化的二分技术，其内容包括递推计算的并行化以及快速变换等。这些资料供读者自学时参考。《计算方法简明教程》追求简明实用。书中所阐述的算法设计原理容易理解，而所推荐的算法设计技术也不难掌握。作为计算机科学重要基础的数值算法设计学，其设计思想的简朴、设计方法的协调、设计技术的实用，体现了这门学科内在的科学美。《计算方法简明教程》所面向的读者没有刻意追求。上篇内容大学的理科、工科、文科各个专业均能采用，下篇则主要面向硕士、博士研究生。《计算方法简明教程》亦可供从事科学计算的工程技术人员以及其他科技人员阅读参考。

　　王能超，教授，是我国并行算法设计的先驱者之一，他在这方面有许多独特的重要贡献，其中最主要的是他巧妙地运用二分技术于并行算法设计，把相当多的一类串行算法需N次运算的问题，只要提供足够数量的处理机进行并行计算，即可把运算次数从N降到log2N。串行算法中的快速算法如FFT把运算次数从N2阶降到Nlog2N阶而著称于世。而并行算法利用二分技术则能对许多类型的大量计算问题的运算次数下降到相应程度。王能超教授在并行算法设计中所以能取得巨大进展。主要由于他对算法设计的基本原理有深刻的研究，这反映在他的专著<数值算法设计》一书中①。读书有许多独到的论点。他首先不同意国际上流行的所谓并行算法是一门“全新”的算法，必须摆脱传统的算法设计的“束缚”。他认为从传统算法到快速算法，进而到今日正在兴起的并行算法。是算法设计的深化与提高。他运用二分技术于并行算法设计并取得丰硕成果，正好说明并行算法设计的研究不应脱离串行算法。而应从中吸取其基本原理并加以深化与提高。另夕卜，他一方面指出计算数学是一门新兴学科，但它又深深扎根于数学的肥沃土壤之中，并从数学的母体里吸取了极为丰富的营养；另一方面他又指出计算数学应当是数学与计算机科学的交叉学科，它应兼有这两门学科的基本特征，从而提出了“面向计算机“的数值算法设计学的尝试。正是由于这些独到的论点。使他在并行算法设计的研究中取得巨大的、实质性的进展。推动了这门算法设计学的发展。他的这本专著曾获中南地区大学出版社协会优秀学术专著一等奖，这确是一本在算法设计学中独具特色富有创造性的优秀学术著作，为此我热烈建议授予（国家教委科技进步奖）一等奖。

引论
1 算法重在设计
1.1 科学计算离不开算法设计
1.2 算法设计要有“智类之明
1.3 数学思维的化归策略
2 化大为小的缩减技术
2.1 Zeno悖论的启示
2.2 数列求和的累加算法
2.3 缩减技术的设计思想
2.4 多项式求值的秦九韶算法
2.5 秦九韶算法的计算流程
3 化难为易的校正技术
3.1 Zeno悖论中的“Zeno钟
3.2 求开方值的迭代公式
3.3 校正技术的设计思想
4 化粗为精的松弛技术
4.1 Zeno算法的升华
4.2 千古绝技“割圆术
4.3 求倒数值的迭代算法
4.4 松弛技术的设计思想
5 会通古今的中华数学
5.1 中华民族是个擅长计算的民族
5.2 《周易》论“简易
习题0
第一章 插值方法
1.1 插值问题的提法
1.1.1 什么是插值
1.1.2 插值平均的概念
1.1.3 代数精度的概念
1.1.4 Lagrange插值的提法
1.2 Lagrange插值公式
1.2.1 插值基函数的概念
1.2.2 两点插值
1.2.3 三点插值
1.2.4 多点插值
1.2.5 Lagrange插值公式的计算流程
1.3 Nevile逐步插值算法
1.3.1 两点插值的松弛公式
1.3.2 插值公式的逐步构造
1.3.3 逐步插值的计算流程
1.4 Newton插值多项式
1.4.1 插值逼近的概念
1.4.2 插值多项式的逐步生成
1.4.3 差商及其性质
1.4.4 差商形式的插值公式
1.4.5 差分形式的插值公式
1.5 Hermite插值
1.5.1 Taylor插值
1.5.2 构造插值多项式的待定系数法
1.5.3 构造插值多项式的余项校正法
1.5.4 构造插值多项式的基函数方法
1.6 分段插值
1.6.1 高次插值的Runge现象
1.6.2 分段插值的概念
1.6.3 分段三次Hermite插值
1.7 样条插值
1.7.1 样条函数的概念
1.7.2 三次样条插值
小结
习题
第二章 数值积分
2.1 机械求积
2.1.1 求积方法的历史变迁
2.1.2 机械求积的概念
2.1.3 求积公式的精度
2.1.4.点注记
2.2 Newton－Cotes公式
2.2.1 Newton－Cotes公式的设计方法
2.2.2 Newton－Cotes公式的精度分析
2.3 Gallss公式
2.3.1 Grauss公式的设计方法
2.3.2 带权的Grauss公式举例
2.4 复化求积法
2.4.1 复化求积公式
2.4.2 变步长的梯形法
2.5 Romberg算法叫
2.5.1 梯形法的加速
2.5.2 Simpson法再加速
2.5.3 Cotes法的进.步加速
2.5.4 Romberg算法的计算流程
2.6 数值微分
2.6.1 数值求导的差商公式
2.6.2 数值求导公式的设计方法
小结
习题二
第三章 常微分方程的差分法
3.1 Euler方法
3.1.1 Euler格式
3.1.2 隐式Euler格式
3.1.3 Euler两步格式
3.1.4 梯形格式
3.1.5 改进的Euler格式
3.1.6 Euler方法的分类
3.1.7 Euler方法的精度分析
3.2 Runl8bKutta方法
3.2.1 Runge－Kutta方法的设计思想
3.2.2 中点格式
3.2.3 二阶Rungc－Kutta方法
3.2.4 Kutta格式
3.2.5 四阶经典Runge－Kutta格式
3.3 Adams方法
3.3.1 二阶Adams格式
3.3.2 误差的事后估计
3.3.3 实用的四阶Adams预报校正系统
3.4 几种重要的线性多步格式
3.4.1 smpson格式
3.4.2 Milne格式
3.4.3 Hamming格式
3.4.4 实用的Milne－Hamming预报校正系统
3.5 收敛性与稳定性
3.5.1 收敛性问题
3.5.2 稳定性问题
3.6 方程组与高阶方程的情形
3.6.1 阶方程组
3.6.2 化高阶方程为.阶方程组
3.7 边值问题
小结
习题三
第四章 方程求根的迭代法
4.1 开方法
4.1.1 开方公式的建立
4.1.2 开方法的直观解释
4.1.3 开方法的收敛性
4.2 Newton法
4.2.1 Newton公式的导出
4.2.2 Newton法的几何解释
4.2.3 Newton法的计算流程
4.2.4 Newton法应用举例
4.3 压缩映象原理
4.3.1 线性迭代函数的启示
4.3.2 大范围的收敛性
4.3.3 局部收敛性
4.3.4 迭代过程的收敛速度
4.4 NeWton法的改进与变形
4.4.1 Newton下山法
4.4.2 弦截法
4.4.3 快速弦截法
4.5 Aitken加速算法
小结
习题四
第五章 线性方程组的迭代法
5.1 引言
5.2 迭代公式的建立
5.2.1 JaCobi迭代
5.2.2 Gauss－Scidel迭代
5.3 迭代法的设计技术
5.3.1 迭代矩阵的概念
5.3.2 矩阵分裂技术
5.3.3 预报校正技术
5.4 迭代过程的收敛性
5.4.1 对角占优阵的概念
5.4.2 迭代收敛的一个充分条件
5.5 超松弛迭代
小结
习题五
第六章 线性方程组的直接法
6.1 追赶法
6.1.1 二对角方程组的回代过程
6.1.2 追赶法的设计思想
6.1.3 追赶法的计算公式
6.1.4 追赶法的计算流程
6.1.5 追赶法的可行性
6.2 三对角阵的二对角分解
6.2.1 追赶法的矩阵分解手续
6.2.2 三对角阵的LDU分解
6.3 对称阵的三角分解
6.3.1 对称阵的Chotesky分解
6.3.2 对称阵的压缩存储技巧
6.4 矩阵分解方法
6.4.1.般矩阵的三角分解
6.4.2 Crout分解的计算公式
6.4.3 Doolittle分解的计算公式
6.5 消去法
6.5.1 Gauss消去法的设计思想
6.5.2 Gauss消去法的计算步骤
6.5.3 选主元素
6.6 中国古代数学的“方程术”
小结
习题六
上篇部分习题参考答案
导论
第七章 叠加计算
第八章 一阶线性递推
第九章 三角方程组
第十章 三对角方程组
第十一章 快速Fourier变换
第十二章 快速Walsh变换