本篇博文是作者当时期末备考期间总结的，里面包含了所有的重点知识以及作业代码。如果有同校同系的学弟学妹们也在看这篇文章，请把本文当做一个参考即可，大家不要直接搬运作业代码，毕竟亲力亲为才能增长能力呀。

本学期作者需要学一门很重要的专业必修课——数值计算方法。

但是，宛如天书的教材、晦涩难懂的PPT、形态各异的公式…这些都不禁让人失去学习动力。几节课下来，深感自己学的不扎实，故需要结合具体题目和代码进行总结与复盘。本篇文章主要记录和整理了我在学习计算方法这门课中学习到的概念、公式、例题，以及用Python编写的相关算法代码。

数值计算方法不研究模型误差和观测误差，其主要研究方法误差（截断误差）和舍入误差。

模型误差：在将实际问题转化为数学模型的过程中，为了使数学模型尽量简单，以便于分析或计算，往往要忽略一些次要的因素，进行合理的简化。这样，实际问题与数学模型之间就产生了误差，这种误差称为模型误差，计算方法课中不讨论此种误差。

观测误差：由于仪器本身的精度有限或某些偶然的客观因素会引入一定的误差，这种误差叫做观测误差，计算方法课中不讨论此种误差。

方法误差：当实际问题的数学模型很复杂，不能获取模型的精确解，必须提供近似解，模型的准确解与数值方法准确解之差称为截断误差或方法误差。

舍入误差：用有限位小数来代替无穷小数或用位数较少的小数来代替位数较多的有限小数所产生的误差。

绝对误差（误差）：绝对误差简称误差。设x是准确值，x*为x的一个近似值，则近似值x的绝对误差为e(x)。

绝对误差限：绝对误差的绝对值不超过某个正数ε，即|x-x*|≤ε，x落在[x-ε,x+ε]范围内。这个正数ε就是绝对误差限。

相对误差：设x为准确值，x是近似值，e是近似值的绝对误差，则ε/x为该近似值的相对误差，记作er*。

相对误差限：相对误差的值不超过某个正数，即|(x-x*)/x|≤εr，这个正数εr就是相对误差限。

如果x*近似表示x准确到小数后第n位，并从x *第n位起直到最左边的非零数字之间的一切数字都称为有效数字，并把有效数字的位数称为有效位数。

规格化形式：

有效数字与绝对误差的关系：

有效数字与相对误差的关系：

i. 要使用数值稳定的算法，防止出现病态问题。

ii. 避免两个相似数相减，需进行等价变换。

iii. 绝对值太小的数不适合作为除数。

iv. 避免大数吃小数的现象。

v. 先化简再进行计算，避免误差的持续积累。

vi. 可以利用算法的递推性，简化结构并节省计算量。

Lagrange插值公式的基本思想是把Pn(x)的构造问题转化为n+1个插值基函数li(x)(i=0,1,…,n)的构造。基函数构造完成后便可构造一个次数不超过n的插值多项式，并使之满足条件Pn(xi)=yi(i=0,1,2…)。

一阶Lagrange插值称为一次线性Lagrange插值。其线性插值基函数和一次插值函数表达式分别为：

二阶Lagrange插值称为二次抛物Lagrange插值。其插值基函数和插值函数表达式分别为：

【例题】

【代码】

【测试】

由一阶二阶可以推广到n阶，n阶Lagrange插值公式如下：

数学公式看着太抽象了，还是结合题目写成代码易懂些。

【例题】 【代码】

【测试】

在学习Newton插值公式之前，我们需要先引入差商的概念。

我们从一阶差商看起：设有函数f(x)以及一系列互不相等的自变量x0, x1,…, xn（即在i≠ j时，xi ≠xj）的值 f(xi) , 称f[xi , xj]为f (x)在点xi , xj处的一阶差商。其计算公式为：

类推可知二阶差商的计算公式为：

则n阶差商公式为：

由差商的定义可知，高阶差商是两个低一阶差商的差商。一般我们用差商表来表示各阶差商的值。

【例题】 【代码】

【测试】

当然，差商还可以通过更直观的均差表得出：（函数值为0阶均差）

经过一大坨复杂的数学证明，Newton插值多项式显然满足差商形式的插值条件。那么，我们可以由差商表得到Newton差商公式： Newton插值公式相较于Lagrange插值公式有着巨大的优点，即其增加一个节点时，只需要再增加一项即可，没必要像Lagrange插值那样全部重新计算。

Newton插值公式的递推公式为：

【例题】

【代码】

【测试】

在实际问题中，对于所构造的插值多项式，不仅要求函数值相等，而且要求其插值光滑，即要求节点处的导数值也相等。导数的阶数越高则光滑度越高。此类插值多项式称为Hermite插值多项式，也叫带导数的插值多项式。

Hermite插值满足的条件：

Hermite插值公式：

在实际情况中，我们最常使用的是两点三次Hermite插值，将n=1代入Hermite插值公式可得两点三次Hermite插值公式：

两点三次Hermite插值的基函数分别为：

为了便于理解，我们还是通过例题来体会Hermite插值算法。

【例题】

【代码】

【测试】

对于代数插值来说，当插值多项式的次数很高时，逼近效果往往很不理想。其原因是，当n增大时，即节点加密时，f(x)与插值多项式的差别将会越来越大， 特别是在两端会发出激烈的振荡，这种现象叫龙格(Runge)现象。为了防止龙格现象的影响过大，我们要慎用高次插值，取而代之的是使用分段低次插值法。

所谓分段插值，就是将被插值函数分成几个小段，然后逐段多项式化。在各个子段上构造好插值多项式后，把它们装配到一起即可作为整个区间[a,b]上的插值函数。

在实际的工业生产中要求插值曲线既要尽可能简单，又要在曲线的连接处比较光滑。即这样的分段插值函数在分段上要求多项式次数低，还要求在节点上连续且存在连续的低阶导数，我们把满足这样条件的插值函数称为样条插值函数。样条插值函数所对应的曲线称为样条曲线，其节点称为样点，这种插值方法也被称为样条插值。

样条插值虽然理解起来比较复杂，但在做了某些近似简化后，样条的数学模型只是分段的三次多项式曲线。

尽管三次样条函数S(x)与分段Hermite插值函数具有很多共同点，但三次样条与分段Hermite插值有着本质区别：三次样条函数S(x)自身是光滑的，除了两个端点外其不需要知道 f 的导数值；而分段Hermite插值则完全依赖于f 在所有插值点的导数值。

三次样条插值一定满足以下条件：

设R(x)为余项（截断误差），f(x)为函数准确值，P(x)为插值函数估计值，则误差R(x)的公式为：

由罗尔定理可以推出：

由此公式可以导出Lagrange插值、Newton插值、Hermite插值等插值公式的误差估计公式：

1.Lagrange插值的误差估计：

2.Newton插值的误差估计：

3.Hermite插值的误差估计：

易知两点三次Hermite插值的误差估计：

4.分段插值的误差估计：

在科学实验和统计分析中，除了可以用插值逼近获得函数近似值，也可以使用曲线拟合的方法获得误差最小的近似函数。与误差较大的插值逼近不同，曲线拟合不需要经过所有数据节点，其适用于数据量较大且对误差要求较高的情况。

用几何来通俗地解释，曲线拟合便是用已知平面内的一组点确定一条曲线，使该曲线能在整体上刻画这组点的变化趋势而不需通过每个点，我们称这种方法为曲线拟合，所求出的曲线称为拟合曲线。

我们通常用“误差的平方和最小”这个准则来进行曲线拟合，这种方法也称为曲线拟合的最小二乘法。为了更好地表示曲线拟合的曲线拟合，我们需要引入线性代数中的向量内积。

设u,v为两个n维向量，则它们的内积(u,v)的表达式为： 内积有三个主要的性质：

  设φk(x)为基函数，ak为待求的系数，则待求的拟合函数P(x)的表达式为： 我们可以把这个式子写成正规方程组的形式：

我们通常将基函数φm(x)取值为x^m，其中m=0,1,2…

是不是感觉很抽象？

没错，我也不是很懂。

所以我们还是得通过具体题目的代码来理解这个拟合的过程。

【例题】

【代码】

【测试】

梯形公式：（两点，n=1时具有一次代数精度）

梯形公式的余项：

中矩形公式：

Simpson公式（三点，n=2时具有三次代数精度）：

Simpson公式的余项：

【例题】 【代码】

【测试】

Cotes系数表：

Cotes公式的余项：

当n为奇数时，Cotes公式具有n次代数精度；当n为偶数时，Cotes公式具有n+1次代数精度。

为了更高的精度，通常我们选取n=4时的Cotes公式使用，其具有五次代数精度：

【例题】

【代码】

【测试】

通过比较梯形公式、Simpson公式和Cotes公式的结果可以发现其精度依次上升。

【例题】

【代码】

【测试】

（梯形公式这误差有那么亿点点大啊。。。。）  

与插值类似，计算积分的时候也会出现龙格现象，故在次数过高时还是需要使用分段低阶的方法。  

将求积区间分成n个小区间，之后在每个小区间上分别用梯形公式求积，再将结果累加起来，就可以得到复化梯形公式。

复化梯形公式的余项为：

复化梯形公式的算法如下：

【例题】

【代码】

【测试】

复化Simpson公式：

复化Simpson公式的余项为：

复化Simpson公式的算法如下：

【例题】

【代码】

【测试】

【例题】 【代码】

【测试】

变步长的梯形求积算法的实现步骤：

【例题】 【代码】