2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Кубическая интерполяция
Сообщение29.06.2014, 16:37 


26/06/14
83
Запонадобилась мне простая кубическая интерполяция. Нагуглил случайно исходник интерполяционной программки, которая что-то делает внутри UFRaw, вырезал из неё три вычисляющих функции, всё работает.

Работает так: есть формулы для определения коэффициентов полинома через значения узлов, значения интерполируемой функции в узлах и вторых производных в этих узлах, при чём формулы требуют непрерывность второй производной (коэффициент d при третьей степени привязан к разности вторых производных в соседних узлах).

Перед использованием полинома вызывается spline_cubic_set, в ней вычисляются вторые производные в узлах с использованием предположения о том, что первая производная тоже непрерывна, и потом можно вызывать spline_cubic_val, которая вычисляет значения в точках и производные заодно.

В комментариях к исходникам есть все эти формулы.

Программа: http://pastebin.com/He7VWjhE
Header nikon-curve.h: http://pastebin.com/UX6deTKz (если будут неопределённые символы, качните его).

Компилируется по меньшей мере в VC2010 Express, должно и в других прогах компилироваться.

И теперь вопрос: как так получается, что вторые производные в узлах при требовании к непрерывности первой и второй производной определяются однозначно? Почему это требование оказывается достаточным для точного определения вторых производных?

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

 Профиль  
                  
 
 Re: Кубическая интерполяция
Сообщение29.06.2014, 17:36 
Аватара пользователя


31/10/08
1244
Ваш вопрос звучит не странно.Он очень похож на учебное задание. А на этом форуме халяву не допускают.

Так почему бы вам это не сделать самому? Прочитать про кубический сплайн. Написать недостающие условия. Согласно условиям составить систему уравнений. Записать её в матричном виде. Далее дело технике найти ранг матрицы.

Ответ сможете найти в книге, только чур не подглядывать:

(Оффтоп)

Ф.Хилл OpenGL. Программирование компьютерной графики глава 11.10.3 Естественный сплайн.

 Профиль  
                  
 
 Re: Кубическая интерполяция
Сообщение29.06.2014, 17:40 
Заслуженный участник


11/05/08
32166
Teletranslator в сообщении #881867 писал(а):
Почему это требование оказывается достаточным для точного определения вторых производных?


Teletranslator в сообщении #881867 писал(а):
Перед использованием полинома вызывается spline_cubic_set,

А какие у этой процедуры входные параметры?
Если среди них нет граничных условий, то, скорее всего, минимизируется "энергетический" функционал, что эквивалентно нулевым граничным условиям на вторые производные. Аналогично для периодической аппроксимации.

 Профиль  
                  
 
 Re: Кубическая интерполяция
Сообщение29.06.2014, 17:46 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Там же все написано (в комментарии к ф-и spline_cubic_set).

Мы записываем условие непрерывности в $i$-м узле (если сплайн на $[t_{i},t_{i+1}]$ задается как $y = a_i + b_i(t-t_i) + c_i(t-t_i)^2 + d_i(t - t_i)^3$, то это будет $b_{i-1} + 2c_{i-1}h_{i-1} + 3d_ih_{i-1}^2 = b_i$, где $h_i = t_{i + 1} - t_i$). Потом мы выражаем все коэффициенты через значения $y$ и $y''$ в точках $t_{i-1}, t_i, t_{i+1}$ и получаем систему линейных уравнений, с помощью которых можно выразить $y''$ через $y$ (получается столько уравнений, сколько внутренних узлов, надо добавить еще 2, чтобы как-нибудь задать y'' в начальной и конечной точках).

 Профиль  
                  
 
 Re: Кубическая интерполяция
Сообщение29.06.2014, 17:55 
Заслуженный участник


11/05/08
32166
Xaositect в сообщении #881922 писал(а):
чтобы как-нибудь задать y'' в начальной и конечной точках


Заставили-таки залезть:

Код:
static double *spline_cubic_set(int n, double t[], double y[], int ibcbeg,
                                double ybcbeg, int ibcend, double ybcend)

Действительно, последние две пары -- это граничные условия. Но не обязательно на $y''$: целочисленные параметры -- это, в принципе, порядки производных, задаваемых на границе.

 Профиль  
                  
 
 Re: Кубическая интерполяция
Сообщение29.06.2014, 18:13 


26/06/14
83
Спасибо за ответы.

Pavia в сообщении #881911 писал(а):
Ваш вопрос звучит не странно.Он очень похож на учебное задание. А на этом форуме халяву не допускают.


Я в отпуске и матешу ни за кого не делаю. :mrgreen:

Xaositect в сообщении #881922 писал(а):
Там же все написано (в комментарии к ф-и spline_cubic_set).

Мы записываем условие непрерывности в $i$-м узле (если сплайн на $[t_{i},t_{i+1}]$ задается как $y = a_i + b_i(t-t_i) + c_i(t-t_i)^2 + d_i(t - t_i)^3$, то это будет $b_{i-1} + 2c_{i-1}h_{i-1} + 3d_ih_{i-1}^2 = b_i$, где $h_i = t_{i + 1} - t_i$). Потом мы выражаем все коэффициенты через значения $y$ и $y''$ в точках $t_{i-1}, t_i, t_{i+1}$ и получаем систему линейных уравнений, с помощью которых можно выразить $y''$ через $y$ (получается столько уравнений, сколько внутренних узлов, надо добавить еще 2, чтобы как-нибудь задать y'' в начальной и конечной точках).


Вот это всё я прочитал и осмыслил, всё понял буквально, и после этого ещё неделю мучался и думал, и только после этого написал сюда.


То есть выходит так, что в условиях непрерывности второй производной я не могу влиять на interpolant (как по-русски-то его) интерполянт? Задавать производные в узлах, например. Исписал листок A4, однозначность формул проверил.

>Ф.Хилл OpenGL. Программирование компьютерной графики глава 11.10.3 Естественный сплайн.

Спасибо, гляну.

 Профиль  
                  
 
 Re: Кубическая интерполяция
Сообщение29.06.2014, 18:29 
Заслуженный участник


11/05/08
32166
Teletranslator в сообщении #881938 писал(а):
Задавать производные в узлах

Задавать первые производные "в узлах" (т.е. внутренних) Вы не можете в принципе -- дефект сплайна окажется равным двум, т.е. вторая производная будет рваться. Если, конечно, не случится чуда.

 Профиль  
                  
 
 Re: Кубическая интерполяция
Сообщение29.06.2014, 18:34 


26/06/14
83
То бишь: для того, чтобы к данной программе прикрутить монотонность, условие непрерывности второй производной нужно убрать, верно?

 Профиль  
                  
 
 Re: Кубическая интерполяция
Сообщение08.05.2015, 13:10 


26/06/14
83
Ещё вопрос. Правильно ли то, что интерполянт зависит от положения узлов?

Наверное, плохая формулировка, надо точнее: если я вычисляю интерполянт, а потом перемещаю один из узлов узел в другую точку этого интерполянта (новые координаты принадлежат интерполянту) и строю второй интерполянт, он будет совпадать с первым?

 Профиль  
                  
 
 Re: Кубическая интерполяция
Сообщение08.05.2015, 15:24 


26/06/14
83
Вопрос наивным оказался. Разумеется, зависит.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group