1   2   3
Ім'я файлу: курсовая по дискретке 2 (1).docx
Розширення: docx
Розмір: 160кб.
Дата: 08.06.2021
скачати

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФГАОУ ВПО «СЕВЕРО-КАВКАЗСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»

ИНСТИТУТ МАТЕМАТИКИ И ЕСТЕСТВЕННЫХ НАУК

КАФЕДРА ВЫСШЕЙ АЛГЕБРЫ И ГЕОМЕТРИИ

Курсовая работа
по дисциплине

«Фундаментальная и компьютерная алгебра»

на тему:

«Отделение действительных корней многочленов»

Выполнила:

Буняева Ирина Евгеньевна студентка группы МКН-б-о-13-1 направления 02.03.01 «Математика и компьютерные науки» очной формы обучения

________________________

(подпись)
Руководитель работы:

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

(подпись руководителя) (дата)
Работа выполнена и

защищена с оценкой _________________________ Дата защиты______________
Члены комиссии: доцент __________ В.В.Бондарь

(должность) (подпись) (И.О. Фамилия)
профессор _____________ О.П.Молофей

доцент _____________ Л.П.Копыткова

Ставрополь, 2015 г.
Введение………………………………………………………………………….

1 Отделение действительных корней многочленов…………………………...

1.1 Теорема Штурма…………………………………………………............

1.2 Другие теоремы о числе действительных корней…………………………

1.3 Теорема Бюдана-Фурье и Декарта………………………………………….

1.4 Приближенное вычисление корней методами Ньютона и линейной интерполяции ……………………………………………………………………

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

Заключение………………………………………………………………………

Список использованных источников…………………………………………….

,Введение

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

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

Задачи:

  1. Изучить основные методы и теоремы отделения действительных корней многочленов.

  2. Рассмотреть приближенное вычисление корней методами Ньютона и линейной интерполяции.

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

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





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

1.1 Теорема Штурма

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

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

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

1,3,-2,1,-4.-8,-3,4,1. (1)

Выпишем последовательно знаки этих чисел:

+,+,-,+,-,-,-,+,+. (2)

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

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

(3)

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

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

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

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

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

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

Если действительное число не является корнем данного многочлена , а (3)-система Штурма для этого многочлена, то возьмем систему действительных чисел



вычеркнем из нее все числа, равные нулю, и обозначим через число перемен знаков в оставшейся системе; назовем числом перемен знаков в системе Штурма (3) многочлена при .

Справедлива следующая

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

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

Для доказательства теоремы рассмотрим, как меняется число при возрастании . Пока , возрастая, не встретит корня ни одного многочленов системы Штурма (3), знаки многочленов этой системы не будут меняться, и поэтому число останется без изменения.

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

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

(4)

и

(5)

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

-, +, +; -, -, +.

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

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

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

(6)

Соответствуют, следовательно, системы знаков

-, + и +, +,

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

+, -, и -, -,

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

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

Этим доказана, очевидно, теорема Штурма. Для того чтобы воспользоваться ею для разыскания общего числа действительных корней многочлена , достаточно в качестве взять нижний предел отрицательных корней, в качестве верхний предел положительных корней. Проще, однако, поступить следующим образом. Ввиду леммы о корнях многочлена, существует такое положительное число , быть может и очень большое, что при знаки всех многочленов системы Штурма будут совпадать со знаками их старших членов. Иными словами, существует столь большое положительное значение неизвестного , что знаки соответствующих ему значений всех многочленов системы Штурма совпадают со знаками их старших коэффициентов; это значение , вычислять которое нет необходимости, условно обозначается символом ∞. Существует, с другой стороны, столь большое по абсолютной величине отрицательное значение , что знаки соответствующих ему значений многочленов четной степени и противоположны знакам старших коэффициентов для многочленов нечетной степени; это значение условимся обозначать через -∞. В отрезке (-∞;∞) содержатся, очевидно, все действительные корни всех многочленов системы Штурма и, в частности, все действительные корни многочлена . Применяя к этому отрезку теорему Штурма, мы найдем число этих корней, применение же теоремы Штурма к отрезкам (-∞;0) и (0;∞) дает соответственно число отрицательных и число положительных корней многочлена .

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

.

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

. (7)

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

Отсюда вытекает, что построенная нами система многочленов



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

,

мы получим, что служит корнем и для . Продолжая далее, мы получим, что служит общим корнем для и , что противоречит, однако, нашим предположениям. Наконец, выполнение условия 3) вытекает непосредственно из неравенства (7): если .

Пример 1: Применим метод Штурма к многочлену



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

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













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

Таблица знаков многочленов Таблица 1.
















Число перемен знаков

-∞

-

+

-

-

+

-

4



+

+

+

-

-

-

1

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

Пример 2. Применим метод Штурма к более простому многочлену.



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

Система Штурма для многочлена будет:









Найдем число перемен знаков в этой системе при ,

Таблица знаков переменных Таблица 2.












Число перемен знаков

-∞

-

+

-

+

3



+

+

+

+

0

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

Таблица знаков переменных Таблица 3.












Число перемен знаков

-3

-

+

-

+

3

-2

+

0

-

+

2

-1

+

-

-

+

2

0

-

0

+

+

1

1

+

+

+

+

0

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




  1   2   3

скачати

© Усі права захищені
написати до нас