Интерполяционные сплайны

[Ivan.]

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

[Dmitriy40]

Интерполяция применяется чаще в моделировании физических процессов, а там часто важна неразрывность не только самой функции, но и её производной. Кубический сплайн позволяет плавно сшить и производную тоже. Наверное потому и применяется.

[Ivan.]

Я считал, что и квадратичный позволяет сшить производную, по крайней мере первую. Пример построения квадратичного сплайна нашел в книге Вержбицкий В.М. Основы численных методов, однако явных преимуществ кубического сплайна над квадратичным не вижу.

[GAA]

У кубического сплайна непрерывны первая и вторая производные. (Это зависит конечно от доп. оговорок, но часто используются кубические сплайны именно с непрерывной второй производной.)
Во многих учебниках по численным методам это есть. См., например, Самарский А.А., Гулин А.В. Численные методы, гл. 3, §4 (Интерполирование сплайнами). Там коэффициенты получаются из условия (в том числе) непрерывности второй производной.

-- Вс 17.09.2017 19:14:02 --

+ естественные граничные условия $f’’(a)=f’’(b)=0$.

Upd. Посмотрел Вержбицкого. (Он даже во многом подробнее Гулина.) Как бы ответ на вопрос исходного сообщения там есть. Даже что-то о связи с экстремальными задачами.

[ewert]

Ivan. в сообщении #1248494 писал(а):

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

Не только. Любая сплайн-интерполяция неоднозначна, и для получения единственного решения требуется ставить дополнительные требования. Естественнее всего добавлять какие-то граничные условия. Так вот: если рассматривать сплайны с наименьшим дефектом (т.е. наивысшей гладкости из возможных), то не хватает $(m-1)$ требования, где $m$ -- степень сплайна.

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

GAA в сообщении #1248509 писал(а):

+ естественные граничные условия $f’’(a)=f’’(b)=0$.

Это ещё как сказать насчёт естественности. Это только если линейку гвоздиками зажимать (оставляя концы свободными), да и то лишь в малом. Но на практике никто линейку сплайнами не аппроксимирует. На практике аппроксимируют функции. И тогда эти замечательные условия -- да, "энергетически" экстремальны, однако сбивают точность аппроксимации на два порядка из четырёх возможных, увы.

[Pphantom]

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

Это ещё как сказать насчёт естественности.

Но тем не менее кубический сплайн, удовлетворяющий этим условиям, называется "естественным". Возможно, GAA именно это и имел в виду.

[GAA]

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

Это ещё как сказать насчёт естественности.

Это такой термин, принятый в буржуйских околокомпьютерных науках.
[В задачах для уравнений в частных производных равенство нулю потока называется естественным граничным условием. На всякий случай. Мне самому это непривычно ещё пару лет назад было, и развивать вопрос о корявости этой терминологии мне кажется пустым делом.
К слову, у Вержбицкого кубический сплайн, построенный при соответствующих условиях, называется естественным. Остальные книжки мне лень сейчас просматривать, а последний раз я их открывал лет 10 назад.]

[Только три раза в работе приходилось использовать сплайны. И ни разу не пришлось использовать «естественные» граничные условия.]

[ewert]

(Оффтоп)

GAA в сообщении #1248533 писал(а):

Это такой термин, принятый в буржуйских околокомпьютерных науках.

Не только в буржуйских. У нас тоже. Я только к тому, что он способен ввести в заблуждение.

А так -- да, он "естественен" в том смысле, что отвечает некоторой простой физической интерпретации.

GAA в сообщении #1248533 писал(а):

В задачах для уравнений в частных производных равенство нулю потока называется естественным граничным условием.

Ни разу не слыхал. Ни разу и ни от кого не слыхал, чтоб условия Неймана считались естественнее, чем условия Дирихле.

[GAA]

(ewert)

Так называемые «естественные» граничные условия возникают в задачах вариационного исчисления. Метод конечных элементов, используемый при решении НУЧП, опирается на вариационное исчисление.
Найти термин “natural boundary condition” можно например в FlexPDE. Быстренько нагуглил: The NATURAL boundary condition statement in FlexPDE supplies the value of the surface flux, as that flux is defined by the integration of the PDE by parts.
И поскольку равно нулю можно в описании проекта в некоторых пакетах не писать, то натуральное без уточнения --- это поток равен нулю.

-- Вс 17.09.2017 23:38:39 --

Ну, вот из этих двух посылок и естественные граничные условия. Хотя, в конечном счете, все к вариационке сводится. :)

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

И тогда эти замечательные условия -- да, "энергетически" экстремальны, однако сбивают точность аппроксимации на два порядка из четырёх возможных, увы.

Если в задаче заданы граничные условия $f’’(a)=C_1$, $f’’(b)=C_2$ (в частности $f’’(a)=0$, $f’’(b)=0$), так их и используем. И «сбивания» точности не будет. Если в задаче заданы $f’(a)=C_1$, $f’(b)=C_2$, значит, нужно эти использовать. И опять получим четвёртый порядок. Это же в учебниках есть. Даже у Волкова в «Численных методах».

[Ivan.]

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

Не только. Любая сплайн-интерполяция неоднозначна, и для получения единственного решения требуется ставить дополнительные требования. Естественнее всего добавлять какие-то граничные условия. Так вот: если рассматривать сплайны с наименьшим дефектом (т.е. наивысшей гладкости из возможных), то не хватает $(m-1)$ требования, где $m$ -- степень сплайна.

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

У Вержбицкого строится квадратичный сплайн дефекта 1, при этом получается $(3n+1)$ уравнений и $(3n+3)$ неизвестных коэффициентов, то есть так же возможно распределить граничные условия равномерно. Кроме того, в процессе построения квадратичного сплайна выявляется лучшая численная устойчивость процедуры нахождения коэффициентов по сравнению с кубическим сплайном.

GAA в сообщении #1248509 писал(а):

У кубического сплайна непрерывны первая и вторая производные. (Это зависит конечно от доп. оговорок, но часто используются кубические сплайны именно с непрерывной второй производной.)
Во многих учебниках по численным методам это есть. См., например, Самарский А.А., Гулин А.В. Численные методы, гл. 3, §4 (Интерполирование сплайнами). Там коэффициенты получаются из условия (в том числе) непрерывности второй производной.

-- Вс 17.09.2017 19:14:02 --

естественные граничные условия $f’’(a)=f’’(b)=0$.

Upd. Посмотрел Вержбицкого. (Он даже во многом подробнее Гулина.) Как бы ответ на вопрос исходного сообщения там есть. Даже что-то о связи с экстремальными задачами.

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

[ewert]

Ivan. в сообщении #1248575 писал(а):

У Вержбицкого строится квадратичный сплайн дефекта 1, при этом получается $(3n+1)$ уравнений и $(3n+3)$ неизвестных коэффициентов

Это невозможно никак. Во-первых, если $n$ -- количество отрезков, то количество неизвестных равно $3n$ (а если иметь в виду количество узлов, то выйдет ещё меньше, но это неестественно, так что не будем). Во-вторых, при этом получится $2n$ условий интерполяции (по два на каждый отрезок) плюс $(n-1)$ условий гладкости (по одному на каждый внутренний узел), итого $(3n-1)$ уравнений. Т.е. не хватает ровно одного уравнения, так что ставить в качестве его граничное условие -- непонятно, зачем.

(Оффтоп)

GAA в сообщении #1248547 писал(а):

Если в задаче заданы граничные условия $f’’(a)=C_1$, $f’’(b)=C_2$ (в частности $f’’(a)=0$, $f’’(b)=0$), так их и используем. И «сбивания» точности не будет. Если в задаче заданы $f’(a)=C_1$, $f’(b)=C_2$, значит, нужно эти использовать. И опять получим четвёртый порядок.

Конечно, если в задаче изначально были именно эти условия, то останется четвёртый в любом случае. Только вот поток -- это первая производная, отнюдь не вторая. Вторая -- это кривизна. А если речь шла просто об аппроксимации какой-то функции, то нет никаких оснований что-то на концах обнулять; фиксировать же гораздо естественнее первые производные, а не вторые.

[GAA]

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

Ivan. в сообщении #1248575 писал(а):

У Вержбицкого строится квадратичный сплайн дефекта 1, при этом получается $(3n+1)$ уравнений и $(3n+3)$ неизвестных коэффициентов

Это невозможно никак.

Вержбицкий вслед за Стечкиным и Субботиным «Сплайны в вычислительной математике», 1976, рассматривает разные определения (полиномиального) интерполяционного сплайна для четных и нечетных порядков. В общем случае узлы сплайна и узлы интерполяции не обязаны совпадать. Если точки интерполяции совпадают с узлами сплайна, то при четном порядке число оставшихся свободных параметров нечетно, одному из концов приходится отдавать предпочтение, а это может приводить к неустойчивому вычислению параметров сплайна. (Во второй главе книги Стечкина и Субботина приводится пример.) Поэтому точки интерполяции при четных степенях выбирают отличными от узлов сплайна.
Точнее Вержбицкий рассматривает случай внутренних узлов сплайна $\tilde x = \frac 1 2 (x_{k-1} + x_k)$ и крайних узлов сплайна $\tilde x_0 = a (=x_0)$, $\tilde x_{n=1} = b (=x_n)$, где $x_i$, $i=1,\ldots, n$ узлы интерполяции.

Итого: $n+1$ звеньев, $3(n+1)$ параметров, $n+1$ условий интерполяции, $2n$ условий непрерывности = 2 связи свободные.

-- Пн 18.09.2017 20:00:17 --

Ivan., отвечу, как только найду время. Если раньше за меня не ответят.

[GAA]

Ivan. в сообщении #1248575 писал(а):

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

Я за популярность сказать не возьмусь. Вот что для меня (в разных случаях) было важно
1. Непрерывность второй производной. (Уже выше было сказано.)
2. Постоянный шаг (постоянное расстояние между узлами).
3. Более высокий порядок аппроксимации на хороших функциях. [Если использовать сплайн в цикле, то хорошо бы, чтобы он не ел много памяти.]

На оффтопик. Типичные краевые условия для третьего порядка — это условия на производные или вторые производные. (Еще есть задача построения периодического сплайна, и другие, но пока замнём для ясности.) Задание первой производной отдалённо аналогично заданию условия на функцию, т.е. аналог первой краевой задачи для ОДУ 2-го порядка. Задание вторых производных — отдаленная аналогия второй краевой задачи. Отсюда и поток. Но это все словеса бессодержательные. Техника удовлетворения условиям немного другая. Хотя прогонка вызывается в любом случае. Вот подпрограммы для задания уравнений прогонки по аналогии с краевыми задачами для ОДУ как-то так иногда и называют: первого рода и второго рода. В общем, это все пустое.

Про естественность фиксации первых производных не понял. Если задача в интерполяции и рассчитать можно как первую, так и вторую производные, то «естественно» выбрать то, что рассчитать проще (особенно, если рассчитывать сложно). Хотя порядок аппроксимации хоть при использовании первой, хоть при использовании второй производной будет четвертый, при использовании первой производной вроде бы точность выше. Также вроде бы есть приемы улучшения точности при задании второй производной. (Детали не помню.) Но это не о порядке аппроксимации; это о величинах коэффициентов идет речь. В общем, что стоит за падением на 2 порядка догадаться я не смог.

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

И тогда эти замечательные условия -- да, "энергетически" экстремальны, однако сбивают точность аппроксимации на два порядка из четырёх возможных, увы.

[ewert]

GAA в сообщении #1248817 писал(а):

Вот что для меня (в разных случаях) было важно
1. Непрерывность второй производной. (Уже выше было сказано.)
2. Постоянный шаг (постоянное расстояние между узлами).
3. Более высокий порядок аппроксимации на хороших функциях.

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

GAA в сообщении #1248817 писал(а):

В общем, что стоит за падением на 2 порядка догадаться я не смог.

Стоит банальность. Если это граничное условие самой постановкой задачи не предполагается, а речь просто об аппроксимации некоей функции, то искусственное обнуление вторых производных на концах какую-то аппроксимацию, конечно, даст. Но -- лишь второго порядка точности, а не (максимально возможного) четвёртого.

[GAA]

1. В разных задачах по-разному бывает. Грубо говоря, сплайн заталкивался в модель, где была нужна не сама функция, а её производная, и желательно, чтобы она была непрерывно дифференцируемой. Вот и непрерывность второй производной для сплайна.
2. Я же написал, что это лично мне было нужно. [И ещё. Для квадратичных сплайнов чуть сложнее программа. Больше кода — больше вытеснения из кэша. Сам же сплайн в какую-то программу засовывается. ]
3. Если точность не нужна, то это хорошо.

Про обнуление наконец понял. Я думал там что-то тонкое. И не мог сообразить. Спасибо.