Каков модуль матрицы qr
Обновлено: 05.07.2024
На этой странице представлены некоторые разделы линейной алгебры, необходимые для построения решений систем линейных алгебраических уравнений и некоторых приложений. Мы используем матрицы и векторы как важные элементы для получения и выражения решений.
QR-разложение ¶
Разложение QR выражает матрицу как произведение ортогональной матрицы и верхней треугольной матрицы. Буква Q заменяет букву O из слова "ортогональный", а буква R - из слова "справа", альтернативу слову "верхний".
Предположим, что A представляет собой матрицу \( m \times n \) с линейно независимыми столбцами (полный ранг столбца), а Q является матрицей, полученной в результате применения процесса Грама--Шмидта к векторам-столбцам матрицы A. Тогда A можно рассматривать как
\[ = \, = \left[ _1 \ _2 \ \cdots \ _n \right] \begin R_ & R_ & \cdots & R_ \\ 0& R_ & \cdots & R_ \\ \vdots & \vdots & \ddots & \vdots \\ 0&0& \cdots & R_ \end , \]
где Q — матрица \( m \times n \) с ортонормированными векторами-столбцами ( \( \| _i \| =1, \quad \mbox \quad ^<\mathrm T>_i _j =0 \), если \( i \ne j \) ), а R является \( n \times n \) обратимой верхней треугольной матрицей. Эта факторизация уникальна, если мы требуем, чтобы диагональные элементы R были положительными. Если \( R_ мы можем поменять местами знаки \( R_ , \ldots , R_ , \) и вектора \( _ \) сделать диагональный член \( R_ \) положительным.
В приведенном выше определении \( ^ <\mathrm T> = ; \) Если A — квадратная матрица, то Q ортогонален: \( ^ <\mathrm T> = ^ <\mathrm T>= . \ ) Если вместо этого A представляет собой комплексную квадратную матрицу, то существует разложение \( \, = , \), где Q является унитарной матрицей (так что \( ^ = \) ).
Существует несколько методов фактического вычисления QR-разложения, например, с помощью процесса Грама--Шмидта ( \( 2mn^2 \) провалы, чувствительные к ошибкам округления), преобразования Хаусхолдера ( \( 2mn^2 - (2/3) n^3 \) флопов), или вращений Гивенса. Каждый из них имеет ряд преимуществ и недостатков.
Пример. Вот пример декомпозиции QR:
Напомним, что матрица имеет полный ранг строки, когда каждая из строк матрицы линейно независима, и полный ранг столбца, когда каждый из столбцов матрицы линейно независим. Используя QR-разложение для матрицы полного ранга столбца A, мы можем выразить ее псевдообратную форму через матрицы Q и R:
Для квадратного неособого A это обратное: \( ^ = \left( \, \right)^ = ^ ^ <\mathrm T>. \)
Подчеркнем главное свойство QR-разложения: Q имеет тот же диапазон, что и A.
Спектральное разложение
Одной из особенностей Sage является то, что мы можем легко расширять его возможности, определяя новые команды. Здесь будет создана функция, которая проверяет, представляет ли расширенная матрица непротиворечивую систему уравнений. Синтаксис просто немного сложен. lambda — это слово, указывающее на то, что мы создаем новую функцию, входные данные временно называются A (представьте, что A дополнено), а имя функции непротиворечиво. Все, что следует за двоеточием, будет оценено и сообщено как результат.
Выполнить этот блок выше. Выхода не будет, но теперь согласованная функция будет определена и доступна. Теперь попробуйте (убедившись, что вы запустили приведенный выше код, определяющий aug). Учтите, что на выходе constable() будет либо True, либо False.
Команда последовательного() работает, просто проверяя, нет ли последнего столбца A в списке сводных данных. Теперь мы можем протестировать множество различных расширенных матриц, например, изменить вектор констант, сохранив фиксированную матрицу коэффициентов. Опять же, убедитесь, что вы выполнили приведенный выше код, определяющий coeff и const.
Почему некоторые векторы констант приводят к непротиворечивой системе с этой матрицей коэффициентов, а другие нет? Это фундаментальный вопрос, который мы будем понимать по-разному.
На этой странице представлены некоторые разделы линейной алгебры, необходимые для построения решений систем линейных алгебраических уравнений и некоторых приложений. Мы используем матрицы и векторы как важные элементы для получения и выражения решений.
QR-разложение ¶
Разложение QR выражает матрицу как произведение ортогональной матрицы и верхней треугольной матрицы. Буква Q заменяет букву O из слова "ортогональный", а буква R - из слова "справа", альтернативу слову "верхний".
Предположим, что A представляет собой матрицу \( m \times n \) с линейно независимыми столбцами (полный ранг столбца), а Q является матрицей, полученной в результате применения процесса Грама--Шмидта к векторам-столбцам матрицы A. Тогда A можно рассматривать как
\[ = \, = \left[ _1 \ _2 \ \cdots \ _n \right] \begin R_ & R_ & \cdots & R_ \\ 0& R_ & \cdots & R_ \\ \vdots & \vdots & \ddots & \vdots \\ 0&0& \cdots & R_ \end , \]
где Q — матрица \( m \times n \) с ортонормированными векторами-столбцами ( \( \| _i \| =1, \quad \mbox \quad ^<\mathrm T>_i _j =0 \), если \( i \ne j \) ), а R является \( n \times n \) обратимой верхней треугольной матрицей. Эта факторизация уникальна, если мы требуем, чтобы диагональные элементы R были положительными. Если \( R_ мы можем поменять местами знаки \( R_ , \ldots , R_ , \) и вектора \( _ \) сделать диагональный член \( R_ \) положительным.
В приведенном выше определении \( ^ <\mathrm T> = ; \) Если A — квадратная матрица, то Q ортогонален: \( ^ <\mathrm T> = ^ <\mathrm T>= . \ ) Если вместо этого A представляет собой комплексную квадратную матрицу, то существует разложение \( \, = , \), где Q является унитарной матрицей (так что \( ^ = \) ).
Существует несколько методов фактического вычисления QR-разложения, например, с помощью процесса Грама--Шмидта ( \( 2mn^2 \) провалы, чувствительные к ошибкам округления), преобразования Хаусхолдера ( \( 2mn^2 - (2/3) n^3 \) флопов), или вращений Гивенса. Каждый из них имеет ряд преимуществ и недостатков.
Пример. Вот пример декомпозиции QR:
Напомним, что матрица имеет полный ранг строки, когда каждая из строк матрицы линейно независима, и полный ранг столбца, когда каждый из столбцов матрицы линейно независим. Используя QR-разложение для матрицы полного ранга столбца A, мы можем выразить ее псевдообратную форму через матрицы Q и R:
Для квадратного неособого A это обратное: \( ^ = \left( \, \right)^ = ^ ^ <\mathrm T>. \)
Подчеркнем главное свойство QR-разложения: Q имеет тот же диапазон, что и A.
Спектральное разложение
Одной из особенностей Sage является то, что мы можем легко расширять его возможности, определяя новые команды. Здесь будет создана функция, которая проверяет, представляет ли расширенная матрица непротиворечивую систему уравнений. Синтаксис просто немного сложен. lambda — это слово, указывающее на то, что мы создаем новую функцию, входные данные временно называются A (представьте, что A дополнено), а имя функции непротиворечиво. Все, что следует за двоеточием, будет оценено и сообщено как результат.
Выполнить этот блок выше. Выхода не будет, но теперь согласованная функция будет определена и доступна. Теперь попробуйте (убедившись, что вы запустили приведенный выше код, определяющий aug). Учтите, что на выходе constable() будет либо True, либо False.
Команда последовательного() работает, просто проверяя, нет ли последнего столбца A в списке сводных данных. Теперь мы можем протестировать множество различных расширенных матриц, например, изменить вектор констант, сохранив фиксированную матрицу коэффициентов. Опять же, убедитесь, что вы выполнили приведенный выше код, определяющий coeff и const.
Почему некоторые векторы констант приводят к непротиворечивой системе с этой матрицей коэффициентов, а другие нет? Это фундаментальный вопрос, который мы будем понимать по-разному.
QR-разложение (факторизация) — это разложение матрицы на ортогональную (Q) и верхнетреугольную (R) матрицы. QR-факторизация используется при решении линейных задач наименьших квадратов и поиске собственных значений. В этом посте показано, как вычисляется QR-разложение и как его использовать для решения практических задач.
Процесс Грама-Шмидта
QR-разложение имеет следующую формулу:
- A — исходная матрица, которую мы хотим разложить
- Q — ортогональная матрица
- R — верхняя треугольная матрица.
Основная цель довольно проста, разложить матрицу на матрицы Q и R. Чтобы найти ортогональную матрицу Q, мы могли бы использовать процесс Грама-Шмидта. Этот процесс берет входную матрицу и делает столбцы ортогональными (перпендикулярными друг другу). На следующем графике мы превращаем векторы a и b в ортогональные векторы v1 и v2.
Для создания ортогональных векторов мы могли бы использовать следующую информацию. Вектор a является первым вектором, и мы можем сопоставить его с v1. v2 должен быть ортогонален вектору v1, поэтому мы должны спроецировать вектор b на v2, чтобы сделать b ортогоналом a (v1). Проекция вектора b на a (v1) определяется как:
Имеющаяся у нас информация представлена на следующем графике:
Теперь нам нужно спроецировать b на v2, чтобы получить ортогональность между a и b. Для этого мы могли бы использовать e, которая является ошибкой нашего прогноза и может быть рассчитана по следующей формуле:
Обратите внимание, что e имеет ту же длину и то же направление, что и v2. Мы можем сделать вывод:
В основном так работает процесс Грама-Шмидта. Для более чем двух измерений (предположим, что у нас есть векторы a, b и c) мы могли бы рассчитать процесс следующим образом (источник):
Что происходит в большем количестве измерений, так это то, что мы вычитаем направления вектора из предыдущих компонентов (v1, v2 и т. д., если у нас больше измерений). Теперь мы знаем, как получить матрицу Q.
Для вычисления матрицы R мы можем использовать следующие изменения в формуле QR:
QᵗA = QᵗQR (поскольку Q ортогонален Qᵗ=inverse(Q))
QᵗA = R, таким образом, R = QᵗA
В Python декомпозиция QR с использованием процесса Грама-Шмидта может быть реализована следующим образом:
Пример использования и вывода:
Как обычно, это не единственный способ расчета QR-разложения. Теперь давайте посмотрим, как использовать отражения Хаусхолдера для QR-разложения.
Размышления домохозяев
Грамм-Шмидт может быть численно нестабильным, а это означает, что небольшие изменения на входе могут привести к относительно большим изменениям на выходе (источник). Более устойчивым способом является использование отражений Хаусхолдера. Проекты домохозяев векторируются через «зеркало». У нас есть вектор x, который мы хотим отразить в векторе Qx. Для отражения мы будем использовать ортогональную матрицу Q.
Из предыдущего мы знаем, что проекция x на u равна:
Из графика отражения Хаусхолдера видно, что если дважды вычесть компонент, параллельный u, из x, мы получим Qx (источник):
QR-разложение
Вам предлагается решить эту задачу в соответствии с описанием задачи, используя любой язык, который вы знаете.
Продемонстрируйте декомпозицию QR на примере матрицы из статьи Википедии:
и использование для линейных задач наименьших квадратов на примере полиномиальной регрессии. Следует использовать метод размышлений Хаусхолдера:
что означает, что все записи, кроме первой, становятся нулевыми. Чтобы избежать числовых ошибок отмены, мы должны взять знак, противоположный 1 > :
и нормализовать по отношению к первому элементу:
или в другой форме
Вот как мы можем, столбец за столбцом, удалить все поддиагональные элементы A > и, таким образом, преобразовать его в R >> .
Затем QR-разложение следует использовать для решения задач линейного метода наименьших квадратов (множественной регрессии) A x = b x=b> путем решения
и то же самое для RHS:
Наконец, решите квадратную верхнюю треугольную систему обратной подстановкой:
Содержание
Ада [ изменить ]
Вывод соответствует решению Matlab, не тестировался с другими матрицами.
Аксиома [править]
Ниже приведено общее QR-разложение для чисел с произвольной точностью, двойных чисел с плавающей запятой и точных вычислений:
Это можно вызвать с помощью:
С выводом в точной форме:
Вычисления сопоставимы с расчетами QR-декомпозиции по умолчанию в R.
BBC BASIC [ изменить ]
Интенсивно используется матричная арифметика BBC BASIC.
C [ изменить ]
С++ [править]
Common Lisp [править]
D [ изменить ]
Фортран [править]
См. документацию по процедурам DGEQRF и DORGQR. Здесь примером матрицы является магический квадрат из Melencolia I Альбрехта Дюрера.
Футарк [править]
Перейти [ изменить ]
Метод описания задачи, библиотека go.matrix [ редактировать ]
Довольно близкий порт решения Common Lisp, это решение использует библиотеку go.matrix для вспомогательных функций. Однако обратите внимание, что go.matrix имеет QR-разложение, как показано в решении Go для полиномиальной регрессии. Решение там закодировано более прямо, чем в примере с CL здесь. Точно так же изучение исходного QR-кода go.matrix показывает, что он вычисляет декомпозицию более точно.
Библиотека QR, гонум/матрица [ редактировать ]
Хаскелл [ изменить ]
Только квадратные матрицы; разложить A и решить Rx = q обратной подстановкой
Разложение QR с помощью Numeric.LinearAlgebra [ редактировать ]
J [ изменить ]
Решение (встроенное): Решение (специальная реализация): Пример: Пример (полиномиальная аппроксимация с использованием QR-редукции):
Notes:J предлагает встроенную функцию декомпозиции QR, 128!:0. Если бы J не предлагал эту функцию как встроенную, ее можно было бы написать на J по образцу второй версии, которая описана в эссе на вики J.
Java [править]
ДЖАМА [ изменить ]
Использование библиотеки JAMA. Скомпилируйте с помощью: javac -cp Jama-1.0.3.jar Decompose.java.
Кольт [ изменить ]
Использование библиотеки Colt. Скомпилируйте с помощью: javac -cp colt.jar Decompose.java.
Математика Apache Commons [править]
Использование математической библиотеки Apache Commons.
Компилировать с помощью: javac -cp commons-math3-3.6.1.jar Decompose.java.
la4j [ изменить ]
Использование библиотеки la4j. Скомпилируйте с помощью: javac -cp la4j-0.6.0.jar Decompose.java.
Юлия [ изменить ]
Клен [ изменить ]
Mathematica/Wolfram Language [ редактировать ]
MATLAB/октава [править]
Максимум [ изменить ]
Ним [ изменить ]
Библиотека arraymancer предоставляет функцию qr для получения QR-разложения. Используя тензорный тип «arraymancer», мы предлагаем здесь реализацию этой декомпозиции, адаптированную из версии Python.
PARI/GP [ изменить ]
Perl [править]
Позволить модулю PDL сделать всю работу.
Исправить [ изменить ]
PowerShell [ изменить ]
Питон [ изменить ]
В Numpy есть функция qr, но здесь представлена ее повторная реализация, показывающая построение и использование отражений Householder.
Читайте также: