Участник:Василий Ломакин/Псевдообратная матрица

Материал из MachineLearning.

< Участник:Василий Ломакин(Различия между версиями)
Перейти к: навигация, поиск
(Новая: '''Псевдообратные матрицы''' — обобощение обратных матриц в математике и, в частности, в линейной алгеб...)
 
Строка 1: Строка 1:
-
'''Псевдообратные матрицы''' — обобощение обратных матриц в математике и, в частности, в линейной алгебре.
+
'''Псевдообратные матрицы''' — обобощение обратных матриц в линейной алгебре.
-
Псевдообратная матрица к матрице <tex>A</tex> обозначается <tex>A^+</tex>. Наиболее известно псевдообращение Мура — Пенроуза, которое было независимо описано Э. Х. Муром и Роджером Пенроузом.
+
Псевдообратная матрица к матрице <tex>A</tex> обозначается <tex>A^+</tex>.
-
Концепцию псевдообратных интегрирующих операторов в 1903 году представил Фредгольм.
+
Псевдообращение можно понимать как наилучшую апроксимацию (по методу наименьших квадратов) решения соответствующей системы линейных уравнений. Псевдообращение определено для любых матриц над действительными и комплексными числами.
-
Термин «обобщенное обращение» иногда используется как синоним для псевдообращения.
+
-
Псевдообращение можно понимать как наилучшую апроксимацию (по методу наименьших квадратов) решения соответствующей системы линейных уравнений (см. далее в применении). Псевдообращение определено для любых матриц над действительными и комплексными числами.
+
Псевдообратная матрица может быть вычислена с помощью собственного представления матрицы.
Псевдообратная матрица может быть вычислена с помощью собственного представления матрицы.
Строка 16: Строка 14:
Здесь <tex>M^*</tex> - эрмитова сопряжённая матрица ''M''. Для матриц над полем действительных чисел <tex>M^* = M^T</tex>.
Здесь <tex>M^*</tex> - эрмитова сопряжённая матрица ''M''. Для матриц над полем действительных чисел <tex>M^* = M^T</tex>.
-
Существует эквивалентный способ задания псевдообратной матрицы через предел обратных:
+
== Происхождение ==
-
:<tex>A^+ = \lim_{\delta \to 0} (A^* A + \delta I)^{-1} A^*
+
 
-
= \lim_{\delta \to 0} A^* (A A^* + \delta I)^{-1}</tex>
+
По методу наименьших квадратов для решения несовместной СЛАУ <tex>A\mathbf{x}=\mathbf{b}</tex>,
-
(смотрите регуляризация Тихонова).
+
состоящей из&nbsp;<tex>M</tex> уравнений с <tex>N</tex> неизвестными, необходимо решить уравнение
-
Этот предел существует, даже если <tex>(A A^*)^{-1}</tex> и <tex>(A^* A)^{-1}</tex> не определены.
+
<center><tex>A^TA\mathbf{x}=A^T\mathbf{b},</tex></center>
 +
называемое <i>нормальным уравнением</i>.
 +
Пусть столбцы матрицы&nbsp;<tex>A</tex> линейно независимы, тогда она обратима и система имеет единственное решение
 +
<center><tex>\mathbf{x}=(A^TA)^{-1}A^T\mathbf{b}.</tex></center>
 +
Таким образом мы приходим к понятию псевдообращения действительных матриц:
 +
<center><tex>A^+=(A^TA)^{-1}A^T.</tex></center>
== Свойства ==
== Свойства ==
* Псевдообращение обратимо, более того, эта операция обратна самой себе:<br> <tex>(A^+)^+ = A </tex>.
* Псевдообращение обратимо, более того, эта операция обратна самой себе:<br> <tex>(A^+)^+ = A </tex>.
-
* Псевдообращение нулевой матрицы равно транспонированию.
+
* Псевдообращение коммутирует с транспонированием, сопряжением и эрмитовым сопряжением: <br> <tex>(A^T)^+ = (A^+)^T</tex>,<br> <tex>(\overline{A})^+ = \overline{A^+} </tex>,<br> <tex>(A^*)^+ = (A^+)^* .</tex>
-
* Псевдообращение комутирует с транспонированием, сопряжением и эрмитовым сопряжением: <br> <tex>(A^T)^+ = (A^+)^T</tex>,<br> <tex>(\overline{A})^+ = \overline{A^+} </tex>,<br> <tex>(A^*)^+ = (A^+)^* .</tex>
+
* Псевдообратное произведения матрицы <tex>A</tex> на скаляр <tex>\alpha</tex> равно соответствующему произведению матрицы <tex>A^+</tex> на обратное число <tex>\alpha^{-1}</tex>:<br> <tex>(\alpha A)^+ = \alpha^{-1} A^+ </tex>, для <tex>\alpha</tex> &ne; 0.
* Псевдообратное произведения матрицы <tex>A</tex> на скаляр <tex>\alpha</tex> равно соответствующему произведению матрицы <tex>A^+</tex> на обратное число <tex>\alpha^{-1}</tex>:<br> <tex>(\alpha A)^+ = \alpha^{-1} A^+ </tex>, для <tex>\alpha</tex> &ne; 0.
* Если псевдообратная матрица для <tex>A^*A</tex> уже известна, она может быть использовано для вычисления <tex>A^+</tex>:<br> <tex>A^+ = (A^*A)^+A^* </tex> .
* Если псевдообратная матрица для <tex>A^*A</tex> уже известна, она может быть использовано для вычисления <tex>A^+</tex>:<br> <tex>A^+ = (A^*A)^+A^* </tex> .
Строка 35: Строка 37:
* Если '''столбцы''' матрицы <tex>A</tex> линейно независимы, тогда матрица <tex>A^* A</tex> обратима. В таком случае псевдообратная матрица задаётся формулой
* Если '''столбцы''' матрицы <tex>A</tex> линейно независимы, тогда матрица <tex>A^* A</tex> обратима. В таком случае псевдообратная матрица задаётся формулой
:<tex>A^+ = (A^* A)^{-1} A^*.</tex>
:<tex>A^+ = (A^* A)^{-1} A^*.</tex>
-
Это эквивалентно тому, что в первой части определения через предел убирается слагаемое с <tex>\delta</tex>.
 
Отсюда следует что <tex>A^+</tex> - левая обратная матрица для ''A'': &nbsp; <tex> A^+ A = I</tex> .
Отсюда следует что <tex>A^+</tex> - левая обратная матрица для ''A'': &nbsp; <tex> A^+ A = I</tex> .
* Если '''строки''' матрицы <tex>A</tex> линейно независимы, тогда матрица <tex>A A^*</tex> обратима. В таком случае псевдообратная матрица задаётся формулой
* Если '''строки''' матрицы <tex>A</tex> линейно независимы, тогда матрица <tex>A A^*</tex> обратима. В таком случае псевдообратная матрица задаётся формулой
:<tex>A^+ = A^*(A A^*)^{-1}.</tex>
:<tex>A^+ = A^*(A A^*)^{-1}.</tex>
-
Это эквивалентно тому, что во второй части определения через предел убирается слагаемое с <tex>\delta</tex>.
 
Отсюда следует, что <tex>A^+</tex> — правая обратная матрица для ''A'': &nbsp; <tex>A A^+ = I</tex> .
Отсюда следует, что <tex>A^+</tex> — правая обратная матрица для ''A'': &nbsp; <tex>A A^+ = I</tex> .
Строка 49: Строка 49:
** либо <tex>A^* A = I</tex>,
** либо <tex>A^* A = I</tex>,
** либо <tex>B B^* = I</tex>,
** либо <tex>B B^* = I</tex>,
-
** либо '''столбцы''' <tex>A</tex> линейно независимы и '''строки''' <tex>B</tex> линейно независимы,
+
** либо '''столбцы''' <tex>A</tex> линейно независимы и '''строки''' <tex>B</tex> линейно независимы, тогда <tex>(AB)^+ = B^+ A^+</tex>.
-
:тогда
+
-
:<tex>(AB)^+ = B^+ A^+</tex>.
+
-
* Псевдообращение можно применять и к скалярам, и к векторам. Это подразумевает, что их будут считать матрицами. Псевдообратный к скаляру <tex>x</tex> — ноль, если <tex>x</tex> — ноль, и обратный к <tex>x</tex> в противном случае:
+
* Псевдообращение можно применять и к скалярам, и к векторам. Псевдообратный к скаляру <tex>x</tex> — ноль, если <tex>x</tex> — ноль, и обратный к <tex>x</tex> в противном случае:
-
:<tex>x^+ = \left\{\begin{matrix} 0, & x=0;
+
<center><tex>x^+ = \left\{\begin{matrix} 0, & x=0; \\ x^{-1}, & x \ne 0. \end{matrix}\right. </tex></center>
-
\\ x^{-1}, & x \ne 0. \end{matrix}\right. </tex>
+
* Псевдообратный для нулевого вектора - транспонированый нулевой вектор. Псевдообратный для иного вектора - сопряжённый транспонированный вектор, делённый на квадрат своей длины:
* Псевдообратный для нулевого вектора - транспонированый нулевой вектор. Псевдообратный для иного вектора - сопряжённый транспонированный вектор, делённый на квадрат своей длины:
-
:<tex>x^+ = \left\{\begin{matrix} 0^T, & x = 0;
+
<center><tex>x^+ = \left\{\begin{matrix} 0^T, & x = 0;\\ {x^* \over x^* x}, & x \ne 0. \end{matrix}\right. </tex></center>
-
\\ {x^* \over x^* x}, & x \ne 0. \end{matrix}\right. </tex>
+
Для доказательства достаточно проверить, что эти величины удовлетворяют определению псевдообратных.
Для доказательства достаточно проверить, что эти величины удовлетворяют определению псевдообратных.
-
 
-
== Происхождение ==
 
-
 
-
Если <tex>(A^* A)^{-1}</tex> существует, то
 
-
:<tex>Ax = b,</tex>
 
-
:<tex>A^* A x = A^* b, </tex>
 
-
:<tex>(A^* A)^{-1}(A^* A) x = (A^* A)^{-1}A^* b, </tex>
 
-
:<tex>x = (A^* A)^{-1}A^* b, </tex>
 
-
что порождает понятие псевдообращения
 
-
:<tex>A^+ = (A^* A)^{-1}A^*</tex> .
 
== Вычисление ==
== Вычисление ==
-
 
-
Пусть ''k'' - ранг матрицы ''A'' размера <tex>m \times n</tex>. Тогда ''A'' может быть представлена как <tex>A = BC</tex>, где ''B'' — матрица размера <tex>m \times k</tex> и ''C'' — матрица размера <tex>k \times n</tex>. Тогда
 
-
 
-
:<tex>
 
-
A^+ = C^*(CC^*)^{-1}(B^*B)^{-1}B^*.
 
-
</tex>
 
-
 
-
Если ''A'' имеет полнострочный ранг, то есть ''k'' = ''m'', тогда в качестве ''B'' может быть выбрана единичная матрица и формула сокращается до <tex>A^+ = A^*(AA^*)^{-1}</tex>. Аналогично, если ''A'' имеет полностолбцовый ранг, то есть, ''k'' = ''n'', имеем <tex>A^+ = (A^*A)^{-1}A^*.</tex>
 
-
 
Простейший вычислительный путь получения псевдообратной матрицы — использование собственного представления матрицы (СПМ).
Простейший вычислительный путь получения псевдообратной матрицы — использование собственного представления матрицы (СПМ).
Строка 93: Строка 70:
Если псевдоинверсия известна для некой матрицы и нужно найти псевдоинверсию для аналогичной матрицы, иногда она может быть вычислена с помощью специальных алгоритмов, требующих меньшего количества расчётов. В частности, если аналогичная матрица отличается от начальной на один изменённый, добавленный или удалённый столбец или строку — существуют накопительные алгоритмы, которые могут использовать взаимосвязь между матрицами.
Если псевдоинверсия известна для некой матрицы и нужно найти псевдоинверсию для аналогичной матрицы, иногда она может быть вычислена с помощью специальных алгоритмов, требующих меньшего количества расчётов. В частности, если аналогичная матрица отличается от начальной на один изменённый, добавленный или удалённый столбец или строку — существуют накопительные алгоритмы, которые могут использовать взаимосвязь между матрицами.
-
== Применение ==
+
== См. также ==
-
 
+
* [[Практикум ММП ВМК, 4й курс, осень 2008|Практикум ММП ВМК, 4й курс, осень 2008]]
-
Псевдоинверсия реализирует решение метода наименьших квадратов для системы линейных уравнений.
+
* [[Метод наименьших квадратов|Метод наименьших квадратов]]
-
 
+
* [[Решение переопределённой СЛАУ|Решение переопределённой СЛАУ]]
-
При этом для данной системы <tex>A x = b</tex> ищется вектор <tex>x</tex>, котрый минимизирует невязку <tex>\|A x - b\|^2</tex>, где <tex>\|\,\cdot\,\|</tex> обозначает евклидову норму.
+
-
 
+
-
Общее решение неоднородной системы <tex>A x = b</tex> представимо как сумма частного решения неоднородной системы и общего решения соответствующей однородной системы <tex>A x = 0</tex>.
+
-
 
+
-
Лемма: Если <tex>(A A^*)^{-1}</tex> существует, тогда решение <tex>x</tex> всегда представимо как сумма решения псевдообратного решения неоднородной системы и решения однородной системы:
+
-
 
+
-
:<tex>x = A^*(A A^*)^{-1}b + (1 - A^*(A A^*)^{-1} A)y.</tex>
+
-
 
+
-
Доказательство:
+
-
 
+
-
:{|
+
-
|-
+
-
|<tex>Ax</tex>
+
-
|<tex>=</tex>
+
-
|<tex>A A^*(A A^*)^{-1}</tex>
+
-
|<tex>b</tex>
+
-
|<tex>+</tex>
+
-
|<tex> A y - A A^*(A A^*)^{-1} A y</tex>
+
-
|-
+
-
|
+
-
|<tex>=</tex>
+
-
|
+
-
|<tex>b</tex>
+
-
|<tex>+</tex>
+
-
|<tex> A y - A y</tex>
+
-
|-
+
-
|
+
-
|<tex>=</tex>
+
-
|
+
-
|<tex>b</tex>
+
-
|.
+
-
|
+
-
|}
+
-
 
+
-
Здесь вектор <tex>y</tex> случаен (с точностью до размерности). В двух других членах есть псевдообратная матрица <tex>A^*(A A^*)^{-1}</tex>. Переписав её в форме <tex>A^+</tex>, приведём выражение к форме:
+
-
 
+
-
:<tex>x = A^+ b + (1 - A^+ A)y.</tex>
+
-
 
+
-
Первый член — псевдообратное решение. В терминах метода наименьших квадратов — это наилучшее приближение к настоящему решению. Это значит, что корректирующий член имеет минимальную евклидову норму. Следующий член даёт решение однородной системы <tex>A x = 0</tex>, потому что <tex>(1 - A^+ A)</tex> — оператор проектирования на ядро оператора A, тогда как <tex>(A^+A) = A^* (A A^*)^{-1} A</tex> — оператор проектирования на образ оператора A.
+

Текущая версия

Псевдообратные матрицы — обобощение обратных матриц в линейной алгебре. Псевдообратная матрица к матрице A обозначается A^+. Псевдообращение можно понимать как наилучшую апроксимацию (по методу наименьших квадратов) решения соответствующей системы линейных уравнений. Псевдообращение определено для любых матриц над действительными и комплексными числами. Псевдообратная матрица может быть вычислена с помощью собственного представления матрицы.

Содержание

Определение

A^+ называется псевдообратной матрицей для матрицы A, если она удовлетворяет следующим критериям:

  1. A A^+A = A;
  2. A^+A A^+ = A^+       (A^+ является слабым обращением в мультипликативной полугруппе);
  3. (AA^+)^* = AA^+       (это означает, что AA^+ — эрмитова матрица);
  4. (A^+A)^* = A^+A       (A^+A - тоже эрмитова матрица).

Здесь M^* - эрмитова сопряжённая матрица M. Для матриц над полем действительных чисел M^* = M^T.

Происхождение

По методу наименьших квадратов для решения несовместной СЛАУ A\mathbf{x}=\mathbf{b}, состоящей из M уравнений с N неизвестными, необходимо решить уравнение

A^TA\mathbf{x}=A^T\mathbf{b},

называемое нормальным уравнением. Пусть столбцы матрицы A линейно независимы, тогда она обратима и система имеет единственное решение

\mathbf{x}=(A^TA)^{-1}A^T\mathbf{b}.

Таким образом мы приходим к понятию псевдообращения действительных матриц:

A^+=(A^TA)^{-1}A^T.

Свойства

  • Псевдообращение обратимо, более того, эта операция обратна самой себе:
    (A^+)^+ = A .
  • Псевдообращение коммутирует с транспонированием, сопряжением и эрмитовым сопряжением:
    (A^T)^+ = (A^+)^T,
    (\overline{A})^+ = \overline{A^+} ,
    (A^*)^+ = (A^+)^* .
  • Псевдообратное произведения матрицы A на скаляр \alpha равно соответствующему произведению матрицы A^+ на обратное число \alpha^{-1}:
    (\alpha A)^+ = \alpha^{-1} A^+ , для \alpha ≠ 0.
  • Если псевдообратная матрица для A^*A уже известна, она может быть использовано для вычисления A^+:
    A^+ = (A^*A)^+A^* .
  • Аналогично, если матрица (AA^*)^+ уже известна:
    A^+ = A^*(AA^*)^+ .

Особые случаи

  • Если столбцы матрицы A линейно независимы, тогда матрица A^* A обратима. В таком случае псевдообратная матрица задаётся формулой
A^+ = (A^* A)^{-1} A^*.

Отсюда следует что A^+ - левая обратная матрица для A:    A^+ A = I .

  • Если строки матрицы A линейно независимы, тогда матрица A A^* обратима. В таком случае псевдообратная матрица задаётся формулой
A^+ = A^*(A A^*)^{-1}.

Отсюда следует, что A^+ — правая обратная матрица для A:   A A^+ = I .

  • Если и столбцы и строки линейно независимы (что верно для квадратных невырожденных матриц), псевдообращение равно обращению:
A^+ = A^{-1} .
  • Если A и B таковы, что произведение AB определено, и
    • либо A^* A = I,
    • либо B B^* = I,
    • либо столбцы A линейно независимы и строки B линейно независимы, тогда (AB)^+ = B^+ A^+.
  • Псевдообращение можно применять и к скалярам, и к векторам. Псевдообратный к скаляру x — ноль, если x — ноль, и обратный к x в противном случае:
x^+ = \left\{\begin{matrix} 0, & x=0; \\ x^{-1}, & x \ne 0. \end{matrix}\right.
  • Псевдообратный для нулевого вектора - транспонированый нулевой вектор. Псевдообратный для иного вектора - сопряжённый транспонированный вектор, делённый на квадрат своей длины:
x^+ = \left\{\begin{matrix} 0^T, & x = 0;\\ {x^* \over x^* x}, & x \ne 0. \end{matrix}\right.

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

Вычисление

Простейший вычислительный путь получения псевдообратной матрицы — использование собственного представления матрицы (СПМ).

Если A = U\Sigma V^* — собственное представление A, тогда A^+ = V\Sigma^+ U^*. Для диагональной матрицы, такой как \Sigma, псевдообратная вычисляется обращением каждого ненулевого элемента на диагонали.

Существуют оптимизированые подходы для вычисления псевдоинверсии блочных матриц.

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

См. также