Решение СЛАУ с помощью LU-разложения матриц

Если матрица A исходной системы (1.1) разложена в произведение треугольных L и U, то, значит, вместо (1.2) можно записать эквивалентное уравнение

LUx=b.

Введя вектор вспомогательных переменных y, последнее выражение можно переписать в виде системы

Таким образом, решение данной системы с квадратной матрицей коэффициентов свелось к последовательному решению двух систем с треугольными матрицами коэффициентов.

Очевидно, все y _i могут быть найдены из системы Ly = b при i =1, 2,…, N по формуле (прямой ход)

(1.6)

Значения неизвестных x _i находятся из системы Ux = y в обратном порядке, т.е. при i = N, N –1,…, 1, по формуле (обратный ход)

(1.7)

Итак, решение СЛАУ посредством LU-факторизации сводится к организации вычислений по четырем формулам: совокупности формул (1.4)–(1.5) для получения матрицы L + U – I (1.3) ненулевых и неединичных элементов матриц для L и U, формулы (1.6) для получения вектора свободных членов треугольной системы Ux = y и формулы (1.7), генерирующей решение исходной системы (1.1).

Обратим внимание на тот факт, что выполнение расчетов по формулам (1.4)–(1.6) можно интерпретировать как преобразование системы (1.1) к треугольной системе Ux = y. С системой, являющейся результатом прямого хода метода Гаусса, последняя имеет не только структурное сходство, но полностью совпадает с ней (совпадение первых уравнений очевидно, коэффициенты при неизвестных и свободные члены вторых уравнений легко выражаются одинаково через исходные данные; можно и дальше проводить сравнение этих систем таким путем, однако обычно идентичность этих систем показывают проще на основе, представления прямого хода метода Гаусса как последовательности умножений матрицы A слева на матрицы очень простой структуры такой, что в итоге получается матрица U, а последовательность обратных преобразований дает L. Так что решение линейных систем с помощью LU-разложения – это просто другая схема реализации метода Гаусса. В отличие от рассмотренной в ранее так называемой схемы единственного деления эту называют компактной схемой Гаусса или схемой Холецкого (чаще схемой Холецкого называют основанный на той же идее способ решения симметричных линейных систем).

Пример использования метода решения СЛАУ, основанного на LU-разложения в системе TALGAT

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

- действительный случай: SET "lu_solve" LU_SOLVE_r LU_FACT_r real_m right_r;

- комплексный случай: SET "lu_solve" LU_SOLVE LU_FACT complex_m right_c;

с частичным упорядочивание по столбцам:

- действительный случай: SET "lu_solve" PLU_r r real_m right_r;

- комплексный случай: SET "lu_solve" PLU complex_m right_c.

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

Дата добавления: 2014-12-27