2014 dxdy logo

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

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




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


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

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


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

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


11/05/08
31889
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
6518
ewert, я бы просил Вас полностью формализовать постановку задачи: указать размеры матриц, указать способ задания скалярного произведения (и в каком пространстве оно задано), объяснить, что значит фраза "скалярное произведение задано матрицей" и т.д. Иначе утверждения типа "такая-то матрица является матрицей Грама" будет трудно обсуждать. Если бы Вы рассказали, как Вы излагаете МНК, стало бы яснее, в чём проблема.

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


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


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


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

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


11/05/08
31889
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
6518
Ну а если скрестить теорему 3 и это утверждение? Я не понимаю, зачем нужно это промежуточное звено --- система уравнений в виде $A^*_{MN}Ax=A^*_{MN}f$. Доказательство напрямую очень простое и из самых общих соображений.

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


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

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

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

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

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


20/12/10
6518
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
31889
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
6518
ewert в сообщении #874582 писал(а):
В общем, занудство
Более чем.

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


11/05/08
31889
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
6518
А мой-то вариант как?

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


11/05/08
31889
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
6518
ewert в сообщении #874619 писал(а):
На мой вкус, он несколько бесчеловечно оформлен.
Да, возможно :)

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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