Прямые и обратные задачи

[Bitman]

Я занимаюсь квантовой химией, и раньше занимался близкой ей по задачам газовой электронографией. У нас электронографисты любят фразу “квантовики решают прямую задачу, а мы обратную”. Эта фраза мне понятна: расчёт изначально находит структуру, а в электронографии структура определяется через МНК (градиентный спуск) по экспериментальным данным.
В действительности же, по-моему, любые задачи в математике в той или иной степени обратные, и вообще вся математика посвящена решению обратных задач. Возьмём для примера пять уравнений:
1) ax+b=0
2) ax^2+bx+c=0
3) ax^3+bx^2+cx+d=0
4) ax^4+bx^3+cx^2+dx+e=0
5) ax^5+bx^4+cx^3+dx^2+ex+f=0
Чтобы решить первую задачу, нужно провести одно деление. Вторая задача решается через детерминант (я всё не могу найти, как называется эта формула – формула Виета?). Третья задача решается по формуле Кардано, чётвёртая, если не ошибаюсь, решается очень похожим образом (через резольвенты), а пятая в общем случае “не решается”, точнее её нельзя решить аналитически.
По сути, все пять задач – это обратные задачи от простого уравнения n-й степени. Т.е. если мы пишем, например, y=ax^2+b+c, то нахождение y по известному x – это прямая задача, а нахождение x по известному y – это обратная задача.
Признаки прямой задачи:
1) Её можно решить в любом интервале x;
2) Для любого x решение единственно;
3) Решение относительно простое по сравнению с обратной задачей
4) Сложность (время) и надёжность решения прямой задачи практически не зависит от того, чему равен x или какое было начальное приближение.
5) Ещё одна связь между прямой и обратной задачей: существуют очень простые и универсальные методы решения обратной задачи через прямую, например простой перебор или градиентный спуск. Хотя они обычно далеко не эффективны в плане требуемых ресурсов.

Теперь я предлагаю такую идею: взять пять уравнений выше и определить их сложность. Сложность решения задачи можно измерить количественно – количеством машинного времени, потраченного на её решение с применением наилучшего алгоритма.
У меня сильное подозрение, что для первых четырёх задач сложность будет описываться некой простой зависимостью от номера (например, экспонентой), а для пятой сложность будет явно выпадать из этой зависимости. И из этого можно будет заключить, что в математике есть нерешённая задача – найти “сверхформулу Кардано”, которая позволит решить пятое уравнение аналитически.
Сложность прямой задачи для этих четырёх уравнений тоже растёт, хотя не очень сильно. И возникает ещё одна идея: как сложность обратной задачи в общем случае зависит от сложности прямой. Я подозреваю, что эта зависимость, может быть, экспоненциальная.
В программировании все эти термины, как я понимаю, тоже вполне применимы. Достаточно понятный пример – нейросети: работа нейросети – это решение прямой задачи, а тренировка нейросети – решение обратной.
По-моему, вся математика и всё computer science так или иначе сводится к оптимальным способам решения обратных задач. И тут можно развить тему для программистов. Я прихожу к выводу, что при программировании сложных алгоритмов полезно применять “тяжёлые ассерты”: это такие ассерты, которые проверяют всё сразу. Эти ассерты довольно легко реализовать, но они сильно тормозят работу программу, поэтому их нужно отключать даже не только в финальном билде программы, но и вообще почти всегда, за исключением моментов когда нужно проверить критические участки алгоритма. С тяжёлыми ассертами баги должны легко выявляться. Так вот это всё тоже входит в изначальную тему: ассерты – это тоже вспомогательное решение прямой задачи, позволяющее проверить, насколько корректно решается обратная.

[Кот Матроскин]

В жизни для большинства задач такой огород городить и не требуется. Это уж если сильно заморочили программу начинают изобретать велосипеды. Видел код одного программиста сильно начитавшегося книг по паттернам и рефакторингу, в общем метод вызывался через 20 вложений, хотя хватило бы для удобства работы одного-двух. Платформа .NET в принципе имеет приличное количество исключений и специально мостить свои не требуется в большинстве случаев. Хотя есть пара любымых проверок что объект не нулл и что индекс в пределах диапазона, дабы не ловить и не обрабатывать лишний раз исключения. У Майкрософт по поводу блоков отлова исключений тоже есть забавные рекомендации использовать тру финали а не тру катч, мол пусть ваша программа вылетит с иключением, хотя сама она этим рекомендациям не следует.

[Н. Светлов]

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

Обобщения (индукции) иногда работают, иногда нет (если только это не строгие математические индукции). Вот как раз тот пример, когда индукция не работает: несуществование "сверхформулы Кардано" - это теорема, следовательно, такая формула никогда не будет найдена.

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

[Весельчак Ы]

в четырёхмерном, внезапно, шесть, а во всех высших мерностях - по три

Я раньше тоже так думал, но недавно мне сказали, что их там куча.

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

Лучшие известные мне оценки:

- Baker, Harman и Pintz показали, что для некоторого x₀ («которое, при достаточных стараниях, можно определить эффективно») и всех x > x₀ интервал [x-x^0.525,x] содержит простое число. [BHP]

- Zhang, «обобщая и без того ошеломляющий результат» Goldstonа, Pintzа и Yildirimа [GPY], показал, что одно из уравнений x−y = 2i, i = 1, ..., 35·10⁶ имеет бесконечно много простых решений [Z]. Число уравнений было уменьшено благодаря poly-math проекту.

Литература

[BHP] R. C. Baker, G. Harman, J. Pintz, The difference between consecutive primes II.
[GPY] D. Goldston, J. Pintz, Yildirim, Primes in tuples I, Ann. of Math. 170 (2009): 819-862
[Z] Y. Zhang, Bounded gaps between primes, Ann. of Math., (to appear?).

PS. Новость для любителей числа π. Вчера-сегодня изучал некоторую числовую последовательность {a_n}. Оказалось, ёе члены с первого по 18-й равны [(n+1)^π/2]. Однако, дальнейшие выкладки склоняют к тому, что a_n=(4/3)n^3/2- n/2+O(n^1/2).

PPS. Последовательность, кстати, возникает в задаче, имеющей следующую романтическую формулировку. В шестой серии «ГиБ» ИнтерГПол доверил Марте Эрастовне перевоспитание пиратов. Также для ещё более прекрасного далёка требуется определить критический этаж, т.е. такой наименьший этаж, при выбрасывании с которого пират перевоспитывается. Исправительное здание имеет n этажей, но номер критического этажа нам неизвестен. Им может быть любой этаж с равной вероятностью 1/(n+1) (ИнтерГПол допускает, что пираты окажутся стойкими и не перевоспитаются даже при падении с последнего этажа). Кроме того, если при падении пират перевоспитывается, то гуманные законы галактики не позволяют проводить над ним дальнейшие эксперименты. Помогите Марте Эрастовне найти ожидаемое число попыток при доброй стратегии, минимизирующей это число. Так вот, a_n/(n+1) и будет искомым числом.

[Н. Светлов]

такой наименьший этаж, при выбрасывании с которого пират перевоспитывается

Сурово. Но, наверное, эффективно. Мёртвый пират считается перевоспитавшимся?

[Весельчак Ы]

Если не перевоспитавшимся, то хорошим. Во всяком случае, не плохим.

PS. У меня нашли ошибку в математической интерпретации. Придётся пересчитывать, и связь {a_n} с π должна исчезнуть.

[Лилия]

Если не перевоспитавшимся, то хорошим. Во всяком случае, не плохим.

Это получится что-то из области, хороший пират, это мертвый пират. Или о мертвых либо хорошо, либо никак.

Придётся пересчитывать, и связь {an} с π должна исчезнуть.

Наверняка.

[Кот Матроскин]

Короче опять какая то философия...и никакого программирования

[Весельчак Ы]

А вот здесь вы, батенька, очень даже ошибаетесь, ибо после построения рекуррентной формулы для a_n, оказалось, что функция b_n=(n+1)a_n – целочисленная. После чего от программирования мне особо отойти не удалось, и всё нижеследующее это результаты вычислительной эвристики.

Оказывается, последовательность разностей b_n-b_n-1 имеет простой паттерн:

2, 3, 3, 4, 4, 4, 5, 5, 5, 5,...

Это дает возможность вычислить b_n-b_n-1=[(√(8n-7)+3)/2]. Также я получил оценку



Причем коэффициенты слева и справа были сначала вычислены как десятичные дроби, а потом выгуглены как радикальные выражения. Середина, делённая на √n, тоже имеет простой паттерн, однако аппроксимировать его, получив приближение b_n, лучшее, чем O(n), мне не удалось.

[Bitman]

Весельчак Ы,
Мне вот интересно, ведь наверно математикам сейчас очень нужно умение программировать?
И вообще я только недавно осознал, что программирование - это настоящая наука, имеющая отношение к математике и лингвистике. В Computer science есть свои теоремы и т.п.

[Весельчак Ы]

Мне вот интересно, ведь наверно математикам сейчас очень нужно умение программировать?

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

И вообще я только недавно осознал, что программирование - это настоящая наука, имеющая отношение к математике и лингвистике. В Computer science есть свои теоремы и т.п.

Вот я пишу статьи про изображение графов. Эта тематика настолько связана с приложениями, что на Западе относится к computer science, хотя по природе исследуемых объектов, уровню строгости и математическому формализму для нас это обычная математика. Поэтому я не считаю себя computer scientist или прикладным математиком.

В действительности же, по-моему, любые задачи в математике в той или иной степени обратные, и вообще вся математика посвящена решению обратных задач. ... По-моему, вся математика и всё computer science так или иначе сводится к оптимальным способам решения обратных задач.

Я думаю, что это мнение профаническое: поверхностное, одностороннее и поспешное. Я скорее сказал бы, что математика изучает формальные структуры аксиоматическим методом. См. например, "Архитектуру математики" Николы Бурбаки.

[Лилия]

Короче опять какая то философия...и никакого программирования

Матроскин, я вот тоже раньше думала, что в программировании всё точно, как в математике. Но здесь на форуме некоторые романтики, я полагаю занимающиеся программированием, мне объяснили, мол нет, бывает, что некоторые вариации невозможно предугадать.

[Bitman]

Обобщения (индукции) иногда работают, иногда нет (если только это не строгие математические индукции). Вот как раз тот пример, когда индукция не работает: несуществование "сверхформулы Кардано" - это теорема, следовательно, такая формула никогда не будет найдена.

Ошибаетесь! И я вам это докажу.
Когда говорят, что какое-то уравнение не решается (или например интеграл не берётся), подразумевается, что нельзя выразить корень этого уравнения в виде многочлена из набора известных алгебраических функций; этот набор включает в себя разные синусы, корни, логарифмы и т.п. Может я не совсем корректно пишу – не только многочлен, но и например многочлен с дробями (есть общее название для таких формул?).
Такие функции как корни и логарифмы считаются как суммы сходящихся рядов. Так вот на мой взгляд очевидно, что набор этих алгебраические функций будет рано или поздно расширен, туда добавят какие-нибудь гиперсинусы или гиперкорни. Между синусом и гиперсинусом не будет принципиально разницы – и то и другое можно будет вычислить как сумма сходящегося ряда.
И корни уравнений 7-й степени, неберущиеся интегралы можно будет выразить через эти, пока ещё не открытые, новые алгебраические функции, например как включающий их степенной многочлен.
Можно привести аналогию с интегралами: есть берущиеся интегралы и есть типа не берущиеся, но в то же время абсолютно любой интеграл можно посчитать как сумма ряда (Тейлора если не ошибаюсь).
Вопрос лишь в том, оптимальны ли вычислительные затраты с тем или иным методом. Я думаю, когда научатся решать уравнения 5-й степени через “гиперкорни”, решение будет отнимать в тысячи раз меньше машинного времени, чем решение, например, через ряды Штурма.

[Н. Светлов]

И корни уравнений 7-й степени, неберущиеся интегралы можно будет выразить через эти, пока ещё не открытые, новые алгебраические функции, например как включающий их степенной многочлен.

В таком случае задачу решает отображение вектора коэффициентов уравнения на вектор его корней. Это прекрасно изученная многомерная алгебраическая функция, для которой известны вполне эффективные численные вычислительные методы - не хуже, чем для того же квадратного корня.

Возможно ли выражение через "ещё какие-то" функции - например, решение уравнения 7-й степени через вышеуказанное отображение 5-й степени? Почему бы и нет? И это действительно интересная задача, которая, быть может, приведёт к интересным теоремам об уравнениях высших степеней - таким, которые имеют физическую интерпретацию и откроют нам глаза на природу каких-либо процессов, которые нам покамест непонятны.

Однако я не думаю, что обоснование таких "imho" через индукцию состоятельно. Оно может быть стимулом для поиска, но в случае неудачи нет причин удивляться.

[Bitman]

Кстати, если уравнения третьей и четвёртой степени научились решать с помощью комплексных чисел, может уравнения 5-й степени решат с помощью кватернионов? А далее седенионов и т.д.?

[Bond]

Кстати, если уравнения третьей и четвёртой степени научились решать с помощью комплексных чисел, может уравнения 5-й степени решат с помощью кватернионов? А далее седенионов и т.д.?

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

[Кот Матроскин]

это тупик

а атака в лоб с помощью численных методов и ЭВМ?

[Bond]

численные методы это не интересно, мы же хотим найти Универсальную Формулу Мироздания