Введение
Наиболее широко известная обобщённая обратная матрица
В математике, и в частности в линейной алгебре, обратная Мура — Пенроуза A⁺ матрицы A, часто называемая псевдообратной, является наиболее широко известным обобщением обратной матрицы. Она была независимо описана Э. Х. Муром в 1920 году, Арне Бьерхаммаром в 1951 году и Роджером Пенроузом в 1955 году. Ранее Эрик Ивар Фредхольм ввёл концепцию псевдообратной интегральных операторов в 1903 году. Термины «псевдообратная» и «обобщённый инверс» иногда используются как синонимы к обратной Мура — Пенроуза матрицы, но иногда применяются к другим элементам алгебраических структур, которые обладают некоторыми, но не всеми свойствами, ожидаемыми от обратного элемента. Распространённое применение псевдообратной — вычисление «наилучшего приближения» (метода наименьших квадратов) для решения системы линейных уравнений, не имеющей точного решения (см. ниже в разделе § Приложения). Другое применение — нахождение решения с минимальной (евклидовой) нормой для системы линейных уравнений, имеющей несколько решений. Псевдообратная облегчает формулировку и доказательство теорем в линейной алгебре. Псевдообратная определена и единственна для всех матриц, элементы которых являются действительными или комплексными числами. Её можно вычислить с помощью сингулярного разложения. В частном случае, когда A является нормальной матрицей (например, эрмитовой матрицей), псевдообратная A⁺ аннулирует ядро A и действует как обычная обратная к A на подпространстве, ортогональном ядру.
In mathematics, and in particular linear algebra, the Moore–Penrose inverse A^+ of a matrix A , often called the pseudoinverse, is the most widely known generalization of the inverse matrix. It was independently described by E. H. Moore in 1920, Arne Bjerhammar in 1951, and Roger Penrose in 1955. Earlier, Erik Ivar Fredholm had introduced the concept of a pseudoinverse of integral operators in 1903. The terms pseudoinverse and generalized inverse are sometimes used as synonyms for the Moore–Penrose inverse of a matrix, but sometimes applied to other elements of algebraic structures which share some but not all properties expected for an inverse element. A common use of the pseudoinverse is to compute a "best fit" (least squares) approximate solution to a system of linear equations that lacks an exact solution (see below under § Applications). Another use is to find the minimum (Euclidean) norm solution to a system of linear equations with multiple solutions. The pseudoinverse facilitates the statement and proof of results in linear algebra. The pseudoinverse is defined and unique for all matrices whose entries are real or complex numbers. It can be computed using the singular value decomposition. In the special case where A is a normal matrix (for example, a Hermitian matrix), the pseudoinverse A^+ annihilates the kernel of A and acts as a traditional inverse of A on the subspace orthogonal to the kernel.
Обозначение
В дальнейшем обсуждении используются следующие обозначения. \mathbb{K} будет обозначать одно из полей вещественных или комплексных чисел, обозначаемых соответственно \mathbb{R} и \mathbb{C}. Векторное пространство матриц размера m \times n над \mathbb{K} обозначается как \mathbb{K}^{m \times n}. Для A \in \mathbb{K}^{m\times n}, транспонирование обозначается как A^\operatorname{T}, а эрмитово-транспонирование (также называемое сопряжённым транспонированием) обозначается как A^*. Если , то для A \in \mathbb{K}^{m\times n}, \operatorname{ran}(A) (обозначающее "область значений") обозначает пространство, порожденное столбцами A (образ A), а \ker(A) обозначает ядро (нулевое пространство) A. Для любого положительного целого числа n, единичная матрица размера n \times n обозначается как I_n \in \mathbb{K}^{n\times n}.
Геометрическая конструкция
Если мы рассматриваем матрицу как линейное отображение A: \mathbb{K}^n \to \mathbb{K}^m над полем \mathbb{K}, то A^+: \mathbb{K}^m \to \mathbb{K}^n можно разложить следующим образом. Мы используем обозначение \oplus для прямой суммы, \perp для ортогонального дополнения, \ker для ядра отображения, и \operatorname{ran} для образа отображения. Заметим, что и ограничение является тогда изоморфизмом. Это означает, что A^+ на \operatorname{ran} A является обратным к этому изоморфизму и равно нулю на .
Другими словами: чтобы найти A^+b для заданного b из \mathbb{K}^m, сначала ортогонально спроецируйте b на образ A, получив точку p(b) в этом образе. Затем найдите A^{-1}(\{p(b)\}), то есть векторы в \mathbb{K}^n, которые A отображает в p(b). Это будет аффинное подпространство \mathbb{K}^n, параллельное ядру A. Элемент этого подпространства с наименьшей длиной (то есть ближайший к началу координат) и есть искомое A^+b. Его можно найти, взяв произвольный элемент из A^{-1}(\{p(b)\}) и ортогонально спроецировав его на ортогональное дополнение ядра A. Это описание тесно связано с решением линейной системы с минимальной нормой.
This description is closely related to the minimum norm solution to a linear system.
Скалярные
Также можно определить псевдообратную матрицу для скаляров и векторов. Это достигается путем рассмотрения их как матриц. Псевдообратная матрица скаляра x равна нулю, если x равен нулю, и 1/x в противном случае.
Векторы
Псевдоинверс нулевого (состоящего из всех нулей) вектора равен транспонированному нулевому вектору. Псевдоинверс ненулевого вектора равен комплексно сопряжённому транспонированному вектору, делённому на квадрат его длины.
Диагональные матрицы
Псевдоинверс квадратной диагональной матрицы получается путем взятия обратных величин для ненулевых элементов диагонали. Формально, если – квадратная диагональная матрица с и , то В более общем случае, если – любая прямоугольная матрица, у которой ненулевые элементы находятся только на диагонали, то есть , , то – прямоугольная матрица, диагональные элементы которой являются обратными величинами соответствующих элементов исходной матрицы, то есть .
Линейно независимые столбцы
Если ранг матрицы A совпадает с её рангом по столбцам, n (при n ≤ m), то существует n линейно независимых столбцов, и матрица A*A обратима. В этом случае явная формула имеет вид:
Следовательно, A⁺ является левым обратным для A: .
Линейно независимые строки
Если ранг матрицы A совпадает с ее строчным рангом m (при m ≤ n), то существует m линейно независимых строк, и матрица AA* обратима. В этом случае явная формула имеет вид:
Следовательно, A⁺ является правообратной матрицей для A: .
Обычные столбцы или строки
Это частный случай либо полного столбцового ранга, либо полного строкового ранга (рассмотренного выше). Если матрица A имеет ортонормальные столбцы или ортонормальные строки, то:
Нормальные матрицы
Если матрица A нормальна, то есть коммутирует со своей сопряжённой транспонированной, то её псевдообратную можно вычислить, диагонализовав её, отображая все ненулевые собственные значения на их обратные величины, а нулевые собственные значения – на ноль. Следствием этого является то, что если A коммутирует со своей транспонированной, то она коммутирует и со своей псевдообратной.
Матрицы EP
Квадратная матрица A называется EP-матрицей, если она коммутирует со своей псевдообратной. В таких (и только таких) случаях псевдообратную можно представить в виде полинома от A. Полином, удовлетворяющий этому условию, можно легко получить из характеристического полинома матрицы A или, в более общем случае, из любого аннигилирующего полинома матрицы A.
Матрицы ортогональной проекции
Это особый случай нормальной матрицы с собственными значениями 0 и 1. Если A является матрицей ортогональной проекции, то есть A² = A и A = A*, то псевдообратная матрица тривиально совпадает с самой собой:
Матрицы циркуляции
Для циркулирующей матрицы C сингулярное разложение задается преобразованием Фурье, то есть сингулярные значения являются коэффициентами Фурье. Пусть \mathcal{F} будет матрицей дискретного преобразования Фурье (DFT); тогда
Распад рангов
Пусть r \le \min(m, n) обозначает ранг матрицы A \in \mathbb{K}^{m\times n}. Тогда матрицу A можно разложить на произведение матриц ранга r следующим образом: A = BC, где B \in \mathbb{K}^{m\times r} и C \in \mathbb{K}^{r\times n} имеют ранг r.
where B \in \mathbb{K}^{m\times r} and C \in \mathbb{K}^{r\times n} are of rank r Then .
Метод QR
Для вычисления произведения A A^* или A^*A и их обратных матриц часто является источником ошибок округления и высоких вычислительных затрат на практике. Вместо этого можно использовать альтернативный подход, основанный на QR-разложении матрицы A. Рассмотрим случай, когда матрица A имеет полный столбцовый ранг, то есть Тогда можно использовать разложение Чолеского, где R – верхнетреугольная матрица. Умножение на обратную матрицу затем легко выполняется путем решения системы линейных уравнений с несколькими правыми частями, которую можно решить методом прямой подстановки с последующей обратной подстановкой. Разложение Чолеского можно вычислить без явного формирования матрицы A^*A, альтернативно используя QR-разложение матрицы , где имеет ортонормальные столбцы, , а R – верхнетреугольная матрица. Тогда R является фактором Чолеского для A^*A. Случай полного строкового ранга рассматривается аналогично, используя формулу и аналогичный аргумент, меняя местами роли A и A^*.
which may be solved by forward substitution followed by back substitution. The Cholesky decomposition may be computed without forming A^*A explicitly, by alternatively using the QR decomposition of , where has orthonormal columns, , and R is upper triangular. Then
so R is the Cholesky factor of A^*A
The case of full row rank is treated similarly by using the formula and using a similar argument, swapping the roles of A and A^* .
Использование многочленов в матрицах
Для произвольного A \in \mathbb{K}^{m\times n} , матрица является нормальной и, как следствие, EP-матрицей. Можно найти такой многочлен, что в этом случае псевдоинверс A задается как Если является сингулярным разложением A, то для прямоугольной диагональной матрицы, такой как \Sigma, псевдоинверс получается, беря обратную величину каждого ненулевого элемента на диагонали, оставляя нули на месте, и затем транспонируя матрицу. В численных вычислениях только элементы, превышающие некоторую небольшую погрешность, считаются ненулевыми, а остальные заменяются нулями. Например, в функции MATLAB или GNU Octave , погрешность принимается равной 1=t = ε⋅max(m, n)⋅max(Σ), где ε – машинный эпсилон. Вычислительная стоимость этого метода определяется стоимостью вычисления сингулярного разложения, которая в несколько раз выше, чем умножение матриц, даже при использовании современной реализации (например, LAPACK). Описанная выше процедура показывает, почему вычисление псевдоинверса не является непрерывной операцией: если исходная матрица A имеет сингулярное значение 0 (соответствующий диагональный элемент матрицы \Sigma), то небольшое изменение A может превратить этот ноль в очень маленькое положительное число, тем самым существенно влияя на псевдоинверс, поскольку теперь необходимо брать обратную величину очень маленького числа.
Блоковые матрицы
Существуют оптимизированные подходы для вычисления псевдообратной блочно-структурированной матрицы.
Итеративный метод Бен-Исраэля и Коэна
Другой метод вычисления псевдоинверса (см. обращение Дразина) использует рекурсию, которую иногда называют последовательностью гиперстепеней. Эта рекурсия порождает последовательность, сходящуюся квадратично к псевдоинверсу A, если она начинается с подходящего A₀, удовлетворяющего условию . Выбор (где , а σ₁(A) обозначает наибольшее сингулярное значение A) был признан неконкурентоспособным по сравнению с методом, использующим сингулярное разложение, упомянутым выше, поскольку даже для умеренно плохо обусловленных матриц требуется значительное время, прежде чем Aᵢ войдет в область квадратичной сходимости. Однако, если начать с A₀, уже близкого к обращению Мура — Пенроуза, и, например, сходимость будет быстрой (квадратичной).
which is sometimes referred to as hyper power sequence. This recursion produces a sequence converging quadratically to the pseudoinverse of A if it is started with an appropriate A 0 satisfying The choice (where , with \sigma 1(A) denoting the largest singular value of A ) has been argued not to be competitive to the method using the SVD mentioned above, because even for moderately ill conditioned matrices it takes a long time before A i enters the region of quadratic convergence. However, if started with A 0 already close to the Moore–Penrose inverse and , for example , convergence is fast (quadratic).
Обновление псевдоинверса
В тех случаях, когда матрица A имеет полный ранг по строкам или столбцам, и обратная корреляционной матрицы (A A* для A с полным рангом по строкам или A*A для A с полным рангом по столбцам) уже известна, псевдообратная для матриц, связанных с A, может быть вычислена с помощью формулы Шермана — Моррисона — Вудбери для обновления обратной корреляционной матрицы, что может потребовать меньше вычислений. В частности, если связанная матрица отличается от исходной только измененной, добавленной или удаленной строкой или столбцом, существуют инкрементные алгоритмы, использующие эту связь. Аналогично, возможно обновление фактора Холецкого при добавлении строки или столбца без явного вычисления обратной корреляционной матрицы. Однако обновление псевдообратной в общем случае, когда ранг матрицы недостаточен, значительно сложнее.
Библиотеки программного обеспечения
Высококачественные реализации SVD, QR и обратной подстановки доступны в стандартных библиотеках, таких как LAPACK. Написание собственной реализации SVD – это масштабный проект программирования, требующий значительной численной экспертизы. Однако, в особых случаях, таких как параллельные или встраиваемые вычисления, альтернативные реализации с использованием QR или даже явного обращения матрицы могут быть предпочтительнее, и создание пользовательских реализаций может оказаться неизбежным. Пакет Python NumPy предоставляет вычисление псевдообратной матрицы через функции `matrix.I` и `linalg.pinv`; его `pinv` использует алгоритм, основанный на SVD. SciPy добавляет функцию `scipy.linalg.pinv`, использующую решатель задачи наименьших квадратов. Пакет MASS для R предоставляет вычисление обобщённой инверсии Мура — Пенроуза через функцию `ginv`. Функция `ginv` вычисляет псевдообратную матрицу, используя сингулярное разложение, предоставляемое функцией `svd` из базового пакета R. Альтернативой является использование функции `pinv`, доступной в пакете `pracma`. Язык программирования Octave предоставляет псевдообратную матрицу через стандартную пакетную функцию `pinv` и метод псевдообращения. В Julia (язык программирования) пакет `LinearAlgebra` стандартной библиотеки предоставляет реализацию обобщённой инверсии Мура — Пенроуза `pinv`, реализованную посредством сингулярного разложения.