==Псевдообратная матрица== В настоящем разделе все матрицы предполагаются вещественными. ===Происхождение== Рассмотрим систему линейных уравнений относительно неизвестных $ x_1,\dots, x_n $ ((:algebra2/linearsystems#matrichnaja_forma_zapisi в матричной форме записи)): $$ 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 $ система является переопределенной: число уравнений превышает число неизвестных. Такая система, как правило, ((:algebra2/linearsystems#teorema_kronekera-kapelli несовместна)). Однако если домножить ее слева на матрицу $ A^{\top} $, то новая система $$ A^{\top}X= A^{\top} \mathcal B $$ становится совместной, и, как правило, имеет единственное решение. Доказательство последнего факта основано на свойстве матрицы $ A^{\top} A $. Эта симметричная матрица имеет неотрицательный определитель $$ \det ( A^{\top} A) \ge 0 \, , $$ (см. теорему $ 2 $ в пункте ☞ ((:algebra:dets:binet_cauchy ТЕОРЕМА БИНЕ-КОШИ))). При дополнительном условии $ \operatorname{rank} (A) =n $ (которое при случайном выборе матрицы $ A $ выполняется с вероятностью $ 1 $, см. комментарий в пункте ((:algebra2/linearsystems#teorema_kronekera-kapelli Теорема Кронекера-Капелли))), этот определитель строго больше нуля. И в этом последнем случае единственное решение новой системы можно представить в виде $$ X_{\ast}=\left(A^{\top}A\right)^{-1} A^{\top} \mathcal B \, . $$ Это решение известно как ((:interpolation/mnk#psevdoreshenie_sistemy_linejnyx_uravnenij псевдорешение)) системы $ AX= \mathcal B $ и оно является решением задачи $$ \min_ {X\in \mathbb R^n} \| AX-\mathcal B \|^2 \, . $$ Грубо говоря: если уж исходная система не имеет решения в традиционном смысле, то будем искать вектор $ X_{\ast} $, который "минимизирует ошибку", т.е. отклонение вектора $ AX $ от $ \mathcal B $. Матрица, участвующая в записи псевдорешения называется **псевдообратной матрицей (Мура-Пенроуза)**[[(//англ.)// pseudoinverse или Moore-Penrose inverse]] к матрице $ A_{} $, она обозначается $ A^{+} $: $$ A^{+}=(A^{\top}A)^{-1} A^{\top} \quad \mbox{при} \ A\in \mathbb R^{m\times n}, \ m>n= \operatorname{rank} (A) \, . $$ Очевидно, что эта матрица является ((:algebra2/inverse#obratnaja_matrica левой обратной матрицей)) к матрице $ 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^{+} $ не является ((:algebra2/inverse#obratnaja_matrica правой обратной)) для матрицы $ A_{} $. ♦ Рассмотрим теперь противоположный случай: количество столбцов матрицы $ A $ больше количества ее строк, т.е. $ n > m $. Система $ AX= \mathcal B $ с такой матрицей, как правило, совместна и имеет бесконечное множество решений. Действительно, ранг случайно выбранной матрицы такого порядка равен $ m $ с вероятностью $ 1 $, но тогда, в соответствии с теоремой ((:algebra2/linearsystems#teorema_kronekera-kapelli Кронекера-Капелли)), система $ 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 $ в пункте ☞ ((:algebra:dets:binet_cauchy ТЕОРЕМА БИНЕ-КОШИ))). Поэтому обратная матрица в формуле существует. Подстановка $ 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 $. Очевидно, что эта матрица является ((:algebra2/inverse#obratnaja_matrica правой обратной матрицей)) к матрице $ 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 $ //и ее ((:algebra2/rank#rangovaja_faktorizacija ранговое разложение)) имеет вид// $$ 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} $$ Фактически эта теорема сводит вычисление псевдообращения к случаю матриц полного ранга --- тех, что рассмотрены ((#proisxozhdenie ВЫШЕ)). !!П!! **Пример 3.** Найти $ A^{+} ({\color{Red}{ \alpha} }) $ для матрицы примера 2 в случае ${\color{Red}{ \alpha} }=-1 $. **Решение.** Ранговое разложение матрицы $ A(-1) $ имеет вид (см.решение ☞ ((:algebra2/rank#rangovaja_faktorizacija ПРИМЕРА ))) $$ 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} $ (без ограничения на ее ранг) может быть вычислена с помощью ((:algebra2/svd#singuljarnoe_razlozhenie сингулярного разложения)). Обозначим ненулевые сингулярные числа матрицы $ 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 $$ //является ((:interpolation/mnk#psevdoreshenie_sistemy_linejnyx_uravnenij псевдорешением)). Система// $AX=\mathcal B $ //совместна (в ((:algebra2/linearsystems#sistemy_linejnyx_uravnenij традиционном смысле))) тогда и только тогда, когда// $$ 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} $ составляет ((:algebra2/linearsystems#sistema_odnorodnyx_uravnenij фундаментальную систему решений)) однородной системы $$ \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} \, , $$ //а// $ |_{} $ //означает ((:algebra2#конкатенация конкатенацию))//. **Доказательство** ☞ ((:algebra2/optimiz/distance/vspom6 ЗДЕСЬ)). ===Свойства== ====Непрерывность== Хотя псевдообратная матрица $ 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 || $ //означает ((:norm_space#норма_матрицы евклидову норму)) (норму Фробениуса) матрицы//. **Доказательство** может быть произведено с использованием сингулярных разложений матриц $ A $ и $ A^{+} $. В обозначения ☞ ((#vychislenie_posredstvom_singuljarnogo_razlozhenija ПУНКТА)): $$ 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 $. И, вдобавок, воспользовались решением ☞ ((:algebra2/ort_matrix/problems#zadachi УПРАЖНЕНИЯ)). Тогда $$ \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} $. ♦