Элементы высшей алгебры: нахождение корней многочленов высших степеней

КурсоваяПомощь в написанииУзнать стоимостьмоей работы

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

Министерство образования и науки Российской Федерации

Воронежский государственный технический университет

КУРСОВАЯ РАБОТА

по дисциплине «Высшая математика»

Тема «Элементы высшей алгебры: нахождение корней многочленов высших степеней»

Выполнил:

студент 1 курса

группы АИ-101

Картунов А.А.

Проверил:

Купцов В.С.

Воронеж, 2011

Элементы высшей алгебры: нахождение корней многочленов высших степеней

Задача

Заключение

Математика ум в порядок приводит

М. Ломоносов

Становление и развитие математики как науки, возникновение ее новых разделов тесно связано с развитием потребностей общества в измерениях, контроле, особенно в областях аграрной, промышленной и налогообложения. Первые области применения математики были связаны с созерцанием звезд и земледелием. Изучение звездного неба позволило проложить торговые морские пути, караванные дороги в новые районы и резко увеличить эффект торговли между государствами. Обмен товарами приводил к обмену культурными ценностями, к развитию толерантности как явления, лежащего в основе мирного сосуществования различных рас и народов. Понятие числа всегда сопровождалось и нечисловыми понятиями. Например, один, два, много… Эти нечисловые понятия всегда ограждали сферу математики. Математика придавала законченный вид всем наукам, где она применялась. В Европе сложилось разделение на гуманитарные и естественные науки по степени влияния математики на эти части.

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

В математике, многочлены или полиномы от одной переменной — функции вида где c_i — фиксированные коэффициенты, а x — переменная. Многочлены составляют один из важнейших классов элементарных функций.

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

Элементы высшей алгебры. Нахождение корней многочленов высшей степени

Многочлен (или полином) от n переменных — есть конечная формальная сумма вида

где I = (i1,i2,…, in) есть набор из целых неотрицательных чисел (называется мультииндекс), c_I — число (называемое «коэффициент многочлена»), зависящее только от мультииндекса I.

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

В случае, когда многочлен имеет всего два ненулевых члена, его называют двучленом или биномом, в случае, когда многочлен имеет всего три ненулевых члена, его называют трёхчленом.

Полной степенью (ненулевого) одночлена называется целое число

| I | = i₁ + i₂ + … + i_n.

Степенью многочлена называется максимальная из степеней его одночленов, тождественный нуль не имеет степени Многочлен, который можно представить в виде произведения многочленов низших степеней с коэффициентами из данного поля, называется приводимым (над данным полем), в противном случае — неприводимым. Неприводимые многочлены играют в кольце многочленов роль, сходную с ролью простых чисел в кольце целых чисел. Например, верна теорема: если произведение pq делится на неприводимый многочлен л, то p или q делится на л. Каждый многочлен, степени большей нуля, разлагается в данном поле в произведение неприводимых множителей единственным образом (с точностью до множителей нулевой степени).

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

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

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

Корень многочлена над полем k — это элемент, который после подстановки его вместо x обращает уравнение в тождество.

Теорема Безу. Остаток от деления многочлена P (x) на двучлен x? a равен P (a). Предполагается, что коэффициенты многочлена содержатся в некотором коммутативном кольце с единицей (например, в поле вещественных или комплексных чисел).

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

Поделим с остатком P (x) = (x? a) Q (x) + R (x). Так как degR (x) < deg (x? a) = 1, R (x) — многочлен степени 0. Подставляя a, поскольку (a? a) Q (a) = 0, имеем P (a) = R (x).

Другой вариант доказательства.

Запишем формулу Тейлора для многочлена:

Берём x₀ = a. Теорема доказана.

Следствие. Число a является корнем многочлена p (x) тогда и только тогда, когда p (x) делится без остатка на двучлен x? a.

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

Всякий многочлен p (x) с вещественными или комплексными коэффициентами имеет по крайней мере один, вообще говоря, комплексный, корень.

Теорема (основная теорема алгебры). Всякий отличный от константы многочлен с комплексными коэффициентами имеет корень в поле комплексных чисел.

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

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

Доказательство. У многочлена f (x) есть корень a, значит, по теореме Безу, он представим в виде (x? a) g (x), где g (x) — другой многочлен. Применим теорему к g (x) и будем применять её таким же образом до тех пор, пока на месте g (x) не окажется линейный множитель. На самом деле существует еще несколько прямых следствий.

Как предположение эта теорема впервые встречается у немецкого математика Питера Роуте (р. 1617). Первые доказательства основной теоремы алгебры принадлежат Жирару, 1629 г., и Декарту, 1637 г., в формулировке, отличной от современной. Маклорен и Эйлер уточнили формулировку придав ей форму, эквивалентную современной: «Всякий многочлен с вещественными коэффициентами можно разложить в произведение линейных и квадратичных множителей с вещественными коэффициентами.»

Д’Аламбер первым в 1746 г. опубликовал доказательство этой теоремы. Его доказательство основывалось на лемме, что если для какого-нибудь x f (x)?0, где f (x) — многочлен степени ?1, то найдется точка x1 такая, что |f (x1)|<|f (x)|. Доказательство это было бы совершенно строгим, если бы Д’Аламбер мог доказать, что где-то на комплексной плоскости значение модуля многочлена достигает наименьшего значения. Во 2-й половине XVIII века появляются доказательства Эйлера, Лапласа, Лагранжа и других. Во всех этих доказательствах предполагается заранее, что какие-то «идеальные» корни многочлена существуют, а затем доказывается, что по крайней мере один из них является комплексным числом. Гаусс первым дал доказательство без этого предположения (единственным недоказанным Гауссом предположением было то, что многочлен с действительными коэффициентами, принимающий как положительное, так и отрицательное значение, также имеет и корень, что весьма геометрически наглядно). Его доказательство, по существу, содержит построение поля разложения многочлена.

Со времён доказательства теоремы в алгебре было открыто очень много нового, поэтому сегодня «основной» эту теорему назвать уже нельзя: это название теперь является историческим.

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

Многочлен с вещественными коэффициентами p (x) можно записать в виде

где

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

Корни многочлена связаны с его коэффициентами формулами Виета.

Формулы Виета — формулы, выражающие коэффициенты многочлена через его корни.

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

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

Иначе говоря (? 1)^ka_k равно сумме всех возможных произведений из k корней.

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

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

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

Пример. Квадратное уравнение

Сумма корней приведенного квадратного уравнения равна второму коэффициенту с обратным знаком, а произведение корней равно свободному члену. Или Если x₁ и x₂ — корни квадратного уравнения ax² + bx + c = 0, то

и .

В частном случае, если a = 1 (приведенная форма x² + px + q = 0), то

x₁ + x₂ =? p и x₁x₂ = q.

Пример. Кубическое уравнение

Если x₁, x₂, x₃ — корни кубического уравнения p (X) = ax³ + bx² + cx + d = 0, то Способ нахождения корней линейных и квадратичных многочленов, то есть способ решения линейных и квадратных уравнений, был известен ещё в древнем мире. Поиски формулы для точного решения общего уравнения третьей степени продолжались долгое время (следует упомянуть метод, предложенный Омаром Хайямом), пока не увенчались успехом в первой половине XVI века в трудах Сципиона дель Ферро, Никколо Тарталья и Джероламо Кардано. Формулы для корней квадратных и кубических уравнений позволили сравнительно легко получить формулы для корней уравнения четвертой степени.

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

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

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

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

Рассмотрим многочлен f (x) с вещественными коэффициентами. Конечная упорядоченная последовательность отличных от нуля многочленов с вещественными коэффициентами называется рядом Штурма для многочлена f (x), если выполнены следующие условия: не имеет корней;

если и, то ;

если ,

то произведение меняет знак с минуса на плюс, когда x, возрастая, проходит через точку c, т. е. когда существует такое д > 0, что

для и для .

Значением ряда Штурма в точке c называется количество смен знака в последовательности f0©, f1©,…, fs© после исключения нулей.

Теорема Штурма Пусть f (x) — ненулевой многочлен с вещественными коэффициентами, f0(x), f1(x),…, fs (x) — некоторый ряд Штурма для него, [a, b] — промежуток вещественной прямой, причём. Тогда число корней многочлена f (x) на промежутке [a, b] равно W (a)? W (b), где W (c) — значение ряда Штурма в точке c.

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

;

Если fk (x) (k > 0) имеет корни, то, где — остаток от деления многочлена f (x) на многочлен g (x) в кольце многочленов, иначе s = k.

Для произвольного многочлена, отличающегося от константы, можно положить, и далее следовать приведенному выше способу. Здесь (f (x), f'(x)) — наибольший общий делитель многочленов f (x) и f'(x). Если многочлен f (x) есть ненулевая константа, то его ряд Штурма состоит из единственного многочлена f0(x) = f (x).

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

Построим указанным выше способом ряд Штурма для многочлена

f (x) = (x? 1)(x? 3) = x2? 4x + 3

Построим указанным выше способом ряд Штурма для многочлена

f(x) = (x? 1)(x? 3) = x²? 4x + 3


Многочлен f_i(x)	Знак многочлена в точке

f₀(x) = x²? 4x + 3
f₁(x) = 2x? 4
f₂(x) = 1
Значение ряда в точке

Таким образом, по теореме Штурма число корней многочлена f (x) равно: 2? 0 = 2 на промежутке

2? 0 = 2 на промежутке (0,4)

2? 1 = 0 на промежутке (0,2)

Метод Лобачевского.

Для отделения корней Лобачевский предложил метод квадратирования — способ построения по исходному уравнению нового уравнения, кони которого связаны с корнями исходного следующим образом: y_i=-x_i²

Процедура выполнения многократна, пока не достигнем серьёзной разницы модуля разности корней b₀⁽^m⁾yⁿ + b₁⁽^m⁾yⁿ^-1+…+ b_n_-1⁽^m⁾y+ b_n⁽^m⁾=0 (*)

Пусть уравнение (*) получено в результате m-го шага квадрирования.

m=1 b₀⁽¹⁾=a₀², b₁⁽¹⁾= a₁²=2 a₀ a₂

b_k⁽¹⁾=a_k²-2a_k-1a_k+1+2a_k-2a_k+2…, k=0,n

При получении b_k коэффициента, который рассчитывается как квадрат соответствующего коэффициента a_k минус удвоенное произведение соседних коэффициентов с a_k плюс удвоенное произведение следующей пары соседей, чередуя знаки, пока в число соседних коэффициентов не попадут а₀ и а_n.

m>1b₀^(m)=(b₀^(m-1))², b₁^(m)=(b₁^(m-1))²-2b₀^(m-1)b₂^(m-1)

b_k^(m)=(b₀^(m-1))²-2b_k-1^(m-1)b_k-1^(m-1)+2b_k-2^(m-1)b_k+2^(m-1)

Критерий остановки: b_k⁽^m⁾?(b₀⁽^m^-1))², k=0,n

Получим корень: y_i⁽^m⁾=-x_i², i=1,nсвязь корней, полученных на m-шаге процесса квадрирования с корнями исходного уравнения.

y_i на m-шаге :

Отсюда

i=1,n

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

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

Метод половинного деления.

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

Пример. Отделим аналитически корни уравнения .

Рассмотрим функцию .

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

при ;

;

или ;

;

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

Для удобства составим таблицу знаков функции :



;	;	;

Следовательно, уравнение, то есть имеет два действительных корня: и .

Уменьшим промежутки, в которых находятся корни:



;	;	;	;	;

Следовательно, уравнение, то есть имеет два действительных корня: и .

Уточним корень уравнения методом проб (методом половинного деления) с точностью до 0,01.

Результаты расчётов поместим в таблице:



		2,5	39,0625	62,5		34,5625
	2,5	2,25	25,62 890 625	45,5625	40,5	13,69 140 625
	2,25	2,125	20,39 086 914	38,3 828 125	36,125	5,648 681 641
	2,125	2,0625	18,9 571 838	35,9 472 656	34,3 125	2,159 194 946
	2,0625	2,3 125	17,2 368 259	33,52 355 957	33,78 125	0,539 429 665
	2,3 125	2,15 625	16,50 588 995	32,75 587 463	32,50 195 313	— 0,240 188 539
2,15 625	2,3 125	2,234 375	16,76 328 689	33,13 823 509	32,75 439 453	0,147 127 453
2,15 625	2,234 375	2,1 953 125	16,63 421 502	32,94 668 508	32,62 805 176	— 0,47 151 658

Итак, корень уравнения (то есть уравнения) принадлежит отрезку. Следовательно, можно сделать вывод, что с точностью корень уравнения .

Пример. Отделим корни уравнения и найдём их с точностью методом деления пополам.

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

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

1) решение, принадлежащее отрезку и приблизительно равное ;

2) решение, принадлежащее отрезку и приблизительно равное 2,1.

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

1) Делим отрезок пополам:; на концах отрезка функция имеет противоположные знаки.

2) Делим отрезок пополам:; на концах отрезка функция имеет противоположные знаки.

3) Делим отрезок пополам:; на концах отрезка функция имеет противоположные знаки.

4) Делим отрезок пополам:; на концах отрезка функция имеет противоположные знаки.

5) Делим отрезок пополам:; на концах отрезка функция имеет противоположные знаки.

6) Делим отрезок пополам:; на концах отрезка функция имеет противоположные знаки.

7) Делим отрезок пополам:; на концах отрезка функция имеет противоположные знаки.

8) Делим отрезок пополам:; на концах отрезка функция имеет противоположные знаки.

Итак, первый корень уравнения (то есть уравнения) принадлежит отрезку. Следовательно, можно сделать вывод, что с точностью первый корень уравнения: .

Снова рассмотрим функцию. Эта функция непрерывна на отрезке, причём и, то есть. Для нахождения второго корня уравнения, то есть уравнения, снова воспользуемся методом половинного деления: