计算方法 读书笔记

写在前面

计算方法课程在第八周就这样匆匆结课了，我还没感觉学会什么东西，可能是去听课太少了吧。每次最后一周或几天预习完一门课程，都觉得有什么东西要留下来，尤其是在去年遇到一些算法的矩阵推到，发现自己已经把大一学的东西都还给老师了。趁刚考完试还有一些印象，我想赶快把一些体会记录一下。

由于本人课没咋听，只能说一些自己认为之后会对自己有帮助的东西，算是这门学科中的一些思想吧，至于对不对，就……

泰勒展开与拉格朗日余项

事实上，计算方法，是一些数值的方法，对于计算机来说就是要解决一些拟合问题。对于这个问题，拉格朗日就给出来很好的方法，使用泰勒展开就可以将大多函数展开成多项式形式，而更好的是，这种展开程度可以表示拟合的好坏。将函数看成是多项式，这就是泰勒展开的想法，也是这些数值方法的基本思想，可以说没有这种展开形式就不会有这些方法。

说句题外话，其实，数学中很多地方都在使用这种具体化的技术，比如离散数学中“群”到“置换群”的同构。本课程中的很多问题就是在解决多取拉格朗日展开项的问题，取得的阶越高就能得到更好的拟合效果。这就是一个光滑问题。

光滑

具体怎样实现光滑，对于积分的很多待定系数的方法（例如Newton-Cotes公式、Gauss公式）来说，就是使用的拉格朗日展开对这些系数进行求解。利用更高的阶来加速收敛，从根本上来说，也是使用的一些同阶无穷小消制造更大阶的无穷小（Romberg积分法）。

对于光滑，也可以直接考虑一些连续性，从原函数连续到n阶导数连续，比如Hermite插值方法，样条插值方法，这都是一些使用n阶导数进行的光滑化处理。在本学期我还选择了图形学的课程，在之中就使用到了很多的类似光滑处理，比如像素化屏幕显示、曲面显示、多边形倒角等等。

迭代法

个人感觉，迭代法才是计算机计算方法的中心，也有可能这是我以前很少接触这种想法吧，感觉这种思想是很值得反思和提倡的。

利用迭代法还可以得到加速收敛的作用，甚至可以合理的控制误差（预报矫正公式），或者选择步长。利用此方法的就是各种迭代，逼近（Newton迭代、Jacobi迭代）等等方法。这种方法也是一种很好地控制加速的方法简单来说，对于变化做一个线性变化即可做到加速（例如超松弛法）。

这种方案也是解一些复杂情况的通用方案，现在也常常用于神经网络的求解等等，在这种计算中也经常使用其类似超松弛法的加速方法，甚至有方法计算步长应该取得的值。

降维、升维

降维、升维思想在计算方法中也很常见，毕竟让计算机去求解积分、微分的解析解还是一件非常困难的事情，甚至对于很多情况这就是不可能的。利用这种思想的就有Newton-Cotes公式、Gauss公式（积分转化为原函数计算）。从这方面来说，泰勒展开就是一种将维度分开的过程，而迭代法也是一种降维（将一种需要大量储存或者运算的方法简化到线性的计算）。例如，追赶法把n^2的矩阵分解变成3n的存储和3n的迭代。

构造

最后提一下构造这件事，这个我觉得就是数学的精华了，但是，数学家一般都不会告诉你他怎么想到这样构造的，一般都是我这样构造你跟着我的思路想这样、这样就证明出来了，但是你自己想就想不到怎么构造。可能这就是应用学科和科学研究的区别吧。利用好的构造往往能够简化问题，甚至创造和挖掘条件（利用余项的加根方法）。

利用到此方法的就有n次插值的多项式方法中的l0-ln函数的设置，适用这种方法就可以得到很好的拟合函数形式，同理Newton插值也是用了这种方式，甚至可以降维到迭代。

动态规划

动态规划可以算是算法设计课程中的一个核心了，很多算法都是由这种思想设计出来的，不过正因为这种方法如此的适用，也导致我经常想到也用不出来。由于本人算法实在不行，下午又刚被虐过，我就捡一些相关的方法简单说一下这个。比如，Romberg法求积分、矩阵三角分解法求方程的根、牛顿插值中微商的计算。利用一些子问题构造高阶父问题，利用子问题解决父问题。