Систем линейных алгебраических уравнений

1. Метод Гаусса.

Система (1) в развернутой форме имеет вид

(2)

Предполагая, что исключим из уравнений начиная с второго. Получим систему уравнений с матрицей

(3)

Допустим, что . Тогда можно исключить и получить систему уравнений с матрицей

Исключая таким же способом неизвестные , приходим к системе уравнений вида

(4)

Матрица этой системы содержит нули всюду ниже главной диагонали. Матрицы такого вида называют верхними треугольными. Нижней треугольной называется матрица, у которой равны нулю все элементы, расположенные выше главной диагонали. Получение системы (4) составляет прямой ход метода Гаусса. Обратный ход заключается в нахождении неизвестных из системы (4). Трудоемкость метода порядка действий. Основным ограничением метода является предположение, что все элементы , на которые приходится делить, не равны 0.

2. Треугольное разложение матрицы.

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

, где . Отсюда

, и вообще

. (5)

Соотношения (5) можно записать в матричном виде ,

где - нижняя треугольная матрица.

Напомним, что основное условие применимости метода Гаусса состоит в том, что все . Поэтому на диагонали матрицы стоят ненулевые элементы. Таким образом, из (4), (5) получаем равенство

(6)

Теперь мы можем трактовать метод Гаусса следующим образом. Вначале проводится разложение матрицы в произведение двух треугольных, а затем последовательно решаются две системы

и .

Заметим, что в методе Гаусса разложение матрицы и решение системы (5) проводятся одновременно.

Обозначим через угловой минор порядка матрицы , т.е.

.

Т е о р е м а (теорема об - разложении). Пусть все угловые миноры матрицы отличны от нуля. Тогда матрицу можно представить единственным образом в виде произведения

, (7)

где - нижняя треугольная матрица с ненулевыми диагональными элементами и - верхняя треугольная матрица с единичной диагональю.

Д о к а з а т е л ь с т в о (см. [ 1 ]). Проведем доказательство методом математической индукции. Рассмотрим случай n = 2. Будем искать разложение матрицы

в виде

,

где - неизвестные. Для их нахождения имеем систему

которая имеет единственное решение

, , ,

.

Пусть утверждение теоремы справедливо при ; докажем, что оно справедливо и для матриц порядка . Представим матрицу порядка в виде

, где

, ,

.

Согласно предположению индукции , где

- нижняя и верхняя треугольные матрицы с указанными свойствами. Будем искать разложение матрицы в виде

, (8)

где - неизвестные пока векторы,

, .

Перемножая матрицы в правой части уравнения (8), приходим к системе уравнений

,

, (9)

.

Откуда

.

Таким образом, - разложение матрицы порядка существует.

Из разложения (8) следует, что

. Поэтому .

Предположим, что матрицу можно разложить двумя способами:

.

Тогда

. (10)

Матрица в левой части уравнения (10) является верхней треугольной, а в правой части – нижней треугольной (см. упражнение). Такое равенство возможно только в случае, если матрицы диагональные. Поэтому

.

Следовательно . Теорема доказана.

3. Ленточные матрицы. Метод прогонки.

Определение. Матрица называется ленточной с полушириной если при и существует при

.

Нас будут интересовать трехдиагональные матрицы т. е. .

Можно показать (см. упражнение), что если матрица ленточная с полушириной , то матрицы и в - разложении также ленточные с полушириной .

Будем говорить, что матрица имеет диагональное преобладание, если

.

Для матриц с диагональным преобладанием справедливо утверждение, что все главные миноры отличны от нуля и система уравнений (1) имеет единственное решение (см. упражнение).

Рассмотрим систему линейных уравнений с трехдиагональной матрицей и диагональным преобладанием.

(11)

........

(12)

........

(13)

К решению таких систем сводится довольно много задач математической физики. Будем решать эту систему методом прогонки. Идея метода прогонки основана на предположении, что неизвестные связаны соотношением

(14)

В пользу такого предположения говорит тот факт, что в - разложении для трехдиагональных матриц, матрица ленточная с полушириной , т.е. на обратном ходе метода Гаусса приходится решать систему

(15)

На прямом ходе прогонки находятся коэффициенты а на обратном неизвестные .

Из уравнения (11)

.

Следовательно

.

Подставляя в уравнение (12)

,

получаем

,

откуда

, т. е.

. (16)

Уравнение (13) используется для нахождения , чтобы начать обратный ход прогонки (14).

,

. (17)

Учитывая диагональное преобладание можно показать, что

. (18)

Заметим, что . Пусть при некотором , тогда

.

Неравенство (18) делает прогонку устойчивой, т. е. если найдено с ошибкой, то при вычислении по формуле (14), эта ошибка нарастать не будет.

4. Метод квадратного корня.

Этот метод применяется для решения системы уравнений (1) с симметричной матрицей . Мы рассмотрим частный случай, когда матрица системы (1) является симметричной и положительно определенной.

Матрица разлагается в произведение

, (19)

где - верхняя треугольная матрица. Решение системы (1) сводится к последовательному решению двух систем

, . (20)

Учитывая структуру матрицы , получаем

. (21)

Откуда

. (22)

При имеем , поэтому

. (23)

5. Обусловленность систем линейных алгебраических уравнений.

Будем считать, что правая часть и решение задачи (1) принадлежат n-мерному линейному нормированному пространству L. Если в пространстве векторов введена норма , то согласованная с ней матричная норма задается формулой

. (24)

Наиболее употребительные нормы

,

,

.

Согласованные с ними матричные нормы задаются соотношениями:

, (25)

, (26)

, (27)

где - собственные значения матрицы .

Легко видеть, что векторные нормы удовлетворяют неравенствам:

.

Наряду с системой (1) рассмотрим ” возмущенную систему”

, (28)

которая отличается от (1) правой частью. Выясним, как сильно может измениться решение в результате изменения правой части.

Введем обозначения

.

Из (1) и (28) получаем уравнение для погрешности

,

откуда

и, следовательно

. (29)

Для получения оценки относительной погрешности учтем, что

. (30)

Перемножая (29) и (30), приходим к требуемой оценке

, (31)

где

. (32)

Число называется числом обусловленности матрицы А. Системы уравнений и матрицы с большими числами принято называть плохо обусловленными, а с малыми – хорошо обусловленными. При численном решении систем с плохо обусловленными матрицами возможно сильное накопление погрешностей. Справедливы следующие свойства чисел обусловленности:

а. ,

б. ,

где и - соответственно наибольшее и наименьшее по модулю собственные значения матрицы А.

в. .