Численный поиск экстремалей

[ibelov]

Возник вопрос, какие существуют численные методы решения самой обыкновенной вариационной задачи? Ну т.е. дан функционал

$$\mathcal{F}[f(x)]=\int\limits_a^bF(f'(x),f(x),x)\,dx$$

и надо найти такую $f(x)$ которая доставляет экстремальное значение $\mathcal F[f(x)]$. Понятно, что можно составить уравнение Эйлера-Лагранжа и решать уже его, но не всегда это будет просто. В справочнике нашел о так называемых «прямых методах», когда $f(x)$ приближают суммой из какой-то последовательности известных $g_n(x)$, интегрируют и сводят задачу к поиску экстремума функций многих переменных (коэффициенты для $g_n(x)$). Всё это конечно круто, но тоже не очень устраивает, т.к. у меня подынтегральная функция представляет собой сумму от всяческих произведений разных степеней $f(x)$ и $f'(x)$ ($x$ в явном виде не входит). Кто-нибудь знает ещё способы численного решения? Меня бы вполне устроила ссылка на литературу.

[mserg]

Выбираете сетку по x, например, равномерную. Производные заменяете разностями, а интеграл – суммой. Возникает задача о поиске минимума функции с большим количеством переменных. Выбираете/подбираете метод минимизации - и вперед. Сам я использую для решения таких задач метод внутренней точки.

[jetyb]

Для всяких многочленов от $t,f(t),f'(t)$ помогает принцип максимума в Понтрягинской форме. В результате получается система типа $\dot{X}=A(X)$, которая обычно неплохо решается методом Рунге или стрельбы.

[ibelov]

mserg в сообщении #260056 писал(а):

Выбираете сетку по x, например, равномерную. Производные заменяете разностями, а интеграл – суммой.

Ну чисто в лоб. А вы пробовали оценивать погрешность для такого решения?

jetyb в сообщении #260203 писал(а):

Для всяких многочленов от $t,f(t),f'(t)$ помогает принцип максимума в Понтрягинской форме. В результате получается система типа $\dot{X}=A(X)$, которая обычно неплохо решается методом Рунге или стрельбы.

Спасибо. Поищу в книжках как время будет. А какого порядка получается система?

[mserg]

Точность подсчитать не пробовал. А как это сделать? Речь ведь идет о "расстоянии" до глобального минимума функционала?

[ibelov]

Погрешность можно взять, например, как максимальное «расстояние». Что-то вроде

$$\Delta = \max_{x\in [a,b]} |f(x) - f_1(x)|,$$

где $f_1(x)$ — численное решение.

Решая численно уравнение Эйлера-Лагранжа я такую оценку сделать могу.

P. S. Надо бы про этого Понтрягина почитать...

[mserg]

А каковы условия применения оценки точности?

Этот вопрос возникает у меня по множеству причин. Например, представим себе вариационную задачу - нахождение пути минимальной длительности по холмистой местности. Эта задача содержит ограничение, но можно предложить близкую к ней без ограничений. Суть не в этом - задача имеет множество локальных минимумов (путей). Т.е. уравнение Эйлера-Лагранжа имеет множество решений (различных функций). Как гарантируется глобальный минимум и точность чего (к чему) гарантируется?

[Lyoha]

Обычные градиентные методы вполне работают. Если предположить $f$ и $F$ достаточно хорошими. А вот вопросы глобальности найденного минимума так просто не решаются. Только специальные знания о функционале или возможность построения сетки начальных значений, гарантирующей, что один из полученных минимумов будет глобальным.