Численное решение уравнения f(t) = 0

W4FhLF

Пробовал только самое простое - Ньютон, метод секущих, постоянный шаг, и их комбинации. Более "тяжелые" алгоритмы видяха боюсь не вытянет.

 

Ustus

Метод хорд юзал. Это он же - метод секущих? Он все-таки тоже ошибается. Меньше чем однопроходный Ньютон, но ошибок достаточно много чтобы было несмотрабельно

 

Ustus

Кстати да, методу хорд видимо действительно побарабану - в нем вроде бы не было черных точек (мест, где метод не сошелся), корни он находит всегда. Проблема в том, что не всегда тот что нужно (наименьший положительный)

 

_DEN_
А если после нахождения какого-то корня продолжать их искать только уже на интервале от 0 до найденного корня?

 

Black_mirror

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


W4FhLF

Спасибо за ссылку. Буду пробовать вот эти алгоритмы:

Halley's method
Householder's method
Inverse quadratic interpolation
Steffensen's method

Кстати, вопрос по Householder's method. Что там означает (1/f)? Это обратная функция от f, или функция полученная делением, 1/(f(x))?

 

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

 

UbIvItS
Судя по изображениям, она вовсе не монотонная.

 

KeSqueer
судя по всему, человеку нужен код учитывающий разные случаи, а стало быть в частных случаях будут и монотонные функи.

 

Это reciprocal function. Обратная.

Почему выбрал Householder?

Я думаю для сложных функций следует попробовать прежде всего Steffensen's method как один из тех, что не требует производной. Он достаточно простой.
Также можно посмотреть на Brent's method, комплексный метод, но он робастный, что как-раз и требуется для функций типа f(t) = cos(t) + cos(50 t) / 5.

 

Это называется bisection method.

 

W4FhLF

Такс... Сегодня меня просвятили - оказывается сегодня для рейтрейса никто не юзает обобщенную F(x, y, z) = 0. Юзается ее частный случай - distance field. То есть та же F(x, y, z), но значение которой имеет определенный геометрический смысл. А именно - кратчайшее расстояние до объекта. Алгоритм трассировки существенно упрощается, уравнения решать не нужно.

Спасибо еще раз за ссылку на список root finders. Если еще раз возникнет такая задача - начну именно оттуда

 

_DEN_

Что-то непонятно. А как находить кратчайшее расстояние до объекта?

 

W4FhLF

Посчитать значение функции Смысл в том, что мы ставим себе условие - юзать не любую F(x, y, z), а только ту, что является дистанс филдом. Например, если мы ходим сферу, то пишем F(x, y, z) = sqrt(x^2 + y^2 + z^2) - R

 

_DEN_

А сфера это типа область видимости?

 

W4FhLF

Насчет области видимости не совсем понял. Distance field это поверхность, заданная по правилу: если F(x, y, z) = 0, то точка (x, y, z) принадлежит поверхности. Иначе - численное значение в точке (x, y, z) равно кратчайшему расстоянию до поверхности от точки (x, y, z). Если функции поверхностей из первой страницы топика, заданные уравнением F(x, y, z) = 0 не имели общего геометрического смысла в точках, где функция не равна нулю, то distance field - это подмножество таких функций, у которых значение функции, отличное от нуля, имеет определенный геометрический смысл (кратчайшее расстояние до поверхности).

 

_DEN_

Ясно теперь, спасибо.

 

W4FhLF

Вот например. 4 источника света, 1 дистанс филд, задающий бесконечность шариков.

 

Теперь это топик про скрины рейтрейса ))

http://img251.imageshack.us/img251/3523/newrt.png (2,3 мегабаета)

 

_DEN_, я так понимаю можно задать любую фигуру, которая описывается аналитически? А если у меня сложное тело, типа mesh какой-нибудь?

 

W4FhLF

Да.

Каждое тело описывается своей функцией. А F(x, y, z), с которой мы работаем, возвращает минимальное значение всех функций в заданной точке.