Вещественные корни многочлена. Определение корня многочлена. Решение систем нелинейных уравнений

Если число с является корнем многочлена f (x), этот многочлен, как известно, делится на х-с. Может случиться, что f (x) делится и на какую-то степень многочлена х-с, т.е. на (х-с) k, k>1. В этом случае с называют кратным корнем. Сформулируем определение более четко.

Число с называется корнем кратности k (k-кратным корнем) многочлена f (x), если многочлен делится на (х-с) k, k>1 (k - натуральное число), но не делится на (х-с) k+1. Если k=1, то с называют простым корнем, а если k>1, - кратным корнем многочлена f (x).

В дальнейшем при определении кратности корней нам будет полезно следующее предложение.

Если многочлен f (x) представим в виде f (x) = (x-c) mg (x), m - натуральное число, то он делится на (х-с) m+1 тогда и только тогда, когда g (x) делится на х-с. В самом деле, если g (x) делится на х-с, т.е. g (x) = (x-c) s (x), то f (x) = (x-c) m+1s (x), а значит, f (x) делится на (х-с) m+1.

Обратно, если f (x) делится на (х-с) m+1, то f (x) = (x-c) m+1s (x). Тогда (x-c) mg (x) = (x-c) m+1s (x) и после сокращения на (х-с) m получим g (x) = (x-c) s (x). Отсюда следует, что g (x) делится на х-с.

А сейчас вернемся к понятию кратности корня. Выясним, например, является ли число 2 корнем многочлена f (x) =x5-5x4+3x3+22x2-44x+24, и если да, найдем его кратность. Чтобы ответить на первый вопрос, проверим с помощью схемы Горнера, делится ли f (x) на х-2. имеем:

Таблица 4

Получили, что g (x) делится на х-2 и g (x) = (x-2) (x3-x2-5x+6). Тогда f (x) = (x-2) 2 (x3-x2-5x+6).

Итак, f (x) делится на (х-2) 2, теперь нужно выяснить, делится ли f (x) на (x-2) 3.

Для этого проверим, делится ли h (x) =x3-x2-5x+6 на х-2:

Таблица 6

Находим, что остаток при делении s (x) на х-2 равен 3, т.е. s (x) не делится на х-2. Значит, f (x) не делится на (х-2) 4.

Таким образом, f (x) делится на (х-2) 3, но не делится на (х-2) 4. Следовательно, число 2 является корнем кратности 3 многочлена f (x).

Обычно проверку корня на кратность выполняют в одной таблице. Для данного примера эта таблица имеет следующий вид:

Таблица 8

Другими словами, по схеме Горнера деление многочлена f (x) на х-2, во второй строке мы получим коэффициенты многочлена g (x). Затем эту вторую строку считаем первой строкой новой системы Горнера и выполняем деление g (x) на х-2 и т.д. продолжаем вычисления до тех нор, пока не получим остаток, отличный от нуля. В этом случае кратность корня равна числу полученных нулевых остатков. В строке, содержащей последний ненулевой остаток, находится и коэффициенты частного при делении f (x) на (x-2) 3. Теперь, используя только что предложенную схему проверки корня на кратность, решим следующую задачу. При каких a и b многочлен f (x) =x4+2x3+ax2+ (a+b) x+2 имеет число - 2 корнем кратности 2?

Так как кратность корня - 2 должна быть равна 2, то, выполняя деление на х+2 по предложенной схеме, мы должны два раза получить остаток 0, а в третий раз - остаток, отличный от нуля. Имеем:

Таблица 9

Таким образом, число - 2 является корнем кратности 2 исходного многочлена тогда и только тогда, когда

Отсюда получаем: a=-7/2, b=-5/2.

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

3 Функции произвольного вида

4 Нахождение корней полиномов

Список используемых информационных источников

1 Нахождение корней уравнений (Equation Section 1)

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

. Будем считать, что x является решением уравнения. Разложим функцию f(x) в ряд в точке x0 близкой к точке x и ограничимся только первыми двумя членами разложения.

Поскольку x – корень уравнения, то

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

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

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

В качестве малой величины

можно взять, например, заданную точность вычислений , тогда расчетная формула примет вид (1.1)

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

(1.2)

В таком виде метод называется методом секущих (secantmethod). При этом, однако, возникает проблема с вычислением первого приближения. Обычно полагают, что

, то есть первый шаг вычислений проводится с использованием формулы (1.1), а все последующие – с использованием формулы (1.2). Именно эта вычислительная схема реализована в пакете Mathcad. Используя метод секущих, мы не можем гарантировать, что корень находится между двумя последними приближениями. Можно, однако, для вычисления очередного приближения использовать границы интервала, на котором функция меняет знак. Такой метод называется методом хорд (falsepositionmethod).

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

Знак перед корнем выбирается так, чтобы абсолютное значение знаменателя было максимальным.

Поскольку поиск корня заканчивается, когда выполнится условие

, то возможно появление ложных корней. Например, для уравнения ложный корень появится в том случае, если точность поиска задана меньше, чем 0,0001. Увеличивая точность поиска, можно избавиться от ложных корней. Однако не для всех уравнений такой подход работает. Например, для уравнения , которое, очевидно, не имеет действительных корней, для любой, сколь угодно малой точности найдется значение x, удовлетворяющее критерию окончания поиска. Приведенные примеры показывают, что к результатам компьютерных вычислений всегда нужно относиться критически, анализировать их на правдоподобность. Чтобы избежать "подводных камней" при использовании любого стандартного пакета, реализующего численные методы, нужно иметь хотя бы минимальное представление о том, какой именно численный метод реализован для решения той или иной задачи.

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

В методе Риддера (Ridder’smethod) вычисляют значение функции в середине интервала

. Затем ищут экспоненциальную функцию такую, что Затем применяют метод хорд, используя значения . Очередное значение вычисляют по формуле (1.5)

Метод Брента (Brentmethod) соединяет быстроту метода Риддера и гарантированную сходимость метода деления отрезка пополам. Метод использует обратную квадратичную интерполяцию, то есть ищет x как квадратичную функцию y. На каждом шаге проверяется локализация корня. Формулы метода достаточно громоздки и мы не будем их приводить.

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

Метод Лобачевского, метод приближённого (численного) решения алгебраических уравнений, найденный независимо друг от друга бельгийским математиком Ж. Данделеном, русским математиком Н. И. Лобачевским (в 1834 в наиболее совершенной форме) и швейцарским математиком К. Греффе. Суть Л. м. состоит в построении уравнения f1(x) = 0, корни которого являются квадратами корней исходного уравнения f(x) = 0. Затем строят уравнение f2(x) = 0, корнями которого являются квадраты корней уравнения f1(x) = 0. Повторяя этот процесс несколько раз, получают уравнение, корни которого сильно разделены. В случае если все корни исходного уравнения действительны и различны по абсолютной величине, имеются простые вычислительные схемы Л. м. для нахождения приближённых значений корней. В случае равных по абсолютной величине корней, а также комплексных корней вычислительные схемы Л. м. очень сложны.

Метод Лагерра (Laguerre’smethod) основывается на следующих соотношениях для полиномов

Знак перед корнем выбирают с таким расчетом, чтобы получить наибольшее значение знаменателя.

Еще один метод, который применяют для поиска корней полиномов, – метод сопровождающей матрицы (companionmatrix). Можно доказать, что матрица

называемая сопровождающей матрицей для полинома

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

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

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

p(x) = ((... ((anx + an-1)x + an-2)x + ... + a2)x + a1)x + a0.

Займемся общим многочленом вида:

p(x) = anxn + an-1xn-1 + an-2xn-2 + ... + a2x2 + a1x + a0.

Мы будем предполагать, что все коэффициенты an, ..., a0 известны, постоянны и записаны в массив. Это означает, что единственным входным данным для вычисления многочлена служит значение x, а результатом программы должно быть значение многочлена в точке x.

Если функция f(х) является полиномом, то все его корни можно определить, используя встроенную функцию

где v - вектор, составленный из коэффициентов полинома.

Поскольку полином n-й степени имеет ровно n корней (некоторые из них могут быть кратными), вектор v должен состоять из n+1 элемента. Результатом действия функции polyroots() является вектор, составленный из n корней рассматриваемого полинома. При этом нет надобности вводить какое-либо начальное приближение, как для функции root(). Пример поиска корней полинома четвертой степени показан на рис. 4. 6:

Рис. 4.6. Поиск корня полинома

Коэффициенты рассматриваемого в примере полинома записаны в виде вектора-столбца начиная со свободного члена и кончая коэффициентом при старшей степени x n .

Для функции polyroots() можно выбрать один из двух численных методов - метод полиномов Лаггера (он установлен по умолчанию) или метод парной матрицы. Чтобы сменить метод необходимо вызвать контекстное меню, щелкнув ПКМ на слове polyroots и в верхней части контекстного меню выбрать либо пункт LaGuerre (Лаггера), либо Companion Matrix (Парная матрица). Затем нужно щелкнуть вне действия функции polyroots – и если включен режим автоматических вычислений, будет произведен пересчет корней полинома в соответствии с вновь выбранным методом.

Для того чтобы оставить за Mathcad’ом выбор метода решения, нужно установить флажок AutoSelect (Автоматический выбор), выбрав одноименный пункт в том же самом контекстном меню.

Решение систем нелинейных уравнений

Рассмотрим решение системы n нелинейных уравнений с m неизвестными

f 1 (x 1 ,... ,х m) = 0,

f n (x 1 ,... ,х m) = 0,

Здесь f 1 (x 1 ,... ,х m) , ..., f n (x 1 ,... ,х m) - некоторые скалярные функции от скалярных переменных x 1 ,... ,х m и, возможно, от еще каких-либо переменных. Уравнений может быть как больше, так и меньше числа переменных. Заметим, что вышеприведенную систему можно формально переписать в виде

где х - вектор, составленный из переменных x 1 ,... ,х m , a f (х) - соответствующая векторная функция.

Для решения систем имеется специальный вычислительный блок, состоящий из трех частей, идущих последовательно друг за другом:

Given - ключевое слово;

Система, записанная с помощью Булевых операторов в виде равенств и, возможно, неравенств;

Find(x 1 ,... ,х m) - встроенная функция для решения системы относительно переменных x 1 ,... ,х m .

Блок Given/Find использует для поиска решения итерационные методы, поэтому, как и для функции root(), требуется задать начальные значения для всех x 1 ,... ,х m . Сделать это необходимо до написания ключевого слова Given. Значение функции Find есть вектор, составленный из решения по каждой переменной. Таким образом, число элементов вектора равно число аргументов Find.

Рассмотрим пример. Решить систему из двух уравнений с двумя неизвестными:

с точностью 0.01. Корни отделить графически.

Представим уравнения системы в виде следующих функций от одной переменной:

Подберем дискретные значения переменных:

Найдем корни уравнения с помощью блока Given – Find():

На рис. 4.7 приведен другой пример решения системы двух уравнений:

Рис. 4.7. Решение системы уравнений

Вначале рис. 4.7 вводятся функции, которые определяют систему уравнений. Затем переменным х и у, относительно которых она будет решаться, присваиваются начальные значения. После этого следует ключевое слово Given и два Булевых оператора равенства, выражающих рассматриваемую систему уравнений. Завершает вычислительный блок функция Find, значение которой присваивается вектору v. После печатается содержимое вектора v, т. е. решение системы. Первый элемент вектора есть первый аргумент функции Find, второй элемент - ее второй аргумент. В конце осуществлена проверка правильности решения уравнений. Заметим, что уравнения можно определить непосредственно внутри вычислительного блока.

Графическая интерпретация рассмотренной системы представлена на рис. 4.8. Каждое из уравнений показано на плоскости xy графиком. Первое уравнение изображено кривой, второе сплошной прямой. Две точки пересечения кривых соответствуют одновременному выполнению обоих уравнений, т. е. искомым действительным корням системы. Как нетрудно убедиться, на рис. 4.7 найдено только одно из двух решений - находящееся в правой нижней части графика Чтобы отыскать и второе решение, следует повторить вычисления, изменив начальные значения так, чтобы они лежали ближе к другой точке пересечения графиков, например x=-1, y=-1.

Рис. 4.8. Графическое решение системы двух уравнений

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

Рис. 4.9. Решение системы уравнений и неравенств

Несмотря на те же начальные значения, что и на рис. 4.8, на рис. 4.9 получен другой корень. Это произошло именно благодаря введению дополнительного неравенства, которое определено в блоке Given (x < 0).

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

В качестве оценки погрешности решения уравнений, введенных после ключевого слова Given, вычислительный блок использует константу CTOL. Например, если CTOL=0.001, то уравнение х=10 будет считаться выполненным и при х=10.001, и при х=9.999. Другая константа TOL определяет условие прекращения итераций численным алгоритмом. Значение CTOL может быть задано пользователем так же как и TOL, например, CTOL:=0.01. По умолчанию принято, что CTOL=TOL=0.001, но по желанию можно их переопределить.

Особенную осторожность следует соблюдать при решении систем с числом неизвестных большим, чем число уравнений. Например, можно удалить одно из двух уравнений из рассмотренного нами рис. 4.7, попытавшись решить единственное уравнение g(х,у)=0 с двумя неизвестными х и у. В такой постановке задача имеет бесконечное множество корней: для любого х и, соответственно, у=-х/2 условие, определяющее единственное уравнение, выполнено. Однако, даже если корней бесконечно много, численный метод будет производить расчеты только до тех пор, пока логические выражения в вычислительном блоке не будут выполнены (в пределах погрешности). После этого итерации будут остановлены и выдано решение. В результате будет найдена всего одна пара значений (х,у), обнаруженная первой.

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

Рис. 4.10. Поиск корня уравнения с одним неизвестным с помощью функции Find().

Mathcad предлагает три различных вида градиентных методов для решения системы нелинейных уравнений с помощью блока Given – Find(). Чтобы поменять численный метод, необходимо:

Щелкнуть правой кнопкой мыши на названии функции Find;

Выбрать пункт Nonlinear (Нелинейный) в появившемся контекстном меню;

Выбрать один из трех методов: Conjugate Gradient (Сопряженных градиентов, установлен по умолчанию), Quasi-Newton (Квази-Ньютоновский) или Levenberg-Marquardt (Левенберга).

K - это элемент c ∈ K {\displaystyle c\in K} (либо элемент расширения поля K), такой, что выполняются два следующих равносильных условия: a 0 + a 1 x + ⋯ + a n x n = 0 {\displaystyle a_{0}+a_{1}x+\dots +a_{n}x^{n}=0}

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

Говорят, что корень c {\displaystyle c} имеет кратность m {\displaystyle m} , если рассматриваемый многочлен делится на (x − c) m {\displaystyle (x-c)^{m}} и не делится на (x − c) m + 1 . {\displaystyle (x-c)^{m+1}.} Например, многочлен x 2 − 2 x + 1 {\displaystyle x^{2}-2x+1} имеет единственный корень, равный 1 , {\displaystyle 1,} кратности 2. Выражение «кратный корень» означает, что кратность корня больше единицы.

Свойства

P (x) = a n (x − c 1) (x − c 2) … (x − c n) , {\displaystyle p(x)=a_{n}(x-c_{1})(x-c_{2})\ldots (x-c_{n}),} где - (в общем случае комплексные) корни многочлена , возможно с повторениями, при этом если среди корней c 1 , c 2 , … , c n {\displaystyle c_{1},c_{2},\ldots ,c_{n}} многочлена p (x) {\displaystyle p(x)} встречаются равные, то общее их значение называется кратным корнем .

Нахождение корней

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

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

Свойства

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

Нахождение корней

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

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

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

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

См. также

Примечания

Wikimedia Foundation . 2010 .

• Канализация
• Словарь терминов вексиллологии

Смотреть что такое "Корень многочлена" в других словарях:

Корень алгебраического уравнения

Корень уравнения - Корень многочлена над полем k элемент, который после подстановки его вместо x обращает уравнение в тождество. Свойства Если c является корнем многочлена p(x … Википедия

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

Корень (значения) - Корень: В Викисловаре есть статья «корень» Корень (в ботанике) вегетативный осевой подземный орган растения, обладающий сп … Википедия

Корень (в математике) - Корень в математике, 1) К. степени n из числа а ≈ число х (обозначаемое), n я степень которого равна а (то есть xn = а). Действие нахождения К. называют извлечением корня. При а ¹ 0 существует n различных значений К. (вообще говоря,… …

Корень - I Корень (radix) один из основных вегетативных органов листостебельных растений (за исключением мхов), служащий для прикрепления к субстрату, поглощения из него воды и питательных веществ, первичного превращения ряда поглощаемых веществ,… … Большая советская энциклопедия

КОРЕНЬ - 1) К. степени n из числа a число n я степень х п к рого равна а. 2) К. алгебраического уравнения над полем К элемент к рый после подстановки его вместо хобращает уравнение в тождество. К. этого уравнения наз. также и К. многочлена Если сявляется… … Математическая энциклопедия

Кратный корень - многочлена f (x) = a0xn + a1xn 1 +... + an, число с такое, что f (x) делится без остатка на вторую или более высокую степень двучлена (х с). При этом с называют корнем кратности, если f (x) делится на (х с) k, но не… … Большая советская энциклопедия

Сопряжённый корень - Если задан некоторый неприводимый многочлен над кольцом и выбран некоторый его корень в расширении, то сопряженным корнем для данного корня многочлена называется любой корень многочлена … Википедия

Квадратный корень из 2 - равен длине гипотенузы в прямоугольном треугольнике с длиной катетов 1. Квадратный корень из числа 2 положительное … Википедия