Алгоритм Абрамова - Википедия - Abramovs algorithm

В математике, особенно в компьютерная алгебра, Алгоритм Абрамова вычисляет все рациональный решения линейное рекуррентное уравнение с полиномиальными коэффициентами. Алгоритм был опубликован Сергеем А. Абрамовым в 1989 году.^[1]^[2]

Универсальный знаменатель

Основное понятие в алгоритме Абрамова - универсальный знаменатель. Позволять ${ textstyle mathbb {K}}$ быть поле из характеристика нуль. В разброс ${ textstyle operatorname {dis} (p, q)}$ двух многочленов ${ textstyle p, q in mathbb {K} [n]}$ определяется как

{ Displaystyle OperatorName {dis} (п, д) = макс {к в mathbb {N} ,: , градус ( НОД (р (п), д (п + к))) geq 1 } чашка {- 1 },}

куда

{ textstyle mathbb {N}}

обозначает набор неотрицательных целых чисел. Следовательно, дисперсия максимальная.

{ textstyle к in mathbb {N}}

такой, что многочлен

{ textstyle p}

и

{ textstyle k}

-раз сдвинутый многочлен

{ displaystyle q}

есть общий фактор. это

{ textstyle -1}

если такой

{ textstyle k}

не существует. Дисперсию можно вычислить как наибольший неотрицательный корень целого числа результирующий

{ textstyle operatorname {res} _ {n} (p (n), q (n + k)) in mathbb {K} [k]}

.^[3]^[4] Позволять

{ textstyle sum _ {к = 0} ^ {r} p_ {k} (n) , y (n + k) = f (n)}

быть рекуррентное уравнение порядка

{ textstyle r}

с полиномиальными коэффициентами

{ displaystyle p_ {k} in mathbb {K} [n]}

, полиномиальная правая часть

{ textstyle f in mathbb {K} [n]}

и решение рациональной последовательности

{ textstyle у (п) в mathbb {K} (п)}

. Можно написать

{ textstyle у (п) = п (п) / д (п)}

для двух относительно простых многочленов

{ textstyle p, q in mathbb {K} [n]}

. Позволять

{ textstyle D = operatorname {dis} (p_ {r} (n-r), p_ {0} (n))}

и

{ Displaystyle и (п) = gcd ([p_ {0} (n + D)] ^ { underline {D + 1}}, [p_ {r} (nr)] ^ { underline {D + 1 }})}

куда

{ textstyle [п (п)] ^ { подчеркивание {к}} = п (п) п (п-1) компакт-дисков р (п-к + 1)}

обозначает падающий факториал функции. потом

{ textstyle q (n)}

разделяет

{ textstyle и (п)}

. Итак, многочлен

{ textstyle и (п)}

можно использовать в качестве знаменателя для всех рациональных решений

{ textstyle у (п)}

и поэтому он называется универсальным знаменателем.^[5]

Алгоритм

Пусть снова ${ textstyle sum _ {к = 0} ^ {r} p_ {k} (n) , y (n + k) = f (n)}$ быть рекуррентное уравнение с полиномиальными коэффициентами и ${ textstyle и (п)}$ универсальный знаменатель. После замены ${ textstyle у (п) = г (п) / и (п)}$ для неизвестного полинома ${ textstyle г (п) в mathbb {K} [п]}$ и установка ${ textstyle ell (n) = operatorname {lcm} (u (n), dots, u (n + r))}$ рекуррентное уравнение эквивалентно

{ displaystyle sum _ {k = 0} ^ {r} p_ {k} (n) { frac {z (n + k)} {u (n + k)}} ell (n) = f ( n) ell (n).}

Поскольку

{ textstyle и (п + к)}

отменить это линейное рекуррентное уравнение с полиномиальными коэффициентами, которое может быть решено для неизвестного полиномиального решения

{ textstyle г (п)}

. Есть алгоритмы нахождения полиномиальных решений. Решения для

{ textstyle г (п)}

затем можно снова использовать для вычисления рациональных решений

{ textstyle у (п) = г (п) / и (п)}

. ^[2]

алгоритм рациональные_решения является    Вход: Линейное рекуррентное уравнение  ${ textstyle sum _ {k = 0} ^ {r} p_ {k} (n) , y (n + k) = f (n), p_ {k}, f in mathbb {K} [ n], p_ {0}, p_ {r} neq 0}$ .    выход: Общее рациональное решение  ${ textstyle y}$  если есть какие-то решения, иначе ложь.  ${ textstyle D = OperatorName {disp} (p_ {r} (n-r), p_ {0} (n))}$      ${ textstyle и (п) = gcd ([p_ {0} (n + D)] ^ { underline {D + 1}}, [p_ {r} (nr)] ^ { underline {D + 1 }})}$      ${ textstyle ell (n) = operatorname {lcm} (u (n), dots, u (n + r))}$     Решать  ${ textstyle sum _ {k = 0} ^ {r} p_ {k} (n) { frac {z (n + k)} {u (n + k)}} ell (n) = f ( n) ell (n)}$  для общего полиномиального решения  ${ textstyle г (п)}$     если решение  ${ textstyle г (п)}$  существуют тогда        возвращаться общее решение  ${ textstyle у (п) = г (п) / и (п)}$     еще        возвращаться ложный конец, если

Пример

Однородное рекуррентное уравнение порядка ${ textstyle 1}$

{ Displaystyle (п-1) , у (п) + (- п-1) , у (п + 1) = 0}

над

{ textstyle mathbb {Q}}

имеет рациональное решение. Его можно вычислить, рассматривая дисперсию

{ displaystyle D = operatorname {dis} (p_ {1} (n-1), p_ {0} (n)) = operatorname {disp} (-n, n-1) = 1.}

Это дает следующий универсальный знаменатель:

{ displaystyle u (n) = gcd ([p_ {0} (n + 1)] ^ { underline {2}}, [p_ {r} (n-1)] ^ { underline {2}} ) = (n-1) n}

и

{ displaystyle ell (n) = operatorname {lcm} (u (n), u (n + 1)) = (n-1) n (n + 1).}

Умножая исходное рекуррентное уравнение на

{ textstyle ell (п)}

и заменяя

{ textstyle у (п) = г (п) / и (п)}

приводит к

{ Displaystyle (n-1) (n + 1) , z (n) + (- n-1) (n-1) , z (n + 1) = 0.}

Это уравнение имеет полиномиальное решение

{ textstyle z (n) = c}

для произвольной постоянной

{ textstyle c in mathbb {Q}}

. С помощью

{ textstyle у (п) = z (п) / и (п)}

общее рациональное решение

{ Displaystyle у (п) = { гидроразрыва {с} {(п-1) п}}}

для произвольных

{ textstyle c in mathbb {Q}}

.

Рекомендации

^ Абрамов, Сергей А. (1989). «Рациональные решения линейных дифференциальных и разностных уравнений с полиномиальными коэффициентами». Вычислительная математика и математическая физика СССР. 29 (6): 7–12. Дои:10.1016 / с0041-5553 (89) 80002-3. ISSN 0041-5553.
^ ^а ^б Абрамов, Сергей А. (1995). Рациональные решения линейных разностных и q-разностных уравнений с полиномиальными коэффициентами. ISSAC '95 Труды Международного симпозиума 1995 года по символьным и алгебраическим вычислениям. С. 285–289. Дои:10.1145/220346.220383. ISBN 978-0897916998.
^ Ман, Ю-Квонг; Райт, Фрэнсис Дж. (1994). Быстрое вычисление полиномиальной дисперсии и его применение к неопределенному суммированию. ISSAC '94 Труды Международного симпозиума по символьным и алгебраическим вычислениям. С. 175–180. Дои:10.1145/190347.190413. ISBN 978-0897916387.
^ Герхард, Юрген (2005). Модульные алгоритмы символьного суммирования и символьного интегрирования. Конспект лекций по информатике. 3218. Дои:10.1007 / b104035. ISBN 978-3-540-24061-7. ISSN 0302-9743.
^ Chen, William Y.C .; Пол, Питер; Саад, Хусам Л. (2007). «Схождение к алгоритму Госпера». arXiv:0711.3386 [math.CA ].

ВикиПроект по математике в Викиданных

[1] Абрамов, Сергей А. (1989). «Рациональные решения линейных дифференциальных и разностных уравнений с полиномиальными коэффициентами». Вычислительная математика и математическая физика СССР. 29 (6): 7–12. Дои:10.1016 / с0041-5553 (89) 80002-3. ISSN 0041-5553.

[Abramov_1995-2] а ^б Абрамов, Сергей А. (1995). Рациональные решения линейных разностных и q-разностных уравнений с полиномиальными коэффициентами. ISSAC '95 Труды Международного симпозиума 1995 года по символьным и алгебраическим вычислениям. С. 285–289. Дои:10.1145/220346.220383. ISBN 978-0897916998.

[3] Ман, Ю-Квонг; Райт, Фрэнсис Дж. (1994). Быстрое вычисление полиномиальной дисперсии и его применение к неопределенному суммированию. ISSAC '94 Труды Международного симпозиума по символьным и алгебраическим вычислениям. С. 175–180. Дои:10.1145/190347.190413. ISBN 978-0897916387.

[4] Герхард, Юрген (2005). Модульные алгоритмы символьного суммирования и символьного интегрирования. Конспект лекций по информатике. 3218. Дои:10.1007 / b104035. ISBN 978-3-540-24061-7. ISSN 0302-9743.

[5] Chen, William Y.C .; Пол, Питер; Саад, Хусам Л. (2007). «Схождение к алгоритму Госпера». arXiv:0711.3386 [math.CA ].

[1]

[2]

[3]

[4]

[5]