Аппроксимация графика по точкам [сплайны литература]

[Disore]

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

График с линейной аппроксимацией:


Необходимо:
Интерполировать график то ли сплайном третьего порядка, то ли какоим-то полиномом, в общем главное, чтобы линия проходила четко через все точки и была гладкая кривая. Чтобы не было разрывов первого и второго родов и чтобы функция так же монотонно возрастала.

Пробую сиё сделать в пакете STATISTICA, но там никакая аппроксимация не проходит через точки (кроме линейной).
Посоветуйте что делать..

[ewert]

Disore в сообщении #294653 писал(а):

чтобы линия проходила четко через все точки

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

Но -- не глобально, конечно. На втором участке -- своя аппроксимация, на третьем -- своя.

А для первого и вовсе никаких мало-мальски достаточных данных для аппроксимации нет. Там, в принципе, может быть всё что угодно.

[Disore]

Не не не, нету шума. Не нужен метод наименьших квадратов. Каждое след. значение больше предыдущего. Эти значения подобны количеству просмотров видео на Ютубе к примеру, то есть в момент выкладывания видео просмотров 0, а с течением времени они растут. Так и здесь. Надо что-то, что будет проходить явно через все точки. А как эта аппроксимация сработает на первом участке не столь критично, главное "проехать" через все точки.

[godsdog]

Вы можете интерполлировать
1) возможно, что Ексель умеет интерполлировать данные
2) в Ориджине (кубичекий сплайн, например)
3) написать простенький код (работающий алгоритм можна найти в Википедии)
4) можете выслать мне данные, я прогоню через свою программу, и вышлю Вам результат аппроксимации (быстро сделать не обещаю).
5) могу выслать вам код на фортране, и Вы прогоните данные сами. А если ещё и укажите мне на возможную оптимизацию, то я Вам буду ещё и признателен. Хотя вряд ли удасться там что-либо оптимизировать, уж больно простой код.

[worm2]

http://en.wikipedia.org/wiki/Monotone_cubic_interpolation

[faruk]

Disore в сообщении #294653 писал(а):

Disore в сообщении #294669 писал(а):

Каждое след. значение больше предыдущего. Эти значения подобны количеству просмотров видео на Ютубе к примеру, то есть в момент выкладывания видео просмотров 0, а с течением времени они растут.

Может быть это: http://ru.wikipedia.org/wiki/Логистическое уравнение ?

[GAA]

Если классический кубический сплайн окажется монотонным, то, возможно, лучше использовать именно его. Достаточные условия монотонности классического кубического сплайна приводятся в работе
Волков Ю.С. О монотонной интерполяции кубическими сплайнами. // Вычислительные технологии. Т.6, № 6, (2001). pdf.
(В этой работе можно найти и ссылки на другие публикации посвященные данной тематике.)

В сети свободно доступна и работа
Пинчуков В.И. ENO-модификация нелокального кубического сплайна на равномерной сетке // Вычислительные технологии. Т.5, № 6, (2000).pdf

[ewert]

GAA в сообщении #294866 писал(а):

Если классический кубический сплайн окажется монотонным,

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

[fer1800]

А в чём проблема?
Полином трудно составить?

-- Пт мар 05, 2010 23:54:31 --

Вот смотрите.
У вас есть точки и значения функции в этих точках - соответственно можно составить полином P(x).
Далее его надо сделать возрастающим.
Допустим у вас точки a, b, c
Вы составляете дополнительный полином R(x)=(x-a)(x-b)(x-c).
Ясно, что полином P(x)+R(x) в точках a,b,c , будет давать нужные цифры.
Добьёмся, чтобы полином R(x) всюду возрастал.
Допустим, что это не так и в точке x=e функция R(x) начинает убывать (а до этого всюду возрастала). Тогда полином D(x)=(-x+e)R(x) будет уже возрастать и после точки x=e.
Допустим, что мы добились того, что функция D(x) всюду возрастает, т.е. её производная больше нуля и её минимальное значение на указанном промежутке равно M1.
Возьмём теперь производную от функции P(x). Допустим, что она не всюду положительна, но тогда на указанном промежутке, очевидно, она достигает своего минимума M2.
Очевидно существует такое число E>0, что E*M1>|M2|.

Функция P(x)+E*D(x) будет монотонно возрастать, она будет гладкой, в нужных точках будет приниматиь нужные значения.

[fer1800]

У меня ошибка в выборе полинома D(x)

-- Сб мар 06, 2010 01:08:13 --

Для нахождения функции D(x) можно воспользоваться тем обстоятельством, что если D(x)=R(x)*F(x), то функция F(x) может быть любой.
Положим
$D(x)=e^{T(x)} \cdot R(x)}$
Чтобы производна от функции D(x) была положительной, требуется выполнение неравенства:
$T(x)' \cdot R(x)+R(x)'>0$
Возьмём $T(x)'=\frac {-R(x)'+1}{R(x)}$
Нужная функция T(x) определяется.

[fer1800]

ewert в сообщении #294935 писал(а):

GAA в сообщении #294866 писал(а):

Если классический кубический сплайн окажется монотонным,

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

нужный график построить можно, но я согласен с ewert

[GAA]

ewert, в своем предыдущем сообщении я в первую очередь пытался дополнить worm2 (в указанных мною статьях даны ссылки на более поздние работы, посвященные интерполяцией монотонными сплайнами, по сравнению со ссылкой в википедии). [Опять же я не отметил какие ограничения надо наложить на функцию, и эти ограничения не указаны топикстартером. Много чего я не указал. Пусть Disore в литературе по ссылкам в статьях это посмотрит.]

(Оффтоп)

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

[ewert]

Нечаянно испортил сообщение. Приношу свои извинения и прошу автора восстановить сообщение.

В исходном сообщении говорилось: несмотря на то, что автор вопроса говорит о том, что данные без шума, они, очевидно, шум содержат. // GAA

[yasya17]

МАТЛАБ, функция pchip (кусочно гладкая функция, пройдёт через все точки)

[Александрович]

Disore в сообщении #294669 писал(а):

Не не не, нету шума. Не нужен метод наименьших квадратов. Каждое след. значение больше предыдущего. Эти значения подобны количеству просмотров видео на Ютубе к примеру.

Пример, который вы привели говорит как раз о наличии случайной составляющей, то есть о шуме.