2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Про псевдорешения
Сообщение11.06.2014, 05:23 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Про псевдорешения
Сообщение11.06.2014, 06:17 
Заслуженный участник


20/12/10
9179
ewert в сообщении #874087 писал(а):
Известно, что $\|Ax-f\|=\mathrm{min} \ \Leftrightarrow\ A^*Ax=A^*f$.
Нужно уточнять постановку этой методической задачи. Что такое $A$? Это матрица? линейный оператор? И вообще, каков контекст этой задачи? Одна из возможных интерпретаций (и, на мой взгляд, самая простая) --- чисто геометрическая, без каких бы то ни было операторов (и тем более сопряжённых) и их образов. Требуется только понимание того, что такое абстрактное евклидово пространство. Ежели студентам нужно объяснить что-то другое на примере этой задачи, то что именно?

 Профиль  
                  
 
 Re: Про псевдорешения
Сообщение12.06.2014, 10:07 
Заслуженный участник


11/05/08
32166
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}$ сократится, конечно).

 Профиль  
                  
 
 Re: Про псевдорешения
Сообщение12.06.2014, 11:19 
Заслуженный участник


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

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


Вложения:
problem-new.pdf [131.93 Кб]
Скачиваний: 255
 Профиль  
                  
 
 Re: Про псевдорешения
Сообщение12.06.2014, 11:37 
Заслуженный участник
Аватара пользователя


08/11/11
5940
ewert в сообщении #874494 писал(а):
Это, кстати, неверно


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

 Профиль  
                  
 
 Re: Про псевдорешения
Сообщение12.06.2014, 12:27 
Заслуженный участник


11/05/08
32166
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$, но не совсем сразу следует, да и само это равенство требует доказательства. А меня интересует, нельзя ли при для получения последнего утверждения обойтись без этого занудства.

 Профиль  
                  
 
 Re: Про псевдорешения
Сообщение12.06.2014, 12:53 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Про псевдорешения
Сообщение12.06.2014, 13:06 
Заслуженный участник


11/05/08
32166
nnosipov в сообщении #874550 писал(а):
Доказательство напрямую очень простое и из самых общих соображений.

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

nnosipov в сообщении #874550 писал(а):
Я не понимаю, зачем нужно это промежуточное звено --- система уравнений в виде $A^*_{MN}Ax=A^*_{MN}f$.

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

 Профиль  
                  
 
 Re: Про псевдорешения
Сообщение12.06.2014, 13:13 
Заслуженный участник


20/12/10
9179
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$.

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

 Профиль  
                  
 
 Re: Про псевдорешения
Сообщение12.06.2014, 14:51 
Заслуженный участник


11/05/08
32166
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.$$
В общем, занудство (в том смысле, что окончательный результат выглядит гораздо проще, чем доказательство).

 Профиль  
                  
 
 Re: Про псевдорешения
Сообщение12.06.2014, 15:03 
Заслуженный участник


20/12/10
9179
ewert в сообщении #874582 писал(а):
В общем, занудство
Более чем.

 Профиль  
                  
 
 Re: Про псевдорешения
Сообщение12.06.2014, 15:31 
Заслуженный участник


11/05/08
32166
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$, но тут свои неприятности. Во-первых, эту теорему (о сведении системы к минимизации "энергетического" функционала) дают в курсе алгебры не всем; во-вторых, если и дают, то для положительных матриц, а нужно для неотрицательных. Кроме того, несколько жаль терять сопряжённую матрицу.

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

 Профиль  
                  
 
 Re: Про псевдорешения
Сообщение12.06.2014, 15:38 
Заслуженный участник


20/12/10
9179
А мой-то вариант как?

 Профиль  
                  
 
 Re: Про псевдорешения
Сообщение12.06.2014, 16:33 
Заслуженный участник


11/05/08
32166
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$.

 Профиль  
                  
 
 Re: Про псевдорешения
Сообщение12.06.2014, 16:43 
Заслуженный участник


20/12/10
9179
ewert в сообщении #874619 писал(а):
На мой вкус, он несколько бесчеловечно оформлен.
Да, возможно :)

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 30 ]  На страницу Пред.  1, 2

Модераторы: Модераторы, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: dgwuqtj


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group