Н.И. Яцкин - Линейная алгебра (Теоремы и алгоритмы) (1109879), страница 78
Текст из файла (страница 78)
В самом деле, если (квадратную) матрицу A умножить справа на элементарную матрицу Sj,i,λ , то над столбцами A будет произведено элементарное преобразование iстб + j стб · λ(внимание: именно так, а не наоборот, должны стоять индексы i и j).tОдновременно мы должны умножить A слева на Sj,i,λ= Si,j,λ , т.
е.произвести над строками элементарное преобразование iстр + j стр · λ.Итак, при переходе к конгруэнтной матрице всякое элементарноепреобразование над столбцами сопровождается точно таким жеэлементарным преобразованием над строками.Замечание 35.5. В терминах замечания 34.8 диагонализирующийбазис для с.б.ф.
можно назвать f -ортогональным. Подробнее о геометрической трактовке понятия диагонализируемости см. ниже,в § 40.§ 36. Диагонализация по Лагранжусимметрических билинейных(квадратичных) форм36.1. Алгоритм Лагранжа диагонализации с.б.ф. (кв.ф.).В данном пункте мы сформулируем и докажем теорему Лагранжао диагонализируемости произвольной с.б.ф. (кв.ф.), заданной над454Линейные, билинейные и квадратичные формыГл. 4полем, характеристика которого отлична от двух, причем будет даноалгоритмическое доказательство.До сих пор мы изучили не так много "великих" алгоритмов:— алгоритм Гаусса приведения матрицы к ступенчатому виду(и его модификацию — алгоритм Жордана — Гаусса);— алгоритм Евклида отыскания НОД в кольце целых чисел ив кольце многочленов;— алгоритм Жордана приведения квадратной матрицы к жордановой нормальной форме;— алгоритм Смита приведения к канонической диагональной форме полиномиальных матриц (и его применение к задаче о приведенииквадратной матрицы к ж.н.ф.).Теперь к этому перечню будет добавлен еще один знаменитый алгоритм, изобретенный выдающимся французским математиком Жозефом Луи Лагранжем (1736 — 1813), добившимся результатов первостепенной важности, наверное, во всех разделах математики, атакже в аналитической механике.
По своей идее этот алгоритм оченьпрост: он сводится к многократному выделению полного квадрата воднородном многочлене второй степени (от нескольких переменных).Замечание 36.1. В классической средней общеобразовательнойшколе навык выделения полного квадрата (в простейшем случаеквадратного трехчлена от одной переменной) считался важнейшими первоочередным для освоения. Сколько красивейших задач решалось этим элементарным приемом (без привлечения позднее введенных в программу — на весьма убогом уровне — производных)!К сожалению, и здесь современная ситуация оставляет желать лучшего. Поэтому и в курсе математического анализа, и в алгебре приходится предварять решение задач университетского уровня упражнениями из школьно-ученического минимума. (В пособии [A1 ] мывстречались с различными версиями процедуры выделения полногоквадрата, например, в пп.
43.4 и 50.3.)В данном парграфе будет применяться формула для квадратасуммы нескольких слагаемых:(c1 + c2 + ... + cn )2 = c21 + c22 + c23 + ... + c2n ++ 2(c1 c2 + c1 c3 + ... + c1 cn + c2 c3 + .... + c2 cn + c3 c4 + ... + cn−1 cn ),а под дополнением до полного квадрата будет подразумеваться следующая выкладка:§ 36Диагонализация квадратичных форм по Лагранжу455c21 + 2(c1 c2 + c1 c3 + ...
+ c1 cn ) = (c1 + c2 + c3 + ... + cn )2 −¡¢− c22 + c23 + ... + c2n + 2(c2 c3 + ... + c2 cn + c3 c4 + ... + cn−1 cn ) .Обратите внимание на то, что выражение, фигурирующее во второй строке этой выкладки, не содержит c1 .Теорема 36.1 (теорема Лагранжа). Над полем P характеристики, отличной от двух, для любой с.б.ф.
f ∈ L2s (V ) [для любой кв.ф.h ∈ K(V )] существует диагонализирующий базис, в котором форме f(форме h) отвечает матрица D = diag(µ1 , ... , µr , 0, ... , 0), где µi ∈ P[ µi 6= 0; i = 1, ... r; r = rank(f ) = rank(h) ].Доказательство представим в виде описания работы алгоритма,причем исходным объектом мы будем считать квадратичную формув координатной записи [см. формулу (35.10)]:th(x) = x A x =nXaii x2i + 2i=1Xaij xi xj ,(36.1)16i<j6nт.
е. фактически задача арифметизируется посредством фиксациинекоторого исходного базиса.Будем искать замену переменныхx = T u,(36.2)такую, что в новых координатах (u1 , u2 , ... , un ) форма (36.1) записывается в видеrXt(36.3)h(x) = u D u =µi u2i ,i=1где r = rank(h).Важная техническая деталь: замену координат придется производить многократно, так что "штрихов не напасешься"; поэтому новыекоординаты (в новом базисе) мы будем обозначать не штрихованиемстарых координат, а новыми буквами. В частности, вектор-столбец u, фигурирующий в (36.3), относится к тому же абстрактномувектору x ∈ V , к которому относился вектор-столбец x (но в другомбазисе).456Линейные, билинейные и квадратичные формыГл.
4Матрица T является матрицей перехода от исходного базиса кдиагонализирующему; она будет накапливаться постепенно, как произведение T = Q1 Q2 ... Qs , где каждый из сомножителей отвечает одному или нескольким (столбцовым) элементарным преобразованиям(см. замечание 35.4).А л г о р и т м 36. 1.Приведение симметрической билинейной(квадратичной) формы к диагональному видуметодом Лагранжа1. Если h = 0, то работать незачем, исходная матрица A = O ужеявляется диагональной (r = 0).2. Если h 6= 0, то возможны две ситуации:— либо форма (36.1) содержит хотя бы один член с квадратом(т.
е. в матрице A имеется хотя бы один ненулевой диагональныйэлемент aii ),— либо диагональ A является чисто нулевой, т. е. (36.1) не содержит квадратов; однако тогда отличен от нуля хотя бы один изкоффициентов aij (i < j).2.1. В первом случае, при выполнении условия a11 6= 0, мы сразупереходим к этапу 2.1.2. Если же a11 = 0, то необходим следующийпредварительный этап.2.1.1. Перенумеруем (а точнее — переименуем) переменные так,чтобы первый диагональный элемент стал отличен от нуля. Если,скажем, aii 6= 0, то производим замену координат, сводящуюся кперестановке базисных векторов:x1 = yi ; xi = y1 ; xk = yk (k 6= 1, i).(36.4)Формулы замены можно представить в матричном виде:x = Q1 y,(36.5)где Q1 = T1,i есть элементарная матрица типа I (см. формулу (14.3)в [A1 ]); она служит матрицей перехода от исходного базиса к новомубазису, отличающемуся от старого лишь тем, что первый и i-й базисные векторы переставлены.
(Можно добавить, что эта матрицаотносится к числу матриц перестановочного перехода; см. замечание 13.5.)§ 36Диагонализация квадратичных форм по Лагранжу457Предположим, что предварительная перестановка (если она понадобилась) уже произведена, т. е. будем далее считать, что изначально в формуле (36.1) коэффициент a11 6= 0. В такой ситуации можетбыть реализован так называемый2.1.2. П е р в ы й п р и е м Л а г р а н ж аВ формуле (36.1) выделим в отдельную группу все слагаемые, содержащие x1 , и вынесем из этой группы за скобку множитель a11 ;остальные слагаемые будут представлять квадратичную форму h1от переменных x2 , ..., xn (ее, если угодно, можно считать определенной на подпространстве размерности n − 1, которое задается в Vлинейным уравнением x1 = 0):h(x) = h(x1 , x2 , ...
, xn ) =¶µaa121nx2 + ... + 2x1 ·xn + h1 (x2 , ... , xn ).= a11 x21 + 2x1 ·a11a11(36.6)Теперь применим к выражению в большой скобке формулу выделения полного квадрата, приведенную выше, в замечании 36.1 [члены, не содержащие x1 , подробно не расписываем; это будет квадратичная форма h2 (x2 , ... , xn ), на следующем шаге она присоединяетсяк форме h1 (x2 , ...
, xn )]:h(x) =µ¶a12a1n= a11 (x1 +x2 + ... +xn )2 + h2 (x2 , ... , xn ) +h1 (x2 , ... , xn ) =a11a11a12a1n= a11 (x1 +x2 + ... +xn )2 + eh(x2 , ... , xn ), (36.7)a11a11где eh = a11 h2 + h1 .Произведем замену переменных по формуламy1 = y2 =y3 =···yn =x1+a12x2a11+a13x3a11+ ... +x2a1nxn ;a11;x3;...xn .(36.8)458Линейные, билинейные и квадратичные формыГл. 4Формулы (36.8) выражают новые переменные через старые. Длятого, чтобы увидеть матрицу перехода, надо выразить старые переменные через новые. В данном случае это сделать легко:a12a13a1nx1 = y1 −y2 −y2 − .
. . −yn ;aaa111111y2; x2 =(36.9)x=y;33...···xn =yn .В векторной записи формулы (36.9) приобретают вид:x = Q2 y,(36.10)где матрица перехода (показаны только ненулевые элементы)Q2 = 1−a12a11−a13a11...−11...a1n a11 (36.11)1является верхней унитреугольной (подслово "уни" означает, что диагональ заполнена единицами).Нетрудно убедиться в том (хотя здесь это не очень нужно и становится важным лишь в программной реализации алгоритма), чтоматрица (36.11) является произведением элементарных матриц типа II (см. формулу (14.4) в [A1 ]):Q2 = S1,2,λ2 · S1,3,λ3 · ... · S1,n,λn ,(36.12)где λj = −a1j /a11 (j = 2, ... , n).Описанная выше замена приводит кв.ф.
к виду:h(x) = µ1 y12 + eh(y2 , ... , yn ),где µ1 = a11 .(36.13)§ 36Диагонализация квадратичных форм по Лагранжу459(Вас не должно смущать то, что в левой части (36.13) фигурируетвектор x ∈ V, а в правой части — переменные y1 , y2 , ... , yn : они, каки старые переменные x1 , x2 , ... , xn , являются координатами для тогоже вектора x, но — в другом базисе.)Матрица A0 , отвечающая представлению (36.13), имеет блочнодиагональный вид:µ1 0 .
. . 00 0A =(36.14).e···A0Поскольку матрица, конгруэнтная симметрической, сама симметрична (см. замечание 34.3), то симметричным будет и юго-восточныйeблок A.Формулы (36.13) и (36.14) свидетельствуют о том, что (в первомслучае) реализован первый шаг к достижению диагонального вида.Теперь о первой переменной можно практически "забыть" и, возвратившись к этапу 2, работать с "остаточной" кв.ф. eh(y2 , ... , yn ) иe (Но все-таки забыть не совсем: заменяя новые переее матрицей A.менные y2 , ... , yn на "еще более новые" z2 , ... , zn , мы должны как бы"перерегистрировать" первую переменную: y1 = z1 .)2.2.
Во втором случае кв.ф. не готова к применению первогоприема Лагранжа, т. к. не содержит ни одного квадрата. Приходится их искусственным образом получать. Идея соответствующейзамены должна быть вам знакома, например, из аналитической геометрии: произведение переменных xy с помощью введения новыхпеременных u и v, которые связаны со старыми формулами перехода x = u − v и y = u + v, преобразуется в разность квадратов:xy = u2 − v 2 .Как и в первом случае, здесь могут представиться две возможности.2.2.1. Если отличен от нуля "ближайший к северо-западному углу" элемент a12 , то можно сразу переходить к этапу 2.2.2.
Еслиже a12 = 0, то требуется перенумерация (переименование) переменных. Будем перебирать построчно элементы A, расположенные выше главной диагонали, пока не обнаружим ненулевой.Если он будет обнаружен в первой строке, в позиции (1, j), гдеj = 3, ... , n, то достаточно одной перестановки столбцов, производимой правым умножением на матрицу Q3 = T2,j (ср. с действиями в460Линейные, билинейные и квадратичные формыГл. 4п. 2.2.1; напомним, что каждая операция над столбцами дублируетсяв точности таким же действием над строками).Если первым найденным ненулевым окажется элемент a2j из второй строки, то в качестве матрицы перестановочного перехода можно взять Q4 = T1,2 T2,j , что соответствует циклической замене переменныхx1 = yj ; x2 = y1 ; xj = y2 ; xk = yk (k 6= 1, 2, j).(36.15)Во всех остальных случаях в перестановке будут участвовать четыре столбца: два первых и столбцы с номерами i, j, где (i, j) — позиция первого обнаруженного ненулевого элемента (3 6 i < j 6 n).Матрицей перехода будет Q5 = T1,i T2,j ; замена переменных запишется в виде:x1 = yi ; x2 = yj ; xi = y1 ; xj = y2 ; xk = yk (k 6= 1, 2, i, j).
(36.16)Предположим, что описанные в данном пункте предварительныеперестановки уже произведены, т. е. будем считать, что в формуле(36.1) изначально коэффициент a12 6= 0.В такой ситуации может быть реализован так называемый2.2.2. В т о р о й п р и е м Л а г р а н ж аВ "бесквадратной" квадратичной формеh(x) = 2Xaij xi xj(36.17)16i<j6nвыделим члены, содержащие x1 или x2 :¡h(x) = 2 a12 x1 x2 + a13 x1 x3 + ... + a1n x1 xn +(36.18)¢+ a23 x2 x3 + ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
