数值积分

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

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

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

牛顿-莱布尼茨公式

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

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

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

拉格朗日中值定理

对求积分也没什么用……

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

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

辛普森公式

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

很玄学的公式: $\int_{a}^{b} f(x) \, dx \approx \frac{b-a}{6}\left[f(a) + 4f\left(\frac{a+b}{2}\right)+f(b)\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) ≥ \gamma$
    则这一块不能很好地拟合上,递归处理$(a,mid)$$(mid,b)$

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

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

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

拉格朗日插值法

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

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

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

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

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

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


update on 2016.8.31

另一种思路。

泰勒展开求积分

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

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


CC0协议 @ ruanxingzhi 2017. CC0是啥玩意?
Home apps close