Вычисление корней в С+

Оглавление Введение

1. Существование корней в C

2. Распределение корней на плоскости комплексной переменной

3. Распределение вещественных корней полинома с вещественными коэффициентами

4. Приближенное вычисление корней полинома Литература

Введение

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

Изучение полиномиальных уравнений и их решений составляет едва ли не главный объект «классической алгебры». С изучением многочленов связан целый ряд преобразований в математике: введение в рассмотрение нуля, отрицательных, а затем и комплексных чисел, а также появление теории групп как раздела математики и выделение классов специальных функций в анализе.

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

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

Цель проведенного нами исследования — изучение распределения корней полинома.

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

— Существование корней в С;

— Распределение корней на плоскости комплексной переменной;

— Распределение вещественных корней полинома с вещественными коэффициентами;

— Приближенное вычисление корней полинома.

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

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

А также подкрепили теоретический курс практическими примерами.

1. Существование корней в C

Доказательство основной теоремы. Пусть f (z) — полином, рассматриваемый как функция от комплексной переменной z. Пусть f (z) и |f (z)| являются непрерывными функциями от z на всей плоскости комплексной переменной. Тогда существует такое значение z0, в котором f (z0) = 0 и |f (z0)| = 0, т. е. что поверхность щ = |f (z)| доходит до плоскости щ = 0 в точке z0.

Мы докажем, что если дана точка на поверхности щ = |f (z)|, которая расположена выше щ = 0, то в ее окрестности найдется точка поверхности, расположенная ниже данной точки. Тогда останется только доказать, что на поверхности щ = |f (z)| существует самая низкая точка, допустим, при z = z0. Она не может находится выше плоскости щ = 0, ибо тогда она не была бы самой низкой. Следовательно, |f (z0)| = 0 и, следовательно, f (z0) = 0, т. е. z0 есть корень полинома f (z).

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

Лемма 1. Дан полином с нулевым свободным членом. Тогда для любого найдется такое, что, как только .

Доказательство: Пусть | z | < 1. Тогда. Положим. Если, то, что и требовалось доказать.

Лемма 2. Полином есть непрерывная функция во всех точках плоскости комплексной переменной.

Доказательство: Пусть дан полином f (z) и точка z0. Расположим полином по степеням :

.

Тогда, так что

.

Правая часть есть полином от с нулевым свободным членом.

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

Лемма 3 (о возрастании модуля полинома). Если f (z) — полином, отличный от константы, то для любого M > 0 существует такое R > 0, что |f (z)|>M, как только |z|>R.

Доказательство:

Пусть, где полином от z-1 с нулевым свободным членом. В силу леммы 1 для найдется такое, что при будет. Модуль может быть сделан сколь угодно большим, именно, при будет. Возьмем. Тогда при будет и, так что .

Что и требовалось доказать.

Лемма 4. Точная нижняя грань значений |f (z)| достигается, т. е. существует такое z0, что при всех z.

Доказательство:

Обозначим точную нижнюю грань |f (z)| через m. Возьмем последовательность, k=1, 2,…, стремящуюся к m сверху. Каждая из этих чисел не является нижней гранью значений |f (z)|, ибо m — точная нижняя грань. Поэтому найдутся zk такие, что, k = 1, 2, … Воспользуемся теперь леммой о возрастании модуля. Для M = m+1 найдем такое R, что при |z|>R будет. Отсюда следует, что при всех k. Последовательность zk оказалась ограниченной, и из нее можно извлечь сходящуюся подпоследовательность. Пусть ее предел равен z0. Тогда в силу непрерывности | f (z)|. Кроме того,. Поэтому. Итак | f (z0)|=m, что и требовалось доказать.

Лемма 5 (лемма Деламбера). Пусть f (z) — полином, отличный от константы, и пусть. Тогда найдется такая точка, что .

Доказательство: Расположим полином f (z) по степеням :

.

Тогда. Пусть — первое отличное от нуля слагаемое после, так что (если k>1). Такое слагаемое имеется, так как f (z) не константа. Тогда

Здесь есть полином с нулевым свободным членом. По лемме 1 для найдется такое, что, как только .

Положим и. Тогда. Выберем r так, что. Для этого нужно взять. Далее, положим, т. е. возьмем. При таком выборе будет. Теперь положим при и. Тогда и Лемма доказана.

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

Теорема (принцип аргумента): Дан простой замкнутый контур и полином, не имеющий корней на контуре. Тогда число корней полинома внутри контура (с учетом кратности) равно, где есть приращение аргумента, вычисленное в предположении, что z проходит данный контур один раз в положительном направлении.

Доказательство: Над полем C каждый полином может быть разложен на линейные множители, соответствующие корням. Пусть — такое разложение. При обходе переменной z контура области все сомножители правой части и их произведение меняются непрерывно. Можно считать, что, и, следовательно,. Здесь приращения отсчитываются при однократном обходе по контуру области. Слагаемые в правой части равны или 0, в зависимости от того, лежит ли соответствующий корень внутри или вне контура. Поэтому, где — число корней, расположенных внутри контура.

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

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

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

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

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

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

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

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

Пусть теперь требуется узнать число корней этого полинома в круге радиуса 2. Преобладающим слагаемым на контуре, , оказывается, модуль которого равен 64. Сумма остальных слагаемых по модулю не превосходит. Слагаемое обходит начало координат 6 раз, и, отходя от не более чем на 34 единицы, тоже обходит начало 6 раз. Число корней полинома в круге радиуса 2 равно 6.

Итак, мы узнали, что имеет 3 корня в единичном круге и 3 корня в кольце между окружностями и .

Мы можем также рассмотреть непрерывность корней полинома.

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

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

.

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

Рассмотрим пример.

Пусть при. При корни равны 0 и 2. Далее,. При изменении от 0 до 1 корни сближаются и, при, сливаются при значении (рис.1). При дальнейшим увеличении корни становятся комплексными и расходятся вдоль прямой. У нас нет никаких оснований считать, который из корней пошел вверх: тот, который пришел слева, или тот, который пришел справа. Корни после столкновения как бы теряют индивидуальность.

3. Распределение вещественных корней полинома с вещественными коэффициентами Ограничение вещественных корней полинома с вещественными коэффициентами.

Лемма о возрастании модуля дает средство для ограничения всех корней по модулю сверху. Именно, если для найти такое, что | f (z)|>M=0, как только, то, очевидно, за пределами круга радиуса полином не имеет корней, и поэтому все его корни не превосходят по модулю.

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

Теорема (оценка Маклорена): Пусть, причем. Если не имеет отрицательных коэффициентов, то отсутствуют положительные корни, так что верхней оценкой для вещественных корней оказывается число 0. Пусть отрицательные коэффициенты имеются, -номер первого по порядку отрицательного коэффициента и A — максимум модулей отрицательных коэффициентов. Тогда вещественные корни не превосходят .

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

.

При будет, следовательно, Итак, при будет, так что все вещественные корни не превосходят, что и требовалось доказать.

При помощи оценки корней сверху легко получить и оценку снизу. Для этого достаточно рассмотреть полином

.

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

Оценка Макролена является довольно грубой оценкой.

Приведем пример.

Найдем оценку сверху и снизу для корней полинома Сверху:

Снизу: составим, имеем

Итак, .

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

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

(1)

называется системой Штурма для многочлена, если выполняются следующие требования:

Соседние многочлены системы (1) не имеют общих корней.

Последний многочлен, не имеет действительных корней.

Если — действительный корень одного из промежуточных многочленов системы (1),, то и имеют разные знаки.

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

Теорема Штурма: Если действительные числа и, , не являются корнями многочлена, не имеющего кратных корней, то и разность, где и — число перемен знаков системе Штурма (1) многочлена, равна числу действительных корней многочлена, заключенных между и .

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

Доказательство: Рассмотрим, как меняется число при возрастании. Пока, возрастая, не встретит корня ни одного из многочленов системы Штурма (1), знаки многочленов этой системы не будут меняться, и поэтому число остается без изменения. Ввиду этого, также ввиду условия 2) из определения системы Штурма, нам остается рассмотреть два случая: переход через корень одного из промежуточных многочленов, , и переход через корень самого многочлена .

Пусть — будет корнем многочлена,. Тогда, по условию 1), и отличны от нуля. Следовательно, можно найти такое положительное число, что в отрезке многочлены и не имеют корней и поэтому сохраняют постоянные знаки, причем, по условию 3), эти знаки различны. Отсюда следует, что каждая из систем чисел

(2)

И

(3)

обладает ровно одной переменой знаков независимо от того, каковы знаки чисел и. Так, например, если многочлен на рассматриваемом участке отрицателен, а положителен и если,, то системам (2) и (3) соответствуют системы знаков

.

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

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

Системам чисел

и (4)

соответствуют системы знаков

И ,

т.е. в системе Штурма теряется одна перемена. Если же знак на отрезке отрицателен, то снова, ввиду условия 4), многочлен меняет знак с плюса на минус при переходе через, т. е. ,; система чисел (4) соответствует теперь системы знаков

И ,

т.е. в системе Штурма снова теряется одна перемена.

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

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

Положим, чем обеспечивается выполнение условия 4) из определения системы Штурма. Действительно, еслидействительный корень многочлена, то. Если, то в окрестности точки, поэтому меняет знак с минуса на плюс при переходе через; это же верно тогда и для произведения. Аналогичные рассуждения проходят и в случае. Делим затем на и остаток от этого деления, взятый с обратным знаком, принимаем за :

.

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

. (5)

Так находится система Штурма.

Рассмотрим пример.

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

Найдем систему Штурма для, применяя указанный метод.

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

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

Таким образом, система Штурма многочлена теряет по одной перемене знаков при переходе от -3 к -2, от -1 к 0 и от 5 к 6. Следовательно, корни этого многочлена удовлетворяют неравенствам:

,

4. Приближенное вычисление корней полинома теорема корень полином переменная Метод непрерывных дробей.

Пусть для полинома известно, что он имеет один простой корень в интервале. Разложим по степеням:. Мы знаем, что лежит в интервале (0, 1). Сделаем инверсию этого интервала, посредством замены и умножим на. Получим. На этом этапе коэффициенты не изменяются, но только записываются в обратном порядке. Корень построенного полинома лежит в интервале (1, + ?). Заключим его между двумя соседними целыми числами,, и повторим процесс. Пусть, , и. Тогда для корня будет причем известно, что. Заменяя на и и учитывая характер изменения при этих заменах (заменяя на, мы увеличиваем, уменьшаем и увеличиваем; заменяя на, мы уменьшаем), получим границы для :

.

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

Применим метод непрерывных дробей к уточнению значения корня полинома,. Разложим полином по степеням. Т. е.. Решим систему:

Получим. Теперь делаем замену и умножаем на. Получим. Корень этого полинома заключен в интервале (1, 2). Разложение по степеням дает. Замена и умножение на дает. Корень этого полинома лежит в интервале (2, 3).

Разложим по степеням. Получим, после замены и умножения на получим и для корня этого полинома .

Итак: .

Рассмотрим еще один метод.

Метод Ньютона.

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

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

откуда для получаем приближенное значение

.

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

По приближению мы можем найти приближение по формуле

и т.д. Если последовательность сходится, то она сходится к корню полинома. Действительно, пусть при. Переходя к пределу в равенстве

Получим

откуда .

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

или, после подстановки в интеграле

.

Положив, получим

.

Поделим это равенство на и перенесем первые два члена в левую часть. Получим В левой части выражение равно .

Итак,

.

Пусть выбирается в окрестности точки, и в этой окрестности модуль ограничен снизу числом и модуль ограничен сверху числом. Тогда

.

Умножив на, получим

.

Поэтому, если, то. Для дальнейших приближений

…, .

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

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

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

Допустим, что и положительны на интервале .

Это значит, что возрастает и выпуклость ее графика направлена

вниз (рис.2).

Возьмем начальное приближение справа от корня. Геометрически очевидно, что следующее приближение будет ближе к чем и остается справа от .

Подтвердим это вычислением:

.

В силу возрастания заключаем, что, но и по условию. Далее,

ибо, а положительна на всем интервале .

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

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

(рис.3).Если же и сохраняют на противоположные знаки, то приближения стоит начинать слева (рис. 4,5).

рис. 4 рис.5

1. Курош А. Г. Курс высшей алгебры / А. Г. Курош — Москва: Москва «Наука» — 1968. — с. 241−265

2. Фадеев Д. К. Лекции по алгебре / Д. К. Фадеев — Москва: Москва «Наука» — 1984. — с. 214−241

3. Александров И. А. Теории функций комплексного переменного / И. А. Александров — Томск: Томский гос. универ. — 2002. — с. 221−224

4. Многочлен [Электронный ресурс] // Википедия: свободная энцикл. — Электрон. дан. — М., 2007. — URL:http://ru.wikipedia.org/wiki/Многочлен (дата обращения 15.05.2011).

www.