А квадратичная - проще, быстрей, и при правильном использовании выглядит красиво. ;) | Версия для печати
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум на Исходниках.RU > Алгоритмы > Интерполяция |
| Автор: codex 11.09.02, 06:16 |
| Помогие начинающему! Подскажите как реализовать метод интеполяции на С++, если даны, например, ключевые точки? :-[ |
| Автор: Alch 11.09.02, 07:49 |
| А какой? Их до чёрта. Линейная, квадратичная и прочая полиномиальная и т.д. |
| Автор: Sanya 11.09.02, 12:58 |
| Держи простейшую. 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 порядка. |
| Автор: Alch 12.09.02, 06:49 |
| Интерполяция полиномом Лагранжа простейшая???!?!!?!?!?! А квадратичная - проще, быстрей, и при правильном использовании выглядит красиво. ;) |
| Автор: codex 12.09.02, 10:45 |
Если не влом покажи как делать квадратичную(Лагранж конечно рулит, но очень уж геморроен)  |
| Автор: Sanya 12.09.02, 11:20 |
| Момент! Квадратичная - ето в смысле полиномом 2-го степеня? Если да то и мне расскажите как по n точкам (n>3) интерполировать таким полиномом? |
| Автор: esperanto 12.09.02, 11:34 |
| Квадратичная проще -!!! странное утверждение кто сказал по какому критерию в каких случаях не совершенно необомнованно а под квадратичной я понял имелось ввиду метод наименьших квадратов |
| Автор: Sanya 12.09.02, 11:49 |
| Не ребята. Тут что-то не то. Метод наименших квадратов - ето АППРОКСИМАЦИЯ (т.е. приближение), и он довольно не простой. А интерполяция должна проходить через точки, которые даны в условии. Методы интерполяции есть еще Ньютона вперед и назад, но там формула немного круче. Имхо лучше Лагранжа. |
| Автор: codex 12.09.02, 11:53 |
| Для построения по заданным точкам вполне подойдет и обычная кусочно-линейная интеполяция, только как ее реализовать я не доезжаю :'( |
| Автор: Alch 12.09.02, 12:12 |
| А для чего надо-то, если не секрет? Просто так проще будет объяснить. |
| Автор: codex 12.09.02, 12:20 |
| Надо для того чтобы посчитать значение функции в лыбой точке, если даны узловые точки - диплом пишу ;D |
| Автор: Alch 12.09.02, 12:35 |
| Я имел ввиду, графическая или математическая, быстрая или понятная, и т.п. |
| Автор: Sanya 12.09.02, 12:53 |
| Кусочно-линейная интерполяция строится просто. На каждом отрезке 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)]; Общая функция является объединением таких. Надо выбирать метод в зависимости от нужной точности. Применить формулу оценки. |
| Автор: Машина 22.09.02, 20:23 |
Молодцы, что с линейной склейкой справились  , у меня к вам похожий вопрос. Мне нужно получить сплайн, зная узлы (т.е. пары <x1, y1>, <x2, y2>, ..., принадлежащие сплайну), но не линейный, а, скажем, квадратный (нужна гладкость). Но самое главное: нет порядка среди x1, x2, x3... , т.е. нет так, что x1 < x2 < x3 < ... . То есть говоря ещё иначе — это не функция. Как мне вычислять мою кривую?Вопрос можно свести к следующему (если кому проще): как, имея пушку с направленным дулом под даным углом, прощитать силу и направление гравитации (ну и скорость выстреленного ядра), чтобы попасть в даную цель? Пока всё это писал, почти решил.  |
| Автор: Sanya 23.09.02, 07:34 |
| Вопрос к тебе. У тебя есть набор точек на прлоскости - ты их хочешь соеденить в что-то. Говоришь ето не функция. Через твои точки можно провести бесконечное множество фигур. Интерполяция сплайнами катит для функции, тоесть на каждом отрезке ты интерполируешьполиномом второй степени, с условиями стыковки и гладкости. А пример про пушку, насколько я понял и говорит, что нужна именно функция. Или может я не прав? |
| Автор: rodion 23.09.02, 08:13 |
| Я сделал интерполяцию произвольной фунцкцией, если надо могу выложить исходники |
| Автор: Sanya 23.09.02, 08:23 |
| 2rodion: Ето как? Как твоя функция задается? И ето точно интерполяция (може аппроксимация)? |
| Автор: Машина 23.09.02, 09:34 |
| Цитата Sanya, 23.09.02, 11:34:42 Вопрос к тебе. У тебя есть набор точек на прлоскости - ты их хочешь соеденить в что-то. Говоришь ето не функция. Через твои точки можно провести бесконечное множество фигур. Интерполяция сплайнами катит для функции, тоесть на каждом отрезке ты интерполируешьполиномом второй степени, с условиями стыковки и гладкости. А пример про пушку, насколько я понял и говорит, что нужна именно функция. Или может я не прав? Да, очень прав. Ты заметил, что я говорил про гравитацию? Идея в том, чтобы для каждых двух узлов принимать свою ось координат, чтобы иметь функцию. И тогда: для начального узла я принимаю почти любое направление, лечу квадратным полиномом в следующий узел и т.д. Т.е. на каждом шагу принимать, что имеем интерполяцию (уже не сплайновую) параболой при заданых концах и заданом первом дифференциале в первом узле. Верно? |
| Автор: Машина 23.09.02, 09:37 |
| Цитата rodion, 23.09.02, 12:13:56 Я сделал интерполяцию произвольной фунцкцией, если надо могу выложить исходники Если вы будете так добры . Знаешь, чтобы посмотреть и сверить. Ты хочешь их прямо здесь выложить? |
| Автор: Sanya 23.09.02, 11:17 |
| 2TrivialCore: Ну да вообщем. Только такая интерполяция называеться сплайновой :-) (а именно квадратичным сплайном). У тебя есть точки, значения в них. Ты ставишь условие стыковки (f(xi-0)=f(xi+0)) и гладкости (df(xi-0)=df(xi+0)). У тебя получается система уравнений, решая которую на каждом отрезке получаешь полином второй степени. В начальной точке обычно задается df(x0)=0. Интерполирует хорошо. Скажу больше: кубичные сплайны интерполируют функцию, что даже глазом не различишь. А насчет гравитации - так ето у тебя уже в сторону оптимального управления задача. Она у тебя стоит в такой мат абстракции, или с трактовкой (Пушка не тянет :-))? |
| Автор: Машина 23.09.02, 12:12 |
| Толбко это не будет обычный сплайн, т.к. я уже говорил, это не функция. (некоторым "х" будет отнесено несколько "у" и наоборот). Ладно, объясню, зачем это всё мне надо. Вот сейчас изучаю winapi и решил развлечься, написать следующую программу: по экрану летают шарики . Их 15, летают гладко (по кривым). А теперь мне захотелось их соединить чертой. Сначала соединил отрезками, но это выглядит ужасно (немного а ля один из win screensaver'ов), поэтому мне надо соединить их гладкой чертой, в результате получится что-то наподобие извивающейся змейки. Сам видишь, что о никакой ф-ии речи быть не может. Вот так. |
| Автор: Sanya 24.09.02, 07:59 |
| Слушай. А они у тебя летают по бильярдному принципу? Тоесть ты обрабатываешь их столкновения? |
| Автор: rodion 24.09.02, 08:42 |
| данана функция вида f(x, k) x вектор пременных k вектор параметров ичется миниум z(k) = E (f(xi, k) - y)2 для градиентного метода надо всего лишь знать частные производные f(x, k) по kj все просто исходники выложу |
| Автор: Машина 24.09.02, 12:32 |
| Цитата rodion, 24.09.02, 12:42:03 данана функция вида f(x, k) x вектор пременных k вектор параметров ичется миниум z(k) = E (f(xi, k) - y)2 для градиентного метода надо всего лишь знать частные производные f(x, k) по kj все просто исходники выложу О, это звучит заманчиво, только я не въехал, что и что обозначает. Что такое k? какие там параметры. А Е это ожидаемое значение? Вобщем объясни, плиз, поподробнее и исходники покажи, если не трудно . А то я сидел, думал и не придумал, как менять ось координат  , а с векторами действительно должно быть проще.Sanya, шары не сталкиваются, они не знают о существовании друг друга. Влом возиться . |
| Автор: Sanya 24.09.02, 13:06 |
| 2rodion: Я все таки был прав! :-) Ето не интерполяция, а аппроксимация. Только ты забыл что для градиентного методу надо еще и начальное приближение. Произвольное его значение может привести к неверным результатам (локальному минимуму вне допустимой области напр.). 2TrivialCore: Чего спросил, просто сам когда-то хотел подобное сделать, а ты упомянул про гравитацию. Помоему сталкивание тоже можно так сделать (только будет вектор не гравитации, а силы). |
| Автор: Машина 24.09.02, 13:25 |
| Короче, если хотите посмотреть, как это выглядит, вот бросил сюда програм: http://republika.pl/x_chaos_x/Blockout3.exe (28кВ). Надеюсь, у вас не слишком быстрые компы, а то, кажется, при быстрой графике нихрена не видно (btw скорость действия программы я регулировал Sleep(milliseconds), так правильно?). Левая мышь - шары падают, правая - взлетают. (Если нужны сорсы, тоже могу бросить, хотя там смотреть особо не на что ). |
| Автор: rodion 25.09.02, 08:35 |
| TrivialCore Е это знак суммы Насчет к, объясню на примере полинома p(x) = Exiki Кстати чем интерполяция отличается от апроксимации вот исходники <{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}> <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> |
| Автор: Машина 28.09.02, 13:08 |
Вот сижу, стараюсь понять, что к чему, а въехать никак не могу  ???. |
| Автор: rodion 30.09.02, 08:46 |
| func *f это указатель на указатель функцию и ее производные все работает все таки придется класть полностью, только до оформлю. |
| Автор: Leprecon 07.10.02, 23:42 |
| Можно интерполировать параболами. Т.е. если вначале заданны вершины ломанной и производная в первой вершине, то для каждого отрезка можно построить параболу. А потом по параметру 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 Для каждого отрезка решить такую систему и интерполяция готова |
| Автор: Psycho 20.05.04, 07:27 |
| Если взять книжечку по численным методам, то там наверное можно найти истину!!! |
| Автор: bezumnyy 21.04.08, 17:46 |
Здраствуйте. Помогите пне пожелуйста с таким делом, я уже незнаю что делать  .Мне к примеру нужно вычесть гипотенузу в треугольнику (я это сделал), после с инкрементом 0,001 пройти с нуля до конечного значения гипотенузы (по нажатии кнопки) |