Опять МФТИ

[zykov]

Что-то много понаписали. Путаница вышла. Попробую кратко подвести резюме.
(У меня через спектр, но конечно есть и другие пути.)


У нас оператор легко диагонализируется (оператор дискретной или обычной производной имеет диагональный вид в Фурье базисе).
По теореме Min-max, минимум нормы будет для собственного вектора с минимальным по абсолютной величине собственным значением.
(Без других ограничений это была бы константа для которой нулевое собственное значение.)

Единственное осложнение, это дополнительное ограничение. Для дискретного , для непрерывного .
Ограничение линейное - должен лежать в подпространстве. Можно рассмотреть это подпространство уже в новом базисе (где оператор диагонален), что уже проще, но всё равно несколько сложно.

В данном случае простой фокус позволяет значительно упростить решение.
Сначала дополним вектор/функцию нечётным образом. Для дискретного при , для непрерывного при . Потом дополним везде периодическим образом. Для дискретного , для непрерывного .
Ограничения и следуют из нечётности. Ограничения и следуют из нечётности и периодичности (например, из периодичности, из нечётности, значит оба нули).
Т.е. дополнительных ограничений нет, кроме периодичности и нечётности.
Периодичность даёт дискретный спектр, т.е. ряд Фурье (плюс, в дискретном случае ещё сам ряд периодичен, т.е. имеет всего измерений).
Нечётность при переходе в Фурье базис тоже имеет простую интерпретацию - амплитуды косинусов нулевые, остаются только синусы.
Теперь уже константа с её нулевым собственным значением запрещена нечётностю.
Следующие собственные вектора с минимальными (по абсолютной величине) собственными значениями будут (для непрерывного ). Они комбинируются в (для непрерывного в ).

[peregoudov]

Source of the post И как этот минимум ищется?

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

Source of the post Замечание: там , это наше .

Ну то есть ровно та матрица, что я и рассматривал?

Тут ведь, как в непрерывном случае, принципиальны граничные условия. Какой спектр имеет оператор на [0,1]? Да хз, от граничных условий зависит. Так и в дискретной цепочке: собственные частоты зависят от граничных условий. Выписать решение для бесконечной цепочки --- не штука, и циркулянты тут мало что упрощают. И ниоткуда вы не получите этот несчастный , кроме как честно решая уравнения для конечной цепочки с учетом граничных условий.

[zykov]

Source of the post И ниоткуда вы не получите этот несчастный ,

Эээ... Нет слов.
В предыдущем посте всё чётко расписано, что и откуда получается.

[peregoudov]

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

[zykov]

Source of the post Просто мне кажется, что стандартный дуболомный подход ничуть не сложнее, а в непрерывном случае --- так даже явно проще.

Стандартный подход "в лоб" потребует бумажки или компьютера.
Здесь же "устный счёт", всё в уме решается.

[Ian]

Ну у меня тоже близко вокруг этой матрицы.
Зная, что вариационную задачу иначе как уравнением Лагранжа мы решать не умеем, в дискретном случае вместо вариаций будут малые отклонения этих [math]x_i по отдельности.Придется найти все локальные экстремумы, интересно же.
Достаточно доказывать неравенство при ограничении[math]\sum x_{k}^{2}=1
[math]F(x_{1},...x_{n-1})=\sum(x_{k}-x_{k-1})^{2}\to\min

Единичная сфера в [math]R^{n-1}компактна, существует точка, где достигается минимум F>0. В этой точке существует градиент F (потому что он везде существует) и должен быть направлен наружу сферы перпендикулярно ей, в крайнем случае равен 0. Значит (уточнение правила множителей Лагранжа), существует [math]t\geq0, что [math]\nabla F=2t\left(2x_{1},2x_{2},...2x_{n-1}\right)
[math]2x_{k}-x_{k-1}-x_{k+1}=2tx_{k}

Рекуррентность [math]x_{k+1}+2(t-1)x_{k}+x_{k-1}=0\; x_{0}=0,\;x_{n}=0
Так как [math]t\geq0 , характеристические корни могут быть либо 2 действительных положительных [math]\mu,\frac{1}{\mu}, либо комплексные [math]e^{\pm i\psi}В первом случае [math]x_{n}=C_{1}\mu^{n}-C_{2}\mu^{-n}=C\mu^{n}-C\mu^{-n}=0(чтобы [math]x_{0}=0,C_{1}=C_{2}) единственный вариант [math]\mu^{2}=1,t=0;2. Мы увидим что в этих случаях локальные максимумы на сфере.

Пусть [math]x_{k}=Ce^{ik\psi}-Ce^{-ik\psi}=2iC\sin(k\psi)
[math]iC=a\in R
[math]2a\sin n\psi=0
[math]\psi=\frac{m\pi}{n}-это точки локальных минимумов при разных m. Найдем [math]a из ограничения[math]\sum_{k=0}^{n}\sin^{2}\frac{km\pi}{n}=\frac{1}{2}\sum_{k=0}^{n}\left(1-\cos\frac{2km\pi}{n}\right)=\frac{n}{2}-\frac{1}{2\sin\frac{m\pi}{n}}\sum_{k=0}^{n}\cos\frac{2km\pi}{n}\sin\frac{m\pi}{n}=[math]=\frac{n}{2}-\frac{1}{4\sin\frac{m\pi}{n}}\left[\sin\frac{(2n+1)m\pi}{n}-\sin\frac{m\pi}{n}\right]=\frac{n}{2}=\frac{1}{4a^{2}}

Сравним в них значения [math]F
[math]F=a^{2}\sum\left(\sin\frac{km\pi}{n}-\sin\frac{(k-1)m\pi}{n}\right)^{2}=\frac{1}{2n}\sum\left(\sin\frac{km\pi}{n}-\sin\frac{(k-1)m\pi}{n}\right)^{2}\to\min

При [math]m=\pm1 сумма меньше, так как [math]\sin\frac{km\pi}{n} не меняют знаки

Значение суммы можно найти тем же приемом понижения степени, должно получиться [math]8n\sin^{2}\frac{\pi}{2n}

[guryev]

Возвращаясь к первой задаче - можно применить индукцию.

Очевидно, что если точек всего две, в единичном шаре они находятся на расстоянии , и их центры масс, естественно, тоже.

Теперь, пусть есть два непересекающиеся множества, и , состоящие каждое из точек единичного шара и расстояние между их центрами масс



Обозначим вектор центра масс множества как , а множества - через . Очевидно,



Берём две новые точки из шара и добавляем одну из них в множество , а другую - в . Больше ничего не меняем, вдруг получится.

Итак, для определённости, добавляем точку в , а точку в . Теперь квадрат расстояния между центрами масс новых множеств будет



То есть,



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

А для второго слагаемого можно считать, что максимум - ноль. Почему? Потому, что если оно окажется положительным, можно повторить вышеупомянутые рассуждения, только на этот раз поместить в , а в . Всё будет точно так же, только и поменяются местами, и соответственно, у второго слагаемого поменяется знак. Таким образом, не теряя общности, можно считать, что второе слагаемое меньше или равно нулю. Надо только правильно выбрать, куда помещать , а куда .

Теперь, после несложных выкладок можно получить , т.е., .

[zykov]

Source of the post Возвращаясь к первой задаче - можно применить индукцию.

Наверно авторы задачи это и имели ввиду.
У peregoudov получилась полее строгая оценка, но и метод сложнее.

[Ian]

Возвращаясь к первой задаче

, Вы ее решили просто.А Вы случайно не участвовали в самой олимпиаде?

А для второго слагаемого можно считать, что максимум - ноль.

Как я и предсказывал в посте 1, худший для такой оценки случай, когда a и b лежат в подпространстве, перпендикулярном гиперплоскости, содержащей остальные 2m-2 точки, тогда ровно ноль.

[zykov]

Source of the post У peregoudov получилась полее строгая оценка, но и метод сложнее.

Что интересно, при размерности от и выше это самая строгая оценка.
Экстремальный пример - правильный мерный симплекс (имеет вершин) вписанный в мерный шар единичного радиуса. Тут, в силу симметрии, как ни разбивай - будет одинаковое расстояние. Значит минимум равен максимуму и равен среднему.

Вот интересно, какая наиболее строгая оценка при размерности менее ? (Она должна быть меньше чем .)
Например в одномерном случае экстремальный пример - одна точка на одном конце, все другие точки на другом конце. Тут наиболее строгая оценка: .