6.7.3. Решение системы линейных уравнений с использованием результатов lu-разложения ее матрицы.

Если LU-разложение найдено и det(U)0, то решение исходной системы уравнений (6.16) сводится к последовательному решению двух систем уравнений с треугольными матрицами коэффициентов:

LY = B ; (6.22.1)

UX = Y. (6.22.2)

Сложность решения систем уравнений с треугольными матрицами равна сложности обратного хода метода Гаусса, т.е. О(n²). В системе (6.22.1) исключение неизвестных производится сверху вниз, в системе (6.22.2) - снизу вверх.

Пример 3. Решить с помощью LU - разложения систему уравнений четвертого порядка АХ =B , в которой матрица А совпадает с матрицей примера 2, а векторB^Т = (-14; 44; 142; -76).

Решение. Матрицы L и U берем из примера 2. Уравнение (6.22.1) имеет вид:

Его решение: y₁ = -14; y₂ = 44 +5y₁ = 44-70 = -26; y₃ = 142+9y₁ = 142-126 = 16;

y₄ = -76-3y₁-(-17/8) y₃ = -76+42+34 = 0.

Уравнение (6.22.2) имеет вид:

Его решение: x₄=0; х₃ = (16 - 53х₄)/(-8) = -2; х₂ = (-26 - 9х₄- 5х₃)/8 =

(-26 +10)/8 = -2; х₁ = (-14 - 5х₄ + 9х₃ - 4х₂)/8 = (-14 -18 +8)/3 = -8.

Искомое решение: (х₁,х₂,х₃,x₄) = (-8;-2;-2;0).

LU-разложение рекомендуется применять в том случае, когда систему вида АХ =В необходимо решать многократно при постоянной матрице А и переменных свободных векторах В. При этом по известным один раз найденным матрицам L и U решение системы (6.22.1)-(6.22.2) требует выполнения О(n²) арифметических операций.

При программной реализации метода и последующего хранения матриц L и U применяют их компактное совместное представление в одной матрице порядка n (матрица L хранится без единичной диагонали):

Рассмотрим особенности LU-разложения. При его выполнении возможны ситуации, когда ведущий диагональный элемент u_kk матрицы U окажется равным нулю либо будет близок к нулю.

В первом случае возможны 3 ситуации.

1. Равен нулю первый диагональный элемент: u₁₁= а₁₁ = 0. В этом случае достаточно в матрице системы поменять порядок столбцов. Например, в матрице из примера 1 после перемены мест столбцов 1 и 2 для измененной матрицы А₁ получим:

2. Равен нулю средний диагональный элемент: u_kk = 0, при 2 ≤ k ≤ n-1. Это свидетельствует о том, что матрица А вырожденная и у нее нет LU-разложения.

3. Равен нулю последний диагональный элемент: u_nn = 0. При этом матрица А вырожденная, но у нее есть LU-разложение, в котором det(U)= 0.

Если диагональный элемент u_kk матрицы U близок к нулю, то в случае 1 ≤ k ≤ n-1 при делении на него могут быть получены большие погрешности в коэффициентах матрицы L и в дальнейшем решении системы. Метод LU-разложения не предусматривает выбор главного элемента (который мог бы предотвратить появление таких элементов на главной диагонали), поскольку перемена местами столбцов с номерами j₁ и j₂ эквивалентна умножению слева матрицы системы уравнений на вспомогательную матрицу вида:

Данная матрица не является нижней треугольной с единичной диагональю, поэтому ее включение в общее произведение С также нарушит ее нижний треугольный вид и единичную диагональ.

Оптимальный с точки зрения уменьшения погрешностей решения порядок неизвестных в системе задает вектор их порядкаР, получаемый после выполнения прямого хода метода Гаусса. Поэтому для того, чтобы максимально уменьшить величину погрешностей в получаемом решении, можно вначале найти верхнюю треугольную матрицу U по методу Гаусса и заодно оптимальный вектор порядка неизвестныхР, а затем, изменив порядок переменных в А, выполнить часть LU-разложения по формулам (6.18.k.1)-(6.18.k.2) относительно коэффициентов матрицы L. При этом число операций увеличивается примерно в 1,5 раза, но обеспечивается максимально возможная точность получаемых решений.

Вопросы для проверки знаний.

1. Что называют LU-разложением квадратных матриц ?

2. Применяется ли в LU-разложении матриц выбор главных элементов ?

3. При выполнении какого необходимого и достаточного условия (критерия) на главные диагональные элементы верхней треугольной матрицы существует LU-разложение произвольных квадратных матриц ?

4. Как формулируется критерий существования LU-разложение для невырожденных матриц ?

5. Какова сложность алгоритма LU-разложения ?

6. Как LU-разложение используется при решении системы линейных уравнений ?

7. В чем заключается компактное совместное представление матриц L и U в LU-разложении ?

8. В каких случаях отсутствие LU-разложения однозначно означает отсутствие решения системы линейных уравнений ?

Практическое задание.

1. Решить с использованием LU-разложения систему линейных уравнений: