如何改进这种自适应梯形法则？

Question

我尝试了 Newman 编写的计算物理练习，并为自适应梯形法则编写了以下代码。当每张幻灯片的误差估计值大于允许值时，它将该部分分成两半。我只是想知道我还能做些什么来提高算法的效率。

xm=[]
def trap_adapt(f,a,b,epsilon=1.0e-8):    
    def step(x1,x2,f1,f2):
        xm = (x1+x2)/2.0
        fm = f(xm)
        h1 = x2-x1
        h2 = h1/2.0
        I1 = (f1+f2)*h1/2.0
        I2 = (f1+2*fm+f2)*h2/2.0
        error = abs((I2-I1)/3.0) # leading term in the error expression
        if error <= h2*delta:
            points.append(xm) # add the points to the list to check if it is really using more points for more rapid-varying regions
            return h2/3*(f1 + 4*fm + f2)
        else:
            return step(x1,xm,f1,fm)+step(xm,x2,fm,f2) 
    delta = epsilon/(b-a)
    fa, fb = f(a), f(b)  
    return step(a,b,fa,fb)

此外，我用几个简单的公式将其与Romberg积分进行了比较，发现对于相同的精度，这种自适应方法使用更多的点来计算积分。

难道只是因为它先天的局限性？使用这种自适应算法而不是 Romberg 方法有什么优势？有什么方法可以让它更快更准确吗？

Answer 1

您的代码正在优化以满足每个子区间的容错要求。它还使用低阶积分规则。这两方面的改进可以显着减少函数计算的次数。

不是单独考虑每个子区间的误差，更高级的代码计算所有子区间的总误差并进行优化，直到总误差低于所需阈值。根据子区间对总误差的贡献选择子区间进行细化，首先细化较大的误差。通常使用优先级队列来快速选择子区间进行细化。

高阶积分规则可以准确地整合更复杂的函数。例如，您的代码基于辛普森规则，该规则适用于次数最多为 3 的多项式。更高级的代码可能会使用适用于更高次数（例如 10-15）的多项式的规则。

从实用的角度来看，最简单的事情就是使用实现上述想法的固定例程，例如scipy.integrate.quad。除非您特别了解要集成的内容，否则您不太可能做得更好。

Romberg 积分需要在等距点进行计算。如果您可以在任何时候评估函数，那么对于 "smooth"（类似多项式）函数，其他方法通常更准确。如果您的函数在所有地方都不是平滑的，那么自适应代码会做得更好，因为它可以专注于消除非平滑区域中的错误。

如何改进这种自适应梯形法则？

how to improve this adaptive trapezoidal rule?

python

algorithm

recursion

numerical-methods

numerical-integration