2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Численный поиск экстремалей
Сообщение09.11.2009, 00:49 
Аватара пользователя
Возник вопрос, какие существуют численные методы решения самой обыкновенной вариационной задачи? Ну т.е. дан функционал
$$\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$ в явном виде не входит). Кто-нибудь знает ещё способы численного решения? Меня бы вполне устроила ссылка на литературу.

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

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

 
 
 
 Re: Численный поиск экстремалей
Сообщение10.11.2009, 22:16 
Аватара пользователя
mserg в сообщении #260056 писал(а):
Выбираете сетку по x, например, равномерную. Производные заменяете разностями, а интеграл – суммой.
Ну чисто в лоб. А вы пробовали оценивать погрешность для такого решения?

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

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

 
 
 
 Re: Численный поиск экстремалей
Сообщение10.11.2009, 23:53 
Точность подсчитать не пробовал. А как это сделать? Речь ведь идет о "расстоянии" до глобального минимума функционала?

 
 
 
 Re: Численный поиск экстремалей
Сообщение11.11.2009, 16:05 
Аватара пользователя
Погрешность можно взять, например, как максимальное «расстояние». Что-то вроде
$$\Delta = \max_{x\in [a,b]} |f(x) - f_1(x)|,$$
где $f_1(x)$ — численное решение.

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

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

 
 
 
 Re: Численный поиск экстремалей
Сообщение24.11.2009, 22:22 
А каковы условия применения оценки точности?

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

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

 
 
 [ Сообщений: 8 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group