Краткое резюме : Как быстро вычислить конечную свертку двух массивов?

Описание проблемы

Я пытаюсь получить конечную свертку двух функций f (x), g (x), определенных в

. Для этого я взял дискретные образцы функций и превратил их в массивы длины шагов :

xarray = [x * i / steps for i in range(steps)]
farray = [f(x) for x in xarray]
garray = [g(x) for x in xarray]

Затем я попытался вычислить свертку с помощью функции scipy.signal.convolve . Эта функция дает те же результаты, что и алгоритм conv , предложенный здесь . Однако результаты значительно отличаются от аналитических решений.Изменение алгоритма conv для использования правила трапеций дает желаемые результаты.

Чтобы проиллюстрировать это, я привел

f(x) = exp(-x)
g(x) = 2 * exp(-2 * x)

следующие результаты:

Здесь Риман представляет собой простую сумму Римана, трапециевидный - это модифицированная версия алгоритма Римана для использования правило трапеции, scipy.signal.convolve - это функция scipy, а аналитический - аналитическая свертка.

Теперь пусть g (x) = x ^ 2 * exp (-x) , и результат станет:

Здесь «ratio» - это отношение значений, полученных из scipy, к аналитическим значениям. . Сказанное выше показывает, что проблема не может быть решена путем перенормировки интеграла.

Вопрос

Можно ли использовать скорость scipy, но сохранить лучшие результаты трапециевидного правила, или мне нужно написать расширение C для достижения желаемых результатов?

Пример

Просто скопируйте и вставьте приведенный ниже код, чтобы увидеть проблему, с которой я столкнулся. Два результата можно приблизить к более тесному согласию, увеличив переменную ступеней . Я считаю, что проблема связана с артефактами от правых сумм Римана, потому что интеграл переоценивается, когда он увеличивается, и снова приближается к аналитическому решению, когда он уменьшается.

РЕДАКТИРОВАТЬ : теперь я включил исходный алгоритм 2 для сравнения, который дает те же результаты, что и функция scipy.signal.convolve .

import numpy as np
import scipy.signal as signal
import matplotlib.pyplot as plt
import math

def convolveoriginal(x, y):
    '''
    The original algorithm from http://www.physics.rutgers.edu/~masud/computing/WPark_recipes_in_python.html.
    '''
    P, Q, N = len(x), len(y), len(x) + len(y) - 1
    z = []
    for k in range(N):
        t, lower, upper = 0, max(0, k - (Q - 1)), min(P - 1, k)
        for i in range(lower, upper + 1):
            t = t + x[i] * y[k - i]
        z.append(t)
    return np.array(z) #Modified to include conversion to numpy array

def convolve(y1, y2, dx = None):
    '''
    Compute the finite convolution of two signals of equal length.
    @param y1: First signal.
    @param y2: Second signal.
    @param dx: [optional] Integration step width.
    @note: Based on the algorithm at http://www.physics.rutgers.edu/~masud/computing/WPark_recipes_in_python.html.
    '''
    P = len(y1) #Determine the length of the signal
    z = [] #Create a list of convolution values
    for k in range(P):
        t = 0
        lower = max(0, k - (P - 1))
        upper = min(P - 1, k)
        for i in range(lower, upper):
            t += (y1[i] * y2[k - i] + y1[i + 1] * y2[k - (i + 1)]) / 2
        z.append(t)
    z = np.array(z) #Convert to a numpy array
    if dx != None: #Is a step width specified?
        z *= dx
    return z

steps = 50 #Number of integration steps
maxtime = 5 #Maximum time
dt = float(maxtime) / steps #Obtain the width of a time step
time = [dt * i for i in range (steps)] #Create an array of times
exp1 = [math.exp(-t) for t in time] #Create an array of function values
exp2 = [2 * math.exp(-2 * t) for t in time]
#Calculate the analytical expression
analytical = [2 * math.exp(-2 * t) * (-1 + math.exp(t)) for t in time]
#Calculate the trapezoidal convolution
trapezoidal = convolve(exp1, exp2, dt)
#Calculate the scipy convolution
sci = signal.convolve(exp1, exp2, mode = 'full')
#Slice the first half to obtain the causal convolution and multiply by dt
#to account for the step width
sci = sci[0:steps] * dt
#Calculate the convolution using the original Riemann sum algorithm
riemann = convolveoriginal(exp1, exp2)
riemann = riemann[0:steps] * dt

#Plot
plt.plot(time, analytical, label = 'analytical')
plt.plot(time, trapezoidal, 'o', label = 'trapezoidal')
plt.plot(time, riemann, 'o', label = 'Riemann')
plt.plot(time, sci, '.', label = 'scipy.signal.convolve')
plt.legend()
plt.show()

Спасибо за уделенное время!