最近一段时间在复习数值计算相关内容，也恰逢简书断更了，不用每天督促着自己非要更出点什么东西才好，有更多的空间来打磨文章的内容，在之前的每天不断更的坚持下，目前写电子稿的速度有了较大的提升，对于以后写文章之类的有着还是很多好处的，虽断了更有点遗憾，但总的来说还是利大于弊的。

这次我准备写一个系列的数值计算的内容，学习的教材是李庆扬的《数值分析》，这是研究生的教材，实际上在本科生的基础上也就加进去一点点新的内容，主要是更加系统，根本的阐述了这些数值计算方法的内容，之后在竞赛完以后应该还会提前学习偏微分方程数值解的内容，这些东西提前系统地一起学了对于以后研究生活应该有不少的好处。
所以目前的大体框架安排为：

数值分析与微积分
数值分析与线性代数
数值分析与常微分方程
数值分析与偏微分方程
这一节我们讲解的是数值分析与微积分：

概述

为什么我们要从微积分开始讲呢？大家如果有心的话，可以注意到，我编排的顺序其实和大多数人学习课程的顺序是极为相似的 $高数\rightarrow 线代\rightarrow 常微\rightarrow 偏微$
不知道大家有没有思考过为什么课程是这么设置的，我个人的理解是前一项往往是后一项的基础，所以按照这个顺序来，效果会最好。

数值分析介绍

学一门课，首先要知道这门课程存在的必要性。我认为对于此课程重要性，大家记住这句话即可：“解决实际问题的时候我们往往是将问题抽象成一个数学模型，而这些模型的完备形式往往不能够方便的求出精确解，只能转为简化模型求其数值解，往往为了方便求解，又过于简化了，这时，使用数值的方法就可以求解较少简化模型，从而得到满足近似程度要求的结果”

误差相关

算法数值稳定性

一个算法，如果输入数据有误差，而在计算过程中舍入误差不增长，则称此算法是数值稳定的，否则则是不稳定的。

病态数和条件数

所谓病态的就是说一个数值问题微小的输入会引起输出数据误差很大，那么这就是病态问题。定义相对误差的比值为条件数，即
$\left|\frac{f(x)-f(x*)}{f(x)}\right|/\left|\frac{\Delta x}{x}\right|\approx\left|\frac{xf'(x)}{f(x)}\right|=C_p$
举个例子：
求解线性方程组 $\left\{\begin{array}{c} x+\alpha y=1,\\ \alpha x+y=0.\end{array}\right.$
当 $\alpha\not =1$ 时解为 $x=\frac{1}{1-\alpha^2},y=-\frac{\alpha}{1-\alpha^2}$ 由公式可以计算得到 $C_p=\left|\frac{\alpha x'(\alpha)}{x(\alpha)}\right|=\left|\frac{2\alpha^2}{1-\alpha^2}\right|$ 我们可以看到当 $\alpha\rightarrow 1$ 时 $C_p\rightarrow +\infty$

数值计算中的算法设计技术

给出几个代表性的算法，其实大家几乎能从几个为数不多的算法之中感受到计算方法的魅力。

多项式求值的秦九韶算法

给定多项式 $p(x)=a_0x^n+a_1x^{n-1}+\ldots+a_{n-1}x+a_n,a_0\not=0$ 直接计算每一项再相加，需要的乘法次数为 $O(n^2)$ 但是采用秦九韶算法以后。迭代计算公式如下：
$\left\{\begin{array}{c}b_0=a_0\\ b_i=b_{i-1}x*+a_i,i=1,2,\ldots,n,\end{array}\right.$ 那么 $b_n=p(x*)$ 即为所求。乘法次数降为了 $O(n)$ ，类似我们还可以求出 $p'(x)$ 在 $x*$ 的值，算法为 $\left\{\begin{array}{c} c_0=b_0,\\ c_i=c_{i-1}x*+b_i,i=1,2,\ldots,n-1,\end{array}\right.$ 则 $c_{n-1}=q(x*)=p'(x*)$

迭代法与开方求值

例如求解方程 $x^2-a=0$ ,可用迭代法求解，转化为 $x_{k+1}=\frac{1}{2}(x_k+\frac{a}{x_k}),k=0,1,2,\ldots$

以曲代直和化整为零

例如刘徽求圆周率使用的割圆术，牛顿迭代法求根，微积分计算定积分时使用的梯形公式。

加权平均的松弛技术

通过将迭代过程中的结果加权从而起到更进一步近似的效果。

插值法

插值法是之后的所有的基础，所以务必要学习牢固。
插值是什么意思呢，就是过给定点的多项式函数，当然这个定点的意思不光包含定点的值，还包括它的导数的值还有光滑性等条件。

要注意的一点是：插值函数不一定就是多项式函数，只要满足经过给定点就好。

插值函数：

拉格朗日插值法

其从简单的两点插值连成一条直线出发，到三点插成抛物线，抽象出一般的规律，导出了线性插值基函数的概念，即对于某一点 $x_i$ ，它的线性插值基函数是满足 $l_i(x_j)=\delta_{ij}$ 的多项式，从而求解得到一般的表达式 $l_i(x)=\prod_{i\not=j,j=0}^n\frac{x-x_j}{x_i-x_j}$ ，那么进一步知道插值多项式的形式 $L_n(x)=\sum_{i=0}^n l_i(x)f(x_i)$ 。

均差与牛顿插值多项式

已经有了拉格朗日插值法，很多人觉得已经够了，其实我们很可能遇到实时采样的问题，每采一个样，根据之前的公式，全部的系数都要重新计算，其实一个样本带来的扰动，并没有那么大，所以拉格朗日插值法对于实时采样的问题来说，做了很多重复的工作，浪费了算力，我们能不能找一种方法来优化一下呢？这就是牛顿插值法。
其核心思想是对于已知n+1个点的插值多项式若已知，为 $P_n(x)$ 那么再加入一个新的点， $P_{n+1}(x)=P_n(x)+K(x-x_0)(x-x_1)\ldots(x-x_{n+1})$ 我们可以求出常数 $K$
我们可以使用归纳法得到 $K$ 的数值，最后使用差商的定义，来将这些有规律的 $K$ 表示出来，记为 $f[x_0,x_1,\ldots,x_k]$ ，称为 $k$ 阶差商。 $f[x_0,x_k]=\frac{f(x_k)-f(x_0)}{x_k-x_0}$ 为函数 $f(x)$ 关于点 $x_0,x_k$ 的一阶均差， $f[x_0,x_1,x_k]=\frac{f[x_0,x_k]-f[x_0,x_1]}{x_k-x_1}$ 称为 $f(x)$ 二阶均差，一般的 $f[x_0,x_1,\ldots,x_k]=\frac{f[x_0,\ldots,x_{k-2},x_k]-f[x_0,x_1,\ldots,x_{k-1}]}{x_k-x_{k-1}}$ 。
最终的插值多项式为： $P_n(x)=f(x_0)+f[x_0,x_1](x-x_0)+\ldots+f[x_0,x_1,\ldots,x_n](x-x_0)(x-x_1)\ldots(x-x_{n-1})$

埃尔米特插值

有了牛顿插值以后我又满足了，但是数学的魅力就像个哲学故事一样：一个高僧的徒弟想要出师，高僧让徒弟装一桶石头，问：满了吗？然后再装沙子，问：满了吗？再装入水，问：满了吗？所以，同志们，还有很长路要继续走，come on。
我们拉格朗日插值解决了插值的问题，使用牛顿插值解决了动态入点的问题，的确，对于没有特殊要求的插值，已经够了，但是对于实际问题中，我们往往还要求导数值的相等，这就是我们要说的埃尔米特插值法。
这里的导数可以通过极限的观点和之前的均差衔接上，那么我们就可以很好的从牛顿插值法过度过来，而不用另辟蹊径。 $f[x_0,x_0]=lim_{x\rightarrow x_0}\frac{f(x)-f(x_0)}{x-x_0}=f'(x_0)$ ，进一步 $f[x_0,x_0,\ldots,x_0]=\frac{1}{n!}f^{(n)}(x_0)$ ，从而我们得到泰勒插值多项式是牛顿插值多项式的极限形式，属于埃尔米特插值多项式的一种。
一般的计算没有什么太多难的地方，按照牛顿插值法来算就好，有几阶导数就写几次。

分段低次插值

我们选用高次插值有一个问题就是次数高了，那些高次项影响太大了，导致函数变化的非常的剧烈，不符合一般实际生活的需要，所以效果不好，一般不会选取高次插值法，为了解决这一问题，我们可以把区间分成一些小的，分别进行低次插值就好。

数值分析+微积分