Линейная алгебра / lectures

Лекции по линейной алгебре

П.С. Петров

Дальневосточный федеральный университет Тихоокеанский океанологический институт им. В.И. Ильичева ДВО РАН

E-mail: [e-mail]

1Многочлены и их корни

1.1Определения

Определение 1. Многочленом Pn(x) называется формальное выражение, состоящее из степеней переменной x с коэффициентами из некоторого числового множества:

n

X

Pn(x) = anxn + an 1xn 1 + + a1x + a0 = aixi ;

i=0

где наибольшая степень переменной x называется степенью многочлена.

Смногочленами связаны такие понятия как:

•старший коэффициент;

•степень многочлена (самая большая степень x);

•свободный член.

Важно, что числовое множество, о котором идет речь в определении, может быть разным в разных контекстах. Например, это может быть множество вещественных чисел R (вспомните, что такое вещественные числа) или множество рациональных чисел Q (какие числа называются рациональными?). В зависимости от того, о каком числовом множестве идет речь, про соответствующие многочлены говорят "многочлены над множеством чисел . . . например "многочлены над R". Одним из центральных понятий, вокруг которых выросла современная алгебра, является понятие "корень многочлена":

Определение 2. Число x0 называется корнем многочлена Pn(x) если его подстановка в этот многочлен вместо x дает ноль:

Pn(x0) = anxn0 + an 1xn0 1 + + a1x0 + a0 = 0 :

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

1

том, что x – формальный символ, а x0 – число. Во втором определении

выражение anxn0 + an 1xn0 1 + + a1x0 + a0 – это сумма произведений ЧИСЕЛ, ее можно вычислить, тогда получится число. В первом опре-

делении anxn + an 1xn 1 + + a1x + a0 – это, как принято говорить, ФОРМАЛЬНОЕ ВЫРАЖЕНИЕ, где x – это просто буква. Следует раз-

личать сам многочлен Pn(x) – выражение с буквой – и его значение в некоторой точке x0 – конкретное число.

1.2Операции над многочленами. Деление с остатком.

Многочлены можно складывать, вычитать и умножать друг на друга, а также на числа. Все эти операции сводятся к "собиранию"членов с одинаковыми степенями переменной. Множество, элементы которого можно складывать, вычитать и умножать (при условии выполнения законов ассоциативности, коммутативности и дистрибутивности этих операций – т.е. переместительного, сочетательного и распределительного законов) в математике называют КОЛЬЦОМ. Поэтому часто встречается термин "кольцо многочленов от переменной x". Кстати, рациональные, целые и вещественные числа также образуют кольца. Кольцо, в котором на ненулевые элементы можно делить, в математике называют ПОЛЕМ. Так, например, вещественные и рациональные числа образуют поля. Целые же числа поля не образуют, ибо, например, при делении целого числа 3 на целое число 4 получается уже рациональное число 34 . Таким образом, операция деления в целых числах выводит нас за пределы множества целых чисел, или, как говорят, множество целых чисел НЕЗАМКНУТО относительно операции деления. Когда говорят, что на множестве задана некоторая операция, подразумевают ЗАМКНУТОСТЬ этого множества относительно этой операции. Следовательно множество целых чисел, незамкнутое относительно деления, не образует поля.

Похожая ситуация наблюдается с кольцом многочленов: хотя НЕКОТОРЫЕ многочлены делятся на другие, в общем случае такое деление невозможно.

Пример. Многочлен x2 + 2x + 1, очевидно, делится на многочлен x + 1. Однако, например, многочлен x не делится на x2 + 2. Их частное представляет собой РАЦИОНАЛЬНУЮ ФУНКЦИЮ:

x

x2 + 2

(по определению, рациональная функция есть частное двух многочленов). Заметим, что рациональные функции образуют ПОЛЕ. Легко по-

2

нять, что это поле относится к кольцу многочленов также, как поле рациональных чисел к кольцу целых чисел (чтобы его получить, мы просто составили все возможные дроби из элементов кольца – такое расширение кольца называется ПОЛЕМ ЧАСТНЫХ).

В некоторых кольцах, не являющихся полями (т.е. таких, где деление вообще говоря невозможно), можно ввести операцию ДЕЛЕНИЯ С ОСТАТКОМ. Такие кольца называются ЕВКЛИДОВЫМИ. Простейший пример евклидова кольца – целые числа. Любое целое число можно поделить на любое другое целое число с остатком, причем значение этого остатка по модулю непременно меньше делителя. В школе часто пользуются следующей записью для операции деления с остатком:

11 : 3 = 3 (остаток: 2)

Обратите внимание, что операция деления с остатком имеет смысл только в том случае, если можно определить, что означает "остаток МЕНЬШЕ делителя". То есть в кольце должна существовать операция СРАВНЕНИЯ двух элементов по некоторому признаку. Для чисел все просто – у них есть абсолютная величина, что же касается многочленов, то у них такой величины нет – ведь это просто формальные выражения с буквой-неизвестной. Многочлены сравнивают по их степени. Поэтому определение деления с остатком в кольце многочленов таково:

Определение. Говорят, что многочлен P (x) делится на многочлен Q(x) с остатком, если существуют такие многочлены D(x) и R(x), что

P (x) = D(x)Q(x) + R(x) ;

причем степень многочлена R(x) меньше степени многочлена Q(x). Остаток часто обозначают буквой R – от английского "remainder".

Степень многочлена часто обозначают как deg(P (x)) – от слова "degree". Теорема. Произвольный многочлен P (x) (над некоторым полем) делится с остатком на произвольный ненулевой многочлен Q(x) (это озна-

чает, что кольцо многочленов евклидово).

Доказательство. Если степень deg(P (x)) < deg(Q(x)), то

P (x) = 0Q(x) + P (x) ;

т.е. частное равно нулю, а остаток от деления равен P (x). Если же

deg(Q(x)) deg(P (x)), то пусть P (x) = pnxn + pn 1xn 1 : : : , Q(x) = qmxm + qm 1xm 1 : : : , m n. Рассмотрим тогда многочлен

P (1)(x) = P (x) pn xn mQ(x) : qm

3

Его степень, очевидно, меньше	степени P (x) (почему?). Если
deg(P (1)(x)) < deg(Q(x)), то P (x) =	pn	xn mQ(x) + P (1)(x) ; т.е. деление с
	qm

остатком закончено, частное –	pn	xn m, остаток P (1)(x). Если нет, то те-
	qm

перь мы удалим старший член многочлена P (1)(x) с помощью вычитания Q(x) с подходящим сомножителем, получим многочлен P (2)(x) со степенью n 2 и будем продолжать эти шаги, пока в конце концов не получим очередной многочлен со степенью, меньшей, чем у Q(x) (объясните, что будет в этом случае частным, а что остатком от деления!).

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

Также заметьте, что выражение pn – это дробь. Таким образом, это до-

qm

казательство годится только для случая многочленов НАД ПОЛЕМ. Доказательство, а также множество других фактов о многочленах кольцах и полях, можно также прочесть в книге [1] (полезно ознакомиться, например, с §11, 13, 14 третьей главы).

Пример. Разделим 2x5 + x3 + 7x2 + 3x + 1 на 3x2 + 4x + 10:

2x5 + x3 + 7x2 + 3x + 1 = 3x2 + 4x + 10

											2					x3					+		2x5 + x3 + 7x2 + 3x + 1 32 x3(3x2 + 4x + 10)																																			=
											3
																																																3x2 + 4x + 10
																												2					x3 +							38 x4								173 x3 + 7x2 + 3x + 1							=
																							3																									3x2 + 4x + 10
2								3			8										2					38 x4 173 x3 + 7x2 + 3x + 1 + 98 x2(3x2 + 4x + 10)
		3			x										9			x				+																												3x2 + 4x + 10									=
																							2											3		8							2				199 x3 + 1439 x2 + 3x + 1
																										3					x							9				x			+					3x2 + 4x + 10							=
																							2											3		8							2				199 x3				+ 1439 x2 + 3x + 1
																															x											x			+												=
																										3												9												3x2 + 4x + 10
2						3					8								2				19													199 x3 + 1439														x2 + 3x + 1 + 2719 x(3x2 + 4x + 10)
3			x									9				x								27							x +																					3x2 + 4x + 10									=
																							2													8										19						50527 x2 + 27127 x + 1
																														x3												x2							x +							=
																										3													9									27				3x2	+ 4x + 10
	2						3				8									2			19													505										50527 x2 + 27127 x + 1 50581 (3x2 + 4x + 10)
	3			x									9				x								27							x +					81								+							3x2 + 4x + 10								=

4

2		3		8		2		19		505			120727 x 496981
3	x			9	x			27	x +		81	+	3x2 + 4x + 10

Таким образом, частное в нашем случае 23 x3 89 x2 1927 x + 50581 , а остаток от деления равен 120727 x 496981 .

1.3Отщепление корней

Как и в случае с числами, говорят, что многочлен P (x) делится на многочлен Q(x), если при делении P (x) на Q(x) с остатком этот остаток равен нулю1, т.е. если существует такой многочлен D(x) что

P (x) = D(x)Q(x).

Для нас с Вами деление многочленов представляет интерес в рамках задачи о нахождении корней многочлена.

Определение. Число x0 является корнем многочлена P (x), если

P (x0) = 0.

Вероятно, Вам известен следующий важный результат:

Теорема (Безу). Число x0 является корнем многочлена P (x) тогда и только тогда, когда многочлен P (x) делится на многочлен x x0.

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

то P (x) = P1(x)(x x0), а следовательно P (x0) = P1(x0)(x0 x0) = 0. Теперь проведем доказательство в обратную сторону: пусть P (x0) = 0.

Тогда разделим многочлен P (x) с остатком на многочлен x x0. В остатке мы должны получить многочлен, степень которого меньше степени делителя x x0. Следовательно, этот остаток - многочлен степени 0, т.е. константа: R(x) = C, причем

P (x) = D(x)(x x0) + C ;

вычислим значение многочлена при x = x0: P (x0) = D(x0)(x0 x0)+C = C ; однако по условию P (x0) = 0, ergo2 C = 0.

1Да-да, мы определили более простую операцию – деление через более сложную – деление с остатком! Математики так постоянно делают. Анекдот:

Задача 1. Как вскипятить чайник? Решение: налить воду в чайник, поставить его на плиту, включить плиту.

Задача 2. Чайник с водой стоит на плите. Как его вскипятить? Физик: Включить плиту!

Математик: Выливаем воду из чайника, далее пользуемся решением задачи 1.

2лат. "следовательно". Искусство строить логические рассуждения родилось в Древней Греции, предположительно в пифагорейской школе. Первым известным трактатом по логике стал труд Аристотеля "Аналитика". Аристотелевой моделью ло-

5

Эта теорема очень полезна при отыскании корней многочленов "вручную": если Вам известен корень x0 многочлена P (x) степени n, то можно отделить его:

P (x) = (x x0)P1(x) ;

где степень P1 уже равна n 1. Теперь задача свелась к поиску многочленов степени n 1, а это уже несколько проще. На самом деле, точно находить корни многочленов, как правило, имеет смысл лишь в тех случаях, когда они рациональны (потому что иррациональные корни, такие

как, например p3 + p2, не особенно удобны для работы). К счастью для нас, в математике зачастую все нужные вещи достаточно просты, а все сложные вещи – бесполезны. В данном случае эта приятная особенность природы вещей выражается в том, что рациональные корни любого многочлена легко найти с помощью весьма нехитрого перебора:

Теорема. Пусть коэффициенты многочлена P (x) – целые числа. Тогда любой целый корень многочлена есть делитель свободного члена P (x). Любой рациональный корень P (x) имеет своим числителем делитель свободного члена P (x), а знаменателем – делитель старшего члена

P (x).

Доказательство. Пусть несократимая дробь

p есть корень много-

члена P (x) = anxn + an 1xn 1 + : : : a0. Тогда

q

p

n

p

n 1

p

an

+ an 1

+ + a1

+ a0

= 0 :

q

q

q

Домножим это соотношение на qn, получим:

anpn + an 1pn 1q + + a1pqn 1 + a0qn = 0 ;

это равенство можно переписать двумя способами:

anpn = q(an 1pn 1 + + a1pqn 2 + a0qn 1) ;

p(anpn 1 + an 1pn 2q + + a1qn 1) = a0qn :

Из первой записи следует, что anpn делится на q, а из второй – что a0qn делится на p. Так как дробь pq несократима, то p и q взаимно просты. Следовательно из делимости anpn на q следует, что an делится на q (объясните, почему). Аналогично получаем, что a0 делится на p. QED 3

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

3QED = quod erat demonstrandum, лат. "что требовалось доказать": еще одно прекрасное латинское выражение.

6

Пример. Давайте найдем корни многочлена P (x) = x4 x3 5x2 + 7x 2. Сначала воспользуемся второй теоремой: так как старший коэффициент многочлена равен 1, знаменатели всех рациональных его корней равны 1, то есть если многочлен имеет рациональные корни, то они целые. Все эти целые числа должны быть делителями свободного коэффициента – т.е. числа 2. Вот эти делители: 1; 2. Проверим их: P (1) = 14 3(13) + 3(12) 3 1 + 2 = 0, следовательно 1 – корень нашего многочлена. Далее, проверяем: P ( 1) = 12, P (2) = 0, P ( 2) = 12. Таким образом, целых корней у нас два – это x1 = 1 и x2 = 2. По первой теореме P (x) делится без остатка на (x 1)(x 2). Выполнив деление,

получим, что P (x) = x2 + 2x 1. Мы получили квадратный трех-

(x 1)(x 2) p

член, корни которого легко найти через дискриминант: это x = 2 1 p 3

и x4 = 2 1. Таким образом, мы нашли все 4 корня многочлена.

1.4Формулы для корней

Как известно, существует общая формула для корней квадратного уравнения (Вы хорошо знаете, как воспользоваться ею – необходимо вычислить дискриминант, а затем найти сами корни). Аналогичные формулы существуют для уравнений третьей степени (формулы Кардано), а также для уравнений четвертой степени (формулы Феррари). Для уравнений степени 5 и выше таких формул нет. Более того, можно доказать, что их нельзя получить (это результат теории Галуа). Дайте себе труд заглянуть в Википедию и посмотреть, как выглядят формулы Кардано. Старайтесь пользоваться англоязычной википедией http://en.wikipedia.org, она существенно обширнее, в ней меньше неточностей и, кроме того, Вы сможете практиковаться в английском, который Вам в любом случае придется освоить. Кстати, Википедия в настоящее время представляет собой в том числе и очень хороший справочник по всем разделам математики. Не стесняйтесь заглядывать в нее, если пропустили лекцию или встретили незнакомое понятие. Если Вы посмотрели на формулы Кардано, то, вероятно, обнаружили, что они исключительно сложны для использования. На самом деле, никто ими и не пользуется! В том случае, когда математиков интересуют нецелые корни уравнений, они находят их численно. Соответствующие функции встроены во все современные вычислительные системы. Так, например, MATLAB (с которым Вам непременно следует познакомиться – не поленитесь установить его на Ваш компьютер) содержит функцию roots, которая принимает набор коэффициентов многочлена и выдает его корни. Вот что она дает для многочлена, рассмотренного в примере из предыдущего раздела

7

лекции:

¿ roots([1 -1 -5 7 -2])

ans =

-2.4142 2.0000 1.0000

0.4142

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

1.5Оценка для корня

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

Теорема. Все корни многочлена P (x) = anxn+an 1xn 1 удовлетворяют следующим неравенствам:

	a0		x	j	c + janj	;
	jb + a0j				janj
			j

+ +a1x+a0

(1)

где c = maxfja0j; ja1j; : : : ; jan 1jg, b = maxfja1j; ja2j; : : : ; janjg

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

x c + janj ; janj

причем для определенности будем считать, что an > 0 (объясните, как остальные случаи получаются из этого!). Очевидно, что самый большой корень в этом случае у многочлена будет тогда, когда все остальные коэффициенты будут отрицательными (почему?). Причем если все их

8

сделать равными c, то корень может только увеличиться (почему?). По-

этому оценим корни многочлена n n 1 , оче-

P (x) = anx cx + cx c

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

P .

	n	cx	n 1	+ cx c = 0 ;
P (x) = anx

anxn cxn 1 = 0 ; x 1

(мы воспользовались формулой суммы членов геометрической прогрес-

сии)

xn(x 1) c (xn 1) = 0 ; a0

xn

x

a0 + c

+

c

= 0 ;

a0

a0

x =

a0 + c

c

<

a0 + c

;

a0

xna0

a0

так как xn – большое положительное число.

1.6Книги

Важно понять, что даже самое тщательное изучение лекций не дает полноценного понимания материала курса. Нужно обязательно пользоваться дополнительной литературой. Студент, который не читает учебники, не имеет шансов стать специалистом. Вы должны хорошо это усвоить. По материалу этого занятия можно рекомендовать две книги: [2, 1]. Разумеется, с бумажными книгами работать приятнее, так что Вы можете посетить библиотеку ДВФУ, где оба эти учебника есть. Однако по меньшей мере для предварительного знакомства удобнее (и быстрее) найти электронный вариант. Думаю, что Вам может помочь ссылка http://lib.homelinux.ru. Вы должны научиться очень быстро находить нужную Вам книгу в сети интернет, это поможет Вам в учебе и дальнейшей работе. Используйте открытые библиотеки, торрент-трекеры (Надеюсь, Вы знаете, что это такое? Если нет - срочно гуглить.) и прочие хранилища.

1.7Задачи для практического занятия

Оцените корни многочленов, а затем вычислите их.

1.

x5 + 2x4 14x3 55x2 68x 28

9

2.

x3 + 3x2 + 3x + 1

3.

x5 + 5 x4 + 8 x3 + 8 x2 + 7 x + 3

1.8Упражнения

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

1.Найдите все корни многочленов

a x3 + 13x2 + 6x 72 b x3 6x2 + 12x 8

c x4 2x3 23x2 2x 24 d x3 2x2 8x 5

2.Выполните деление многочленов с остатком: a x3 + 9x2 + 27x + 27 на x + 3

b x4 + 7x2 + 22x + 8 на x2 2x + 2

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

a x4 x3 5x2 + 7x 2

b x4 2x3 23x2 2x 24

4.Воспроизведите по памяти доказательство теоремы Безу. Если споткнулись, разберите это место, а затем попробуйте снова.

5.Изучите функции syms и solve системы MATLAB. Как использовать их для вычисления корней многочленов в радикалах? Иногда это удобнее функции roots! Проверьте Ваши расчеты.

6.Докажите, что многочлен степени n имеет не более n корней.

10