В.А. Ильин, Г.Д. Ким - Линейная алгебра и аналитическая геометрия (1113055), страница 4
Текст из файла (страница 4)
Элементарные преобразования мат иц а,„м /ась, соответственно (т.е. выполним элементарные преобразования строк третьего типа). После выполнения пе ного шага матрица А переходит в матрицу Р агд а,ь,+ О ... О аз 1с,.1.1 ... а2п О ' " 'О' 'О' а...+ " а- в которой н срв ад строка является первой строкой строяшейся верхней ступенчатой матрицы. Если при этом все строки, начинил со второй, стали нулевыми, то весь процесс заканчивается, так как матрица уже приведена к верхней ступенчатой форме.
Если же в этих строках есть хотя бы один ненулевой элемент, т.е. если матрица 02 Ьс+1 ... а2п А1= ........ ~О, а 1+1 ... ап) то переходим ко второму шагу. Второй шаг. Второй шаг аналогичен первому. Он состоит в при- менении к матрице А, процедуры описанного выше первого шага. При этом можно считать, что выполняются элементарные преобра- зования строк всей матрицы А, так как нулевые элементы этих строк, р асположенные в первых Ь1 столбцах, прн элементарных преобразова- ниях строк не изменяются.
В результате второго шага уже и вторая строка матрицы А станет вспорой строкой строящейся верхней сту- пенчатой матрицы. Переход к следуюшему шагу аналогичен уже известному переходу :от первого шага ко второму. Повторяя описанные преобразования , на следуюших шагах, самое большее через й = ццп(гп, и) шагов мы .получим требуемый результат. Отметим, что ведущим элементом з-го шага является первый ненулевой элемент з-й строки, т.е.
а;ь,. Описанный здесь процесс будем называть основным процессом , приведения матрицы к ступенчатой форме. ° Земечеппз е осноеполу процессу. 1. Основной процесс с незвамолификавией монет быть использован и для црнведевия матрзшы к чителъной и элемента вые в ерхвей трацеяиевидвой форме. Йля этого нуиво привлечь есце и э р преобразования столбцов: церестааить в стуценчатои матриде стол цы б так, что- бы йкй столбец оказался на с-м месте. Итак, цроизвольная невулеяае матрица элементарными цреобразоваввямн строк и цереставовкамв столбцов монет быть цриведеиа к верхней трацеиневидвой форме.
2. Квадратная матрица с цомозцью основного процесса црвводнтс» к треуголь- ной форме. 3. Если в основном цроцессе поменять ролями строки в столбцы, то матрипа А приведется к виивей стуцевчатой (трацецвеавлной) форме. 4. В чных вычисленные ао избеиание больших чисел целесообразно в основ- вомцроце се нсцо ть элемент раме цг бр вястр р ру ст вто го типа: сокрашать все элементы на общин мнозсвтель. 5. Во иэбехсание дробвых чисел в ручных аьгчвслевиях удобно такие в каче- стве ведушего элемента выбирать элемент, равный 1. Если такого элемента вет, то, как цравило, его моино получить, используя элементарные цреобразоаасшя строк и церестановки столбнов.
б. Идеа основано процесса используются во мнопсх компьютерных алгорвт- мах вычислитедьвойалгебрм. Выбор ведупвко элемента здесь цредставлзет собой особую цроблеьсу, так как от этого заавсат точность вычнсзмиан. сследовавв 20 Глава 1 Матрицы 21 34. Определители 34. Определители з, оно, 1 О . 1 1вз м 1, О 1 1 . О й»з = , идей, 1з.1) этшз проблемы выходит зв рамка двиной квиги; отмезим лишь, что ведущий элемент ве делиев быть "маленьким". Имевво этим ощмделяется многообразие влгорвтмов, реализующих освовиой пропесс, с рвзлвчвымв стрвтегвями выбора велушего элемеитв.
Матрицы элементарных преобразований. Элементарные преобразования матрицы просты и удобны в матричных исследованиях. Однако словесное описание выполняемых преобразований весьма утомительно как само по себе, так и для его восприятия. Этого можно избежать, если ввести некоторые матрицы специального вида. Магприцвми элемепгпариых преобразований называются квадратные матрицы О;, РЧ, Глу вида 1 з в которых все диагональные элементы, кроме указанных, равны 1, а все внедиагональные элементы, хроме указанных, равны О.
Теорема 3.2. Умножение матприцы А на магприцы элеменгпариых преобразований Ру, О;, Г,; справа равносильно элементарным преобразованиям столбцов магприцы А первого, втпорого и третьего зпипов соответственно, а умножение слева на м атриц»д — аналогичным элементарн»лм преобразованиям стпрок. ж Показательство. Докажем одно из сформулированных утведений: умножение матрицы А на Ь»з справа равносильно прибавлению к з-му столбцу матрицы А ее 1'-го столбца, умноженного на 13. Действительно, пусть 11, 1»,..., 1„— столбцы матрицы 1 б.
Тогда, как следует из (2.3), (2.2) и (2.1), А1„1ш(А11 ... А1„)=(1»=е» брийэ»з)ш =(а1 ... а» 1 А11 а»+1 ... а»] = (А1; = а;+ »за11 = — (а» ... а; 1 (а»+ 1зэа1) ах »1 .. ао) ° Итак, с помощью матриц элементарных преобразованрй все элементарные преобразования матрицы могут быть записаны весьма лаконично; Р;, А, О»А, Я А, АРЧ, АО;, АЦ„. В свете доказанной теоремы можно по-иному сформулировать теорему 3.1: для любой ненулевой матрицы А существуют магприцы элементпариых преобразований 1.1,..., Л» и»ание, что произведение Л»...Х1 А имеет верхнюю ступенчатую форму. Перестановки.
Упорядоченная совокупность чисел сз1, аэ, ..., а„, в которой 1) бц Е (1, 2,..., и), з = 1, и; 2) о» ф сз при 1 ф 1, называется перестановкой из чисел 1, 2,..., и. Перестановка 1, 2,..., и называется натуральной. 3 а и е х з х з е. Аналогично рассматриваются перестввовки из в лроизвольвых символов: достаточно перенумеровать зти символы и иметь дело с их номерами 1,э,...,в~.
Преобразование перестановки, при котором два ее числа сн и ау с номерами з ф 1меняются местами, называется гпранспоэицией. Говорят, что два числа бн и оу в перестановке сх1, сзз,..., ао образуют инверсию 1'беспорядок), если большее из них предшествует меньшему, т.е. если еп ) о прн з < у, и порядок — в противном случае, т.е. если о» < о при з < 11 Перестановка называется четной, если общее число инверсий в ней четно, и нечетной — в противном слу- ЧаЕ. Общсс ЧИСЛО ИНВЕрСИй В ПЕрЕСтаНОВКЕ О1, аг,..., Оо ОбсэиаЧаетсЯ символами о(оз, оз,..., Оо) или о(о).
Теорема 4.1. Число всевозможных перестановок из п чисел равно и!. Доказательство. Переберем все перестановки нз и чисел. В качестве о1 можно взять любое из этих чисел. Это дает и возможностей. В каждой из них а1 уже выбрано и в качестве аг можно выбрать любое из и — 1 оставшихся чисел. Это означает, что число различных способов выбрать о1 и ог равно п1п — 1). Продолжая эти рассуждения, полУчим, что число Различных способов выбРать а1, аг,..., Оо Равно п(п — 1) ....2 1=п!. ° Т е оре ма 4.2. Каждае трапспоэиция меняет вещность перес»поповки. Доказательство.
1. Пусть в перестановке О»,оз,..., сзп меняются местами два соседних числа бн и о»+1, т.е. ' В $8 будет двво общее определение перестввовки и-го порядка. з 4. Определители 22 Глава й Матрицы ...„ао а;+!,... ! — > ...,а!+!, а;,... (здесь многоточия заменяют числа, которые не затрагивались при транспозицин), Очевидно, что в обеих перестановках числа, оставшиеся на местах, составляют одни н те же инверсии друг с другом и с ао а;+!. Если числа а, и а;+! раньше составляли инверсию, то в новой перестановке она пропадает; если же они не составляли инверсию, то теперь появится одна новая инверсия. Таким образом, общее число инверсий в новой перестановке отличается от старой на единицу, т.е.
четногть при такой транспозиции меняется. 2. Пусть теперь между переставляемыми числами 'а; и ау расположено к чисел, т.е. ..., а„а;+т,..., а;+ь, а ... т- ..., а, а;+т,..., а! ьь, а,... Новую перестановку можно получить из старой, последовательно меняя местами соседние числа: а; поменять местами (к+ 1) раз с соседними числами а!+!,а!+э,...,а!+в,а), а затем а! поменять местами й раз с числами ат+ю..., а;ьз, а;ь!.
При этом четность перестановки изменится 2й + 1 раз. Следовательно, и при такой транспозиции четность перестановки меняется. ° Теорема 4.3. Все и! перестановок из и чисел могут бытпь упорядочены тпвк, чтпобы квждвя иоследующвя оптличвлвсь от предыдущей нв одну трвнспозииию, причем нвчинвтпь зто упорядочение можно с любой перестановки.
Показательство. Проведем индукцию по и. Лля и = 2 утверждение теоремы легко проверить: (1, 2), (2, 1) и (2, 1), (1, 2). Пусть утверждение теоремы верно для и — 1 чисел. Покажем его для и чисел. Пусть первая перестановка имеет вид ат, аг,..., а, . а) Сначала упорядочим все перестановки, начинающиеся с а!. Таких перестановок (и — 1)!, и по индуктивному предположению они могут быть упорядочены нужным образом, начиная с перестановки а!, аз,..., а„, так как это сводится к упорядочению перестановок из и — 1 чисел, начиная с аз, аз,, а„. б) Палее в последней перестановке иэ этого списка сделаем одну транспозицию, поменяв местами числа а! и аз.
И снова упорядочим все перестановки, начинающиеся с аг, и т.д. ° Сл е д с т в и е 1. При и > 2 число четных перестановок ровно числу нечетпных. Лействительно, после упорядочения в списке всех перестановок четные и нечетные перестановки будут чередоваться, а так как и! четко прн и > 2, то количества четных и нечетных перестановок совпадают и равны и!/2. След с и! в и е 2. Отп квзкдой перествновки из п чисел можно перейти к любой другой перествновке из этих же чисел при помощи конечного число трвнспозииий. Теорема 4.4.
Если ат,аз,..., а„- перестановки из первых и нвтурвльных чисел с числом инверсий в, то после преобрвзоввнил ее в нвтпурвльную перествновку индексные номера 1, 2,..., и образую!и новую перестпвновку с тем же числом инверсии в. Показательство. Рассмотрим в перестановке (4.1) ат,аз, ° еп ° '' тг)~'' ° 1а» любые ее два числа а; и а;. Числа а; и а образуют либо инверсию (а; > а, т < /), либо порядок (ат < а, т < у). После преобразования перестановки (4.1) в натуральную числа а; и а; будут располагаться следующим образом: 1, 2,..., а,,..., а;,, .., а„в случае инверсии, причем в обоих случаях т < ~.
Это означает, что числа а; и а в перестановке (4.1) и их индексы т и ~' в перестановке индексных номеров одновременно образуют либо инверсию, либо порядок. Следовательно, обе этн перестановки имеют одинаковое число инверсий в. ° Построение определителя и-го порядка. Пусть А = (Об)— квадратная матрица и-го порядка. Рассмотрим произведение элементов этой матрицы, взятых по одному из каждой строки и каждого столбца; (4.2) Отатпзат .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
