Войти
ПрограммированиеСтатьиОбщее

Быстрое многократное суммирование полиноминальных функций

Внимание! Этот документ ещё не опубликован.

Автор:

    Описан метод многократного суммирования (интегрированая) функций, которые могут быть представлены рядом полиноминальных коэффициентов.
    Дополнительным преимуществом метода является тот случай когда одна из полученых сумм может быть выражена в квадратурах, тогда метод сводит исходную задачу вообще к однократному суммированию (или интегрированию).
    Метод может быть использован для ускорения вычисления физических явлений, в частности, систем частиц.

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


    [cht] s = \sum_ {i=0}^n \sum_{j=0}^n K_i_,_j   [/cht]


      В случае если K разлагается на множители


    [cht] K_i_,_j  = P_iQ_j   [/cht]


    Исходная повторная сумма может быть выражена в виде двух сумм


    [cht] s = \sum_ {i=0}^n \sum_{j=0}^n P_iQ_j = \sum_ {i=0}^n (P_i \sum_{j=0}^n Q_j)  [/cht]


и тем самым исходная задача с вычислительной сложностью  O(n2) становится задачей сложности O(n).
Рассмотрим применение этой идеи на сумме полиномов типа


    [cht] s = \sum_ {i=0}^n \sum_{j=0}^n (p_i - q_j)^4   [/cht]


    Здесь Pi и Qj могут быть представлены в форме


    [cht] P_i = p_i^4 - 4 p_i^3 + 6 p_i^ 2 - 4 p_i + 1 [/cht]


и соответственно


    [cht] Q_j = 1 + q_j + q_j^2 + q_j^3 + q_j^4 [/cht]


тогда


    [cht] P_iQ_j =  (p_i - q_j)^4  [/cht]


    Очевидно, что в этом случае исходная сумма может быть найдена по формуле


    [cht] s = \sum_ {i=0}^n (P_i \sum_{j=0}^n Q_j)  [/cht]

    Численная реализация метода подтвердила ожидаемую его выскоую эффективность (см. приложенный проект), при размерах исходных векторов в 300000 элементов, время счета традиционным методом составляет 109438 мсек, а с представлением функции с помощью произведения векторов - 16 мсек.

Проект к статье PolynominalSum

#C++, #вычислительная математика, #Интегрирование, #Полиномы, #Суммирование

14 февраля 2013

Комментарии [1]