Разложение матрицы

Разложе́ние ма́трицы — представление матрицы $A$ в виде произведения матриц, обладающих некоторыми определёнными свойствами (например, ортогональностью, симметричностью, диагональностью). У каждого класса матричных разложений имеется своя область применения; в частности, многие эффективные алгоритмы вычислительной линейной алгебры основаны на построении соответствующих матричных разложений.

Разложения для решения СЛАУ

LU-разложение

Ограничения: матрица $A$ — квадратная и невырожденная, причём все её ведущие главные миноры отличны от нуля[1].
Вид разложения: $A=LU$ , где $L$ — нижняя треугольная матрица, а $U$ — верхняя треугольная. Для однозначности разложения обычно дополнительно требуют, что матрица $L$ была унитреугольной, т. е. треугольной матрицей с диагональными элементами, равными единице (иногда вместо этого требование унитреугольности накладывают на матрицу $U$ )[2].
Сходные разложения: LDU-разложение в виде $A=LDU$ , где $L$ — нижняя унитреугольная матрица, $U$ — верхняя унитреугольная, а $D$ — диагональная.
Сходные разложения: LUP-разложение в виде $PA=LU$ , где $P$ — матрица перестановок (выбирается в процессе построения разложения), $L$ нижняя унитреугольная матрица, $U$ — верхняя треугольная матрица. Это — обобщение LU-разложения на случай произвольных невырожденных матриц.
Существование: LUP-разложение существует для любой квадратной матрицы $A$ . Когда матрица $P$ сводится к единичной матрице, LUP-разложение сводится к LU-разложению.
LUP и LU-разложения используются при решении СЛАУ $Ax=b$ размерности $n\times n$ . Соответствующие методы представляют собой варианты матричной формы метода Гаусса. Матрица $P$ характеризует при этом совокупный эффект перестановок строк в методе Гаусса.

Ранговая факторизация

Ограничения: произвольная матрица $A$ размера $m\times n$ и ранга $r$ .

Вид разложения: $A=CF$ , где $C$ — матрица $m\times r$ и $F$ — матрица $r\times n$ .
Ранговая факторизация может быть использована для вычисления псевдообратной матрицы, которая применяется при отыскании общего решения СЛАУ $Ax=b$ .

Разложение Холецкого

Ограничения: симметричная положительно определённая матрица $A$ [3].
Вид разложения: $A=U^{T}U$ (или, что эквивалентно, $A=LL^{T}$ ), где матрица $U$ — верхняя треугольная (соответственно, матрица $L$ — нижняя треугольная)[3].
Сходные разложения: альтернативой является модифицированное разложение Холецкого (LDL-разложение), которое позволяет избежать извлечения корней (в нём матрица $L$ — нижняя унитреугольная, а $D$ — диагональная).
Разложение Холецкого единственно.
Разложение Холецкого также применимо, если матрица $A$ эрмитова и положительно определена.
Разложение Холецкого применяется для решения СЛАУ $Ax=b$ , если матрица $A$ имеет соответствующие свойства. Этот способ решения, по сравнению с методом LU-разложения, заведомо численно устойчив и требует в два раза меньше арифметических операций[4].

QR-разложение

Ограничения: произвольная матрица $A$ размера $m\times n$ .
Вид разложения: $A=QR$ , где $Q$ — ортогональная матрица размера $m\times m$ , и $R$ — верхняя треугольная размера $m\times n$ .
Сходные разложения: существуют аналогичные QL-, RQ- и LQ-разложения.
В силу ортогональности матрицы $Q$ (что означает совпадение обратной матрицы $Q^{-1}$ с транспонированной матрицей $Q^{T}$ ) система $Ax=b$ эквивалентна системе $Rx=Q^{T}b$ с треугольной матрицей, решение которой не доставляет труда.
Одним из способов получения матрицы $Q$ является процесс Грама ― Шмидта, и тогда $R=Q^{T}A$ .
Построение QR-разложения является основой QR-алгоритма ― одного из методов поиска собственных векторов и значений матрицы.
Алгоритмы решения СЛАУ на основе QR-разложения практически одинаково работают как для хорошо обусловленных, так и для сингулярных систем[5].

Интерполяционное разложение

Ограничения: произвольная матрица $A$ размерности $m\times n$ и ранга $r$ .
Вид разложения: $A=A_{(:,J)}X$ , где $J$ — подмножество из $r$ индексов $1,...,n$ ; матрица $A_{(:,J)}$ состоит из соответствующих столбцов изначальной матрицы; $X$ — $r\times n$ матрица, все элементы которой по модулю не больше 2 (кроме того, $X$ содержит единичную подматрицу размерности $r\times r$ ). Аналогичное разложение можно получить и по строкам.

Разложения, связанные с собственными или сингулярными значениями

Спектральное разложение

Ограничения: диагонализуемая квадратная матрица $A$ , т. е. имеющая набор из $n$ различных собственных векторов (при этом собственным значениям не обязательно различаться).
Вид разложения: $A=VDV^{-1}$ , где $D$ — диагональная, образованная из собственных значений $A$ , а столбцы $V$ — соответствующие собственные вектора.
Существование: матрица размерности $n\times n$ всегда имеет $n$ собственных значений (с учётом кратности), которые могут быть упорядочены (не единственным способом), чтобы построить диагональную матрицу $D$ размерности $n\times n$ и соответствующую матрицу из ненулевых столбцов $V$ , которые удовлетворяют равенству $AV=VD$ . Если $n$ собственных векторов различны, тогда матрица $V$ имеет обратную, что и даст искомое разложение $A=VDV^{-1}$ [6].
Всегда можно нормировать собственные векторы, чтобы те имели длину 1. Если $A$ вещественная симметричная матрица, то $V$ всегда обратима и нормализуема. В этом случае матрица $V$ оказывается ортогональной, поскольку собственные векторы ортогональны по отношению друг к другу. Таким образом, искомое разложение (которое в рассматриваемом случае всегда существует) можно записать как $A=VDV^{T}$ .
Необходимым и достаточным условием диагонализуемости является совпадение геометрической и алгебраической кратности каждого собственного значения. В частности, наличие $n$ различных собственных значений является достаточным (но не необходимым) условием.
Спектральное разложение полезно для понимания решений систем линейных обыкновенных дифференциальных уравнений или разностных уравнений. Например, разностное уравнение $x_{t+1}=Ax_{t}$ с начальным условием $x_{0}=c$ имеет решение $x_{t}=A^{t}c$ , что можно записать иначе как $x_{t}=VD^{t}V^{-1}c$ (в случае, если $A=VDV^{-1}$ ). Возведение в степень $t$ диагональной матрицы $D$ сведётся к возведению каждого элемента на диагонали в степень $t$ , что несравнимо проще, чем $A$ (если, конечно, последняя изначально не имеет диагональный вид).

Жорданова нормальная форма

Ограничения: квадратная матрица $A$ .
Вид разложения: $A=CJC^{-1}$ , где $J$ — жорданова матрица, а $C$ — матрица перехода к новому базису.
Жорданова нормальная форма является обобщением диагональной формы матрицы $A$ , составленной из собственных значений, на случай, когда геометрическая кратность одного или нескольких собственных значений меньше алгебраической кратности.

Разложение Шура

Ограничения: квадратная матрица $A$ .
Существует две версии разложения: для случая вещественной матрицы и для случая комплексной матрицы. Последняя всегда имеет комплексное разложение Шура.
Вид разложения (вещественный случай): $A=VSV^{T}$ (все матрицы в обеих частях равенства составлены из строго вещественных значений). В этом случае $V$ — ортогональная матрица, а $S$ — квазитреугольная. Последняя называется вещественной формой Шура. Блоки на диагонали $S$ либо размера $1\times 1$ (в таком случае они представляют собой действительные собственные значения) или $2\times 2$ (образуемые парой комплексно-сопряжённых собственных чисел).
Вид разложения (комплексный случай): $A=UTU^{H}$ , где $U$ — унитарная, $U^{H}$ — её эрмитово-сопряжённая, а $T$ — верхняя треугольная матрица, называемая комплексной формой Шура, которая содержит собственные значения $A$ на диагонали.

QZ-разложение

Ограничения: квадратные матрицы $A$ и $B$ .
Существует две версии разложения: комплексная и действительная.
Вид разложения (комплексный случай): $A=QSZ^{H},B=QTZ^{H}$ , где $Q$ и $Z$ — унитарные матрицы, $Z^{H}$ — эрмитово-сопряжённая к $Z$ , $S$ и $T$ — верхне-треугольные матрицы.
В указанном разложении соотношение диагональных элементов в $S$ и соответствующих в $T$ , $\lambda _{i}=S_{ii}/T_{ii}$ являются обобщёнными собственными значениями, которые являются решением обобщённой задачи поиска собственных значений $Av=\lambda Bv$ (где $\lambda$ — неизвестный скаляр и $v$ — неизвестный ненулевой вектор).
Вид разложения (вещественный случай): $A=QSZ^{T},B=QTZ^{T}$ , где все матрицы состоят строго из вещественных значений. $Q,Z$ — ортогональные матрицы, а $S,T$ — квазитреугольные, состоящие из блоков $1\times 1$ или $2\times 2$ (аналогичных соответствующим блокам в разложении Шура).

Сингулярное разложение

Ограничения: произвольная матрица $A$ размера $m\times n$ [7].
Вид разложения: $A=U\Sigma V^{H}$ , где $\Sigma$ — неотрицательная диагональная матрица, $U,V$ — унитарные матрицы, а $V^{H}$ — эрмитово-сопряжённая. В вещественном случае $A=U\Sigma V^{T}$ , причём $\Sigma$ , как и прежде, неотрицательная диагональная матрица, $U,V$ — ортогональные[7][8].
Элементы на диагонали матрицы $\Sigma$ называются сингулярными значениями матрицы $A$ и обозначаются $\sigma _{j}.$ Число ненулевых сингулярных значений матрицы $A$ равно рангу этой матрицы[9].
Сингулярное разложение, как и спектральное разложение, включает в себя отыскание базиса подпространств, действие на элементы которых оператора ${\mathcal {A}}$ эквивалентны умножению на скаляр (т. е. $Av=\sigma _{j}v$ ), но при этом сингулярное разложение является более общим методом, поскольку матрица $A$ не обязана быть квадратной.

Другие разложения

Полярное разложение

Ограничения: квадратная комплексная матрица $A$ [10].
Вид разложения (комплексный случай): $A=SU$ , где $S$ — эрмитова матрица с неотрицательными ведущими минорами, а $U$ — унитарная матрица[10][11].
Вид разложения (вещественный случай): $A=SQ$ , где $S$ — симметричная матрица с неотрицательными ведущими минорами, а $Q$ — ортогональная матрица[12][13].
Для невырожденной матрицы полярное разложение единственно, а для вырожденной матрицы однозначно определён лишь множитель $S$ [10].
Полярное разложение матрицы в комплексном случае является аналогом представления произвольного комплексного числа $z$ в виде $z=|z|e^{i\varphi }$ [14].

Фробениусова нормальная форма

Ограничения: квадратная матрица $A$ .
Вид разложения: $A=PCP^{-1}$ , где $C$ — блочно-диагональная матрица, состоящая из сопровождающих матриц для унитарных многочленов $f_{i}$ таких, что $f_{i+1}$ кратен $f_{i}$ . $P$ — переходная матрица.

Примечания

Икрамов, 1991, с. 20.
Воеводин и Кузнецов, 1984, с. 75—76.
Воеводин и Кузнецов, 1984, с. 176.
William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. . 2.9 Cholesky Decomposition // Numerical Recipes in C. 2nd edition. — Cambridge: Cambridge University Press. — ISBN 0-521-43108-5.
QR- и SVD- разложения: «плохие» СЛАУ (неопр.).
Meyer, 2000, p. 514.
Икрамов, 1991, с. 21.
Воеводин и Кузнецов, 1984, с. 80.
Форсайт Дж., Малькольм М., Моулер К. . Машинные методы математических вычислений. — М.: Мир, 1980. — 280 с. — С. 214, 225.
Воеводин и Кузнецов, 1984, с. 78.
Гантмахер, 1988, с. 234—236.
Воеводин и Кузнецов, 1984, с. 79.
Гантмахер, 1988, с. 244.
Гантмахер, 1988, с. 236.

Литература

Воеводин В. В., Кузнецов Ю. А. . Матрицы и вычисления. — М.: Наука, 1984. — 320 с.
Гантмахер Ф. Р. . Теория матриц. 4-е изд. — М.: Наука, 1988. — 552 с. — ISBN 5-02-013722-7.
Икрамов Х. Д. . Несимметричная проблема собственных значений. Численные методы. — М.: Наука, 1991. — 240 с. — ISBN 5-02-014462-2.
Meyer, Carl D. . Matrix Analysis and Applied Linear Algebra. — Philadelphia: SIAM, 2000. — xii + 718 p. — ISBN 0-89871-454-0.

Векторы и матрицы

Основные понятия	Вектор в геометрии Базис Ортогональный базис Координаты вектора Коллинеарность Ортогональность Линейная зависимость Пространство столбцов
Виды векторов	Единичный вектор Аксиальный вектор Изотропный вектор Нормаль Коллинеарность Нулевой вектор Радиус-вектор Собственный вектор
Операции над векторами	Скалярное произведение Векторное произведение Смешанное произведение Псевдоскалярное произведение Двойное векторное произведение
Типы пространств	Векторное пространство Аффинное пространство Евклидово пространство Псевдоевклидово пространство Нормированное пространство Пространство Минковского

Основные понятия	Умножение матриц Транспонированная матрица Эрмитово-сопряжённая матрица Симметричная матрица Обратная матрица Собственное значение Характеристический многочлен матрицы
Специальные матрицы	Единичная матрица Нулевая матрица Диагональная матрица Лямбда-матрица
Разложения матриц	LU-разложение Разложение Холецкого QR-разложение LUP-разложение Сингулярное разложение Спектральное разложение матрицы

Другое

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.