计算方法

本书介绍数值计算方法的基本原理、基础知识，并通过讲解函数插值、数值微分与积分、线性方程组的解法、矩阵特征值与特征向量的计算、非线性方程(组)的解法等基本数学问题的数值解法来阐述如何应用计算方法的基本原理解决实际问题，结合具有实际背景的案例，做到理论与实际相结合，帮助学生掌握数值计算的基本方法和基本思想。

时小虎，吉林大学计算机科学与技术学院教授，博士生导师，一直从事机器学习、生物信息学等领域的教学与科研工作。作为项目负责人主持国家自然科学基金面上项目1项、完成国家自然科学基金青年项目1项；获省部级科技进步奖一等奖3项、二等奖4项。合作出版专著1部；先后发表学术论文70余篇，其中SCI索引论文24篇。2014年至2017年连续四年入选由Elsevier出版集团评选的“中国高被引学者榜单”。

第1章　绪论　1 1.1　计算方法概述　1 1.1.1　科学计算与计算方法　1 1.1.2　数学模型与计算方法　2 1.1.3　计算方法的特点及学习方法　4 1.2　误差　5 1.2.1　计算机的浮点表示及算术运算　5 1.2.2　误差来源　7 1.2.3　误差的基本概念　8 1.2.4　误差分析　9 1.3　实验——函数导数的近似计算　11 1.4　延伸阅读　14 1.5　思考题　14 1.6　习题　14 1.7　实验题　15 第2章　线性代数方程组的数值解　17 2.1　引入——谷歌搜索PageRank算法　17 2.2　高斯消元法　19 2.2.1　消元过程　21 2.2.2　回代过程　22 2.2.3　计算量与存储　23 2.3　矩阵的三角分解　24 2.3.1　矩阵的LU分解　24 2.3.2　杜利特尔分解　26 2.3.3　对称正定矩阵的平方根法和LDLT分解　29 2.3.4　解三对角方程组的追赶法　33 2.4　消元法在计算机上的实现　34 2.4.1　选主元的必要性　34 2.4.2　选主元的方法　35 2.4.3　迭代改善　37 2.4.4　行列式和逆矩阵的计算　38 2.5　向量和矩阵范数　38 2.5.1　向量范数　38 2.5.2　矩阵范数　39 2.5.3　谱半径　41 2.6　矩阵的条件数与病态方程组　42 2.7　迭代法　44 2.7.1　迭代法的一般形式　44 2.7.2　迭代法的收敛性　45 2.7.3　雅可比迭代法　47 2.7.4　高斯-赛德尔迭代法　49 2.8　实验——常数项扰动对误差的影响　52 2.9　延伸阅读　53 2.10　思考题　54 2.11　习题　54 2.12　实验题　56 第3章　非线性方程（组）的数值解　58 3.1　引入——开平方计算　58 3.2　非线性方程问题　59 3.3　二分法　60 3.4　不动点迭代法　62 3.4.1　不动点迭代法　62 3.4.2　迭代法的几何解释　63 3.4.3　迭代法的收敛　64 3.4.4　稳定性与收敛阶　67 3.5　牛顿迭代法　68 3.5.1　定义　68 3.5.2　牛顿迭代法的几何解释　69 3.5.3　牛顿迭代法的收敛性与收敛阶　69 3.5.4　割线法　71 3.6　解非线性方程组的牛顿迭代法　73 3.7　实验——牛顿迭代法求解非线性方程　74 3.8　延伸阅读　76 3.9　思考题　76 3.10　习题　76 3.11　实验题　77 第4章　特征值问题的数值解　78 4.1　引入——再论PageRank算法　78 4.2　幂法及其变体　80 4.2.1　乘幂法　80 4.2.2　反幂法　83 4.2.3　幂法的平移　86 4.3　雅可比旋转法　87 4.3.1　平面旋转变换矩阵　88 4.3.2　雅可比旋转法　89 4.3.3　雅可比过关法　92 4.4　豪斯霍尔德变换*　92 4.4.1　实对称矩阵的三对角化　93 4.4.2　求对称三对角矩阵特征值的对分法　97 4.4.3　三对角矩阵特征向量的计算　100 4.5　QR方法　101 4.5.1　QR算法的基本思想　101 4.5.2　QR分解　102 4.5.3　QR算法求解矩阵特征值　105 4.6　特征值问题的一些应用　107 4.6.1　主成分分析与数据降维　107 4.6.2　奇异值分解　111 4.7　实验——奇异值分解对图像压缩　115 4.8　延伸阅读　116 4.9　思考题　117 4.10　习题　117 4.11　实验题　118 第5章　函数插值与曲线拟合　119 5.1　引入——图像缩放　119 5.1.1　最近邻插值算法　119 5.1.2　双线性插值算法　120 5.2　拉格朗日插值法　121 5.2.1　代数插值　122 5.2.2　插值余项　123 5.2.3　拉格朗日插值公式　124 5.3　牛顿插值法　129 5.4　三次埃尔米特插值　132 5.5　差分与等距节点的插值公式　136 5.6　曲线拟合和最小二乘法　138 5.6.1　最小二乘法的原理　139 5.6.2　最小二乘法的多项式拟合　139 5.6.3　非线性最小二乘拟合的线性化　141 5.7　实验——龙格现象的模拟　142 5.8　延伸阅读　143 5.9　思考题　143 5.10　习题　144 5.11　实验题　145 第6章　数值积分　146 6.1　引入——波纹瓦材料长度　146 6.2　牛顿-柯特斯求积公式　147 6.2.1　插值型求积公式与代数精度　147 6.2.2　牛顿-柯特斯求积公式　148 6.3　复合公式与龙贝格求积公式　150 6.3.1　复合求积公式　150 6.3.2　分半加速算法　151 6.4　高斯型求积公式　154 6.4.1　高斯型求积公式　154 6.4.2　正交多项式　155 6.4.3　高斯-勒让德求积公式　156 6.5　实验——广义积分的数值求解　158 6.6　延伸阅读　160 6.7　思考题　160 6.8　习题　160 6.9　实验题　161 第7章　常微分方程初值问题的数值解　162 7.1　引入——三论PageRank算法　162 7.2　常微分方程初值问题　163 7.3　欧拉方法及其改进　164 7.3.1　欧拉方法　165 7.3.2　欧拉方法的几何解释　165 7.3.3　欧拉方法的截断误差　166 7.3.4　向后欧拉方法　166 7.4　梯形方法　167 7.4.1　梯形方法　167 7.4.2　改进欧拉格式　168 7.5　龙格-库塔方法　170 7.5.1　龙格-库塔方法的基本思想　170 7.5.2　龙格-库塔方法　171 7.5.3　二级龙格-库塔格式　172 7.5.4　四级龙格-库塔格式　173 7.6　常微分方程组的数值解法　175 7.7　实验——欧拉显式方法的收敛性数值分析　177 7.8　延伸阅读　178 7.9　思考题　179 7.10　习题　179 7.11　实验题　179 第8章　GNU Octave简介　181 8.1　GNU Octave简介　181 8.2　基础操作　182 8.2.1　变量　183 8.2.2　矩阵及其基本运算　183 8.3　编程基础　188 8.3.1　控制语句　188 8.3.2　自定义函数　188 8.3.3　M文件　188 8.4　绘图与图形处理　189 8.4.1　简单绘图　189 8.4.2　图形有关的一些命令　189 8.4.3　在同一张图中绘制多个函数　190 8.4.4　绘制三维图　190 8.5　数值计算相关函数　191 8.5.1　特征根和特征向量　191 8.5.2　PCA函数　192 8.5.3　SVD函数　192 8.5.4　interp1插值函数　193 8.5.5　梯形求积公式　194 8.5.6　抛物线自适应积分　194 参考文献　196