3 Глава Параллельные вычисления при численном решении уравнений математической физики

LU разложение матриц

Рассмотрим систему Ax = f . В результате применения метода Гаус- са мы получили систему Ux = y, где U есть верхняя треугольная матрица с единицами на главной диагонали. Вектор y зависит толь- ко от вектора f и матрицы A. Рассмотрим соотношение между y и f . В случае n = 3 мы имеем


y_n
Понятно, что для произвольных n мы будем иметь

a
Таким образом, f=Ly,где L – нижняя треугольная матрица с элемент

которая может быть рассчитана с использованием формул базового
алгоритма (10)-(12). Так как

то получаем

Ax = f, Ux = y, Ly = f,

Ax = Ly = LUx.

Следовательно, мы имеем A = LU , где L есть нижняя треугольная матрица и U - верхняя треугольная матрица. Это представление LU разложения для матрицы A часто называется LU факторизацией матрицы A. Приведем пример для 3 × 3 матрицы

Предположим, что для системы Ax = f мы знаем матрицы L и U . Тогда мы сможем легко решить систему в два простых шага: первый - Ly = f дает решение для y, второй - Ux = y обеспечи- вает решение для x. Проблема состоит в получении матриц L и U . Матрица A имеет n² коэффициентов, тогда число коэффициентов в двух матрицах L и U определяется как n(n + 1), поэтому есть неко- торая недоопределенность. Это дает нам свободу выбора некоторых коэффициентов в L или U .
Укажем некоторые конкретные варианты:

•
Если метод исключения Гаусса косвенно выбирает l_ii = 1, то этот вариант называется Метод Дулитла.

•
Представление с условием u_ii = 1 известно как Метод Кроута.

•
Если A = A^T (т. е. A является симметричной матрицей) и A является также положительно-определенной матрицей (т. е. имеет положительные собственные значения), то мы можем выбрать u_ij = l_ji. Этот вариант называется Метод Холецкого. В этом случае будем иметь

A = LU, A^T = U^T L^T = LU, → L = U^T .
Заметим, что, строго говоря, LU разложение матрицы не все- гда возможно. Теорема утверждает, что если все главные миноры матрицы A не равны нулю, то A представляется как A = LU един- ственным образом. При этом диагональные элементы L отличны от нуля.
С другой стороны, все гауссовские преобразования могут быть записаны в матричной форме. Например, если n = 3, имеем

5.