Qr разложение где используется

Обновлено: 07.07.2024

В линейной алгебры , A QR - разложение , также известный как QR - разложения или QU разложения является разложением из матрицы A в произведение A = QR в качестве ортогональной матрицы Q и верхней треугольной матрицы R . QR - разложение часто используется для решения линейной наименьших квадратов проблемы и является основой для конкретного собственного значения алгоритма , в QR алгоритма .

СОДЕРЖАНИЕ

Любая вещественная квадратная матрица A может быть разложена как

А знак равно Q р ,

где Q - ортогональная матрица (ее столбцы означают ортогональные единичные векторы ), а R - верхнетреугольная матрица (также называемая правотреугольной матрицей, отсюда и название). Если является обратимым , то разложение единственно , если мы требуем диагональные элементы R , чтобы быть положительным. Q Т знак равно Q - 1 > = Q ^ >

Если вместо этого A - это комплексная квадратная матрица, то существует разложение A = QR, где Q - унитарная матрица (так ). Q * знак равно Q - 1 = Q ^ >

Если имеют п линейно независимые столбцы, то первый п столбцы Q образует ортогональный базис для столбца пространства из A . В более общем смысле, первые k столбцов Q образуют ортонормированный базис для диапазона первых k столбцов A для любого 1 ≤ k ≤ n . [1] Тот факт , что любой столбец к из А зависит только от первых K столбцов Q отвечает за треугольной формы R . [1]

В более общем смысле, мы можем факторизовать комплексную матрицу A размера m × n , где m ≥ n , как произведение унитарной матрицы Q размера m × m и верхней треугольной матрицы R размера m × n . Поскольку нижние ( m - n ) строк верхней треугольной матрицы размером m × n полностью состоят из нулей, часто бывает полезно разделить R или оба R и Q :

где R ₁ - верхняя треугольная матрица размера n × n , 0 - нулевая матрица ( m - n ) × n , Q ₁ - это m × n , Q ₂ - это m × ( m - n ) , а Q ₁ и Q ₂ оба имеют ортогональные столбцы.

Голуб и Ван займа (1996 , §5.2) вызова Q ₁ R ₁ тонкий QR - разложение в A ; Трефетен и Бау называют это сокращенной QR-факторизацией . [1] Если A имеет полный ранг n и мы требуем, чтобы диагональные элементы R ₁ были положительными, то R ₁ и Q ₁ уникальны, но в общем случае Q ₂ - нет. R ₁ при этом равна верхней треугольной фактор разложения Холецкого из А * A (= A T A, если A вещественно).

Аналогичным образом мы можем определить разложения QL, RQ и LQ, где L является нижней треугольной матрицей.

Существует несколько методов реального вычисления QR-разложения, например, с помощью процесса Грама – Шмидта , преобразований Хаусхолдера или вращений Гивенса . У каждого есть ряд преимуществ и недостатков.

Специалистам по данным стоит хорошо знать несколько разложений матриц, потому что они помогают находить методы для актуальных вычислений и оценки результатов для моделей и алгоритмов, с которыми мы работаем. В некоторых случаях конкретной формой разложения является алгоритм (например, в методе главных компонент и сингулярном разложении). И во всех случаях разложение матриц помогает развивать интуицию и способность к анализу.

QR — разложение — одно из самых полезных. Ему находится множество важных применений в науке о данных, статистике и анализе данных. Одно из подобных применений — вычисление решения задачи наименьших квадратов.

Содержание статьи

Повторение проблемы наименьших квадратов.
Описание с QR-разложения.
Решение задачи наименьших квадратов с помощью QR-разложения.
Реализация вычисления QR-разложения на R и C++ и сравнение реализаций.

Задача наименьших квадратов

QR-разложение позволяет вычислить решение задачи наименьших квадратов. Подчеркиваю, именно вычислить , поскольку обычный метод наименьших квадратов дает нам закрытое решение в форме нормальных уравнений. Это замечательно, но, если нам нужно найти актуальное числовое решение, этот метод не подойдет.

Вспомним задачу наименьших квадратов. Нужно решить уравнение ниже:

Проблема состоит в том, что не существует решения для β , потому что обычно, если у нас больше наблюдений, чем переменных, X не имеет обратного значения, следовательно, вычисление ниже невозможно:

Вместо этого попробуем найти некоторое β̂ , решающее уравнение неидеально, но с минимально возможной ошибкой. Один из способов— минимизировать следующую целевую функцию, являющуюся функцией от β̂ .

Минимизация этой суммы квадратов отклонений и дает имя задаче наименьших квадратов . Взятие производных по β̂ и приравнивание к нулю приведут к нормальным уравнениям и предоставят решение в замкнутой форме.

Это один из способов. Но можно использовать линейную алгебру. И вот здесь QR-разложение подойдет как нельзя лучше.

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

Для начала давайте опишем это разложение. QR -разложение позволяет отобразить матрицу как произведение двух отдельных матриц Q и R .

Многие сложные матричные операции не могут быть решены эффективно или со стабильностью, используя ограниченную точность компьютеров.

Матричные декомпозиции - это методы, которые сокращают матрицу на составные части, что облегчает вычисление более сложных матричных операций. Методы матричной декомпозиции, также называемые методами матричной факторизации, являются основой линейной алгебры в компьютерах, даже для базовых операций, таких как решение систем линейных уравнений, вычисление обратного и вычисление определителя матрицы.

В этом уроке вы узнаете о разложении матриц и о том, как их вычислять в Python.

После завершения этого урока вы узнаете:

Что такое матричная декомпозиция и почему эти типы операций важны.
Как рассчитать LU и QR матричные разложения в Python.
Как рассчитать разложение матрицы Холецкого в Python.

Обновление март / 2018: Исправлена небольшая опечатка в описании QR-разложения.

Обзор учебника

Этот урок разделен на 4 части; они есть:

Что такое матричная декомпозиция?
LU Matrix Разложение
Разложение QR-матрицы
Холесский Разложение

Что такое матричная декомпозиция?

Разложение матрицы - это способ разложения матрицы на составные части.

Это подход, который может упростить более сложные матричные операции, которые могут быть выполнены на разложенной матрице, а не на самой исходной матрице.

Распространенной аналогией для разложения матриц является разложение чисел, такое как разложение 10 на 2 x 5. По этой причине разложение матриц также называется разложением матриц. Подобно факторизации реальных значений, существует много способов разложения матрицы, поэтому существует целый ряд различных методов разложения матрицы.

Два простых и широко используемых метода декомпозиции матрицы - это декомпозиция матрицы LU и декомпозиция матрицы QR.

Далее мы подробнее рассмотрим каждый из этих методов.

LU Matrix Разложение

Разложение LU предназначено для квадратных матриц и разбивает матрицу на компоненты L и U.

Или без точечной записи.

Где A - квадратная матрица, которую мы хотим разложить, L - матрица нижнего треугольника, а U - матрица верхнего треугольника.

Факторы L и U являются треугольными матрицами. Факторизация, возникающая в результате исключения, равна A = LU.

Разложение LU найдено с помощью итерационного числового процесса и может дать сбой для тех матриц, которые не могут быть легко разложены или разложены.

Вариант этого разложения, который численно более устойчив для решения на практике, называется разложением LUP, или разложением LU с частичным поворотом.

Строки родительской матрицы переупорядочены, чтобы упростить процесс декомпозиции, а дополнительная P-матрица указывает способ перестановки результата или возврата результата в исходный порядок. Есть и другие варианты LU.

Разложение LU часто используется для упрощения решения систем линейных уравнений, например, для нахождения коэффициентов в линейной регрессии, а также для вычисления детерминанта и обратной матрицы.

Декомпозиция LU может быть реализована в Python с помощью функции lu (). Более конкретно, эта функция вычисляет разложение LPU.

В приведенном ниже примере сначала определяется квадратная матрица 3 × 3. Рассчитывается разложение LU, а затем исходная матрица восстанавливается по компонентам.

При выполнении примера сначала печатается определенная матрица 3 × 3, затем компоненты разложения P, L и U, а затем, наконец, восстанавливается исходная матрица.

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

QR-разложение предназначено для m x n матриц (не ограничено квадратными матрицами) и разбивает матрицу на Q и R компоненты.

Или без точечной записи.

Где A - матрица, которую мы хотим разложить, Q - матрица с размером m x m, а R - верхняя треугольная матрица с размером m x n.

QR-разложение находится с использованием итерационного численного метода, который может дать сбой для тех матриц, которые невозможно разложить или легко разложить.

Как и LU-разложение, QR-разложение часто используется для решения систем линейных уравнений, хотя не ограничивается квадратными матрицами.

QR-разложение может быть реализовано в NumPy с помощью функции qr (). По умолчанию функция возвращает матрицы Q и R с меньшими или «уменьшенными» размерами, что является более экономичным. Мы можем изменить это, чтобы вернуть ожидаемые размеры m x m для Q и m x n для R, указав аргумент mode как «complete», хотя это не требуется для большинства приложений.

В приведенном ниже примере определяется матрица 3 × 2, вычисляется QR-разложение, а затем восстанавливается исходная матрица из разложенных элементов.

При выполнении примера сначала печатается определенная матрица 3 × 2, затем элементы Q и R, а затем, наконец, восстановленная матрица, которая соответствует тому, с чего мы начали.

Холесский Разложение

Разложение Холецкого предназначено для квадратных симметричных матриц, где все значения больше нуля, так называемых положительно определенных матриц.

Что касается наших интересов в машинном обучении, мы сосредоточимся на разложении Холецкого для вещественных матриц и проигнорируем случаи при работе с комплексными числами.

Разложение определяется следующим образом:

Или без точечной записи:

Где A - разлагаемая матрица, L - нижняя треугольная матрица, а L ^ T - транспонирование L.

Разложение также может быть записано как произведение верхней треугольной матрицы, например:

Где U - верхняя треугольная матрица.

Разложение Холецкого используется для решения линейных наименьших квадратов для линейной регрессии, а также для методов моделирования и оптимизации.

При разложении симметричных матриц разложение Холецкого почти в два раза эффективнее разложения LU и должно быть предпочтительным в этих случаях.

Хотя симметричные положительно определенные матрицы являются довольно особыми, они встречаются довольно часто в некоторых приложениях, поэтому об их специальной факторизации, называемой разложением Холецкого, полезно знать. Когда вы можете использовать его, разложение Холецкого примерно в два раза быстрее, чем альтернативные методы решения линейных уравнений.

Разложение Cholesky может быть реализовано в NumPy путем вызова функции cholesky (). Функция возвращает только L, так как мы можем легко получить доступ к транспонированию L по мере необходимости.

Приведенный ниже пример определяет симметричную и положительно определенную матрицу 3 × 3 и вычисляет разложение Холецкого, после чего восстанавливается исходная матрица.

При выполнении примера сначала печатается симметричная матрица, затем нижняя треугольная матрица из разложения, за которым следует восстановленная матрица.

расширения

В этом разделе перечислены некоторые идеи по расширению учебника, которые вы, возможно, захотите изучить.

Создайте 5 примеров, используя каждую операцию со своими собственными данными.
Найдите документы по машинному обучению и найдите 1 пример каждой используемой операции.

Если вы исследуете какое-либо из этих расширений, я хотел бы знать.

Дальнейшее чтение

Этот раздел предоставляет больше ресурсов по теме, если вы хотите углубиться.

книги

Раздел 6.6 Матричные разложения.Руководство по линейной алгебре, 2017
Лекция 7 QR Факторизация,Численная линейная алгебра, 1997.
Раздел 2.3. Разложение ЛУ и его применения,Числовые рецепты: искусство научных вычислений, третье издание, 2007.
Раздел 2.10 QR-разложение,Численные рецепты: искусство научных вычисленийТретье издание, 2007.
Раздел 2.9 Разложение Холецкого,Численные рецепты: искусство научных вычисленийТретье издание, 2007.
Лекция 23, Разложение Холецкого,Численная линейная алгебра, 1997.

статьи

Резюме

В этом уроке вы обнаружили матричные декомпозиции и способы их вычисления в Python.

В частности, вы узнали:

Что такое матричная декомпозиция и почему эти типы операций важны.
Как рассчитать LU и QR матричные разложения в Python.
Как рассчитать разложение матрицы Холецкого в Python.

У вас есть вопросы?
Задайте свои вопросы в комментариях ниже, и я сделаю все возможное, чтобы ответить.

В линейной алгебры , A QR - разложение , также известный как QR - разложения или QU факторизации , является разложение из матрицы A в произведение A = QR в качестве ортогональной матрицы Q и верхней треугольной матрицы R . QR - разложение часто используется для решения линейной наименьших квадратов проблемы и является основой для конкретного собственного значения алгоритма , в QR алгоритма .

СОДЕРЖАНИЕ

Случаи и определения

Квадратная матрица

Любая вещественная квадратная матрица A может быть разложена как

А знак равно Q р ,

где Q - ортогональная матрица (ее столбцы означают ортогональные единичные векторы ), а R - верхнетреугольная матрица (также называемая правотреугольной матрицей). Если является обратимым , то разложение единственно , если мы требуем диагональные элементы R , чтобы быть положительным. Q Т знак равно Q - 1 > = Q ^ >

Если вместо этого A - комплексная квадратная матрица, то существует разложение A = QR, где Q - унитарная матрица (так ). Q * знак равно Q - 1 = Q ^ >

Если имеют п линейно независимые столбцы, то первый п столбцы Q образует ортогональный базис для столбца пространства из A . В более общем смысле, первые k столбцов Q образуют ортонормированный базис для диапазона первых k столбцов A для любого 1 ≤ k ≤ n . Тот факт , что любой столбец к из А зависит только от первых K столбцов Q отвечает за треугольную форму R .

Прямоугольная матрица

Голуб и Ван займа (1996 , §5.2) вызова Q ₁ R ₁ тонкий QR - разложение в A ; Трефетен и Бау называют это сокращенной QR-факторизацией . Если A имеет полный ранг n и мы требуем, чтобы диагональные элементы R ₁ были положительными, то R ₁ и Q ₁ уникальны, но в общем случае Q ₂ - нет. R ₁ при этом равна верхней треугольной фактор разложения Холецкого из A * A (= A T A , если реальна).

QL, RQ и LQ разложения

Аналогичным образом мы можем определить разложения QL, RQ и LQ, где L является нижней треугольной матрицей.

Вычисление QR-разложения

Использование процесса Грама – Шмидта

Теперь мы можем выразить s по нашему недавно вычисленному ортонормированному базису: а я _ >

А знак равно Q р

Пример

Затем мы можем вычислить с помощью Грама – Шмидта следующим образом: Q

Таким образом, мы имеем

Связь с разложением RQ

RQ разложение преобразование матрица в произведение верхней треугольной матрицы R (также известная как правая треугольная форма) и ортогональной матрице Q . Единственное отличие от QR-разложения - это порядок этих матриц.

QR-разложение - это ортогонализация по Граму – Шмидту столбцов матрицы A , начиная с первого столбца.

Разложение RQ - это ортогонализация по Граму – Шмидту строк матрицы A , начинающаяся с последней строки.

Преимущества и недостатки

Процесс Грама-Шмидта по своей природе численно нестабилен. Хотя применение проекций имеет привлекательную геометрическую аналогию с ортогонализацией, сама ортогонализация подвержена числовым ошибкам. Однако существенным преимуществом является простота реализации, что делает этот алгоритм полезным для использования при создании прототипов, если заранее созданная библиотека линейной алгебры недоступна.

Использование отражений Хаусхолдера

Отражение Хаусхолдера для QR-разложения: цель состоит в том, чтобы найти линейное преобразование, которое изменяет вектор в вектор той же длины, который коллинеарен . Мы могли бы использовать ортогональную проекцию (Грама-Шмидта), но она будет численно нестабильной, если векторы и близки к ортогональным. Вместо этого отражение Хаусхолдера отражается через пунктирную линию (выбранную, чтобы разделить угол между и ). Максимальный угол с этим преобразованием составляет 45 градусов. Икс > е 1 _ > Икс > е 1 _ > Икс > е 1 _ >

Хаусхолдера отражения (или Хаусхолдер преобразование ) является преобразованием , который принимает вектор и отражает его о некоторой плоскости или гиперплоскости . Мы можем использовать эту операцию для вычисления QR- факторизации матрицы размером m на n с m ≥ n . А

Q может использоваться для отражения вектора таким образом, что все координаты, кроме одной, исчезают.

Позвольте быть произвольным вещественным m -мерным вектор-столбцом такой, что для скаляра α . Если алгоритм реализован с использованием арифметики с плавающей точкой , то α должен получить противоположный знак как к -й координате , где должна быть стержень координат , после которого все записи равны 0 в матрице А ' с окончательной верхней треугольной формой, избегайте потери значимости . В сложном случае установите Икс > А ‖ Икс ‖ знак равно | α | \ | = | \ альфа |> Икс > Икс k >

( Stoer & Bulirsch 2002 , p. 225) и заменим транспонирование сопряженным транспонированием при построении Q ниже.

Тогда где - вектор [1 0 ⋯ 0] T , || · || является евклидова нормы и является м × м единичной матрицы, набор е 1 _ > я

Или, если комплекс А

Это можно использовать для постепенного преобразования матрицы A размером m на n к верхнетреугольной форме. Сначала мы умножаем A на матрицу Хаусхолдера Q _1, которую получаем, когда выбираем первый столбец матрицы для x . В результате получается матрица Q ₁ A с нулями в левом столбце (кроме первой строки).

Это можно повторить для A '(полученного из Q ₁ A путем удаления первой строки и первого столбца), в результате чего получится матрица Хаусхолдера Q ' ₂ . Обратите внимание, что Q ' ₂ меньше, чем Q ₁ . Поскольку мы хотим, чтобы он действительно работал с Q ₁ A вместо A ', нам нужно развернуть его в левый верхний угол, заполнив 1, или в целом:

- верхнетреугольная матрица. Итак, с

Этот метод имеет большую числовую устойчивость, чем метод Грама – Шмидта, описанный выше.

В следующей таблице показано количество операций на k -м шаге QR-разложения с помощью преобразования Хаусхолдера, предполагая квадратную матрицу с размером n .

Операция	Количество операций на k -м шаге
Умножения	2 ( п - k + 1 ) 2 >
Дополнения	( п - k + 1 ) 2 + ( п - k + 1 ) ( п - k ) + 2 + (п-к + 1) (пк) +2>
Разделение	1
Квадратный корень	1

Суммируя эти числа за n - 1 шаг (для квадратной матрицы размера n ), сложность алгоритма (в терминах умножения с плавающей запятой) определяется как

Читайте также: