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

Пытаюсь найти хороший численный алгоритм для решения уравнения f(t) = 0. Нужно не просто решение, а минимальный положительный корень.

Метод Ньютона (касательных) имеет хорошую сходимость, но очень не любит функции с экстремумами. Например f(t) = cos(t) + cos(50 t) / 5 будет ему не по зубам - касательные будут прыгать туда-сюда. Про f(t) известно только то, что она непрерывна, и, скорее всего - бесконечно-диффиренцируема.

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

x = x0 + m t
y = y0 + n t
z = z0 + z t

Подставляю x, y и z в F, получаю уравнение F(x0 + m t, y0 + n t, z0 + p t) = 0. То есть, некоторое уравнение одной переменной f(t) = 0. Его и нужно решить численно.

Вот пример (PNG, ~331 кб) использования двух алгоритмов на одной и той же поверхности. Простой итеративный поиск с константным шагом (слева) и метод Ньютона (справа). На картинке видно, что простой поиск дает лучшую решаемость, но плохое качество - это видно по гранености бликов. Ньютон дает хорошую точность (гладкие блики), но решабельность плохая. Особенно, когда луч пронизывает поверхность несколько раз.

Итак, задача - численно найти первую точку пересечения луча и поверхности. То есть, найти минимальный положительный корень f(t) = 0. Ньютон имеет хорошую скорость и точность, но плохую сходимость. Итеративный аглогитм с константным шагом - плохую точность, хорошую сходимость, и совершенно неприемлемую скорость. Хочется чтобы и сходилось, и точно, и быстро. Что бы вы посоветовали?

PS. spa, qqwe, Matan, и т.д. - пожалуйста, умоляю, не пишите в этом топике.

 

Немного напутал в применении термина "сходимость". Имелось ввиду, что Ньютон сходится реже, чем константный шаг, но если сходится, то результат более точен.

 

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

 

_DEN_, есть хороший пакет ALGLIB для решения подобных задач. считает и уравнения и интегралы и нейросети и много чего ещё. очень рекомендую.

 

Pavia

Начальные условия всегда одни - t = 0.

Можно показать, как предварительно использовать постоянный шаг на, например, такой функции?

 

cupuyc

Сторонние проги тут не помогут - мне нужно считать самостоятельно в своей проге.

 

попробуйте квазиньютоновские методы типа БФГС, так как ньютон - он жуткий боян. также на долбонутых функциях довольно эффективны ген-алгоритмы

 

Freeman

А что это за методы? Гугл говорит Результаты 1 - 1 из примерно 0 для численный метод БФГС.

 

http://www.google.com.ua/search?q=BFGS

 

Freeman

Хм... Как я понял, BFGS это численный поиск стационарных точек функции многих переменных? Умение искать стационарные точки мне как-то поможет научиться решать уравнение?

 

Pavia

Если я все правильно понимаю, то на первом этапе нужно поймать такой отрезок, внутри которого есть интересующий корень, и нет экстремумов. Но если научиться находить такой отрезок, то тут и дихотомия прекрасно справится. Если же внутри отрезка будет экстремум, то он уже может "увести" алгоритм далеко в сторону - например если касательная f(xn) будет "смотреть" в противоположную от корня сторону.

 

Вот комбинация постоянного шага и Ньютона. Ищутся решения начиная с t = 0, 1, 2, 3, ... 9, и среди них выбирается минимальное положительное. Результат заметно лучше, но все еще неудовлетворительный.

 

это не прога, а библиотека с открытыми сорцами. попробовать стоит хотя бы для того, чтобы убедиться, что метод уточнения корней для вашей функции вообще сходится.

 

cupuyc

Дык не могу я попробовать - raytracing считается на фрагментном шейдере видеокартой И на каждый кадр у меня 800х600 = 480000 разных функций

 

_DEN_, нет, это метод минимизации функции многих переменых.

 

В этом случае можно попробовать методы, которые не требует производной функции или её градиента. Например, метод Недлера-Мида или метод главных осей. Сходимость хорошая.

 

W4FhLF

Но как перейти от поиска экстремума к поиску корня?

 

_DEN_
http://www.ray-tracing.ru/
тут в разделе "Быстрая трассировка лучей" есть несколько алгоритмов.

 

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

Может сюда заглянешь: http://en.wikipedia.org/wiki/Category:Root-finding_algorithms

Методов много в прицнипе. Ты смотрел что-нибудь ещё?

 

_DEN_
как варианты:
http://ru.wikipedia.org/wiki/Метод_секущих
http://ru.wikipedia.org/wiki/Метод_хорд
Методу хорд вообще по-барабану на поведение функции, насколько помню.