Что-то много понаписали. Путаница вышла. Попробую кратко подвести резюме.
(У меня через спектр, но конечно есть и другие пути.)
У нас оператор легко диагонализируется (оператор дискретной или обычной производной имеет диагональный вид в Фурье базисе).
По теореме Min-max, минимум нормы будет для собственного вектора с минимальным по абсолютной величине собственным значением.
(Без других ограничений это была бы константа для которой нулевое собственное значение.)
Единственное осложнение, это дополнительное ограничение. Для дискретного , для непрерывного .
Ограничение линейное - должен лежать в подпространстве. Можно рассмотреть это подпространство уже в новом базисе (где оператор диагонален), что уже проще, но всё равно несколько сложно.
В данном случае простой фокус позволяет значительно упростить решение.
Сначала дополним вектор/функцию нечётным образом. Для дискретного при , для непрерывного при . Потом дополним везде периодическим образом. Для дискретного , для непрерывного .
Ограничения и следуют из нечётности. Ограничения и следуют из нечётности и периодичности (например, из периодичности, из нечётности, значит оба нули).
Т.е. дополнительных ограничений нет, кроме периодичности и нечётности.
Периодичность даёт дискретный спектр, т.е. ряд Фурье (плюс, в дискретном случае ещё сам ряд периодичен, т.е. имеет всего измерений).
Нечётность при переходе в Фурье базис тоже имеет простую интерпретацию - амплитуды косинусов нулевые, остаются только синусы.
Теперь уже константа с её нулевым собственным значением запрещена нечётностю.
Следующие собственные вектора с минимальными (по абсолютной величине) собственными значениями будут (для непрерывного ). Они комбинируются в (для непрерывного в ).
Опять МФТИ
-
- Сообщений: 620
- Зарегистрирован: 29 дек 2015, 13:17
Опять МФТИ
Напрямую, поиском минимального собственного значения. Спектр в яме известен.zykov писал(а):Source of the post И как этот минимум ищется?
Ну то есть ровно та матрица, что я и рассматривал?zykov писал(а):Source of the post Замечание: там , это наше .
Тут ведь, как в непрерывном случае, принципиальны граничные условия. Какой спектр имеет оператор на [0,1]? Да хз, от граничных условий зависит. Так и в дискретной цепочке: собственные частоты зависят от граничных условий. Выписать решение для бесконечной цепочки --- не штука, и циркулянты тут мало что упрощают. И ниоткуда вы не получите этот несчастный , кроме как честно решая уравнения для конечной цепочки с учетом граничных условий.
Опять МФТИ
peregoudov писал(а):Source of the post И ниоткуда вы не получите этот несчастный ,
Эээ... Нет слов.
В предыдущем посте всё чётко расписано, что и откуда получается.
-
- Сообщений: 620
- Зарегистрирован: 29 дек 2015, 13:17
Опять МФТИ
Да я понимаю, как вы рассуждаете. Вы фактически определяете минимальное собственное число трехдиагональной теплицевой матрицы таким вот вычурным методом. Просто мне кажется, что стандартный дуболомный подход ничуть не сложнее, а в непрерывном случае --- так даже явно проще.
Опять МФТИ
peregoudov писал(а):Source of the post Просто мне кажется, что стандартный дуболомный подход ничуть не сложнее, а в непрерывном случае --- так даже явно проще.
Стандартный подход "в лоб" потребует бумажки или компьютера.
Здесь же "устный счёт", всё в уме решается.
Опять МФТИ
Ну у меня тоже близко вокруг этой матрицы.
Зная, что вариационную задачу иначе как уравнением Лагранжа мы решать не умеем, в дискретном случае вместо вариаций будут малые отклонения этих [math] по отдельности.Придется найти все локальные экстремумы, интересно же.
Достаточно доказывать неравенство при ограничении[math]
[math]
Единичная сфера в [math]компактна, существует точка, где достигается минимум F>0. В этой точке существует градиент F (потому что он везде существует) и должен быть направлен наружу сферы перпендикулярно ей, в крайнем случае равен 0. Значит (уточнение правила множителей Лагранжа), существует [math], что [math]
[math]
Рекуррентность [math]
Так как [math] , характеристические корни могут быть либо 2 действительных положительных [math], либо комплексные [math]В первом случае [math](чтобы [math]) единственный вариант [math],t=0;2. Мы увидим что в этих случаях локальные максимумы на сфере.
Пусть [math]
[math]
[math]
[math]-это точки локальных минимумов при разных m. Найдем [math] из ограничения[math][math]
Сравним в них значения [math]
[math]
При [math] сумма меньше, так как [math] не меняют знаки
Значение суммы можно найти тем же приемом понижения степени, должно получиться [math]
Зная, что вариационную задачу иначе как уравнением Лагранжа мы решать не умеем, в дискретном случае вместо вариаций будут малые отклонения этих [math] по отдельности.Придется найти все локальные экстремумы, интересно же.
Достаточно доказывать неравенство при ограничении[math]
[math]
Единичная сфера в [math]компактна, существует точка, где достигается минимум F>0. В этой точке существует градиент F (потому что он везде существует) и должен быть направлен наружу сферы перпендикулярно ей, в крайнем случае равен 0. Значит (уточнение правила множителей Лагранжа), существует [math], что [math]
[math]
Рекуррентность [math]
Так как [math] , характеристические корни могут быть либо 2 действительных положительных [math], либо комплексные [math]В первом случае [math](чтобы [math]) единственный вариант [math],t=0;2. Мы увидим что в этих случаях локальные максимумы на сфере.
Пусть [math]
[math]
[math]
[math]-это точки локальных минимумов при разных m. Найдем [math] из ограничения[math][math]
Сравним в них значения [math]
[math]
При [math] сумма меньше, так как [math] не меняют знаки
Значение суммы можно найти тем же приемом понижения степени, должно получиться [math]
Опять МФТИ
Возвращаясь к первой задаче - можно применить индукцию.
Очевидно, что если точек всего две, в единичном шаре они находятся на расстоянии , и их центры масс, естественно, тоже.
Теперь, пусть есть два непересекающиеся множества, и , состоящие каждое из точек единичного шара и расстояние между их центрами масс
Обозначим вектор центра масс множества как , а множества - через . Очевидно,
Берём две новые точки из шара и добавляем одну из них в множество , а другую - в . Больше ничего не меняем, вдруг получится.
Итак, для определённости, добавляем точку в , а точку в . Теперь квадрат расстояния между центрами масс новых множеств будет
То есть,
Найдём максимальные значения для трёх слагаемых второго множителя. Для первого слагаемого это, как следует из гипотезы индукции, . Для третьего это , поскольку и лежат в одном единичном шаре.
А для второго слагаемого можно считать, что максимум - ноль. Почему? Потому, что если оно окажется положительным, можно повторить вышеупомянутые рассуждения, только на этот раз поместить в , а в . Всё будет точно так же, только и поменяются местами, и соответственно, у второго слагаемого поменяется знак. Таким образом, не теряя общности, можно считать, что второе слагаемое меньше или равно нулю. Надо только правильно выбрать, куда помещать , а куда .
Теперь, после несложных выкладок можно получить , т.е., .
Очевидно, что если точек всего две, в единичном шаре они находятся на расстоянии , и их центры масс, естественно, тоже.
Теперь, пусть есть два непересекающиеся множества, и , состоящие каждое из точек единичного шара и расстояние между их центрами масс
Обозначим вектор центра масс множества как , а множества - через . Очевидно,
Берём две новые точки из шара и добавляем одну из них в множество , а другую - в . Больше ничего не меняем, вдруг получится.
Итак, для определённости, добавляем точку в , а точку в . Теперь квадрат расстояния между центрами масс новых множеств будет
То есть,
Найдём максимальные значения для трёх слагаемых второго множителя. Для первого слагаемого это, как следует из гипотезы индукции, . Для третьего это , поскольку и лежат в одном единичном шаре.
А для второго слагаемого можно считать, что максимум - ноль. Почему? Потому, что если оно окажется положительным, можно повторить вышеупомянутые рассуждения, только на этот раз поместить в , а в . Всё будет точно так же, только и поменяются местами, и соответственно, у второго слагаемого поменяется знак. Таким образом, не теряя общности, можно считать, что второе слагаемое меньше или равно нулю. Надо только правильно выбрать, куда помещать , а куда .
Теперь, после несложных выкладок можно получить , т.е., .
Опять МФТИ
guryev писал(а):Source of the post Возвращаясь к первой задаче - можно применить индукцию.
Наверно авторы задачи это и имели ввиду.
У peregoudov получилась полее строгая оценка, но и метод сложнее.
Опять МФТИ
, Вы ее решили просто.А Вы случайно не участвовали в самой олимпиаде?guryev писал(а):Возвращаясь к первой задаче
Как я и предсказывал в посте 1, худший для такой оценки случай, когда a и b лежат в подпространстве, перпендикулярном гиперплоскости, содержащей остальные 2m-2 точки, тогда ровно ноль.А для второго слагаемого можно считать, что максимум - ноль.
Опять МФТИ
zykov писал(а):Source of the post У peregoudov получилась полее строгая оценка, но и метод сложнее.
Что интересно, при размерности от и выше это самая строгая оценка.
Экстремальный пример - правильный мерный симплекс (имеет вершин) вписанный в мерный шар единичного радиуса. Тут, в силу симметрии, как ни разбивай - будет одинаковое расстояние. Значит минимум равен максимуму и равен среднему.
Вот интересно, какая наиболее строгая оценка при размерности менее ? (Она должна быть меньше чем .)
Например в одномерном случае экстремальный пример - одна точка на одном конце, все другие точки на другом конце. Тут наиболее строгая оценка: .
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 3 гостей