МенюСхема Горнера
Обычно многочлен представлен в виде:
$f(x)=\sum\limits_{k=0}^{n} a_k x^k$
или
Где ak это действительные числа, представляющие коэффициенты многочлена и
xk это переменные многочлена.
Вышеупомянутый многочлен называют многочленом n-ой степени, то есть deg(f(x)) = n, где n представляет наивысшую степень переменной.
Схема Горнера для деления многочлена - это алгоритм упрощения вычисления значения многочлена f(x) при определённой величине x = x0 методом деления многочлена на одночлены (многочлены 1ой степени). Каждый одночлен включает в себя максимум один процесс умножения и один процесс сложения. Результат, полученный из одного одночлена, прибавляют к результату полученному от следующего одночлена и так далее в аккумулятивной манере. Такой процесс деления также называют синтетическим делением.
Чтобы объяснить вышесказанное, давайте перепишем многочлен в развёрнутой форме;
Это также может быть записано как:
Алгоритм, предложенный данной схемой, основан на нахождении значений одночленов образованных выше, начиная с тех которые заключены в больше скобок и двигаясь наружу, для нахождения значения одночленов во внешних скобках.
Алгоритм приводится в действие, следуя нижеизложенным шагам:
2. Пусть bk = ak
3. Пусть bk - 1 = ak - 1 + bkx0
4. Пусть k = k - 1
5. Если k ≥ 0, то вернуться на шаг 3
иначе Конец
Этот алгоритм может быть также графически визуализирован, принимая во внимание данный многочлен 5ой степени:
значение которого находится как x = x0, путём перестановки его следующим образом:
Другим способом представить результаты используя этот алгоритм можно в виде данной ниже таблицы:
| K | 5 | 4 | 3 | 2 | 1 | 0 |
| b5 = a5 | b4 = a4 + x0b5 | b3 = a3 + x0b4 | b2 = a2 + x0b3 | b1 = a1 + x0b2 | b0 = a0 + x0b1 |
Пример: Найти значение многочлена f(x) = x4 + 3x3 + 5x2 + 7x + 9 at x = 2
Решение:
Так как многочлен 4ой степени, то n = 4
| K | 4 | 3 | 2 | 1 | 0 |
| Шаг | b4 = 1 | b3 = 3 + 2 * 1 | b2 = 5 + 2 * 5 | b1 = 7 + 2 * 15 | b0 = 9 + 2 * 37 |
| Результат | 1 | 5 | 15 | 37 | 83 |
Таким образом, f(2) = 83.
Почему нам это необходимо делать?
Обычно, находя значения многочлена при определённом значении переменной, мы привыкли подставлять это значение в многочлен и производить вычисления. Мы также можем разработать копьютерную программу для математического вычисления, которая является необходимостью, когда мы имеем дело со сложными многочленами высоких степеней.
Метод, с помощью которого компьютер обрабатывает проблему, зависит, в основном, от того как Вы, как программист, описываете это компьютеру. Вы можете разработать Вашу программу для нахождения значения многочлена методом прямой подстановки значения переменной или использовать синтетическое деление, данное в схеме Горнера. Единственное отличие между этими двумя подходами это скорость, с которой компьютер будет находить решение том или ином случае.
Преимущество схемы Горнера в том, что оно снижает количество операций умножения. Принимая во внимание то, что время обработки каждого процесса умножения от 5 до 20 раз больше, чем время обработки процесса сложения, Вы можете утверждать, что построение программы для нахождения значения многочлена по схеме Горнера существенно уменьшит затрачиваемое компьютером время вычисления.
