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

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

< Участник:Василий Ломакин(Различия между версиями)

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

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

Определение

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

$A A^+A = A;$
$A^+A A^+ = A^+$ ( $A^+$ является слабым обращением в мультипликативной полугруппе);
$(AA^+)^* = AA^+$ (это означает, что $AA^+$ — эрмитова матрица);
$(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 таковы, что произведение определено, и
- либо $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$ , псевдообратная вычисляется обращением каждого ненулевого элемента на диагонали.

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

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

См. также

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%92%D0%B0%D1%81%D0%B8%D0%BB%D0%B8%D0%B9_%D0%9B%D0%BE%D0%BC%D0%B0%D0%BA%D0%B8%D0%BD/%D0%9F%D1%81%D0%B5%D0%B2%D0%B4%D0%BE%D0%BE%D0%B1%D1%80%D0%B0%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D1%80%D0%B8%D1%86%D0%B0»

@@ Строка 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>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^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^*A</tex> уже известна, она может быть использовано для вычисления <tex>A^+</tex>:<br> <tex>A^+ = (A^*A)^+A^* </tex> .
@@ Строка 35: / Строка 37: @@
 * Если '''столбцы''' матрицы <tex>A</tex> линейно независимы, тогда матрица <tex>A^* 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> линейно независимы, тогда матрица <tex>A A^*</tex>  обратима.  В таком случае псевдообратная матрица задаётся формулой
 :<tex>A^+ = A^*(A A^*)^{-1}.</tex>
-Это эквивалентно тому, что во второй части определения через предел убирается слагаемое с <tex>\delta</tex>.
 Отсюда следует, что <tex>A^+</tex> — правая обратная матрица для ''A'': &nbsp; <tex>A A^+ = I</tex> .
@@ Строка 49: / Строка 49: @@
 ** либо <tex>A^* A = 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.

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

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

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

Содержание

Определение

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

Свойства

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

Вычисление

См. также

Просмотры

Личные инструменты

Навигация

Поиск

Инструменты