精华内容
下载资源
问答
  • 2017-08-16 20:56:00

    自适应Simpson积分

    作用

      如标题所示,这玩意就是当你不会微积分的时候来求积分的。

      总所周知,积分的定义就是函数的某一段与坐标轴之间的面积。

      那么,自适应Simpson积分就是一种可以再某些精度下计算出较为平滑的函数的积分的比较简单优美的算法。

      (PS:这玩意的时间复杂度?大概是O(玄学)吧)

    引子

      积分的定义是面积,那么我们可以通过最基本的切割法来求出一定精度下面积。

      (ps:就是0.0000……01那样扫过去,把这个当做宽,把函数值当做高,然后乘起来当做面积)

      然而这个耗费的时间太多,而且精度也不如人意,所以就出现了Simpson积分。

    正文

      依旧是总所周知,一条二次函数曲线由三个点确定,那么也意味着,我们确定三个点可以确定一条二次函数曲线。

      还是总所周知,二次函数的积分是好求的,也就是牛顿科特斯的公式中n=2的情况。那么我们就可以通过二分取点来吧当前区间的积分拟成一个二次函数的积分。

      来写份伪代码可能会清楚一点

    double get(double l,double r){
    
        mid=(l+r)/2;
    
        return (横坐标为l,r,mid,纵坐标为他们在要积分的函数上的值)穿过这三个点的二次函数在l到r之间的积分。这一步具体可以表现为(r-l)(f(l)+f(r)+4*f(mid))/6(这个公式据说用导数求很方便,在这里会用就好,我也并不会证明(我太弱啦))
    
    }
    
    double Simpson(double l,double r){
    
        double mid=(l+r)/2;
    
        s1=get(l,mid)+get(mid,r);
    
        s2=get(l,r);
    
        if(abs(s1-s2)<eps(这玩意是精度误差))return s2;
    
        return Simpson(l,mid)+Simpson(mid,r);
    
    }

      如代码所示,自适应Simpson积分就是不停地二分区间,然后把每一段函数看成两段二次函数,然后积分,再中间取点,若这个与继续分下去的差小于精度误差,那么这个区间再分下去也不会对答案的精度范围造成什么影响,那么就直接返回这一段区间的值。

      然而据大佬yww讲,这玩意是假的自适应Simpson积分,因为没有精度保障,他的都是把eps也二分传下去。这样做确实能有精度保障(然而在bzoj的某道题目,yww的真丶自适应积分爆炸了,假的自适应积分过了),所以我还是写假的自适应Simpson积分吧。

    某些注意事项

      有许多根本积不了分的函数也照样可以被自适应Simpson积分摁在地上日,原因很显然,就是这玩意就一逼近算法,没太多数学上的限制。当然,越平滑的函数用Simpson积分所造成的误差会越小,如果有什么七次函数八次函数什么的倒是也可以用,不过效果怎么样就不知道了。

    转载于:https://www.cnblogs.com/Star-dust/p/7375853.html

    更多相关内容
  • 自适应simpson积分

    千次阅读 2018-10-16 20:14:17
    还好辛普森积分有一个重要的“变种”,称为自适应辛普森法(adaptive Simpson’s rule),设置一个精度Eps,让算法根据具体情况递归的划分区间,容易近似的地方少划几份,不容易近似的地方多划几份。这就是所谓的...

    辛普森积分是数值积分的一种,是中点公式和梯形公式的改进。

    假定我们要求如下定积分 

    \int_{a}^{b}f(x)dx

    略微懂一点微积分知识的都知道,对于一个黎曼可积的函数,我们要求其在某个闭区间上的定积分,要先求该函数的不定积分,即先求原函数。就是找到一个函数F(x),使得F′(x)=f(x),然后根据牛顿—莱布尼茨公式,即:

    \int_{a}^{b}f(x)dx=F(b)-F(a)

    而有时候原函数并不好求,比如要求原的函数很复杂,要求的原函数非初等函数,但用程序进行积分,一般的方法是矩形(梯形)切割法,但精度比较差。这里用Simpson积分公式,原理是用二次曲线逼近原函数,精度比矩形切割要好。

    引理:在平面直角坐标系中,由任意三点(x1, y1), (x2, y2), (x3, y3)(x1<x2<x3x2 = (x1 + x3)/2)确定的抛物线y= f(x)在[x1, x3]的定积分为

    证明如下:引自传送门

    在区间[a,b]中等距地取奇数个点a=x0,x1,x2,...,xn=b,相邻两点间的距离为Δx,再设yi=f(xi),然后套用公式 

    点取得越多,近似程度就越高,但计算量也越大,当只取三个点的时候,有


    这就是三点辛普森公式,又简称辛普森公式。
    然而如果只取三个点误差肯定大,取太多的点计算量也会上去。那么到底取多少个点合适呢?

    还好辛普森积分有一个重要的“变种”,称为自适应辛普森法(adaptive Simpson’s rule),设置一个精度Eps,让算法根据具体情况递归的划分区间,容易近似的地方少划几份,不容易近似的地方多划几份。这就是所谓的“自适应”。

    具体的话,就是设区间[a,b]的中点为c,则当且仅当

    时(加==亦可)直接返回结果,否则递归调用,再次划分区间。递归调用时精度Eps也要相应地减小一半。

    这里的S(a,b)就是[a,b]的三点辛普森公式值,返回的结果是S(c,b)+S(a,c)+Δs,Δs=[S(a,c)+S(c,b)−S(a,b)]/15|。顺便提醒一句,如果直接返回S(a,b)的话,可能存在的误差超出可接受范围,就是比较可能会出错。

    double f(double x){
        return x * x + x;//写要求辛普森积分的函数
    }
    
    double simpson(double L, double R){//三点辛普森积分法,要求f(x)是全局函数
        double mid = (L + R) / 2.0;
        return (f(L) + 4.0 * f(mid) + f(R)) * (R - L) / 6.0;
    }
    
    double integral(double L, double R, double Eps){//自适应辛普森积分递归过程
        double mid = (L + R) / 2.0;
        double ST = simpson(L, R), SL = simpson(L, mid), SR = simpson(mid, R);
        if(fabs(SL + SR - ST) <= 15.0 * Eps)  return SL + SR + (SL + SR - ST) / 15.0;//直接返回结果
        return integral(L, mid, Eps/2.0) + integral(mid, R, Eps/2.0);//对半划分区间
    }

     

    展开全文
  • 数值积分课程需编制自适应Simpson公式,此代码采用递归函数,函数中采用了fcnchk函数,matlab6.5及以下版本会报错,只需将函数定义语句改成inline函数即可
  • 然后直接自适应Simpson法套进去就好了. 然后? 没有了qwq 代码实现 #include #include #include #include #include #include #include #include #include using namespace std; #define ll long long #define ...

    前言

    不知道为什么,今天感觉想要写一下数学的东西,然后就看了一下我还有这个模板不会,顺手写了一下。

    没有学过微积分的最好还是看一下求导为好。

    求导

    听说很多人都不会求导,我写一下吧qwq

    \(f(x)=ax^2+bx+c\)

    那么显然这个东西求导的话就是:

    \(f'(x)=\frac{\triangle{y}}{\triangle{x}}\)

    那么\(\triangle{y}=f(x+\triangle{x})-f(x)\)

    你把这个东西拆开:

    \[ \triangle{y}= \\ f(x+\triangle{x})-f(x) \\ =a*(x+\triangle{x})^2-a*x^2+b*(x+\triangle{x})-b*x+c-c \\ =a*(x^2+\triangle{x}^2+2*x*\triangle{x})-a*x^2+b*x-b*x+b*\triangle{x} \\ =a*\triangle{x}^2+2*a*x*\triangle{x}+b*\triangle{x} \]

    然后考虑一下除一下就是:

    \[ f'(x)=\frac{\triangle{y}}{\triangle{x}} \\ =\frac{a*\triangle{x}^2+2*a*x*\triangle{x}+b*\triangle{x}}{\triangle{x}} \\ =a\triangle{x}+2*a*x+b \]

    然后我们又发现\(lim_{\triangle{x}->0}\triangle{x}\)

    所以化简就是:

    \(f'(x)=2*a*x+b\)

    由此我们还可以得到一些比较好的东西:

    \((x^n)'=n*x^{n-1}\)

    与:

    \((g(x)*f(x))'=g(x)\centerdot f'(x)+g'(x)\centerdot f(x)\)

    然后把两个搞在一起就是:
    \[ (c*f(x))'=c*f'(x) \]

    大概入门就只要这么点东西吧。

    积分

    定义就是曲面围成的面积。

    然后就是许多的式子qwq(这个直接背记就好了。)

    当然如果有网的话也可以查。

    还有一个比较需要记住的公式:

    可导函数\(f(x)\)在区间\([a,b]\)的弧长

    \(\int_a^b\sqrt{1+f'(x)}dx\)

    我突然发现我自己越来越不会算区间,凉凉了。

    开始

    假定我们现在已经有了一个函数\(f(x)\),现在要求这样子的积分:
    \[ \int_a^bf(x)dx \]

    Simpson公式

    \[ \int_a^bf(x)dx\approx\frac{\triangle{x}}{3}(y_0+4*y_1+y_2)+\frac{\triangle{x}}{3}(y_2+4*y_3+y_4)+... \]

    然后直接自适应Simpson法套进去就好了.

    然后?
    没有了qwq

    代码实现

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<math.h>
    #include<algorithm>
    #include<queue>
    #include<set>
    #include<map>
    #include<iostream>
    using namespace std;
    #define ll long long
    #define re register
    #define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
    inline int gi(){
        int f=1,sum=0;char ch=getchar();
        while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
        while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
        return f*sum;
    }
    const double eps=1e-12;
    double a,b,c,d,l,r;
    double F(double x){
        return (c*x+d)/(a*x+b);
    }
    double Simpson(double a,double b){
        double c=a+(b-a)/2;
        return (F(a)+4*F(c)+F(b))*(b-a)/6;
    }
    double simpson(double a,double b,double eps,double A){
        double c=a+(b-a)/2;
        double L=Simpson(a,c),R=Simpson(c,b);
        if(fabs(L+R-A)<=eps*15)return L+R+(L+R-A)/15;
        return simpson(a,c,eps/2,L)+simpson(c,b,eps/2,R);
    }
    double Ask(double a,double b,double eps){
        return simpson(a,b,eps,Simpson(a,b));
    }
    int main(){
        scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&l,&r);
        printf("%.6lf\n",Ask(l,r,eps));
        return 0;
    }

    转载于:https://www.cnblogs.com/mle-world/p/10265280.html

    展开全文
  • 学习笔记: 自适应Simpson积分+例题

    千次阅读 2019-01-15 22:13:56
    参考bloghttps://blog.csdn.net/lunch__/article/...这个东西对于三次以下的函数是正确的,但是对于三次以上的函数我们可以将其近似为低次函数套用Simpson公式,这个东西学名好像叫自适应Simpson积分。 昨天AC...

    参考bloghttps://blog.csdn.net/lunch__/article/details/82288676
    https://blog.csdn.net/xyz32768/article/details/81392369

    这个东西对于三次以下的函数是正确的,但是对于三次以上的函数我们可以将其近似为低次函数套用Simpson公式,这个东西学名好像叫自适应Simpson积分。

    昨天ACMACM模拟的时候遇到了一道SimpsonSimpson积分相关的题

    完全不知道怎么求,我们组FishmenFishmen被BymBym嘲讽了很久

    于是今天下午结合各种资料还是看了一下

    这个东西不要觉得它看上去讲什么积分很高级 实际上认真推导也不是很难

    首先SimpsonSimpson积分的式子是这个东西

    积分号的下标代表区间左端点,上标代表区间右端点

    这个值的意思就是函数在[a,b][a,b]区间与xx轴,x=ax=a, x=bx=b围成的面积

    首先引入一些东西,SimpsonSimpson积分就是用一个二次曲线来无限逼近原曲线

    来达到求得近似值的效果

    首先引入一个东西 对于一个二次函数f(x)=ax2+bx+cf(x)=ax2+bx+c
    求积分可得F(x)=∫x0f(x)dx=a3x3+b2x2+cx+DF(x)=∫0xf(x)dx=a3x3+b2x2+cx+D
    在这里DD是一个常数 这个东西具体怎么证等我问了物理组的同学再来填坑

    那么∫RLf(x)dx=F®−F(L)∫LRf(x)dx=F®−F(L)
    ∫RLf(x)dx=a3(R3−L3)+b2(R2−L2)+c(R−L)∫LRf(x)dx=a3(R3−L3)+b2(R2−L2)+c(R−L)
    ∫RLf(x)dx=(R−L)[a3(L2+R2+LR)+b2(L+R)+c]∫LRf(x)dx=(R−L)[a3(L2+R2+LR)+b2(L+R)+c]
    ∫RLf(x)dx=b−a6(2aL2+2aR2+2aLR+3bL+3bR+6c)∫LRf(x)dx=b−a6(2aL2+2aR2+2aLR+3bL+3bR+6c)
    ∫RLf(x)dx=b−a6{(aL2+bL+c)+(aR2+bR+c)+4[a(L+R2)2+b(L+R2)+c]}∫LRf(x)dx=b−a6{(aL2+bL+c)+(aR2+bR+c)+4[a(L+R2)2+b(L+R2)+c]}
    ∫RLf(x)dx=b−a6[f(L)+f®+4f(L+R2)]∫LRf(x)dx=b−a6[f(L)+f®+4f(L+R2)]
    就这样证完了… 然后我们来考虑这个代码怎么实现

    double Simpson(double a, double b) {
    int mid = (a + b) / 2;
    return (b - a) / 6 * (f(a) + f(b) + 4 * f(mid));
    }
    1
    2
    3
    4
    好了写完了
    这样子直接计算我们发现误差非常大,毕竟原图像可能不能很好的用二次函数逼近

    自适应Simpson积分
    那怎么办呢,我们可以考虑模拟微分的过程,把区间分成无穷小份再把得到的答案积分就是最后的答案了

    但是一般我们只要求一个近似值,所以我们就递归到满足正常误差即可

    还有一个问题 每次递归下去都有精度误差,那么累加起来可能就和正确答案相差甚远了

    这个时候我们可以在递归的时候提高精度要求,尽量让小的答案精确这样就可以了

    double DFS(double L,double R,double eps){
        double ans=J(L,R);
        double mid=(L+R)/2;
        double ans1=J(L,mid),ans2=J(mid,R);
        if(fabs(ans1+ans2-ans)<eps*15) return ans1+ans2+(ans1+ans2-ans)/15;
        return DFS(L,mid,eps/2)+DFS(mid,R,eps/2);
    }
    

    在上式中eps一般取1e-6(具体看题题目的要求了,在下面的一道洛谷模板题中要求精度达到小数点后六位)
    在这里插入图片描述
    洛谷模板题
    下面是AC的代码

    //#include <cstdio>
    //#include<cstring>
    //#include<iostream>
    //#include<algorithm>
    //#include<set>
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define rep(i,a,b) for(int i=a;i<=b;i++)
    const int maxn = 0x3f3f3f3f;
    const int N=1e6+10;
    const double eps=1e-6;
    double a,b,c,d,l,r;
    double F(double x){
        return (c*x+d)/(a*x+b);
    }
    double J(double L,double R){
        double mid=(L+R)/2;
        return (R-L)/6*(F(R)+4*F(mid)+F(L));
    }
    double DFS(double L,double R,double eps){
        double ans=J(L,R);
        double mid=(L+R)/2;
        double ans1=J(L,mid),ans2=J(mid,R);
        if(fabs(ans1+ans2-ans)<eps*15) return ans1+ans2+(ans1+ans2-ans)/15;
        return DFS(L,mid,eps/2)+DFS(mid,R,eps/2);
    }
    int main(){
        #ifndef ONLINE_JUDGE
        freopen("in.txt","r",stdin);
        #endif // ONLINE_JUDGE
        scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&l,&r);
        printf("%.6f\n",DFS(l,r,eps));
    }
    
    

    然后还有一道HDU1724的板子题
    题意:题目就是求两条线所夹的椭圆的面积。这是个标准的椭圆,其中心在原点。我好像看到了题目连椭圆面积公式都给了,然而并没有任何用,直接上辛普森!
    如果改变eps的大小,比如这道题eps=1e-6时46ms,eps=1e-4时15ms,看题目而定

    //#include <cstdio>
    //#include<cstring>
    //#include<iostream>
    //#include<algorithm>
    //#include<set>
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define rep(i,a,b) for(int i=a;i<=b;i++)
    const int maxn = 0x3f3f3f3f;
    const int N=1e6+10;
    const double eps=1e-6;
    double a,b;
    double F(double x){
        return sqrt(b*b*(1-(x*x)/(a*a)));
    }
    double J(double L,double R){
        double mid=(L+R)/2;
        return (R-L)/6*(F(R)+F(L)+4*F(mid));
    }
    
    double DFS(double L,double R,double eps){
        double mid=(L+R)/2;
        double ans=J(L,R),ans1=J(L,mid),ans2=J(mid,R);
        if((ans1+ans2-ans)<=eps*15) return ans1+ans2+(ans1+ans2-ans)/15;
        return DFS(L,mid,eps/2.0)+DFS(mid,R,eps/2.0);
    }
    int main(){
        #ifndef ONLINE_JUDGE
        freopen("in.txt","r",stdin);
        #endif // ONLINE_JUDGE
        double l,r;
        int t;
        scanf("%d",&t);
        while(t--){
        scanf("%lf%lf%lf%lf",&a,&b,&l,&r);
        printf("%.3f\n",2.0*DFS(l,r,eps));
        }
    }
    
    
    展开全文
  • 何为自适应Simpson法 自适应辛普森算法(Adaptive Simpson′s rule)是一类近似算法(Approximation algorithm),主要用于在信息计算时求较难反导的函数的定积分。其思想是利用二次函数曲线来不断**拟合(Overfitting)所...
  • Simpson&自适应Simpson

    2019-05-31 21:43:22
    Simpson公式: ∫lrf(x)dx≈(r−l)(f(l)+f(r)+4f(l+r2))6\int^{r}_{l}f(x)dx\approx\frac{(r-l)(f(l)+f(r)+4f(\frac{l+r}{2}))}{6}∫lr​f(x)dx≈6(r−l)(f(l)+f(r)+4f(2l+r​))​ inline double simpson(double l...
  • 自适应simpson公式解定积分

    千次阅读 2014-04-28 21:09:56
    //则直接使用保存的simpson值不用再调用simpson函数, //若改变则调用函数并保存修改后的值 //eps为自定义精度 double asr(double a,double b,double eps,double A) { double c=a+(b-a)/2; double L=simpson(a,c),...
  • 自适应Simpson积分算法(MATLAB及C++实现代码)[文].pdf
  • 浙大月赛的时候卡在了一道积分题目上,被积函数无法求出原函数。 ...问了学长方法,学习了刘汝佳的白书《算法...自适应Simpson积分也是在被积函数上取微元然后积分,普通的积分取点越多,精度越高, 但是时间也越长,在
  • hdu 4498 自适应simpson

    2017-10-02 21:42:41
    传送门 题意:  给出k1,k2,…,kn, a1,a2,…,an 和 b1,b2,…,bn  求函数:  F(x)=min{100,min{ki*(x-ai)^2+bi | 0 在坐标上画出的曲线的长度。 限制:  1 思路:  ...利用自适应si
  • 自适应Simpson

    2019-12-04 13:08:53
    Simpson是什么呢?...加一个自适应就是适应精度,当精度很小的时候,就直接返回。 Simpson公式: 例题:Simpson例题 AC代码: #pragma GCC optimize(2) #include<bits/stdc++.h> //#define int lo...
  • 自适应Simpson公式

    2019-10-06 22:43:28
    参考刘汝佳<算法指南>P163 #include<cstdio> #include<cmath> double a; double F(double x){ return sqrt(1+4*a*a*x*x);...double simpson(double a,double b) { double c=a+(b-a...
  • 定积分的定义 简单来说,函数 f(x)f(x)f(x) 在区间 [l,r][l,r][l,r] 上的定积分 ∫lrf(x)dx\int_{l}^{r}f(x)\mathrm{d}x∫lr​f(x...下面介绍的 辛普森法,就是这样一种求数值积分的方法。 辛普森法 这个方法的思想是将
  • 自适应Simpson积分 来求它的面积(也可以用纯几何的方法,不过个人感觉那种方法不灵活,推起来复杂)。 首先,这些圆应该是长成一坨一坨的(有一些圆互相部分重叠变成了一坨),那么我们的 自适应积分 就是用来处理...
  • 可导函数f(x)在区间[a,b]上的弧长:有公式(无法打出来),可以用微元法来推导,公式中的积分部分用自适应Simpson公式来求 【代码】 #include #include #include double w,h,_a;//_a:设 F(x)=_a*x^2 ...
  • 输入:函数、区间端点、容差输出:该函数在间隔内的积分 该代码包含该函数的示例。 为了进行更精确的计算,请将一个间隔分成多个子间隔,在每个子间隔上实现该函数,然后对... 拆分的一种方法是采用均匀拆分的子区间。
  • c++自适应simpson源码

    2008-06-26 10:11:06
    使用自适应simpson算法求积分的源码
  • 自适应Simpson

    2012-11-21 22:35:30
    自适应Simpson法,用于解决方程组问题
  • 思路:正常积分不可积,考虑求近似解,即利用simpson积分求解。 公式:∫(a-&gt;b)f(x)dx = (b-a)/6*(f(a)+4*f((a+b)/2)+f(b)) 注意精度要到1e-10 #include &lt;cstdio&gt; #in...
  •  解题思路:这是一道数值积分的裸题,直接利用自适应Simpson公式就可求解。由于该题是模板题,code给出了详细分析,这里就不赘述了。具体的分析可以参见白书上的数学基础章节,如果需要学习理论知识【 Simpson积分...
  • 自适应Simpson算法

    2010-04-18 21:58:08
    simpson自适应算法 下的 实现 代码
  • 数值分析——自适应辛普森积分 自适应辛普森积分法是利用二次函数对被积函数进行插值的一种模拟积分法,常用于估计积分的数值,利用递归自动适应所需精度。 公式推导 基本思想公式: ∫abf(x)dx≈∫ab(Ax2+Bx+C)dx \...
  • 一、积分的概念 积分(integral)的几何意义是函数的曲线上 xxx 的一段区间与 xxx 轴围成的曲边梯形的面积: ...计算方法一:分割成无穷多个小区间。 ∫baf(x)dx=limn→∞∑i=1nb−anf(a+b−ani)∫a...
  • 题目大意: 给定一个由圆台构成的树以及平行光线的夹角,求树的阴影面积。...可以按照圆心连线为x轴建系,可以对于在x轴上的部分求解积分,不难发现这个不规则图形的大部分都是规则图形,于是直接自适应simpson...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 852
精华内容 340
关键字:

自适应的simpson方法