УказательРазделыОбозначенияАвторО проекте


§

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


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}.


2015/06/24 00:11 редактировал au