Сдвиг многочлена

Для выделения корней многочлена методом VAS требуется выполнить ряд сдвигов Тейлора, т.е. преобразований полинома: p(x)->p(x+x₀). Существует несколько способов, выполнения данного преобразования. Одним из наиболее оптимальных методов выполнения сдвига Тейлора¹, без применения параллельных вычислений, является алгоритм, описанный Шоу и Траубом², который мы используем в данном калькуляторе. Описание алгоритма - сразу же за калькулятором:

Сдвиг многочлена

Многочлен

Коэффициенты многочлена, разделенные пробелом.

Приращение

Точность вычисления

Точно

Округленно

Знаков после запятой: 2

Рассчитать

Входной многочлен

 

Многочлен со сдвигом

 

 Ссылка  Сохранить  Виджет

Алгоритм Шоу и Трауба для сдвига многочлена

Преобразование q(x) = p(x+x₀) сводится к трем последовательным преобразованиям:

• g(x) = p(x₀x)
• f(x) = g(x+1) - выполняется методом Горнера
• q(x) = f(x/x₀)

Пошаговый алгоритм

Дан полином степени n: p(x) = a_nxⁿ+a_n-1x^n-1+...+a₁x+a₀
Требуется получить коэффициенты нового полинома q_i, после сдвига Тейлора q(x) = p(x+ x₀).
Для хранения данных будем использовать матрицу t, размера m x m, m=n+1.

1. Вычислим t_i,0 = a_n-i-1x₀^n-i-1 для всех i=0..n-1
2. Сохраним t_i,i+1 = a_nx₀ⁿ для всех i=0..n-1
3. Вычислим t_i,j+1 = t_i-1,j+t_i-1,j+1 для всех j=0..n-1, i=j+1..n
4. Получим коэффициенты: q_i = t_n,i+1/x₀ⁱ для всех i=0..n-1
5. Старший коэффициент остается без изменения: q_n = a_n