Уровень задачи

QR-разложения плотных неособенных матриц: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[досмотренная версия][выверенная версия]
 
(не показано 8 промежуточных версий 2 участников)
Строка 7: Строка 7:
 
Классические методы QR-разложения можно разделить на две группы: приведения матрицы унитарными преобразованиями к треугольному виду и приведения матрицы неунитарными преобразованиями к унитарному виду. К первой группе относятся методы Гивенса (вращений) и Хаусхолдера (отражений), ко второй — метод ортогонализации. Строго говоря, доказательство теоремы<ref name="VOLA" /> о существовании даёт ещё один способ разложения — через разложение Холецкого матрицы <math>A^*A</math> с последующей обратной подстановкой, но для вырожденных матриц он не работает, поэтому обычно не применяется.  
 
Классические методы QR-разложения можно разделить на две группы: приведения матрицы унитарными преобразованиями к треугольному виду и приведения матрицы неунитарными преобразованиями к унитарному виду. К первой группе относятся методы Гивенса (вращений) и Хаусхолдера (отражений), ко второй — метод ортогонализации. Строго говоря, доказательство теоремы<ref name="VOLA" /> о существовании даёт ещё один способ разложения — через разложение Холецкого матрицы <math>A^*A</math> с последующей обратной подстановкой, но для вырожденных матриц он не работает, поэтому обычно не применяется.  
  
=== Метод Гивенса ===
+
=== Методы приведения унитарными преобразованиями к треугольному виду ===
  
Классический [[Метод Гивенса (вращений) QR-разложения квадратной матрицы (вещественный вариант)|метод Гивенса (вращений)]] основан на преобразованиях вращения (умножения на матрицы Гивенса) слева.
+
==== Метод Гивенса ====
  
=== Метод Хаусхолдера ===
+
Классический [[Метод Гивенса (вращений) QR-разложения матрицы|метод Гивенса (вращений)]] основан на преобразованиях вращения (умножения на матрицы Гивенса) слева для приведения матрицы к правому треугольному виду <math>R</math>. Имеет линейный по размеру задачи критический путь графа.
  
Классический [[Метод Хаусхолдера (отражений) QR-разложения квадратной матрицы, вещественный вариант|метод Хаусхолдера (отражений)]] основан на преобразованиях отражения (Хаусхолдера).
+
==== Метод Хаусхолдера ====
  
=== Метод ортогонализации ===
+
Классический [[Метод Хаусхолдера (отражений) 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]]

Текущая версия на 16:14, 16 марта 2018


Нахождение разложения матриц в виде [math]A = QR[/math], где [math]Q[/math] - унитарная, [math]R[/math] — правая треугольная матрица[1]., является важным этапом при решении некоторых более сложных задач. Существование такого разложения, в котором правая треугольная матрица ещё и не содержит нулей на диагонали, доказано[2] для невырожденных матриц. Однако в ряде случаев [math]QR[/math]-разложение (возможно, с нулями на диагонали [math]R[/math]) нужно и в задачах без гарантии невырожденности. Поэтому для нахождения такого разложения разработано несколько классических методов, являющихся конструктивным доказательством существования разложения в общем случае, а также их варианты.

1 Методы нахождения QR-разложения плотных неособенных матриц

Классические методы QR-разложения можно разделить на две группы: приведения матрицы унитарными преобразованиями к треугольному виду и приведения матрицы неунитарными преобразованиями к унитарному виду. К первой группе относятся методы Гивенса (вращений) и Хаусхолдера (отражений), ко второй — метод ортогонализации. Строго говоря, доказательство теоремы[2] о существовании даёт ещё один способ разложения — через разложение Холецкого матрицы [math]A^*A[/math] с последующей обратной подстановкой, но для вырожденных матриц он не работает, поэтому обычно не применяется.

1.1 Методы приведения унитарными преобразованиями к треугольному виду

1.1.1 Метод Гивенса

Классический метод Гивенса (вращений) основан на преобразованиях вращения (умножения на матрицы Гивенса) слева для приведения матрицы к правому треугольному виду [math]R[/math]. Имеет линейный по размеру задачи критический путь графа.

1.1.2 Метод Хаусхолдера

Классический метод Хаусхолдера (отражений) основан на преобразованиях отражения (Хаусхолдера) слева для приведения матрицы к правому треугольному виду [math]R[/math]. Устойчивый классический вариант имеет квадратичный по размеру задачи критический путь графа, применение сдваивания уменьшает его до [math]O (n log_{2} n)[/math]. Тем не менее, в библиотеках программ более популярен, чем метод Гивенса, из-за того, что легче опирается на базовые подпрограммы библиотеки BLAS.

1.2 Другие методы

1.2.1 Метод ортогонализации

Метод ортогонализации основан на процессе ортогонализации столбцов матрицы. Таким образом, правыми треугольными преобразованиями матрица приводится к унитарному виду [math]Q[/math]. Классический метод неустойчив, а переортогонализация делает этот метод более медленным.

1.2.2 Метод треугольного разложения матрицы Грама

Практически не применяющийся метод работает только в условиях гарантированной невырожденности исходной матрицы [math]A[/math]. Состоит из трёх частей: нахождение матрицы Грама [math]A^*A[/math] столбцов исходной матрицы, нахождение_симметричного_треугольного_разложения матрицы Грама [math]A^*A[/math] в виде [math]R^*R[/math], нахождение унитарной матрицы [math]Q=AR^{-1}[/math], например, с помощью модифицированной обратной подстановки.

2 Литература

  1. В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.
  2. 2,0 2,1 Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.