Вычислительная математика и программирование - Боглаев Ю.П.
ISBN 5-06-00623-9
Скачать (прямая ссылка):
Напомним, что матрица ортогонального преобразования Т обладает свойством
Г“1* Г,
329
T<f
Рис. 8.9
где Т—транспонированная к Т матрица; кроме тоге, произведение ортогональных матриц есть ортогональная матрица.
В качестве ліатриц Т будем рассматривать матрицы отражения. Матрица отражения Г, порожденная вектором d=(d1, (і2, ..., йп), определяется формулой
T=E—2dd' =
d\ d\d2 .. d^dn
d2dl d\ . .. d2dn
dA : 4? : 4з* : : чз
(8.4.3)
где ||</||2 = 1.
Геометрически матрица Т задает отражение вектора л: относительно плоскости с единичным нормальным вектором d (рис. 8.8).
Заметим, что матрица Т симметрична, ортогональна: Td=—d; если вектор х ортогонален d, то Тх=х.
Построим элементарное отражение Г, которое переводит заданный вектор а = (ри а2, ап) в вектор, коллинеарный вектору /1=(1? 0, ..., 0). Таких отражений два (соответствуют ниже знакам ±) (рис. 8.9):
Та- ±|| а ||2ех.
Вектор d, порождающий искомое отражение, задается формулами
^=с(й1 + IIа ||2, а2, ..., а„), (8.4.4)
где константа с определяется из условия
|| rf || 2 = 1. (8.4.5)
Объединяя (8.4.4), (8.4.5) и (8.4.3), получим искомое отражение Т.
Для однозначного приведения вещественной матрицы А к виду
(8.4.1) обычно используют дополнительное требование, состоящее в том, чтобы значения поддиагонали в (8.4.1) были одного знака, например
я*,i-i^O, (8.4.6)
Это условие выделяет определенный знак в (8.4.4) и единственное элементарное отражение.
Алгоритм приведения к почти треугольной матрице следующий.
1-й шаг. Определим матрицу л-го порядка:
0 7\
330
\
V
где Т г — матрица (п — 1 )-го порядка — отражение, переводящее
вектор
*?2,1
лп, 1
в вектор, коллинеарный /х =(1, 0, ..., 0). Матрица
Л* = 51^5Г1 = *М51
имеет вид
А* =
г * ? * .. - * л *
* * * * *
0 * * .. * *
0 * * * *
У ? * * *
^2,1 ^0,
где знаком * обозначены элементы, которые могут отличаться от нуля.
2-й шаг. Определим матрицу л-го порядка:
(\ о о\
^2 ( 0 1 0 1>
\о о т2)
где Т2 — матрица (л — 2)-го порядка — отражение, переводящее вектор
'ДЗ.2'
(Г)
‘ ап,2
в вектор, коллинеарный /х = (1, 0, ... 0). Матрица
А* = 3231А3132
имеет вид
А* =
* * * * *
* * * * ?
0 * * * *
0 0 * * *
Г °: о- ? * *
а*Ъ,2 ^0,
Продолжая этот процесс, после л —2 шагов получим
Л*=^п_2 ... 51Л51 ...
где А*—матрица (8.4.1), для которой выполняются неравенства
(8.4.6).
Если на каком-либо шаге / получился нулевой вектор, для которого строится отражение, то полагают 5( = Е. Окончательно ортогональное преобразование Т матрицы А к почти треугольному виду определяется произведением ортогональных матриц
Т= $П~2 •••
331
Если матрица А симметрична, то промежуточные матрицы и конечная оказываются также симметричными; следовательно, почти треугольная форма таких матриц является трехдиагональной (8.4.2).
8.4.3. Разложение матрицы в произведение ортогональной и треугольной матриц. Будем считать, что матрица А приведена к почти треугольному виду (8.4.1). Найдем разложение матрицы А в произведение:
А = (2К, (8.4.7)
где <2 — ортогональная матрица, Я—верхняя треугольная матрица:
Я =
А
* * *
о
Определим матрицу элементарного вращения:
і
Р,=
1
О
1
8ІП0? СО80* — СОв 0* БІЙ 0;
О і
1
Можно проверить, что Рь 1, — ортогональные матрицы.
Умножая матрицу А вида (8.4.1) на матрицу Ри получим
8ІЦ0ІСО80! а1Л ••• а1,п
—созО^іп©! 0 а2,1 а2 ,п
1
0 0 '
1^ &п,п- 1@п,п
а1л$тд1+а2'іСО$$і -ах лсо$в1+а2Л вшОї
аЪ,2
а1п 8Іп01+а2ія со80х — «1 „сов©! Н-Я2,л 8ІП0Х
*Ъ,п
я,я -1 ип,п
Выберем угол 0! таким, чтобы поддиагональный элемент в первом столбце обратился в нуль:
— а1Л со80х +д2,1 §іп®і= ®і= (а1Л/а2Л).
В результате умножения матрицы А на Р19 Р2, ..., Рп~і и соответ-
ствующего выбора углов вращения 0* все поддиагональные элементы матрицы А можно обратить в нуль. Таким образом, получим
Л-Л-2 ... РХА = Я, (8.4.8)
\
332
V.
4
.4
І
і
где Я—треугольная матрица. Из (8.4.8) имеем
А = (2Я,
0 = Р'1Р,2... Р'п-и
т. е. (8.4.7). Матрица б— ортогональная как произведение ортогональных матриц.
8.4.4. 0#-алгоритм определения собственных значений и векторов.
Пусть матрица А приведена к почти треугольному виду (8.4.1). Если бы поддиагональ в (8.4.1) обладала свойством
я»,»— і#і+і,і = 0, 2^і^п 1,
т. е. в матрице А отсутствовали бы соседние ненулевые поддиаго-нальные элементы, то матрица А имела бы блочно-треугольную форму
Л\л А\а ? •• AU
0 А\г ? •• AU (8.4.9)
0 0 . - AU
Здесь A*ifi—квадратные блоки порядка 1 или 2. Блоки второго порядка соответствуют ненулевым элементам поддиагонали.
Так как А* и А имеют одни и те же собственные значения, то блоки Ah первого порядка—это собственные значения А. Собственные значения блоков А*>{ второго порядка—это также собственные значения А, но среди них могут быть комплексные числа.
Таким образом, приведение матрицы А к форме (8.4.9) полностью решает проблему собственных значений. Собственные векторы после приведения к (8.4.9) также легко определяются.
Однако для матрицы А, вообще говоря, не существует конечного вычислительного процесса над ее элементами, приводящего А к форме
