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


§

Вспомогательная страница к разделу МЕТОД НАИМЕНЬШИХ КВАДРАТОВ.


T

Теорема. Существует псевдорешение системы $$ AX={\mathcal B} $$ и оно является решением нормальной системы $$ \left[A^{\top}A \right]X=A^{\top} {\mathcal B} \ . $$ Это решение будет единственным тогда и только тогда, когда $ \operatorname{rank} A =n_{} $.

Доказательство. Как обычно, $ A^{[i]} $ обозначает $ i_{} $-ю строчку матрицы $ A_{} $, а $ A_{[j]} $ — ее $ j_{} $-й столбец. На основании теоремы из пункта "ЭКСТРЕМУМЫ ПОЛИНОМА" точка экстремума функции $$ F(X)= \sum_{i=1}^m [a_{i1}x_1 +a_{i2}x_2+\ldots+a_{in}x_n-b_i]^2= \sum_{i=1}^m [A^{[i]}X-b_i]^2 $$ ищется из условий $$ \partial F / \partial x_1=0, \dots, \partial F / \partial x_n=0 \ . $$ Распишем выражение для $ \partial F / \partial x_j $: $$ \partial F / \partial x_j=\sum_{i=1}^m 2\,[ A^{[i]}X-b_i] \frac{\partial (a_{i1}x_1 +a_{i2}x_2+\ldots+a_{in}x_n)}{\partial x_j}= 2\, \sum_{i=1}^m [A^{[i]}X-b_i]\, a_{ij}=$$ $$= 2\left[\left(a_{1j}A^{[1]}+\dots+a_{mj}A^{[m]}\right)X -\left(a_{1j}b_1+\dots+ a_{mj}b_m \right)\right]=2\,\left[A_{[j]}^{\top}AX- A_{[j]}^{\top} {\mathcal B}\right].$$ Таким образом, условия $ \{ \partial F / \partial x_j=0 \}_{j=1}^n $ эквивалентны следующим $$A_{[1]}^{\top}AX=A_{[1]}^{\top}{\mathcal B}, \dots, A_{[n]}^{\top}AX =A_{[n]}^{\top}{\mathcal B} \iff A^{\top} A X= A^{\top} {\mathcal B} \ .$$ Итак, если существует псевдорешение системы $ AX={\mathcal B} $, то оно обязательно должно быть (обычным) решением нормальной системы $$ A^{\top} A X= A^{\top} {\mathcal B} \ . $$ Покажем теперь, что последняя система всегда совместна. Предположим сначала, что $ \operatorname{rank} A=n $. Для доказательства единственности решения нормальной системы в этом случае, вычислим определитель матрицы $ A^{\top}A $ с помощью теоремы Бине--Коши. Если $ m=n_{} $, то $$\det (A^{\top} A) = \det A^{\top} \det A = (\det A)^2 \ .$$ Если же $ m>n_{} $, то $$ \det (A^{\top} A)= $$ $$ = \sum_{1\le j_1<\dots<j_n \le m } \left| \begin{array}{llll} a_{j_11} & a_{j_21} & \dots & a_{j_n1} \\ a_{j_12} & a_{j_22} & \dots & a_{j_n2} \\ \dots & & & \dots \\ a_{j_1n} & a_{j_2n} & \dots & a_{j_nn} \end{array} \right|\cdot \left| \begin{array}{llll} a_{j_11} & a_{j_12} & \dots & a_{j_1n} \\ a_{j_21} & a_{j_22} & \dots & a_{j_2n} \\ \dots & & & \dots \\ a_{j_n1} & a_{j_n2} & \dots & a_{j_nn} \end{array} \right| =$$ $$ = \sum_{1\le j_1<\dots<j_n \le m } \left| \begin{array}{llll} a_{j_11} & a_{j_12} & \dots & a_{j_1n} \\ a_{j_21} & a_{j_22} & \dots & a_{j_2n} \\ \dots & & & \dots \\ a_{j_n1} & a_{j_n2} & \dots & a_{j_nn} \end{array} \right|^2 \ge 0\ . $$ По предположению $ \operatorname{rank} A=n $. В случае $ m=n_{} $ это означает, что $ \det A \ne 0 $, но тогда и $ \det (A^{\top} A) > 0 $. В случае $ m>n_{} $ то же условие означает существование у матрицы $ A_{} $ хотя бы одного минора порядка $ n_{} $ отличного от нуля. Соответствующее слагаемое в последней сумме строго положительно, и снова $ \det (A^{\top} A) > 0 $. По теореме Крамера, нормальная система имеет единственное решение.

Пусть теперь $ \operatorname{rank} A={\mathfrak r}<n $. Такое может произойти, например, когда $ m<n $. Докажем, сначала, что $ \operatorname{rank} (A^{\top}A)={\mathfrak r} $. Теорема Сильвестра утверждает, что $$ \operatorname{rank} (A^{\top}A)\le \operatorname{rank} A={\mathfrak r} \, . $$ Установим теперь существование ненулевого минора порядка $ {\mathfrak r}_{} $ для матрицы $ C=A^{\top}A $. Предположим для определенности, что ненулевой минор порядка $ {\mathfrak r}_{} $ матрицы $ A_{} $ находится в ее столбцах с номерами $ 1,\dots,{\mathfrak r} $. Тогда $$ C \left( \begin{array}{ccc} 1 & \dots & {\mathfrak r} \\ 1 & \dots & {\mathfrak r} \end{array} \right)=\det \left( \left[ \begin{array}{llcl} a_{11} & a_{21}& \dots & a_{m1} \\ a_{12} & a_{22}& \dots & a_{m2} \\ \dots & & & \dots \\ a_{1{\mathfrak r}} & a_{2{\mathfrak r}}& \dots & a_{m{\mathfrak r}} \end{array} \right] \cdot \left[ \begin{array}{llcl} a_{11} & a_{12}& \dots & a_{1{\mathfrak r}} \\ a_{21} & a_{22}& \dots & a_{2{\mathfrak r}} \\ \dots & & & \dots \\ a_{m1} & a_{m2}& \dots & a_{m{\mathfrak r}} \end{array} \right] \right) \ . $$ Применяем теорему Бине-Коши, и, рассуждая по аналогии с предыдущей частью доказательства, придем к заключению, что данный минор матрицы $ A^{\top}A $ отличен от нуля. Итак, $ \operatorname{rank} (A^{\top}A)={\mathfrak r} $.

Вычислим теперь ранг расширенной матрицы нормальной системы. С одной стороны: $${\mathfrak r}=\operatorname{rank} \left(A^{\top}A \right) \le \operatorname{rank} \left[ A^{\top}A \mid A^{\top} {\mathcal B} \right] \ .$$ С другой стороны, на основании теоремы Сильвестра, имеем: $$ \operatorname{rank} \left[ A^{\top}A \mid A^{\top} {\mathcal B} \right] = \operatorname{rank} A^{\top} \left[ A \mid {\mathcal B} \right] \le \operatorname{rank} A^{\top}={\mathfrak r} \ . $$ Два неравенства приводят к заключению: расширенная матрица нормальной системы имеет ранг $ {\mathfrak r} $. На основании теоремы Кронекера--Капелли делаем вывод: в этом случае нормальная система совместна и имеет бесконечное множество решений.

Докажем теперь, что любое решение $ X_{\ast} $ нормальной системы доставляет функции $ F_{} $ именно значение минимума. С этой целью найдем выражение для разности $ F(X)-F(X_{\ast}) $. Выражение для функции $ F_{} $ можно записать в матричном виде: $$F(X)=(AX-{\mathcal B})^{\top}(AX-{\mathcal B}) \ .$$ Тогда $$F(X)-F(X_{\ast})=(AX-{\mathcal B})^{\top}(AX-{\mathcal B}) - (AX_{\ast}-{\mathcal B})^{\top}(AX_{\ast}-{\mathcal B})=$$ $$ =(AX-{\mathcal B})^{\top}(AX-{\mathcal B}) - (AX_{\ast}-{\mathcal B})^{\top}(AX-{\mathcal B}) + $$ $$ + (AX_{\ast}-{\mathcal B})^{\top}(AX-{\mathcal B}) - (AX_{\ast}-{\mathcal B})^{\top}(AX_{\ast}-{\mathcal B})= $$ $$=(AX-AX_{\ast})^{\top}(AX-{\mathcal B})+(AX_{\ast}-{\mathcal B})^{\top}(AX-AX_{\ast})= $$ $$= (X-X_{\ast})^{\top}A^{\top}(AX-{\mathcal B})+(AX_{\ast}-{\mathcal B})^{\top}A(X-X_{\ast})=$$ $$= (X-X_{\ast})^{\top}(A^{\top}AX-A^{\top}{\mathcal B})+(A^{\top}AX_{\ast}-A^{\top}{\mathcal B})^{\top}(X-X_{\ast})= $$ и воспользуемся теперь тем, что $ A^{\top}AX_{\ast}=A^{\top}{\mathcal B} $: $$=(X-X_{\ast})^{\top}(A^{\top}AX-A^{\top}AX_{\ast})=(X-X_{\ast})^{\top}A^{\top}A(X-X_{\ast})= $$ $$ =\sum_{i=1}^m \left[A^{[i]} (X-X_{\ast}) \right]^2 \ge 0 $$ при любом столбце $ X_{} $. Таким образом, при $ X=X_{\ast} $ функция $ F(X_{}) $ действительно имеет минимум. При каком условии этот минимум будет строгим? Последнее неравенство обращается в равенство только когда $ X_{} $ удовлетворяет условию $ A(X-X_{\ast})=\mathbb O $. В случае когда $ \operatorname{rank}(A)=n_{} $ это условие выполняется только при $ X_{}=X_{\ast} $.

interpolation/mnk/vspom1.txt · Последние изменения: 2020/07/03 17:38 — au