关闭

财富坊cff888: 辛普森积分(自适应辛普森公式求积分)

2080人阅读 评论(3) 收藏 举报
分类:

自适应辛普森公式求积分

第一回接触辛普森积分,至于这个辛普森是干嘛的呢,在这里就有必要好好地讲一讲了。

来源:辛普森(Simpson)公式是牛顿-科特斯公式当n=2时的情形,也称为三点公式。利用区间二等分的三个点来进行积分插值。其科特斯系数分别为1/6,4/6,1/6。

应用:立体几何中用来求拟柱体体积的公式。

这里就不详细说辛普森公式了,有需要的朋友可以看这里https://baike.baidu.com/item/%E8%BE%9B%E6%99%AE%E6%A3%AE%E5%85%AC%E5%BC%8F/9255085?fr=aladdin

接下来我们好好的说说自适应辛普森公式求积分自适应辛普森公式求积分是很重要的一个知识点,弄懂了自适应辛普森公式求积分就能明白辛普森积分是干嘛的了,

下面的内容是重点!!!:

假设我们求以下积分:

这里写图片描述

比较特殊的情况,就是可以推导出来最后的形式。但是比较一般的情况是,我们只能大致得到一个XY坐标系里的曲线,我们求的就是曲线和X轴所围成的面积。

因此我们有自适应辛普森公式,他会根据实际情况来自动的调整精度。

它的大致过程就是,给定一个要求达到的精度eps,算法就会根据实际情况递归的划分区间。容易近似的地方少划分,不容易近似的地方多划分几份。

具体来讲,我们在以下情况下直接返回结果,否则递归划分区间:

这里写图片描述

具体参考博客:/bc5/frosero/article/details/45799135

下面举个例题:hdu-1724

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1724

题目大意:题目就是求两条线所夹的椭圆的面积。这是个标准的椭圆,其中心在原点。我好像看到了题目连椭圆面积公式都给了,然而并没有任何用,直接上辛普森!

根据椭圆的对称性,我们求x轴上方的面积然后乘以2就是答案。根据椭圆方程x2a2+y2b2=1,构造函数y=。。。其中y>0,然后对此函数进行自适应辛普森积分就可以了。

写完程序过了样例后立马交,TLE,1000ms。结果发现是Eps取的太小了,取了1e-10,随着递归下去,Eps不断除以2,导致不断递归划分,做的次数很多就超时了。这题只要求保留3位小数,所以精度没有太大问题,将Eps改为1e-5立马就AC了,109ms。

ac代码:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#define ri(n) scanf("%d",&n)
#define oi(n) printf("%d\n",n)
#define rl(n) scanf("%lld",&n)
#define ol(n) printf("%lld\n",n)
#define rep(i,l,r) for(i=l;i<=r;i++)
#define rep1(i,l,r) for(i=l;i<r;i++)
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const double eps=1e-5;//这里的eps是整个辛普森应用的关键,至于取多大,得依题目而定
double a,b,l,r;
double f(double x)//这里的f函数是自己根据题目推导出来的,主要还是x有关y的函数
{
    double y=b*sqrt(1.0-(x*x)/(a*a));
    return y;
}
double simpson(double a,double b)//这里是辛普森公式
{
    double c=(a+b)/2.0;
    return (f(a)+f(b)+4.0*f(c))*(b-a)/6.0;
}
double ars(double a,double b,double eps)//这里就是递归求辛普森最重要的一段函数了,
{
    double c=(a+b)/2.0;
    double mid=simpson(a,b),l=simpson(a,c),r=simpson(c,b);
    if(fabs(l+r-mid)<=15*eps)
        return l+r+(l+r-mid)/15.0;
    return ars(a,c,eps/2.0)+ars(c,b,eps/2.0);
}
int main()
{
    int t;
    ri(t);
    while(t--)
    {
        scanf("%lf%lf%lf%lf",&a,&b,&l,&r);
        printf("%.3lf\n",2.0*ars(l,r,eps));//递归求辛普森
    }
    return 0;
}
0
0
查看评论

【转】hzwer的OI省选算法汇总[打卡记录]

1.1 基本数据结构 数组 链表,双向链表 队列,单调队列,双端队列 栈,单调栈 1.2 中级数据结构 堆 并查集与带权并查集 hash 表自然溢出双hash 1.3 高级数据结构 树状数组 线段树,线段树合并 平衡树Treap 随机平衡二叉树Splay 伸展树*Scapegoat Tree 替罪羊...
  • OIljt12138
  • OIljt12138
  • 2017-02-19 10:38
  • 517

关于辛普森积分法的研究

一部分函数的积分是可以通过Newton-Leibniz formula计算的。 然而另一部分就不行,我们就要通过数值积分的方式计算。 我们首先看一下 拉格朗日插值法,有了函数的值,通过拉格朗日插值法就可以计算出函数式。 我们设每个多项式是pj(x),我们通过构造,得出pj(x)的式子。...
  • yyx2000
  • yyx2000
  • 2017-05-06 20:42
  • 849

学习笔记: 自适应Simpson积分

看了一些大牛的博客,终于对自适应Simpson积分有了初步的了解。 Q:自适应Simpson积分是用来做什么的? A:用来求积分啊! Q:它和一般的微积分有什么区别? A:不能求出精确解,但是可以近似地求出不可导图像的面积。 首先是Simpson积分公式:   (感谢维...
  • greatwall1995
  • greatwall1995
  • 2013-03-05 18:39
  • 3381

HDU1724-辛普森积分公式法求椭圆面积

Ellipse Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1061  &...
  • leolinsheng
  • leolinsheng
  • 2014-01-21 21:44
  • 3322

变步长辛普森求数值积分

先贴代码:整理好了在给出介绍/*变步长辛普森公式 *double simp(double a,double b,double eps,double (*f)(double)) *double a:区间的左端点 *double b:区间的右端点 *double eps:误差精度 *double (*f...
  • qq_26025363
  • qq_26025363
  • 2016-12-26 12:01
  • 1612

辛普森积分法的学习

微积分是许多学科的基础,在编程方面也有很大的作用
  • kjcsdnblog
  • kjcsdnblog
  • 2014-11-22 15:01
  • 2694

复化梯形法和辛普森数值积分的matlab实现程序

  • 2013-06-30 11:06
  • 35KB
  • 下载

自适应Simpson积分

自适应Simpson积分目录 简介 例题 HDU 1724 BZOJ 1502 SPOJ CIRUT 简介: Simpson积分是解决一重积分问题的强大公式 由公式可以看出,我们可以通过积分上下界来近似逼近积分的值。 但具体如何实现呢?我们可以二分区间然后递归的方法来求积分。 由积分的可叠...
  • WuBaizhe
  • WuBaizhe
  • 2017-04-20 23:47
  • 370

自适应辛普森公式求积分

辛普森公式求积分假设我们求一下积分: ∫baf(x)dx\int_{a}^b f(x) dx 比较特殊的情况,就是可以推导出来最后的形式。但是比较一般的情况是,我们只能大致得到一个XYXY坐标系里的曲线,我们求的就是曲线和XX轴所围成的面积。因此我们有自适应辛普森公式,他会根据实际情况来自动的...
  • Frosero
  • Frosero
  • 2015-05-17 22:46
  • 2456

自适应辛普森积分算法

辛普森积分是数值积分的一种,是中点公式和梯形公式的改进。 ——这是我在APIO2017时听某位大神讲课所了解的。 下面就讲讲辛普森积分到底是啥玩意儿。假定我们要求如下定积分 ∫baf(x)dx\int_a^bf(x)dx 略微懂一点微积分知识的都知道,对于一个黎曼可积的函数,我们要求其...
  • Ab_Ever
  • Ab_Ever
  • 2017-07-30 02:29
  • 690