Опять МФТИ

Ian · Сообщение **Ian** » 16 дек 2019, 05:46

3-6 курс.4.
Предположим, в единичном шаре некоторого евклидова пространства находится

2m точек

x_1,...x_{2m}. Докажите, что их можно разбить на два множества по

m точек каждое таким образом, что центры масс этих множеств окажутся на расстоянии не более

\frac 2{\sqrt m} друг от друга
Соображения по решению.
Для

2m точек можно найти

(2m-1)-мерную гиперплоскость, содержащую все точки, в сечении гиперплоскостью любого единичного шара получится шар радиуса не больше 1, поэтому можем далее считать, что размерность пространства равна

2m-1.

Например

m=2, для тетраэдра , вписанного в единичный шар, минимальное расстояние между серединами противоположных ребер у правильного тетраэдра,

d=\frac{2}{\sqrt{3}}<\sqrt{2}-требуемая оценка не для всех

m является точной

Пусть перемещением одной точки мы хотим максимально испортить возможность сделать центры тяжести близко. Тогда возьмем гиперплоскость, содержащую остальные точки, и перпендикулярную ей ось через их центр тяжести.

2m-ю точку отодвинем на этой оси так далеко от гиперплоскости, как позволяет объемлющий шар, на некоторое расстояние

d_{2m} Тогда мы точно можем сказать, что проекции центров тяжести на эту ось находятся на

\frac 1md_{2m} друг от друга, ведь одно множество содержит двинутую точку, другое нет.
А что изменяется - при оптимальном движении и гиперплоскость должна немного отодвинуться от центра шара и в сечении дать шар чуть меньшего диаметра (как плоскость основания вписанного правильного тетраэдра отодвинута от центра вниз, а вершина вверх до упора в шар). Попробовать отодвинуть 2 точки, каждую по своей новой координате, и будет какая-то рекуррентность по

m для конструкций . И сделать из этого рекуррентность для оценок

peregoudov · Сообщение **peregoudov** » 16 дек 2019, 12:33

А размерность евклидова пространства какая? Может быть, тут надо какие-то неравенства для первого и второго моментов употребить?

Ian · Сообщение **Ian** » 16 дек 2019, 15:45

судя по тексту, размерность как угодно велика. "Евклидово" -значит расстояние считается по теореме Пифагора.
Я показал, что размерность выше 2m-1 смотреть не стоит
Например, как частный случай может быть задача про 4 точки в шаре в двадцатимерном пространстве. Но тогда существует трехмерная гиперплоскость, содержащая все 4 точки, в пересечении с шаром она дает трехмерный шар радиуса не больше 1, и можно решать в нем.

peregoudov · Сообщение **peregoudov** » 18 дек 2019, 14:13

Да, я, как всегда, из вашей рваной речи не понял, о чем вы. Теперь понял с размерностью.

Меня в этой задаче смущает необходимость выбора. Нужно сформулировать какой-то критерий и доказать его. Причем просто добавлять точки не получится, потому что добавление новой пары может потребовать кардинально перестроить прежнее разбиение. Нужно начинать с того, что все точки уже даны. Была у меня еще идея вместо исходных точек рассматривать центры масс всех выборок m из 2m, но она пока ничего не дала...

peregoudov · Сообщение **peregoudov** » 18 дек 2019, 17:34

Собственно, похоже, что сработала еще одна идея: если не знаешь, как выбрать, попробуй доказать некую оценку для суммы всех вариантов, тогда из нее будет следовать оценка для по крайней мере одного из слагаемых.

Обозначим через $x_i$

радуис-векторы отдельных точек, а через $c_a$

--- радиус векторы всевозможных центров масс выборок m из 2m точек. Через $c_0$

обозначим центр масс всех 2m точек, он же --- центр масс всех центров масс. Тогда, если я правильно сосчитал (считал долго и муторно, но мне кажется, это должно быть как-то очевидно из матстатистики)

$\displaystyle\frac1{C_{2m}^m}\sum_a(c_a-c_0)^2=\frac1{2m-1}\frac1{2m}\sum_i(x_i-c_0)^2$

Сумму справа вроде бы можно мажорировать единицей, тогда по крайней мере для одной $c_a$

должно выполняться

$|c_a-c_0|<\frac1{\sqrt{2m-1}}.$

А расстояние между $c_a$

и центром масс остатка вдвое больше.

Ian · Сообщение **Ian** » 18 дек 2019, 21:59

peregoudov писал(а): мне кажется, это должно быть как-то очевидно из матстатистики)

Есть такая формула в дисперсионном анализе -общая дисперсия равна сумме межгрупповой и средней внутригрупповой дисперсий. Это результат сложного раскрытия скобок в сумме квадратов.
Группы будем считать - всевозможные наборы m точек. Каждая точка получается повторена в ген.совокупности ровно

C^{m-1}_{2m-1} раз
Межгрупповая средняя совпадает с общей средней, поэтому межгрупповая дисперсия и общая дисперсия считаются от одного центра

c_0. А внутригрупповые средние могут быть разные и куда их приткнуть

zykov · Сообщение **zykov** » 19 дек 2019, 02:28

peregoudov писал(а):Source of the post тогда по крайней мере для одной должно выполняться

$|c_a-c_0|<\frac1{\sqrt{2m-1}}.$

Вроде похоже на правду. По крайней мере для тетраэдра совпадает с экстремумом $\frac{1}{\sqrt 3}$ .
Это более строгая оценка, чем требовалось - $\frac{1}{\sqrt{m}}$ .
Наверно они имели ввиду какое-то другое, более простое, решение...

peregoudov · Сообщение **peregoudov** » 19 дек 2019, 11:40

Ian писал(а):Source of the post А внутригрупповые средние могут быть разные и куда их приткнуть

Я не понял, вы что-то имеете против моего решения?

Ian писал(а):Source of the post Каждая точка получается повторена в ген.совокупности ровно $C_{2m-1}^{m-1}$ раз

Собственно, так и считалось. Давайте тогда напишу детали расчета, раз возникают вопросы.

Но вообще из матстатистики результат довольно очевидный. Если у нас есть n измерений, а дисперсия каждого измерения $\sigma$ , то дисперсия среднего $\sigma/n$ . А тут как бы численная реализация: дисперсия считается по куче средних, взятых по разным выборкам.

zykov писал(а):Source of the post Наверно они имели ввиду какое-то другое, более простое, решение...

Мне кажется, идея была именно такая, как я написал выше. Просто не были уверены, какое число брать: размер выборки или размер полной совокупности.

Запишем среднее по выборке $a$

в виде

$c_a=\frac1m\sum_i a_ix_i.$

Здесь $a_i$

--- вектор длины 2m из нулей и единиц, среди компонент m единиц и m нулей. Теперь "дисперсия средних" представляется в виде

$\frac1{C_{2m}^m}\sum_a(c_a-c_0)^2=\frac1{m^2}\sum_{i,j}G_{ij}x_ix_j-c_0^2,\quad G_{ij}=\frac1{C_{2m}^m}\sum_a a_ia_j.$

Если $i=j$

, то члены суммы отличны от нуля при $a_i=1$

и произвольных остальных $a$

, всего $C_{2m-1}^{m-1}$ комбинаций. Если $i\neq j$ , то члены суммы отличны от нуля при $a_i=1$

,

и произвольных остальных $a$

, всего $C_{2m-2}^{m-2}$ комбинаций. Итого

$G_{ij}=\begin{cases} 1/2,&i=j,\\ (m-1)/2(2m-1),&i\neq j. \end{cases}$

Подставляя, получаем

$\frac1{C_{2m}^m}\sum_a(c_a-c_0)^2=\frac1{m^2}\sum_i\frac12x_i^2+\frac1{m^2}\sum_{i\neq j}\frac{m-1}{2(2m-1)}x_ix_j-c_0^2.$

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

$\frac1{C_{2m}^m}\sum_a(c_a-c_0)^2=\frac1{m^2}\sum_i\left(\frac12-\frac{m-1}{2(2m-1)}\right)x_i^2+ \frac1{m^2}\sum_{i,j}\frac{m-1}{2(2m-1)}x_ix_j-c_0^2.$

Первая сумма в результате дает $\displaystyle\frac1{2m-1}\frac1{2m}\sum_ix_i^2$ , вторая $\displaystyle\frac{2(m-1)}{2m-1}c_0^2$ , окончательно

$\frac1{C_{2m}^m}\sum_a(c_a-c_0)^2=\frac1{2m-1}\frac1{2m}\sum_ix_i^2-\frac1{2m-1}c_0^2=\frac1{2m-1}\frac1{2m}\sum_i(x_i-c_0)^2.$

zykov · Сообщение **zykov** » 19 дек 2019, 18:26

Да, у меня так же вышло.

peregoudov писал(а):Source of the post окончательно

$\frac1{C_{2m}^m}\sum_a(c_a-c_0)^2=\frac1{2m-1}\frac1{2m}\sum_ix_i^2-\frac1{2m-1}c_0^2=\frac1{2m-1}\frac1{2m}\sum_i(x_i-c_0)^2.$

Последний шаг лишний.
Вот это - $(x_i-c_0)^2$

- уже нельзя мажорировать единицей (оно может быть и больше 1, но не больше 4).
Достаточно так:
$\frac1{C_{2m}^m}\sum_a(c_a-c_0)^2=\frac1{2m-1}\frac1{2m}\sum_ix_i^2-\frac1{2m-1}c_0^2 \leq \frac1{2m-1}\frac1{2m}\sum_ix_i^2 \leq \frac1{2m-1}\frac1{2m}\sum_i 1=\frac1{2m-1}\frac1{2m}2m$

Если известно, что $c_0$

не равно нулю, то просто оценка будет ещё строже:
$\frac1{C_{2m}^m}\sum_a(c_a-c_0)^2 \leq \frac{1-c_0^2}{2m-1}$

Ian · Сообщение **Ian** » 19 дек 2019, 18:27

peregoudov, спасибо за содержательный пост
Вот еще одна
3-6 курс
5. Докажите неравенство

\sum_{k=1}^n(x_k-x_{k-1})^2\geq 4\sin^2\frac{\pi}{2n}\sum_{k=0}^nx_k^2 для любых действительных чисел

x_0,x_1,...x_n, для которых

x_0=x_n=0
Эту решил но сложным путем

zykov · Сообщение **zykov** » 19 дек 2019, 18:41

Ian писал(а):Source of the post Эту решил но сложным путем

Это как?

$\sum_{k=0}^nx_k^2$ - это квадрат вектора $x_k$

, который как известно не зависит от базиса.
$\sum_{k=1}^n(x_k-x_{k-1})^2$ - это квадрат вектора $x_k - x_{k-1}$ (линейный оператор от $x_k$

- дискретная производная), который так же не зависит от базиса.
Переходим просто в другой базис - дискретное преобразование Фурье. Там оператор дискретной производной будет диагональным.

Ian · Сообщение **Ian** » 20 дек 2019, 04:42

Поправил в условии коэффициент.
И сразу шаг в сторону непрерывной задачи

\int_0 ^1(x'(t))^2dt\to\min,\int_0 ^1(x(t))^2dt=1,x(0)=x(1)=0, почему мы с Вами 2 раза уже в предыдущих темах там Фурье не применили (доопределив функцию вне отрезка нулем)
Впрочем, в классе

x'(t) из

L_2 есть решение еще проще - рассмотрим ее синус- коэффициенты Фурье, сразу видно , что у оптимальной функции только при

\sin\pi t он отличен от нуля.

peregoudov · Сообщение **peregoudov** » 20 дек 2019, 18:02

Ian писал(а):Source of the post peregoudov, спасибо за содержательный пост

Ну да, я ж обычно бессодержательно пишу...

zykov писал(а):Source of the post $\sum_{k=0}^nx_k^2$ - это квадрат вектора , который как известно не зависит от базиса.
$\sum_{k=1}^n(x_k-x_{k-1})^2$ - это квадрат вектора $x_k - x_{k-1}$ (линейный оператор от - дискретная производная), который так же не зависит от базиса.
Переходим просто в другой базис - дискретное преобразование Фурье. Там оператор дискретной производной будет диагональным.

Ни фига не понял...

zykov · Сообщение **zykov** » 21 дек 2019, 04:32

peregoudov писал(а):Source of the post Ни фига не понял...

$\sum_{k=0}^nx_k^2=\sum_{k=1}^nx_k^2=|x|^2=|a|^2=\sum_{k=0}^{n-1}|a_k|^2$
$\sum_{k=1}^n(x_k-x_{k-1})^2=|Ax|^2=|A_Fa|^2=\sum_{k=0}^{n-1}|\lambda_k|^2|a_k|^2$

Единственное что надо обиграть, это ограничение на подпространство (проекцию): $x_0=0$

, оно же $\sum_{k=0}^{n-1}a_k=0$ .

PS: Да, стандартный ход в DFT - это периодическое дополнение ( $x_{k+n}=x_k$ ). Дискретность $x$

означает периодичность спектра, периодичность $x$

означает дискретность спектра. С этим дополнением будет симметрично - и $x$

, и спектр будут дискретными и периодическими.

zykov · Сообщение **zykov** » 21 дек 2019, 19:45

В такой форме это можно сделать. "В лоб", как условный экстремум. Но получается несколько тяжеловесно. (Там $a_k$

комплексные.)

Если доопределить $x_k$

по-другому - сначала расширить его до интервала от $-(n-1)$

до

так чтобы было нечётное ( $x_{-k}=-x_k$ ).
А потом уже доопределить периодически от этого двойного интервала (период $2n$

) и брать Фурье, то в Фурье только синусы останутся без косинусов. Ограничение $x_0=0$

получается автоматом.
В разложении Фурье можно скомбинировать члены, как $a_k i (e^{-ik\pi/n}-e^{ik\pi/n})$ . Здесь уже $a_k$

будут действительные.
Константы уже не будет в разложении (у неё $\lambda_0=0$ ). Минимальное $\lambda$ будет $\lambda_1=e^{i\pi/n}-1$ , которое и даст минимальную норму после действия оператора.

$|e^{i\pi/n}-1|^2=(\cos(\pi/n)-1)^2+\sin^2(\pi/n)=$
$=\cos^2(\pi/n)-2\cos(\pi/n)+1+\sin^2(\pi/n)=2(1-\cos(\pi/n))=2(1-(1-2\sin^2\frac{\pi}{2n}))=4\sin^2\frac{\pi}{2n}$

Экстремальные $x$

будут $x_k=\sin\frac{\pi k}{n}$ .

zykov · Сообщение **zykov** » 22 дек 2019, 20:08

Ian писал(а):Source of the post И сразу шаг в сторону непрерывной задачи $\int_0 ^1(x'(t))^2dt\to\min,\int_0 ^1(x(t))^2dt=1,x(0)=x(1)=0$ , почему мы с Вами 2 раза уже в предыдущих темах там Фурье не применили (доопределив функцию вне отрезка нулем)

Да, здесь можно аналогично сделать.
Доопределить $x(t)$

на

нечётным образом, потом доопределить на $\mathbb{R}$ периодически с периодом $2$

.
Для периодической функции получим ряд Фурье. Т.к. она нечётная, то амплитуды косинусов будут нулевые (в том числе и амплитуда константы). Останутся только синусы.
Самые маленькие по абсолютной величине собственные значения войдут в $x(t)=\sin(\pi t)$ (т.к. константа, которая имеет ещё меньше - нулевое значение - запрещена по чётности).

peregoudov · Сообщение **peregoudov** » 22 дек 2019, 23:13

Ну, про циркулянты и Фурье я слыхал. Просто сначала не понял, что $\sum_i x_i^2$ стоит множителем, а не под синусом. Так вы предлагаете трактовать это неравенство как оценку нормы квадратичной формы $\sum_{k=1}^n (x_k-x_{k-1})^2$ ? Ее матрица

$\begin{pmatrix} 1&-1\\ -1&2&-1\\ &-1&2&-1\\ &&&\ddots\\ &&&-1&2&-1\\ &&&&-1&1 \end{pmatrix}.$

Раз $x_0$

и

нулевые, матрицу можно обрезать

$\begin{pmatrix} 2&-1\\ -1&2&-1\\ &-1&2&-1\\ &&&\ddots\\ &&&-1&2&-1\\ &&&&-1&2 \end{pmatrix}.$

Это не циркулянт и преобразованием Фурье не диагонализуется.

Но мне кажется, что тут имелась в виду физика, одномерная цепочка масс, связанных пружинками. Решение для собственного вектора ищется в виде $x_i=c^i$

, для

из каждой строки, кроме первой и последней, получается квадратное уравнение $-1+(2-\lambda)c-c^2=0$ , так что общее решение $x_k=Ac_1^i+Bc_2^i$

, из первой и последней строк тогда получаем

$\begin{pmatrix} (2-\lambda)c_1-c_1^2&(2-\lambda)c_2-c_2^2\\ -c_1^{n-2}+(2-\lambda)c_1^{n-1}&-c_2^{n-2}+(2-\lambda)c_2^{n-1} \end{pmatrix} \begin{pmatrix}A\\B \end{pmatrix}=0$

Немного замучено, но, если учесть, что по теореме Виета $c_1+c_2=2-\lambda$ , $c_1c_2=1$

, то все упрощается до

$\begin{pmatrix} 1&1\\ c_1^n&c_2^n \end{pmatrix} \begin{pmatrix}A\\B \end{pmatrix}=0,$

так что собственные значения определяются из $c_2^n-c_1^n=0$

или $c_1^{2n}=1$ . Откуда и получаем $c_1=e^{i\pi k/n}$ , $\lambda_k=2-c_1-1/c_1=4\sin^2\frac{\pi k}{2n}$ . Нулевое собственное значение исключено, посколку для него получаем $x_i=0$

.

peregoudov · Сообщение **peregoudov** » 22 дек 2019, 23:55

Ian писал(а):И сразу шаг в сторону непрерывной задачи \int_0 ^1(x'(t))^2dt\to\min,\int_0 ^1(x(t))^2dt=1,x(0)=x(1)=0, почему мы с Вами 2 раза уже в предыдущих темах там Фурье не применили (доопределив функцию вне отрезка нулем)

Мне кажется, тогда уж проще так:

$\int_0 ^1x^{\prime2}(t))\,dt=x(t)x'(t)|_0^1-\int_0^1x(t)x''(t)\,dt=-\int_0^1x(t)x''(t)\,dt$

и получаем задачу на поиск минимума оператора энергии для частицы в яме с бесконечными стенками.

zykov · Сообщение **zykov** » 23 дек 2019, 06:16

peregoudov писал(а):Source of the post и получаем задачу на поиск минимума оператора энергии для частицы в яме с бесконечными стенками

И как этот минимум ищется?
Так же - через вариационное исчисление (универсальный метод) или, в данном случае, через спектр (Min-max theorem).

zykov · Сообщение **zykov** » 23 дек 2019, 06:37

peregoudov писал(а):Source of the post Так вы предлагаете трактовать это неравенство как оценку нормы квадратичной формы

Вовсе нет. Там же русским языком написано: дискретная производная - первая, а не вторая.
$|Ax| \to \min, \; |x|=1$
$Ax=y, \; y_k=x_k-x_{k-1}$
А квадрат - это уже для нахождения нормы этого вектора.
Вобщем на википедии всё написано:

zykov писал(а):Source of the post через спектр (Min-max theorem).

Замечание: там $A$

, это наше $A^TA$

.

Портал Естественных Наук, версия 1.1