Интерполяция квадратичным сплайном.

[M<ath]

Даже не знаю, в нужный ли раздел пишу. Нужен алгоритм, чтоб реализовать это в программе.
Есть программа, строит интерполяцию квадратичным сплайном:

float A[14], B[14], C[14], X[15], Y[15], H[14];   /*заполнены X и Y, A, B, C, H - коэффициенты,
необходимые для построения интерполяционного полинома */

     for(j=0; j<14; j++)   {
     H[j]=X[j+1]-X[j];
     }

     for(j=1; j<=14; j++)  {
     if(H[j]!=0)
     B[j]=2*(Y[j]-Y[j-1])/H[j-1]-B[j-1];
     else break;
     }

     for(j=0; j<=14; j++)
     A[j]=Y[j];

      for(j=0; j<=13; j++)  {
      C[j]=(Y[j+1]-Y[j])/pow(H[j],2)-B[j]/H[j];
      }


   float S[15];
   S[0]=A[0];

   for(i=0; i<=14; i++)  {
   S[i+1]=A[i]+H[i]*B[i]+pow(H[i],2)*C[i];   /* это как раз тот полином,
который нужно построить */
   }   

Получившийся график выглядит так: http://clip2net.com/s/5RCto2. Все значения тут же.
Проблема заключается в том, что график нужно сделать плавным. Полагаю, для этого нужно просто больше точек, т е не 15 X и Y, а, к примеру, 50. Что с иксами делать понятно, заданы начальное и конечное значения, в пределах этого отрезка изменить шаг и сделать из 15 значений - 50 с меньшим шагом. Заменяю все массивы динамическими, вычисляю 50 эл-тов X, но что делать с сооответствующими им значениями по Y? Как узнать, где будут значения Y в этих новых иксах?

[Pavia]

Что-бы получить алгоритм нужно задачу чётко описать.

Цитата:

/*заполнены X и Y, A, B, C, H - коэффициенты,

Вот это что такое?
Какой тип сплайна? Какие параметры у сплайна? Какую интерполяцию используете?

M<ath в сообщении #769734 писал(а):

Что с иксами делать понятно, заданы начальное и конечное значения, в пределах этого отрезка изменить шаг и сделать из 15 значений - 50 с меньшим шагом. Заменяю все массивы динамическими, вычисляю 50 эл-тов X, но что делать с сооответствующими им значениями по Y? Как узнать, где будут значения Y в этих новых иксах?

Подставляй в сплайн параметр Х получаешь соответствующий Y.

[M<ath]

Так ведь квадратичным сплайном.
Как я могу просто взять и подставить 50 иксов в сплайн, когда коэффициентов у меня - 14?
Т е там 14 функций S. В общем, такой вопрос тогда: может, что-то не так с самой интерполяцией у меня? Потому как здесь ф-ия зависит и от x, и от y. Может, должно быть иначе? Но я где только можно смотрел алгоритмы интерполяции, по идее, должно быть всё верно.

[Yuri Gendelman]

M<ath в сообщении #769734 писал(а):

Проблема заключается в том, что график нужно сделать плавным. Полагаю, для этого нужно просто больше точек, т е не 15 X и Y, а, к примеру, 50.

1.
То, что изображено на Вашем графике, больше всего похоже на кусочно-линейную интерполяцию по 15 точкам.
Для ее построения Вам нужно определить 14 линейных функций, т.е. 28 параметров. Для каждой функции у Вас есть 2 уравнения на концах соответствубщего интервала, т.е. всего 28 уравнений. Все просто.
В какой-то степени кусочно-линейная интерполяция - это "линейный сплайн" или сплайн типа (1,1): функции 1-го порядка с дефектом 1 (т.е. равенством 0-х производных - непрерывность) в точках сшивки.

2.
Чтобы получить гладкую кривую, Вам нужен сплайн как минимум типа (2,1): функции 2-го порядка с условием 1-го порядка в точках сшивки (непрерывность + гладкость - равенство 1-х производных).
Ваши 14 квадратичных функций определяются 42 параметрами. А уравнений у Вас - 28 на значения каждой функции +13 - на равенство 1-х производных в точках сшивки. Всего - 41 уравнение. Нужно дополнительное условие на одной из границ.

3.
Стандартными считаются кубические сплайны типа (3,1): функции 3-го порядка с условием 2-го порядка в точках сшивки (непрерывность + равенство 1-х и 2-х производных).
14 кубических функций определяются 56 параметрами. А уравнений у Вас - 28 на значения каждой функции +26 - на равенство 1-х и 2-х производных в точках сшивки. Всего - 54 уравнение. Нужны еше 2 дополнительных условия на границах.
Если нет других соображений, приравнивают к нулю 2-е производные в краевых точках (типа "хода нет - ходи с бубей").

[Pavia]

M<ath
Ваш код не похож на сплайн и на интерполяцию. Поэтому я и просил уточнить, а что же такое считается в вашей программе.

Я сплайны изучал по этой книге:
Ф.Хилл OpenGL. Программирование компьютерной графики глава 11.
В интернете достаточно материала.

Сплайн это кусочный полином. Где на каждом куске определён полином.
Квадратичный сплайн это значит, что члены полинома не превышают 2 степень.

Существует несколько определений и подходов к получения полиномов.
Вот для каждого участка у тебя определен полином путём задания коэффициентов или стыковочной функции/функций.
1) $S(t)=\Sigma^{L-1}_{k=0}(A_{k}(t)+B_{k}(t)*t+C_{k}(t)*t^2)$

2) $S(t)=\Sigma^{L-1}_{k=0}P_{k}*R_{k}(t)$
В первом случае у тебя коэффициенты зависят от параметра, во втором функции.
Вот в качестве параметра t и используешь новые значения X.

Yuri Gendelman
Только не стандартный, а сплайн Эрмита и его разновидность естественный сплайн.
Стандартный это скорее B-сплайн.

[Yuri Gendelman]

Pavia в сообщении #770353 писал(а):

Только не стандартный, а сплайн Эрмита и его разновидность естественный сплайн. Стандартный это скорее B-сплайн.

Я, называя стандартными кубические сплайны, имел в виду исключительно их степень. Можно назвать их наиболее употребительными.
Упомянул я это потому, что ТС собрался строить квадратичные сплайны.

[ewert]

Yuri Gendelman в сообщении #770339 писал(а):

Всего - 41 уравнение. Нужно дополнительное условие на одной из границ.

Куда так много-то? Достаточно 13 уравнений на 14 вторых производных $a_i$:

$$\frac12(a_ih_i+a_{i+1}h_{i+1})=v_{i+1}-v_i,$$

где $h_i=x_i-x_{i-1}$ -- шаги между узлами и $v_i=\frac{y_i-y_{i-1}}{h_i}$ -- средние наклоны. А вот добавлять условие именно граничное -- крайне нехорошо, ибо несимметрично. Лучше минимизировать, например, квадратичную норму второй производной, т.е. $\sum a_i^2h_i$. Для этого к той системе надо добавить условие ортогональности (с весами $h_i$) любому решению однородной системы $\tilde a_ih_i+\tilde a_{i+1}h_{i+1}=0.$ Поскольку система двухдиагональна, это решение выписывается мгновенно (а в случае равноотстоящих узлов и попросту $\tilde a_i=(-1)^i$). Или можно аналогичным образом минимизировать квадратичную норму первой производной, т.е. $\sum a_i^2h_i^4$.

[_Ivana]

Как обычно, ТС пропал, а участники развивают тему по собственному усмотрению. Я бы вообще локальные сплайны предложил, во всем их разнообразии Количество уравнений уменьшается до 3 (трех).

[Yuri Gendelman]

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

Yuri Gendelman в сообщении #770339 писал(а):

Всего - 41 уравнение. Нужно дополнительное условие на одной из границ.

Куда так много-то? Достаточно 13 уравнений на 14 вторых производных ...

Строим квадратичные сплайны.
Даны 15 точек, т.е. нужно построить 14 квадратичных функций == определить 42 параметра.
Есть 28 уравнений, по 2 на интервал, для привязки к известным 15 точкам и 13 уравнений на равенство 1-х производных на внутренних границах интервалов.
Всего - 41 уравнение.
Что тут не так?

[ewert]

Yuri Gendelman в сообщении #770640 писал(а):

Что тут не так?

То, что сплайн -- интерполяционный. И считать для него уравнениями условия интерполяции -- как-то совсем не совсем. Это просто исходные данные.

Я же не спорю, что формально их 41. Просто это практически вредная формальность.