Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]


Псевдорешения системы линейных уравнений

Псевдорешения системы линейных уравнений


Как показано выше, система m линейных алгебраических уравнений с n неизвестными


Ax=b
(5.27)

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


Для дальнейших рассуждений нам потребуется количественная характеристика для "измерения" и "сравнения" между собой матриц-столбцов. Для этого каждому столбцу поставим в соответствие неотрицательное действительное число.


Модулем (нормой) столбца x=\begin{pmatrix}x_1&x_2&\ldots&x_n\end{pmatrix}^{T} называется неотрицательное число


\begin{vmatrix}x\end{vmatrix}= \sqrt{x_1^2+x_2^2+\ldots+x_n^2}\,.

Заметим, что величина \varepsilon(x)=|Ax-b| характеризует погрешность решения системы. Если величина \varepsilon(x) велика, то столбец x — плохое приближенное решение. Если погрешность \varepsilon(x) мала, то столбец x — хорошее приближенное решение. Если же x является решением системы (в привычном понимании), то \varepsilon(x)=0.


Псевдорешением системы линейных уравнений (5.27) называется наименьший по модулю столбец \widetilde{x} среди всех столбцов x, минимизирующих величину |Ax-b|.


Любая система имеет единственное псевдорешение


\widetilde{x}= A^{\sim1}\cdot b,

где матрица A^{\sim1} — псевдообратная для матрицы системы.


Понятие псевдорешения позволяет обойти не только факт неединственности, но и факт несуществования решений. Если система несовместна, то псевдорешение \widetilde{x} обеспечивает наименьшую величину погрешности \varepsilon(x). Если система совместна, то псевдорешение \widetilde{x} является ее решением, т.е. \varepsilon(\widetilde{x})=0, причем наименьшим по модулю.




Алгоритм нахождения псевдорешения неоднородной системы


1. Найти псевдообратную матрицу A^{\sim1} одним из способов, рассмотренных ранее.


2. Найти псевдорешение \widetilde{x}=A^{\sim1}b.


Пример 5.8. Найти псевдорешение системы уравнений


\begin{cases}x_1+x_2+2x_3+x_4=1,\\ 2x_1+3x_2+x_4=0,\\ 3x_1+4x_2+2x_3+2x_4=1.\end{cases}

Решение. 1. Найдем псевдообратную матрицу. При решении примера 5.6 матрица системы была приведена к простейшему виду


\Lambda=SAT= \begin{pmatrix}1&0\!\!&\vline\!\!&0&0\\ 0&1\!\!&\vline\!\!&0&0\\\hline 0&0\!\!&\vline\!\!&0&0\end{pmatrix}\!,\quad S=\begin{pmatrix}1&0&0\\-2&1&0\\-1&-1&1\end{pmatrix}\!,\quad T=\begin{pmatrix}1&-1&-6&-2\\0&1&4&1\\ 0&0&1&0\\ 0&0&0&1 \end{pmatrix}\!,\quad r=2.

По матрицам S и T находим псевдообратную матрицу. Вычисляем произведения SS^{\ast},~T^{\ast}T и разбиваем их на блоки


\begin{aligned}SS^{\ast}&= \begin{pmatrix}1&0&0\\-2&1&0\\-1&-1&1\end{pmatrix} \!\cdot\! \begin{pmatrix}1&-2&-1\\ 0&1&-1\\ 0&0&1\end{pmatrix}= \begin{pmatrix}1&-2\!\!&\vline\!\!&-1\\ -2&5\!\!&\vline\!\!&1\\\hline -1&1\!\!&\vline\!\!&3 \end{pmatrix}= \begin{pmatrix}S_1\!\!&\vline\!\!& S_2\\\hline S_3\!\!&\vline\!\!&S_4 \end{pmatrix}\!;\\[5pt] T^{\ast}T&= \begin{pmatrix}1&0&0&0\\-1&1&0&0\\ -6&4&1&0\\ -2&1&0&1\end{pmatrix}\!\cdot\! \begin{pmatrix}1&-1&-6&-2\\0&1&4&1\\ 0&0&1&0\\ 0&0&0&1\end{pmatrix}= \begin{pmatrix}1&-1\!\!&\vline\!\!&-6&-2\\ -1&2\!\!&\vline\!\!& 10&3\\\hline -6&10\!\!&\vline\!\!&53&16\\ -2&3\!\!&\vline\!\!&16&6\end{pmatrix}= \begin{pmatrix} T_1\!\!&\vline\!\!& T_2\\\hline T_3\!\!&\vline\!\!&T_4\end{pmatrix}\!. \end{aligned}

Вычисляем матрицы


\begin{aligned}U&=-T_4^{-1}T_3= -\frac{1}{62}\! \begin{pmatrix}6&-16\\-16&53\end{pmatrix}\!\cdot\! \begin{pmatrix}-6&10\\-2&3\end{pmatrix}= \frac{1}{62}\! \begin{pmatrix}4&-12\\10&1\end{pmatrix}\!;\\[5pt] V&=-S_2S_4^{-1}= -\begin{pmatrix}-1\\1\end{pmatrix}\!\cdot\frac{1}{3}= \frac{1}{3}\! \begin{pmatrix}1\\-1\end{pmatrix}\!,\end{aligned}

По формуле (4.21) вычисляем псевдообратную матрицу


A^{\sim1}=T\cdot\! \begin{pmatrix}\dfrac{E_r}{U}\end{pmatrix}\!\cdot\! \begin{pmatrix}E_r\mid V\end{pmatrix}\!\cdot S=

=\begin{pmatrix}1&-1&-6&-2\\ 0&1&4&1\\0&0&1&0\\0&0&0&1\end{pmatrix}\!\cdot\! \begin{pmatrix}\begin{matrix}1&0\\0&1\end{matrix}\\\hline \dfrac{1}{62}\! \begin{pmatrix}4&-12\\ 10&1 \end{pmatrix}\end{pmatrix}\!\cdot\! \begin{pmatrix}\begin{matrix}1&0\\0&1\end{matrix} \!\!\!&\vline\!\!\!&\dfrac{1}{3}\! \begin{pmatrix}1\\-1\end{pmatrix}\!\end{pmatrix}\!\cdot\! \begin{pmatrix}1&0&0\\-2&1&0\\-1&-1&1\end{pmatrix}=

=\frac{1}{62}\cdot\frac{1}{3} \cdot\! \begin{pmatrix}1&-1&-6&-2\\ 0&1&4&1\\0&0&1&0\\0&0&0&1\end{pmatrix}\!\cdot\! \begin{pmatrix}62&0\\0&62\\\hline 4&-12\\10&1\end{pmatrix}\!\cdot\! \begin{pmatrix}3&0\!\!&\vline\!\!&1\\0&3\!\!&\vline\!\!&-1 \end{pmatrix}\!\cdot\! \begin{pmatrix}1&0&0\\-2&1&0\\-1&-1&1\end{pmatrix}=

= \frac{1}{186}\cdot\! \begin{pmatrix}1&-1&-6&-2\\ 0&1&4&1\\0&0&1&0\\ 0&0&0&1 \end{pmatrix}\!\cdot\! \begin{pmatrix}186&0&62\\0&186&-62\\ 12&-36&16\\30&3&9 \end{pmatrix}\!\cdot\! \begin{pmatrix}1&0&0\\-2&1&0\\-1&-1&1\end{pmatrix}=

= \frac{1}{186}\cdot\! \begin{pmatrix}1&-1&-6&-2\\ 0&1&4&1\\0&0&1&0\\ 0&0&0&1 \end{pmatrix}\!\cdot\! \begin{pmatrix}124&-62&62\\-310&248&-62\\ 68&-52&16\\15&-6&9\end{pmatrix}= \frac{1}{186}\cdot\! \begin{pmatrix}-4&14&10\\-23&34&11\\ 68&-52&16\\ 15&-6&9 \end{pmatrix}\!.

2. Находим псевдорешение


\widetilde{x}=A^{\sim1}b= \frac{1}{186}\cdot\! \begin{pmatrix}-4&14&10\\-23&34&11\\ 68&-52&16\\ 15&-6&9 \end{pmatrix}\!\cdot\! \begin{pmatrix}1\\0\\1\end{pmatrix}= \frac{1}{186}\!\cdot \begin{pmatrix}6\\-12\\84\\24\end{pmatrix}= \frac{1}{31}\cdot\! \begin{pmatrix}1\\-2\\14\\4 \end{pmatrix}\!.

Покажем, что это решение минимальное по модулю по сравнению со вееми остальными решениями системы. Действительно, в примере 5.5 было найдено общее решение рассматриваемой системы


x=\begin{pmatrix}3\\-2\\0\\0\end{pmatrix}+ C_1\cdot\! \begin{pmatrix}-6\\4\\1\\0 \end{pmatrix}+ C_2\cdot\! \begin{pmatrix}-2\\1\\0\\1\end{pmatrix}= \begin{pmatrix}3-6C_1-2C_2\\ -2+4C_1+C_2\\ C_1\\C_2\end{pmatrix}\!.

Модуль этого столбца имеет выражение


\begin{vmatrix}x\end{vmatrix}= \sqrt{(3-6C_1-2C_2)^2+(-2+4C_1+C_2)^2+C_1^2+C_2^2}\,.

Вместо минимизации модуля будем искать минимум его квадрата, чтобы избавиться от квадратного корня. Эти задачи, разумеется, эквивалентны, так как точки минимума неотрицательной функции и ее квадрата совпадают. Итак, будем искать минимум функции


f(C_1,C_2)=|x|^2= (3-6C_1-2C_2)^2+(-2+4C_1+C_2)^2+C_1^2+C_2^2,

зависящей от двух переменных.


Для нахождения стационарных точек приравниваем частные производные первого порядка нулю (применяем необходимое условие экстремума):


\begin{aligned} \frac{\partial f}{\partial C_1}&= 2(3-6C_1-2C_2)(-6)+2(-2+4C_1+C_2)(4)+2C_1=0,\\[5pt] \frac{\partial f}{\partial C_2}&= 2(3-6C_1-2C_2)(-2)+2(-2+4C_1+C_2)+2C_2=0. \end{aligned}

Упрощая уравнения, получаем систему \begin{cases}53C_1+16C_2=26,\\16C_1+6C_2=8,\end{cases} которую решаем, например, по правилу Крамера:


C_1=\frac{\Delta_1}{\Delta}= \dfrac{\begin{vmatrix}26&16\\8&6\end{vmatrix}}{\begin{vmatrix}53&16\\16&6\end{vmatrix}}=\frac{28}{62}=\frac{14}{31};\quad C_2=\frac{\Delta_2}{\Delta}= \dfrac{\begin{vmatrix}53&26\\16&8\end{vmatrix}}{\begin{vmatrix}53&16\\16&6\end{vmatrix}}=\frac{8}{62}=\frac{4}{31}\,,

Поскольку угловые миноры матрицы Гессе H=\begin{pmatrix}53&16\\16&6 \end{pmatrix} положительные:\Delta_1=53>0, \Delta_2=53\cdot6-16^2>0, то найденная стационарная точка \left(\frac{14}{31};\,\frac{4}{31}\right) является точкой минимума.


Следовательно, наименьший модуль среди всех решений системы имеет решение


\widetilde{x}= \begin{pmatrix}3\\-2\\0\\0\end{pmatrix}+\frac{14}{31}\cdot\! \begin{pmatrix}-6\\4\\1\\0\end{pmatrix}+ \frac{4}{31}\cdot\! \begin{pmatrix}-2\\1\\0\\1\end{pmatrix}= \frac{1}{31}\cdot\! \begin{pmatrix}1\\-2\\14\\4\end{pmatrix}\!,

что совпадает с ранее найденным псевдорешением.




Пример 5.9. Найти псевдорешение системы линейный уравнений


\begin{cases}x_1-x_2=6,\\ -x_1+2x_2+x_3=9,\\ 2x_1-3x_2-x_3=-9,\\ x_2+x_3=18. \end{cases}

Решение. Нетрудно заметить, что эта система несовместна (сложив второе и третье уравнения, получим уравнение x_1-x_2=0, которое противоречит первому уравнению системы). Составим матрицу системы


A=\begin{pmatrix}1&-1&0\\-1&2&1\\2&-3&-1\\0&1&1\end{pmatrix}\!.

Псевдообратная матрица для матрицы A была найдена в примере


A^{\sim1}= \begin{pmatrix}1/3&1/9&2/9&4/9\\ 0&1/9&-1/9&1/9\\ 1/3&2/9&1/9&5/9 \end{pmatrix}\!.

2. По формуле (5.28) получаем псевдорешение


\widetilde{x}=A^{\sim1}b= \begin{pmatrix}1/3&1/9&2/9&4/9\\ 0&1/9&-1/9&1/9\\ 1/3&2/9&1/9&5/9 \end{pmatrix}\!\cdot\! \begin{pmatrix}6\\9\\-9\\18\end{pmatrix}= \begin{pmatrix} 9\\4\\13\end{pmatrix}\!.

Покажем, что это решение минимизирует погрешность \varepsilon(x)=|Ax-b|. Для этого найдем минимум квадрата этой функции (см. пример 5.8)


\varepsilon^2(x)= |Ax-b|^2= (x_1-x_2-6)^2+ (-x_1+2x_2+x_3-9)^2+ (2x_1-3x_2-x_3+9)^2+ (x_2+x_3-18)^2.

2. Приравнивая к нулю частные производные по переменным x_1,\,x_2,\,x_3, получаем после упрощений систему уравнений


\begin{cases}2x_1-3x_2-x_3=-7,\\ -3x_1+5x_2+2x_3=19,\\ -x_1+2x_2+x_3=12.\end{cases}

Методом Гаусса находим общее решение этой системы (5.29)


\begin{cases}x_1=22-x_3,\\x_2=17-x_3,\end{cases}

где x_3 — свободная переменная. Следовательно, функция \varepsilon(x) имеет бесконечно много стационарных точек, на которых достигается ее наименьшее значение. Заметим, что найденное псевдорешение \widetilde{x} принадлежит этому множеству. Покажем теперь, что \widetilde{x} — это наименьший по модулю элемент множества (5.29). Для этого составим функцию, равную квадрату модуля решения


x=\begin{pmatrix}22-x_3&17-x_3&x_3\end{pmatrix}^T\colon\,~ f(x_3)=|x|^2= (22-x_3)^2+(17-x_3)^2+x_3^2.

Найдем точку минимума этой функции одной переменной:


f'(x_3)= 2(22-x_3)(-1)+ 2(17-x_3)(-1)+2x_3=0~~ \Rightarrow~~ x_3=13.

Поскольку функция выпуклая, наименьшее по модулю решение (5.29) получается при x_3=13. Это решение совпадает с найденным ранее псевдорешением \widetilde{x}= \begin{pmatrix}9&4&13\end{pmatrix}^T.

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"
Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.

Часовой пояс: UTC + 3 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved