Помогите решить задачу (числовое и аналитическое решение функции)
и дифференциальную геометрию, иначе всю
жизнь будете страдать вот такими тупыми
первокурсными матановыми задачами.
کπιν∅rε ☭
Общая постановка
Дано:
- ƒ конечна, если конечны оба её аргумента, причём ƒ ( 0, 0 ) = 0.
- При любом фиксированном y функция ƒ выпукла вверх по x и монотонно растёт по x до бесконечности.
- При любом фиксированном x функция ƒ имеет предел limy→∞ ƒ ( x, y ) = log2 ( 2x + 1 ).
- ƒ — неявная функция обоих своих аргументов, зависящая от корня сложного трансцендентного уравнения, из-за чего прямой подход к аналитическому исследованию ƒ затруднён.
- Квадрант x ≥ 0, y ≥ 0 может быть разбит на конечное число областей, в каждой из которых функция ƒ является выпуклой.
Требуется:
Важные частные случаи
Рассмотреть варианты:
- При любом фиксированном x функция ƒ:
- Монотонно убывает по y и выпукла вниз по y.
Численное решение для конкретной интересуемой ƒ в этом случае всегда достигается при каких-то Δx, не обязательно равных нулю или x0, и при Δy = y (т.е. одна точка всегда на границе, а другая — на максимальном удалении от исходной y0). Существенным вкладом в решение может считаться нахождение контрпримера: любой конкретной ƒ с вышеоговоренными свойствами, подпадающей под пункт 1.a и приводящей к другому решению.
- Имеет только один экстремум по y, который является глобальным максимумом по y и досигается при каком-то конечном ненулевом y = ymax. На промежутке 0 ≤ y ≤ yinflec, содержащем точку ymax, функция ƒ выпукла вверх; а на промежукте
yinflec ≤ y &le ∞ — выпукла вниз. Точка y = yinflec является единственной точкой изгиба ƒ.
- Монотонно убывает по y и выпукла вниз по y.
- В зависимости от фиксированного значения x функция может быть как монотонно растущей по y (и, в том числе, иметь седловую точку при конечном ненулевом y), так и иметь два локальных экстремума, достижимых при конечных ненулевых y: локальный максимум при меньшем значении y, и локальный минимум — при большем (на промежутке от нуля до максимума ƒ выпукла вверх). Также, при каких-то фиксированных x может наблюдаться поведение, описанное в вышеприведённом случае 1.b.
Пояснения и идеи к решению
Геометрические смысл решения прост: можно вообразить себе две точки ( x1, y1 ) и ( x2, y2 ), которые изначально сидят в одном месте на плоскости ( x, y ) — в заданной точке ( x0, y0 ). Далее мы начинаем разносить эти точки так, чтобы как сумма их абцисс, так и сумма их ординат оставались одинаковыми и равными, соответственно x0 (для абцисс) и y0 (для ординат). Если мы пододвинули одну точку на некоторое расстояние влево, значит, на такое же расстояние другую точку надо пододвинуть вправо. Более того, «разносить» эти точки можно только до тех пор, пока они не достигнут границы прямоугольника 0 ≤ x ≤ 2x0, 0 ≤ y ≤ 2y0. Далее, перебрав все возможные «разношения» точек надо найти такое, которое даст максимальное усреднённое значение функции в этих точках, то есть максимум для
[ &fnof( x1, y1 ) + &fnof( x2, y2 ) ] / 2.
Для наглядности можно сначала рассмотреть модельный пример — функцию ƒ, зависящую только от одного аргумента. Решение тривиально, если ƒ монотонна на всём промежутке [ 0, ∞ ) и сохраняет на нём значение выпуклости: точки разносить не надо, если ƒ выпукла вверх, и точки надо разнести на максимальное расстояние, если ƒ выпукла вниз — геометрически это легко видеть из неравенства Йенсена. Однако, это не помогает решить даже случай 1.a, поскольку ƒ выпукла вверх по одной переменной, но вниз по другой.
Более сложный модельный случай — функция ƒ от одного аругмента, не являющаяся выпуклой на всём интервале [ 0, ∞ ). Гугление позволило найти, что интересуемая операция используется при обработке сигналов для устранения шума и называется «метод скользящих средних» («moving average»), только в этом случае Δx фиксировано (размер окна скольжения), а значения x0 перебираются. Это позволяет построить «сглаженную» функцию, без пиков, но имеющую то же качественное поведение глобально (хорошие графики на эту тему есть здесь). В интересуемом же нас случае размер окна надо подбирать под каждую точку, чтобы получающаяся сглаженная функция имела как можно большее значение — задача, которая не похоже, чтоб ставилась в теории сигналов. Тем не менее, есть нечто, что позволяет объединить как нашу задачу, так и обработку сигналов, в одну общую:
G = | cos ( x ) |.
Более грубой верхней границей на получающийся набор можно считать выпуклую оболочку, натянутую на множество всех рассматриваемых точек ( x, ƒ ( x ) ). Например, для функции ƒ = cos ( x ) это даст прямую, параллельную оси абцисс, проходящую через точку с оридинатой 1. Наглядно видно, что это — ещё более грубая граница, чем G = | cos ( x ) |. Основная идея — найти какие-то интересные топологические свойства кривых/поверхностей; понять, что в задаче определяется чисто выпуклостью функций, а что — следствие их конкретного вида. Очевидно, что если нечто является следствием выпуклости, то вид функции ƒ совершенно не важен — задачу можно решать в общем виде.
Физический смысл
Пусть ƒ — пропускная способность квантового канала, x — средняя энергия на его входе, и y — средняя энергия в его среде (т.е. доступная Еве). Рассмотрим два использования канала3, считая, что среднее количество энергии на входе на одно использование канала ограничено и равно x0. Аналогично, будем считать, что среднее значение энергии в среде ограничено, и равно в среднем y0 на одно использование канала. Тем не менее, у нас есть свобода перераспределять энергию между первым и вторым использованиями канала, и мы хотим найти метод делать это так, чтобы его пропускная способность была максимальной. Если вообразить, что шум/среда/Ева ограничена по энергии при воздействии на канал, мы найдём тот вид распределения, который наболее выгоден Алисе и Бобу.
Можно показать, что решение случая 1.a полностью решает поставленную задачу для канала с аддитивным классическим шумом, а также для любого числа его использований для посылки (классической) информации. Решение случая 1.b позволяет найти то же, но для двух, в общем случае, использований канала и некоторых параметров (если ещё опереться на ряд недоказанных гипотез). Решение задачи 2 полностью даёт ответ для двух использований «lossy»-канала (канал с затуханием амплитуды). Так как неоднородное распределение энергии по использованиям канала приводит к корреляциям между его использованиями, вид среды часто называют памятью, а сами каналы — каналами с памятью. Соответственно, задача может быть сформулирована, как «найти оптимальный вид памяти для гауссова канала при условии ограничения на энергию в его среде» (энергия на входе считается ограниченной всегда, иначе пропускная способность будет бесконечной, т.е. тривиальным случаем). Более подробно смысл задачи раскрыт в комментариях к топику «Проблема определения криптостойкости» (перенесено в «Вопросы по квантовым каналам, их моделирование и применение»).
Мотивация и плюшки
- Решение случая 1.a2 (вкупе с имеющимися наработками) — задача уровня публикации в Phys. Rev. A.
- Полное решение всей задачи (возможно, объединяя оба типа канала в один) и всех частных случаев, при условии, что удастся получить какие-то нетривиальные важные свойства, строго доказанные аналитически и мотивированные физически с точки зрения их смысла — уровень публикации в IEEE Tran. Inf. Theor.
Желающие есть помочь/поучаствовать?
1А, значит, и с финансовыми трейдерами, биржевиками, и прочими, кто использует сглаживание для отделения тренда от шума — гугл преиспещрен ссылками на эту тему.
2Как и случая 1.b или 2, каждый по отдельности.
3Обычно с разными использованиями канала ассоциируют его разные моды: одно использование n-модового канала в некотором смысле эквивалентно n использованиям одномодового, в котором разные его использования скоррелированы между собой (Ева по-разному воздействует на сигнал при разных его использованиях).
комментариев: 9796 документов: 488 редакций: 5664
комментариев: 1515 документов: 44 редакций: 5786
Короче говоря, эффективный численный метод — это хорошо, этим надо будет заняться в любом случае, но главная мишень и трудность — то, что можно найти/оценить аналитически. Функция ƒ вычисляется быстро, так что разработка численного метода больших сложностей не составляет. Не буду скрывать, что решение 1.a и 1.b уже численно получено, не плохо (хотя и не до конца) исследовано, но с аналитикой и пониманием всё сложнее. Я ещё детально википедию/литературу не штудировал по вопросу метода скользящих средних и связанных с ними вопросам (это может что-то дать).
В случае 1.b, если взять для простоты (модельно), что от x он не зависит, получается следующее: пока y0 мал, в силу монотонного роста и выпуклости вверх оптимально точки не разносить. Потом, с увеличением y0, обе точки сидят в максимуме, и даже перескакивают через него. Однако, начиная с какого-то значения за максимумом, точки вдруг начинают разбегаться4: одна полёзёт обратно в максимум, на горку, а другая вправо, в сторону убывания функции. Как точка «разбегания» связана с точкой изгиба — вопрос.
Аналогичное решение получается и для большого числа точек5 (мод) [до сих пор выше всегда рассматривался случай только двух точек]: одна ползёт вниз, а все другие — обратно на горку. Т.е. n – 1 точек сидят в одном месте, и n'ая — в другом, на «мусорной моде», куда загоняется излишек энергии. Видимо, профит от движения n – 1 точек назад перекрывает убыль от движения одной точки вперёд, в сторону убывания функции. Когда ограничение по энергии растёт на бесконечность, естественно, все n – 1 точкек перебираться на горку в максимум, а одна — в бесконечность (но это тривиальное решение).
Куда более интересно, что даже если перебирать вообще все случаи и результаты числененной оптимизации, якобы решение всегда получается6 этого типа: всего два разных значения по y: одна точка в каком-то одном месте на кривой/поверхности, а все остальные совпадают друг с другом. В классической теории информации, говорят, результат такой же для каналов.
4Эдакий «перегрев по энергии, приводящий к фазовому переходу» — было б круто подвести под это дело какую-то теорию фазовых переходов.
5Такую задачу легко сформулировать как «расставь n точек на оси абцисс так, чтобы среднее значений функции в этих точках было максимальным, при условии что средняя абцисс точек фиксирована».
6Хотя, может, плохо исследовали.
комментариев: 9796 документов: 488 редакций: 5664
Напоминает шутку про "бифуркацию субмодальных сингулярностей".
комментариев: 1515 документов: 44 редакций: 5786
Главное, чтоб не чёрнодырочную проводимость с квадратно-гнездовым методом :)
Некие параллели с теорией фазовых переходов здесь есть, об этом действительно стоит подумать (правда, я с физикой твёрдого тела вообще плохо знаком, к сожалению). Обычно в физике по заданным свойствам модели восстанавливают «начинку» (функционал плотности?), а здесь обратная задача: начинка дана, и надо понять какая «физика» из неё следует.
комментариев: 9796 документов: 488 редакций: 5664
комментариев: 1515 документов: 44 редакций: 5786
Отлично! Изначальное название было дано по приколу, как пародия на последние топики в разделе «криптография» :)
Только, чтобы не терять связность, надо тогда поправить ссылки в том топике на этот — в местах
комментариев: 1515 документов: 44 редакций: 5786
А вот для задаче 1.a, которая кажется более простой, метод Лагранжа не поможет: там решение строго на границе по y7, и показать это можно, лишь доказав монотонность или определённые свойства выпуклости, что сводится к аналитическому доказательству постоянства знака8 длинного крокодила-выражения.
7Т.е., если положить, что в одной из функций y нулевой, то задача становится тривиальной: нахождение оптимальных значений x при заданных значениях y — уже решённая задача (тут — для lossy, и тут — для additive-канала).
8Ещё и при любых параметрах.
найти площадь АВСД
5,4352;
комментариев: 1515 документов: 44 редакций: 5786
> бифуркацию субмодальных сингулярностей
Наткнулся случайно :)
В связи с 1.b возникла (ещё давно) задача:
Дано:
Требуется:9
Решение:10
Мораль:
9Задача на всю жизнь испортит карму тому, кто осмелится дать её на экзамене студентам.
10Спасибо Vadim_Z.
комментариев: 1060 документов: 16 редакций: 32
Кажется, можно и проще: f(x,y) = xy – гиперболический параболоид.Не кажется :) Строгой выпуклости по переменным нет.комментариев: 1515 документов: 44 редакций: 5786
Пример тоже интересный. Во всяком случае, сразу позволяет задуматься, что от недиагональных членов в гессиане не уйти. Просто поначалу думалось, что монотонный рост как-то меняет суть дела, но это не так: прибавкой линейной функции к заданной выпуклой её всегда можно сделать монотонно возрастающей (на ограниченной области), не испортив свойств выпуклости. Если не требовать монотонности, а ограничиться только выпуклостью, пример был найден ещё раньше: – x2 – y2 + 3xy. Добавляя к ней функцию nx + my, где n и m — большие числа, получим и монотонно растущую на ограниченной области. Пример с бесконечной областью был дан в предыдущем посте.