Интерполяция

 Помогие начинающему! Подскажите как реализовать метод интеполяции на С++, если даны, например, ключевые точки? :-[

А какой? Их до чёрта. Линейная, квадратичная и прочая полиномиальная и т.д.

Держи простейшую. x1...xn - заданые точки, f1...fn - значение функции в них

Цитата

f(x)=f1*((x-x2)*(x-x3)*...*(x-xn)/(x1-x2)*(x1-x3)*...*(x1-xn))+
 f2*((x-x1)*(x-x3)*...*(x-xn)/(x2-x1)*(x2-x3)*...*(x2-xn))+...+
  fn*((x-x1)*(x-x2)*...*(x-x(n-1))/(xn-x1)*(xn-x2)*...*(xn-x(n-1)));

f(x) - интерполирующий полином n-1 порядка.

Интерполяция полиномом Лагранжа простейшая???!?!!?!?!?! А квадратичная - проще, быстрей, и при правильном использовании выглядит красиво.  ;)

Если не влом покажи как делать квадратичную(Лагранж конечно рулит, но очень уж геморроен)

Момент! Квадратичная - ето в смысле полиномом 2-го степеня? Если да то и мне расскажите как по n точкам (n>3) интерполировать таким полиномом?

Квадратичная проще -!!!
странное утверждение кто сказал по какому критерию в каких случаях

не совершенно необомнованно

а под квадратичной я понял имелось ввиду метод наименьших квадратов

Не ребята. Тут что-то не то. Метод наименших квадратов - ето АППРОКСИМАЦИЯ (т.е. приближение), и он довольно не простой. А интерполяция должна проходить через точки, которые даны в условии. Методы интерполяции есть еще Ньютона вперед и назад, но там формула немного круче. Имхо лучше Лагранжа.

Для построения по заданным точкам вполне подойдет и обычная кусочно-линейная интеполяция, только как ее реализовать я не доезжаю :'(

А для чего надо-то, если не секрет? Просто так проще будет объяснить.

Надо для того чтобы посчитать значение функции в лыбой точке, если даны узловые точки - диплом пишу ;D

Я имел ввиду, графическая или математическая, быстрая или понятная, и т.п.

Кусочно-линейная интерполяция строится просто. На каждом отрезке x(n)...x(n+1) строится линейная функция, проходящая через ети точки.
f(x)=f(x(n))+[f(x(n+1))-f(x(n))]*[x-x(n)]/[x(n+1)-x(n)];
Общая функция является объединением таких.
 Надо выбирать метод в зависимости от нужной точности. Применить формулу оценки.

Молодцы, что с линейной склейкой справились , у меня к вам похожий вопрос. Мне нужно получить сплайн, зная узлы (т.е. пары <x1, y1>, <x2, y2>, ..., принадлежащие сплайну), но не линейный, а, скажем, квадратный (нужна гладкость). Но самое главное: нет порядка среди x1, x2, x3... , т.е. нет так, что x1 < x2 < x3 < ... . То есть говоря ещё иначе — это не функция. Как мне вычислять мою кривую?
Вопрос можно свести к следующему (если кому проще): как, имея пушку с направленным дулом под даным углом, прощитать силу и направление гравитации (ну и скорость выстреленного ядра), чтобы попасть в даную цель?
Пока всё это писал, почти решил.

Вопрос к тебе. У тебя есть набор точек на прлоскости - ты их хочешь соеденить в что-то. Говоришь ето не функция. Через твои точки можно провести бесконечное множество фигур. Интерполяция сплайнами катит для функции, тоесть на каждом отрезке ты интерполируешьполиномом второй степени, с условиями стыковки и гладкости.
 А пример про пушку, насколько я понял и говорит, что нужна именно функция. Или может я не прав?

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

2rodion:
Ето как? Как твоя функция задается? И ето точно интерполяция (може аппроксимация)?

Цитата Sanya, 23.09.02, 11:34:42

Вопрос к тебе. У тебя есть набор точек на прлоскости - ты их хочешь соеденить в что-то. Говоришь ето не функция. Через твои точки можно провести бесконечное множество фигур. Интерполяция сплайнами катит для функции, тоесть на каждом отрезке ты интерполируешьполиномом второй степени, с условиями стыковки и гладкости.
 А пример про пушку, насколько я понял и говорит, что нужна именно функция. Или может я не прав?

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

Цитата rodion, 23.09.02, 12:13:56

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

Если вы будете так добры . Знаешь, чтобы посмотреть и сверить. Ты хочешь их прямо здесь выложить?

2TrivialCore:
  Ну да вообщем. Только такая интерполяция называеться сплайновой :-) (а именно квадратичным сплайном). У тебя есть точки, значения в них. Ты ставишь условие стыковки (f(xi-0)=f(xi+0)) и гладкости (df(xi-0)=df(xi+0)). У тебя получается система уравнений, решая которую на каждом отрезке получаешь полином второй степени. В начальной точке обычно задается df(x0)=0.
  Интерполирует хорошо. Скажу больше: кубичные сплайны интерполируют функцию, что даже глазом не различишь.
  А насчет гравитации - так ето у тебя уже в сторону оптимального управления задача. Она у тебя стоит в такой мат абстракции, или с трактовкой (Пушка не тянет :-))?

Толбко это не будет обычный сплайн, т.к. я уже говорил, это не функция. (некоторым "х" будет отнесено несколько "у" и наоборот). Ладно, объясню, зачем это всё мне надо. Вот сейчас изучаю winapi и решил развлечься, написать следующую программу: по экрану летают шарики . Их 15, летают гладко (по кривым). А теперь мне захотелось их соединить чертой. Сначала соединил отрезками, но это выглядит ужасно (немного а ля один из win screensaver'ов), поэтому мне надо соединить их гладкой чертой, в результате получится что-то наподобие извивающейся змейки. Сам видишь, что о никакой ф-ии речи быть не может. Вот так.

Слушай. А они у тебя летают по бильярдному принципу? Тоесть ты обрабатываешь их столкновения?

данана функция вида f(x, k)
x вектор пременных
k вектор параметров
ичется миниум z(k) = E (f(x_i, k) - y)²
для градиентного метода надо всего лишь знать частные производные f(x, k) по  k_j
все просто исходники выложу

Цитата rodion, 24.09.02, 12:42:03

данана функция вида f(x, k)
x вектор пременных
k вектор параметров
ичется миниум z(k) = E (f(x_i, k) - y)²
для градиентного метода надо всего лишь знать частные производные f(x, k) по  k_j
все просто исходники выложу

О, это звучит заманчиво, только я не въехал, что и что обозначает. Что такое k? какие там параметры. А Е это ожидаемое значение? Вобщем объясни, плиз, поподробнее и исходники покажи, если не трудно . А то я сидел, думал и не придумал, как менять ось координат , а с векторами действительно должно быть проще.

Sanya, шары не сталкиваются, они не знают о существовании друг друга. Влом возиться .

2rodion:
  Я все таки был прав! :-) Ето не интерполяция, а аппроксимация. Только ты забыл что для градиентного методу надо еще и начальное приближение. Произвольное его значение может привести к неверным результатам (локальному минимуму вне допустимой области напр.).
  2TrivialCore: Чего спросил, просто сам когда-то хотел подобное сделать, а ты упомянул про гравитацию. Помоему сталкивание тоже можно так сделать (только будет вектор не гравитации, а силы).

Короче, если хотите посмотреть, как это выглядит, вот бросил сюда програм: http://republika.pl/x_chaos_x/Blockout3.exe (28кВ). Надеюсь, у вас не слишком быстрые компы, а то, кажется, при быстрой графике нихрена не видно (btw скорость действия программы я регулировал Sleep(milliseconds), так правильно?). Левая мышь - шары падают, правая - взлетают.
(Если нужны сорсы, тоже могу бросить, хотя там смотреть особо не на что ).

TrivialCore
Е это знак суммы
Насчет к, объясню на примере полинома p(x) = Exⁱk_i
Кстати чем интерполяция отличается от апроксимации
вот исходники

<br>double *Regres(const double* y, const double* x, double *k, double e, const func *f, int d, int N, int Nk)<br>// d размерность x<br>// dN  размер y<br>// Nk  число параметров<br>{<br>double *ck = new double [Nk];<br>double *yc = new double [N];<br>double ec = 1;<br>e*=e;<br>while (ec > e)<br>{<br>for (int i = 0; i < N; i++) yc[i] = f[0](x + i*d, k, Nk, d);<br>ec = 0;<br>double r = 0;<br>for (int j = 0; j < Nk; j++)<br>  {<br>  double s = 0;<br>  for (int i = 0; i < N; i++)<br>     s+= 2.*(y[i]- yc[i])*f[1 + j](x + i*d, k, Nk, d);<br>  s /= N*N;<br>  ec += s*s;<br>  r += k[j]*k[j];<br>  ck[j] = k[j] + s;<br>  }<br>CopyMemory(k, ck, sizeof(double)*Nk);<br>ec /= r;<br>}<br>delete[] ck, yc;<br>return k;<br>}<br>//---------------------------------------------------------------------------<br>

Вот сижу, стараюсь понять, что к чему, а въехать никак не могу ???.

func *f это указатель на указатель функцию и ее производные
все работает
все таки придется класть полностью, только до оформлю.

   Можно интерполировать параболами.
Т.е. если вначале заданны вершины ломанной и производная в первой вершине, то для каждого отрезка можно построить параболу. А потом по параметру x находить номер отрезка и подставлять в ур-ние параболы для этого отрезка икс.
   Вобщем вот так:
Дано: y[0],y[1],...,y[n], x[0]<x[1]<...<x[n],  y'[0]
Нахождение параболы для i-го отрезка:
   ax[i]x[i] + bx[i] + cx[i] = y[i]
   ax[i+1]x[i+1] + bx[i+1] = y[i+1]
   2ax[i]+b = y'[i]
Система из трех уравнений с тремя неизвестными a,b,c
   Потом для следущего шага найти y'[i+1] = 2ax[i+1]+b
Для каждого отрезка решить такую систему и интерполяция готова

Если взять книжечку по численным методам, то там наверное можно найти истину!!!

Здраствуйте. Помогите пне пожелуйста с таким делом, я уже незнаю что делать .
Мне к примеру нужно вычесть гипотенузу в треугольнику (я это сделал), после с инкрементом 0,001 пройти с нуля до конечного значения гипотенузы (по нажатии кнопки)

Сообщение отредактировано: bezumnyy - 21.04.08, 17:48