Васильев Юрий Николаевич
Нахождение наибольшего корня многочлена с рекуррентными коэффициентами: аналитическая форма метода Бернулли для произвольного порядка

Самиздат: [Регистрация] [Найти] [Рейтинги] [Обсуждения] [Новинки] [Обзоры] [Помощь|Техвопросы]
Links
Кожевенное мастерство: сумки, ремни своими руками Юристы. Круглосуточно
 Ваша оценка:
  • Аннотация:
    В работе исследуется поведение наибольшего корня многочлена, коэффициенты которого являются членами линейной рекуррентной последовательности. Доказано, что при стремлении степени многочлена к бесконечности наибольший корень стремится к наибольшему корню алгебраического уравнения, полученного из характеристического уравнения рекурренции прибавлением единицы к коэффициенту при старшем члене. Показана связь с классическим методом Бернулли (1728): данный результат представляет его замкнутую форму для специальной структуры коэффициентов. Проведена численная проверка для m = 2, 3, 4, 5, демонстрирующая сходимость с точностью до 6 знаков.
  Метод Бернулли (1728) - один из старейших численных методов нахождения корней многочленов. Он заключается в следующем: для многочлена степени m строится рекуррентная последовательность, коэффициенты рекурренции совпадают с коэффициентами многочлена, и тогда отношение соседних членов последовательности сходится к наибольшему по модулю корню. Метод универсален, но требует построения длинной последовательности и ожидания сходимости.
  В данной работе рассматривается обратная ситуация: коэффициенты многочлена P_n(x) сами являются членами рекуррентной последовательности. Оказывается, что в этом случае предельное значение наибольшего корня P_n(x) при n, стремящемся к бесконечности, выражается явно - как корень алгебраического уравнения степени m, получаемого простой модификацией характеристического уравнения рекурренции. Это позволяет найти ответ за один шаг, без построения последовательности и итераций.
  Случай рекурренции второго порядка
  Пусть элементы последовательности {N_k} удовлетворяют рекуррентному соотношению второго порядка
  N_k = bN_{k-1} + cN_{k-2}, N_0 = 0, N_1 = 1,
  которому соответствует характеристическое уравнение
  r^2 - br - c = 0.
  Построим многочлен степени n, коэффициентами которого служат члены этой последовательности:
  P_n(x) = x^n - N_1 x^{n-1} - N_2 x^{n-2} - ... - N_{n-1} x - N_n.
  Теорема 1. При n, стремящемся к бесконечности, наибольший корень многочлена P_n(x) стремится к наибольшему корню квадратного уравнения
  x^2 - (b+1)x - c = 0.
  Доказательство. Уравнение P_n(x) = 0 при x, не равном нулю, равносильно
  1 = N_1/x + N_2/x^2 + ... + N_n/x^n.
  Перейдём к пределу n, стремящемуся к бесконечности. Полагая t = 1/x, получаем
  1 = ∑_{k=1}^∞N_k t^k.
  
  Производящая функция последовательности {N_k}, удовлетворяющей рекурренции N_k = b N_{k-1} + c N_{k-2} с N_0 = 0, N_1 = 1, имеет вид
  G(t) = t / (1 - bt - ct^2).
  Подставляя в уравнение:
  1 = t / (1 - bt - ct^2),
  откуда
  1 - bt - ct^2 = t,
  то есть
  1 - (b+1) t - c t^2 = 0.
  Возвращаясь к x = 1/t и умножая на x^2:
  x^2 - (b+1) x - c = 0.
  Что и требовалось доказать.
  Пример 1. Числа Мерсенна.
  Характеристическое уравнение r^2 - 3r + 2 = 0, то есть b = 3, c = -2. Последовательность: 1, 3, 7, 15, 31, 63, ... (M_n = 2^n - 1).
  Новое уравнение: x^2 - 4x + 2 = 0, корни x = 2 Ђ √2.
  Наибольший корень: 2 + √2, примерно 3,414214.
  Численная проверка: наибольший корень многочлена P_30(x) равен 3,414213 - совпадение до 6 знаков.
  Пример 2. Числа Фибоначчи.
  Характеристическое уравнение r^2 - r - 1 = 0, то есть b = 1, c = 1. Последовательность: 1, 1, 2, 3, 5, 8, 13, ...
  Новое уравнение: x^2 - 2x - 1 = 0, корни x_1,2 = 1 Ђ √2.
  Наибольший корень: 1 + √2, примерно 2,414214.
  Численная проверка: наибольший корень многочлена P_30(x) равен 2,414209 - совпадение до 5 знаков.
  Пример 3. Произвольная последовательность.
  Пусть b = 7, c = -12. Характеристическое уравнение r^2 - 7r + 12 = 0 с корнями 3 и 4. Последовательность: 1, 7, 37, 175, 781, ...
  Новое уравнение: x^2 - 8x + 12 = 0, корни x = 2 и x = 6.
  Наибольший корень: 6. Численная проверка: наибольший корень многочлена P_30(x) равен 5,999984 - совпадение до 5 знаков.
  Пример 4. Числа Пелля.
  Характеристическое уравнение r^2 - 2r - 1 = 0, то есть b = 2, c = 1. Последовательность: 1, 2, 5, 12, 29, 70, ...
  Новое уравнение: x^2 - 3x - 1 = 0, корни x_1,2 = (3 Ђ √13)/2.
  Наибольший корень: (3 + √13)/2, примерно 3,302776.
  Численная проверка: наибольший корень многочлена P_30(x) равен 3,302703 - совпадение до 4 знаков.
  Обобщение на произвольный порядок m.
  Пусть элементы последовательности {N_k} удовлетворяют рекуррентному соотношению порядка m:
  N_k = b_1 N_{k-1} + b_2 N_{k-2} + ... + b_m N_{k-m}, N_0 = 0, N_1 = 1,
  с естественными начальными условиями (N_k = 0 при k <= 0, кроме N_1 = 1). Характеристическое уравнение рекурренции:
  r^m - b_1 r^{m-1} - b_2 r^{m-2} - ... - b_m = 0.
  Построим многочлен
  P_n(x) = x^n - N_1 x^{n-1} - N_2 x^{n-2} - ... - N_n.
  Теорема 2. При n, стремящемся к бесконечности, наибольший корень многочлена P_n(x) стремится к наибольшему корню уравнения
  x^m - (b_1 + 1) x^{m-1} - b_2 x^{m-2} - ... - b_m = 0.
  Доказательство. Уравнение P_n(x) = 0 при x, не равном нулю, равносильно
  1 = N_1/x + N_2/x^2 + ... + N_n/x^n.
  Перейдём к пределу n, стремящемуся к бесконечности. Полагая t = 1/x, получаем
  1 = ∑_{k=1}^∞N_k t^k.
  Производящая функция последовательности {N_k}, удовлетворяющей рекурренции порядка m с N_0 = 0, N_1 = 1, имеет вид
  G(t) = t / (1 - b_1 t - b_2 t^2 - ... - b_m t^m).
  Подставляя в уравнение:
  1 = t / (1 - b_1 t - b_2 t^2 - ... - b_m t^m),
  откуда
  1 - b_1 t - b_2 t^2 - ... - b_m t^m = t,
  то есть
  1 - (b_1 + 1) t - b_2 t^2 - ... - b_m t^m = 0.
  Возвращаясь к x = 1/t и умножая на x^m:
  x^m - (b_1 + 1) x^{m-1} - b_2 x^{m-2} - ... - b_m = 0.
  Что и требовалось доказать.
  Замечание. Правило модификации предельно простое: берётся характеристическое уравнение рекурренции и прибавляется единица к коэффициенту при r^{m-1} (старшем члене после ведущего). Полученное уравнение даёт предельный наибольший корень.
  Численные примеры для m = 3, 4, 5
  Пример 5. Рекурренция третьего порядка, b_1 = 6, b_2 = -11, b_3 = 6.
  Характеристическое уравнение r^3 - 6r^2 + 11r - 6 = 0, корни 1, 2, 3. Последовательность: 1, 6, 25, 90, 301, 966, ...
  Новое уравнение: x^3 - 7x^2 + 11x - 6 = 0. Наибольший корень: примерно 5,060647.
  Численная проверка - наибольший корень P_n(x):
  n = 10: 5,042571
  n = 20: 5,060552
  n = 30: 5,060647
  n = 50: 5,060647
  Совпадение до 6 знаков при n = 30.
  Пример 6. Числа трибоначчи, b_1 = b_2 = b_3 = 1.
  Последовательность: 1, 1, 2, 4, 7, 13, 24, 44, ...
  Новое уравнение: x^3 - 2x^2 - x - 1 = 0. Наибольший корень: примерно 2,546818.
  Численная проверка - наибольший корень P_n(x):
  n = 10: 2,517033
  n = 20: 2,545789
  n = 30: 2,546779
  n = 50: 2,546818
  Совпадение до 6 знаков при n = 50.
  Пример 7. Рекурренция четвёртого порядка, b_1 = 10, b_2 = -35, b_3 = 50, b_4 = -24.
  Характеристическое уравнение r^4 - 10r^3 + 35r^2 - 50r + 24 = 0, корни 1, 2, 3, 4. Последовательность: 1, 10, 65, 350, 1701, ...
  Новое уравнение: x^4 - 11x^3 + 35x^2 - 50x + 24 = 0. Наибольший корень: примерно 6,908697.
  Численная проверка - наибольший корень P_n(x):
  n = 10: 6,880319
  n = 20: 6,908575
  n = 30: 6,908697
  n = 50: 6,908697
  Совпадение до 6 знаков при n = 30.
  Пример 8. Числа тетраначчи, b_1 = b_2 = b_3 = b_4 = 1.
  Последовательность: 1, 1, 2, 4, 8, 15, 29, 56, 108, ...
  Новое уравнение: x^4 - 2x^3 - x^2 - x - 1 = 0. Наибольший корень: примерно 2,592053.
  Численная проверка - наибольший корень P_n(x):
  n = 10: 2,553490
  n = 20: 2,590316
  n = 30: 2,591964
  n = 50: 2,592053
  Совпадение до 6 знаков при n = 50.
  Пример 9. Рекурренция пятого порядка, b_1 = 15, b_2 = -85, b_3 = 225, b_4 = -274, b_5 = 120.
  Характеристическое уравнение r^5 - 15r^4 + 85r^3 - 225r^2 + 274r - 120 = 0, корни 1, 2, 3, 4, 5. Последовательность: 1, 15, 140, 1050, 6951, ....
  Новое уравнение: x^5 - 16x^4 + 85x^3 - 225x^2 + 274x - 120 = 0. Наибольший корень: примерно 8,945980.
  Численная проверка - наибольший корень P_n(x):
  n = 10: 8,906481
  n = 20: 8,945851
  n = 30: 8,945980
  n = 50: 8,945980
  Совпадение до 6 знаков при n = 30.
  Пример 10. Числа пентаначчи, b_1 = b_2 = b_3 = b_4 = b_5 = 1.
  Последовательность: 1, 1, 2, 4, 8, 16, 31, 61, 120, ...
  Новое уравнение: x^5 - 2x^4 - x^3 - x^2 - x - 1 = 0. Наибольший корень: примерно 2,608330.
  Численная проверка - наибольший корень P_n(x):
  n = 10: 2,565100
  n = 20: 2,606134
  n = 30: 2,608202
  n = 50: 2,608329
  Совпадение до 6 знаков при n = 50.
  Пример 11. Рекурренция пятого порядка, b_1 = 28, b_2 = -288, b_3 = 1358, b_4 = -2927, b_5 = 2310.
  Характеристическое уравнение r^5 - 28r^4 + 288r^3 - 1358r^2 + 2927r - 2310 = 0, корни 2, 3, 5, 7, 11. Последовательность: 1, 28, 496, 7182, 93345, ....
  Новое уравнение: x^5 - 29x^4 + 288x^3 - 1358x^2 + 2927x - 2310 = 0. Наибольший корень: примерно 15,038211.
  Численная проверка - наибольший корень P_n(x):
  n = 10: 14,737329
  n = 20: 15,027013
  n = 30: 15,037727
  n = 50: 15,038210
  Совпадение до 5 знаков при n = 50.
  Сравнение с методом Бернулли.
  Метод Бернулли (1728) позволяет находить корни произвольного многочлена через рекуррентные последовательности, построенные из его коэффициентов. Для многочлена
  P(x) = x^m + d_1 x^{m-1} + d_2 x^{m-2} + ... + d_m
  строится последовательность {M_n} по рекуррентной формуле
  M_n = -d_1 M_{n-1} - d_2 M_{n-2} - ... - d_m M_{n-m}, M_0 = 0, M_1 = 1,
  и при условии, что корни действительны и различны по модулю, выполняется
  lim_n->∞M_n/M_{n-1} = c_1,
  где c_1 - наибольший по модулю корень.
  Связь с нашей теоремой. Применим метод Бернулли к предельному уравнению
  x^m - (b_1 + 1) x^{m-1} - b_2 x^{m-2} - ... - b_m = 0.
  Рекуррентная формула для этого уравнения:
  M_n = (b_1 + 1) M_{n-1} + b_2 M_{n-2} + ... + b_m M_{n-m}, M_0 = 0, M_1 = 1.
  Сравним с исходной рекурренцией:
  N_k = b_1 N_{k-1} + b_2 N_{k-2} + ... + b_m N_{k-m}, N_0 = 0, N_1 = 1.
  Разница - ровно в одном коэффициенте: у M_n первый коэффициент равен (b_1 + 1), у N_k - b_1. Всё остальное совпадает.
  Таким образом, метод Бернулли, применённый к предельному уравнению, использует почти ту же последовательность, что и исходная - с заменой b_1 на b_1 + 1. Отношение M_n / M_{n-1} сходится к наибольшему корню предельного уравнения, то есть к тому же значению, что даёт наша теорема.
  Сравнение скорости сходимости на примере 9 (m = 5, корни 1, 2, 3, 4, 5):
  Многочлен P_n(x), n = 30: 8,945980 - 6 знаков
  Метод Бернулли, n = 20: 8,945980 - 6 знаков
  Метод Бернулли, n = 10: 8,946008 - 4 знака
  На примере 10 (числа пентаначчи):
  Многочлен P_n(x), n = 50: 2,608329 - 5 знаков
  Метод Бернулли, n = 20: 2,608330 - 6 знаков
  Метод Бернулли, n = 10: 2,608365 - 4 знака
  Метод Бернулли сходится быстрее, поскольку его рекуррентная последовательность построена непосредственно для предельного уравнения. Многочлену P_n(x) требуется большая степень n, чтобы приблизиться к предельному уравнению.
  Ключевой вывод: теорема 2 представляет аналитическую форму метода Бернулли для случая рекуррентных коэффициентов. Метод Бернулли делает итеративно то, что теорема даёт в один шаг - через решение одного алгебраического уравнения степени m.
  Ограничение Абеля - Руффини
  Для m = 2, 3, 4 предельное уравнение решается в радикалах: квадратное - по формуле Виета, кубическое - по формуле Кардано, уравнение четвёртой степени - по формуле Феррари.
  Для m ≥ 5 теорема Абеля - Руффини утверждает, что не существует общей формулы, выражающей корни произвольного уравнения степени 5 и выше через коэффициенты с помощью радикалов и арифметических операций. Однако это ограничение касается только аналитической записи ответа, а не его существования или численного нахождения. Наибольший корень предельного уравнения всегда существует, однозначно определён и может быть найден численно (например, методом Ньютона).
  Следует отметить, что в частных случаях предельное уравнение при m ≥ 5 может разлагаться на множители, и тогда корни выражаются явно. Например, в примере 11 (m = 5, характеристические корни 2, 3, 5, 7, 11) предельное уравнение имеет наибольший корень примерно 15,038, который не выражается в простых радикалах, но легко находится численно. Если же характеристическое уравнение имеет специальную структуру, предельное уравнение может оказаться разрешимым.
  Таким образом, ограничение Абеля - Руффини не препятствует применению теоремы 2: оно лишь означает, что для m ≥ 5 ответ записывается численно, а не в виде формулы.
  Заключение
  Основной результат работы: для многочлена, коэффициенты которого подчиняются линейной рекурренции порядка m, наибольший корень при стремлении степени к бесконечности равен наибольшему корню уравнения, полученного из характеристического уравнения рекурренции прибавлением единицы к коэффициенту при старшем члене. Это сводит задачу к решению одного алгебраического уравнения степени m вместо построения многочлена большой степени и итеративного поиска его корней.
  
  Результат является аналитической формой метода Бернулли для специальной структуры коэффициентов: вместо построения длинной рекуррентной последовательности и ожидания сходимости отношений, достаточно решить одно уравнение. Для m <= 4 ответ выражается в радикалах; для m >= 5 - находится численно, что не является препятствием для практического применения.
  Численная проверка для m = 2, 3, 4, 5 подтверждает теорему с точностью до 6 знаков при умеренных значениях n (от 30 до 50).
  Перспективы дальнейших исследований:
  Исследование поведения остальных корней многочлена P_n(x) (не только наибольшего) и их связи с корнями предельного уравнения.
  Обобщение на рекурренции с кратными корнями характеристического уравнения.
  Обобщение на рекурренции с комплексными корнями.
  Применение к конкретным классам последовательностей (числа Люка, числа Деланнуа и др.).
  Список литературы
  Bernoulli D. Observationes de seriebus recurrentibus. - Commentarii Academiae Scientiarum Imperialis Petropolitanae, 1728, т. 3, с. 85--100.
  Householder A. S. The Numerical Treatment of a Single Nonlinear Equation. - McGraw-Hill, 1970.
  Henrici P. Applied and Computational Complex Analysis, vol. 1. - Wiley, 1974.
  Wilf H. S. Generatingfunctionology. - Academic Press, 1994.
  Graham R. L., Knuth D. E., Patashnik O. Concrete Mathematics. - Addison-Wesley, 1994.
  Stanley R. P. Enumerative Combinatorics, vol. 1. - Cambridge University Press, 1997.
  Ленг С. Алгебра. - М.: Мир, 1968.
  Postnikov M. M. Foundations of Galois Theory. - Pergamon Press, 1962.
  
  
  
 Ваша оценка:
Связаться с программистом сайта.

Новые книги авторов СИ, вышедшие из печати:
О.Болдырева "Крадуш. Чужие души" М.Николаев "Вторжение на Землю"

Как попасть в этoт список

Кожевенное мастерство | Сайт "Художники" | Доска об'явлений "Книги"