Мосин В.Г. Математические основы компьютерной графики: Монография
Подождите немного. Документ загружается.
A.1. Определители 161
Пример 102 Еще один числовой пример на применение метода Гаусса.
213
532
143
← III
← I
= −
143
532
213
−I ∗5
−I ∗2
= −
143
0 −17 −13
0 −7 −3
=
= −
143
01713
073
−III ∗ 2
= −
143
037
073
−II ∗ 2
=
= −
14 3
03 7
01−11
← III
← II
=
14 3
01−11
03 7
−II ∗ 3
=
14 3
01−11
00 40
=40.
Прежде всего, на первом-первом месте определителя мы организуем 1. Это де-
лается для того, чтобы дальнейшие действия по построению нулей ниже главной
диагонали было легче (то есть — чтобы не приходилось оперировать с дробными
числами). Для этого на первом шаге мы меняем местами первую и третью строки.
При этом определитель меняет знак.
На втором шаге выкладки мы устраиваем два нуля ниже единицы, расположенной
на первой-первой позиции в определителе. Для этого мы отнимаем от второй
строки первую, домножив ее на 5, и от третьей строки — первую, домножив ее
на 2.
На третьем шаге мы выносим (−1) из второй и из третьей строк. При этом сам
определитель приобретает дополнительный множитель (−1)
2
, который мы не за-
писываем, так как (−1)
2
=1.
Далее нам во что бы то ни стало необходимо получить единицу на втором-втором
месте определителя, так как это позволит нам применить тот же алгоритм полу-
чения нулей ниже главной диагонали, что и в первом столбце. Но на это у нас
уйдет несколько шагов
6
.
На следующем шаге мы отнимаем от втрой строки третью, домножив ее на 2.
Выгода от этого на первый взгляд, конечно, сомнительная, но все-таки: после
этого действия числа во второй строке стали меньше!
Воодушевленные таким пусть небольшим, но все же успехом, продолжим умень-
шать фигурирующие в определителе числа: отнимаем от третьей строки вторую,
домножив ее на 2.
В третьей строке на втором месте наконец появилась долгожданная единица
7
!
Остается расположить ее на втором-втором месте в определителе.
Для этого мы меняем местами вторую и третью строки. При этом определитель
снова меняет знак на противоположный, и коэффициент (−1), появившийся перед
определителем после первого звена выкладки, исчезает.
Теперь для получения верхнего треугольного определителя достаточно отнять от
третьей строки вторую, домножив ее на 3, что мы и делаем.
Полученный определитель равен произведению элементов главной диагонали.
6
Можно было бы в этой ситуации поступить гораздо прямолинейнее: просто вынести
из второй строки 17 как общий множитель. Однако все остальные операции пришлось
бы выполнять уже с дробными числами. Возможно, вам все равно, с какими числами
оперировать: с дробными или с целыми. А нам — не все равно. Мы поступим умнее.
7
Действия, которые мы только что выполнили, основаны на алгоритме Евклида на-
хождения наибольшего общего делителя двух целых чисел. В данном случае исходные
числа 17 и 7 были взаимнопросты, их наибольший общий делитель — это 1, которую мы
и отыскали за два шага.
162 Приложение A. Определители, матрицы и линейные системы
Пример 103 Дан определитель четвертого порядка. При помощи свойств опре-
делителя мы можем его вычислить сведением к треугольному виду. Причем —
легко.
1111
1 −111
11−11
111−1
−I
−I
−I
=
1111
0 −200
00−20
000−2
=1· (−2) · (−2) · (−2) = −8 .
В этом примере нули ниже главной диагонали получаются за один шаг: вычита-
нием первой строки из всех остальных строк.
Пример 104 Наконец, рассмотрим еще один пример. Здесь мы докажем тожде-
ственное равенство нулю данного определителя, не вычисляя его.
sin
2
α sin
2
β sin
2
γ
111
cos
2
α cos
2
β cos
2
γ
+I
=
sin
2
α sin
2
β sin
2
γ
111
111
=0
Я надеюсь, основное тригонометрическое тождество помнят все. Других коммен-
тариев, кажется, не требуется.
Еще одним мощным инструментом вычисления определителей служат их
разложения по строкам и столбцам. Этот прием позволяет свести вычис-
ление определителя n-го порядка к вычислению n определителей (n − 1)-го
порядка. Прежде, чем сформулировать соответствующую теорему, дадим
два определения.
Определение 68 (дополнительные миноры) Дополнительным мино-
ром к элементу a
ij
матрицы A называется определитель M
ij
матричного
фрагмента, который получается из матрицы A вычеркиванием i-й строки
и j-го столбца.
Определение 69 (алгебраические дополнения) Алгебраическим до-
полнением A
ij
к элементу a
ij
называется дополнительный минор, взятый с
точностью до знака:
A
ij
= M
ij
· (−1)
i+j
.
Итак, каждый матричный элемент обладает дополнительным минором и
алгебраическим дополнением. Причем в том случае, когда сумма индексов
i+j является четным числом, алгебраическое дополнение в точности равно
дополнительному минору. Если же сумма индексов i + j нечетна, алгебра-
ическое дополнение отличается от дополнительного минора знаком.
Нетрудно убедиться,что знаки алгебраических дополнений к элементам мат-
рицы следуют в шахматном порядке: на первом-первом месте знак всегда
родной, а далее — нетрудно подсчитать.
Пример 105 Рассмотрим матрицу третьего порядка: A =
10−3
25 1
−12 4
.
Каждый из ее девяти элементов обладает собственным дополнительным минором
и собственным алгебраическим дополнением. Вычислим некоторые из них:
M
11
=
51
24
=18,A
11
=
51
24
(−1)
1+1
=18.
A.1. Определители 163
При вычислении дополнительного минора M
11
мы умозрительно вычеркнули в
исходной матрице первую строку и первый столбец, после чего вычислили остав-
шийся после вычеркивания определитель второго порядка. При вычислении ал-
гебраического дополнения A
11
мы учли его знак: домножили дополнительный ми-
нор на (−1)
1+1
. Как видим, в данном случае алгебраическое дополнение в точно-
сти совпадает с дополнительным минором. Но что произойдет на первом-втором
месте?
M
12
=
21
−14
=9,A
12
=
21
−14
(−1)
1+2
=9· (−1)
3
= −9.
В этом случае дополнительный минор и алгебраическое дополнение отличаются
знаком.
Теорема 86 (о разложении определителя) Пусть A ∈ Matr
n
—неко-
торая матрица. Ее определитель может быть вычислен по следующим фор-
мулам:
|A| = a
i1
A
i1
+ a
i2
A
i2
+ ···+ a
in
A
in
,
|A| = a
1j
A
1j
+ a
2j
A
2j
+ ···+ a
nj
A
nj
.
Первая из этих формул называется разложением определителя по i-й стро-
ке, а вторая — разложением определителя по j-му столбцу.
Определитель может быть разложен по любому столбцу и по любой строке.
Таким образом, опредилитель n-го порядка имеет ровно 2n разложений.
Пример 106 Вычислим следующий определитель третьего порядка разложени-
ем его по второй строке.
13−3
221
0 −13
=2·
3 −3
−13
· (−1) + 2 ·
1 −3
03
+1·
13
0 −1
· (−1) =
=2· (9 − 3) · (−1) + 2 · (3 −0) + 1 · (−1 − 0) · (−1) = −12 + 6 + 1 = −5.
Применяя разложение, мы фиксируем строку разложения (в данном случае —
вторую), после чего последовательно поступаем следующим образом.
Первый элемент второй строки, то есть 2, домножаем на его алгебраическое до-
полнение, то есть на минор
3 −3
−13
с учетом знака алгебраического дополне-
ния, а знак на этом месте — чужой (см. таблицу смены знаков).
Далее — то же самое проделываем со вторым и с третьим элементами второй
строки, после чего все складываем.
Пример 107 Вычислим следующий определитель разложением по первому столб-
цу.
203
141
3 −12
=2·
41
−12
+1·
03
−12
· (−1) + 3 ·
03
41
· =
=2· (8 + 1) + 1 ·(0 + 3) · (−1) + 3 · (0 − 12) = 18 − 3 − 36 = −21.
Здесь мы фиксировали первый столбец и с его элементами проделали то же, что
с элементами второй строки в предыдущем примере.
164 Приложение A. Определители, матрицы и линейные системы
Итак, мы рассмотрели три способа вычисления определителей: по опре-
делению, сведением к треуголному виду по методу Гаусса и разложением
по строке или столбцу. Наиболее трудоемким является первый из них, так
как именно вычисление определителя по определению требует наибольшего
количества арифметических действий. Наиболее алгоритмически упорядо-
чен, конечно же, метод Гаусса. Все компьютерные алгоритмы вычисления
определителей основаны именно на методе Гаусса (или его модификациях).
Что же касается метода разложения, то это наиболее быстрый способ для
ручного вычисления, хотя, конечно, он требует фантазии для того, что-
бы им воспользоваться — ведь разложение можно осуществлять по любой
строке и по любому столбцу, как выбрать наиболее выгодный ход?
Ответ следующий. Метод разложения дает колоссальную вычислительную
экономию в том случае, когда строка (или столбец) разложения содержат
единственный ненулевой элемент: ведь тогда вычисление определителя n-го
порядка сводится к вычислению определителя (n −1)-го порядка! Если же
такой строки (или столбца) в исходной матрице нет, то ее (или его) нужно
организовать.
Пример 108 Мы видим, что второй столбец определителя содержит единствен-
ный ненулевой элемент. Поэтому разложение этого определителя по второму столб-
цу содержит единственное ненулевое слагаемое:
−43−3
10 1
30 2
=3·
11
32
· (−1) = 3 · (2 − 3) · (−1) = 3.
Итак, если перед нами стоит задача вычисления определителя, то наиболее
целесообразно скомбинировать все известные нам методы для достижения
наибольшей экономичности в вычислении. А именно: следует предваритель-
но преобразовать определитель таким образом, чтобы в какой-нибудь его
строке (или в каком-нибудь столбце) остался единственный ненулевой эле-
мент, после чего устроить разложение по этой строке (или по этому столб-
цу).
Пример 109 В этом примере нетрудно заметить, что первая и третья строки
определителя очень похожи друг на друга (точнее, отличаются только первым
элементом). Мы можем воспользоваться этим для того, чтобы упростить вычис-
ления.
213
532
113
−III
=
100
532
113
=1·
32
13
=1· (9 − 2) = 7.
После вычитания третьей строки из первой в первой строке остался единственный
ненулевой элемент, и мы устраиваем разложение по первой строке.
A.2 Действия с матрицами
Как мы установили, множество квадратных матриц одного порядка n обра-
зует алгебру, которая называется полной матричной алгеброй и обозначает-
ся Matr
n
(см. раздел 2.1.2, стр. 21). Это означает, что с квадратными мат-
рицами одного порядка можно выполнять следующие действия: сложение,
A.2. Действия с матрицами 165
умножение на число и умножение
8
. Сложение матриц и скалярное кратное
являются тривиальными операциями (см. опр. 3, стр. 19 и опр. 4, стр. 19, а
также — соответствующие примеры). Мы не рассматриваем их в приложе-
нии, уделяя основное внимание матричному умножению (см. раздел A.2.1,
стр.165).
Кроме того, невырожденные матрицы допускают матричное обращение (мат-
ричный аналог операции деления на множестве чисел). Этой операции по-
священ отдельный раздел (см. раздел A.2.2, стр. 167).
A.2.1 Умножение матриц
Необходимые сведения о матричных действиях представлены в соответству-
ющем теоретическом разделе (см. раздел 2.1.1, стр. 18). Из соображений
удобства практического изучения материала мы продублируем здесь тео-
ретический минимум.
Определение 70 (произведение матриц) Пусть имеется матрица A ∈
Matr
m×p
и матрица B ∈ Matr
p×n
. Тогда их произведением AB (именно в
этом порядке, а не наоборот) называется матрица C ∈ Matr
m×n
, компонен-
ты которой вычислются по следующим формулам:
c
ij
= a
i1
b
1j
+ a
i2
b
2j
+ ···+ a
ip
b
pj
.
Другими словами — для того, чтобы вычислить к омпоненту произведения,
находящуюся на месте с номером ij,нужноi-ю строку первого множителя
умножить на j-й столбец второго множителя.
Пример 110 Возьмем две прямоугольные матрицы: A ∈ Matr
2×3
и B ∈ Matr
3×2
:
A =
10−3
21−1
,B=
20
1 −2
02
.
Согласно определению (см. опр. 70, стр. 165), для этой пары матриц призведение
AB определено (так как число столбцов в первой матрице равно числу строк во
второй). В резултате такого действия получится матрица порядка 2 × 2, и для ее
записи нам нужно вычислить четыре ее компоненты:
1.1) 1 · 2+0·1+(−3) · 0=2
здесь мы вычисляем первую-первую компоненту результирующей матри-
цы, для этого — умножаем первую строку первого множителя на первый
столбец второго множителя;
1.2) 1 · 0+0·(−2) + (−3) · 2=−6
далее мы вычисляем первую-вторую компоненту результирующей матрицы,
для этого — умножаем первую строку первого множителя на второй столбец
второго множителя;
2.1) 2 · 2+1·1+(−1) · 0=5
далее мы вычисляем вторую-первую компоненту результирующей матри-
цы, для этого — умножаем вторую строку первого множителя на первый
столбец второго множителя,
8
Напомним, кроме того, что матричное умножение ассоциативно (см. теор. 3, стр. 23)
и некоммутативно (см. теор. 2, стр. 22)
166 Приложение A. Определители, матрицы и линейные системы
2.2) 2 · 0+1· (−2) + (−1) · 2=−4
и, наконец, вычисляем вторую-вторую компоненту результирующей матри-
цы, для этого — умножаем вторую строку первого множителя на второй
столбец второго множителя.
Остается записать полученный результат в виде матирицы 2 × 2:
10−3
21−1
20
1 −2
02
=
2 −6
5 −4
.
Пример 111 Любые две квадратные матрицы одного порядка можно перемно-
жать, но нельзя менять местами множители. Продемонстрируем это. Пусть
A =
1 −3
2 −1
,B=
20
12
.
В результате умножения получится матрица порядка 2 × 2. Ее компоненты мы
вычисляем так же, как в предыдущем примере:
1.1) 1 · 2+(−3) · 1=−11.2) 1 · 0+(−3) · 2=−6
2.1) 2 · 2+(−1) · 1=3 2.2) 2 ·0+(−1) · 2=−2
Остается записать полученный результат в виде матирицы 2 × 2:
AB =
1 −3
2 −1
20
12
=
−1 −6
3 −2
.
Теперь поменяем множители местами, то есть — вычислим призведение BA.
B =
20
12
,A=
1 −3
2 −1
.
В результате получится матрица 2 × 2 со следующими компонентами:
1.1) 2 · 1+0· 2=2 1.2) 2 ·(−3) + 0 · (−1) = −6
2.1) 1 · 1+2· 2=5 2.2) 1 ·(−3) + 2 · (−1) = −5
и произведение двух матриц, вычисленное в обратном порядке выглядит следую-
щим образом:
BA =
20
12
1 −3
2 −1
=
2 −6
5 −5
.
Мы видим, что результат умножения существенно зависит от порядка множите-
лей (это иллюстрирует свойство некоммутативности матричного умножения).
Пример 112 Пусть требуется возвести матрицу
11
01
в n-ю степень. Ра-
зумеется, мы не в состоянии этого сделать. Однако мы можем сделать то, что
в наших силах: возвести матрицу в квадрат, затем — в куб и т. д. Для начала
вычислим квадрат матрицы:
11
01
2
=
11
01
11
01
=
12
01
.
Далее мы можем найти третью степень матрицы:
11
01
3
=
11
01
2
11
01
=
12
01
11
01
=
13
01
.
A.2. Действия с матрицами 167
Если еще не понятно, что получится в общем случае, можно вычислить и четвер-
тую степень:
11
01
4
=
11
01
3
11
01
=
13
01
11
01
=
14
01
.
Теперь понятно? Правильно:
11
01
n
=
1 n
01
.
Пример 113 Покажем, пользуясь прямым вычислением как инструментом до-
казательства, что имеет место следующее матричное тождество
9
:
cos α −sin α
sin α cos α
2
=
cos 2α −sin 2α
sin 2α cos 2α
.
Действительно, применим (опустив подробные выкладки) определение матрично-
го умножения (см. опр. 70, стр. 165) и получим:
cos α −sin α
sin α cos α
cos α −sin α
sin α cos α
=
=
cos
2
α −sin
2
α −2sinα cos α
2sinα cos α cos
2
α −sin
2
α
=
=
cos 2α −sin 2α
sin 2α cos 2α
.
A.2.2 Обратные матрицы
Матричным аналогом операции деления служит матричное обращение (см.
раздел 2.1.3, стр. 24). Для решения практических задач на эту тему мы
продублируем здесь необходимый теоретический минимум. Кроме того, мы
рассмотрим еще один метод матричного обращения — метод Гаусса (см.
теор. 88, стр. 169), который в ряде случаев оказывается эффективнее.
Определение 71 (обратная матрица) Пусть A — некоторая матрица из
полной матричной алгебры Matr
n
. Если существует матрица X ∈ Matr
n
такая, что
AX = E, XA= E,
то матрица X называется обратной к матрице A и обозначается A
−1
. Мат-
рица, обладающая обратной, называется обратимой.
Квадратная матрица является обратимой тогда и только тогда, когда она
невырождена, то есть — когда ее определитель отличен от нуля (см. крите-
рий обратимости, теор. 8, стр. 27), и для ее вычисления можно воспользо-
ваться формулой, которую дает следующая теорема.
9
Забегая вперед, заметим, что матрицы из этого примера — не что иное, как матрицы
операторов поворота на углы α и 2α, соответственно, а возведение матрицы в квадрат
— не что иное, как последовательное двукратное применение оператора поворота (см.
раздел 2.3.5, стр. 59). В свете этого замечания тождество выглядит абсолютно естествен-
ным.
168 Приложение A. Определители, матрицы и линейные системы
Теорема 87 (о вычислении обратной матрицы) Пусть матрица A об-
ратима. Тогда матрица A
−1
может быть вычислена по следующей формуле:
A
−1
=
1
|A|
(
˜
A)
T
,
где
˜
A — матрица, составленная из алгебраических дополнений к элементам
матрицы A,аT означает транспонирование.
Пример 114 Вычислим матрицу, обратную к данной A =
13−2
031
3 −22
.
Для того, чтобы воспользоваться теоремой о вычислении обратной матрицы при
помощи алгебраических дополнений (см. теор. 87, стр. 168), нам необходимо знать:
1. определитель исходной матрицы,
2. девять алгебраических дополнений к каждому из девяти элементов исход-
ной матрицы.
Вычислим определитель:
|A| =
13−2
031
3 −22
−I ∗3
=
13−2
031
0 −11 8
=
=
31
−11 8
=24+11=35.
Здесь мы предварительно преобразовали определитель так же, как мы делали
это выше (см. раздел A.1.2, стр. 159), а затем разложили его по первому столбцу.
Далее — перейдем к вычислению алгебраических дополнений (см. опр. 69, стр. 162
и соответствующие примеры).
A
11
=
31
−22
=8,A
12
= −
01
32
=3,A
13
=
03
3 −2
= −9 ,
A
21
= −
3 −2
−22
= −2 ,A
22
=
1 −2
32
=8,A
23
= −
13
3 −2
=11,
A
31
=
3 −2
31
=9,A
32
= −
1 −2
01
= −1 ,A
33
=
13
03
=3.
Следовательно, матрица
˜
A нам известна, и после транспонирования (то есть —
после операции, меняющей ролями ее строки и столбцы, или, если угодно, после
ее симметричного отражения относительно главной диагонали) она приобретает
следующий вид:
˜
A =
83−9
−2811
9 −13
, (
˜
A)
T
=
8 −29
38−1
−911 3
.
Теперь, наконец, мы можем записать, пользуясь заявленной выше формулой (см.
теор. 87, стр. 168), выражение для обратной матрицы:
A
−1
=
1
35
8 −29
38−1
−911 3
=
8/35 −2/35 9/35
3/35 8/35 −1/35
−9/35 11/35 3/35
.
A.2. Действия с матрицами 169
Чтобы убедиться, что все вычисления выполнены верно, необходимо сделать про-
верку. Она состоит в применении определения (см. опр. 71, стр. 167): исходная
матрица после умножения ее на обратную должна дать единичную.
8/35 −2/35 9/35
3/35 8/35 −1/35
−9/35 11/35 3/35
13−2
031
3 −22
=
100
010
001
.
Подсчет осуществляется, как мы это делали выше, умножая матрицы (см. раз-
дел A.2.1, стр. 165). Выкладки мы опускаем.
Итак, понятно, что чем выше порядок матрицы, тем более сложной с вы-
числительной точки зрения становится задача нахождения обратной к ней.
Проще всего вычислять обратные матрицы в случае 2 × 2. Единственное,
что здесь нужно учитывать, это то, что дополнительные миноры в таких
матрицах имеют порядок 1, то есть — это просто матричные компоненты,
числа.
Пример 115 Вычислим матрицу, обратную к A =
13
2 −1
. Нам нужно знать
(см. теор. 87, стр. 168): определитель матрицы и четыре алгебраических допол-
нения к каждому матричному месту. Вычислим определитель:
|A| =
13
2 −1
= −1 −6=−7
— это очень легко. Несложно вычислить и алгебраические дополнения:
A
11
= −1 A
12
=2(−1) = −2
A
21
=3(−1) = −3 A
22
=1
Составим матрицу
˜
A и транспонированную к ней:
˜
A =
−1 −2
−31
, (
˜
A)
T
=
−1 −3
−21
.
Следовательно (см. теор. 87, стр. 168), A
−1
= −
1
7
−1 −3
−21
=
1/73/7
2/7 −1/7
.
Выполним проверку:
1/73/7
2/7 −1/7
13
2 −1
=
10
01
. Задача решена
верно.
Теорема 88 (метод Гаусса вычисления обратных матриц) Для вы-
числения матрицы, обратной к матрице A, можно выполнить следующие
действия. Составить расширенную матрицу (A |E),гдеE — единичная мат-
рица того же порядка, что и A. Затем по цепочке элементарных преобра-
зований строк преобразовать левую часть расширенной матрицы к единич-
ному виду:
(A |E) ∼ (E |A
−1
) ,
после этого в правой части получится матрица, обратная к исходной мат-
рице A.
170 Приложение A. Определители, матрицы и линейные системы
Пример 116 Вычислим матрицу, обратную к A =
41
31
. Применим метод
Гаусса (см. теор. 88, стр. 169).
41
31
10
01
−II
∼
10
31
1 −1
01
−I ∗3
∼
10
01
1 −1
−34
.
Таким образом, A
−1
=
1 −1
−34
. Выполним проверку:
41
31
1 −1
−34
=
10
01
.
В данном примере цепочка преобразований оказалась очень короткой — всего два
звена. Метод Гаусса дал существенную вычислительную экономию (для сравне-
ния вспомните, сколько мы мучались в примере 115).
Пример 117 Рассмотрим более сложную ситуацию: A =
111
011
001
. Если
применить теорему о вычислении обратной матрицы при помощи алгебраических
дополнений к ее элементам (см. теор. 87, стр. 168), то нам придется вычислить
девять алгебраических дополнений к каждому матричному месту, что затрудни-
тельно. С другой стороны, метод Гаусса (см. теор. 88, стр. 169) очень быстро
приведет к результату:
111
011
001
100
010
001
−II
−III
∼
100
010
001
1 −10
01−1
001
,
точнее говоря, за один шаг. Ошибиться здесь было решительно негде, поэтому
проверку мы выполнять не будем.
Казалось бы, метод Гаусса гораздо удобнее, однако приведенные выше при-
меры скрывают одну замаскированную тонкость: определители матриц, ко-
торые мы обращали по методу Гаусса, были равны ±1 (это были так назы-
ваемые унимодулярные матрицы). Если же матрица имеет произвольный
(отличный от нуля и плюс-минус единицы) определитель, то метод Гаусса
потребует проводить вычисления с дробными числами, и выгода от таких
действий окажется весьма сомнительной.
Итак: в случае, когда исходная матрица имеет специальный (то есть удоб-
ный для элементарных преобразований) вид, разумнее применять метод
Гаусса для ее обращения. Если же матрица произвольна — метод матрич-
ного обращения, основанный на вычислении алгебраических дополнений,
предпочтительнее, так как он алгоритмически разделяет арифметические
действия на блоки, и вероятность допустить выичислительную ошибку сни-
жается.
A.2.3 Матричные уравнения
Матричные действия — умножение и обращение — часто используются для
нахождения различных неизвестных величин: векторов или матриц. Напри-
мер, решая задачу о нахождении координатного представления вектора в