Наиболее известным алгоритмом разложения матрицы на произведение ортогональной и треугольной матриц является алгоритм Грамма-Шмидта.
Вариант ортогонализации по столбцам. Суть алгоритма основана на утверждении, что всякую неособенную матрицу 
можно представить в виде произведения матрицы 
с ортогональными столбцами на верхнетреугольную матрицу 
с единичной диагональю либо в виде произведения ортонормальной по столбцам матрицы 
на обычную верхнетреугольную матрицу 
:
. (6.55)
Представим исходную матрицу как совокупность векторов-столбцов
,
где 
. 
.
Т.к. матрица 
неособенная, то векторы 
линейно независимы. Будем искать матрицу 
в виде
,
где 
– искомые ортогональные столбцы.
Вначале положим 
. Следующий вектор 
должен быть построен из 
ортогонально 
. Для этого вектор 
разложим на составляющие:
при условии 
. Умножая это выражение скалярно на 
с учетом ортогональности, получаем
Аналогично вектор 
раскладываем на три составляющие:
при условиях 
и 
.
Последовательно умножая это выражение скалярно на 
, затем на 
, получим
|
|
|
В общем виде, разложение исходных векторов 
на ортогональные векторы 
запишем
(6.56)
где 
.
В соответствии с матричными операциями разложение (6.56) исходной матрицы 
соответствует произведению ортогональной матрицы 
на верхнетреугольную матрицу 
с единичной диагональю.
Продолжая дальше процесс ортогонализации, приходим к следующей форме записи алгоритма
, (6.57)
, 6.58)
где 
,
(6.59)
где 
. 
. 
.
В результате данного алгоритма окажутся сформированными ортогональная по столбцам матрицам 
и верхнетреугольная матрица 
с единичной диагональю.
Если необходимо получить вместо ортогональной ортонормированную матрицу 
(сумма квадратов элементов столбца равна 
), то следует нормировать каждый текущий вектор:
, (6.60)
где 
. Заметим также, что скалярное произведение вектора самого на себя равно квадрату длины вектора:
. (6.61)
В случае нормировки разложение исходных векторов 
на ортогонормальные векторы 
запишется
, (6.62)
где 
.
В соответствии с матричными операциями разложение (6.62) исходной матрицы 
соответствует произведению ортонормальной матрицы 
на верхнетреугольную матрицу 
.
Процесс ортогонализации и нормировки, соответствующий разложению матрицы 
на ортонормальную и верхнетреугольную с учетом (6.57) – (6.59) и (6.60), можно записать соотношениями
, (6.63)
, (6.64)
где 
,
, (6.65)
(6.66)
где 
. 
. 
. Этот процесс называется ортогонализацией Грамма-Шмидта.
Проиллюстрируем разложение матрицы на ортогональную и верхнетреугольную с единичной диагональю на простейшем примере матрицы порядка 
:
.
Зададимся конкретными значениями элементов матрицы
|
|
|
.
Согласно алгоритму, полагаем вначале
.
Тогда
После чего находим
Для определения 
вычисляем
Откуда
Проверяем результат разложения:
|
|
и взаимную ортогональность векторов 
Правильность разложения и ортогональность векторов выполняется, однако векторы не нормированы.
Используя данный пример, рассмотрим процесс разложения матрицы на произведение ортонормальной и верхнетреугольной матриц.
Нормируем первый вектор:
Вычислим
Теперь можем найти
Вычисляем норму
и нормируем вектор
Для определения 
вычислим
Далее находим
Вычислим норму
и нормируем вектор
Вычислим
Проверим результат разложения
|
|
и взаимную ортогональность векторов 
Обратим внимание, что значения матриц 
и 
существенно изменились в результате нормировки системы ортогональных векторов.
Вариант ортогонализации по строкам. Суть алгоритма основана на альтернативном утверждении, что всякую неособенную матрицу 
можно представить в виде произведения матрицы 
с ортогональными строками и нижнетреугольной матрицы 
с единичной диагональю либо в виде произведения ортонормальной по строкам матрицы 
и обычной нижнетреугольной матрицы 
:
. (6.67)
Представим исходную матрицу как совокупность векторов-строк
,
где 
. 
.
Т.к. матрица 
неособенная, то векторы 
линейно независимы. Будем искать матрицу 
в виде
,
где 
– искомые ортогональные строки.
Вначале положим 
. Следующий вектор 
должен быть построен из 
ортогонально 
. Для этого вектор 
разложим на составляющие:
,
где 
. Умножая это выражение скалярно на 
с учетом ортогональности, получаем
Аналогично вектор 
раскладываем на три составляющие:
,
при условиях 
и 
.
Последовательно умножая это выражение скалярно на 
, а затем на 
, получим
В общем виде разложение исходных векторов 
на ортогональные векторы 
запишется как
, (6.68)
где 
.
Матричным операциям разложения (6.68) исходной матрицы 
соответствует произведение нижнетреугольной матрицы 
с единичной диагональю на ортогональную матрицу 
.
Продолжая дальше процесс ортогонализации, приходим к следующей форме записи алгоритма:
, (6.69)
, (6.70)
где 
,
, (6.71)
где 
. 
. 
.
В результате данного алгоритма окажутся сформированными ортогональная по строкам матрица 
и нижнетреугольная матрица 
с единичной диагональю.
В случае нормировки разложение исходных векторов 
на ортогонормальные вектора 
запишется как
, (6.72)
где 
.
В соответствии с матричными операциями разложение (6.72) исходной матрицы 
соответствует произведению нижнетреугольной матрицы 
на ортонормальную матрицу 
.
Процесс ортогонализации нормировки, соответствующий разложению матрицы 
на ортонормальную и верхнетреугольную с учетом (6.69)–(6.71) и (6.60), можно записать соотношениями
, (6.73)
, 6.74)
где 
,
, (6.75)
, (6.76)
где 
. 
. 
. Этот процесс также соответствует ортогонализации Грамма-Шмидта.
При факторизации матрицы с целью решения линейной системы удобно рассмотреть матрицу, расширенную вектором свободных членов, в качестве (
)-го столбца. В результате процесса ортогонализации на месте вектора свободных членов
или
(6.77)
окажется трансформированный вектор 
.
