1. 多项式插值

多项式插值的理论基础是：n+1个不同的点可以唯一确定一个n次多项式。
此多项式有很多计算方法，基本都是基于待定系数法。典型的为 Lagrange法、Newton 法等。
例如，Newton 法是假设一个多项式 $Q(x)=c_0+c_1(x-x_1)+c_2(x-x_1)(x-x_2)+…+c_n(x-x_1)(x-x_2)…(x-x_n)$ 然后把n+1个点的坐标带入进去解出来。
进而推导出用线性代数、差分等方法，来加快运算。

2. 样条插值

多项式插值其实用途很有限，
例如 $f(x)=\dfrac{1}{1+25x^2}$ 在 $[-1,1]$ 上很光滑，但是在0附近插值效果很好，在1附近出现震动，且随着点个数 n 增加，震荡现象更严重。（Runge现象）

三次样条插值，给定分划 $a = x_1 \lt x_2 \lt … \lt x_{n-1} \lt x_n = b$，要找到分段函数 s(x)，满足：

1. s(x) 在每个 $[x_i,x_{i+1}]$ 上都是三次多项式
2. s(x) 在 $(a,b)$ 上连续、一阶导数连续、二阶导数连续

如何求出 s(x)？

1. 根据条件一，共有 n-1 个区间，对应 n-1 个三次多项式，每个多项式有4个待定系数。也就是共 4(n-1) 个待定系数
2. $s_i$ 的左端点和右端点都给定了，$s_i(x_i)=f(x_i), s_i(x_{i+1}) = f(x_{i+1})$ 每个多项式2个方程。也就是共 2(n-1) 个方程
3. 一阶导数连续。也就是说，相邻两个多项式的一阶导数相等。从 $x_2$ 到 $x_{n-1}$ 可以列 n-2 个方程
4. 二阶导数连续。类似的，n-2 个方程

从上面的分析发现，还差2个方程，通常有3种“流派”

1. 要求给定两端的一阶导数值 $s’(x_1), s’(x_n)$，这种情况称为 D1样条
2. 要求给定两端的二阶导数值 $s’‘(x_1), s’‘(x_n)$，这种情况称为 D2样条。特别的，如果 $s’‘(x_1) = s’‘(x_n) = 0$， 称为 自然样条
3. 去掉 $s(x_1)=f(x_1),s(x_n)=f(x_n)$ 中的1个，附加3个条件： $s(x_1) = s(x_n), s’(x_1) = s’(x_n), s’‘(x_1) = s’‘(x_n)$，称为 周期样条

之后的很多工作就是如何更快的解方程了。

3. Bezier 曲线

多项式插值和样条插值的思路是，要求n个点在函数图像上，以此建立方程。

还有另一种思路，不要n个点在函数上，而是这n个点作为“隐变量”，来生成一条曲线。

Bezier 曲线有很多优良的性质，例如

1. 凸包性：如果n个控制点组成的多边形是凸的，那么 Bezier 曲线在这个凸包内。
2. 对控制点旋转、平移、伸缩有不变形

4. 最佳逼近

前面都是给定了有限的n个点，让我们找一个对应的函数。现在的问题是，给定一个函数 $f(x)$ 在 $[a,b]$ 上连续，能否找到一个多项式，使得 $\min\limits_{p\in P_n} \max\limits_{x\in [a,b]} \mid f(x) - p(x) \mid$

看上面的描述，就知道接下来要引入泛数了。

4.1 最佳多项式逼近

记$C_{[a,b]}$ 是 $[a,b]$ 上所有连续函数构成的无限维线性空间。

存在性是已经证明的（Weierstrass 第一定理）：对任意 $f(x) \in C_{[a,b]},\forall \epsilon>0$，都存在一个多项式 $p(x)$，使得 $\mid\mid f(x) - p(x) \mid\mid_\infty \lt \epsilon$
（其中 $P_n$ 是最多n阶的多项式集合）

然后是多种计算方式

4.2 最佳三角多项式逼近

记$C_{0,2\pi]}$ 是所有 $2\pi$为周期的连续函数构成的无限维线性空间

（Weierstrass 第二定理）：对任意 $f(x) \in C_{[a,b]},\forall \epsilon>0$，都存在三角多项式 $T(x)$，使得 $\mid\mid f(x) -T(x) \mid\mid_\infty \lt \epsilon$
其中$T(x)$ 是三角函数的线性组合： \(1,\cos x,\sin x,...,\cos nx,\sin nx\)

4.3 最佳平方逼近

最佳多项式逼近、最佳三角多项式逼近，都是在讨论 $\mid\mid .\mid\mid_{\infty}$，最佳平方逼近讨论的是 $\mid\mid . \mid \mid_2$

1. 最佳正交逼近可以转化为正交系上的讨论，
2. 最小二乘法是一个特例

5. 数值积分

计算积分值的时候往往遇到一些困难：

1. 函数的不定积分无法用简单函数表达出来
2. 甚至函数本身都没有解析式，而是以表格方式给出一些离散的函数值。

例如：

1. 土地丈量时遇到的不规则地块，不知道其边缘曲线对应的函数值
2. $\int_0^1 e^{x^2}dx$ 不存在原函数

5.1 Newton-Cotes公式

问题：需要求出 $\int_a^b f(x) dx$ 的近似解。

思路：

1. 先求 $f(x)$ 的 Lagrange 插值多项式 $p(x)$
2. 计算 $\int p(x)$

（得到一个通用公式）

Newton-Cotes 公式:

1. 附加假设：给定的点是等距的 $x_k=a+\dfrac{b-a}{n} k,k=0,1,…,n$。
2. 可以把通用公式大大化简，对应的求积公式就是 Newton-Cotes 公式

几个常用的 Newton-Cotes 公式:

1. n=1 时：$\dfrac{b-a}2[f(a)+f(b)]$ 就是梯形公式
2. n=2 时：$\dfrac{b-a}6 [f(a)+4f(\dfrac{a+b}2)+f(b)]$ 是抛物线公式或 Simpson 公式
3. n=4 时：$\dfrac{b-a}{90} [7f(x_0)+32f(x_1)+12f(x_3)+32f(x_4)+7f(x_5)]$ 称为 Cotes 公式

然后是

1. 误差分析
2. 稳定性分析

5.2 复化公式

对于n个给定的等距点 $x_k=a+hi, h=\dfrac{b-a}{n}, i=0,1,…,n$

1. 每个区间 $[x_i, x_{i+1}]$ 上使用梯形公式，然后累加，得到 $\dfrac{h}{2} \sum\limits_{i=0}^{n-1} [f(x_i)+f(x_{x+1})]$
2. 每个区间 $[x_i, x_{i+1}]$ 上使用 Simpson 公式，然后累加，得到 $\sum\limits_{i=0}^{n-1} \dfrac{h}{6}[f(x_i)+4(x_{i+0.5})+f(x_{x+1})]$

5.3 特殊积分的处理

对于 震荡函数，看能不能转化为三角形式

对于 反常积分，看能不能用换元法、分布积分法，转化为正常积分

5.4 多重积分

多重积分往往复杂很多，但思路是相似的

6. 快速傅立叶变换

7. 方程求根

7.1 二分法

是找连续函数 $f(x)$ 实根的可靠方法。

step1:找到两个值 $a_1, b_1$，使得 $f(a_1)f(b_1) \lt 0$
step2:开始二分法 $x_1 = (a_1+b_1)/2$
step3:按 $f(x_1)$ 的符号，判断 $a_2=x_1$ or $b_2=x1$ or 结束迭代
step4:反复迭代。

7.2 反插值法

（反插值法这个名字来源：推导过程中先求逆函数，然后用插值公式，然后舍弃高阶项。我觉得这个解释不好，下面我用直线的解释）

在 二分法 中，我们用 $x_1 = (a_1+b_1)/2$ 来寻找下一次迭代的节点。
我们想，用“$a_1,b_1$组成的直线” 对应的零点作为下一次迭代的 $x_1$。

step1:找到两个值 $a_1, b_1$，使得 $f(a_1)f(b_1) \lt 0$
step2:利用直线公式 $x_1 = a_1-\dfrac{b_1-a_1}{f(b_1)-f(a_1)}f(a_1)$
step3:按 $f(x_1)$ 的符号，判断 $a_2=x_1$ or $b_2=x1$ or 结束迭代
step4:反复迭代。

这在很多情况下会更快的逼近真实值。尤其是当 $f(x)$ 是直线时候，一步就能得到结果结束迭代。

7.3 迭代法

我们要解方程 $F(x)=0$

令 $f(x)=x-F(x)$

问题转化为解方程 $x=f(x)$

迭代法求解的过程：$x_{k+1}=f(x_k), k=0,1,2,…$

下面就是解决这两个问题：

1. 什么条件下，上面的迭代式可以收敛到方程的解
2. 收敛速度如何？

TH1:
如果同时满足以下条件

1. $f(x)$在$[a,b]$上连续
2. $f([a,b])\subset [a,b]$
3. f(x) 满足 Lipschitz 条件 $\mid f(x) - f(y) \mid \leq L \mid x-y \mid$
4. $0 \leq L \lt 1$

那么，有结论：

1. 迭代收敛到方程的解 $x^\star$
2. $\mid x_k - x^\star \mid \leq \dfrac{L^k}{1-L}\mid x_0-x_1 \mid$

TH2：
如果同时满足以下条件

1. $f(x)$ 在$[a,b]$ 上连续可导，
2. $f([a,b])\subset [a,b]$
3. $\mid f’(x) \mid \leq L \lt 1$

那么结论也成立

7.4 Newton 法

要解方程 $F(x)=0$,

使用迭代 $x_{k+1}=x_k-\dfrac{F(x_k)}{F’(x_k)}$

可以用 1 阶 Taylor 级数导出。

直观理解，就是在 $x_i$ 找一个切线，根据切线和x轴的交点得到 $x_{x+1}$

从 Newton 法出发，同样有一些推广

1. 什么条件下，上面的迭代式可以收敛到方程的解
2. 收敛速度如何？
3. 求导数的过程复杂度较高，如何优化

参考文献

蒋尔雄《数值逼近》，复旦大学出版社