Инструменты сайта


Псевдообратная матрица

В настоящем разделе все матрицы предполагаются вещественными.

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

Рассмотрим систему линейных уравнений относительно неизвестных $ x_1,\dots, x_n $ в матричной форме записи: $$ AX= \mathcal B ; $$ здесь $ A\in \mathbb R^{m\times n}, \mathcal B \in \mathbb R^{m\times 1}, X=(x_1,\dots,x_n)^{\top} $. При $ m > n $ система является переопределенной: число уравнений превышает число неизвестных. Такая система, как правило, несовместна. Однако если домножить ее слева на матрицу $ A^{\top} $, то новая система $$ A^{\top}X= A^{\top} \mathcal B $$ становится совместной, и, как правило, имеет единственное решение. Доказательство последнего факта основано на свойстве матрицы $ A^{\top} A $. Эта симметричная матрица имеет неотрицательный определитель $$ \det ( A^{\top} A) \ge 0 \, , $$ (см. теорему $ 2 $ в пункте ТЕОРЕМА БИНЕ-КОШИ). При дополнительном условии $ \operatorname{rank} (A) =n $ (которое при случайном выборе матрицы $ A $ выполняется с вероятностью $ 1 $, см. комментарий в пункте Теорема Кронекера-Капелли), этот определитель строго больше нуля. И в этом последнем случае единственное решение новой системы можно представить в виде $$ X_{\ast}=\left(A^{\top}A\right)^{-1} A^{\top} \mathcal B \, . $$ Это решение известно как псевдорешение системы $ AX= \mathcal B $ и оно является решением задачи $$ \min_ {X\in \mathbb R^n} \| AX-\mathcal B \|^2 \, . $$ Грубо говоря: если уж исходная система не имеет решения в традиционном смысле, то будем искать вектор $ X_{\ast} $, который «минимизирует ошибку», т.е. отклонение вектора $ AX $ от $ \mathcal B $. Матрица, участвующая в записи псевдорешения называется псевдообратной матрицей (Мура-Пенроуза)1) к матрице $ A_{} $, она обозначается $ A^{+} $: $$ A^{+}=(A^{\top}A)^{-1} A^{\top} \quad \mbox{при} \ A\in \mathbb R^{m\times n}, \ m>n= \operatorname{rank} (A) \, . $$ Очевидно, что эта матрица является левой обратной матрицей к матрице $ A $: $$ A^{+}A=E_{n} \, , $$ где $ E_n $ — единичная матрица порядка $ n $.

П

Пример. Найти $ A^{+} $ для

$$ A= \left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \\ 1 & 1 \end{array} \right) \ . $$

Решение. $$ A^{\top}= \left( \begin{array}{ccc} 1 & 0 & 1 \\ 0 & 1 & 1 \end{array} \right) \quad \Rightarrow \quad A^{\top} \cdot A = \left( \begin{array}{cc} 2 & 1 \\ 1 & 2 \end{array} \right) \quad \Rightarrow \quad (A^{\top} \cdot A)^{-1} = \left( \begin{array}{cc} 2/3 & -1/3 \\ -1/3 & 2/3 \end{array} \right) \ \Rightarrow $$ $$ \Rightarrow \ A^{+} = (A^{\top} \cdot A)^{-1} A^{\top} = \left( \begin{array}{rrr} 2/3 & -1/3 & 1/3 \\ -1/3 & 2/3 & 1/3 \end{array} \right) \ . $$ При этом $$ A^{+} \cdot A = \left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array} \right),\quad A \cdot A^{+} = \left( \begin{array}{rrr} 2/3 & -1/3 & 1/3 \\ -1/3 & 2/3 & 1/3 \\ 1/3 & 1/3 & 2/3 \end{array} \right) \ , $$ т.е. матрица $ A^{+} $ не является правой обратной для матрицы $ A_{} $.

Рассмотрим теперь противоположный случай: количество столбцов матрицы $ A $ больше количества ее строк, т.е. $ n > m $. Система $ AX= \mathcal B $ с такой матрицей, как правило, совместна и имеет бесконечное множество решений. Действительно, ранг случайно выбранной матрицы такого порядка равен $ m $ с вероятностью $ 1 $, но тогда, в соответствии с теоремой Кронекера-Капелли, система $ AX=\mathcal B $ имеет бесконечное множество решений. Одно, частное, решение может быть представлено в виде $$ X_{\ast}= A^{\top} \left(A\cdot A^{\top}\right )^{-1} \mathcal B \, . $$ Действительно, $ \det \left(A\cdot A^{\top}\right ) > 0 $ (снова см. теорему $ 2 $ в пункте ТЕОРЕМА БИНЕ-КОШИ). Поэтому обратная матрица в формуле существует. Подстановка $ X=X_{\ast} $ в систему приводит к верному равенству. Матрица $$ A^{+}=A^{\top} \left(A\cdot A^{\top}\right )^{-1} \quad \mbox{при} \ A\in \mathbb R^{m\times n}, \ n>m= \operatorname{rank} (A) $$ называется псевдообратной матрицей (Мура-Пенроуза) к матрице $ A $. Очевидно, что эта матрица является правой обратной матрицей к матрице $ A $: $$ A \cdot A^{+} =E_{m} \, , $$ где $ E_m $ — единичная матрица порядка $ m $.

П

Пример 2. Найти $ A^{+}({\color{Red}{ \alpha} }) $ для

$$ A({\color{Red}{ \alpha} })=\left[ \begin {array}{cccc} 1&-2&1&2\\ 1&1&-2&2 \\ 2&{\color{Red}{ \alpha} } &-1&4\end {array} \right] \quad \mbox{где} \ {\color{Red}{ \alpha} } \in \mathbb R \, . $$

Решение. $$ A^{+}({\color{Red}{ \alpha} })=A^{\top}({\color{Red}{ \alpha} }) \left(A({\color{Red}{ \alpha} })\cdot A^{\top}({\color{Red}{ \alpha} })\right )^{-1}=\frac{1}{{\color{Red}{ \alpha} }+1} \left[ \begin {array}{ccc} \frac{2}{15}\,{\color{Red}{ \alpha} }-\frac{1}{15} &\frac{1}{15}{\color{Red}{ \alpha} }-\frac{2}{15}&\frac{1}{5} \\ -1&-1&1\\ \frac{1}{3}{\color{Red}{ \alpha} }-\frac{2}{3}&-\frac{1}{3}{\color{Red}{ \alpha} } -\frac{4}{3}&1\\ \frac {4}{15}\,{\color{Red}{ \alpha} }-\frac{2}{15}&\frac{2}{15}\,{\color{Red}{ \alpha} }- \frac{4}{15}&\frac{2}{5}\end {array} \right] \quad \mbox{при} \ {\color{Red}{ \alpha} }\ne -1 \, . $$ Но вот случай $ {\color{Red}{ \alpha} }= -1 $ не покрывается полученной формулой.

Наконец, в случае квадратной матрицы $ A\in \mathbb R^{n\times n} $ ранга $ n $ (что эквивалентно $ \det A \ne 0 $) псевдообратная матрица определяется любой из двух указанных формул, и, легко видеть, что в этом случае она совпадает с обратной к матрице $ A $: $$ A^{+}=A^{-1} \quad \mbox{при} \ A\in \mathbb R^{n\times n}, \ n= \operatorname{rank} (A) \, . $$ Рассмотренные выше определения относятся к случаю матрицы $ A $ полного ранга, т.е. матрицы, удовлетворяющей условию $$ \operatorname{rank} (A) = \min \{m,n\} \, . $$ Осталось рассмотреть случай когда это условие нарушается.

Существование

Т

Теорема 1. Для любой матрицы $ A \in \mathbb R^{m\times n} $ существует единственная псевдообратная матрица $ A^{+}\in \mathbb R^{n\times m} $, т.е. матрица, удовлетворяющая следующим условиям

1. $ A\cdot A^{+} \cdot A = A $;

2. $ A^{+} \cdot A \cdot A^{+} = A^{+} $;

3. матрица $ A\cdot A^{+} $ симметрична: $ (A\cdot A^{+})^{\top} = A \cdot A^{+} $.

4. матрица $ A^{+} A $ симметрична: $ (A^{+} A )^{\top} =A^{+} A $.

Вычисление

Т

Теорема 2. Пусть матрица $ A\in \mathbb R^{m\times n} $ имеет ранг $ \mathfrak r $ и ее ранговое разложение имеет вид

$$ A=CF \quad \mbox{при} \ C\in \mathbb R^{m \times \mathfrak r},\ F\in \mathbb R^{\mathfrak r \times n}, \operatorname{rank} (C)= \operatorname{rank} (F) = \mathfrak r \, .$$ Тогда $$ A^{+}=F^{+}C^{+}=F^{\top} \left( F \cdot F^{\top} \right)^{-1} \left(C^{\top} C \right)^{-1} C^{\top} $$

Фактически эта теорема сводит вычисление псевдообращения к случаю матриц полного ранга — тех, что рассмотрены ВЫШЕ.

П

Пример 3. Найти $ A^{+} ({\color{Red}{ \alpha} }) $ для матрицы примера 2 в случае ${\color{Red}{ \alpha} }=-1 $.

Решение. Ранговое разложение матрицы $ A(-1) $ имеет вид (см.решение ПРИМЕРА) $$ A(-1)=CF \quad \mbox{при} \ C= \left[ \begin {array}{rr} 1&-2\\1&1 \\ 2&-1\end {array} \right],\ F=\left[ \begin {array}{cccc} 1&0&-1&2\\ 0&1&-1&0 \end {array} \right] \, . $$ Теперь применяем теорему $$ C^{\top} C =\left[ \begin{array}{rr} 6 & -3 \\ -3 & 6 \end{array} \right] \ \Rightarrow \ (C^{\top} C)^{-1}=\frac{1}{9} \left[ \begin{array}{rr} 2 & 1 \\ 1 & 2 \end{array} \right] \ \Rightarrow \ С^{+}= \left(C^{\top} C \right)^{-1} C^{\top} =\frac{1}{3} \left[ \begin{array}{rr} 0 & 1 & 1 \\ -1 & 1 & 0 \end{array} \right] $$ Аналогично $$ F^{+}=F^{\top} \left( F \cdot F^{\top} \right)^{-1}=\frac{1}{11} \left[ \begin {array}{rr} 2&-1\\ -1 &6\\ -1&-5 \\ 4&-2\end {array} \right] $$ и $$ A^{+}(-1) = \frac{1}{33} \left[ \begin {array}{rrr} 1&1&2\\ -6&5&-1\\ 5&-6&-1\\ 2&2&4 \end{array} \right] $$

Вычисление посредством сингулярного разложения

Псевдообратная к произвольной матрице $ A \in \mathbb R^{m\times n} $ (без ограничения на ее ранг) может быть вычислена с помощью сингулярного разложения. Обозначим ненулевые сингулярные числа матрицы $ A $ ранга $ \mathfrak r $ через $ \{\sigma_j\}_{j=1}^{\mathfrak r} $, а соответствующие левые и правые сингулярные векторы через $ \{U_{[j]}\}_{j=1}^{\mathfrak r} $ и $ \{V_{[j]}\}_{j=1}^{\mathfrak r} $. Вектора каждой из систем предполагаются ортонормированными. Тогда сингулярное разложение матрицы имеет вид $$ A=\sum_{j=1}^{\mathfrak r} \sigma_j U_{[j]} V_{[j]}^{\top} \, . $$ а $$ A^{+}=\sum_{j=1}^{\mathfrak r} \frac{1}{\sigma_j} V_{[j]} U_{[j]}^{\top} \, . $$

Проверим этим методом ответ в примере предыдущего пункта.

П

Пример 4. Найти $ A^{+} ({\color{Red}{ \alpha} }) $ для матрицы примера 2 в случае ${\color{Red}{ \alpha} }=-1 $.

Решение. Будем записывать матрицу $ A(-1) $ без указания аргумента $$ A=\left[ \begin {array}{cccc} 1&-2&1&2\\ 1&1&-2&2 \\ 2&-1&-1&4\end {array} \right] \, . $$ $$ A\cdot A^{\top} = \left[ \begin {array}{rrr} 10&1&11\\ 1&10&11 \\ 11&11&22\end {array} \right] $$ $$ \det(A\cdot A^{\top}-\lambda E)\equiv - \lambda (\lambda-9)(\lambda - 33) \ ; $$ таким образом $ \sigma_1=\sqrt{33}, \sigma_2=3, \sigma_3=0 $. Левые сингулярные векторы — собственные для матрицы $ A\cdot A^{\top} $: $$ U_{[1]}=\left[ \begin{array}{c} 1/\sqrt{6} \\ 1/\sqrt{6} \\ 2/\sqrt{6} \end{array} \right], \ U_{[2]}=\left[ \begin{array}{r} -1/\sqrt{2} \\ 1/\sqrt{2} \\ 0 \end{array} \right] ; $$ правые получаются из них по правилу $ V_{[j]}=A^{\top} U_{[j]}/\sigma_j $ $$ V_{[1]}=\left[ \begin{array}{r} 2/\sqrt{22} \\ -1/\sqrt{22} \\ -1/\sqrt{22} \\ 4/\sqrt{22} \\ \end{array} \right], \ V_{[2]}=\left[ \begin{array}{r} 0 \\ 1/\sqrt{2} \\ -1/\sqrt{2} \\ 0 \\ \end{array} \right] \, . $$ Таким образом, $$ A^{+}=\frac{1}{\sigma_1} V_{[1]}U_{[1]}^{\top}+ \frac{1}{\sigma_2} V_{[2]}U_{[2]}^{\top} = \frac{1}{33} \left[ \begin {array}{rrr} 1&1&2\\ -6&5&-1 \\ 5&-6&-1\\ 2&2&4\end {array} \right] $$

Способ вычисления псевдообращения, основанный на сингулярном разложении матрицы, в некоторых источниках упоминается как вычислительно эффективный. Лично у меня это утверждение вызывает сомнения. Сравним решения примеров 3 и 4. Псевдообратная матрица является «рациональной функцией» матрицы $ A $ (т.е. элементы $ A^{+} $ являются рациональными функциями элементов матрицы $ A $), причем рациональной функцией с целочисленными коэффициентами. Вместе с тем, решение примера 4 выводит в область иррациональных чисел. И это еще не самый плохой случай: для матриц порядков $ > 4 $ с элементами рациональными не приходится ожидать представления сингулярных чисел хотя бы и в радикалах… Придется ограничиваться приближенными их значениями — и это при том, что конечный ответ обязан быть представим в рациональных числах! А уж о случаях, когда матрица зависит от параметров ужасает даже сама мысль о сингулярных числах! m(

Применения

Решение систем линейных уравнений

Т

Теорема 3. Для системы линейных уравнений

$$AX=\mathcal B , \ A\in \mathbb R^{m\times n}, \ \mathcal B \in \mathbb R^m $$ относительно столбца неизвестных $ X=(x_1,\dots x_n)^{\top} $ столбец $$ X_{\ast} =A^{+} \mathcal B $$ является псевдорешением. Система $AX=\mathcal B $ совместна (в традиционном смысле) тогда и только тогда, когда $$ A \cdot A^{+} \mathcal B = \mathcal B \, . $$ При выполнении этого условия, общее решение системы записывается в виде $$ X=A^{+} \mathcal B + (E_n-A^{+}A)Y \quad \mbox{при произвольном столбце } \ Y\in \mathbb R^n \, . $$

Доказательство первой части теоремы производится прямой подстановкой $ X=X_{\ast} $ в нормальную систему $$ \left[A^{\top}A \right]X=A^{\top} {\mathcal B} $$ и проверкой равенства $ A^{\top} A \cdot A^{+} = A^{\top} $ с помощью теоремы 2.

П

Пример 5. Найти общее решение системы уравнений

$$ \left\{\begin{array}{rrrr} x_1 & + 2\,x_2 & +3\, x_3 &=3, \\ -x_1 & + x_2 & &=5. \end{array} \right. $$

Решение. Здесь $$ A=\left( \begin{array}{rrr} 1 & 2 & 3 \\ -1 & 1 & 0 \end{array} \right) \ \Rightarrow \ A\cdot A^{\top}= \left( \begin{array}{rr} 14 & 1 \\ 1 & 2 \end{array} \right) \ \Rightarrow \ \left(A\cdot A^{\top}\right)^{-1} = \left( \begin{array}{rr} 2/27 & -1/27 \\ -1/27 & 14/27 \end{array} \right) \ \Rightarrow $$ $$ \ \Rightarrow A^{+}= A^{\top} (A\cdot A^{\top})^{-1}= \left( \begin{array}{rr} 1/9 & -5/9 \\ 1/9 & 4/9 \\ 2/9 &-1/9 \end{array} \right) \ \Rightarrow \ $$ $$ \ \Rightarrow A^{+}\mathcal B = \left( \begin{array}{r} -22/9 \\ 23/9 \\ 1/9 \end{array} \right) \ , A^{+}A= \left( \begin{array}{rrr} 2/3 & -1/3 & 1/3 \\ -1/3 & 2/3 & 1/3 \\ 1/3 & 1/3 & 2/3 \end{array} \right) \ \Rightarrow $$ $$ X= \left( \begin{array}{r} -22/9 \\ 23/9 \\ 1/9 \end{array} \right) + \frac{1}{3} (y_1+y_2-y_3) \left( \begin{array}{r} 1 \\ 1 \\ -1 \end{array} \right) $$ Столбец $ [1,1,-1]^{\top} $ составляет фундаментальную систему решений однородной системы $$ \left\{\begin{array}{rrrr} x_1 & + 2\,x_2 & +3\, x_3 &=0, \\ -x_1 & + x_2 & &=0. \end{array} \right. $$

Расстояние до линейных многообразий

Т

Теорема. Ближайшая (в стандартной евклидовой метрике) к точке $ X_{0} \in \mathbb R^n $ точка многообразия

$$ \mathbb M= \{ Y_0+\lambda_1 Y_1+\dots+\lambda_k Y_k \quad \mid \quad \{\lambda_1,\dots,\lambda_k\} \subset {\mathbb R} \} $$ при фиксированных линейно независимых столбцах $$ \{Y_0,Y_1,\dots,Y_k \}\subset {\mathbb R}^n$$ определяется по формуле $$ X_{\ast}=Y_0+ L\cdot L^{+} (X_0-Y_0) \, . $$ Здесь $$ L=\left[ Y_1|\dots|Y_k \right]_{n\times k} \, , $$ а $ |_{} $ означает конкатенацию.

Доказательство ЗДЕСЬ.

Свойства

Непрерывность

Хотя псевдообратная матрица $ A^{+} $ существует всегда, и зависит от элементов матрицы $ A $ посредством рациональных функций, непрерывность этой зависимости не гарантирована. См. решение примеров 2 и 3. Матрица $A^{+} ({\color{Red}{ \alpha} }) $ существует при всех значениях параметра, но $$ \lim_{ {\color{Red}{ \alpha} } \to -1} A^{+} ({\color{Red}{ \alpha} }) $$ не существует.

Оптимизационная задача

Оба произведения $ A \cdot A^{+} $ и $ A^{+} A $ определены, но при этом может случиться, что ни одно не совпадает с единичной матрицей. Иными словами, $ A^{+} $ может не оказаться ни левой обратной матрицей, ни правой обратной для матрицы $ A $. Тем не менее, $ A^{+} $ оказывается, образно говоря, «наилучшим приближением» обратной матрицы: если уж невозможно найти обратную матрицу для матрицы $ A \in \mathbb R^{m\times n} $, давайте найдем хотя бы такую матрицу $ X_{n\times m} $, чтобы отклонение произведения $ A\cdot X $ от единичной матрицы $ E_m $, вычисленное как квадрат расстояния между матрицами $ A\cdot X $ и $ E_m $, было бы минимальным.

Т

Теорема. Псевдообратная матрица $ A^{+} $ является решением двух задач минимизации

$$ \mbox{(a)} \quad \min_{X\in \mathbb R^{n\times m}} ||AX-E_m||^2 $$

$$ \mbox{(b)} \quad \min_{Y\in \mathbb R^{n\times m}} ||YA-E_n||^2 \, . $$

где $ || \cdot || $ означает евклидову норму (норму Фробениуса) матрицы.

Доказательство может быть произведено с использованием сингулярных разложений матриц $ A $ и $ A^{+} $. В обозначения ПУНКТА: $$ A=\sum_{j=1}^{\mathfrak r} \sigma_j U_{[j]} V_{[j]}^{\top} \, , \ A^{+}=\sum_{j=1}^{\mathfrak r} \frac{1}{\sigma_j} V_{[j]} U_{[j]}^{\top} $$ Тогда $$ A\cdot A^{+} - E_m = - \sum_{j=\mathfrak r +1}^m U_{[j]} U_{[j]}^{\top} \ ; $$ здесь столбцы $ \{U_{[j]}\}_{j=\mathfrak r +1}^m $ — произвольные такие, чтобы система $ \{U_{[j]}\}_{j=1}^m $ составляла ортнонормированный базиc $ \mathbb R^m $. И, вдобавок, воспользовались решением УПРАЖНЕНИЯ. Тогда $$ \operatorname{Sp} \left[ \left( A\cdot A^{+} - E_m \right)^{\top} \left( A\cdot A^{+} - E_m \right) \right] = m-\mathfrak r $$ и $ \| A\cdot A^{+} - E_m \| = \sqrt{m-\mathfrak r} $.

Аналогично доказывается, что $ \| A^{+} A - E_n \| = \sqrt{n-\mathfrak r} $.

1)
(англ.) pseudoinverse или Moore-Penrose inverse
algebra2/inverse/p_inverse.txt · Последние изменения: 2023/09/09 23:08 — au