Рекомендации по интерполяции (линейный, кубический?)

Question

Мне нужно найти хорошее приближение точек, где неопределенная функция пересекает пороговое значение. Я пересекаю свое пространство и всякий раз, когда обнаруживаю, что два последующих шага находятся по разные стороны от порога, я добавляю точку где-то посередине:

_{(источник: ning.com )}

Мой первый подход состоял в том, чтобы просто выбрать середину, но это, очевидно, ужасное решение:

_{(источник: ning.com )}

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

_{(источник: ning.com )}

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

_{(источник: ning.com )}

Или есть лучшие способы?

Очень обязан, Дэвид Руттен

пс. Я пишу на C #, но это не зависит от языка.

Answer 1

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

Самый простой способ - просто пропустить (уникальный) полином через все четыре точки.

Другой способ - использовать касательные. Опять же, нам нужно четыре очка. Пусть две левые точки определяют наклон. Пусть полином проходит через точку second (обычно она не проходит через первую точку) и соответствует вычисленному уклону в этой точке. И то же самое с правой стороны для четвертого и третьего пункта.

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

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

Обновление : глупо, я оставил предложение, ссылаясь на два способа, не печатая их. Напечатал их сейчас.

Answer 2

Волшебное слово "корень решатель"; математический корень - это значение, при котором функция равна нулю. Добавляя / вычитая порог, вы можете использовать корневые искатели.

Если у вас есть подсказка, какую функцию вы интерполируете, вы можете настроить очень быстрый корневой искатель. Если у вас нет подсказки, как подсказывает ваш пост ("undefined"), лучшим методом является "метод Брента", комбинация "secant method" и "bisection" или "secant" метод "один. В Википедии есть запись для этого метода.

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

Метод Ньютона-Рафсона ОЧЕНЬ ПЛОХО, если вы находитесь рядом с точкой максимума / минимума / перегиба, потому что производная, близкая к нулю, отсылает вас далеко от точки, и с ней возникают другие проблемы. Не используйте его, пока не узнаете, что делаете.

Answer 3

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