Как найти значение многочлена в точке - Исправление недочетов и поиск решений вместе с Examum.ru

Вычисление значения многочлена. Все ли тривиально в этом вопросе?

Время на прочтение
5 мин

Количество просмотров 46K

Вычисление значения многочлена в точке является одной из простейших классических задач программирования.
При проведении различного рода вычислений часто приходится определять значения многочленов при заданных значениях аргументов. Часто приближенное вычисление функций сводится к вычислению аппроксимирующих многочленов.
Рядового читателя Хабрахабр нельзя назвать неискушенным в применении всяческих извращений. Каждый второй скажет, что многочлен надо вычислять по правилу Горнера. Но всегда есть маленькое «но», всегда ли схема Горнера является самой эффективной?

Я не ставлю цель точно описать алгоритмы для вычисления многочленов, а лишь показать, что в некоторых случаях можно (нужно) применять схемы отличные правила Горнера. Для тех, кого заинтересует материал, в конце статьи приведен список литературы, с которой можно ознакомиться для более детального изучения вопроса.
Кроме того, иногда становиться обидно, что фамилии наших русских математиков остаются малоизвестными. К тому же мне просто приятно рассказать о работах наших математиков.

Схема Горнера

При вычислении значений многочленов очень широкое применение получило правило Горнера. Метод назван в честь британского математика Уильяма Джорджа Горнера.
В соответствии с этим правилом многочлен n-й степени:

${{P}_{n}}(x)={{a}_{0}}{{x}^{n}}+{{a}_{1}}{{x}^{n-1}}+...+{{a}_{n-1}}x+{{a}_{n}}$

представляется в виде

${{P}_{n}}(x)=(...(({{a}_{0}}x+{{a}_{1}})x+{{a}_{2}})x+...+{{a}_{n-1}})x+{{a}_{n}}.$

Вычисление значения многочлена производится в порядке, определяемом скобками. Что имеем? Чтобы вычислить многочлен ${{P}_{n}}(x)$ по схеме Горнера, надо выполнить n умножений и n-k сложений (здесь k – число коэффициентов многочлена, равных 0). Если ${{a}_{0}}=1$ , то умножений будет n-1.
Можно показать, что для вычисления многочленов, общего вида нельзя построить схему более экономичную по числу операций, чем схема Горнера.
Самая большая привлекательность схемы Горнера состоит в простоте алгоритма для вычисления значения многочлена.

Исключения

При вычислении многочленов специального вида может потребоваться меньшее число операций, чем при применении универсальной схемы Горнера. Например, вычисление степени ${{x}^{n}}$ по схеме Горнера означает последовательное перемножение n множителей и требует n-1 умножение. Однако каждый первый читатель скажет, что для вычисления, например, ${{x}^{8}}$ нужно последовательно вычислить ${{x}^{2}}=xcdot x$ , ${{x}^{4}}={{x}^{2}}cdot {{x}^{2}}$ , ${{x}^{8}}={{x}^{4}}cdot {{x}^{4}}$ , т.е. выполнить всего 3 умножения вместо 7.

А есть что-то еще, ведь схема Горнера самая экономичная?

На самом деле все решают объемы вычислений. Если надо вычислить одно значение многочлена, то лучше схемы Горнера ничего не придумано. Но если значения многочлена вычисляются во многих точках, то появляется возможность сэкономить большое число операций умножения за счет предварительных вычислений, выполняемых ровно один раз. Это может значительно ускорить работу программы.

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

Снова замечу, что такие методы вычислений целесообразны при вычислении значений многочлена ${{P}_{n}}(x)$ для большого числа значений x. Выигрыш получается, за счет того, что первый этап для многочлена выполняется лишь один раз. Примером может послужить вычисление элементарных функций, где приближающий многочлен готовиться заранее.

В дальнейших рассуждениях, говоря о количестве операций для вычисления ${{P}_{n}}(x)$ , я буду иметь в виду сложность второго этапа вычислений.

Схема Дж.Тодта для многочленов 6 степени

Имеем следующий многочлен:

${{P}_{6}}(x)={{x}^{6}}+A{{x}^{5}}+B{{x}^{4}}+C{{x}^{3}}+D{{x}^{2}}+Ex+F.$

Для вычислений используем следующие вспомогательные многочлены:

${{p}_{1}}(x)=x(x+{{b}_{1}})$ ,

${{p}_{2}}(x)=({{p}_{1}}+x+{{b}_{2}})({{p}_{1}}+{{b}_{3}})$ ,

${{p}_{3}}(x)=({{p}_{2}}+{{b}_{4}})({{p}_{1}}+{{b}_{5}})+{{b}_{6}}$ .

Коэффициенты ${{b}_{j}}$ определяются методом неопределенных коэффициентов исходя из условия ${{p}_{3}}(x)equiv {{P}_{6}}(x)$ . Из последнего условия составляем систему уравнений, приравнивая коэффициенты при равных степенях многочленов.

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

Говорить об универсальности данной схемы не приходится, но зато читатель наглядно может оценить уменьшение числа операций по сравнению со схемой Горнера.

Схема Ю.Л. Кеткова

Наконец-то, добрался и до наших математиков.

Ю.Л. Кетков дал общее представление многочлена n-й степени для n>5, всегда приводящее к действительным выражениям и требующее для вычисления многочлене n-й степени выполнения [(n+1)/2]+[n/4] умножений и n+1 сложений.

Например, при n=2k схема Кеткова сводится к нахождению многочленов:

${{N}_{2}}(x)=x({{b}_{0}}+x),$

${{N}_{4}}(x)=({{N}_{2}}+{{b}_{1}}+x)({{N}_{2}}+{{b}_{2}})+{{b}_{3}},$

${{N}_{6}}(x)={{N}_{2}}{{N}_{4}}+{{b}_{4}}x+{{b}_{5}},$

${{N}_{2k}}(x)=({{N}_{2}}+{{s}_{k}}{{b}_{2k-2}}){{N}_{2k-2}}+{{r}_{k}}{{b}_{2k-2}}x+{{b}_{2k-1}},$

где ${{r}_{k}}=0$ , ${{s}_{k}}=1$ при k –четном, и ${{r}_{k}}=1$ , ${{s}_{k}}=0$ , если k нечетное (k>2).

Все неизвестные коэффициенты находятся из равенства ${{P}_{n}}(x)={{N}_{2k}}$ . В работах Кеткова для решения получающихся систем дается метод, дающий всегда действительные коэффициенты ${{b}_{j}}$ .

Схемы В.Я. Пана

Э. Белага в своих работах дал строгое доказательство невозможности построения схемы вычисления произвольных многочленов n-й степени, использующей на втором этапе меньше, чем [(n+1)/2]+1 умножений и n сложений.

В.Я. Пан занимался вопросами оптимального вычисления многочленов. В частности, им предложено несколько схем для вычисления действительных многочленов, которые весьма близко подобрались к оценкам Э. Белаги. Приведу некоторые схемы Пана для действительных многочленов.
1. Схема для вычисления многочленов четвертой степени.
Рассматривается многочлен ${{P}_{4}}(x)={{a}_{0}}{{x}^{4}}+{{a}_{1}}{{x}^{3}}+{{a}_{2}}{{x}^{2}}+{{a}_{3}}x+{{a}_{4}}$ .

Представим ${{P}_{4}}(x)$ в виде:

$g(x)=x(x+{{lambda }_{1}}),$

${{P}_{4}}(x)equiv {{a}_{0}}left( left( g(x)+{{lambda }_{2}} right)left( g(x)+x+{{lambda }_{3}} right)+{{lambda }_{4}} right),$

где

${{lambda }_{1}}=frac{{{a}_{1}}-{{a}_{0}}}{2{{a}_{0}}},{{lambda }_{2}}=frac{{{a}_{3}}}{{{a}_{0}}}-{{lambda }_{1}}frac{{{a}_{2}}}{{{a}_{0}}}+({{lambda }_{1}}+1)lambda _{1}^{2},$

${{lambda }_{3}}=frac{{{a}_{2}}}{{{a}_{0}}}-{{lambda }_{1}}({{lambda }_{1}}+1)-{{lambda }_{2}},{{lambda }_{4}}=frac{{{a}_{4}}}{{{a}_{0}}}-{{lambda }_{2}}{{lambda }_{3}}.$

2. Схема для вычисления ${{P}_{n}}(x)$ , nge 5 .
Строим вспомогательные многочлены g(x) , h(x) , ${{p}_{s}}(x)$ :

$g(x)=x(x+{{lambda }_{1}}),h(x)=g(x)+x,{{p}_{0}}(x)=x,$

${{p}_{s}}(x)={{p}_{s-1}}(x)left( (g(x)+{{lambda }_{4s-2}})(h(x)+{{lambda }_{4s-1}})+{{lambda }_{4s}} right)+{{lambda }_{4s+1}}$ , s=1,2,…,k.

Для вычисления значения многочлена используем выражения:

${{P}_{n}}(x)equiv {{a}_{0}}{{p}_{k}}(x)$ , при n=4k+1 ,

${{P}_{n}}(x)equiv {{a}_{0}}x{{p}_{k}}(x)+{{lambda }_{n}}$ , при n=4k+2 ,

${{P}_{n}}(x)equiv {{a}_{0}}left( {{p}_{k}}(x)(g(x)+{{lambda }_{n-1}})+{{lambda }_{n}} right)$ , при n=4k+3 ,

${{P}_{n}}(x)equiv {{a}_{0}}xleft( {{p}_{k}}(x)(g(x)+{{lambda }_{n-2}})+{{lambda }_{n-1}} right)+{{lambda }_{n}}$ , при n=4k+4 ,

Эта схема на втором этапе требует [n/2]+2 умножения и n+1 сложения.

Особенностью данной схемы является то, что коэффициенты ${{lambda }_{j}}$ всегда существуют при nge 5 и действительных коэффициентах исходного многочлена.

У В.Я. Пана существуют и другие схемы для вычисления многочленов, в том числе и для комплексных.

Заключение

Резюмируя сказанное, замечу, что вычисление одного или нескольких значений полинома бесспорно нужно проводить с использованием схемы Горнера.

Однако, если число значений полинома, которые потребуется вычислить велико, а производительность очень важна, то имеет смысл рассмотреть применение специальных методов вычисления многочленов.

Некоторые читатели скажут, что возиться с применением схем, отличных от схемы Горнера, сложно, муторно и не стоит с этим связываться. Однако в реальной жизни встречаются задачи, в которых требуется вычислять просто огромное число значений многочленов с большими степенями (например, на их вычисление могут уходить месяцы), и уменьшение числа умножений в два раза даст существенный выигрыш во времени, даже если вам придется потратить пару дней на реализацию конкретной схемы для вычисления многочленов.

Литература

Кетков Ю.Л. Об одном способе вычисления полиномов на математических машинах. // Известия ВУЗ’ов. Радиофизика, т.1., № 4, 1958
В. Я. Пан, “Вычисление многочленов по схемам с предварительной обработкой коэффициентов и программа автоматического нахождения параметров”, Ж. вычисл. матем. и матем. физ., 2:1 (1962), 133–140
В. Я. Пан, “О способах вычисления значений многочленов”, УМН, 21:1(127) (1966), 103–134
В. Я. Пан, “О вычислении многочленов пятой и седьмой степени с вещественными коэффициентами”, Ж. вычисл. матем. и матем. физ., 5:1 (1965), 116–118
Пан В. Я. Некоторые схемы для вычисления значений полиномов с вещественными коэффициентами. Проблемы кибернетики. Вып. 5. М.: Наука, 1961, 17–29.
Белага Э. Г. О вычислении значений многочлена от одного переменного с предварительной обработкой коэффициентов. Проблемы кибернетики. Вып. 5. М.: Физматгиз, 1961, 7–15.

Источник

Схема Горнера

11 июля 2022

Схема Горнера — это алгоритм для быстрого (счёт идёт на секунды) вычисления значения многочлена

[Pleft( x right)={{a}_{n}}{{x}^{n}}+{{a}_{n-1}}{{x}^{n-1}}+ldots +{{a}_{1}}x+{{a}_{0}}]

в точке $x=a$. Также схема Горнера позволяет быстро (быстрее, чем столбиком) делить многочлен $Pleft( x right)$ на линейные двучлены вида $x-a$, искать остатки от деления и многое другое.

Содержание

Описание Схемы Горнера
Вычисление значения многочлена
Деление многочлена с остатком
Перебор корней уравнения
Разложение на множители
Разложение по степеням
Как всё это работает

1. Описание схемы Горнера

Итак, рассмотрим многочлен

[Pleft( x right)= color{blue}{{a}_{n}}{{x}^{n}}+color{blue}{{a}_{n-1}}{{x}^{n-1}}+ldots +color{blue}{{a}_{1}}x+color{blue}{{a}_{0}}]

Для наглядности коэффициенты выделены синим цветом. Распишем схему Горнера для многочлена $Pleft( x right)$ в точке $x=color{red}{a}$. Для этого заполним таблицу

[begin{array}{c|c|c|c|c|c|c} {} & color{blue}{{a}_{n}} & color{blue}{{a}_{n-1}} & color{blue}{{a}_{n-2}} & ldots & color{blue}{{a}_{1}} & color{blue}{{a}_{0}} \ hlinecolor{red}{a} & {} & {} & {} & {} & {} & {} \ end{array}]

В первой строке мы видим коэффициенты многочлена $Pleft( x right)$ в порядке убывания степеней. Таких коэффициентов всегда на один больше, чем степень многочлена: для квадратного многочлена всего 3 коэффициента, для кубического — уже 4, и т.д.

Во второй строке таблицы мы вписываем лишь число $color{red}{a}$ в самой левой клетке. Остальные клетки заполняются последовательно по следующему алгоритму.

В первую свободную клетку мы переносим элемент из верхней строки без изменений. Назовём этот элемент ${{b}_{n-1}}$ — дальше вы поймёте, зачем нужна такая нумерация:

Вторая клетка — элемент ${{b}_{n-2}}$ — считается по формуле ${{b}_{n-2}}={{b}_{n-1}}cdot color{red}{a}+color{blue}{{a}_{n-1}}$. Другими словами, берём элемент слева, умножаем на число $a$ и добавляем элемент сверху:

Далее находим элемент ${{b}_{n-3}}$ по аналогичной формуле: ${{b}_{n-3}}={{b}_{n-2}}cdot color{red}{a}+color{blue}{{a}_{n-2}}$. Заносим результат в третью клетку:

Аналогично находим элементы ${{b}_{n-4}}$, ${{b}_{n-5}}$ и далее. Берём элемент слева, умножаем на исходное число $color{red}{a}$, добавляем элемент сверху, результат записываем в клетку:

[{{b}_{k-1}}={{b}_{k}}cdotcolor{red}{a}+color{blue}{{a}_{k}}]

В какой-то момент мы доберёмся до элемента ${{b}_{0}}$, который находится в клетке под коэффициентом $color{blue}{{a}_{1}}$:

Элемент в последней клетке считается по той же схеме: ${{b}_{0}}cdot color{red}{a}+color{blue}{{a}_{0}}$. Обозначим его буквой $r$:

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

Схема заполнения этой таблицы как раз и называется схемой Горнера. Найденные элементы ${{b}_{n-1}}$, …, ${{b}_{0}}$ и $r$ позволяют переписать исходный многочлен $Pleft( x right)$ в виде

[Pleft( x right)=left( {{b}_{n-1}}{{x}^{n-1}}+ldots +{{b}_{1}}x+{{b}_{0}} right)left( x-color{red}{a} right)+r]

Такая запись оказывается грозным оружием для решения задач с многочленами, если знать её свойства. И сегодня мы изучим все эти свойства, но сначала немного практики.

Пример 1. Простой многочлен

Заполните таблицу по схеме Горнера для многочлена

[Pleft( x right)=2{{x}^{4}}-7{{x}^{3}}+{{x}^{2}}+2x-3]

в точке $x=3$.

Решение. Для начала аккуратно запишем коэффициенты исходного многочлена. Для наглядности они вновь помечены синим:

[Pleft( x right)= color{blue}{2}cdot {{x}^{4}}+left( color{blue}{-7} right)cdot {{x}^{3}}+color{blue}{1}cdot {{x}^{2}}+color{blue}{2} cdot x+left( color{blue}{-3} right)]

Составим таблицу. Поскольку степень многочлена $deg Pleft( x right)=4$, в таблице будет пять основных столбцов и один дополнительный столбец слева, в котором мы запишем число $x=color{red}{3}$:

[begin{array}{c|c|c|c|c|c} {} & color{blue}{2} & color{blue}{-7} & color{blue}{1} & color{blue}{2} & color{blue}{-3} \ hlinecolor{red}{3} & {} & {} & {} & {} & {} \ end{array}]

Заполняем пустые клетки во второй строке. В первую клетку переносим без изменений элемент сверху:

[begin{array}{c|c|c|c|c|c} {} & color{blue}{2} & color{blue}{-7} & color{blue}{1} & color{blue}{2} & color{blue}{-3} \ hlinecolor{red}{3} & 2 & {} & {} & {} & {} \ end{array}]

Элемент во второй клетке считается по формуле $2cdot color{red}{3}+left( color{blue}{-7} right)=-1$:

[begin{array}{c|c|c|c|c|c} {} & color{blue}{2} & color{blue}{-7} & color{blue}{1} & color{blue}{2} & color{blue}{-3} \ hlinecolor{red}{3} & 2 & -1 & {} & {} & {} \ end{array}]

Третью и четвёртую клетку заполняем аналогично: сначала $-1cdot color{red}{3}+color{blue}{1}=-2$, затем $-2cdot color{red}{3}+color{blue}{2}=-4$:

[begin{array}{c|c|r|r|r|c} {} & color{blue}{2} & color{blue}{-7} & color{blue}{1} & color{blue}{2} & color{blue}{-3} \ hlinecolor{red}{3} & 2 & -1 & -2 & -4 & {} \ end{array}]

Наконец, последняя клетка: $-4cdot color{red}{3}+left( color{blue}{-3} right)=-15$:

[begin{array}{c|c|r|r|r|r} {} & color{blue}{2} & color{blue}{-7} & color{blue}{1} & color{blue}{2} & color{blue}{-3} \ hlinecolor{red}{3} & 2 & -1 & -2 & -4 & -15 \ end{array}]

Готово! Мы заполнили таблицу по схеме Горнера.

Пример 2. Пропущенные коэффициенты

Заполните таблицу по схеме Горнера для многочлена

[Pleft( x right)={{x}^{4}}+3{{x}^{3}}-4]

в точке $x=1$.

Решение. Обратите внимание: в записи многочлена отсутствуют одночлены ${{x}^{2}}$ и $x$. Другими словами, коэффициенты в этих двух одночленах равны нулю:

[Pleft( x right)= color{blue}{1}cdot {{x}^{4}}+color{blue}{3}cdot {{x}^{3}}+color{blue}{0}cdot {{x}^{2}}+color{blue}{0} cdot x+left( color{blue}{-4} right)]

Для наглядности мы вновь отметили коэффициенты синим цветом — всего их снова пять, т.е. на один больше степени многочлена. И все они переносятся в таблицу. Пропуск нулевых коэффициентов будет грубой ошибкой:

[begin{array}{c|c|c|c|c|c} {} & color{blue}{1} & color{blue}{3} & color{blue}{0} & color{blue}{0} & color{blue}{-4} \ hlinecolor{red}{1} & {} & {} & {} & {} & {} \ end{array}]

Заполняем таблицу по схеме Горнера. Первый элемент переносим сверху:

[begin{array}{c|c|c|c|c|c} {} & color{blue}{1} & color{blue}{3} & color{blue}{0} & color{blue}{0} & color{blue}{-4} \ hlinecolor{red}{1} & 1 & {} & {} & {} & {} \ end{array}]

Второй, третий и четвёртый элемент считаем по формуле: $1cdot color{red}{1}+color{blue}{3}=4$; $4cdot color{red}{1}+color{blue}{0}=4$; $4cdot color{red}{1}+color{blue}{0}=4$:

[begin{array}{c|c|c|c|c|c} {} & color{blue}{1} & color{blue}{3} & color{blue}{0} & color{blue}{0} & color{blue}{-4} \ hlinecolor{red}{1} & 1 & 4 & 4 & 4 & {} \ end{array}]

Наконец, последний элемент таблицы: $4cdot color{red}{1}+left( color{blue}{-4} right)=0$:

[begin{array}{c|c|c|c|c|r} {} & color{blue}{1} & color{blue}{3} & color{blue}{0} & color{blue}{0} & color{blue}{-4} \ hlinecolor{red}{1} & 1 & 4 & 4 & 4 & 0 \ end{array}]

Готово! Таблица заполнена, последний элемент оказался равен нулю. И это не случайно. Скоро узнаем почему.:)

2. Вычисление значения многочлена

Чтобы понять, зачем нужна схема Горнера, давайте вкратце повторим всю цепочку рассуждений. Берём произвольный многочлен

[Pleft( x right)= color{blue}{{a}_{n}}{{x}^{n}}+color{blue}{{a}_{n-1}}{{x}^{n-1}}+ldots +color{blue}{{a}_{1}}x+color{blue}{{a}_{0}}]

и произвольную точку $x=color{red}{a}$. Составляем таблицу:

Найденные коэффициенты ${{b}_{n-1}}$, …, ${{b}_{0}}$, $r$ позволяют переписать многочлен $Pleft( x right)$ в новом виде:

[Pleft( x right)=left( {{b}_{n-1}}{{x}^{n-1}}+ldots +{{b}_{1}}x+{{b}_{0}} right)left( x-color{red}{a} right)+r]

Но чем так примечательна эта запись? В ближайших четырёх пунктах мы детально разберём все её свойства. И начнём с самого простого. Подставим в эту новую запись число $x=color{red}{a}$, т.е. вычислим $Pleft( color{red}{a} right)$:

[Pleft( color{red}{a} right)=left( {{b}_{n-1}}{color{red}{a}^{n-1}}+ldots +{{b}_{1}}color{red}{a}+{{b}_{0}} right)left( color{red}{a}-color{red}{a} right)+r=r]

Итак, последнее число $r$ в таблице — это значение многочлена $Pleft( x right)$ в точке $x=color{red}{a}$:

[Pleft( color{red}{a} right)=r]

А это значит, что благодаря схеме Горнера можно считать значения многочленов быстро (нет операции возведения в степень) и надёжно (в сложении мы ошибаемся реже, чем в умножении).

Так, из Примера 1 следует, что значение многочлена

[Pleft( x right)=2{{x}^{4}}-7{{x}^{3}}+{{x}^{2}}+2x-3]

в точке $x=3$ равно

[Pleft( 3 right)=r=-15]

Сравните это с прямой подстановкой $x=3$ в многочлен:

[begin{align} Pleft( 3 right) &=2cdot {{3}^{4}}-7cdot {{3}^{3}}+{{3}^{2}}+2cdot 3-3= \ &=2cdot 81-7cdot 27+left( 9+6-3 right)= \ &=162-189+12= \ &=-15 end{align}]

Результат один и тот же, но объём вычислений вырос на порядок.

Пример 3. «Некрасивые» значения

С помощью схемы Горнера найдите значение многочлена

[Pleft( x right)=8{{x}^{4}}-12{{x}^{3}}-24{{x}^{2}}+11x+7]

в точке $x=2,5$.

Решение. Выделим коэффициенты многочлена

[Pleft( x right)= color{blue}{8}cdot {{x}^{4}}+left( color{blue}{-12} right)cdot {{x}^{3}}+left( color{blue}{-24} right)cdot {{x}^{2}}+color{blue}{11} cdot x+color{blue}{7}]

и заполним таблицу для $x=color{red}{2,5}$:

[begin{array}{c|c|c|c|c|c} {} & color{blue}{8} & color{blue}{-12} & color{blue}{-24} & color{blue}{11} & color{blue}{7} \ hlinecolor{red}{2,5} & 8 & 8 & -4 & 1 & 9,5 \ end{array}]

Итого значение многочлена $Pleft( color{red}{2,5} right)=9,5$. Точно такое же значение можно получить прямой подстановкой, но вычисления будут настолько громоздкими, что мы не будем приводить их.

3. Деление многочлена с остатком

Напомню, что разделить многочлен $color{blue}{Pleft( x right)}$ на многочлен $color{red}{Aleft( x right)}$ с остатком — значит найти многочлены $Qleft( x right)$ и $Rleft( x right)$ такие, что

[color{blue}{Pleft( x right)}=Qleft( x right)cdot color{red}{Aleft( x right)}+Rleft( x right)]

причём степень многочлена $Rleft( x right)$ строго меньше степени делителя $color{red}{Aleft( x right)}$:

[deg Rleft( x right) lt deg color{red}{Aleft( x right)}]

Многочлен $Qleft( x right)$ называют неполным частным, $Rleft( x right)$ — остатком от деления. Можно показать, что $Qleft( x right)$ и $Rleft( x right)$ определены однозначно для исходных многочленов $color{blue}{Pleft( x right)}$ и $color{red}{Aleft( x right)}$.

3.1. Случай линейного делителя

Пусть $Aleft( x right)=x- color{red}{a}$ — линейный двучлен. Очевидно, его степень $deg Aleft( x right)=1$.

Рассмотрим произвольный многочлен

[Pleft( x right)= color{blue}{{a}_{n}}{{x}^{n}}+color{blue}{{a}_{n-1}}{{x}^{n-1}}+ldots +color{blue}{{a}_{1}}x+color{blue}{{a}_{0}}]

и составим таблицу для $x=color{red}{a}$ по схеме Горнера:

Получим новую запись многочлена $Pleft( x right)$:

[Pleft( x right)=left( {{b}_{n-1}}{{x}^{n-1}}+ldots +{{b}_{1}}x+{{b}_{0}} right)left( x-color{red}{a} right)+r]

где $r$ — обычное число, т.е. $deg r=0 lt deg Aleft( x right)$. Но тогда многочлен

[Qleft( x right)={{b}_{n-1}}{{x}^{n-1}}+{{b}_{n-2}}{{x}^{n-1}}+ldots +{{b}_{1}}x+{{b}_{0}}]

является неполным частным при делении $Pleft( x right)$ на двучлен $x-color{red}{a}$, а число $r$ — остаток этого деления:

[Pleft( x right)=Qleft( x right)cdot left( x-color{red}{a} right)+r]

Итак, схема Горнера позволяет быстро находить неполное частное и остаток от деления произвольного многочлена $Pleft( x right)$ на двучлен $x-color{red}{a}$.

Пример 4. Деление с остатком

Найдите частное и остаток при делении многочлена

[{{x}^{4}}-2{{x}^{3}}+4{{x}^{2}}-6x+10]

На многочлен $x-1$.

Решение. Выделим синим цветом коэффициенты исходного многочлена:

[color{blue}{1}cdot {{x}^{4}}+left( color{blue}{-2} right)cdot {{x}^{3}}+color{blue}{4}cdot {{x}^{2}}+left( color{blue}{-6} right)cdot x+color{blue}{10}]

Заполним таблицу по схеме Горнера для $x=color{red}{1}$:

[begin{array}{c|c|r|c|r|c} {} & color{blue}{1} & color{blue}{-2} & color{blue}{4} & color{blue}{-6} & color{blue}{10} \ hlinecolor{red}{1} & 1 & -1 & 3 & -3 & 7 \ end{array}]

Первые четыре числа — это коэффициенты многочлена-частного. Отметим их зелёным цветом:

[begin{array}{c|c|r|c|r|c} {} & color{blue}{1} & color{blue}{-2} & color{blue}{4} & color{blue}{-6} & color{blue}{10} \ hlinecolor{red}{1} & color{#green}{1} & color{#green}{-1} & color{#green}{3} & color{#green}{-3} & 7 \ end{array}]

Остаток от деления равен $r=7$. Составим многочлен-частное:

[Qleft( x right)= color{#green}{1}cdot {{x}^{3}}+left( color{#green}{-1} right)cdot {{x}^{2}}+color{#green}{3}cdot x+left( color{#green}{-3} right)]

Очевидно, при делении на линейный двучлен степень частного должна быть на единицу меньше степени исходного многочлена. Так и получилось:

[deg Qleft( x right)=4-1=3]

Пример 5. Проверка делимости

Убедитесь, что многочлен

[{{x}^{5}}-6{{x}^{4}}+16{{x}^{2}}-33{{x}^{2}}+44x-28]

делится на двучлен ${{left( x-2 right)}^{2}}$.

Решение. Многочлен делится без остатка на ${{left( x-2 right)}^{2}}$, если сначала он делится на двучлен $x-2$, а затем частное вновь делится на $x-2$. Следовательно, решение состоит из двух шагов.

Первый шаг: выделим коэффициенты исходного многочлена

[color{blue}{1}cdot {{x}^{5}}+left( color{blue}{-6} right)cdot {{x}^{4}}+color{blue}{16}cdot {{x}^{2}}+left( color{blue}{-33} right)cdot {{x}^{2}}+color{blue}{52} cdot x+left( color{blue}{-36} right)]

[begin{align}color{blue}{1}cdot {{x}^{5}} &+left( color{blue}{-6} right)cdot {{x}^{4}}+color{blue}{16}cdot {{x}^{2}}+ \ &+left( color{blue}{-33} right)cdot {{x}^{2}}+color{blue}{52} cdot x+left( color{blue}{-36} right) \ end{align}]

Составим таблицу для $x=color{red}{2}$. В ней будет 6 основных столбцов:

[begin{array}{c|c|c|c|c|c|c} {} & color{blue}{1} & color{blue}{-6} & color{blue}{16} & color{blue}{-33} & color{blue}{52} & color{blue}{-36} \ hlinecolor{red}{2} & {} & {} & {} & {} & {} & {} \ end{array}]

Заполним все пустые клетки по схеме Горнера:

[begin{array}{c|c|c|c|r|c|c} {} & color{blue}{1} & color{blue}{-6} & color{blue}{16} & color{blue}{-33} & color{blue}{52} & color{blue}{-36} \ hlinecolor{red}{2} & color{green}{1} & color{green}{-4} & color{green}{8} & color{green}{-17} & color{green}{18} & 0 \ end{array}]

Получили остаток $r=0$, поэтому исходный многочлен действительно делится на $x-color{red}{2}$, а частное равно

[Qleft( x right)= color{green}{1}cdot {{x}^{4}}+left( color{green}{-4} right)cdot {{x}^{3}}+color{green}{8}cdot {{x}^{2}}+left( color{green}{-17} right) cdot x+color{green}{18}]

Следовательно, исходный многочлен можно представить так:

[begin{align} & {{x}^{5}}-6{{x}^{4}}+16{{x}^{2}}-33{{x}^{2}}+44x-28= \ = & left( {{x}^{4}}-4{{x}^{3}}+8{{x}^{2}}-17x+18 right)cdot left( x-color{red}{2} right) \ end{align}]

Второй шаг: выделяем коэффициенты и заполняем ту же самую таблицу, но уже для многочлена $Qleft( x right)$.

[Qleft( x right)= color{blue}{1}cdot {{x}^{4}}+left( color{blue}{-4} right)cdot {{x}^{3}}+color{blue}{8}cdot {{x}^{2}}+left( color{blue}{-17} right) cdot x+color{blue}{18}]

Но все коэффициенты в нужном количестве уже присутствуют в таблице, которую мы получили на предыдущем шаге. А потому достаточно приписать к этой таблице ещё одну строку и вновь заполнить её для $x=color{red}{2}$:

[begin{array}{c|c|c|c|r|c|c} {} & 1 & -6 & 16 & -33 & 52 & -36 \ hlinecolor{red}{2} & color{blue}{1} & color{blue}{-4} & color{blue}{8} & color{blue}{-17} & color{blue}{18} & 0 \ hlinecolor{red}{2} & color{green}{1} & color{green}{-2} & color{green}{4} & color{green}{-9} & 0 & {} \ end{array}]

Остаток от деления равен нулю, поэтому многочлен $Qleft( x right)$ делится на $x-color{red}{2}$, и его можно переписать так:

[Qleft( x right)=left( color{green}{1}cdot {{x}^{3}}+left( color{green}{-2} right){{x}^{2}}+color{green}{4} cdot x+left( color{green}{-9} right) right)cdot left( x-color{red}{2} right)]

Возвращаясь к исходному многочлену, получим

[begin{align} & {{x}^{5}}-6{{x}^{4}}+16{{x}^{2}}-33{{x}^{2}}+44x-28= \ = & left( {{x}^{3}}-2{{x}^{2}}+4x-9 right)cdot {{left( x-color{red}{2} right)}^{2}} \ end{align}]

Такая запись, как и приведённая выше таблица, доказывает, что исходный многочлен делится на ${{left( x-color{red}{2} right)}^{2}}$.

Обратите внимание: на каждом следующем шаге количество коэффициентов уменьшается на единицу:

В первой строке мы выписали все 6 коэффициентов исходного многочлена.
Во второй строке осталось лишь 5 коэффициентов, а последнее число — остаток.
Третья срока — 4 коэффициента и вновь остаток.

Всё это пригодится нам в следующем пункте.

4. Перебор корней уравнения

До сих пор мы применяли схему Горнера для некоторой точки $x=color{red}{a}$, которая была прямо указана в условии задачи. Но что если найти такую точку — как раз и есть условие задачи?

Рассмотрим уравнение

[color{blue}{{a}_{n}}{{x}^{n}}+color{blue}{{a}_{n-1}}{{x}^{n-1}}+ldots +color{blue}{{a}_{1}}x+color{blue}{{a}_{0}}=0]

Число $x=color{red}{a}$ будет корнем этого уравнения, если $Pleft( color{red}{a} right)=0$. Это значит, что последний элемент в схеме Горнера должен быть равен нулю:

Следовательно, мы можем быстро проверить, является ли число $x=color{red}{a}$ корнем уравнения. Достаточно просто подставить его в таблицу и найти последний элемент.

Кроме того, мы знаем, что последний элемент — это остаток $r$. При $r=color{green}{0}$ исходное уравнение примет вид

[left( {{b}_{n-1}}{{x}^{n-1}}+ldots +{{b}_{1}}x+{{b}_{0}} right)left( x-color{red}{a} right)=0]

Произведение равно нулю тогда и только тогда, когда хотя бы один из множителей равен нулю. Откуда либо $x-color{red}{a}=0$ (этот случай мы уже разобрали), либо

[color{blue}{{b}_{n-1}}{{x}^{n-1}}+ldots +color{blue}{{b}_{1}}x+color{blue}{{b}_{0}}=0]

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

Более того: этот перебор можно ускорить. Но об этом чуть позже. Сначала рассмотрим пару простых примеров.

Пример 6. Уравнение третьей степени

Решите уравнение:

[{{x}^{3}}+9{{x}^{2}}+23x+15=0]

Решение. Заметим, что все коэффициенты многочлена положительны, поэтому уравнение не имеет положительных корней. Иначе, если $x gt 0$, левая часть равенства представляет собой сумму положительных чисел, которая никогда не равна нулю.

Рассмотрим отрицательные числа. Начнём с $x=color{red}{-1}$:

[begin{array}{c|c|c|c|c} {} & color{blue}{1} & color{blue}{9} & color{blue}{23} & color{blue}{15} \ hlinecolor{red}{-1} & 1 & 8 & 15 & color{green}{0} \ end{array}]

Получили $r=color{green}{0}$. Следовательно, $x=color{red}{-1}$ — корень, и всё уравнение можно переписать так:

[left( {{x}^{2}}+8x+15 right)left( x+1 right)=0]

Далее уравнение разделяется на линейное $x+1=0$, которое мы уже решили, и квадратное

[{{x}^{2}}+x+15=0]

Такое уравнение можно решить через дискриминант или по теореме Виета. Получим корни $x=-3$ и $x=-5$.

Окончательный ответ: $x=-1$, $x=-3$, $x=-5$.

Впрочем, с тем же успехом мы могли продолжить решение по схеме Горнера:

[begin{array}{r|c|c|c|c} {} & color{blue}{1} & color{blue}{9} & color{blue}{23} & color{blue}{15} \ hlinecolor{red}{-1} & 1 & 8 & 15 & color{green}{0} \ hlinecolor{red}{-3} & 1 & 5 & color{green}{0} & {} \ hlinecolor{red}{-5} & 1 & color{green}{0} & {} & {} \ end{array}]

При этом уравнение примет вид

[left( x+3 right)left( x+5 right)left( x+1 right)=0]

По сути, мы получили разложение на множители. И чуть ниже об этом будет отдельный пункт.

Пример 7. Ещё одно уравнение

Решите уравнение:

[2{{x}^{3}}-{{x}^{2}}-5x-2=0]

Решение. В этот раз мы видим, что корни вполне могут быть положительными. Начнём с $x=color{red}{1}$:

[begin{array}{c|c|r|r|r} {} & color{blue}{2} & color{blue}{-1} & color{blue}{-5} & color{blue}{-2} \ hlinecolor{red}{1} & 2 & 1 & -4 & color{red}{-6} \ end{array}]

Получили $r=color{red}{-6}ne 0$. Следовательно, $x=color{red}{1}$ не является корнем. Проверим $x=color{red}{2}$:

[begin{array}{c|c|r|r|r} {} & color{blue}{2} & color{blue}{-1} & color{blue}{-5} & color{blue}{-2} \ hlinecolor{red}{1} & 2 & 1 & -4 & color{red}{-6} \ hlinecolor{red}{2} & 2 & 3 & 1 & color{green}{0} \ end{array}]

Обратите внимание: при заполнении третьей строки таблицы мы игнорируем вторую строку, где нас постигла неудача. И если бы мы могли стирать строки, то схема Горнера выглядела бы так:

[begin{array}{c|c|r|r|r} {} & color{blue}{2} & color{blue}{-1} & color{blue}{-5} & color{blue}{-2} \ hlinecolor{red}{2} & 2 & 3 & 1 & color{green}{0} \ end{array}]

В любом случае мы получили $r=color{green}{0}$, поэтому $x=color{red}{2}$ — корень, и уравнение примет вид

[left( 2{{x}^{2}}+3x+1 right)left( x-2 right)=0]

Далее можно решить квадратное уравнение через дискриминант, а можно продолжить заполнять таблицу. Например, для $x=color{red}{-1}$:

[begin{array}{r|c|r|r|r} {} & 2 & -1 & -5 & -2 \ hline1 & 2 & 1 & -4 & -6 \ hline2 & color{blue}{2} & color{blue}{3} & color{blue}{1} & color{green}{0} \ hline-1 & 2 & 1 & color{green}{0} & {} \ end{array}]

Вновь получили ноль в последней клетке, поэтому $x=color{red}{-1}$ — тоже корень, а уравнение примет вид

[left( 2x+1 right)left( x+1 right)left( x-2 right)=0]

Теперь ответ очевиден: $x=2$, $x=-1$, $x=-0,5$.

Помните: «неудачные» строки — это нормально. Их бывает много. Главное при переборе корней — игнорировать такие строки и заполнять таблицу так, будто этих строк не существует.

4.1. Теорема Безу

Теорема Безу и следствия из неё позволяет значительно сузить круг потенциальных корней.

Теорема Безу. Остаток от деления многочлена

[Pleft( x right)={{a}_{n}}{{x}^{n}}+{{a}_{n-1}}{{x}^{n-1}}+ldots +{{a}_{1}}x+{{a}_{0}}]

на двучлен $x-a$ равен $Pleft( a right)$.

Несложно заметить, что схема Горнера и следующая из неё запись многочлена

[Pleft( x right)=left( {{b}_{n-1}}{{x}^{n-1}}+ldots +{{b}_{1}}x+{{b}_{0}} right)left( x-color{red}{a} right)+r]

является прямым доказательством этой теоремы. Действительно, если подставить в эту запись значение $x=color{red}{a}$, мы получим

[Pleft( color{red}{a} right)=left( {{b}_{n-1}}color{red}{{a}^{n-1}}+ldots +{{b}_{1}}color{red}{a}+{{b}_{0}} right)left( color{red}{a}-color{red}{a} right)+r=r]

У теоремы Безу огромное количество полезных приложений — см. урок «Теорема Безу». Сейчас же нас интересует не сама теорема, а следствие из неё, связанное с корнями многочлена.

Пусть $x=color{red}{a}$ — корень многочлена $Pleft( x right)$. Распишем многочлен по схеме Горнера для $x=color{red}{a}$:

[Pleft( x right)=left( {{b}_{n-1}}{{x}^{n-1}}+ldots +{{b}_{1}}x+{{b}_{0}} right)left( x-color{red}{a} right)]

Поскольку $x=color{red}{a}$ — корень, остаток $r=0$, и мы получили разложение многочлена $Pleft( x right)$ на множители. А теперь выполним обратную операцию — раскроем скобки и приведём подобные слагаемые:

[Pleft( x right)={{b}_{n-1}}{{x}^{n}}+ldots -color{red}{a}cdot {{b}_{0}}]

Получается, что корень $x=color{red}{a}$ является делителем свободного члена $Pleft( x right)$. Более того, можно показать, что в многочлене

[Pleft( x right)= color{blue}{{a}_{n}}{{x}^{n}}+color{blue}{{a}_{n-1}}{{x}^{n-1}}+ldots +color{blue}{{a}_{1}}x+color{blue}{{a}_{0}}]

с целыми коэффициентами $color{blue}{{a}_{n}}$, …, $color{blue}{{a}_{0}}$ все рациональные корни имеют вид

[x=frac{m}{n}]

где $min mathbb{Z}$ — делитель свободного члена $color{blue}{{a}_{0}}$, а $nin mathbb{N}$ — делитель старшего коэффициента $color{blue}{{a}_{n}}$.

И хоть при первом взгляде на все эти рассуждения они могут показаться сложными, на практике теорема Безу значительно упрощает поиск корней. Взгляните на примеры.:)

Пример 8. Сплошной перебор

Решите уравнение:

[{{x}^{5}}+8{{x}^{4}}+24{{x}^{3}}+35{{x}^{2}}+28x+12=0]

Решение. Слева от знака равенства стоит многочлен пятой степени. Старший коэффициент многочлена ${{a}_{5}}=color{blue}{1}$, свободный член ${{a}_{0}}=color{blue}{12}$. Если такой многочлен имеет рациональные корни вида

[x=frac{m}{n}]

то $n=1$ — это единственный натуральный делитель для ${{a}_{5}}=color{blue}{1}$. А вот число $m$ будем искать среди делителей числа ${{a}_{0}}=color{blue}{12}$:

[m=pm 1, pm 2, pm 3, pm 4, pm 6, pm 12.]

Итого 12 вариантов. Далее заметим, что все коэффициенты исходного многочлена положительны, поэтому достаточно проверить лишь отрицательные корни. Начнём с $x=color{red}{-1}$, затем $x=color{red}{-2}$, $x=color{red}{-3}$ и т.д.:

[begin{array}{r|c|c|c|c|c|c} {} & color{blue}{1} & color{blue}{8} & color{blue}{24} & color{blue}{35} & color{blue}{28} & color{blue}{12} \ hline color{red}{-1} & 1 & 7 & 17 & 18 & 10 & color{red}{2} \ hline color{red}{-2} & 1 & 6 & 12 & 11 & 6 & color{green}{0} \ hline color{red}{-3} & 1 & 3 & 3 & 2 & color{green}{0} & {} \ end{array}]

Как видим, вариант $x=color{red}{-1}$ не подошёл, поэму строку с проверкой этого числа можно вычеркнуть. Зато $x=color{red}{-2}$ и $x=color{red}{-3}$ — корни. Более того: можно повторно проверить $x=color{red}{-2}$. Получим интересный результат:

[begin{array}{r|c|c|c|c|c|c} {} & color{blue}{1} & color{blue}{8} & color{blue}{24} & color{blue}{35} & color{blue}{28} & color{blue}{12} \ hline color{red}{-2} & 1 & 6 & 12 & 11 & 6 & color{green}{0} \ hline color{red}{-3} & 1 & 3 & 3 & 2 & color{green}{0} & {} \ hline color{red}{-2} & 1 & 1 & 1 & color{green}{0} & {} & {} \ end{array}]

Другими словами, исходное уравнение можно переписать так:

[left( {{x}^{2}}+x+1 right){{left( x+2 right)}^{2}}left( x+1 right)=0]

Число $x=color{red}{-2}$ оказалось корнем второй кратности, а квадратное уравнение

[{{x}^{2}}+x+1=0]

не имеет корней. Поэтому окончательный ответ: $x=-2$, $x=-3$.

Пример 9. Дробные корни

Решите уравнение:

[3{{x}^{4}}+5{{x}^{3}}-{{x}^{2}}-5x-2=0]

Решение. По теореме Безу получаем, что рациональные корни вида

[x=frac{m}{n}]

должны быть составлены из чисел $min left{ pm 1, pm 2 right}$ и $nin left{ 1,3 right}$. Всего существует восемь таких комбинаций:

[xin left{ pm 1; pm 2; pm frac{1}{3}; pm frac{2}{3} right}]

Рассмотрим самые простые корни: $x=color{red}{1}$ и $x=color{red}{-1}$. Причём на каждом шаге будем проверять возможную кратность:

[begin{array}{r|c|c|c|c|c} {} & color{blue}{3} & color{blue}{5} & color{blue}{-1} & color{blue}{-5} & color{blue}{-2} \ hline color{red}{1} & 3 & 8 & 7 & 2 & color{green}{0} \ hline color{red}{1} & 3 & 11 & 18 & color{red}{20} & {} \ hline color{red}{-1} & 3 & 5 & 2 & color{green}{0} & {} \ hline color{red}{-1} & 3 & 2 & color{green}{0} & {} & {} \ end{array}]

Получили корень $x=color{red}{1}$ (первой кратности) и $x=color{red}{-1}$ (как минимум второй кратности), а само уравнение можно переписать так:

[left( 3x+2 right){{left( x+1 right)}^{2}}left( x-1 right)=0]

Теперь очевидно, что всего уравнение имеет три корня: $x=1$, $x=-1$ и $x=-{2}/{3};$.

4.2. Учёт кратности корней

Как видим, схема Горнера позволяет не просто перебирать корни, но и определять их кратность. Это особенно важно при решении неравенств и задач с параметрами.

Чтобы определить кратность корня $x=color{red}{a}$, достаточно подставлять его в таблицу до тех пор, пока не появится остаток, отличный от нуля. Либо пока исходный многочлен не будет полностью разложен на множители.

Пример 10. Корень четвёртой кратности

Решите уравнение и определите кратность корней:

[{{x}^{5}}-10{{x}^{3}}-20{{x}^{2}}-15x-4=0]

Решение. Слева стоит многочлен с целыми коэффициентами. Выпишем потенциальные корни по теореме Безу:

[xin left{ pm 1; pm 2; pm 4 right}]

Начнём с самых простых чисел: $x=color{red}{1}$ и $x=color{red}{-1}$. Проверим их по схеме Горнера:

[begin{array}{r|c|r|r|r|r|r} {} & color{blue}{1} & color{blue}{0} & color{blue}{-10} & color{blue}{-20} & color{blue}{-15} & color{blue}{-4} \ hlinecolor{red}{1} & 1 & 1 & -9 & -29 & -44 & color{red}{-48} \ hlinecolor{red}{-1} & 1 & -1 & -9 & -11 & -4 & color{green}{0} \ hlinecolor{red}{-1} & 1 & -2 & -7 & -4 & color{green}{0} & {} \ hlinecolor{red}{-1} & 1 & -3 & -4 & color{green}{0} & {} & {} \ hlinecolor{red}{-1} & 1 & -4 & color{green}{0} & {} & {} & {} \ end{array}]

Перепишем исходное уравнение:

[{{left( x+1 right)}^{4}}left( x-1 right)left( x-4 right)=0]

Итого уравнение имеет три различных корня: $x=-1$ (четвёртой кратности), $x=1$ (первой кратности) и $x=4$ (тоже первой кратности).

Ключевая мысль: с помощью схемы Горнера можно решать даже уравнения высших степеней. Поэтому если при решении текстовой задачи (и особенно задачи с параметром) возникло уравнение 3-й степени и выше, это вовсе не означает, что вы где-то ошиблись. Вполне возможно, что составители задачи хотят проверить, умеете ли вы решать уравнения высших степеней.

5. Разложение на множители

Схему Горнера часто применяют для разложения многочлена на множители. Мы знаем, что для всякого $x=color{red}{a}$ такого, что последний элемент таблицы $r=color{green}{0}$, можно переписать исходный многочлен $Pleft( x right)$ в виде

[Pleft( x right)=left( x-color{red}{a} right)cdot Qleft( x right)]

Коэффициенты многочлена $Qleft( x right)$ будут также даны в таблице, и к нему тоже применима схема Горнера.

Пример 11. Простой многочлен

Разложите на множители многочлен

[{{x}^{4}}+2{{x}^{3}}+4{{x}^{2}}+3x-10]

Решение. Рассмотрим многочлен

[Pleft( x right)= color{blue}{1}cdot {{x}^{4}}+color{blue}{2}cdot {{x}^{3}}+color{blue}{4}cdot {{x}^{2}}+color{blue}{3}cdot x+left( color{blue}{-10} right)]

Будем выделять из него двучлены вида $left( x-color{red}{a} right)$, где $x=color{red}{a}$ — корни многочлена $Pleft( x right)$. Рассмотрим в качестве таких корней делители свободного члена ${{a}_{0}}=color{blue}{-10}$. Начнём с $x=color{red}{1}$ и $x=color{red}{-1}$:

[begin{array}{r|c|c|c|c|c} {} & color{blue}{1} & color{blue}{2} & color{blue}{4} & color{blue}{3} & color{blue}{-10} \ hlinecolor{red}{1} & 1 & 3 & 7 & 10 & color{green}{0} \ hlinecolor{red}{-1} & 1 & 2 & 5 & color{red}{5} & {} \ hlinecolor{red}{-2} & 1 & 1 & 5 & color{green}{0} & {} \ end{array}]

Итого одна неудачная попытка и две удачных. Получили разложение многочлена

[Pleft( x right)=left( x-1 right)left( x+2 right)left( {{x}^{2}}+x+5 right)]

Квадратный трёхчлен в третьей скобке всегда положителен:

[{{x}^{2}}+x+5 gt 0]

Его нельзя разложить на множители, поэтому указанное разложение $Pleft( x right)$ — окончательное.

Пример 12. Сложный многочлен

Разложите на множители многочлен

[{{x}^{5}}-6{{x}^{4}}+2{{x}^{3}}+36{{x}^{2}}-27x-54]

Решение. Рассмотрим многочлен

[Pleft( x right)= color{blue}{1}cdot {{x}^{5}}+left( color{blue}{-6} right)cdot {{x}^{4}}+color{blue}{2}cdot {{x}^{3}}+color{blue}{36}cdot {{x}^{2}}+left( color{blue}{-27} right)cdot x+left( color{blue}{-54} right)]

[begin{align}Pleft( x right)= color{blue}{1}cdot {{x}^{5}} &+left( color{blue}{-6} right)cdot {{x}^{4}}+color{blue}{2}cdot {{x}^{3}}+ \ &+color{blue}{36}cdot {{x}^{2}}+left( color{blue}{-27} right) cdot x+left( color{blue}{-54} right) \ end{align}]

Проверим делители свободного члена ${{a}_{0}}=color{blue}{-54}$. Таких делителей очень много, поэтому начнём с самых простых: $x=color{red}{1}$ и $x=color{red}{-1}$:

[begin{array}{r|c|c|c|c|c|c} {} & color{blue}{1} & color{blue}{-6} & color{blue}{2} & color{blue}{36} & color{blue}{-27} & color{blue}{-54} \ hlinecolor{red}{1} & 1 & -5 & -3 & 33 & 6 & color{red}{-48} \ hlinecolor{red}{-1} & 1 & -7 & 9 & 27 & -54 & color{green}{0} \ hlinecolor{red}{-1} & 1 & -8 & 17 & 10 & color{red}{-64} & {} \ hlinecolor{red}{2} & 1 & -5 & -1 & 25 & color{red}{-4} & {} \ hlinecolor{red}{-2} & 1 & -9 & 27 & -27 & color{green}{0} & {} \ hlinecolor{red}{3} & 1 & -6 & 9 & color{green}{0} & {} & {} \ hlinecolor{red}{3} & 1 & -3 & color{green}{0} & {} & {} & {} \ hlinecolor{red}{3} & 1 & color{green}{0} & {} & {} & {} & {} \ end{array}]

Получили три неудачных попытки и пять удачных. В целом многочлен привет вид

[Pleft( x right)=left( x+1 right)left( x+2 right){{left( x-3 right)}^{3}}]

Это и есть искомое разложение на множители.

Обратите внимание: после проверки корня $x=color{red}{-2}$ в таблице возникла формула сокращённого умножения — куб разности:

[{{x}^{3}}-9{{x}^{2}}+27x-27={{left( x-3 right)}^{3}}]

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

[Pleft( x right)=left( x+1 right)left( x+2 right){{left( x-3 right)}^{3}}]

6. Разложение по степеням

Наконец, ещё одно применение схемы Горнера — это разложение многочлена по степеням двучлена $left( x-color{red}{a} right)$. Для этого достаточно составлять таблицу с указанным $x=color{red}{a}$ до тех пор, пока не закончатся столбцы с коэффициентами.

Полученные остатки будут коэффициентами искомого разложения. Взгляните на примеры.

Пример 13. Разложение многочлена

Разложите по степеням $left( x-1 right)$ многочлен

[{{x}^{4}}-6{{x}^{3}}+16{{x}^{2}}-17x-5]

Решение. Выделим коэффициенты многочлена:

[Pleft( x right)= color{blue}{1}cdot {{x}^{4}}+left( color{blue}{-6} right)cdot {{x}^{3}}+color{blue}{16}cdot {{x}^{2}}+left( color{blue}{-17} right)cdot x+left( color{blue}{-5} right)]

[begin{align}Pleft( x right)= color{blue}{1}cdot {{x}^{4}} &+left( color{blue}{-6} right)cdot {{x}^{3}}+color{blue}{16}cdot {{x}^{2}}+ \ &+left( color{blue}{-17} right) cdot x+left( color{blue}{-5} right) \ end{align}]

Занесём эти коэффициенты в таблицу и будем заполнять её по схеме Горнера для $x=color{red}{1}$ до тех пор, пока не вычеркнем все столбцы:

[begin{array}{c|c|c|c|c|c} {} & color{blue}{1} & color{blue}{-6} & color{blue}{16} & color{blue}{-17} & color{blue}{-5} \ hlinecolor{red}{1} & 1 & -5 & 11 & -6 & color{green}{-11} \ hlinecolor{red}{1} & 1 & -4 & 7 & color{green}{1} & {} \ hlinecolor{red}{1} & 1 & -3 & color{green}{4} & {} & {} \ hlinecolor{red}{1} & 1 & color{green}{-2} & {} & {} & {} \ hlinecolor{red}{1} & color{green}{1} & {} & {} & {} & {} \ end{array}]

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

[Pleft( x right)= color{green}{1}cdot {{left( x-1 right)}^{4}}+left( color{green}{-2} right)cdot {{left( x-1 right)}^{3}}+color{green}{4}cdot {{left( x-1 right)}^{2}}+color{green}{1}cdot left( x-1 right)+left( color{green}{-11} right)]

[begin{align}Pleft( x right) &=color{green}{1}cdot {{left( x-1 right)}^{4}}+left( color{green}{-2} right)cdot {{left( x-1 right)}^{3}}+ \ &+color{green}{4}cdot {{left( x-1 right)}^{2}}+color{green}{1}cdot left( x-1 right)+left( color{green}{-11} right) \ end{align}]

Представим эту запись более компактно:

[Pleft( x right)={{left( x-1 right)}^{4}}-2{{left( x-1 right)}^{3}}+4{{left( x-1 right)}^{2}}+left( x-1 right)-11]

[begin{align}Pleft( x right) &={{left( x-1 right)}^{4}}-2{{left( x-1 right)}^{3}}+ \ &+4{{left( x-1 right)}^{2}}+left( x-1 right)-11 \ end{align}]

Это и есть искомое разложение.

Пример 14. Финал

Разложите по степеням $left( x-2 right)$ многочлен

[{{x}^{4}}-8{{x}^{3}}+24{{x}^{2}}-50x+48]

Решение. В раз не будем переписывать многочлен с выделением коэффициентов, а сразу составим таблицу:

[begin{array}{c|c|c|c|c|c} {} & color{blue}{1} & color{blue}{-8} & color{blue}{24} & color{blue}{-50} & color{blue}{48} \ hlinecolor{red}{2} & 1 & -6 & 12 & -26 & color{green}{-4} \ hlinecolor{red}{2} & 1 & -4 & 4 & color{green}{-18} & {} \ hlinecolor{red}{2} & 1 & -2 & color{green}{0} & {} & {} \ hlinecolor{red}{2} & 1 & color{green}{0} & {} & {} & {} \ hlinecolor{red}{2} & color{green}{1} & {} & {} & {} & {} \ end{array}]

Запишем найденное разложение в порядке убывания степеней:

[color{green}{1}cdot {{left( x-2 right)}^{4}}+color{green}{0}cdot {{left( x-2 right)}^{3}}+color{green}{0}cdot {{left( x-2 right)}^{2}}+left( color{green}{-18} right)cdot left( x-2 right)+left( color{green}{-4} right)]

[begin{align}color{green}{1}cdot {{left( x-2 right)}^{4}}&+color{green}{0}cdot {{left( x-2 right)}^{3}}+color{green}{0}cdot {{left( x-2 right)}^{2}}+ \ &+left( color{green}{-18} right)cdot left( x-2 right)+left( color{green}{-4} right) \ end{align}]

То же самое разложение, но более компактно:

[{{left( x-2 right)}^{4}}-18left( x-2 right)-4]

Это окончательный ответ.

7. Как работает Схема Горнера

Очень просто. Вернёмся к исходному многочлену:

[Pleft( x right)= color{blue}{{a}_{n}}{{x}^{n}}+color{blue}{{a}_{n-1}}{{x}^{n-1}}+ldots +color{blue}{{a}_{1}}x+color{blue}{{a}_{0}}]

Вынесем за скобки множитель $x$ из всех слагаемых, кроме последнего:

[Pleft( x right)=left( color{blue}{{a}_{n}}{{x}^{n-1}}+color{blue}{{a}_{n-1}}{{x}^{n-2}}+ldots +color{blue}{{a}_{1}} right)cdot x+color{blue}{{a}_{0}}]

В скобках стоит новый многочлен. Вновь вынесем за скобки $x$. Сделаем так много раз и в какой-то момент получим запись вида

[Pleft( x right)=left( ldots left( left( color{blue}{{a}_{n}} right)cdot x+color{blue}{{a}_{n-1}} right)cdot x+ldots +color{blue}{{a}_{1}} right)cdot x+color{blue}{{a}_{0}}]

Мы видим множество скобок. Обозначим элемент в самой внутренней скобке через ${{b}_{n-1}}$:

[{{b}_{n-1}}=color{blue}{{a}_{n}}]

Элемент в предыдущей скобке обозначим ${{b}_{n-2}}$:

[{{b}_{n-2}}={{b}_{n-1}} cdot x+color{blue}{{a}_{k}}]

И так далее по уже известной формуле

[{{b}_{k-1}}={{b}_{k}} cdot x+color{blue}{{a}_{k}}]

В какой-то момент мы находим ${{b}_{0}}$ и $r$:

[begin{align} {{b}_{0}} &={{b}_{1}}cdot x+color{blue}{{a}_{1}} \ r &={{b}_{0}}cdot x+color{blue}{{a}_{0}} end{align}]

Собираем все найденные значения в таблицу:

[begin{array}{c|c|c|c|c|c|c} {} & color{blue}{{a}_{n}} & color{blue}{{a}_{n-1}} & color{blue}{{a}_{n-2}} & ldots & color{blue}{{a}_{1}} & color{blue}{{a}_{0}} \ hline x & {{b}_{n-1}} & {{b}_{n-2}} & {{b}_{n-3}} & ldots & {{b}_{0}} & r \ end{array}]

Легко показать, что $r=Pleft( x right)$. Кроме того, согласно теореме Безу, при подстановке $x=color{red}{a}$ найденное число $r=Pleft( color{red}{a} right)$ есть остаток от деления многочлена $Pleft( x right)$ на двучлен $x-color{red}{a}$:

[Pleft( x right)=Qleft( x right)cdot left( x-color{red}{a} right)+r]

В частности, при $r=0$ деление выполнено без остатка, поэтому многочлен $Pleft( x right)$ раскладывается на множители:

[Pleft( x right)=Qleft( x right)cdot left( x-color{red}{a} right)]

Далее по индукции или прямым вычислением можно показать, что коэффициенты $Qleft( x right)$ — это те самые числа ${{b}_{n-1}}$, …, ${{b}_{0}}$ из таблицы. Поскольку $deg Qleft( x right)=n-1$, на каждом шаге степень этого многочлена будет уменьшаться.

В какой-то момент окажется, что $Qleft( x right)= color{blue}{{a}_{n}}$ — константа, и дальнейшее заполнение таблицы по схеме Горнера невозможно. Вот и всё.:)

Смотрите также:

Бином Ньютона
Теорема Безу и корни многочленов
Решение задач B12: №448—455
Задача B3 — работа с графиками
Пример решения задачи 15
Задача B15: частный случай при работе с квадратичной функцией

Источник

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

Рассмотрим многочлен

ой
степени

.
(2.2)

Если непосредственно вычислить значение
этого многочлена в произвольной точке

,
то потребуется

арифметических действий. При этом
возникает потеря точности за счет
погрешности вычисления.

Вычисление многочлена

удобнее производить следующим образом.
Представим его в виде

.
(2.3)

Отсюда, последовательно
вычисляя числа

(2.4)

находим

.

Описанный метод вычисления значения
многочлена в заданной точке носит
название схемы Горнера. Она позволяет
сократить число сложений и умножений
до

операций, при этом повышается точность
вычисления.

Пример. Вычислить значение многочлена

при

.

Решение. Имеем

Последовательное применение формулы
(2.4) дает

Следовательно,

Практически схему Горнера удобно
реализовывать в виде следующей таблицы

Тогда рассмотренный пример будет иметь
вид

2.3. Интерполяционный многочлен Лагранжа

Будем искать многочлен

степени не выше

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

.
Запишем этот многочлен в виде (2.2).
Неизвестные коэффициенты

,

,
…,

можно найти из условия

.
Это условие приводит к системе линейных
уравнений

(2.5)

Определитель
этой системы

называется
определителем Ван-дер-Монда. Он отличен
от нуля, так как все узлы интерполирования
различны. Следовательно, система (2.5)
имеет единственное решение и
интерполяционный многочлен

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

можно построить
другим способом:
строятся

многочленов

таких, что

Так как искомый
многочлен обращается в нуль в

точках

,
то он имеет вид

,
(2.6)

где

— постоянный коэффициент. Полагая

в формуле (2.6) и учитывая, что

,
получим

Отсюда

Подставив это
значение в формулу (2.6), будем иметь

.
(2.7)

Тогда, многочлен

,
удовлетворяющий условиям

,
имеет вид

. (2.8)

Подставив в
формулу (2.8) значение

из (2.7), получим

.
(2.9)

Многочлен

,
определяемый по формуле (2.9) , называется
интерполяционным многочленом Лагранжа.
Очевидно, что степень многочлена Лагранжа
не превышает числа

.
Часто многочлен Лагранжа записывают
виде

При

имеем две точки, и формула Лагранжа
представляет в этом случае уравнение
прямой

,
проходящей через две заданные точки

где

— абсциссы этих точек.

При

получим уравнение параболы

,
проходящей через три точки

Пример. Для функции

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

Решение. Многочлен Лагранжа для
трех узлов интерполирования запишется
так

Вычисляем
соответствующие значения функции

Применяя
формулу Лагранжа, получим

или

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

Источник

Формулировка. Дано натуральное число n, вещественное число x и набор вещественных чисел a_n, a_n_-1, …, a₀. Вычислить значение многочлена n-ной степени с коэффициентами a_n, a_n_-1, …, a₀ от одной переменной в точке x.

Примечание: многочленом n-ной степени от одной переменной x называется выражение вида a_nxⁿ + a_n_-1xⁿ^-1 + … + a₁x + a₀, где a_n, a_n_-1, …, a₀ – коэффициенты.

Решение. Собственно, в этой задаче требуется возведение переменной x (точнее, конкретного ее значения) в некоторую степень n – 1 раз, а также n операций умножения и n операций сложения. В принципе, для полноценного решения она не требует одновременного знания более чем одного коэффициента, так как мы можем в цикле ввести коэффициент a_n в переменную a, умножить его на xⁿ и прибавить полученное число к переменной результата res (которой перед входом в цикл должно быть присвоено значение 0) и повторить этот шаг для всех коэффициентов. Тогда количество операций: (1 + 2 + … + n + 2n), что примерно соответствует асимптотической сложности O(n²).

Не занимаясь реализацией этого алгоритма, давайте оптимизируем его. Например, пусть нам дан многочлен третьей степени a₃x³ + a₂x² + a₁x + a₀. Вынесем за скобки общий множитель x при слагаемых, в которых это возможно. Получим: (a₃x² + a₂x + a₁)x + a₀. Вынесем за скобки x также и в полученном выражении со скобками, в итоге получим: ((a₃x + a₂)x +a₁)x + a₀.

Полученную форму записи называют схемой Горнера. Очевидно, что она существует для многочлена любой степени.

Итак, имея n = 3 и коэффициенты a₃, a₂, a₁ и a₀, мы можем посчитать его значение с помощью n операций умножения и nопераций сложения, а это значит, что для вычисления требуется порядка 2n операций и алгоритм имеет линейную асимптотическую сложность O(n), что демонстрирует очевидное преимущество перед предыдущим решением.

Посмотрим, как может выглядеть цикл, в котором вычисляется значение многочлена в точке. Для этого немного изменим представление в виде схемы Горнера, не меняя при этом значения многочлена: (((0x + a₃)x + a₂)x + a₁)x + a₀.

Теперь нам требуется n + 1 операций, однако заведя переменную res для накопления результата, которая перед входом в цикл будет равна 0, мы можем, вводя коэффициенты a₃, a₂, a₁ и a₀, посчитать значение многочлена в одном цикле:

res := 0;

for i := 1 to n + 1 do begin

read(a);

res := res * x + a

end;

Примечание: оператор read нужен нам для того, чтобы можно было вводить коэффициенты через пробел, а не черезEnter.

Теперь разберем сам цикл. На первом шаге мы получаем в res значение выражения 0x + a₃ = a₃, на втором – a₃x + a₂, на третьем – (a₃x + a₂)x + a₁, на четвертом – ((a₃x + a₂)x + a₁)x + a₀. Как видно, формула полностью восстановилась, причем вычисление идет от наиболее вложенных скобок к верхним уровням.

Код:

program ValueOfPolynomial;
var
i, n: byte;
x, a, res: real;
begin
readln(n, x);
res := 0;
for i := 1 to n + 1 do begin
read(a);
res := res * x + a
end;
writeln(res:4:2)
end.

Источник