Беклемишев - Дополнительные главы линейной алгебры (947281), страница 30

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 30)

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

Применение этой схемы состоит в выполнении ряда последовательных шагов, в результате которых исходная матрица А = Аио преобразуется в матрицы Ап>, Аг", ... 22)ы начнем с простейшего случая, в котором отличны от нуля все главные миноры матрицы А, т. е. миноры вида а„... ам 1 бе1 ° ° ° ° ~, /г= 1, ..., н. ам ... а221 Отличие от нуля главных миноров позволяет не включать в число производимых элементарных операций перестановки строк н столбцов. Первый шаг схемы единственного деления преобразует матрицу Л в матрицу А~", у которой первый столбец равен первому столбцу единичной матрицы порядка п. По предпологкению минор первого ггорядка, равный элементу ам, отличен от нуля, и, разделив первую строку А на агг (единственное деление), превратим А в матрицу А', у которой а'„= 1 и ал, — — а„для всех Iг ~ 2. Затем при и = 2,..., и в матрице А' вычтем из и-й строки первую строку, умноженную на а„.

В результате мы получим матрицу нужного вида ~~ о 222 ... а'„'„' Заметим, что при описанных преобразованиях мы прибавляем строку к нижележащим строкам, и потому главные миноры матрицы не могут обратиться в нуль. Итак, главные миноры матрицы Апг отличны от нуля. Отсюда следует, что отличен от нуля элемент а,",' этой матрицы, так как ее главныи минор второго порядка равен а22, Второй шаг схемы единственного деления состоит в применении преобразований первого шага к той подматрице матрицы АП1, которая расположена в строках и столбцах с номерами 2, ..., н. Это переведет матрицу Агп в матрицу ~!2 '" 1л, Л,2, )о ! " 22'„'~ у которой первыедва столбца имеют на главной диагонали единицы, а ниже диагонали — нули. При проделанных преобразованиях снова вышележащая строка прибавлялась к нижележащим, и потому главные миноры матрицы Агм пе равны нулю.

В частности, отличен от нуля элемент а3, равный главному минору третьего порядка матрицы Аггй ГЛ, Ць ВВЕДЕНИЕ В ЧИСЛЕННЫЕ МЕТОДЫ На третьем шагу преобразуется подматрица матрицы А(е>, расположенная в строках и столбцах с номерами 3, ..., и. И так далее. На й-м шагу преобразования первого шага применяются к подматрице матрицы А ~~ '), расположенной в последних и — й + 1 строках н столбцах. В полученной матрице Апп отличен от нуля элемент а<4+~,,+ „так как его обращение в нуль означало бы, что удалось обратить в нуль главный минор порядка й + 1 матрицы А за счет элементарных преобразований со строками этого минора.

После (и — 1)-го шага мы получим матрицу Лм '1, у которой на главной диагонали все элементы равны 1, кроме о~"„- и, а элемен- ты, расположенные ниже главной диагонали, равны нулю. Матрицы, у которых элементы, стоящие ниже диагонали, равны нулю, называются верхнили треугольными матрицами (ср. стр. 33). Разделив последнюю строкуматрнцы Агл н на а~л„— '>, мы получим верхнюю треугольную матрицу Аьо = У с единицами на главной диагонали.

Описанный выше процесс превращения матрицы Л элементар- ными преобразованиями в верхнюю треугольную матрицу У носит название прямого исключения или метода Гаусса в узком смысле слова. Если все элементарные операции со строками проделывались пад расширенной матрнцей (т. е. матрицей А, дополненной столб- цом свободных членов), то в результате будет получена система ли- нейных уравнений с треугольной матрицей и =й, эквивалентная ') системе (1).

Она легко может быть решена. Действи- тельно, последнее уравнение системы имеет вид х„= Ь'. Кроме того, каково бы ни было й, если определены х„, ..., хы то из (й+ 1)-го уравнения л хь,=ое 1 — ~ и~ цхр (2) к-е Применяя эту формулу последовательно для й = и, ..., 2, мы найдем все компоненты решения, не прибегая к делению.

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

Затем, используя (и — 1)-ю строку, обращаем в нуль элементы 11 См. К., Вредложеяые 2 $4 гл. У. Ф з. пгямыя мятоды гвшвния систем (п — 1)-го столбца, расположенные выше диагонали, и т. д. Этот процесс преобразования называется обратным ходом метода Гаусса. Если все операции со строками проделывались над расширенной матрицей, то в результате прямого и обратного хода метода Гаусса система заменится на эквивалентную систему с единичной матрицей, т. е. будет решена.

Отметим, что обратный ход метода Гаусса требует большего числа арифметических операций, чем решение системы с треугольной матрицей по формулам (2). Ниже, в и. 3, мы вернемся к схеме единственного деления и опишем, как освободиться от ограничительного предположения об отличииот нуля всех главных миноров матрицы. Сейчас же мы вкратце рассмотрим так называемый метод оптимального исключения как пример того, насколько могут измениться характеристики алгоритма прн изменении порядка выполнения операций.

Подробнее он описан в книге Воеводина 171. Начинается процесс оптимального исключения, как и схема единственного деления, с того, что все элементы первой строки делятся на ам.(Мы по-прежнему предполагаем все главные миноры матрицы отличными от нуля.) Новая первая строка умножается на а„ и вычитается из второй, Однако после этого не преобразуют третью строку, а с помощью второй строки обращают в нуль первый элемент второго столбца и только тогда переходят к третьей строке. В третьей строке с помощью двух первых обращают в нуль два первых элемента, а с помощью третьей строки обращают в нуль первые два элемента третьего столбца. Вообще, пусть после й шагов первые й строк преобразованы так, что содержащиеся в них части первых Й столбцов совпадают со столбцами единичной матрицы порядка й.

На (й+1)-м шагу к (й+!)-й строке добавляются строки 1, ..., й с такими множителями, чтобы обратить в нуль ее первые й элементов. Далее (й+ 1)-я строка делится на ее (й + 1)-й элемент и после умножения на соответствующие элементы вычитается из вышележащих строк с тем, чтобы обратить в нуль первые й элементов (й+ 1)-го столбца. Таким образом, в методе оптимального исключения попеременно выполняются операции прямого и обратного хода метода Гаусса. Это позволяет не вводить в оперативное запоминающее устройство (й+1)-ю строку до тех пор, пока не преобразованы предыдущие строки. После преобразования й строк количество подлежащих запоминанию элементов в этих строках уменьшается на й" и становится равным пй — йз.

Максимальное значение этого выражения при четном а достигается при й = п/2 и равно и'/4. При нечетном и результат будет близким к этому. Итак, решение системы при помощи метода оптимального исключения требует примерно вчетверо меньшего объема оперативной памяти, чем применение схемы един~ ственного деления. 138 гл нь вввденив в чнслвнныв методы Отметим еще один возможный порядок выполнения элементарных операций, при котором все столбцы матрицы А последовательно превращаются в столбцы единичной матрицы.

Это — так называемый метод Жордана. Он не имеет никаких преимуществ перед схемой единственного деления. 2. А<1'-разложение. Изнестно, что выполнение какой-либо элементарной операции со строками матрицы А равносильно умножению А слева на некоторую невырожденную матрицу, а последовательное выполнение ряда таких операций — умножению на матрицу 5, равную произведениюсоответствующих матриц. Чтобы найти матрицу 5, достаточно проделать последовательно все элечентарные операции над единичной матрицей.

(Действительно, результатом будет матрица 5Е, т. е. 5.) Превращая матрицу А в верхнюю треугольную матрицу У, мы проделывали определенную последовательность элементарных операций. Легко видеть, что эта последовательность операций переведет Е в нижнюю треугольную матрицу 5. Действительно, кроме умножения строк на числа, употребляется толы<о прибавление строки к нижележащей строке.

При этом все элементы преобразуемой единичной матрицы, расположенные выше диагонали, останутся равными нулю. Итак, справедливо П р едл о же н и е 1. Для любой матрицы А с ненулевыми главными минорами найдется такал невырожденная нижняя треугольная матрица 5, что 5А есть верхняя треугольная матрица У с единицами на главной диагонали. Докажем далее П р е д л о ж е н и е 2. Матрица Е, обратная к нижней треугольной матрице 5 из предложения 1, сама является нижней треугольной и имеет вид 1~пи О ... О ...

Характеристики

Список файлов книги