Как найти корень уравнение для многочлена

Схема Горнера. Корни многочлена

Разделы: Математика

Цели урока:

• научить учащихся решать уравнения высших степеней используя схему Горнера;
• воспитывать умение работать в парах;
• создать в совокупности с основными разделами курса базу для развития способностей учащихся;
• помочь ученику оценить свой потенциал, развивать интерес к математике, умение мыслить, высказываться по теме.

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

Метод обучения: лекция, рассказ, объяснение, выполнение тренировочных упражнений.

Форма контроля: проверка задач самостоятельного решения, самостоятельная работа.

Ход урока

1. Организационный момент

2. Актуализация знаний учащихся

— Какая теорема позволяет определить, является ли число корнем данного уравнения (сформулировать теорему)?

Теорема Безу. Остаток от деления многочлена Р(х) на двучлен х-с равен Р(с), число с называют корнем многочлена Р(х), если Р(с)=0. Теорема позволяет, не выполняя операцию деления, определить, является ли данное число корнем многочлена.

— Какие утверждения облегчают поиск корней?

а) Если старший коэффициент многочлена равен единице, то корни многочлена следует искать среди делителей свободного члена.

б) Если сумма коэффициентов многочлена равна 0, то один из корней равен 1.

в)Если сумма коэффициентов стоящих на четных местах, равна сумме коэффициентов, стоящих на нечетных местах, то один из корней равен -1.

г) Если все коэффициенты положительны, то корнями многочлена являются отрицательные числа.

д) Многочлен нечетной степени имеет хотя бы один действительный корень.

3. Изучение нового материала

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

Пусть дан произвольный многочлен Р(х)=а₀х n + а₁х n-1 + …+ а_n-1х+ а_n. Деление этого многочлена на х-с – это представление его в виде Р(х)=(х-с)g(х) + r(х). Частное g(х)=в₀х n-1 + в_nх n-2 +…+в_n-2х + в_n-1, где в₀=а₀, в_n=св_n-1 +а_n, n=1,2,3,…n-1. Остаток r(х)= св_n-1 +а_n . Этот метод вычисления и называется схемой Горнера. Слово « схема» в названии алгоритма связана с тем, что обычно его выполнение оформляют следующим образом. Сначала рисуют таблицу 2(n+2). В левой нижней клетке записывают число с, а в верхней строке коэффициенты многочлена Р(х). При этом левую верхнюю клетку оставляют пустой.

Как найти корень уравнение для многочлена

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

Решите уравнение: `x^3 +4x^2 — 2x-3=0`.

Заметим, что `x=1` является корнем уравнения (значение многочлена при `x=1` равно сумме коэффициентов многочлена). Тогда по теореме Безу многочлен `x^3 +4x^2 -2x -3` делится на многочлен `x-1`. Выполнив деление, получаем:

`x^3 +4x^2 -2x -3=0 hArr (x-1)(x^2 + 5x +3) =0 hArr`

Обычно кубические уравнения решают именно так: подбирают один корень, выполняют деление уголком, после чего остаётся решить только квадратное уравнение. А что делать, если у нас уравнение четвёртой степени? Тогда придётся подбирать корень два раза. После подбора первого корня и деления останется кубическое уравнение, у которого надо будет подобрать ещё один корень. Возникает вопрос. Что делать, если такие «простые» числа как `+-1`, `+-2` не являются корнями уравне ния? Неужели тогда надо перебирать всевозможные числа? Ответ на этот вопрос даёт следующее утверждение.

Если несократимая дробь `p//q` (`p` — целое, `q` — натуральное) является корнем многочлена с целыми коэффициентами , то сво бодный член делится на `p` , а старший коэффициент делится на `q`.

Пусть несократимая дробь `p//q` — корень многочлена (8). Это означает, что

`a_n (p/q)^n +a_(n-1)(p/q)^(n-1) + a_(n-2) (p/q)^(n-2)+ . «+a_2 (p/q)^2 +a_1(p/q)+0=0`.

Умножим обе части на `q^n`, получаем:

`a_n p^n + a_(n-1) p^(n-1) q+a_(n-2) p^(n-2) q^2 + . + a_2 p^2 q^(n-2) +a_1 pq^(n-1)+a_0q^n=0`.

Перенесём в правую часть, а из оставшихся слагаемых вынесем `p` за скобки:

Справа и слева в (14) записаны целые числа. Левая часть делится на `p=>` правая часть также делится на `p`. Числа `p` и `q` взаимно просты (т. к. дробь `p//q` несократимая), откуда следует, что `a_0 vdotsp`.

Аналогично доказывается, что `a_n vdotsq`. Теорема доказана.

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

а) `x^4+4x^3-102x^2-644x-539=0`; (15)

б) `6x^4-35x^3+28x^2+51x+10=0`. (16)

а) Попробуем найти целые корни уравнения. Пусть `p` — корень. Тогда `539vdotsp`; чтобы найти возможные значения `p`, разложим число `539` на простые множители:

Поэтому `p` может принимать значения:

Подстановкой убеждаемся, что `x=-1` является корнем уравнения. Разделим многочлен в левой части (15) уголком на `x+1` и получим:

Далее подбираем корни у получившегося многочлена третьей степени. Получаем `x=-7`, а после деления на `(x+7)` остаётся `(x+1)(x+7)(x^2-4x-77)=0`. Решая квадратное уравнение, находим окончательное разложение левой части на множители:

1) После того, как найден первый корень, лучше сначала выполнить деление уголком, и только потом приступать к поиску последующих корней. Тогда вычислений будет меньше.

2) В разложении многочлена на множители множитель `(x+7)` встретился дважды. Тогда говорят, что `(–7)` является корнем кратности два. Аналогично говорят о корнях кратности три, четыре и т. д.

б) Если уравнение имеет рациональный корень `x_0=p/q`, то `10vdotsp`, `6vdotsq`, т. е. `p in<+-1;+-2;+-5;+-10>`; `qin<1;2;3;6>`.Возможные варианты для `x_0`:

Начинаем перебирать числа из этого списка. Первым подходит число `x=5/2`. Делим многочлен в левой части (16) на `(2x-5)` и получаем

Заметим, что для получившегося кубического уравнения выбор рациональных корней заметно сузился, а именно, следующие числа могут быть корнями: `x_0=+-1,+-2,+-1/3,+-2/3`, причём мы уже знаем, что числа `+-1` и `+-2` корнями не являются (так как мы их подставляли раньше, и они не подошли). Находим, что `x=-2/3` — корень; делим `3x^3-10x^2-11x-2` на `3x+2` и получаем:

Решаем квадратное уравнение: `x^2-4x-1=0 iff x=2+-sqrt5`.

К сожалению, уравнения не всегда имеют рациональные корни. Тогда приходится прибегать к другим методам.

Разложите на множители:

а) `x^4+4=x^4+4x^2+4-4x^2=(x^2+2)^2-(2x)^2=`

Таким образом, сумму четвёртых степеней, в отличие от суммы квадратов, можно разложить на множители:

в) Вынесем `x^2` за скобки и сгруппируем:

Обозначим `x+2/x=t`. Тогда `x^2+4+4/x^2=t^2`, `x^2+4/x^2=t^2-4`, выражение в скобках принимает вид:

В итоге получаем:

Этот приём иногда используется для решения уравнений четвёртой степени; в частности, с его помощью решают возвратные уравнения (см. пример 12 е).

г)* Можно убедиться, что никакой из рассмотренных выше методов не помогает решить задачу, а именно: рациональных корней уравнение не имеет (числа `+-1` и `+-2` – не корни); вынесение числа `x^2` за скобки и группировка слагаемых приводит к выражению

Если здесь обозначить `4x-13/x=t`, то `x^2-2/x^2` через `t` рационально не выражается.

Прибегнем к методу неопределённых коэффициентов. Пусть

Попробуем подобрать коэффициенты `a`, `b`, `c`, `d` так, чтобы (17) обратилось в верное равенство. Для этого раскроем скобки в правой части и приведём подобные слагаемые:

Приравняем в (18) коэффициенты при одинаковых степенях в обеих частях уравнения. Получим систему уравнений:

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

Рассмотрим четвёртое уравнение. Возможны только два принципиально различных случая:

2) `b=2` и `d=-1`. Рассмотрим каждый из них. Подставляем значения `b` и `d` в первые три уравнения:

Из первого и третьего уравнений системы получаем `c=5/3`; `a=-17/3`, что не удовлетворяет второму уравнению, поэтому система решений не имеет; пара чисел `b=1` и `d=-2` не подходит.

Эта система имеет одно решение `a=-7`, `c=3`. Значит, числа `a=-7`, `b=2`, `c=3`, `d=-1` являются решением системы (19), поэтому

Далее каждый из квадратных трёхчленов можно разложить на множители.

Во многих ситуациях степень уравнения можно понизить с помощью замены переменных.

Алгоритм расчёта вещественных корней полиномов

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

А теперь по порядку.

Проблема нахождения корней алгебраических полиномов известна давно, по крайней мере со средневековья. В школе учат решать квадратные уравнения. В википедии можно найти формулы Кардано для решения кубических уравнений и описание метода Феррари для решения в радикалах уравнения четвёртой степени. Там же описан метод Лобачевского для решения алгебраических уравнений произвольной степени. Суть метода Лобачевского вкратце сводится к следующему.

Нетрудно, имея некоторый исходный полином, построить полином2, имеющий те же по модулю корни, что и исходный полином, но с противоположным знаком. Перемножая исходный полином и полином2, получаем полином, корни которого равны квадратам корней исходного полинома.

Это преобразование (квадрирование) полезно повторить несколько раз. В результате, если корни исходного полинома не были равны друг другу, их многократно квадрированные значения оказываются далеко разнесёнными по величине, а их приближенные значения очень просто выражаются через коэффициенты соответствующего квадрированного полинома.

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

Для конкретности сообщим, что для полинома 4-й степени с корнями 1, 2, 3, 4 метод Лобачевского уже после четвёртого квадрирования даёт правильные до второго знака после запятой значения корней. При этом для представления коэффициентов полиномов достаточно формата long double.

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

Теперь я начну описывать иной метод. В общедоступной печати упоминание о нём начинается с работы [1]. Какие-либо независимые публикации о применении такого метода мне неизвестны. Этот алгоритм сводится к последовательному исследованию интервалов монотонного изменения исходного полинома. Если на границах этого интервала монотонности значения полинома имеют разные знаки, то запускается процедура деления отрезка пополам для расчёта точного значения очередного корня. Границами интервалов монотонности являются точки, в которых значение производной полинома обращается в нуль, т.е. это корни производного полинома. Производный полином имеет степень на единицу меньшую, чем исходный полином, и процесс расчёта коэффициентов производных полиномов следует продолжить до полинома первой степени, корень которого находится непосредственно, без привлечения процедуры деления отрезка пополам. В результате этого шага получим два интервала монотонного изменения для производного полинома второй степени.

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

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

Для доказательства рассмотрим расчёт полинома p(x)=x^n+k[n-1]*x^(n-1)+. +k[1]*x+k[0] по схеме Горнера.

На первом шаге вычисляется p[1]=k[n-1]+x и очевидно, что p[1]>1.
На втором шаге вычисляется p[2]=k[n-2]+x*p[1] и вновь очевидно, что p[2]>1.
Аналогичное имеет место на последующих шагах.
На последнем шаге вычисляется p(x)=k[0]+x*p[n-1] и окончательно получим p(x)>1.

Таким образом, если нужно определить знак полинома при бесконечном значении аргумента, следует взять аргумент равным M+1.

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

Прокомментирую, наконец, не вполне очевидную особенность реализации алгоритма деления отрезка пополам.

Пробная точка pt, расположенная посередине между текущими концами ng и vg отрезка, вычисляется оператором pt=0.5*(ng+vg); а цикл делений пополам прерывается оператором if(pt =vg)break;.

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

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

Ниже, как приложение, приведен полный текст файла polynomRealRoots.cpp, реализующего описанныйалгоритм.

Примите также текст заголовочного файла polynomRealRoots.h, позволяющего легко организовать ссылку на приведенный выше программный модуль.

Литература

1. Костин И.К. Семейство алгоритмов расчета интервалов прохождения космического аппарата над круговым наземным объектом с учетом продольной ошибки определения параметров орбиты

Вопросы радиоэлектроники, сер. РЛТ, 2004г., вып. 1

Эту ссылку можно найти в Яндексе поиском по закавыченной фразе «семейство алгоритмов расчета», но текст этой статьи в электронном виде, кажется, недоступен. Поэтому приведу здесь цитату из двух предложений этой статьи:

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

Но производная полинома — это тоже полином, однако, меньшей степени и, найдя его вещественные корни, надо искать корни исходного полинома между корнями производной методом деления пополам.