Пусть некоторый пользователь в моменты времени $%T_i (i=1..N)$% получает $%D_i$% баллов уважения. $%T_{i+1}\gt T_i$%. $%D_i\ne0$%. $%T_1$% - момент регистрации пользователя. $%D_1=1$%. Обозначим количество очков уважения в момент $%t$% как функцию $%B(t)$%, определенную на $%t\in(-\infty;T_N]$%. $$t\lt T_0\Rightarrow B(t)=0;\space T_i\le t\lt T_{i+1}\Rightarrow B(t)=S_i=\sum_{k=1}^i D_k$$ Ни для кого здесь не секрет, как ХэшКод и многие другие системы строят график уважения/рейтинга - соединяют прямыми линиями точки $%(T_i;S_i)$%. При этом, к примеру, если пользователь с января прошлого года не получал баллов, а в декабре вернулся и ему сразу же кто-то подарил 100500 очков, то на графике это будет смотреться так, будто он набирал эти очки на протяжении всего года, что не правда. Моя цель - построить график уважения, отражающий эту особенность, т.е. более близкий к $%B(t)$%, но при этом сохраняющий "гладкость". Формальные требования к функции:

  • дифференцируема
  • определена на $%t\in(-\infty;T_N]$% $$F(T_i)=S_i$$ $$\lim_{t\rightarrow-\infty}F(t)=0$$ $$(\forall i)D_i\gt0\Rightarrow (\forall t)F'(t)\ge0$$

Неформальные требования:

  • разница между $%F(t)$% и $%B(t)$% должна быть небольшой
  • сильный рост/убывание функции должны происходить поближе к $%T_i$% (что, собственно, является следствием предыдущих требований)
  • величина $%|F''(t)|$% (там, где она определена) не должна быть слишком большой, т.е. график не должен быть "дерганым" и "ступенчатым"

Вопрос:

  • какие можно выбрать критерии "правдоподобия" функции? единственное, что приходит в голову, - это $$\sum_{i=1}^{N-1}\frac{\int_{T_i}^{T_{i+1}}\left(F(t)-B(t)\right)^2dt}{T_{i+1}-T_i}\rightarrow\min$$
  • есть какие-то идеи по поводу самой $%F(t)$%? мне пока-что думается составить ее из суммы степенных функций

задан 14 Фев '13 15:49

10|600 символов нужно символов осталось
1

А не подойдёт ли для этой цели такая функция, которая "кусочно" состоит из графиков парабол? Если заданы значения функции на отрезке, а также производная на левом конце, то квадратичная функция этим определяется однозначно. Тогда можно, считая производную в нуле равной нулю, построить график последовательно по таким "кусочкам". Задали график, стала известна производная на правом конце, и её приравниваем к производной на левом конце следующей части графика. Получится функция класса $%C^1$%, и график, скорее всего, получится "гладкий" на вид. Но лучше это проверить экспериментально. Сам метод построения -- очень простой.

ссылка

отвечен 15 Фев '13 3:17

Мы не знаем производных (хотя, можно предположить, что $%F'(T_i)=cD_i,c=const$%). Да и графики интерполяции полиномами часто бывают очень страшными: из-за жестких условий коэффициенты полиномов (не только парабол) получаются огромными, график - огромные волны.

(15 Фев '13 5:59) chameleon

Производные находятся по рекуррентным формулам. Если есть отрезок $%[a,b]$%, и мы знаем $%f(a)$%, $%f(b)$%, а также $%f'(a)$%, то квадратичная формула для $%f(x)$% находится однозначно. Из неё мы далее находим $%f'(b)$%, и это значение становится производной в начальной точке следующего отрезка $%[b,c]$%, и так далее. Начальное значение $%f'(0)$% в нулевой момент времени можно положить равным нулю, так как рейтинг был нулевым при всех $%x<0$%.

Вполне возможно, что рисунок такого типа получится не очень красивым, но я не проверял этого на практике.

(15 Фев '13 6:23) falcao

Знаю я, как интерполяцию полиномом делать. Я вот, как раз, проверял это на практике. И опыт мне говорит, что в данном случае параболы - не выход, в основном из-за широкого разброса $%T_{i+1}-T_i$%. Не будет соблюдено даже последнее формальное требование (о монотонном возрастании функции).

(15 Фев '13 6:51) chameleon

А почему не будет монотонного возрастания? Если $%f(a)<f(b)$% и $%f'(a)\ge0$%, то квадратичная функция $%f(x)$% будет возрастать на отрезке.

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

(15 Фев '13 7:02) falcao

Из-за того, что мы зафиксировали производную только в одной точке, а все остальные строго ей определяются и совсем не обязаны быть положительными. Чтоб долго не спорить, приведу пример: $%F(0)=1;F(1)=16;F(1000)=18;F(1001)=33$%. Если напишите соотв. неубывающую функцию, значит я был не прав или неправильно Вас понял.
UPD: м-да, похоже неудачный пример. добавлю ка я еще $%F(2000)=35$% =)

(15 Фев '13 7:28) chameleon

Я исходил вот из какого соображения. Рассмотрим параболу, проходящую через точки $%(a,f(a))$% и $%(b,f(b))$%. Пусть ветви направлены вверх. Поскольку $%f'(a)\ge0$%, то это происходит на правой ветви, то есть далее функция возрастает, и $%f'(b)>0$%. Но сейчас я заметил, что ветви могут быть направлены и вниз. Это возможно, если $%f'(a)$% большое, а изменение функции на $%[a,b]$% невелико. Тогда парабола (с ветвями вниз) может возрастать до некоторой точки, и далее слегка идти вниз. Возможно, в Вашем примере будет как раз так -- надо будет сегодня проверить в Maple.

(15 Фев '13 7:49) falcao

Я сейчас написал программу для Maple и посмотрел, что будет для таких данных: $%1,3,4,6,11$% и $%0,2,5,8,9$%. Это абсциссы и ординаты точек графика, соответственно. Кусочно-параболическое приближение там получается "нехорошее", то есть у части парабол ветви идут вниз. То есть, Вы были правы, что в общем случае такой способ не подходит. Что если разрешить тогда кубические полиномы на промежутках? Такое ощущение, что здесь уже дополнительные степени свободы позволят обеспечить монотонность.

(15 Фев '13 15:38) falcao

Нет, полиномы тут в принципе не подходят

(15 Фев '13 17:04) chameleon
показано 5 из 8 показать еще 3
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×158
×17

задан
14 Фев '13 15:49

показан
716 раз

обновлен
15 Фев '13 17:04

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru