Вычислительная математика и программирование - Боглаев Ю.П.
ISBN 5-06-00623-9
Скачать (прямая ссылка):
?1,1*1 +«1.2*2 + -+аипхп = Ь1,
аЧЬх2 + ...+а^яхп=ЬЧ), (8.2.2)
аУ,и2+- +«п!и»=^«1),
где элементы матрицы а\)\ 2<г',7<л, и вектора Ь\1), 2</ после первого шага получены по формулам
(И 1
«1.7 = «и----«ий1.я
й1, 1
1,1
2-й шаг. Исключение неизвестной х2 из всех уравнений системы (8.2.2), кроме 1-го и 2-го. Пусть а^2ф0. Тогда из второго уравнения выражаем х2
х2=^^(а^3х3+... Л-а^х^+Ь^ (8.2.3)
через остальные неизвестные и подставляем (8.2.3) в третье, четвертое, ..., л-е уравнения системы (8.2.2). После подстановки получаем преобразованную исходную систему
312 \
Л, '
«1,1*1 + - +«1.Л = *1,
а$\х 2 + - +а^„хл = Ь^\
а??зх3 +-+а%\хп = Ь<$),
(8.2.4)
«В* з +... + а(?Ххп = Ь{?\
где элементы матрицы а\2], 3^1,]^п, и вектора Ь\2), 3^/-<п. после второго шага получены по формулам
1
а(2)= (1) _ _________
и1 вй>2
1
«І.Ш.
ЪР^Ь.-^аПЬР.
«1.2
Продолжая этот процесс исключения при условии, что
«^з#0, ..., а("-2)„-1 ^0,
после (п— 1)-го шага исключения получим преобразованную исходную систему
«1.1*1 + - +«1,Л =Ьі,
а?)2*2 + - + «?»*» =ЬУ\
(8.2.5)
с верхней треугольной матрицей и
г
и=
а, ,Й
1, 1М1,2 .... 1, /I
«УЛ
о
ип,п
и преобразованным вектором правых частей
ь,
біг1»
В матричной записи система уравнений (8.2.5) примет вид
С/х = ?. (8.2.6)
Преобразование исходной системы линейных уравнений к системе (8.2.6) с треугольной матрицей С/—прямой ход исключения.
313
На этом этапе мы еще не вычислили ни одной компоненты вектора решения *, но эквивалентными преобразованиями привели систему к такой форме, для которой легко вычислить все компоненты решения *.
Пусть Ф0. Тогда осуществляем обратный ход: вы-
числяем компоненты вектора решения в обратном порядке. Из
(8.2.5) находим
ЬГ1}
(8-2'7)
*1=-— {Ь1-аипхп-...-аи2х2). > а1,1
Для примера решим систему уравнений *х—2*2 + 3*3 = 1,
2 *1 + 3*2+ *з = 2,
— х1— *2 + *3 = 3.
Первый шаг прямого хода исключения
* Хл — 2х2 + 3*з = 1,
7*2-7*3 = 0,
— 3*2+ 4*з = 4;
второй шаг
хх — 2*2 + 3*з = 1,
7*2 —7*з = 0, *з=4;
обратный ход:
*з = 4,
*2 = 4,
*!= —3.
Определим нижнюю треугольную матрицу Ь с единичной главной диагональю формулой
314 \
V.
Прямой подставкой можно проверить, что справедливо разложение исходной матрицы А в произведение:
А = Ьи. (8.2.8)
Представление матрицы А в виде (8.2.8) называется Ы1-разло-жением матрицы. Очевидно, что решение исходной системы уравнений эквивалентно решению двух систем с треугольными матрицами
1* = Ь, (8.2.9)
Ux=g. (8.2.10)
Таким образом, рассмотренный вариант метода исключения Гаусса—это определение вектора g решением (8.2.9) и затем определение вектора л: решением (8.2.10).
Справедливо следующее утверждение.
Теорема 8.4. Для существования Ы/-разложения матрицы А необходимо и достаточно, чтобы у матрицы А все главные миноры были отличны от нуля.
У произвольной невырожденной матрицы А главные миноры, т. е.
«1.1 а1,2 «1.1 * «1,я
«1,1 1 ’ а2,1 а2,2 ап, 1 «и, и
вообще говоря, могут обращаться в нуль. Например, матрица
невырожденная, а ее первый главный минор равен нулю.
Чтобы применить метод Гаусса к таким матрицам, или, что то же самое, получить ПУ-разложение, необходимо произвести перестановку строк (или столбцов) так, чтобы главные миноры стали отличными от нуля.
315
Теорема 8.5. Произвольная невырожденная матрица перестановкой строк (столбцов) может быть приведена к матрице с главными минорами, отличными от нуля.
Обычно перестановку строк (столбцов) не производят отдельно от процедуры исключения, а соединяют эти два процесса в один.
Если ?ltl=0, переставим строки матрицы А так, чтобы в левом верхнем углу оказался ненулевой элемент. В первом столбце такой элемент всегда найдется, иначе det,4 = 0. Если после первого шага получим 2 = 0, то выполним, как и выше, перестановку; во втором
столбце всегда найдется ненулевой элемент, иначе два первых столбца были бы линейно зависимы и с1еЫ = 0. Поместим строку с ненулевым элементом во втором столбце на место второй строки, тогда Продолжая з^от процесс исключения и перестановки строк (если элемент a%k1) = 0) до к=п, получим LU-разложение матрицы А с дополнительной матрицей Р-матрицей перестановок строк:
‘ . PA = LU. (8.2.11)
Матрица Р получается из единичной матрицы Е перестановкой тех же строк. Например, перестановке 2-й и 4-й строк матрицы соответствует
Р=
Заметим, что цатрица Р—это и есть та матрица перестановок, существование которой утверждается в теореме 8.5.
8.2.2. Вычисление определителя и обратной матрицы с помощью L (/-разложения. Напомним формулу для определителя произведения двух матриц:
det А = det L det U.
Заметим, что определитель треугольных матриц равен произведению диагональных элементов. Следовательно,
detL= 1, detU=a1'j
Отсюда значение определителя матрицы А вычисляется по формуле
detA = aul ? - 'ап,Йи?
Если матрица А представлена в форме (8.2.11) с перестановками, то
det Р det А = det L det U.
Но так как матрица Р получается перестановкой строк единичной матрицы Е, то
detР—{ ^ ПРИ четном числе ^ перестановок,
