§ 5.8. Метод Холецкого (метод квадратных корней)

1. Описание метода.

Пусть требуется решить систему линейных алгебраических уравнений

с симметричной положительно определенной матрицей А. Линейные системы такого типа часто встречаются в приложениях (например, в задачах оптимизации, при решении уравнений математической физики и др.). Для их решения весьма часто применяется метод Холецкого (другое название — метод квадратных корней).

В основе метода лежит алгоритм построения специального LU-разложения матрицы А, в результате чего она приводится к виду

В разложении (5.64) нижняя треугольная матрица

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

Если разложение (5.64) получено, то решение системы (5.63) сводится к последовательному решению двух систем с треугольными матрицами:

Для решения систем (5.66) требуется выполнение примерно арифметических операций.

Найдем элементы матрицы Для этого вычислим элементы матрицы и приравняем их соответствующим элементам матрицы А. В результате получим систему уравнений

Решая систему (5.67), последовательно находим

Заметим, что для вычисления диагональных элементов используется операция извлечения квадратного корня. Поэтому метод Холецкого

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

2. Достоинства метода.

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

Как нетрудно подсчитать, число операций, выполняемых в ходе вычисления разложения (5.64) по формулам (5.68), равно примерно Учитывая, что для решения систем (5.66) требуется примерно арифметических операций, убеждаемся, что при больших метод Холецкого требует вдвое меньше вычислительных затрат по сравнению с методом Гаусса.

Учет симметричности матрицы А позволяет экономно использовать память ЭВМ при записи исходных данных задачи и результатов вычислений. Действительно, для задания матрицы А достаточно ввести в память ЭВМ только элементы расположенные на главной диагонали и под ней. В формулах (5.68) каждый такой элемент используется лишь однажды для получения и далее в вычислениях не участвует. Поэтому в процессе вычислений найденные элементы могут последовательно замещать элементы

В результате нижняя треугольная матрица может быть расположена в той области памяти, где первоначально хранилась нижняя треугольная часть матрицы А. Применение для решения системы (5.63) метода Гаусса потребовало бы использования примерно вдвое большего объема памяти.

Безусловным достоинством метода Холецкого является также его гарантированная устойчивость.

Пример 5.16. Используя метод Холецкого, найдем решение системы уравнений с симметричной положительно определенной матрицей:

По формулам (5.68) последовательно находим

Следовательно, матрица такова:

Система имеет вид

Решая ее, получаем Далее из системы которая имеет вид

находим решение