![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
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)
Число называется числом обусловленности матрицы А. Системы уравнений и матрицы с большими числами
принято называть плохо обусловленными, а с малыми – хорошо обусловленными. При численном решении систем с плохо обусловленными матрицами возможно сильное накопление погрешностей. Справедливы следующие свойства чисел обусловленности:
а. ,
б. ,
где и
- соответственно наибольшее и наименьшее по модулю собственные значения матрицы А.
в. .
Дата публикования: 2015-01-10; Прочитано: 224 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!