Про псевдорешения

[g______d]

Ладно, я всё ещё не могу сказать, что дано, а что надо доказать. Я думал, что всё, что написано, – дано. Вот например, является ли очевидной причиной тот факт, что $A^*A$ всегда матрицей Грама, если операция сопряжения согласована со скалярным произведением?

[nnosipov]

ewert в сообщении #874087 писал(а):

Известно, что $\|Ax-f\|=\mathrm{min} \ \Leftrightarrow\ A^*Ax=A^*f$.

Нужно уточнять постановку этой методической задачи. Что такое $A$? Это матрица? линейный оператор? И вообще, каков контекст этой задачи? Одна из возможных интерпретаций (и, на мой взгляд, самая простая) --- чисто геометрическая, без каких бы то ни было операторов (и тем более сопряжённых) и их образов. Требуется только понимание того, что такое абстрактное евклидово пространство. Ежели студентам нужно объяснить что-то другое на примере этой задачи, то что именно?

[ewert]

nnosipov в сообщении #874195 писал(а):

Что такое $A$? Это матрица? линейный оператор? И вообще, каков контекст этой задачи?

Это, конечно, именно матрица, а контекст -- это метод наименьших квадратов. Его схема на языке скалярных произведений столбцов узловых значений базисных функций (т.е. вот именно что матрицы Грама) выглядит наиболее лаконично, а следует эта схема из теоремы "$\|Ax-f\|=\mathrm{min} \ \Leftrightarrow\ A^*Ax=A^*f$" мгновенно.

g______d в сообщении #874192 писал(а):

Вот например, является ли очевидной причиной тот факт, что $A^*A$ всегда матрицей Грама, если операция сопряжения согласована со скалярным произведением?

Это не причина, а именно то, что требуется. В том и проблема, что мне это не кажется очевидным в общем случае (для стандартного-то скалярного произведения это тривиально). Причём речь идёт о курсе вовсе не алгебры (второкурсники к этому моменту алгебру уже давно сдали, причём сдали очень глубоко), а о курсе численных методов, поэтому перегружать их линейноалгебраическими штучками не хочется.

Произвольного же скалярного произведения хочется потому, что метод наименьших квадратов бывает (причём бывает сугубо практически) ещё и весовым. Конечно, это тоже лишь очень частный случай скалярного произведения, и тем не менее: если соотв. обобщение понятия псевдорешения есть, то схема МНК выскакивает автоматом, иначе же приходится как-то ковыряться.

-- Чт июн 12, 2014 11:19:36 --

Да, пардон:

g______d в сообщении #874192 писал(а):

$A^*A$ всегда матрицей Грама

Это, кстати, неверно: матрицей Грама будет $A^*MA$, в то время как $A^*_MA=M^{-1}A^*MA$ (где $M$ -- положительная матрица, задающая скалярное произведение; потом-то лишняя $M^{-1}$ сократится, конечно).

[nnosipov]

ewert, я бы просил Вас полностью формализовать постановку задачи: указать размеры матриц, указать способ задания скалярного произведения (и в каком пространстве оно задано), объяснить, что значит фраза "скалярное произведение задано матрицей" и т.д. Иначе утверждения типа "такая-то матрица является матрицей Грама" будет трудно обсуждать. Если бы Вы рассказали, как Вы излагаете МНК, стало бы яснее, в чём проблема.

Как пример подобной формализации, могу привести текст решения одной хорошо известной учебной задачи на схожую тему (мы её тоже раньше обсуждали).

[g______d]

ewert в сообщении #874494 писал(а):

Это, кстати, неверно

Да, я должен был сказать "в ортонормированном базисе, отвечающем тому же скалярному произведению", но тогда и задачи нет.

[ewert]

nnosipov в сообщении #874519 писал(а):

указать размеры матриц,

Да, Вы правы -- матрицы, вообще говоря, неквадратные, поэтому с обозначениями надо быть аккуратнее.

Теорема 1. Любое скалярное произведение в пространстве $\mathbb R^n$ или $\mathbb C^n$ задаётся билинейной формой некоторой положительно определённой матрицы.
(общеизвестно)

Далее обозначаем $(x,y)_M\equiv(Mx,y)$, где $(u,v)\equiv\sum\limits_{k=1}^nu_k\overline v_k$ -- стандартное скалярное произведение; соответственно, $\|x\|_M\equiv\sqrt{(x,x)_M}$ и $\|x\|\equiv\sqrt{(x,x)}.$

Определение. Матрица $B$ называется сопряжённой к матрице $A$ относительно соответствующей пары скалярных произведений (обозначение: $B=A^*_{MN}$), если $(Ax,y)_M=(x,By)_N\ (\forall x\in\mathbb C^n,\;y\in\mathbb C^m)$.

(Здесь пометки $M,N$ сами по себе излишни, но они нужны для дальнейшего и просто для того, чтобы иметь право под $(\cdot,\cdot)$ понимать стандартное.) Матрицу, сопряжённую относительно стандартных скалярных произведений, будем обозначать как просто $A^*.$

Теорема 2. $B=A^*\ \Leftrightarrow\ b_{ik}\equiv\overline a_{ki}.$

Теорема 3. $\|Ax-f\|_M\leqslant\|Ay-f\|_M\ (\forall y)\ \Leftrightarrow\ A^*_{MN}Ax=A^*_{MN}f.$

--------------------------------------------------------
Эти факты -- совершенно стандартны, хотя при стандартных построениях курса идут в другом порядке (и в определении сопряжённой матрицы конкретизация скалярных произведений не нужна). Требуется же вот что. Обозначим через $\{a_i\}$ столбцы матрицы $A$.

$\text{{\bf Утверждение.} \it Систему уравнений }A^*_{MN}Ax=A^*_{MN}f\ \text{\it можно записать как }\ Gx=b, \text{\it\ где } g_{ik}=(a_k,a_i)_M \text{\it\ и }b_i=(f,a_i)_M .$

Это следует из того, что $A^*_{MN}=N^{-1}A^*M$, но не совсем сразу следует, да и само это равенство требует доказательства. А меня интересует, нельзя ли при для получения последнего утверждения обойтись без этого занудства.

[nnosipov]

Ну а если скрестить теорему 3 и это утверждение? Я не понимаю, зачем нужно это промежуточное звено --- система уравнений в виде $A^*_{MN}Ax=A^*_{MN}f$. Доказательство напрямую очень простое и из самых общих соображений.

[ewert]

nnosipov в сообщении #874550 писал(а):

Доказательство напрямую очень простое и из самых общих соображений.

Ну скрестите, буду признателен; у меня как-то не выходит.

nnosipov в сообщении #874550 писал(а):

Я не понимаю, зачем нужно это промежуточное звено --- система уравнений в виде $A^*_{MN}Ax=A^*_{MN}f$.

Нет, тот факт, что умножение происходит на сопряжённую матрицу (точнее, на сопряжённый оператор) -- он идеен. А вот второй вариант записи этой системы уже использует конечномерную специфику, и его идейность имеет совершенно другой характер.

[nnosipov]

ewert в сообщении #874556 писал(а):

Ну скрестите, буду признателен; у меня как-то не выходит.

Хорошо. Чуть позже, нужно переписать в Ваших обозначениях.

ewert в сообщении #874556 писал(а):

Нет, тот факт, что умножение происходит на сопряжённую матрицу (точнее, на сопряжённый оператор) -- он идеен.

Окей.

-- Чт июн 12, 2014 18:08:20 --

ewert в сообщении #874543 писал(а):

Да, Вы правы -- матрицы, вообще говоря, неквадратные, поэтому с обозначениями надо быть аккуратнее.

Уточняю размеры: $A=A_{n \times m}$, $x=x_{m \times 1} \in \mathbb{R}^m$, $f=f_{n \times 1} \in \mathbb{R}^n$. Тогда $Ax-f=(Ax-f)_{n \times 1}$ и матрица, задающая скалярное произведение, есть $M=M_{n \times n}$ (т.е. речь будет идти о скалярном произведении в $\mathbb{R}^n$). Пусть $a_i \in \mathbb{R}^n$ ($i=1,\dots,m$) --- столбцы матрицы $A$, $G=((a_i,a_j)_M)_{i,j=1}^m$ --- их матрица Грама, $b=b_{m \times 1} \in \mathbb{R}^m$ --- столбец скалярных произведений $(a_i,f)_M$ ($i=1,\dots,m$).

Теорема. $\min\limits_{y \in \mathbb{R}^m}{\|Ay-f\|_M}=\|Ax-f\|_M$ тогда и только тогда, когда $Gx=b$.

Ещё раз спрошу: доказательство именно этой теоремы нужно? У меня такое ощущение, что Вы сами её раньше уже доказывали (в той теме, ссылку на которую я давал выше).

Доказательство. Пусть $L \subset \mathbb{R}^n$ --- линейная оболочка $a_i$ ($i=1,\dots,m$), $\overline{y}=Ay=y_1a_1+\ldots+y_ma_m \in L$, $\overline{x}=Ax=x_1a_1+\ldots+x_ma_m \in L$, $f=f'+f''$, где $f' \in L$, $f'' \in L^\perp$ ($\perp=\perp_M$). Тогда:
1) Система $Gx=b$ --- это система $(a_i,\overline{x})_M=(a_i,f)_M$, $i=1,\dots,m$, а последняя равносильна системе $(a_i,\overline{x})_M=(a_i,f')_M$, $i=1,\dots,m$.
2) Равенство $\min\limits_{y \in \mathbb{R}^m}{\|Ay-f\|_M}=\|Ax-f\|_M$ равносильно равенству $\overline{x}=f'$ (следствие теоремы Пифагора).
3) Равенство $\overline{x}=f'$ равносильно системе $(a_i,\overline{x})_M=(a_i,f')_M$,$i=1,\dots,m$.

Ну как, годится?

[ewert]

nnosipov в сообщении #874558 писал(а):

Теорема. $\min\limits_{y \in \mathbb{R}^m}{\|Ay-f\|_M}=\|Ax-f\|_M$ тогда и только тогда, когда $Gx=b$.

Ещё раз спрошу: доказательство именно этой теоремы нужно?

Не совсем. Во-первых, мне хочется исходить не из определения псевдорешения, а именно из системы $A^*_{MN}Ax=A^*_{MN}f$. Во-вторых (хотя это и несущественно), мне нужен комплексный вариант. Впрочем, если Вы докажете именно эту теорему -- тоже будет интересно.

nnosipov в сообщении #874558 писал(а):

У меня такое ощущение, что Вы сами её раньше уже доказывали (в той теме, ссылку на которую я давал выше).

Насколько я помню, нет, и в той теме тоже никакого доказательства не приводил. На всякий случай приведу сейчас.

$$\begin{array} BB=A^*_{MN}\ \Leftrightarrow\ (Ax,y)_M\equiv(x,By)_N\ \Leftrightarrow\ (MAx,y)\equiv(Nx,By)\ \Leftrightarrow \\ \\ \Leftrightarrow\ (x,A^*My)\equiv(x,NBy)\ \Leftrightarrow\ A^*M=NB\ \Leftrightarrow\ B=N^{-1}A^*M;\end{array}$$

$$A^*_{MN}Ax=A^*_{MN}f\ \Leftrightarrow\ N^{-1}A^*MAx=N^{-1}A^*Mf\ \Leftrightarrow\ A^*MAx=A^*Mf;$$

$$b=A^*Mf\ \Leftrightarrow\ b_i=\sum\limits_{j,k=1}^m(A^*)_{ij}\mu_{jk}f_k=\sum\limits_{j,k=1}^m\mu_{jk}f_k\overline a_{ji}=(f, a_i)_M;$$

$$G=A^*MA\ \Leftrightarrow\ g_{ik}=\sum\limits_{j,l=1}^m(A^*)_{ij}\mu_{jl}a_{lk}=\sum\limits_{j,l=1}^m\mu_{jl}a_{lk}\overline a_{ji}=(a_k, a_i)_M.$$

В общем, занудство (в том смысле, что окончательный результат выглядит гораздо проще, чем доказательство).

[nnosipov]

ewert в сообщении #874582 писал(а):

В общем, занудство

Более чем.

[ewert]

nnosipov в сообщении #874585 писал(а):

Более чем.

Ну альтернативный вариант такой:

$\|A\vec x-\vec f\|^2=\|\sum\limits_kx_k\vec a_k-\vec f\|^2=\sum\limits_{i,k}x_i\overline x_k(\vec a_i,\vec a_k)-2\operatorname{Re}\sum\limits_kx_k(\vec a_k,\vec f)+\|\vec f\|^2=$

$=\sum\limits_{i,k}g_{ki}x_i\overline x_k-2\operatorname{Re}\sum\limits_kx_k\overline b_k+\|\vec f\|^2=(G\vec x,\vec x)-2\operatorname{Re}(\vec x,\vec b)+\|\vec f\|^2=\min.$

Минимизация последнего выражения равносильна решению системы $G\vec x=\vec b$, но тут свои неприятности. Во-первых, эту теорему (о сведении системы к минимизации "энергетического" функционала) дают в курсе алгебры не всем; во-вторых, если и дают, то для положительных матриц, а нужно для неотрицательных. Кроме того, несколько жаль терять сопряжённую матрицу.

На самом деле я в зависимости от настроения даю иногда первый способ, а иногда второй; и ни тот, ни другой не особо нравится.

[nnosipov]

А мой-то вариант как?

[ewert]

nnosipov в сообщении #874601 писал(а):

А мой-то вариант как?

Я его, естественно, не заметил -- Вы же его потом добавили.

На мой вкус, он несколько бесчеловечно оформлен. Попробую пересказать то же самое немножко другими словами.

По теореме о проекции $\|A\vec x-f\|=\min$ равносильно тому, что $A\vec x$ -- это проекция вектора $\vec f$ на образ матрицы $A$, т.е. на линейную оболочку её столбцов. Это означает, что вектор $A\vec x-\vec f$ ортогонален этой оболочке (*) или, что эквивалентно, ортогонален каждому из столбцов:

$$(A\vec x-\vec f,\vec a_i)=0\ (\forall i)\ \Leftrightarrow\ \left[A\vec x=\sum\limits_kx_k\vec a_k\right]\ \Leftrightarrow\ \sum\limits_k(x_k\vec a_k,\vec a_i)=(\vec f,\vec a_i)\ (\forall i)\ \Leftrightarrow$$

$$\Leftrightarrow\ \sum\limits_kg_{ik}x_k=b_i\ (\forall i) \Leftrightarrow\ G\vec x=\vec b.$$

Да, так лучше, спасибо.

----------------------------------------------------
(*) Здесь развилка: именно отсюда естественным образом получается система $A^*A\vec x=A^*\vec f$.

[nnosipov]

ewert в сообщении #874619 писал(а):

На мой вкус, он несколько бесчеловечно оформлен.

Да, возможно :)