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