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

Калькулятор осуществляет преобразование многочлена одной переменной p(x) в p(x+x0), используя алгоритм описанный Шоу и Траубом.

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

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

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

Коэффициенты многочлена, разделенные пробелом.
Входной многочлен
 
Многочлен со сдвигом
 

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

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

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

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

Дан полином степени n: p(x) = anxn+an-1xn-1+...+a1x+a0
Требуется получить коэффициенты нового полинома qi, после сдвига Тейлора q(x) = p(x+ x0).
Для хранения данных будем использовать матрицу t, размера m x m, m=n+1.

  1. Вычислим ti,0 = an-i-1x0n-i-1 для всех i=0..n-1
  2. Сохраним ti,i+1 = anx0n для всех i=0..n-1
  3. Вычислим ti,j+1 = ti-1,j+ti-1,j+1 для всех j=0..n-1, i=j+1..n
  4. Получим коэффициенты: qi = tn,i+1/x0i для всех i=0..n-1
  5. Старший коэффициент остается без изменения: qn = an

  1. Joachim von zur Gathen, Jürgen Gerhard Fast Algorithms for Taylor Shifts and Certain Difference Equations. 

  2. Mary Shaw, J.F. Traub On the number of multiplications for the evaluation of a polynomial and some of its derivatives. 

Ссылка скопирована в буфер обмена
PLANETCALC, Сдвиг многочлена

Комментарии