Поиск решения уравнения, Оптимизация поиска

uaha1979

Есть уравнение f(x) - v = 0;
f(x) - сколь угодно гладкая,
f(t0) = v,
f '(t0) < 0,
f(x) = a + ... over 9000 символов ... b; =)
Все производные f(x) имеются в явном виде.
Задача найти следующее решение (которое обязательно будет).
Сейчас мое решение:
Берем шаг dx, идем с ним, как только нашли f(x1) < 0 && f(x1 + dx) > 0, применяем метод деления отрезка пополам.
Слишком медленно получается.
Охота сделать dx побольше.
Например сначала ищем локальный минимум методом градиентного спуска, потом локальный максимум, итд... пока не получим f(x1) < 0 && f(x1 + dx) > 0, или не попадем в условия метода Ньютона.
Есть ли менее наркоманские способы?

SPARTAK3959

Если про функцию больше ничего не известно, то никаких хороших алгоритмов нет.
Я бы взял отрезок на котором мы ищем корень. Если знаки разные - делим пополам. Если одинаковые - добавляем в приоритетную очередь. Оценка в приоритетной очереди отрезка $[math]$[x_1,x_2]$[/math]$ , к примеру, $[math]$C\ln(\min(|f(x_1)|,|f(x_2)|-\ln(|x_1-x_2|)$[/math]$ . Константу С берем 2-3 - посмотри как лучше на практике работает. После чего выбираем отрезок с минимальной оценкой и делим пополам. Если нет разных знаков, то засовываем оба отрезка обратно в приоритетную очередь.

uaha1979

Я бы взял отрезок на котором мы ищем корень

Непонятно что делать, если отрезок взят неверно:
1. решений на отрезке нет,
2. решения на отрезке более одного, можем найти не то решение.
//******************************************************//
Придумал другой метод:
Допустим v - f(x_n) = а, а > 0,
И известен х*: f '(x*) - максимум f '(x) на [x_n, х*]
тогда x_(n+1) = x_n + а/f '(x* прошли "а" с максимальной скоростью, при таком шаге мы не перепрыгнем v,
или x_(n+1) = x_n + dx, если dx > a/f '(x*)
х* ищется градиентным спуском
//******************************************************//
где можно почитать как в Mathematic 7.0 реализован поиск решений уравнения?

nawok

где можно почитать как в Mathematic 7.0 реализован поиск решений уравнения?

Там реализовано несколько методов, они задаются параметром Method, см. хелп Options -> Method. Параметры функции еще можно смотреть прямо в программе, если набрать в отдельной ячейке ? FindRoot и нажать Shift+Enter.

marina7573

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

Охота сделать dx побольше.
Например сначала ищем локальный минимум методом градиентного спуска, потом локальный максимум, итд... пока не получим f(x1) < 0 && f(x1 + dx) > 0, или не попадем в условия метода Ньютона.

Я бы так и делал. Можешь почитать про квазиньютоновские методы, они чутка быстрее

Ivan8209

> Есть уравнение f(x) - v = 0;
> f(x) - сколь угодно гладкая
Метод Брента.
> Например сначала ищем локальный минимум методом градиентного спуска
Забудь методы оптимизации со словами "градиентный спуск" и
"скорейшего спуска."
Для многомерного случая есть Broyden-Fletcher-Goldfarb-Shanno,
для одномерного есть варианты типа метода Пауэлла (Powell
например, приближение квадратичной функцией, минимум которой ты
всегда легко вычисляешь.
И открой для себя существование такой книги, как "Numerical Recipes."
---
"Vyroba umelych lidi, slecno, je tovarni tajemstvi."

Оставить комментарий