数值积分

靠，除了刘汝佳的书和一些人的博客，什么中文资料都找不到

定积分真是迷人…… 有时可以算出原函数，有的时候算不出来原函数。（俗称“积不出来”）

我们需要一些求积分的方法——数值积分算法。

牛顿-莱布尼茨公式

应用于我们能容易地算出$f\left(x\right)$的原函数的情况。往往是多项式函数。

float F(float x)                //已经计算出F(x)为f(x)的导函数
{
    return 3*x+1;
}

float integral(float a,float b)
{                               
    return F(b)-F(a);           //基本定理
}

拉格朗日中值定理

对求积分也没什么用……

如果$f\left(x\right)$满足： 1. 在闭区间$[a,b]$上连续； 2. 在开区间$(a,b)$上可导。

那么开区间$(a,b)$中至少有一点$\epsilon$，使得$f\left(b\right)-f\left(a\right)=f\prime \left(\epsilon \right)(b-a)$。

辛普森公式

辛普森公式用于求我们很难求原函数的函数的积分。

很玄学的公式： ${\int }_a^{b}f\left(x\right)dx\approx \frac{b-a}{6}\left[f\right(a)+4f\left(\frac{a+b}{2}\right)+f(b\left)\right]$

大意是：选取在$x=a$、$x=\frac{a+b}{2}$和$x=b$，拿二次函数来拟合这三个点。 当然，这样搞精度误差很大。解决的方法是，把$[a,b]$分割成很多个区段，对每个区段用辛普森公式求积分。 区段的个数由要求的精度确定。（我喜欢取$233$段

自适应辛普森算法

Adaptive Simpson's method。这个东西中文资料少得可怜……

具体的方法是，改每隔$\Delta x$取一个区段为智能地取区段。 如何让程序智能起来？容易脑补，如果某段区间容易拟合上，那就少取几段；如果难以拟合，就多取几段。

如何衡量是否“容易拟合”？上面的辛普森公式给了很好的方案。 令$Sim(le,rt)$为辛普森公式所求出的答案。那么：

1. 如果$Sim(a,mid)+Sim(mid,b)-Sim(a,b)<\gamma$
   则这一块可以很好地拟合上，返回$Sim(a,mid)+Sim(mid,b)$；
2. 如果$Sim(a,mid)+Sim(mid,b)-Sim(a,b)\ge \gamma$
   则这一块不能很好地拟合上，递归处理$(a,mid)$和$(mid,b)$。

上面的方法很容易理解。如果$(a,b)$可以很好地被拟合，那么$Sim(a,mid)+Sim(mid,b)$应该和$Sim(a,b)$相差无几。

如果函数难以拟合，那么我们就需要多次拟合，来计算出尽可能准确的结果。所以，这个算法是“自适应”的。

精度比之前的普通辛普森算法好得多。

拉格朗日插值法

拉格朗日插值法求积分的原理是，以多项式来拟合被积函数，然后积多项式。

拉格朗日插值法：给定$n$个点，拟合出一条多项式函数，过这些点。

由于我们可以选择很多个点，因此多项式可以做得与原函数相当接近。同时，多项式函数很容易求导，所以也容易求积分。精度有保障。

时间复杂度：找到$n$个点用时$O\left(n\right)$，插值$O\left(n^2\right)$，求导$O\left(n\right)$，求积分$O\left(n\right)$。 当然，如果你懒得写拉格朗日插值法，高斯消元也可以，但是插值的复杂度就变成$O\left(n^3\right)$。

（其实我觉得拉格朗日插值法比高斯消元好写多了……

附上《拉格朗日插值法》的文档：拉格朗日插值法.pdf

---

update on 2016.8.31

另一种思路。

泰勒展开求积分

如果我们遇到的函数可以泰勒展开（例如$e^x$，$\sin \left(x\right)$之类的函数），那么我们可以将它展开成一个多项式，然后直接用多项式的积分方法来求解。

例如，如果我们要求$f\left(x\right)=\sin \left(x\right)$的积分，我们先把它在$O\left(n\right)$内展开成$f\left(x\right)=x-\frac{x^3}{3!}+\frac{x^5}{5!}-\frac{x^7}{7!}+\cdots$，然后在$O\left(n\right)$内求出对应的原函数$F\left(x\right)$，然后在$O\left(n\right)$内用霍纳法则求出$F\left(l\right)$和$F\left(r\right)$的值。