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

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

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

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

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


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

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


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


[math]Ax=b[/math]
(5.27)

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

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


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


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

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


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


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


[math]\wudetilde{x}= A^{\sim1}\cdot b,[/math]

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


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




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


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


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


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


[math]\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}[/math]

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


[math]\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.[/math]

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


[math]\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}[/math]

Вычисляем матрицы
[math]\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}[/math]

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


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

[math]=\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}=[/math]

[math]=\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}=[/math]

[math]= \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}=[/math]

[math]= \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}\!.[/math]

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


[math]\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}\!.[/math]

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


[math]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}\!.[/math]

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

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

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


[math]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,[/math]

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

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


[math]\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}[/math]

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


[math]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}\,,[/math]

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


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


[math]\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}\!,[/math]

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



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


[math]\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}[/math]

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


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

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


[math]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}\!.[/math]

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


[math]\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}\!.[/math]

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


[math]\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.[/math]

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


[math]\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}[/math]

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


[math]\begin{cases}x_1=22-x_3,\\x_2=17-x_3,\end{cases}[/math]

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


[math]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.[/math]

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


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

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


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


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

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