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

Поскольку матрица В положительно определена, ее можно, и притом единственным образом, представить в виде

где - вещественная верхняя треугольная матрица с положительными диагональными элементами. Такая факторизация матрицы В называется разложением Холецкого. Ее применение к регрессии (под названием метода квадратного корня) стало популярным, по-видимому, благодаря работе Dwyer (1945). Некоторые авторы предпочитают использовать нижнюю треугольную матрицу. При этом матрица В записывается в виде где

Приравнивая соответственные элементы правой и левой частей (11.5), мы находим, что матрицу можно вычислять строка за строкой, используя выражения

и для

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

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

так что из (3.9) имеем

Если вместо матрицы X работать с расширенной матрицей ( то одновременное можно получить также вектор (см. упр. 4 в конце главы).

Матрицу, обратную к В, можно получить, решая уравнений где -единичный вектор, у которого равны нулю все элементы, кроме равного 1. Решение, соответствующее будет столбцом матрицы В то же время, поскольку верхняя треугольная матрица, найти обратную к ней матрицу (также являющуюся верхней треугольной) не составляет труда. При этом

Элементы матрицы вычисляются для по формулам

и

т. е. это равно произведению столбцов матрицы Поскольку матрица симметрична, достаточно найти только элементы, составляющие ее верхнюю треугольную часть. Как указывают Martin и др. (1965), после того как вычислен элемент элемент больше уже не требуется. Этот факт может быть полезен для сокращения объема занимаемой памяти.

Обратную к В матрицу можно найти и непосредственно из матрицы решая уравнение

относительно столбцов матрицы начиная с последнего ее столбца [Fox, Hayes (1951), Plackett (1960, с. 4)]; см. упр. 5 в конце главы. Комментируя этот метод, Golub (1969, с. 378) утверждает, что число операций, требующихся для его реализации, оказывается приблизительно тем же, что и для предшествующего метода, использующего

Другую факторизацию матрицы В предложили Martin и др. (1965); она не требует большего числа умножения и позволяет при этом избежать вычисления квадратных корней в (11.6) и (11.7). Пусть

где верхняя треугольная матрица с единичными диагональными элементами. Тогда

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

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