QR-разложения плотных неособенных матриц: различия между версиями
| [досмотренная версия] | [досмотренная версия] |
Frolov (обсуждение | вклад) |
ASA (обсуждение | вклад) Нет описания правки |
||
| (не показано 11 промежуточных версий 2 участников) | |||
| Строка 1: | Строка 1: | ||
{{level-p}} | {{level-p}} | ||
Нахождение разложения матриц в виде <math>A = QR</math>, где <math>Q</math> - унитарная, <math>R</math> — правая треугольная матрица<ref>В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.</ref>., является важным этапом при решении некоторых более сложных задач. Поэтому для нахождения такого разложения разработано несколько классических методов, а также их варианты. | Нахождение разложения матриц в виде <math>A = QR</math>, где <math>Q</math> - унитарная, <math>R</math> — правая треугольная матрица<ref>В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.</ref>., является важным этапом при решении некоторых более сложных задач. Существование такого разложения, в котором правая треугольная матрица ещё и не содержит нулей на диагонали, доказано<ref name="VOLA">Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref> для невырожденных матриц. Однако в ряде случаев <math>QR</math>-разложение (возможно, с нулями на диагонали <math>R</math>) нужно и в задачах без гарантии невырожденности. Поэтому для нахождения такого разложения разработано несколько классических методов, являющихся конструктивным доказательством существования разложения в общем случае, а также их варианты. | ||
== Методы нахождения QR-разложения плотных неособенных матриц == | == Методы нахождения QR-разложения плотных неособенных матриц == | ||
Классические методы QR-разложения можно разделить на две группы: приведения матрицы унитарными преобразованиями к треугольному виду и приведения матрицы неунитарными преобразованиями к унитарному виду. К первой группе относятся методы Гивенса (вращений) и Хаусхолдера (отражений), ко второй | Классические методы QR-разложения можно разделить на две группы: приведения матрицы унитарными преобразованиями к треугольному виду и приведения матрицы неунитарными преобразованиями к унитарному виду. К первой группе относятся методы Гивенса (вращений) и Хаусхолдера (отражений), ко второй — метод ортогонализации. Строго говоря, доказательство теоремы<ref name="VOLA" /> о существовании даёт ещё один способ разложения — через разложение Холецкого матрицы <math>A^*A</math> с последующей обратной подстановкой, но для вырожденных матриц он не работает, поэтому обычно не применяется. | ||
=== | === Методы приведения унитарными преобразованиями к треугольному виду === | ||
==== Метод Гивенса ==== | |||
Классический [[Метод Гивенса (вращений) QR-разложения матрицы|метод Гивенса (вращений)]] основан на преобразованиях вращения (умножения на матрицы Гивенса) слева для приведения матрицы к правому треугольному виду <math>R</math>. Имеет линейный по размеру задачи критический путь графа. | |||
==== Метод Хаусхолдера ==== | |||
Классический [[Метод Хаусхолдера (отражений) QR-разложения матрицы|метод Хаусхолдера (отражений)]] основан на преобразованиях отражения (Хаусхолдера) слева для приведения матрицы к правому треугольному виду <math>R</math>. Устойчивый классический вариант имеет квадратичный по размеру задачи критический путь графа, применение сдваивания уменьшает его до <math>O (n log_{2} n)</math>. Тем не менее, в библиотеках программ более популярен, чем метод Гивенса, из-за того, что легче опирается на базовые подпрограммы библиотеки BLAS. | |||
[[Метод ортогонализации]] основан на процессе ортогонализации столбцов матрицы. | === Другие методы === | ||
==== Метод ортогонализации ==== | |||
[[Метод ортогонализации]] основан на процессе ортогонализации столбцов матрицы. Таким образом, правыми треугольными преобразованиями матрица приводится к унитарному виду <math>Q</math>. Классический метод неустойчив, а переортогонализация делает этот метод более медленным. | |||
==== Метод треугольного разложения матрицы Грама ==== | |||
Практически не применяющийся [[Метод треугольного разложения матрицы Грама|метод]] работает только в условиях гарантированной невырожденности исходной матрицы <math>A</math>. Состоит из трёх частей: нахождение матрицы Грама <math>A^*A</math> столбцов исходной матрицы, [[Метод_Холецкого_(нахождение_симметричного_треугольного_разложения)|нахождение_симметричного_треугольного_разложения]] матрицы Грама <math>A^*A</math> в виде <math>R^*R</math>, нахождение унитарной матрицы <math>Q=AR^{-1}</math>, например, с помощью модифицированной обратной подстановки. | |||
== Литература == | == Литература == | ||
<references /> | <references /> | ||
[[Категория:Законченные статьи]] | |||
[[en:QR decomposition of dense nonsingular matrices]] | |||
Текущая версия от 13:14, 16 марта 2018
Нахождение разложения матриц в виде [math]\displaystyle{ A = QR }[/math], где [math]\displaystyle{ Q }[/math] - унитарная, [math]\displaystyle{ R }[/math] — правая треугольная матрица[1]., является важным этапом при решении некоторых более сложных задач. Существование такого разложения, в котором правая треугольная матрица ещё и не содержит нулей на диагонали, доказано[2] для невырожденных матриц. Однако в ряде случаев [math]\displaystyle{ QR }[/math]-разложение (возможно, с нулями на диагонали [math]\displaystyle{ R }[/math]) нужно и в задачах без гарантии невырожденности. Поэтому для нахождения такого разложения разработано несколько классических методов, являющихся конструктивным доказательством существования разложения в общем случае, а также их варианты.
Методы нахождения QR-разложения плотных неособенных матриц
Классические методы QR-разложения можно разделить на две группы: приведения матрицы унитарными преобразованиями к треугольному виду и приведения матрицы неунитарными преобразованиями к унитарному виду. К первой группе относятся методы Гивенса (вращений) и Хаусхолдера (отражений), ко второй — метод ортогонализации. Строго говоря, доказательство теоремы[2] о существовании даёт ещё один способ разложения — через разложение Холецкого матрицы [math]\displaystyle{ A^*A }[/math] с последующей обратной подстановкой, но для вырожденных матриц он не работает, поэтому обычно не применяется.
Методы приведения унитарными преобразованиями к треугольному виду
Метод Гивенса
Классический метод Гивенса (вращений) основан на преобразованиях вращения (умножения на матрицы Гивенса) слева для приведения матрицы к правому треугольному виду [math]\displaystyle{ R }[/math]. Имеет линейный по размеру задачи критический путь графа.
Метод Хаусхолдера
Классический метод Хаусхолдера (отражений) основан на преобразованиях отражения (Хаусхолдера) слева для приведения матрицы к правому треугольному виду [math]\displaystyle{ R }[/math]. Устойчивый классический вариант имеет квадратичный по размеру задачи критический путь графа, применение сдваивания уменьшает его до [math]\displaystyle{ O (n log_{2} n) }[/math]. Тем не менее, в библиотеках программ более популярен, чем метод Гивенса, из-за того, что легче опирается на базовые подпрограммы библиотеки BLAS.
Другие методы
Метод ортогонализации
Метод ортогонализации основан на процессе ортогонализации столбцов матрицы. Таким образом, правыми треугольными преобразованиями матрица приводится к унитарному виду [math]\displaystyle{ Q }[/math]. Классический метод неустойчив, а переортогонализация делает этот метод более медленным.
Метод треугольного разложения матрицы Грама
Практически не применяющийся метод работает только в условиях гарантированной невырожденности исходной матрицы [math]\displaystyle{ A }[/math]. Состоит из трёх частей: нахождение матрицы Грама [math]\displaystyle{ A^*A }[/math] столбцов исходной матрицы, нахождение_симметричного_треугольного_разложения матрицы Грама [math]\displaystyle{ A^*A }[/math] в виде [math]\displaystyle{ R^*R }[/math], нахождение унитарной матрицы [math]\displaystyle{ Q=AR^{-1} }[/math], например, с помощью модифицированной обратной подстановки.