首页 > 编程语言 >Romberg 数值积分算法+P3779 题解(马上写完)

Romberg 数值积分算法+P3779 题解(马上写完)

时间:2024-01-23 21:46:02浏览次数:34  
标签:xi frac Romberg int 题解 求积 梯形 dx P3779

Romberg 算法

吊打 Simpson 的且不玄学(没有什么十五倍)的数值积分算法。

缺点是过程复杂一点,但是只体现在证明上,代码很短。

铺垫算法

梯形求积公式

公式

\[\int _a^b f(x)dx\approx \frac{(f(a)+f(b))(b-a)}2\\ \text{令 }(1)=\frac{(f(a)+f(b))(b-a)}2 \]

计算梯形求积公式的误差

注意到

\[\int _a^bf(x)dx=\int_a^b 1\cdot f(x)d(x-a)\\ =(b-a)f(b)-\int_a^b (x-a)f'(x)dx\\ =(b-a)f(a)-\int_a^b (x-b)f'(x)dx \]

上两式相加得到

\[\int_a^b f(x)dx=\frac{(f(a)+f(b))(b-a)}2-\frac{1}{2}\int_a^b((x-a)+(x-b))f'(x)dx\\ =(1)-\frac{1}{2}\int_a^b((x-a)+(x-b))f'(x)dx\\ =(1)+\frac 12\int _a^b(x-a)(x-b)f''(x)dx \]

根据定积分第一中值定理:

\[\exists \xi \in [a,b],\int_a^bf(x)g(x)=f(\xi)\int_a^bg(x)dx \]

\[\int_a^bf(x)dx=(1)+\frac{f(\xi)}2\int_a^b(x-a)(x-b)dx\\ =(1)-\frac{f''(\xi)(b-a)^3}{12} \]

误差为

\[-\frac{f''(\xi)(b-a)^3}{12} \]

复化梯形求积公式

把他分割成 \(n\) 段,每段应用梯形求积公式就得到了复化梯形求积公式。

设 \(x_k=a+\dfrac{k(b-a)}n\)。

\[\int _a^bf(x)dx=\sum _{k=0}^{n-1}\int _{x_k}^{x_{k+1}}f(x)dx\approx \frac{b-a}{2n}(f(a)+f(b)+2\sum _{k=1}^{n-1}f(x_k))\\ \text{令 }(2)=\frac{b-a}{2n}(f(a)+f(b)+2\sum _{k=1}^{n-1}f(x_k)) \]

计算复化梯形求积公式的误差

标签:xi,frac,Romberg,int,题解,求积,梯形,dx,P3779
From: https://www.cnblogs.com/british-union/p/17983464/romberg

相关文章

  • 前端打包后上传至服务器,发现css样式都未生效,查看请求preview预览格式不正确问题解决
    参考:https://blog.csdn.net/wzj_110/article/details/112850811 我的问题前端打包后上传至服务器,发现css样式都未生效,查看css请求,发现preview预览格式不正确,Response-Headers里的Content-type未对应 原因服务器的nginx配置中, mime.types文件缺失。 原理 MIME:Multip......
  • P2627 [USACO11OPEN] Mowing the Lawn G ( [USACO Open11] 修剪草坪/P2034 选择数字 )题
    P2627[USACO11OPEN]MowingtheLawnG搬运工单调队列优化DP简单题,和P2034重了题意:给定一行\(n\)个非负整数\(a_1\cdotsa_n\)。现在你可以选择其中若干个数,但不能有超过\(k\)个连续的数字被选择。你的任务是使得选出的数字的和最大。(直接抄的2034)正着考虑发现很麻烦,......
  • LOJ3990/LG9602 IOI2023 足球场 题解 (区间DP+精简无用状态)
    首先考虑一个足球场长啥样才是合法的。发现一个点能只拐弯一次到达另一个点,可以分为两种情况:先左右走,再上下走或先上下走,后左右走。无论哪种情况,都要求我们走一步使得和目标点一个轴相同,再走一步使得另一个轴也相同,所以加入把每一行选择的格子看成一个区间(因为如果不连续显然是......
  • CF327C Magic Five 题解
    CF327CMagicFive搬运工单调队列优化DP加等比数列求和首先\(5\)的倍数要求末尾是\(0\)或\(5\)所以我们只用看给定字符串的\(0\)和\(5\)就好,我们钦定他是最终的数的末尾。在他之前的选择删掉,在他之后的全部删掉,方案数就是\(2^{pow-1}\),答案累加就可以了。容易想到......
  • P2254 [NOI2005] 瑰丽华尔兹 题解
    P2254[NOI2005]瑰丽华尔兹搬运工单调队列优化DP还是先朴素,设\(f_{t\i\j\d}\)表示在第\(t\)个时刻,在\(i,j\)位置上,上一步是停留还是滑动的最大步数。这个就是四个方向随便转移。\(T_{max}=4*10^4\)这么做肯定不行。发现\(k\)很小,只有\(200\),所以不妨让\(k\)......
  • P2569 [SCOI2010] 股票交易 题解
    P2569[SCOI2010]股票交易搬运工稍微复杂一点的单调队列优化DP直接设\(f_{i\j}\)表示在第\(i\)天,手上还剩\(j\)个股票时的最大收入。容易写出状态转移方程:\(f_{i\j}=max\{f_{k\t}+(t-j)\cdotw\}\),这样不好看,我们可以拆成这样的形式:\[f_{i\j}=max\{f_{k\t}+t\cdo......
  • P4899 [IOI2018] werewolf 狼人 题解
    因为我记忆力不好,经常遇到之前做过的题一下子想不起来,所以打算基本上给每个比较有意思的题写题解,同时造福后代。这是werewolf,它是furry,很可爱题意:一张无向图,点有点权,每次询问从\(u\)到\(v\)的路径中,是否存在一条先走点权大于等于\(L\),再走点权小于等于\(R\)的路径。思路......
  • hugeの张江蔡唐氏模拟赛题解
    晚三huge不让去一机房,说便于管理,我的评价是:唐氏况且二机房没有luogu,改完题后没事干(指写不了狼人),遂写个没人看的题解。T1纯哈希,不写。T2纯tarjan,一直没学,不写。T3比较套路的双指针,赛时降智题意:给定由\(B\)和\(R\)组成的字符串,环形结构,每次可以交换相邻,问最少多少次可以......
  • 01.22 ARC170 题解慢报
    补完了,来发题解慢报。AB就不写了。CPrefixMexSequence考虑DP,\(f(i,j)\)表示前\(i\)个数,填了\(j\)个不同的数。如果\(s_{i+1}=1\)那么这位唯一确定,只需要保证\(j<m\)即可转移到\(f(i+1,j+1)\);如果\(s_{i+1}=0\)那么可以选旧的数也可以选新的数,分别转移即可。D......
  • 「Daily OI Round 1」block 题解
    设\(c_u\)表示节点\(u\)的颜色,\(f_u\)表示只考虑原树中\(u\)的子树中的点、选择点\(u\)的方案数。对于儿子\(v\),可以选择同色儿子节点,也可以跳过这个儿子节点,选择\(v\)的与\(u\)同色的儿子节点\(w\),故状态转移方程为:\[f_u=\prod[c_u=c_v]f_v+\left(\prod[c_u=c_w]......