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

ASA в 13:14, 16 марта 2018

2018-03-16T13:14:55Z

← Предыдущая версия		Версия от 13:14, 16 марта 2018
Строка 30:		Строка 30:
	<references />		<references />

	~~[[Категория:Законченные статьи без перевода на английский язык]]~~
	[[Категория:Законченные статьи]]		[[Категория:Законченные статьи]]

	[[en:QR decomposition of dense nonsingular matrices]]		[[en:QR decomposition of dense nonsingular matrices]]

ASA в 07:47, 2 марта 2018

2018-03-02T07:47:24Z

← Предыдущая версия		Версия от 07:47, 2 марта 2018
Строка 32:		Строка 32:
	[[Категория:Законченные статьи без перевода на английский язык]]		[[Категория:Законченные статьи без перевода на английский язык]]
	[[Категория:Законченные статьи]]		[[Категория:Законченные статьи]]

			[[en:QR decomposition of dense nonsingular matrices]]

Frolov в 12:44, 15 февраля 2018

2018-02-15T12:44:54Z

← Предыдущая версия		Версия от 12:44, 15 февраля 2018
Строка 29:		Строка 29:
	== Литература ==		== Литература ==
	<references />		<references />

			[[Категория:Законченные статьи без перевода на английский язык]]
			[[Категория:Законченные статьи]]

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

2017-11-06T14:09:42Z

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

← Предыдущая версия		Версия от 14:09, 6 ноября 2017
Строка 25:		Строка 25:
	==== Метод треугольного разложения матрицы Грама ====		==== Метод треугольного разложения матрицы Грама ====

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

	== Литература ==		== Литература ==
	<references />		<references />

Frolov: /* Метод Хаусхолдера */

2017-11-06T13:38:35Z

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

← Предыдущая версия		Версия от 13:38, 6 ноября 2017
Строка 15:		Строка 15:
	==== Метод Хаусхолдера ====		==== Метод Хаусхолдера ====

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

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

Frolov: /* Метод Гивенса */

2017-11-06T12:58:51Z

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

← Предыдущая версия		Версия от 12:58, 6 ноября 2017
Строка 11:		Строка 11:
	==== Метод Гивенса ====		==== Метод Гивенса ====

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

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

Frolov: /* Метод Хаусхолдера */

2017-05-17T10:03:40Z

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

← Предыдущая версия		Версия от 10:03, 17 мая 2017
Строка 15:		Строка 15:
	==== Метод Хаусхолдера ====		==== Метод Хаусхолдера ====

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

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

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

2017-05-17T10:00:28Z

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

← Предыдущая версия		Версия от 10:00, 17 мая 2017
Строка 7:		Строка 7:
	Классические методы QR-разложения можно разделить на две группы: приведения матрицы унитарными преобразованиями к треугольному виду и приведения матрицы неунитарными преобразованиями к унитарному виду. К первой группе относятся методы Гивенса (вращений) и Хаусхолдера (отражений), ко второй — метод ортогонализации. Строго говоря, доказательство теоремы<ref name="VOLA" /> о существовании даёт ещё один способ разложения — через разложение Холецкого матрицы <math>A^*A</math> с последующей обратной подстановкой, но для вырожденных матриц он не работает, поэтому обычно не применяется.		Классические методы QR-разложения можно разделить на две группы: приведения матрицы унитарными преобразованиями к треугольному виду и приведения матрицы неунитарными преобразованиями к унитарному виду. К первой группе относятся методы Гивенса (вращений) и Хаусхолдера (отражений), ко второй — метод ортогонализации. Строго говоря, доказательство теоремы<ref name="VOLA" /> о существовании даёт ещё один способ разложения — через разложение Холецкого матрицы <math>A^*A</math> с последующей обратной подстановкой, но для вырожденных матриц он не работает, поэтому обычно не применяется.

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

	~~Классический [[~~Метод Гивенса (вращений) QR-разложения квадратной матрицы (вещественный вариант)\|метод Гивенса (вращений)]] основан на преобразованиях вращения (умножения на матрицы Гивенса) слева для приведения матрицы к правому треугольному виду <math>R</math>.		==== Метод Гивенса ====

	~~===~~ Метод ~~Хаусхолдера ===~~		Классический [[Метод Гивенса (вращений) QR-разложения квадратной матрицы (вещественный вариант)\|метод Гивенса (вращений)]] основан на преобразованиях вращения (умножения на матрицы Гивенса) слева для приведения матрицы к правому треугольному виду <math>R</math>. Имеет линейный по размеру задачи критический путь графа.

	~~Классический [[~~Метод Хаусхолдера (отражений) QR-разложения квадратной матрицы, вещественный вариант\|метод Хаусхолдера (отражений)]] основан на преобразованиях отражения (Хаусхолдера) слева для приведения матрицы к правому треугольному виду <math>R</math>.		==== Метод Хаусхолдера ====

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

	[[Метод ортогонализации]] основан на процессе ортогонализации столбцов матрицы. Таким образом, правыми треугольными преобразованиями матрица приводится к унитарному виду <math>Q</math>.		=== Другие методы ===

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

			[[Метод ортогонализации]] основан на процессе ортогонализации столбцов матрицы. Таким образом, правыми треугольными преобразованиями матрица приводится к унитарному виду <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 />

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

2017-05-17T09:15:54Z

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

← Предыдущая версия		Версия от 09:15, 17 мая 2017
Строка 9:		Строка 9:
	=== Метод Гивенса ===		=== Метод Гивенса ===

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

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

	Классический [[Метод Хаусхолдера (отражений) QR-разложения квадратной матрицы, вещественный вариант\|метод Хаусхолдера (отражений)]] основан на преобразованиях отражения (Хаусхолдера).		Классический [[Метод Хаусхолдера (отражений) QR-разложения квадратной матрицы, вещественный вариант\|метод Хаусхолдера (отражений)]] основан на преобразованиях отражения (Хаусхолдера) слева для приведения матрицы к правому треугольному виду <math>R</math>.

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

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

	== Литература ==		== Литература ==
	<references />		<references />

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

2017-05-17T09:08:16Z

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

← Предыдущая версия		Версия от 09:08, 17 мая 2017
Строка 5:		Строка 5:
	== Методы нахождения QR-разложения плотных неособенных матриц ==		== Методы нахождения QR-разложения плотных неособенных матриц ==

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

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