ПРИЛОЖЕНИЕ D. ФАКТОРИЗАЦИЯ МАТРИЦЫ (ПРИ РЕШЕНИИ СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ)
Рассмотрим решение системы линейных
уравнений
(D.1)
где
-
положительно определённая
симметричная матрица,
-
-мерный вектор коэффициентов. которых
надо определить, a
- произвольный
-мерный вектор. Уравнение (D.1) можно эффективно разрешить путём
факторизации
в
виде произведения
(D.2)
где
- нижняя треугольная матрица с
элементами
,
a
- диагональная матрица с
диагональными элементами
. Диагональные элементы
образуют ряд
единиц, то есть
.
Тогда имеем
(D.3)
,
где
- элементы
. Следовательно, элементы
и
определяются (D.3) согласно правилам
,
, (D.4)
(D.4) определяет
и
через элементы
Решение (D. 1) осуществляется в два этапа. При подстановке (D.2) в (D.1) имеем
Пусть
(D.5)
Тогда
(D.6)
Сначала решим (D.6)
для
. С
учётом треугольной формы
имеем
(D.7)
Получив
, на втором этапе определяем
, Имеем
Начинаем с
, (D.8)
а оставшиеся коэффициенты
получаются
рекуррентно:
(D.9)
Число умножений и делений, требуемых
для формирования факторизации,
пропорционально
. Число умножений и делений, требуемых для вычисления
когда
определено, пропорционально
. Если
- матрица
Теплица, алгоритм Левинсона-Дурбина эффективно используется для нахождения
решения (D.1), так как число умножений и
делении пропорционально
, С другой стороны, непосредственно методом наименьших
квадратов
и
не вычисляются, как в (D.3), но они поддаются рекуррентному обновлению. Обновление
выполняется
операциями (умножений и делений).
Затем решение для вектора
производится шагами (D.5)-(D.9).
Как следствие, вычислительные затраты для рекуррентной
процедуры пропорционально
.