1Анализ алгоритмов методов

В этом разделе будут рассмотрены следующие численные методы нахождения определителей: метод LU разложения, метод Гаусса, метод понижения порядка разложением по элементам строки.

1.1 Метод lu-разложения

LU-разложение – это представление матрицы в виде двух: нижней треугольной (L-матрица) и верхней треугольной (U-матрица).

(4)

Условия существования такого разложения даются следующей теоремой.

Если все главные миноры квадратной матрицы А отличны от нуля, то данную матрицу можно разложить на нижнюю треугольную и верхнюю треугольную матрицы, причем это разложение единственное. Заметим также, что U матрица на своей главной диагонали имеет одни единицы.

Формулы, по которым рассчитываются элементы этих матриц, представлены ниже.

(5)

(6)

где n – порядок исходной матрицы;

l_ij – элемент матрицы L;

u_ij – элемент матрицы U.

Тогда определитель исходной матрицы равен произведению определителей матриц L и U. Напомним, что определитель треугольной матрицы равен произведению всех элементов, лежащих на главной диагонали. Так как определитель U матрицы всегда равен единице, то достаточно найти определитель матрицы L. В этом и заключается этот метод.

Выделим основной алгоритм.

1 Следует поэлементно перебирать исходную матрицу и запоминать индексы элемента. Если , то заполнить эту же позицию матрицы L по формуле (5), в противном случае заполнить нулем.

2 Если , то заполнить эту же позицию матрицы U по формуле (6), в противном случае заполнить нулем, или, если это элемент главной диагонали, единицей.

3 Продолжать пункты 1 и 2 пока не закончатся элементы исходной матрицы.

4 Найти определитель матрицы L, перемножив ее диагональные элементы.

Так как результат всегда предсказуем, то данный алгоритм легко запрограммировать. Программная реализация алгоритма в среде Mathcad состоит из одного модуля user_lu_expansion(A). Данный модуль возвращает вектор из матриц L и U. Перемножение элементов главной диагонали матрицы L производится в данной реализации условно «вручную».

Осталось проверить исходные матрицы на разложимость. Напомним, что минор матрицы А – это определитель квадратной матрицы порядка n, элементы которого стоят в матрице А на пересечении одинакового числа строк и столбцов, начиная с первой строки и первого столбца. Главным минором называется всякий выделенный минор, у которого номера отмеченных строк совпадают с номерами отмеченных столбцов.

Так очевидно, что в матрицах (1) и (2) не существует нулевых главных миноров. В матрице же (3) видно, что первый главный минор второго порядка нулевой, т.е. матрица в таком виде неразложима. Дальнейший анализ показывает, что главные миноры более высоких порядков ненулевые.

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

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

(7)

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

Результаты данного метода следует смотреть в следующей главе.