ПРИЛОЖЕНИЕ 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). Как следствие, вычислительные затраты для рекуррентной  процедуры пропорционально .