Метод ортогонализации (QR-факторизации)
Основные понятия и определения. Существует серия матричных алгоритмов решения линейных систем уравнений общего вида, основанных на идее ортогонализации. Однако, прежде чем изложить содержание некоторых из них, дадим необходимые понятия и определения.
Два вектора 
и 
называются ортогональными, если их скалярное произведение равно нулю
,
или
.
В комплексной плоскости операции транспонирования соответствует операция эрмитового сопряжения – знак «
»:
,
что соответствует понятию унитарности. Эрмитово сопряжение означает применение операции транспонирования и комплексного сопряжения 
.
Длина вектора , обозначаемая через 
и называемая нормой вектора , определяется выражением:
.
Вектор называется единичным, если его длина равна единице, при этом 
. В связи с этим различают нормированную и ненормированную системы векторов.
Так, если интерпретировать матрицы как систему нормированных по строкам либо столбцам векторов, то можно дать следующие важные определения.
Матрица называется ортогональной, если выполняется соотношение
.
Матрица 
называется эрмитовой, если для ее элементов выполняется соотношение 
,
это означает, что диагональные элементы эрмитовых матриц вещественны.
Матрица называется унитарной, если
.
Для ненормированных ортогональных и унитарных матриц имеют место соотношения
где 
– диагональная матрица. Из этого соотношения следует, что элементы диагональной матрицы представляют собой скалярные произведения строк либо столбцов ортогональных по строкам либо столбцам матриц
при 
.
Для ортогональных и унитарных матриц соответственно имеем
т.к. ортогональность есть частный случай унитарности, то в дальнейшем при изложении для упрощения будем использовать термин ортогональность, подразумевая его расширение до унитарности для комплексных матриц.
Из введенных понятий и определений следуют основные свойства ортогональных матриц:
1) строки (столбцы) ортогональных матриц ортогональны;
2) сумма квадратов элементов любой строки (столбца) ортогональной нормированной (ортонормированной) матрицы равна 
;
3) определитель ортонормальной матрицы равен 
;
4) транспонированная (эрмитово-сопряженная) ортогональной (унитарной) матрицы или, что то же самое, матрица, обратная ортогональной (унитарной), – ортогональна (унитарна).
Из линейной алгебры известно, что любую невырожденную матрицу можно разложить (факторизовать) на произведение ортогональной и верхней либо нижней треугольной матриц. Существует несколько алгоритмов ортогональной факторизации, для обобщенного названия которых воспользуемся термином 
-факторизация, подразумевая под 
– ортогональную, а под 
– треугольную матрицы. На основе -факторизации, можно реализовать решение линейных систем уравнений общего вида. Вначале рассмотрим идеи алгоритмов решения, основанных на -факторизации, а затем – алгоритмы -факторизации как на основе ортогонализации матриц по Грамму-Шмидту, так и на основе элементарных операций над строками и столбцами исходной матрицы. При изложении алгоритмов решения подразумевается, что -факторизация реализована.
Ортогональные алгоритмы решения. Рассмотрим алгоритмы решения линейных систем, основанные на ортогонализации исходной матрицы. Перейдем непосредственно к изложению алгоритмов решения линейных систем уравнений
(6.29)
основанных на различных способах ортогонального разложения матрицы коэффициентов исходной системы уравнений.
Вариант ортогонализации по столбцам. Используя алгоритм ортогонализации по столбцам, исходную систему можно записать в виде
(6.30)
где – ортогональная по столбцам матрица либо ортонормированная матрица; – верхнетреугольная матрица с единичной диагональю либо обычная.
Умножая уравнение (6.30) справа на 
, в соответствии с соотношениями ортогональности получаем
где 
– диагональная матрица. Вводя обозначение
(6.31)
запишем
откуда формально следует
Последнее соотношение, если ввести обозначение
(6.32)
можно записать в виде
(6.33)
либо
(6.34)
При этом, учитывая, что матрица Q-верхнетреугольная, мы фактически свели решение исходной системы к обратному ходу алгоритма Гаусса. Рассматривая расширенную вектором 
матрицу , в соответствии с обратным ходом алгоритма Гаусса без нормировки имеем
(6.35)
где 
; 
; 
. В результате на месте вектора будет сформирован вектор решений . Для этих же целей можно воспользоваться алгоритмом Гаусса-Жордана, исключив нормировку и ограничив перебор строк от до (
), где 
– номер ведущей строки.
Отметим, что вычисления векторов 
по выражению (6.31) и по выражению (6.32), включая обращение диагональной матрицы , достаточно тривиальны.
Так, если воспользоваться ортонормальным разложением, то, как следует из соотношения ортогональности 
, решение определится выражением
(6.36)
где – обычная верхнетреугольная матрица.
Вариант ортогонализации по строкам. В случае факторизации, основанной на ортогонализации по строкам, исходная система представляется в виде
(6.37)
где – нижнетреугольная матрица с единичной диагональю либо обычная; – ортогональная по строкам матрица либо ортонормированная матрица.
Умножая соотношение (6.37) на 
справа, получаем систему
,
или, обозначая
,
имеем
(6.38)
Решение этой системы с учетом соотношений ортогональности запишется как
(6.39)
а в случае ортонормальной матрицы имеем
(6.40)
Очень важно отметить тот факт, что, если факторизация, основанная на ортогонализации по строкам, осуществляется над расширенной вектором матрицей 
, то на месте (
)-го столбца формируется вектор . В противном случае алгоритм факторизации, основанный на ортогонализации строк, требует обращения нижнетреугольной матрицы. Для этой цели можно воспользоваться алгоритмом Гаусса-Жордана с учетом треугольности. Кроме того, алгоритм обращения треугольных матриц легко получить следующим способом.
Обращение треугольной матрицы. Обозначив элементы обратной матрицы через 
и ограничившись для наглядности порядком матрицы 
, распишем произведение 
для нижнетреугольных матриц:
.
Проанализировав соотношения, описываемые этим выражением, легко записать алгоритм определения элементов матрицы, обратной к нижнетреугольной:
, (6.41)
при 
; 
; 
;
(6.42)
при 
; 
;
(6.43)
при 
; 
;
.
Аналогичным образом можно получить выражения для обращения верхнетругольной матрицы.
Ортогональные алгоритмы решения линейных алгебраических систем уравнений можно интерпретировать через ортогонализацию исходной матрицы коэффициентов системы элементарными операциями над строками либо столбцами.
Вариант элементарных операций над строками. Факторизация на основе элементарных операций над строками в силу соотношения
(6.44)
преобразует исходную систему (6.29) к виду
(6.45)
или
(6.46)
Умножив правую и левую части выражения (6.46) на и учитывая соотношение ортогональности, запишем решение в виде
, (6.47)
где – ортогональная либо ортонормированная по строкам матрица; – нижнетреугольная матрица с единичной диагональю либо обычная.
В случае ортонормальной матрицы из соотношений ортогональности следует 
, и решение системы запишется в виде
. (6.48)
Видим, что принципиальной разницы между данным алгоритмом решения (на основе факторизации путем элементарных операций над строками) и предыдущим вариантом, основанном на факторизации путем ортогонализации строк, практически нет. При изложении алгоритмов факторизации доказывается, что эти алгоритмы отличаются лишь порядком выполнения операций над строками.
Как и в предыдущем варианте алгоритма, на этапе факторизации, можно рассматривать матрицу , расширенную вектором , тогда в результате преобразований на месте ()-го столбца образуется вектор . В противном случае необходимо вычислять обратную матрицу .
Вариант элементарных операций над столбцами. Факторизация на основе элементарных операций над столбцами в силу соотношения
(6.49)
преобразует исходную систему (6.32) к виду
или
,
где – ортогональная либо ортонормированная по столбцам матрица; – верхнетреугольная матрица с единичной диагональю либо обычная.
Вводя обозначение
, (6.50)
можем записать
,
откуда следует
.
Последнее соотношение, если ввести обозначение
, (6.51)
можно записать
(6.52)
либо
. (6.53)
В случае ортонормальной матрицы из соотношения ортогональности следует , и решение системы запишется в виде
. (6.54)
Видим, что принципиальной разницы между данным алгоритмом решения, на основе факторизации путем элементарных операций над столбцами и предыдущим вариантом, основанном на факторизации путем ортогонализации столбцов, практически нет. При изложении алгоритмов факторизации доказывается, что эти алгоритмы отличаются лишь порядком выполнения операций над столбцами.
Метод -факторизации матрицы коэффициентов исходной системы уравнений и метод 
-факторизации имеют преимущества перед методами исключения Гаусса и Гаусса-Жордана при многократном решении системы с разными правыми частями, встречающимися при вычислении чувствительности и численном интегрировании систем дифференциальных уравнений. Это обстоятельство объясняется тем фактом, что разложение производится один раз и хранится в матрицах и , что составляет примерно половину операций необходимых для решения.
Методы решений систем уравнений, основанные на ортогональном разложении исходной матрицы коэффициентов, отличаются повышенной устойчивостью и точностью вычислений. Дело в том, что погрешности вычислений при ортогональных преобразованиях минимизируются.
Остановимся подробнее на алгоритмах -факторизации на основе ортогонализации по Грамму-Шмидту и элементарных операций над строками и столбцами.