Сдвиг многочлена
Калькулятор осуществляет преобразование многочлена одной переменной p(x) в p(x+x0), используя алгоритм описанный Шоу и Траубом.
Этот материал распространяется на условиях лицензии Creative Commons Attribution/Share-Alike License 3.0 (Unported). Это означает, что вы можете размещать этот контент на своем сайте или создавать на его основе собственный (в том числе и в коммерческих целях), при условии сохранения оригинального лицензионного соглашения. Кроме того, Вы должны отметить автора этой работы, путем размещения HTML ссылки на оригинал работы https://planetcalc.ru/7726/. Пожалуйста оставьте без изменения все ссылки на других авторов данной работы или работы, на основе которой создана данная работа (если таковые имеются в спроводительном тексте).
Для выделения корней многочлена методом VAS требуется выполнить ряд сдвигов Тейлора, т.е. преобразований полинома: p(x)->p(x+x0). Существует несколько способов, выполнения данного преобразования. Одним из наиболее оптимальных методов выполнения сдвига Тейлора1, без применения параллельных вычислений, является алгоритм, описанный Шоу и Траубом2, который мы используем в данном калькуляторе. Описание алгоритма - сразу же за калькулятором:
Алгоритм Шоу и Трауба для сдвига многочлена
Преобразование 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.
- Вычислим ti,0 = an-i-1x0n-i-1 для всех i=0..n-1
- Сохраним ti,i+1 = anx0n для всех i=0..n-1
- Вычислим ti,j+1 = ti-1,j+ti-1,j+1 для всех j=0..n-1, i=j+1..n
- Получим коэффициенты: qi = tn,i+1/x0i для всех i=0..n-1
- Старший коэффициент остается без изменения: qn = an
Комментарии