Из выражений (3 57) - (3 59) следует, что в результате г-го шага процесса КГШ преобразуется только г-й вектор-столбец Ьг, причем в два этапа вначале он ортогонализируется по отношению к (/-1) предыдущим столбцам {q}, а затем нормируется После реализации К шагов получим

Q = Впш (D,C/,D, UiDk) = Впш" = BnuR, (3 60)

где Q, R - унитарная и верхняя треугольная матрицы

Заметим, что часто для ортогонализации используют левое умножение на нижние треугольные матрицы (т е ортогонали-

зируются строки Впш) в этом случае вместо (3 60) получим

Q. = ЬВпш. (3 61)

где L, Qi - нижняя треугольная и с ортогональными строками матрицы

Соотношение (3 61) называется LQ-разложением матрицы Рассмотрим связь КГШ-ортогонализации с матрицами проектирования. Из соотношений (3 57) - (3 59) следует, что процедура строится по следующей схеме

(2) p, = (/, P„)b„ q- I / b Рч = ЪЧ2,

(3) Рз = {Ik - Pgi - Pqi) Ьз, Чз = ur p p\ ъ \ >

\ vk ql q2) "3 I

Р«з = ЯэЯз~, (3 62)

{r)r = и к - Z Pqi) br (Ik - S Pq) b,

V /==1 / Ч j = l /

. Pqr - 4r47,

r=l, 2,.. ,K,

где Pqr - проектор на одномерное подпространство, заданное вектором Яг

Из приведенных соотношений видно, что очередной вектор Qr строится из исходного вектора-столбца br как его нормированная проекция на ортогональное дополнение к подпространству уже построенных г - 1 векторов Такой способ построения ортонормированных векторов оказывается очень чувствительным к ошибкам округления [34, 41-43] При весьма косо-

угольной исходной системе векторов {bj, что характерно для задач радиолокационного наблюдения, ошибки вычисления проекций накапливаются и ортогональность векторов нарушается Для повышения численной устойчивости применяется переортогонализация [42], которая требует дополнительно порядка арифметических операций, или используются различные модификации классической процедуры

Модифицированный алгоритм ортогонализации Грама- Шмидта Повышение численной устойчивости достигается следующим видоизменением классического варианта За первые (г-1) шагов в матрице ортонормированы {г-1) столбцов, а г-й столбец ортогонален к ним На г-м шаге г-й стол-

бец матрицы Втп нормируется, а последние К - г столбцов ортогонализируются к г-му столбцу

После реализации /С-шагов элементарных преобразований получим

(3 63)

где SW = Впш, и г - элементарная верхняя треугольная матрица

г=/ + еДР~<-еГ)==

1гт • frK 1

(3 64)

где f.; = 0, у<г, Ur = \b74\\ frj-=- />

b(0 - /-столбец преобразуемой матрицы на г-м шаге

Из приведенных выражений следует, что столбцы матрицы g(r-f-i) Q(r)u определяются соотношениями

J<r,

j=r, (3.65)

bj> - [ьГ (ьГ *>b[)- ъ7 П ъП J > г.

Из соотношения (3 65) следует связь . модифицированного алгоритма с операторами проектирования Аналогично (3 62) в данном случае имеем схему

(1) q. = -, Р. =q,qr, bf=ilK-Pqdb„ у = 2, 3. . „К.

(2) 42 = jilK-Pgi)b2\ilK-Pqi)b2\~\ Рд2 = Ч2Ч2,

(3) qs =

iU-Pq.) iK-Pq) Ьз

h(3)

"3

Wk-Ря.) [Ik-P,.) Ьз ЬГ = Д(/.-Р,,)Ь;, /=4, 5, ,К

. <7э = qaqr,

{г) q,= n(/j,-P,Jb, П(/-РЬ,

« = 1

. ?,=qrqr. (3.66)

г = 1

Сравнение (3 62) и (3 66) показывает отличия модифицированного алгоритма На каждом шаге процедуры производится ортогонализация (без нормировки) оставшихся К - г векторов Ыр путем проектирования каждого из них на ортогональное

дополнение к построенному вектору q Такая корректировка на каждом шаге процесса позволяет избежать трудоемкой процедуры переортогонализации Умножая (3 63) слева на В- и учитывая, что Q- = Q~, найдем

B-==U,U2 UkQT (3 67)

Таким образом, алгоритм ортогонализации может быть использован для вычисления обратной матрицы в факторизованном виде Для разреженных матриц это существенно экономит требуемую память ОЗУ

Для решения системы линейных уравнений с использованием ортогонализации Грама-Шмидта требуется К+К умножений, -{2К. - - К) сложений, К - делений, /С -извлечений квадратного корня 112