homechevron_rightУчебаchevron_rightМатематикаchevron_rightАлгебра

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

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

Creative Commons Attribution/Share-Alike License 3.0 (Unported)

Этот материал распространяется на условиях лицензии Creative Commons Attribution/Share-Alike License 3.0 (Unported). Это означает, что вы можете размещать этот контент на своем сайте или создавать на его основе собственный (в том числе и в коммерческих целях), при условии сохранения оригинального лицензионного соглашения. Кроме того, Вы должны отметить автора этой работы, путем размещения HTML ссылки на оригинал работы https://planetcalc.ru/7726/. Пожалуйста оставьте без изменения все ссылки на других авторов данной работы или работы, на основе которой создана данная работа (если таковые имеются в спроводительном тексте).

Для выделения корней многочлена методом 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. 

Creative Commons Attribution/Share-Alike License 3.0 (Unported) PLANETCALC, Сдвиг многочлена

Комментарии