题解 P4525 【【模板】自适应辛普森法1】

· · 题解

更好的阅读体验请参考我的博客

Simpson公式

在学习Simpson公式之前最好要对定积分有一个基本的了解，不过不了解也没有关系 （比如我）

Simpson公式就是在积分区间[a,b]上去找三个点a,b和m=(a+b)/2，计算其原函数的在此处的值，然后用抛物线来拟合原函数。

定积分计算方法

定积分就是求函数f(x)在区间[a,b]中的图像包围的面积。即由y=0,x=a,x=b,y=f(x)所围成图形的面积。

这里的面积是有正负的，y=0上方的面积为正，下方为负。

如何计算呢，可以用把区间分成几个小区间然后把小区间的积分求解再求和的方法，这时候就要用到Simpson公式了

Simpson公式推导

推导过程除了一个步骤其余都是初中内容了，推导过程如下

设f(x)为原函数，g(x)=Ax^2+Bx+C为拟合后的函数，则有

\int_a^bf(x)dx \approx\int_a^bAx^2+Bx+C =\frac{A}{3}(b^3-a^3)+\frac{B}{2}(b^2-a^2)+C(a-b) =\frac{(b-a)}{6}(2A(b^2+ab+a^2)+3B(b+a)+6C) =\frac{(b-a)}{6}(2Ab^2+2Aab+2Aa^2+3Bb+3Ba+6C) =\frac{(b-a)}{6}(Aa^2+Ba+C+Ab^2+Bb+C+4A(\frac{a+b}{2})^2+4B(\frac{a+b}{2})+4C) =\frac{(b-a)}{6}(f(a)+f(b)+4f(\frac{a+b}{2}))

然后就得到了Simpson公式

\int_a^bf(x)dx\approx\frac{(b-a)(f(a)+f(b)+4f(\frac{a+b}{2}))}{6}

用C++语言描述如下

inline double simpson(double l,double r) {
    double mid=(l+r)/2;
    return (f(l)+4*f(mid)+f(r))*(r-l)/6; //f(x)是原函数
}

自适应辛普森法

我们知道了定积分的计算方法，也知道了Simpson公式，按理说可以计算了。

但是有一个很重要的问题需要注意：精度。

区间分少了精度可能不够，区间分多了又会太慢，自动控制区间分割的大小，就是自适应辛普森法的好处。

实现很简单，就是二分递归的过程，如果满足了精度需要，则可以终止递归，而这就是自适应辛普森法能够自动控制区间分割大小的手段。

代码如下

double asr(double l,double r,double eps,double ans) {
    double mid=(l+r)/2;
    double l_=simpson(l,mid),r_=simpson(mid,r);
    if(fabs(l_+r_-ans)<=15*eps) return l_+r_+(l_+r_-ans)/15;
    return asr(l,mid,eps/2,l_)+asr(mid,r,eps/2,r_);
}
inline double asr(double l,double r,double eps) {
    return asr(l,r,eps,simpson(l,r));
}

调用的时候只要给出区间起点和终点和需要的精度就可以了

这个题的话直接套板子就没有问题，注意精度精确到1e-6

#include <bits/stdc++.h>
double a,b,c,d,l,r;
inline double f(double x) {
    return (c*x+d)/(a*x+b);       //原函数
}
inline double simpson(double l,double r) {      //Simpson公式
    double mid=(l+r)/2;
    return (f(l)+4*f(mid)+f(r))*(r-l)/6;
}
double asr(double l,double r,double eps,double ans) {
    double mid=(l+r)/2;
    double l_=simpson(l,mid),r_=simpson(mid,r);
    if(fabs(l_+r_-ans)<=15*eps) return l_+r_+(l_+r_-ans)/15;     //确认精度
    return asr(l,mid,eps/2,l_)+asr(mid,r,eps/2,r_);     //精度不够则递归调用
}
inline double asr(double l,double r,double eps) {
    return asr(l,r,eps,simpson(l,r));
}
int main() {
    scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&l,&r);
    printf("%.6lf",asr(l,r,1e-6));
    return 0;
}