Прямые и обратные задачи
От: Khimik  
Дата: 03.01.19 12:32
Оценка: 9 (2) :)
Я занимаюсь квантовой химией, и раньше занимался близкой ей по задачам газовой электронографией. У нас электронографисты любят фразу “квантовики решают прямую задачу, а мы обратную”. Эта фраза мне понятна: расчёт изначально находит структуру, а в электронографии структура определяется через МНК (градиентный спуск) по экспериментальным данным.
В действительности же, по-моему, любые задачи в математике в той или иной степени обратные, и вообще вся математика посвящена решению обратных задач. Возьмём для примера пять уравнений:
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 так или иначе сводится к оптимальным способам решения обратных задач. И тут можно развить тему для программистов. Я прихожу к выводу, что при программировании сложных алгоритмов полезно применять “тяжёлые ассерты”: это такие ассерты, которые проверяют всё сразу. Эти ассерты довольно легко реализовать, но они сильно тормозят работу программу, поэтому их нужно отключать даже не только в финальном билде программы, но и вообще почти всегда, за исключением моментов когда нужно проверить критические участки алгоритма. С тяжёлыми ассертами баги должны легко выявляться. Так вот это всё тоже входит в изначальную тему: ассерты – это тоже вспомогательное решение прямой задачи, позволяющее проверить насколько корректно решается обратная.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.