Разложение Холецкого (метод квадратного корня).

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

. (2.12)

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

Элементы матрицы находятся непосредственно из уравнения (2.12) из которого согласно определению матричного умножения следует

. (2.13)

Заметим, что в скалярном произведении -ой строки матрицы на -й столбец матрицы суммирование в (2.13) ведется не по всем компонентам векторов, а только для их ненулевых значений. В силу этого из равенства (2.13) для

, (2.14))

В случае из равенства (2.13) следует

, . (2.15)

Для из равенства (2.13) имеем

, (2.16)

.

Формулы (2.14)-(2.16) дают явные рекуррентные выражения для элементов матрицы . Применимость описанного алгоритма помимо симметричности матрицы ограничена также требованием положительности величин , стоящих под знаком квадратного корня в формулах (1.14), (1.15). Данное требование всегда выполняется для положительно определенных матриц и матриц с диагональным преобладанием. В общем случае может быть использовано представление симметричной матрицы в виде A=LDL*, где D – диагональная матрица с элементами ±1 на главной диагонали.

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

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