把网站做静态化,视频门户网站建设项目标书,零基础怎么学美工,建网平台什么是数值积分 数值积分可以用来求定积分的近似值。对于很多函数来说#xff0c;我们是可以使用初等函数来表示出其积分的#xff0c;对于这种函数#xff0c;只需要求出不定积分然后代入值就能得到定积分了。 可是除此之外还有许多难求的函数和没法使用初等函数表示的函数… 什么是数值积分 数值积分可以用来求定积分的近似值。对于很多函数来说我们是可以使用初等函数来表示出其积分的对于这种函数只需要求出不定积分然后代入值就能得到定积分了。 可是除此之外还有许多难求的函数和没法使用初等函数表示的函数。当我们想要求出它们的定积分的时候需要使用数值积分来求解。 在ACM中一些题目需要使用数值积分来求解以下列出一些求数值积分的方法由简单到难而对ACMer来说最重要的是复合Simpson其精度较高且可调精度是乱搞积分几何的利器。 我从这学的网易公开课 MIT 数值积分 学习的契机是想要A掉这题ZOJ 3898我的题解 法一·黎曼和 黎曼和是用将区间等长分为n段然后用矩形去逼近函数每段的长为Δx。 可以选择每段左侧的函数值作为矩形的高也可以选择每段右侧的函数值作为矩形的高。 若设n1个函数值从左至右为x0,x1⋯xn可得如下公式 Left Hand RiemannRight Hand RiemannΔxf(x0)Δxf(x1)⋯Δxf(xn−1)Δx∑i0n−1f(xi)Δxf(x1)Δxf(x2)⋯Δxf(xn)Δx∑i1nf(xi) 这种逼近比较粗糙不过能比较好地传达数值积分的概念。 法二·梯形法 黎曼和虽然简单但是精度堪忧没法很好地模拟逼近函数接下来介绍第二种方法。 可以看出用矩形逼近的时候有很多空缺使用梯形去逼近就能大大提高精度了看上去很像了。 沿用之前的xi由梯形公式我们可以得到如下公式 TrapezoidΔx(f(x0)f(x1))2Δx(f(x1)f(x2))2⋯Δx(f(xn−1)f(xn))2Δx(f(x0)2f(x1)⋯f(xn−1)f(xn)2)Left Hand RiemannRight Hand Riemann2 可以看出梯形法求出的就是左右黎曼和的平均值。 公式中第一个和最后一个需要除以2其他都能合出来1个。 法三·Simpson公式 前两种都比较简单但是精度比较差第三种方法是用抛物线去逼近。 其实我并不知道是怎么计算的是从公开课上学来的。 使用Simpson公式首先需要n为偶数。 将整个区间分为n2段每段的底为2Δx高比较难搞但是是有公式的Simpson heightf(xl)4f(xm)f(xr)6 于是有公式 SimpsonΔx3(f(x0)4f(x1)2f(x2)⋯2f(xn−2)4f(xn−1)f(xn)) 法四·复合Simpson Simpson公式的精度其实已经相当不错了可是相对于ACM中所需的精度仍然有差距。 为了提高精度我们需要多次重复利用Simpson公式。 我们先定义被积函数为f(x)定义Simpson(l,r)(r−l)f(l)4f(lr2)f(r)6 这也就是常规的Simpson公式再定义函数RSimpson为复合Simpson。 当我们要求RSimpson(l,r)先令mlr2 当Simpson(l,r)≈Simpson(l,m)Simpson(m,r)时我们就认为精度够了返回其中一个。 当不满足的时候我们就再分段去求RSimpson(l,m)RSimpson(m,r) 这样得到的精度就比较高了而且通过定义≈的范围可以调整精度。 总结公式如下 RSimpson(l,r){Simpson(l,r) approximateRSimpson(l,m)RSimpson(m,r) else 复合Simpson的实现 inline double getAppr(double fl, double fm, double fr, double l, double r) {return (fl4*fmfr)*(r-l)/6.0;
}double Simpson(double l, double r, double fl, double fr) {double m (lr)/2, lm (lm)/2, rm (rm)/2;double fm f(m), flm f(lm), frm f(rm);double vlr getAppr(fl, fm, fr, l, r);double vlm getAppr(fl, flm, fm, l, m);double vrm getAppr(fm, frm, fr, m, r);return fabs(vlr-vlm-vrm) EPS ? vlr : Simpson(l, m, fl, fm)Simpson(m, r, fm, fr);
} 复合Simpson的实现2(Natureal的代码)
inline double getAppr(double l,double r){return (f(l) 4.0*f((lr)/2) f(r)) * (r - l) / 6.0;
}double Simpson(double l,double r){double sum getAppr(l,r);double mid (lr)/2;double suml getAppr(l,mid);double sumr getAppr(mid,r);return (fabs(sum - suml - sumr) EPS) ? sum : Simpson(l, mid) Simpson(mid, r);
}
