2014-02-12
7553
Наиболее известным алгоритмом разложения матрицы на произведение ортогональной и треугольной матриц является алгоритм Грамма-Шмидта.
Вариант ортогонализации по столбцам. Суть алгоритма основана на утверждении, что всякую неособенную матрицу 
можно представить в виде произведения матрицы 
с ортогональными столбцами на верхнетреугольную матрицу 
с единичной диагональю либо в виде произведения ортонормальной по столбцам матрицы на обычную верхнетреугольную матрицу :
. (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)
окажется трансформированный вектор 
.
