Можно ли избавиться от рекуррентности в формуле?

[sherzod_]

Здравствуйте.

Существует ли способы избежать рекуррентного вычисления?
Я хочу сказать избавиться от рекуррентности в формуле, например преобразовать в ряд.
Если да то общие ли эти методы или можно будет сказать лишь взглянув на формулу?

Я не математик, вопрос прикладной, возник при вычислении себестоимости товара, при программировании в БД гораздо быстрее и эффективнее можно посчитать ряды, а рекуррентность (суммы с накоплением) связана с большими затратами.

Спасибо.

[maxal]

Общих методов нет. Есть частные методы - например, для линейных рекуррентных зависимостей.

[sherzod_]

Формула такая, растет вниз с новыми $c_n, q_n, m_n$
$ \frac{ c_1 + c_2 + c_3 + c_4 - \frac{ c_1 + c_2 + c_3 - \frac{ c_1 + c_2 - \frac{c_1}{q_1}m_1}{q_1+q_2-m_1}m_2 }{q_1+q_2+q_3-m_1-m_2}m_3 }{q_1+q_2+q_3+q_4-m_1-m_2-m_3} $

Посоветуйте что можно с ней сделать.

[maxal]

Непонятная формула. Чему равно каждое из $c_n$, $q_n$, и $m_n$ ?

[sherzod_]

Прошу прощения не разъяснил.
Индексы это дни.
$c$ это стоимость
$q$ это общее количество
$\frac{c}{q}$ - себестоимость
$m$ - это расход
все это по отношению к какому нибудь товару.

То есть товара на 1 день было $q_1$, общей стоимостью $c_1$. После этого был расход $m_1$.
Затем поступление в количестве $q_2$ стоимостью $c_2$. Затем $m_2$, $q_3$, $c_3$.. и т. д.
В итоге по вышеуказанной формуле получаем результативную себестоимость на 4-й день.

Я вычисляю по этой формуле себестоимость на $n$-й день.

[maxal]

Так последовательности $q_1, q_2, \dots, q_n$, $c_1, c_2, \dots, c_n$ и $m_1, m_2, \dots, m_n$ вам даны? И по ним нужно вычислить себестоимость?
Тогда эта задача не о рекуррентных зависимостях, а скорее об оптимизации вычислений.

Судя по формуле, вам нужно накапливать суммы $C_k=\sum_{i=1}^k c_i$, $Q_k=\sum_{i=1}^k q_i$ и $M_k=\sum_{i=1}^k m_i$. И тогда себестоимость на $n$-й день $s_n$ выразится как

$$s_n = \frac{C_n - s_{n-1}m_{n-1}}{Q_n - M_{n-1}}.$$

[sherzod_]

Вобщем-то я так и делаю.

Проблема в том что, чтобы вычислить $s_n$, нужно вычислить $s_{n-1}$. Чтобы вычислить $s_{n-1}$, нужно вычислить $s_{n-2}$ и т. д. до $s_1$. Т. е. чтобы вычислить себестоимость на 763-й день с начала работы программы, ей нужно произвести 763 вычислений)). Ничто не мешает хранить накопительные $C_n, Q_n, S_n$ и пользоваться ими, но я надеялся решить задачу математически)). И все еще надеюсь).

Добавлю что вычислить $C_n, Q_n$ не проблема, в них не задействована рекурсия, и вычисление происходит очень быстро.
Проблема именно в $S_n$, получается очень накладно по вычресурсам.

Почему все-таки не использовать накопители? Программа отлаживается и возможны внесения изменений в предыдущие дни. Приходится пересчитывать эти самые накопители.
Так что хранить накопители, или вычислять все за раз уравнивается.

[ewert]

sherzod_ в сообщении #282832 писал(а):

и пользоваться ими, но я надеялся решить задачу математически))

Что значит "математически"?... Ведь всё равно все предшествующие данные необходимо задействовать. А тогда рекуррентное соотношение -- это ровно то, что и нужно для вычислений. Даже обычная сумма -- и та на практике считается именно рекуррентно.

[sherzod_]

под "математически" я имел в виду алгебраически преобразовать формулу чтобы из рекуррентной получить например ряд, по форме что-то вроде $S_n = Kc_1q_1 + Kc_2q_2m_1 + \dots + Kc_nq_nm_{n-1}$.

-- Сб янв 23, 2010 12:29:59 --

то есть чтобы при вычислении каждого $n$-го члена не учавствовали множители из предыдущих членов.

начинаю подозревать что это невозможно.

-- Сб янв 23, 2010 12:31:23 --

можно ли доказать невозможность этого?
чтобы не тратить усилия впустую).

[jetyb]

А в чем заключается сложность вычислений?
Изначально в памяти хранятся три последовательности: $c_n,q_n$ и $m_n$. От них никак нельзя избавиться - значит, предполагается, что на компьютере есть место для $12N$ байт. По предложенной maxal формуле надо добавить в память еще две последовательности: $C_n$ и $Q_n-M_{n-1}$. Это в $\frac{5}{3}$ раз увеличит занимаемую память и потребует $3N$ сложений. Со знанием полученных последовательностей подчет $s_N$ будет простым.
Всего для вычисления $s_N$ потребуется $4N$ сложений, $N$ умножений и $N$ делений. Это очень малые затраты. Учитывая что каждый шаг считается за день, одного Excelа хватит на 179 лет.

[sherzod_]

Можно ответить двояко на ваш пост.

1. Вне зависимости от контекста(товары, себестоимость) меня интересует(я хочу разобраться) возможно-ли преобразование указанной рекуррентной формулы в ряд, каждый член которого не зависит от других.

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

Я бы хотел чтобы дискуссия шла по первому направлению, по второму направлению все достаточно очевидно(суммы с накоплением истертая тема на sql форумах), или вообще будет здесь вне темы форума. И оно служит лишь оправданием того, зачем мне нужно первое).

[maxal]

sherzod_ в сообщении #282839 писал(а):

под "математически" я имел в виду алгебраически преобразовать формулу чтобы из рекуррентной получить например ряд, по форме что-то вроде $S_n = Kc_1q_1 + Kc_2q_2m_1 + \dots + Kc_nq_nm_{n-1}$.

-- Сб янв 23, 2010 12:29:59 --

то есть чтобы при вычислении каждого $n$-го члена не учавствовали множители из предыдущих членов.

Преобразовать-то можно, только формула будет не такая простая, как вы ее себе представляете.

Обозначим $\alpha_n = \frac{C_n}{Q_n - M_{n-1}}$ и $\beta_n = -\frac{m_{n-1}}{Q_n - M_{n-1}}.$ Тогда

$$s_n = \alpha_n + \beta_n s_{n-1} = \alpha_n + \beta_n (\alpha_{n-1} + \beta_{n-1}s_{n-2}) = \dots$$

$$\dots = \alpha_n + \beta_n \alpha_{n-1} + \beta_n \beta_{n-1} \alpha_{n-2} + \dots + \beta_n \beta_{n-1} \cdots \beta_2 s_1.$$

Остается только подставить в эту формулу $s_1 = \frac{c_1}{q_1}$, чтобы окончательно избавится от зависимостей от $s_i$.

[sherzod_]

Спасибо большое за подробные разъяснения и выкладки. Вы очень помогли понять что мне нужно)). Попробую сформулировать задачу теперь.

(я допустил ошибку при написании формулы прежде, прошу прощения, думаю она не повлияла на существо задачи)

Итак
Даны три последовательности: $c_n, q_n, m_n$. На этих трех последовательностях задана четвертая последовательность $s_n$ определяемая рекуррентной формулой
$ \frac { c_1 + c_2 + c_3 + c_4 - \frac{c_1}{q_1}m_1 - \frac { c_1 + c_2 - \frac{c_1}{q_1}m_1 }{ q_1+q_2-m_1 }m_2 - \frac{ c_1 + c_2 + c_3 - \frac{c_1}{q_1}m_1 - \frac { c_1 + c_2 - \frac{c_1}{q_1}m_1 }{ q_1+q_2-m_1 }m_2 }{ q_1+q_2+q_3-m_1-m_2 }m_3 }{ q_1+q_2+q_3+q_4-m_1-m_2-m_3} } \dots $.

Требуется преобразовать формулу так, чтобы $n$-й член последовательности $s_n$ зависел лишь от соответствующих элементов последовательностей $c_n, q_n, и m_n$, то есть $s(n)$ зависит от $c(n)$, $q(n)$ и $m(n-1)$. Т. е. по существу найти нерекуррентную формулу $n$-го члена.

Или же представить формулу в виде ряда, члены которого обладают указанным свойством, т.е. зависят лишь от !соответствующих! элементов первых трех последовательностей.

Постановка не противоречива, что показывает, например, последовательность Фибоначчи или последовательность приближений числа pi.

Буду рад любым идеям, советам, критике.

[maxal]

sherzod_ в сообщении #283030 писал(а):

Даны три последовательности: $c_n, q_n, m_n$. На этих трех последовательностях задана четвертая последовательность $s_n$ определяемая рекуррентной формулой
$ \frac { c_1 + c_2 + c_3 + c_4 - \frac{c_1}{q_1}m_1 - \frac { c_1 + c_2 - \frac{c_1}{q_1}m_1 }{ q_1+q_2-m_1 }m_2 - \frac{ c_1 + c_2 + c_3 - \frac{c_1}{q_1}m_1 - \frac { c_1 + c_2 - \frac{c_1}{q_1}m_1 }{ q_1+q_2-m_1 }m_2 }{ q_1+q_2+q_3-m_1-m_2 }m_3 }{ q_1+q_2+q_3+q_4-m_1-m_2-m_3} } \dots $.

Другими словами, формула такая:

$$s_n = \frac{C_n - s_1m_1 - s_2m_2 - \dots - s_{n-1}m_{n-1}}{Q_n - M_{n-1}}$$

?

[sherzod_]

Совершенно верно