Формула горнера примеры: Схема Горнера. Примеры с пояснениями.

{n-2}+\ldots+\normblue{a_{n-1}}x+\normblue{a_n}\\ $$ $$ \begin{array} {c|c|c|c|c|c|c|c} & \normblue{a_0} & \normblue{a_1} & \normblue{a_2} & \normblue{a_3} & \ldots & \normblue{a_{n-1}} & \normblue{a_n} \\ \hline a & & & & & & & \end{array} $$

Вторая строка таблицы заполняется постепенно. Второй элемент этой строки (обозначим его $b_0$) равен $a_0$, т.е., по сути, мы просто переносим вниз число $a_0$:

$$ \begin{array} {c|c|c|c|c|c|c|c} & a_0 & a_1 & a_2 & a_3 & \ldots & a_{n-1} & a_n \\ \hline a & b_0=a_0 & & & & & & \end{array} $$

Следующий элемент второй строки, который мы обозначим как $b_1$, получается по такой формуле: $b_1=a\cdot{b_0}+a_1$:

$$ \begin{array} {c|c|c|c|c|c|c|c} & a_0 & a_1 & a_2 & a_3 & \ldots & a_{n-1} & a_n \\ \hline a & b_0 & b_1=a\cdot{b_0}+a_1 & & & & & \end{array} $$

Далее находим элемент $b_2$ по формуле $b_2=a\cdot{b_1}+a_2$:

$$ \begin{array} {c|c|c|c|c|c|c|c} & a_0 & a_1 & a_2 & a_3 & \ldots & a_{n-1} & a_n \\ \hline a & b_0 & b_1 & b_2=a\cdot{b_1}+a_2 & & & & \end{array} $$

Аналогично вычисляем и элемент $b_3=a\cdot{b_2}+a_3$:

$$ \begin{array} {c|c|c|c|c|c|c|c} & a_0 & a_1 & a_2 & a_3 & \ldots & a_{n-1} & a_n \\ \hline a & b_0 & b_1 & b_2 & b_3=a\cdot{b_2}+a_3 & & & \end{array} $$

Далее находим $b_4$, $b_5$ и так далее.

2}+\normblue{0}\cdot{x}+\normblue{(-11)}\\ $$

Так как мы делим на $x-\normred{1}$, то в первой ячейке второй строки запишем число $\normred{1}$. Таблица, с которой мы будем работать, имеет такой вид:

$$ \begin{array} {c|c|c|c|c|c} & \normblue{5} & \normblue{5} & \normblue{1} & \normblue{0} & \normblue{-11} \\ \hline \normred{1} & & & & & \end{array} $$

Начнём заполнять пустые ячейки во второй строке. Во вторую ячейку второй строки запишем число $5$, просто перенеся его вниз из второй ячейки первой строки:

$$ \begin{array} {c|c|c|c|c|c} & \normgreen{5} & 5 & 1 & 0 & -11 \\ \hline 1 & \normgreen{5} & & & & \end{array} $$

Следующую ячейку заполним по такому принципу: $\normred{1}\cdot\normgreen{5}+\normpurple{5}=\normblue{10}$:

$$ \begin{array} {c|c|c|c|c|c} & 5 & \normpurple{5} & 1 & 0 & -11 \\ \hline \normred{1} & \normgreen{5} & \normblue{10} & & & \end{array} $$

Аналогично заполним и четвертую ячейку второй строки: $\normred{1}\cdot\normgreen{10}+\normpurple{1}=\normblue{11}$:

$$ \begin{array} {c|c|c|c|c|c} & 5 & 5 & \normpurple{1} & 0 & -11 \\ \hline \normred{1} & 5 & \normgreen{10} & \normblue{11} & & \end{array} $$

Для пятой ячейки получим: $\normred{1}\cdot\normgreen{11}+\normpurple{0}=\normblue{11}$:

$$ \begin{array} {c|c|c|c|c|c} & 5 & 5 & 1 & \normpurple{0} & -11 \\ \hline \normred{1} & 5 & 10 & \normgreen{11} & \normblue{11} & \end{array} $$

И, наконец, для последней, шестой ячейки, имеем: $\normred{1}\cdot\normgreen{11}+\normpurple{(-11)}=\normblue{0}$:

$$ \begin{array} {c|c|c|c|c|c} & 5 & 5 & 1 & 0 & \normpurple{-11} \\ \hline \normred{1} & 5 & 10 & 11 & \normgreen{11} &\normblue{0} \end{array} $$

Числа, расположенные во второй строке (между единицей и нулём), есть коэффициенты многочлена, полученного после деления $P(x)$ на $x-1$. 6$) равен единице. В этом случае целочисленные корни многочлена нужно искать среди делителей свободного члена, т.е. среди делителей числа 45. Для заданного многочлена такими корнями могут быть числа $45; \; 15; \; 9; \; 5; \; 3; \; 1$ и $-45; \; -15; \; -9; \; -5; \; -3; \; -1$. Проверим, к примеру, число $1$:

Табл. №1

$$ \begin{array} {c|c|c|c|c|c|c|c} & 1 & 2 & -21 & -20 & 71 & 114 & 45 \\ \hline 1 & 1 & 3 & -18 & -38 & 33 & 147 & 192 \end{array} $$

Как видите, значение многочлена $P(x)$ при $x=1$ равно $192$ (последнее число в второй строке), а не $0$, посему единица не является корнем данного многочлена. Так как проверка для единицы окончилась неудачей, проверим значение $x=-1$. Новую таблицу составлять не будем, а продолжим использование табл. №1, дописав в нее новую (третью) строку. Вторую строку, в которой проверялось значение $1$, выделим красным цветом и в дальнейших рассуждениях использовать её не будем. 2-21x+45$. Проверим еще раз число $-1$:

$$ \begin{array} {c|c|c|c|c|c|c|c} & 1 & 2 & -21 & -20 & 71 & 114 & 45 \\ \hline \normred{1} & \normred{1} & \normred{3} & \normred{-18} & \normred{-38} & \normred{33} & \normred{147} & \normred{192}\\ \hline -1 & 1 & 1 & -22 & 2 & 69 & 45 & 0 \\ \hline -1 & 1 & 0 & -22 & 24 & 45 & 0 & \\ \hline -1 & 1 & -1 & -21 & 45 & 0 & & \\ \hline -1 & 1 & -2 & -19 & 64 & & & \end{array} $$

Проверка окончилась неудачей. Выделим шестую строку красным цветом и попробуем проверить иное число, например, число $3$:

В остатке ноль, посему число $3$ – корень рассматриваемого многочлена. 2+2x-15\right) \end{equation} $$

Проверим ещё раз число $3$:

Полученный результат можно записать так (это продолжение равенства (6)):

$$ \begin{equation} P(x)=(x+1)^3(x-3)\left(x^2+2x-15\right) =(x+1)^3(x-3)(x-3)(x+5) =(x+1)^3(x-3)^2(x+5) \end{equation} $$

Из последней скобки видно, что число $-5$ также является корнем данного многочлена. 2(x+5)$$

Числа $-1$, $3$, $-5$ – корни данного многочлена. Причем, так как скобка $(x+1)$ в третьей степени, то $-1$ – корень третьего порядка; так как скобка $(x-3)$ во второй степени, то $3$ – корень второго порядка; так как скобка $(x+5)$ в первой степени, то $x=-5$ – корень первого порядка (простой корень).

Вообще, обычно оформление таких примеров состоит из таблицы, в которой перебираются возможные варианты корней, и ответа:

Из таблицы следует вывод, полученный нами ранее с подробным решением:

$$ P(x)=(x+1)^3(x-3)\left(x^2+2x-15\right)=(x+1)^3(x-3)^2(x+5)$$

Ответ: $-1$, $3$, $-5$. {n-1}+\ldots+a_{1} x+a_{0}\], и линейный двучлен \[x-s\], и нам надо узнать можно ли их разделить без остатка, или найти частное и остаток. Для решения будет удобно использовать схему Горнера. Метод для решения уравнений по схеме Горнера для деления многочленов путем основан на составлении специальной таблицы.

Вам просто нужно взять исходные данные из ваших примеров и по аналогии вставить их в таблицу:

\[S_{i}\]	коэффициенты многочленов
—	\[a_{n}\]	\[a_{n-1}\]	\[a_{n-2}\]	…	\[a_{0}\]
\[S\]	\[a_{n}=b_{n}\]	\[a_{n-1}+b_{n} \times s=b_{n-1}\]	\[ a_{n-2}+b_{n-1} \ \times s=b_{n-2} \]	…	\[a_{0}+b_{1} \times s=b_{0} \]

На базе составленной таблицы, мы определили коэффициенты деления \[b_{n}, b_{n-1}, \ldots, b_{1}\] от деления многочлена \[P_{n}(x)=a_{n} a^{n}+a_{n-1} x^{n-1}+\ldots+a_{1} x+a_{0}\] на x-s. {n-2}+\ldots+b_{1}\right)
\end{gathered}\]

Таким образом, когда мы применяем схему Горнера, то корни уравнения находим в уравнениях высшей степени с целыми коэффициентами или разложить на простые множители исходный многочлен. В применении схемы Горнера самое сложное — запомнить алгоритм заполнения таблицы и внимательно вписать в неё коэффициенты.

Оценить статью (78 оценок):

Содержание

Введение в метод Хорнера

предпосылки: базовые знания языка Haskell или аналогичного.

«Что делает пустыню прекрасной»,
сказал Маленький принц,
«это то, что где-то она скрывает колодец…»
– Антуан де Сент-Экзюэри, Маленький принц

1.9001. Введение

Цель этой записи в блоге — представить Метод Хорнера для полиномиальное вычисление и полиномиальное деление, а затем доказать отношения эквивалентности между этими двумя типами приложений.

Сообщение в блоге имеет следующую структуру. В разделе 2, мы аргументируем применение метода Хорнера для полиномиальной оценки, а затем получить его определение. Рассмотрев полиномиальное вычисление, мы затем приводим доводы в пользу применение метода Горнера для полиномиального деления и получение его определения в разделе 3. Наконец, мы формулируем и доказать отношение эквивалентности между определением полиномиальной оценки и определение полиномиального деления с использованием метода Хорнера в разделе 4. Пост в блоге завершается Раздел 5. 92 = (3 \cdot 3)\), как его промежуточное Результаты. К счастью, мы можем преобразовать формулу многочлена $p$ таким образом, чтобы операции вычисления показатели степени являются общими для членов. На самом деле, поскольку число умножения на $3$ убывает на $1$ для каждого члена мы можем вложить умножения через такие условия,

\[\начать{выравнивать} \tag{1}\label{eq:polynomial-evaluation-horner-example-formula} p(3) &= 7 \cdot (3 \cdot 3 \cdot 3 \cdot 3) + 2 \cdot (3 \cdot 3 \cdot 3) + 5 \cdot (3 \cdot 3) + 4 \cdot (3) + 6 \\ p(3) &= (7 \cdot (3 \cdot 3 \cdot 3) + 2 \cdot (3 \cdot 3) + 5 \cdot (3) + 4) \cdot 3 + 6 \\ p(3) &= ((7 \cdot (3 \cdot 3) + 2 \cdot (3) + 5) \cdot 3 + 4) \cdot 3 + 6 \\ p(3) &= (((7 \cdot 3 + 2) \cdot 3 + 5) \cdot 3 + 4) \cdot 3 + 6, \конец{выравнивание}\]

, таким образом удаляя любые избыточные умножения, используемые для оценки экспоненты. Формула \ref{eq:полиномиальная-оценка-хорнера-пример-формула} теперь демонстрирует простую индуктивную структуру, которая добавляет один умножение и одно сложение для каждого члена многочлена $п$. В результате теперь мы можем оценить окончательный формула $р$,

\[\начало{уравнение} \tag{2}\label{eq:polynomial-evaluation-horner-example-inductive} p(3) = (((7 \cdot 3 + 2) \cdot 3 + 5) \cdot 3 + 4) \cdot 3 + 6, \конец{уравнение},\]

путем многократного выполнения умножения и сложения, начиная с самый внутренний набор скобок,

\[\начать{выравнивать} \tag{3}\label{eq:polynomial-evaluation-horner-example-calculation} p(3) &= (((7 \cdot 3 + 2) \cdot 3 + 5) \cdot 3 + 4) \cdot 3 + 6 \\ &= ((23 \cdot 3 + 5) \cdot 3 + 4) \cdot 3 + 6 \\ &= (74 \cdot 3 + 4) \cdot 3 + 6 \\ &= 226 \cdot 3 + 6 \\ &= 684. \конец{выравнивание}\]

Если сравнить количество операций, выполненных в первом и последнем уравнение Формула \ref{eq:polynomial-evaluation-horner-example-formula}, мы подсчитайте в общей сложности $14$ в первом и $8$ в последнем. Разница $6$ операций точно соответствует количеству умножения, необходимые для вычисления показателей степени в первом уравнение. Таким образом, наше преобразование полиномиальной формулы в ее индуктивная форма, убрала вычислительные накладные расходы на оценку каждый из показателей по порядку. Наконец, даже доказано что количество сложений и умножений, используемых в этом процедуры, действительно являются наименьшим числом, возможным для оценки многочлен. ¹

При ближайшем рассмотрении промежуточных результатов Формула \ref{eq:полиномиальная-оценка-хорнера-пример-вычисления}, мы можем разобрать рекурсивную схему замены, происходящую под капотом,

\[\начать{выравнивать} \tag{4}\label{eq:polynomial-evaluation-horner-example-substitution-numbers} 7 &= 7\\ 23 &= 7 \cdot 3 + 2\\ 74 &= 23 \cdot 3 + 5\\ 226 &= 74 \cdot 3 + 4\\ 684 &= 226 \cdot 3 + 6. \конец{выравнивание}\]

где каждый промежуточный результат является результатом умножения предыдущий результат на $3$ и добавление следующего коэффициента. Если мы назначим промежуточные значения в левой части, $(7, 23, 74, 226, 684)$, переменной $b_i$, присвоить значение $3$ переменной $k$ и, наконец, присвоить значения, соответствующие коэффициенты $p$, $(7, 2, 5, 4, 6)$, к переменной $a_i$, мы можем повторить Формула \ref{eq:полиномиальная-оценка-хорнера-пример-замещения-номера} вот так,

\[\начать{выравнивать} \tag{5}\label{eq:polynomial-evaluation-horner-example-substitution-variables} б_4 &= а_4\\ b_3 &= b_4 \cdot k + a_3\\ b_2 &= b_3 \cdot k + a_2\\ b_1 &= b_2 \cdot k + a_1\\ b_0 &= b_1 \cdot k + a_0. \конец{выравнивание}\]

Формула \ref{eq:polynomial-evaluation-horner-example-substitution-variables} теперь отражает рекурсивно структурированный и легко обобщаемый, процедура подстановки, где $b_4 = a_4$ базовый случай, а индуктивный случай определяется в терминах следующего коэффициент в многочлене и предыдущий промежуточный результат, $b_3 = b_4 \cdot k + a_3$. Процедура завершается когда он достигает последнего члена многочлена $p$, где $b_0 = b_1 \cdot k + a_0$ является результатом вычисления $p(k)$.

Мы называем описанную выше процедуру методом Хорнера ² для полиномиального оценку и формализовать ее в Хаскелл сначала представив многочлен в виде списка целых чисел,

 type Polynomial = [Int]

, для которого мы определяем процедуру,

 hornersPolyEvalAcc :: Polynomial -> Int -> Int -> Int
hornersPolyEvalAcc cs x a = case cs of
  [] -> а
  (c:cs') -> пусть a' = c + x * a
             в hornersPolyEvalAcc cs' x a'

, который принимает полином, cs , что соответствует $a_i$, целому числу, x , соответствующий $k$, и аккумулятор, a , соответствующий промежуточный результат $b_i$. Как описано выше, он возвращает конечное значение аккумулятора (результат), a в базовом случае, и умножает на на x для каждого рекурсивного вызова и добавляет коэффициент с . Наконец, мы определяем процедуру-оболочку,

hornersPolyEval :: Polynomial -> Int -> Int hornersPolyEval cs x = hornersPolyEvalAcc cs x 0 92+4х+6, \end{уравнение*}\]

для $x = 3$, передав коэффициенты $p$ в виде списка [7, 2, 5, 4, 6] , вместе со значением $x$, 3 , до hornersPolyEval вроде Итак, hornersPolyEval[7, 2, 5, 4, 6] 3 , что дает ожидаемый результат 684 .

Формализовав метод Хорнера для полиномиальной оценки, поскольку процедуры hornersPolyEvalAcc и hornersPolyEval , мы теперь определяем Хорнера метод полиномиального деления.

3. Полиномиальное деление с использованием метода Хорнера

Теперь, когда мы использовали метод Хорнера как эффективную процедуру для оценивая многочлен, используя рекурсивную схему подстановки, мы идем дальше изучить его использование для полиномиального деления.

Согласно определению полиномиальное деление, при делении двух многочленов, $p$ и $d$, $\frac{p(x)}{d(x)}$, где $d \not= 0$, результатом является частное, $q$ и остаток, $r$, удовлетворяющее соотношению,

92+8х+27)+57.

\end{уравнение*}\]

Если рассмотреть промежуточные результаты процедуры, $(2, 8, 27, 57)$, т. е. крайние левые значения каждого шага процедуры, можно составить схему рекурсивной подстановки, аналогичную той, что мы видели в случай полиномиальной оценки,

\[\начать{выравнивать*} 2 &= 2\\ 8 &= 2 \cdot 2 + 4\\ 27 &= 8 \cdot 2 + 11\\ 57 &= 27 \cdot 2 + 3. \конец{выравнивание*}\]

, где каждый промежуточный результат равен предыдущему результату умножить на второй член знаменателя, $х - 2$, плюс следующий коэффициент. На этот раз мы назначаем промежуточные результаты на слева к переменной $b_{i-1}$, последний результат к переменной $r$, второй член знаменателя переменной $k$ и коэффициенты $p$ к переменной $a_i$, что дает следующий набор уравнений,

\[\начать{выравнивать*} б_{2} &= а_3\\ b_{1} &= b_2 \cdot k + a_2\\ b_{0} &= b_1 \cdot k + a_1\\ r &= b_0 \cdot k + a_0. \конец{выравнивание*}\]

Эти уравнения убедительно свидетельствуют о том, что мы можем разделить $p$ с $d$, используя тот же рекурсивная процедура замены, как описано в случае оценки, тратя только одно сложение и умножение за член, что снова сводит количество операций к минимуму. Кроме того, мы можем положить схема подстановки выше в табличном формате, аналогичная полиномиальное длинное деление,

\[\начало{уравнение} \tag{7}\label{eq:horner-div-abstract} \начать{массив}{ с | с с с с } & a_3 & a_2 & a_1 & a_0 \\ k & & b_2 \cdot k & b_1 \cdot k & b_0 \cdot k \\ \hline & a_3 & b_2 \cdot k + a_2 & b_1 \cdot k + a_1 & b_0 \cdot k + a_0 \\ & =b_2 & =b_1 & =b_0 & =r \конец{массив} \конец{уравнение}\]

где коэффициенты полинома расположены в верхней строке, второй член знаменателя крайний слева, а коэффициенты полученного частного, $b_2,b_1,b_0$, а остаток, $r$ в нижней строке таблицы.

Формализуем табличное представление в Формула \ref{eq:horner-div-abstract} в виде следующей процедуры:

 hornersPolyDivAcc :: Polynomial -> Int -> Int -> Polynomial
hornersPolyDivAcc cs x a = case cs of
  [] -> []
  (c:cs') -> пусть a' = c + x * a
              in a' : (hornersPolyDivAcc cs' x a')

, который выполняет ту же схему замены, что и в hornersPolyEvalAcc , за исключением того, что он также агрегирует промежуточные результаты и добавляет их к результирующий полином. Точно так же мы определяем функцию-оболочку, 92 + 11x + 3\) с биномом $d(x) = x - 2$, мы бы передали список [2, 4, 11, 3] в качестве входных данных полином cs и 2 в качестве входного значения x до hornersPolyDiv , из которого мы получили бы список результатов [2, 8, 27, 57] , где [2, 8, 27] — коэффициенты частного, 57 — коэффициенты остаток. Таким образом, мы определили метод Хорнера для полиномиального разделение как процедуры hornersPolyDivAcc и рожкиPolyDiv .

4. Эквивалентность двух процедур Горнера

Из-за сильного сходства между процедурой полиномиального вычисления и процедуры полиномиального деления, мы заинтересован в установлении отношения эквивалентности между ними. Как таким образом, заметим, что последний элемент результирующего многочлена hornersPolyDiv равно результату hornersPolyEval , когда учитывая тот же ввод,

 forall (cs: многочлен) (x: Int),
  hornersPolyEval cs x == last $ hornersPolyDiv cs

Доказательство отношения требует, чтобы мы сначала доказали аналогичное отношение эквивалентности между базовыми процедурами hornersPolyEvalAcc и hornersPolyDivAcc , параметризуется по аккумулятору,

 forall (cs' : полиномиальный) (c x a : Int),
  hornersPolyEvalAcc (c:cs') x a ==
  пусть а' = с + х * а
  in last $ hornersPolyDivAcc cs' x

Эквивалентность можно доказать, сначала доказав основную теорему, используя структурная индукция по многочлену, cs' с последующим анализом случая на многочлен cs в исходной теореме. ⁴ Кстати, приведенная выше теорема также доказывает специфичную для реализации версию теорема о полиномиальном остатке.

5. Заключение

В этом посте мы представили метод Хорнера для полиномиального оценка и полиномиальное деление. Кроме того, мы также заявили и доказал отношение эквивалентности между определением Хорнера метод полиномиального вычисления и полиномиального деления.

В следующем посте мы покажем, как мы может получить Полиномы Тейлора с использованием Метод Горнера.

См. «О двух задачах абстрактной алгебры, связанных с Правило» (1954) Александра Марковича Островского и «Методы вычисления значений многочленов» (1966) Виктора Я. Пана. ↩
См. «Новый метод решения численных уравнений всех порядков, путем непрерывного приближения» (1819) Уильяма Г. Хорнера. ↩
К сожалению, MathJax не поддерживают частичные горизонтальные линии ( \cline ), поэтому мы не можем форматировать полиномиальное длинное деление традиционным способом.
No related posts.