Ищу алгоритм.

← →
Гриф (2001-11-28 11:33) [0]

Может, кто в курсе, где посмотреть.
Задача:
Есть график, построенный по N точкам (не функция).
Необходимо получить M точек этого графика.
Возможны случаи: M > N и M < N.
Первая и последняя точки совпадают.

Кое-какие исходники у меня есть, но они без комментариев,
не полные, на QBasic-е и сделаны для частного случая...

← →
Labert (2001-11-28 11:50) [1]

Нужно по этим N точкам построить функцию (этот процесс называется аппроксимация). Возможные методы:
1. построить интерполяционный многочлен Лагранжа
2. интерполяционный многочлен Ньютона

Подробнее об этом можно прочитать в книге Бахвалова "Численные методы"

или вот ссылочка есть:

http://www.exponenta.ru/educat/class/courses/vvm/theme_8/theory.asp

← →
Гриф (2001-11-28 13:28) [2]

> Labert (28.11.01 11:50)
Спасибо за ссылочку.
Интерполяционный многочлен - это первое, что мне пришло в голову,
но боюсь, что он мне не подходит.
Поэтому я надеюсь найти другие методы.

← →
Romkin (2001-11-28 14:28) [3]

Так интерполяционных методов немного - полином, Фурье (тригонометрический полином), экспоненциальный полином, сплайны. Полином не подходит, по-моему, если первая и вторая производные имеют разные знаки

← →
Гриф (2001-11-28 17:35) [4]

> Romkin © (28.11.01 14:28)
Я больше склоняюсь к сплайнам. Но пока не нашел хорошей литературы.

← →
Romkin (2001-11-28 18:20) [5]

Так в общем почти то же самое
http://delphi.mastak.ru/cgi-bin/forum.pl?look=1&id=1006897561&n=0
Сплайны - ссылка выше, но там граничные условия нужно задавать, а их не всегда подберешь. Только пару раз пользовался интерполяцией, после - только аппроксимация, гораздо удобнее, особенно если точки с погрешностью.
А критерий какой - обязательное прохождение через точки?
Какие еще условия, может достаточно просто линейной интерполяции между точками?

← →
Гриф (2001-11-29 09:42) [6]

>Romkin © (28.11.01 18:20)
Спасибо. Я вчера эту ветку обнаружил.
Ссылки там полезные (уже кое-что подобрал себе).

> А критерий какой - обязательное прохождение через точки?
Правильнее сказать - максимально близко.

> Какие еще условия, может достаточно просто линейной интерполяции между точками?
Увы, обрабатываемые графики могут иметь совершенно непредсказуемое
поведение (прямая, полином, периодическая). Линейной интерполяцией,
следовательно, пользоваться нет желания.

Вобщем, буду работать сплайнами. Еще раз спасибо.

Ищу алгоритм. Найти похожие ветки