Кубическая интерполяция

[Teletranslator]

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

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

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

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

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

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

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

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

[Pavia]

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

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

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

(Оффтоп)

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

[ewert]

Teletranslator в сообщении #881867 писал(а):

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

Teletranslator в сообщении #881867 писал(а):

Перед использованием полинома вызывается spline_cubic_set,

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

[Xaositect]

Там же все написано (в комментарии к ф-и 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'' в начальной и конечной точках).

[ewert]

Xaositect в сообщении #881922 писал(а):

чтобы как-нибудь задать y'' в начальной и конечной точках

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

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

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

[Teletranslator]

Спасибо за ответы.

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

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

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

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 Естественный сплайн.

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

[ewert]

Teletranslator в сообщении #881938 писал(а):

Задавать производные в узлах

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

[Teletranslator]

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

[Teletranslator]

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

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

[Teletranslator]

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