Численные методы

т.е.
-нижняя
треугольная
матрица, имеющая
обратную.
Из (18), учитывая
равенство
,
получим
(19)
Отсюда и из (16) видно, что
![]()
где обозначено
.
Поскольку
Р-матрица
перестановок
и L-нижняя
треугольная
матрица, свойство
(17) доказано. Оно
означает, что
метод Гаусса
с выбором главного
элемента по
столбцу эквивалентен
обычному методу
Гаусса, примененному
к матрице РА,
т.е. к системе,
полученной
из исходной
системы перестановкой
некоторых
уравнений.
Общий вывод. Результат, полученный ранее для очень частного примера, справедлив и в случае общей системы уравнений (1).
А именно, метод Гаусса с выбором главного элемента по столбцу можно записать в виде
(20)
где
-
элементарные
матрицы перестановок
такие, что
и
-элементарные
нижние треугольные
матрицы.
Отсюда, используя соотношения перестановочности, аналогичные (19), можно показать, что метод Гаусса с выбором главного элемента эквивалентен обычному методу Гаусса, примененному к системе
PAx=Pf, (21)
где Р - некоторая матрица перестановок.
Теоретическое обоснование метода Гаусса с выбором главного элемента содержится в следующей теореме.
ТЕОРЕМА
1. Если
то
существует
матрица перестано-
вок Р такая, что матрица РА имеет отличные от нуля угловые ми-
норы.
Доказательство в п.4.
СЛЕДСТВИЕ.
Если
то
существует
матрица престана-
вок Р такая, что справедливо разложение
РА=LU, (22)
где L- нижняя треугольная матрица с отличными от нуля диагональными элементами и U- верхняя треугольная матрица с единичной главной диагональю. В этом случае для решения системы (1) можно применять метод Гаусса с выбором главного элемента.
4. Доказательство теоремы 1. Докажем теорему индукцией по числу m -порядку матрицы А.
Пусть m=2, т.е.

Если
то утверждение
теоремы выполняется
при Р=Е,
где Е
- единичная
матрица второго
порядка. Если
,
то
,
т.к.
При
этом у матрицы

все угловые миноры отличны от нуля.
Пусть утверждение теоремы верно для любых квадратных матриц порядка m-1. Покажем, что оно верно и .для матриц порядка m. Разобьем матрицу А порядка m на блоки

где


![]()
Достаточно
рассмотреть
два случая :
и
.
В первом случае
по предположению
индукции существует
матрица перестановок
порядка
m-1
такая,
что
имеет
отличные от
нуля угловые
миноры. Тогда
для матрицы
перестановок

имеем

причем
.
Тем самым все
угловые миноры
матрицы РА
отличны
от нуля.
Рассмотрим
второй случай,
когда
. Т.к.
, найдется хотя
бы один отличный
от нуля минор
порядка m-1
матрицы
А,
полученный
вычеркиванием
последнего
столбца и какой-либо
строки. Пусть,
например,

где
.
Переставляя
в матрице А
строки
с номерами l
и m,
получим
матрицу
,
у
которой угловой
минор порядка
m-1 имеет
вид

и отличается от (23) только перестановкой строк. Следовательно, этот минор не равен нулю и мы приходим к рассмотренному выше случаю.
Теорема доказана.
ВЫЧИСЛЕНИЕ ОПРЕДЕЛИТЕЛЯ МЕТОДОМ ГАУССА С ВЫБОРОМ ГЛАВНОГО ЭЛЕМЕНТА.
Одновременно с решением системы линейных алгебраических уравнений
можно вычислить определитель матрицы А.
Пусть в процессе исключения найдено распожение
![]()
т.е. построены матрицы L и U . Тогда
![]()
и, таким образом, произведение диагональных елементов матрицы L (ведущих, главных елементов метода исключения) равно определителю матрицы РА. Поскольку матрицы РА и А отличаются только перестановкой строк, определитель матрицы РА может отличаться от определителей матрицы А только знаком.
А
именно,

Таким образом, для вычисления определителя необходимо знать, сколько перестановок было осуществлено в процессе сключения.
Если матрица А выроджена, то при использовании метод Гаусса с выбором главного элемента по столбцу на некотором шаге исключения К все элементы которого столбца, находящиеся ниже главной диагонали и на ней, окажутся равными нулю.При этом дальнейшее исключение становится невозможным и программа должна выдать информацию о том, что определитель матрицы равен нулю.
ОБРАЩЕНИЕ МАТРИЦ.
Нахождение матрицы, обратной матрице А , еквивалентно решению матричного уравнения
(1)
где Е - единичная матрица, X - искомая квадратная матрица.
Уравнение
(1) можно записать
в виде системы
уравнений
(2)
где
![]()
Можно заметить, что система (2) распадается на m независимых систем уравнений с одной и той же матрицей А , но с различными правыми частями. Эти системы имеют
вид ( фиксируем j ) :
(3)
где
у вектора - столбца
равна единице
j-та
компонента
и равны нулю
остальные
компоненты.
Например, для матрицы второго порядка система (2) распадается на две независимые системы:

Для решения систем (3) используется метод Гаусса ( обычный или с выбором главного элемента).
Рассмотрим применение метода Гаусса без выбора главного элемента. Поскольку все системы (3) имеют одну и ту же матрицу А , достаточно один раз совершить прямой ход метода Гаусса, т.е. получить разложение A=LU и запомнить матрицы L i U .
Обратный
ход осуществляется
путем решения
систем уравнений

с треугольными матрицами L и U.
При осуществлении обратного хода можно сократить число действий, принимая во внимание специальный вид правых частей системы (4).
Запишем подробнее первые j-1 уравнений системы (4):

Учитывая
невырожденность
матрицы L
( т.е.
отсюда получаем
![]()
При
этом оставшиеся
уравнения
системы (4) имеют
вид

Отсюда
последовательно
находятся
неизвестные
по формулам:
Можно
показать, что
общее число
действий умножения
и деления,
необходимое
для обращения
матрицы указанным
способом, порядка
.
Тем самым обращение
матрицы требует
не намного
больше времени,
чем решение
системы уравнений.
ІТЕРАЦІЙНІ МЕТОДИ РОЗВ’ЯЗАННЯ СИСТЕМ ЛІНІЙНИХ
АЛГЕБРАЇЧНИХ РІВНЯНЬ.
Розглядається система лінійних алгебраїчних рівнянь
(1)
де
- квадратна
матриця вимірності
![]()
-
вектор - стовпець
правих частин
системи;
- вектор - стовпець
невідомих.
Ідея найпростіших ітераційних методів розв’язання системи (1) полягає у наступному. За допомогою еквівалентних перетво-рень система (1) зводиться до системи вигляду
(2)
де
-квадратна
матріця
-відомий
вектор.
А
потім задається
деяке початкове
наближення
(наприклад,
у якості
береться вектор
, або деякий
розв’язок
системи (1), який
одержується
іншим методом
з деякою похибкою).
Інші наближення
послі-довно
знаходяться
за рекурентною
формулою
(3)
доки
на деякому
кроці не буде
досягнута
задана точність
![]()
обчислення
значення невідомого
вектору
.
Виникає
питання, за
яких умов на
послідовність![]()
збігається
(у певному розумінні)
до точного
розв’язку
.
Не
зупиняючись
на подробицях
(дивись спецкурс
‘Додат-кові
розділи чисельного
аналізу’),
дамо деякі
достатні умови,
за яких

або

або

Швидкість збіжності оцінюється нерівністю

де
-
відстань між
векторами
та
,
що може бути
заданою:
коли
виконується
умова (4);
коли виконується
умова (5);
коли
виконується
умова (6).
Задаючи
потрібну точність
можна з рівності

одержати
необхідну
кількість
ітерацій
,
щоб досягти
задане
.
Наведені умови є достатніми для збіжності методу ітерацій, але аж ніяк не необхідними. Необхідні і достатні умови збіжності методу ітерацій дає