Схема Горнера
Схема Горнера – способ деления многочлена
на бином $x-a$. Работать придётся с таблицей, первая строка которой содержит коэффициенты заданного многочлена. Первым элементом второй строки будет число $a$, взятое из бинома $x-a$:
После деления многочлена n-ой степени на бином $x-a$, получим многочлен, степень которого на единицу меньше исходного, т.е. равна $n-1$. Непосредственное применение схемы Горнера проще всего показать на примерах.
Разделить $5x^4+5x^3+x^2-11$ на $x-1$, используя схему Горнера.
Составим таблицу из двух строк: в первой строке запишем коэффициенты многочлена $5x^4+5x^3+x^2-11$, расположенные по убыванию степеней переменной $x$. Заметьте, что данный многочлен не содержит $x$ в первой степени, т.е. коэффициент перед $x$ в первой степени равен 0. Так как мы делим на $x-1$, то во второй строке запишем единицу:
Начнем заполнять пустые ячейки во второй строке. Во вторую ячейку второй строки запишем число $5$, просто перенеся его из соответствующей ячейки первой строки:
Следующую ячейку заполним по такому принципу: $1\cdot 5+5=10$:
Аналогично заполним и четвертую ячейку второй строки: $1\cdot 10+1=11$:
Для пятой ячейки получим: $1\cdot 11+0=11$:
И, наконец, для последней, шестой ячейки, имеем: $1\cdot 11+(-11)=0$:
Задача решена, осталось только записать ответ:
Как видите, числа, расположенные во второй строке (между единицей и нулём), есть коэффициенты многочлена, полученного после деления $5x^4+5x^3+x^2-11$ на $x-1$. Естественно, что так как степень исходного многочлена $5x^4+5x^3+x^2-11$ равнялась четырём, то степень полученного многочлена $5x^3+10x^2+11x+11$ на единицу меньше, т.е. равна трём. Последнее число во второй строке (ноль) означает остаток от деления многочлена $5x^4+5x^3+x^2-11$ на $x-1$. В нашем случае остаток равен нулю, т.е. многочлены делятся нацело. Этот результат ещё можно охарактеризовать так: значение многочлена $5x^4+5x^3+x^2-11$ при $x=1$ равно нулю.
Можно сформулировать вывод и в такой форме: так как значение многочлена $5x^4+5x^3+x^2-11$ при $x=1$ равно нулю, то единица является корнем многочлена $5x^4+5x^3+x^2-11$.
Разделить многочлен $x^4+3x^3+4x^2-5x-47$ на $x+3$ по схеме Горнера.
Сразу оговорим, что выражение $x+3$ нужно представить в форме $x-(-3)$. В схеме Горнера будет учавствовать именно $-3$. Так как степень исходного многочлена $x^4+3x^3+4x^2-5x-47$ равна четырём, то в результате деления получим многочлен третьей степени:
Полученный результат означает, что
$$x^4+3x^3+4x^2-5x-47=(x+3)(x^3+0\cdot x^2 +4x-17)+4=(x+3)(x^3+4x-17)+4$$
В этой ситуации остаток от деления $x^4+3x^3+4x^2-5x-47$ на $x+3$ равна $4$. Или, что то самое, значение многочлена $x^4+3x^3+4x^2-5x-47$ при $x=-3$ равно $4$. Кстати, это несложно перепроверить непосредственной подстановкой $x=-3$ в заданный многочлен:
$$x^4+3x^3+4x^2-5x-47=(-3)^4+3 \cdot (-3)^3-5 \cdot (-3)-47=4.$$
Т.е. схему Горнера можно использовать, если необходимо найти значение многочлена при заданном значении переменной. Если наша цель – найти все корни многочлена, то схему Горнера можно применять несколько раз подряд, – до тех пор, пока мы не исчерпаем все корни, как рассмотрено в примере №3.
Найти все целочисленные корни многочлена $x^6+2x^5-21x^4-20x^3+71x^2+114x+45$, используя схему Горнера.
Коэффициенты рассматриваемого многочлена есть целые числа, а коэффициент перед старшей степенью переменной (т.е. перед $x^6$) равен единице. В этом случае целочисленные корни многочлена нужно искать среди делителей свободного члена, т.е. среди делителей числа 45. Для заданного многочлена такими корнями могут быть числа $45; \; 15; \; 9; \; 5; \; 3; \; 1$ и $-45; \; -15; \; -9; \; -5; \; -3; \; -1$. Проверим, к примеру, число $1$:
Как видите, значение многочлена $x^6+2x^5-21x^4-20x^3+71x^2+114x+45$ при $x=1$ равно $192$ (последнее число в второй строке), а не $0$, посему единица не является корнем данного многочлена. Так как проверка для единицы окончилась неудачей, проверим значение $x=-1$. Новую таблицу для этого составлять не будем, а продолжим использование табл. №1, дописав в нее новую (третью) строку. Вторую строку, в которой проверялось значение $1$, выделим красным цветом и в дальнейших рассуждениях использовать её не будем.
Можно, конечно, просто переписать таблицу заново, но при заполнении вручную это займет немало времени. Тем более, что чисел, проверка которых окончится неудачей, может быть несколько, и каждый раз записывать новую таблицу затруднительно. При вычислении «на бумаге» красные строки можно просто вычёркивать.
Итак, значение многочлена $x^6+2x^5-21x^4-20x^3+71x^2+114x+45$ при $x=-1$ равно нулю, т.е. число $-1$ есть корень этого многочлена. После деления многочлена $x^6+2x^5-21x^4-20x^3+71x^2+114x+45$ на бином $x-(-1)=x+1$ получим многочлен $x^5+x^4-22x^3+2x^2+69x+45$, коэффициенты которого взяты из третьей строки табл. №2 (см. пример №1). Результат вычислений можно также представить в такой форме:
Продолжим поиск целочисленных корней. Теперь уже нужно искать корни многочлена $x^5+x^4-22x^3+2x^2+69x+45$. Опять-таки, целочисленные корни этого многочлена ищут среди делителей его свободного члена, – числа $45$. Попробуем ещё раз проверить число $-1$. Новую таблицу составлять не будем, а продолжим использование предыдущей табл. №2, т.е. допишем в нее еще одну строку:
Итак, число $-1$ является корнем многочлена $x^5+x^4-22x^3+2x^2+69x+45$. Этот результат можно записать так:
Учитывая равенство (2), равенство (1) можно переписать в такой форме:
Теперь уже нужно искать корни многочлена $x^4-22x^2+24x+45$, – естественно, среди делителей его свободного члена (числа $45$). Проверим еще раз число $-1$:
Число $-1$ является корнем многочлена $x^4-22x^2+24x+45$. Этот результат можно записать так:
С учетом равенства (4), равенство (3) перепишем в такой форме:
Теперь ищем корни многочлена $x^3-x^2-21x+45$. Проверим еще раз число $-1$:
Проверка окончилась неудачей. Выделим шестую строку красным цветом и попробуем проверить иное число, например, число $3$:
В остатке ноль, посему число $3$ – корень рассматриваемого многочлена. Итак, $x^3-x^2-21x+45=(x-3)(x^2+2x-15)$. Теперь равенство (5) можно переписать так:
Проверим ещё раз число $3$:
Полученный результат можно записать так (это продолжение равенства (6)):
Из последней скобки видно, что число $-5$ также является корнем данного многочлена. Можно, конечно, формально продолжить схему Горнера, проверив значение $x=-5$, но необходимости в этом нет. Итак,
Числа $-1; \; 3; \; 5$ – корни данного многочлена. Причем, так как скобка $(x+1)$ в третьей степени, то $-1$ – корень третьего порядка; так как скобка $(x-3)$ во второй степени, то $3$ – корень второго порядка; так как скобка $(x+5)$ в первой степени, то $x=-5$ – корень первого порядка (простой корень).
Вообще, обычно оформление таких примеров состоит из таблицы, в которой перебираются возможные варианты корней, и ответа:
Из таблицы следует вывод, полученный нами ранее с подробным решением:
Убедиться, что числа $2$ и $-5$ являются корнями многочлена $3x^6+9x^5-28x^4+6x^3-30x^2-30x+100$. Разделить заданный многочлен на биномы $x-2$ и $x+5$.
Степень многочлена $3x^6+9x^5-28x^4+6x^3-30x^2-30x+100$ равна $6$. После деления на два заданных бинома степень заданного многочлена уменьшится на $2$, т.е. станет равна $4$.
Конечно, данный метод подбора малоэффективен в общем случае, когда корни не являются целыми числами, но для целочисленных корней метод довольно-таки неплох.
Источник
Научно-исследовательская работа по тема «Схема Горнера»
1.Горнер Вильямc Джордж -английский математик………………………….5
2.1.Уравнения высших степеней……………………………………………….5
2.3.Теоремы для нахождения делителя многочлена…………………………..6
Увлечение математикой начинается с размышления над какой-то интересной задачей или проблемой. Любому завороженному математическими тайнами человеку интересно знать историю математических открытий, разные способы решения задач, уметь использовать математические теоремы для решения сложных задач. Заинтересовался решениями уравнений высших степеней. «В математике нет царских путей» но я решил найти способ решения уравнении высших степеней. Для этого мы с моим учителем решили изучить схему Горнера. В моей работе я рассмотрел уравнения высших степеней, которые на взгляд учащихся старших классов являются сложными, т.к. способы их решения не изучаются в школьной программе.
Актуальность: р ешение многих практических задач сводится к решению различных видов уравнений, которые необходимо научиться решать. Изучив схему Горнера и деление уголком можно научиться решать: уравнения, разложение многочлена на множители, а это позволит сократить дроби с многочленами, доказать что многочлен делится на многочлен и т.д.
Объект : Схема Горнера.
Предмет исследования : уравнения и решение уравнений по схеме Горнера. Цель работы : научиться: — решать уравнения высших степеней по схеме Горнера, не зная решения уравнений школьной программы; -использовать схему Горнера для разложения на множители, что поможет доказать делимость многочлена на одночлен.
-изучить схему Горнера подобрав необходимую литературу;
-выбрать проблемные задачи, после опроса учеников старших классов;
-проанализировать и систематизировать полученную информацию.
Методы исследования: сбор информации, обработка данных, анализ.
Гипотеза: зная схему Горнера можно решить уравнение любой степени с целочисленными корнями.
Источник
Алгоритм Горнера
Для того чтобы понять принцип работы алгоритма (который также называют «схемой Горнера» или «методом Горнера»), разберемся, что с его помощью можно делать, откуда берется этот алгоритм, как именно и почему он работает.
- Алгоритм Горнера помогает решать две алгебраические задачи:
Все это можно делать и без использования алгоритма, однако его преимущество заключается в скорости.
Выведем схему Горнера
Пусть нам нужно найти корни многочлена $P\left(x\right),$ то есть решить уравнение $P\left(x\right)=0.$ $P\left(x\right)$ представим в виде: $$\displaystyle\sum\limits_
По следствию из теоремы Безу, многочлен $P\left(x\right)$ можно представить в виде: $$P\left(x\right) = \left(x-x_<0>\right)Q\left(x\right) + R\left(x\right),$$ где $Q\left(x\right)\ — $ результат деления $P\left(x\right)$ на $\left(x-x_<0>\right),\ R\left(x\right)\ — $ остаток от этого деления. Обозначим $Q\left(x\right)$ как $b_
Алгоритм берет свое начало из теоремы Безу, которая звучит так: если многочлен $P\left(x\right)$ разделить на двучлен $\left(x-x_<0>\right),$ то остаток от этого деления будет равен значению $P\left(x\right)$ на элементе $x_<0>,$ т.е. (остаток)$R\left(x\right) = P\left(x_<0>\right).$
В тождестве $\left(1\right)$ умножим $\left(x-x_<0>\right)$ на $Q\left(x\right)$. Получаем $$a_
| $a_n$ | $a_ | $\ldots$ | $a_0$ | |
| $x_0$ | $b_ | $b_ | $\ldots$ | $R\left(x\right)$ |
|---|
Эта таблица и есть схемой Горнера.
Замечание: помимо значения остатка $R\left(x\right),$ алгоритм дает нам $Q\left(x\right)$ (неполное частное). Также, если остаток $R\left(x\right)=0,$ то $x_ <0>— $ корень многочлена $P\left(x\right).$
Далее, с помощью примеров, рассмотрим, как алгоритм работает на практике.
Примеры решения задач
- Разделить многочлен $P_<5>\left(x\right) = x^5-8x^4+7x^3-4x^2+16x+24$ на $\left(x-2\right).$
Вместо деления уголком, воспользуемся алгоритмом Горнера:
| $1$ | $-8$ | $7$ | $-4$ | $16$ | $24$ |
| $2$ | $1$ |
В ячейки, выделенные розовым, записываем коэффициенты многочлена $P_5\left(x\right),$ а в желтую ячейку — $x_0.$ Оставшееся место в таблице будем заполнять вычислениями. Первое число всегда сносим без изменений.
| $1$ | $-8$ | $7$ | $-4$ | $16$ | $24$ |
| $2$ | $1$ | $-6$ |
$x_0$ умножаем на число в ячейке напротив, складываем со следующим коэффициентом $P_5\left(x\right),$ и под ним записываем результат (в зеленой ячейке). Дальше продолжаем выполнять действия, которые указаны выше. Получаем таблицу:
| $1$ | $-8$ | $7$ | $-4$ | $16$ | $24$ | |
| $2$ | $1$ | $-6$ | $-5$ | $-14$ | $-12$ | $0$ |
Область, выделенная голубым — это получившиеся коэффициенты нового многочлена $Q\left(x\right),$ а фиолетовым — остаток $R\left(x\right).$
Ответ: $P_5\left(x\right) = x^5-8x^4+7x^3-4x^2+16x+24= \\ =\left(x-2\right)\left(x^4-6x^3-5x^2-14x^2-12x\right) + 0.$
Заметим, что степень $Q\left(x\right)$ всегда на $1$ меньше степени $P\left(x\right).$ Также, выше было сказано, что если $R\left(x\right)=0,$ то $x_ <0>— $ корень многочлена. В данном случае $x_<0>$ является корнем $P_<5>\left(x\right).$
Кратность корня определяется количеством нулевых остатков от деления $P\left(x\right)$ на $\left(x-x_<0>\right).$ Воспользуемся схемой Горнера:
| $1$ | $0$ | $-8$ | $14$ | $-9$ | $2$ | |
| $1$ | $1$ | $1$ | $-7$ | $7$ | $-2$ | $0$ |
Так как $R\left(x\right)=0,$ мы можем проверить, является ли $x_0=1$ корнем для уже нового многочлена $Q\left(x\right).$ Продолжаем заполнять таблицу по тому же принципу.
| $1$ | $0$ | $-8$ | $14$ | $-9$ | $2$ | |
| $1$ | $1$ | $1$ | $-7$ | $7$ | $-2$ | $0$ |
| $1$ | $1$ | $2$ | $-5$ | $2$ | $0$ | |
| $1$ | $1$ | $3$ | $-2$ | $0$ | ||
| $1$ | $1$ | $4$ | $2$ |
В последней строке мы получили ненулевой остаток. Значит, вычисления можно закончить. Определяем кратность по количеству нулей на «лесенке». Записываем получившееся разложение: $$P_5\left(x\right) = x^5-8x^3+14x^2-9x+2 = \left(x-1\right)^3\left(x^2+3x-2\right).$$
Ответ: $x_0$ для многочлена $P_5\left(x\right)$ является корнем третьей кратности.
Перефразируем условие задачи для лучшего понимания: при каких $A$ и $B$ число $x_0$ будет корнем $P_4\left(x\right)$, кратности не ниже $2?$ Воспользуемся алгоритмом Горнера.
| $A$ | $0$ | $B$ | $0$ | $1$ | |
| $1$ | $A$ | $A$ | $A+B$ | $A+B$ | $A+B+1$ |
| $1$ | $A$ | $2A$ | $3A+B$ | $4A+2B$ | |
| $1$ | $A$ | $3A$ | $6A+B$ |
Можем сделать вывод, что кратность корня будет не ниже двух тогда и только тогда, когда $\begin
Ответ: $\left(x-1\right)^2$ делит $P_4\left(x\right) \Leftrightarrow A=1,\ B=-2.$ $\left(x-1\right)^3$ не делит $P_4\left(x\right)$ ни при полученных значениях $A$ и $B,$ ни при каких других.
Используем схему Горнера таким же образом, как в примерах выше.
| $1$ | $-2-i$ | $0$ | $-3-2i$ | $5$ | |
| $1-i$ | $1$ | $-1-2i$ | $-3-i$ | $-7$ | $2-7i$ |
- $1-i-2+i = \mathbf<-1-2i>;$
- $\left(-1-2i\right)\left(1-i\right) = -1+i-2i+2i^2 = -1-i-2 = \mathbf<-3-i>;$
- $\left(-3-i\right)\left(1-i\right) = -3+3i-i+i^2 = -3+2i-1 = -4+2i; \\ -4+2i-3-2i = \mathbf<-7>;$
- $\left(-7\right)\left(1-i\right) = -7-7i; \\ -7-7i+5 = \mathbf<2-7i>.$
Ответ: $P_4\left(x\right) = \left(x-\left(1-i\right)\right)\left(x^3+\left(-1-2i\right)x^2+\left(-3-i\right)x-7\right)+\left(2-7i\right);$ $P_4\left(x_0\right) = 2-7i.$
Почему алгоритм Горнера работает?
После ознакомления с примерами решения задач, можно приступить к изучению данного вопроса. Представим многочлен уже привычным нам образом $P\left(x\right) = a_
Почему разложение $P\left(x\right) = \left(x-x_0\right)Q\left(x\right)+R\left(x\right)$ — верно? Начнем с арифметики. Возьмем какое-то натуральное число $a.$ Как гласит нам основная теорема арифметики, его всегда можно представить в виде произведения двух других чисел с остатком, то есть $a = s \cdot q + r.$ Например, $7 = 2 \cdot 3 +1,$ $8 = 4 \cdot 2 + 0.$ Разложение такого типа единственно, причем $0 \leqslant r 0 \right)\big\>,$$ $$\mathcal : s \in \mathcal
,\ t \in \mathcal
Сначала проверим по Горнеру, являются ли $\pm 1$ корнями $P_7\left(x\right).$
| $9$ | $3$ | $-23$ | $4$ | $-5$ | $23$ | $-13$ | $2$ | |
| $1$ | $9$ | $12$ | $-11$ | $-7$ | $-12$ | $11$ | $-2$ | $0$ |
| $1$ | $9$ | $21$ | $10$ | $3$ | $-9$ | $2$ | $0$ | |
| $1$ | $9$ | $30$ | $40$ | $43$ | $34$ | $36$ | ||
| $-1$ | $9$ | $12$ | $-2$ | $5$ | $-14$ | $16$ |
По таблице видно, что $x_0=1\ — $ корень второй кратности, а $x_0=-1$ корнем не является. Получаем разложение: $$P_7\left(x\right) = \left(x-1\right)^<2>g\left(x\right),$$ $$g\left(x\right) = 9x^5+21x^4+10x^3+3x^2-9x+2.$$Также мы определили значения $g\left(1\right) = 36$ и $g\left(-1\right) = 16.$
Для свободного члена $b_0 = 2$ формируем $\mathcal\ — $ множество всех его целых делителей, а для $b_m = 9$ формируем $\mathcal= \<2;\ -2;\ 1;\ -1\>,\ \mathcal
Формируем множество $\mathcal,$ а $t \in \mathcal
Сразу вычеркиваем дроби со значениями $\pm 1.$ То что остается, проверяем на двух тестах:
Теперь, каждое из этих чисел проверим с помощью алгоритма Горнера.
| $9$ | $21$ | $10$ | $3$ | $-9$ | $2$ | |
| $-2$ | $9$ | $3$ | $4$ | $-5$ | $1$ | $0$ |
| $-2$ | $9$ | $-15$ | $34$ | $-73$ | $-145$ | |
| $\displaystyle\frac13$ | $9$ | $6$ | $6$ | $-3$ | $0$ | |
| $\displaystyle\frac13$ | $9$ | $9$ | $9$ | $0$ | ||
| $\displaystyle\frac13$ | $9$ | $12$ | $13$ | |||
| $\displaystyle-\frac13$ | $9$ | $6$ | $7$ |
Нам подходят строки с нулевым остатком. Запишем получившееся разложение: $g\left(x\right) = \left(x-\displaystyle\frac13\right)^2\left(x+2\right)\left(9x^2+9x+9\right) = \\ = 9\left(x-\displaystyle\frac13\right)^2\left(x+2\right)\left(x^2+x+1\right).$
У нас появился квадратный трехчлен, который может дать нам новые корни. Однако у него отрицательный дискриминант, следовательно, корней больше нет.
Ответ: корни $P_7\left(x\right):\ 1;\ -2;\ \displaystyle\frac13.$
Источник