Кубический интерполяционный сплайн. Теоретические основы сплайн-интерполяции или почему IQ тесты не имеют решения

Это функция, которая:

Проходит через все заданные точки
,
;

На каждом отрезке между соседними точками является кубической параболой;

Непрерывна вместе со своими первой и второй производными во всех точках.).

интерполяция
локальная			глобальная
линейная	параболическая	кубическая парабола	полином степени (N -1)	кубический сплайн
Рис. 1.5.

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

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

Если функция измеряется или вычисляется приближенно и погрешности существенны, то не имеет смысла проводить интерполяцию и переходят к аппроксимации. В латыни слово ap-proximo означает "почти близкий". При аппроксимации кривая проводится вблизи заданных точек в соответствии с некоторым критерием близости, например, критерием наименьших квадратов или минимаксным критерием. Различия интерполяции и аппроксимации иллюстрирует рис.1.6.

Если имеем непрерывную или дискретную функцию, то обычно используют 5 видов преобразований функций:

Непрерывная в дискретную (дискретизация),

Дискретная в непрерывную (интерполяция),

Дискретная в непрерывную (аппроксимация),

Непрерывная в непрерывную (интерполяция),

Дискретная в дискретную (сглаживание).

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

Кубический сплайн.
Кубические сплайны для интерполяции предложил использовать Шенберг в 1949 г. Слово "сплайн" происходит от названия длинных тонких металлических реек, которые с давних времен немецкие чертежники крепили гвоздиками на кульмане вместо лекал для проведения сложных кривых.

Кубический сплайн - это функция, которая:

Проходит через все заданные точек
,
;

На каждом отрезке между соседними точками является кубическим полиномом;

Непрерывна вместе со своими первой и второй производными во всех точках.

Заметим, что, благодаря третьему условию, кубическая парабола
через две точки проводится однозначно.

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

Причем между заданными точками имеем отрезок, так что в этой формуле
.

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

, , ,

(2.2)

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

Постановка задачи: даны точек , . Определить все коэффициенты сплайна , , , т.е. всего
коэффициентов,
, т.к. отрезок.

Рассмотрим два любых соседних отрезка
и
с номерами
и . Точка для них является общей, см. рис. 2.1.

Для правого отрезка кубический сплайн имеет вид (2.1), а для левого, т.е. при

В общей точке
приравняем левые и правые значения
и производных
и
в соответствии с определением кубического сплайна. Используя обозначение
для длины левого отрезка, получаем три уравнения для пяти неизвестных коэффициентов
,
,
, , .

Такие тройки уравнений можно записать для всех внутренних узлов ,
, что даёт
уравнений.

Эти дополнительные два уравнения могут быть произвольными, но обычно полагают, что функция
вблизи её концов является линейной. Тогда, имеем из последнего и первого уравнений (2.4) и уравнения (2.5):

Часто систему уравнений (2.8) записывают для вторых производных в узлах, обозначая их
. Тогда она принимает вид (Бахвалов, Численные методы, М., 2002):

Кривые и поверхности, встречающиеся в практических задачах, часто имеют довольно сложную форму, не допускающую универсального аналитического задания в целом при помощи элементарных функций. Поэтому их собирают из сравнительно простых гладких фрагментов - отрезков (кривых) или вырезков (поверхностей), каждый из которых может быть вполне удовлетворительно описан при помощи элементарных функций одной или двух переменных. При этом вполне естественно потребовать, чтобы гладкие функции, которые используются для построения частичных кривых или поверхностей, имели схожую природу, например, были бы многочленами одинаковой степени. А чтобы получающаяся в результате кривая или поверхность оказалась достаточно гладкой, необходимо быть особенно внимательным в местах стыковки соответствующих фрагментов. Степень многочленов выбирается из простых геометрических соображений и, как правило, невелика. Для гладкого изменения касательной вдоль всей составной кривой достаточно описывать стыкуемые кривые при помощи много-членов третьей степени, кубических многочленов. Коэффициенты таких многочленов всегда можно подобратьтак, чтобы кривизна соответствующей составной кривой была непрерывной. Кубические сплайны, возникающие при решении одномерных задач, можно приспособить к посгрое нию фрагментов составных поверхностей. И здесь вполне естественно появляются бикубические сплайны, описываемые при помощи многочленов третьей степени по каждой из двух переменных. Работа с такими сплайнами требует уже значительно большего объема вычислений. Но правильно организованный процесс позволитучесть непрерывно нарастающие возможности вычислительной техники в максимальной степени. Сплайн-функции Пусть на отрезке , то есть Замечание. Индекс (t) у чисел а^ указывает на то. что набор коэффициентов, которым определяется функция 5(х), на каждом частичном отрезке Д, свой. На каждом из отрезков Д1, сплайн 5(х) является многочленом степени р и определяется на этом отрезке р + 1 коэффициентом. Всего частичных отрезков - то. Значит, для того, чтобы полностью определить сплайн, необходимо найти (р + 1)то чисел Условие) означает непрерывность функции 5(ж) и ее производных во всех внутренних узлах сетки ш. Число таких узлов m - 1. Тем самым, для отыскания коэффициентов всех многочленов получается р(т - 1) условий (уравнений). Для полного определения сплайна недостает (условий (уравнений). Выбор дополнительных условий определяется характером рассматриваемой задачи, а иногда и просто - желанием пользователя. ТЕОРИЯ СПЛАЙНОВ примеры решения Наиболее часто рассматриваются задачи интерполяции и сглаживания, когда требуется построить тот или иной сплайн по заданному массиву точек на плоскости В задачах интерполяции требуется, чтобы график сплайна проходил через точки что накладывает на его коэффициенты m + 1 дополнительных условий (уравнений). Остальные р - 1 условий (уравнений) для однозначного построения сплайна чаще всего задают в виде значений младших производных сплайна на концах рассматриваемого отрезка [а, 6] - граничных (краевых) условий. Возможность выбора различных граничных условий позволяет строить сплайны, обладающие самыми разными свойствами. В задачах сглаживания сплайн строят так, чтобы его график проходил вблизи точек (я»» У»), * = 0, 1,... , т, а не через них. Меру этой близости можно определять по-разному, что приводит к значительному разнообразию сглаживающих сплайнов. Описанные возможности выбора при построении сплайн-функций далеко не исчерпывают всего их многообразия. И если первоначально рассматривались только кусочно полиномиальные сплайн-функции, то по мере расширения сферы их приложений стали возникать сплайны, «склеенные» и из других элементарных функций. Интерполяционные кубические сплайны Постановка задачи интерполяции Пусть на отрезке [а, 6) задана сетка ш Рассмотрим набор чисел Задача. Построить гладкую на отрезке (а, 6] функцию которая принимает в узлах сетки о» заданные значения, то есть Замечание. Сформулированная задача интерполяции состоит в восстановлении гладкой функции, заданной таблично (рис. 2). Ясно, что такая задача имеет множество различных решений. Накладывая на конструируемую функцию дополнительные условия, можно добиться необходимой однозначности. В приложениях часто возникает необходимость приблизить функцию, заданную аналитически, при помощи функции с предписанными достаточно хорошими свойствами. Например, в тех случаях, когда вычисление значений заданной функции /(х) в точках отрезка [а, 6] связано со значительными трудностями и/или заданная функция /(х) не обладает требуемой гладкостью, удобно воспользоваться другой функцией, которая достаточно хорошо приближала бы заданную функцию и была лишена отмеченных ее недостатков. Задача интерполяции функции. Построить на отрезке [а, 6] гладкую функцию а(х), совпадающую в узлах сетки ш с заданной функцией /(х). Определение интерполяционного кубического сплайна Интерполяционным кубическим сплайном S(x) на сетке ш называется функция, которая 1) на каждом из отрезков, представляет собой многочлен третьей степени, 2) дважды непрерывно дифференцируема на отрезке [а, Ь], то есть принадлежит классу С2[а, 6], и 3) удовлетворяет условиям На каждом из отрезков сплайн S(x) является многочленом третьей степени и определяется на этом отрезке четырьмя коэффициентами. Всего отрезков - т. Значит, для того, чтобы полностью определить сплайн, необходимо найти 4т чисел Условие означает непрерывность функции S(x) и ее производных S"(x) и 5"(х) во всех внутренних узлах сетки ш. Число таких узлов - m - 1. Тем самым, для отыскания коэффициентов всех многочленов получается еще 3(m - 1) условий (уравнений). Вместе с условиями (2) получается условия (уравнения). Граничные (краевые) условия Два недостающих условия задаются в виде ограничений на значения сплайна и/или его производных на концах промежутка [а, 6]. При построении интерполяционного кубического сплайна наиболее часто используются краевые условия следующих четырех типов. A. Краевые условия 1-го типа. - наконцах промежутка [а, Ь] задаются значения первой производной искомой функции. Б. Краевые условия 2-го типа. - наконцах промежутка (а, 6) задаются значения второй производной искомой функции. B. Краевые условия 3-го типа. называются периодическими. Выполнения этих условий естественно требовать в тех случаях, когда интерполируемая функция является периодической с периодом Т = Ь-а. Г. Краевые условия 4-го типа. требуют особого комментария. Комментарий. Во внутренних узлах сепси третья производная функции S(x), вообще говоря, разрывна. Однако число разрывов третьей производной можно уменьшить при помоши условий 4-го типа. В этом случае построенный сплайн будет трижды непрерывно дифференцируем на промежутках Построение интерполяционного кубического сплайна Опишем способ вычисления коэффициентов кубического сплайна, при котором число величин, подлежащих определению, равно. На каждом из промежутков интерполяционная сплайн-функция ищется в следующем виде Здесь ТЕОРИЯ СПЛАЙНОВ примеры решения а числа являются решением системы линейных алгебраических уравнений, вид которой зависит от типа краевых условий. Для краевых условий 1-го и 2-го типов эта система имеет следующий вид где Коэффициенты зависят от выбора краевых условий. Краевые условия 1-го типа: Краевые услоемв 2-го типа: В случае краевых условий 3-го типа система для определения чисел записывается так Число неизвестных в последней системе равно тп, так как изусловия периодичности вытекает, что по = пт. Для краевых условий 4-го типа система для определения чисел, имеет вид где По найденному решению системы числа по и пт можно определить при помощи формул Важное замечание. Матрицы всех трех линейных алгебраических систем являются матрицами с диагональным преобладавшем. Тамие матрицы не вырождены, и потому каждая из этих систем имеет единственное решение. Теорема. Интерполяционный кубический сплайн, удовлетворяющий условиям (2) и краевому условию одного из перечисленных четырех типов, существует и единствен. Таким образом, построить интерполяционный кубический сплайн - это значит найти его коэффициенты Когда коэффициенты сплайна найдены, значение сплайна S(x) в произвольной точке отрезка [а, Ь] можно найти г!о формуле (3). Однако для практических вычислений больше подходит следующий алгоритм нахождения величины 5(ж). Пусть х 6 [х», Сначала вычисляются величины А и В по формулам а затем находится величина 5(ж): Применение этого алгоритма существенно сокращает вычислительные затраты на определение величины Советы пользователю Выбор граничных (краевых) условий и узлов интерполяции позволяет в известной степени управлять свойствами интерполяционных сплайнов. А. Выбор граничных (краевых) условий. Выбор граничных условий является одной из центральных проблем при интерполяции функций. Он приобретает особую важность в том случае, когда необходимо обеспечить высокую точность аппроксимации функции f(x) сплайном 5(ж) вблизи концов отрезка [а, 6). Граничные значения оказывают заметное влияние на поведение сплайна 5(ж) вблизи точек а и Ь, и это влияние по мере удаления от них быстро ослабевает. Выбор граничных условий часто определяется наличием дополнительных сведений о поведении аппроксимируемой функции f(x). Если на концах отрезка (а, 6] известны значения первой производной f"(x), то естественно воспользоваться краевыми условиями 1-го типа. Если на концах отрезка [а, 6) известны значения второй производной f"(x), то естественно воспользоваться краевыми условиями 2-го типа. Если есть возможность выбора между краевыми условиями 1-го и 2-го типов, то предпочтение следует отдать условиям 1- го типа. Если f(x) - периодическая функция, то следует остановиться накраевых условиях 3-го типа. В случае, если никакой дополнительной информации о поведении аппроксимируемой функции нет, часто используют так называемые естественные граничные условия Однако следует иметь ввиду, что при таком выборе граничны*условий точность аппроксимации функции f(x) сплайном S(x) вблизи концов отрезка (а, ft] резко снижается. Иногда используются краевые условия 1-го или 2-го типа, но не с точными значениями соответствующих производных, а с их разностными аппроксимациями. Точность такого подхода невысока. Практический опыт расчетов показывает, что в рассматриваемой ситуации наиболее целесообразным является выбор граничных условий 4-го типа. Б. Выбор узлов интерполяции. Если третья производная f""(x) функции терпитразрыв в не которыхточках отрезка [а, Ь], то для улучшения качества аппроксимации эти точки следует включить в число узлов интерполяции. Если разрывна вторая производная /"(х), то для того, чтобы избежать осцилляции сплайна вблизи точек разрыва, необходимо принять специальные меры. Обычно узлы интерполяции выбирают так, чтобы точки разрыва второй производной попадали внутрь промежутка \xif), такого, что. Величину а можно выбрать путем численного эксперимента (часто достаточно положить а =0,01). Существует набор рецептов по преодолению трудностей, возникающих при разрывной первой производной f"{x). В качестве одного из самых простых можно предложить такой: разбить отрезок аппроксимации на промежутки, где производная непрерывна, и на каждом из этих промежутков построить сплайн. Выбор интерполяционной функции (плюсы и минусы) Подход 1-й. Интерполяционный многочлен Лагранжа По заданному массиву ТЕОРИЯ СПЛАЙНОВ примеры решения (рис.3) интерполяционный многочлен Лагранжа определяется формулой Свойства интерполяционного многочленаЛагранжа целесообразно рассматривать с двух противоположных позиций, обсуждая основные достоинства отдельно от недостатков. Основные достоинства 1 -го подхода: 1) график интерполяционного многочлена Лагранжа проходит через каждую точку массива, 2) конструируемая функция легко описывается (число подлежащих определению коэффициентов интерполяционного многочлена Лагранжа на сетке и> равно m + 1), 3) построенная функция имеет непрерывные производные любого порядка, 4) заданным массивом интерполяционный многочлен определен однозначно. Основные недостатки 1 -го подхода: 1) степень интерполяционного многочлена Лагранжа зависит от числа узлов сетки, и чем больше это число, тем выше степень интерполяционного многочлена и, значит, тем больше требуется вычислений, 2) изменение хотя бы одной точки в массиве требует полного пересчета коэффициентов интерполяционного многочлена Лагранжа, 3) добавление новой точки в массив увеличивает степень интерполяционного многочлена Лагранжа на единицу и таиже приводит к полному пересчету его коэффициентов, 4) при неограниченном измельчении сетки степень интерполяционного многочлена Лагранжа неограниченно возрастает. Поведение интерполяционного многочлена Лагранжа при неограниченном измельчении сетки вообше требует особого внимания. Комментарии А. О приближении непрерывной функции многочленом. Известно (Вейерштрасс, 1885 год), что всякая непрерывная (а тем более гладкая) на отрезке функция может быть как угодно хорошо приближена на этом отрезке многочленом. Опишем этот факт на языке формул. Пусть f(x) - функция, непрерывная на отрезке [а, 6]. Тогдадл я любого е > 0 найдется такой многочлен Р„(х),чтодля любого х из промежутка [а, 6] будет выполняться неравенство (рис. 4) Отметим, что многочленов даже одной степени, приближающих функцию f(x) с указанной точностью, существует бесконечно много. Построим наотрезке [а, 6] сетку w. Ясно, что ее узлы, вообще говоря, не совпадают с точками пересечения графиков многочлена Рп(х) и функции f(x) (рис. 5). Поэтому для взятой сетки многочлен Рп(х) не является интерполяционным. При аппроксимации непрерывной функции интерполяционным многочленом Jla-гракжа его график не только не обязан быть близким графику функции f(x) в каждой точке отрезка [а, Ь), но может уклоняться от этой функции как угодно сильно. Приведем два примера. Пример 1 (Рунг, 1901 год). При неограниченном увеличении числа узлов для функции на отрезке [-1, 1] выполняется предельное равенство (рис.6) Пример 2 (Бериштейн, 1912год). Последовательность интерполяционных многочленов Лагранжа построенных на равномерных сетках шт для непрерывной функции /(х) = |х| на отрезке с возрастанием числе узлов т не стремится к функции /(х) (рис.7). Подход 2-й. Кусочно-лииейнм интерполяция При отказе от гладкости интерполируемой функции соотношение между числом достоинств и числом недостатков можно заметно изменить в сторону первых. Построим кусочно-линейную функцию путем последовательного соединения точек (xit у,) прямолинейными отрезками (рис. 8). Основные достоинства 2 -го подхода: 1) график кусочно-линейной функции проходит через каждую точку массива, 2) конструируемая функция легко описывается (число подлежащих определению коэффициентов соответствующих линейных функций для сетки (1) равно 2т), 3) заданным массивом построенная функция определена однозначно, 4) степень многочленов, используемых для описания интерполяционной функции, не зависит от числа узлов сетки (равна 1), 5) изменение одной точки в массиве требует вычисления четырех чисел (коэффициентов двух прямолинейных звеньев, исходящих из новой точки), 6) добавление дополнительной точки в массив требует вычисления четырех коэффициентов. Кусочно-линейная функция достаточно хорошо ведет себя и при измельчении сетки. я Основной недостаток 2-гоподхода: аппроксимирующая кусочно-линейная функция не является гладкой: первые производи ые терпят разрыв в узлах сетки (ушах интерполяции). Подход 3-й. Сплайн-интерполяция Предложенные подходы можно объединить так, чтобы число перечисленных достоинств обоих подходов сохранилось при одновременном уменьшении числа недостатков. Это можно сделать путем построения гладкой интерполяционной сплайн-функции степени р. Основные достоинства 3 -го подхода: 1) график построенной функции проходит через каждую точку массива, 2) конструируемая функция сравнительно легко описывается (число подлежащих определению коэффициентов соответствующих многочленов для сетки (1) равно 3) заданным массивом построенная функция определена однозначно, 4) степень многочленов не зависит от числа узлов сетки и, следовательно, не изменяется при его увеличении, 5) построенная функция имеет непрерывные производные до порядка р - 1 включительно, 6) построенная функция обладает хорошими аппроксимационными свойствами. Краткая справка. Предложенное название - сплайн - не является случайным - введенные нами гладкие ку-сочно-полиномиальныефункции и чертежные сплайны тесно связаны. Рассмотрим гибкую идеально тон кую линейку, проходящую через расположенные на плоскости (х, у) опорные точки массива. Согласно закону Бернулли-Эйлера линеаризованное уравнение изогнутой линейки имеет вид где S(x) - изгиб, М(х) - изменяющийся линейно от опоры к опоре изгибающий момент, Е1 - жесткость линейки. Функция S(x), описывающая формулинейки, является многочленом третьей степени между каждым и двумя соседними точками массива (опорами) и дважды непрерывно дифференцируема на всем промежутке (а, 6). Комментарий. 06 интерполировании непрерывной функции В отличие от интерполяционных многочленов Лагранжа, последовательность интерполяционных кубических сплайнов на равномерной сетке всегдасходится к интерполируемой непрерывной функции, причем с улучшением дифференциальных свойств этой функции скорость сходимости повышается. Пример. Для функции кубический сплайн на сетке с числом узлов m = 6 дает погрешность аппроксимации того же порядка, что и интерполяционный многочлен Ls(z), а на сетке с числом узлов m = 21 эта погрешность настолько мала, что в масштабе обычного книжного рисунка просто не может быть показана (рис.10) (интерполяционный многочлен 1>2о(г) дает в этом случае погрешность около 10 000 Ж). Свойства имтерполяцкокного кубического сплайна А. Алпроксимационмые свойства кубического сплайна. Аппроксимационные свойства интерполяционного сплайна зависят от гладкости функции f(x) - чем выше гладкость интерполируемой функции, тем выше порядок аппроксимации и при измельчении сетки тем выше скорость сходимости. Если интерполируемая функция f(x) непрерывна на отрезке Если интерполируемая функция f{x) имеет на отрезке [а, 6] непрерывную первую производную, то есть интерполяционный сплайн, удовлетворяющий граничным условиям 1-го или 3-го типа, то при h О имеем В этом случае не только сплайн сходится к интерполируемой функции, но и производная сплайна сходится к производной этой функции. В случае, если сплайн S(x) аппроксимирует на отрезке [а, Ь] функцию f(x), а его первая и вторая производные аппроксимируют соответственно функции Б. Экстремальное свойство кубического сплайна. Интерполяционный кубический сплайн обладает еще одним полезным свойством. Рассмотрим следующий пример. ример. Построить функцию/(х), минимизирующую функционал на классе функций из пространства С2, графики которых проходят через точки массива Среди всех функций, проходящих через опорные точки (х;, /(х,)) и принадлежащих указанному пространству, именно кубический сплайн 5(х), удовлетворяющий краевым условиям доставляет Экстремум (минимум) функционалу Замечание 1. Часто именно это экстремальное свойство берут в качестве определения интерполяционного кубического сплайна. Замечание 2. Интересно отметить, что интерполяционный кубический сплайн обладает описанным выше экстремальным свойством на очень широком классе функций, а именно, на классе |о, 5 ]. 1.2. Сглаживающие кубические сплайны О постановке задачи сглаживания Пусть заданы сетка и набор чисел Комментарий к исходным данным На практике часто приходится иметь дело со случаем, когда значения у, в массиве заданы с некоторой погрешностью. Фактически это означает, что для каждого указан интервал и любое число из этого интервала может быть взято в качестве значения у, . Величины у, удобно интерпретировать, например, как результаты измерений некоторой функции у(х) при заданных значениях переменной х, содержащие случайную погрешность. При решении задачи восстановления функции по таким ее «экспериментальным» значениям вряд ли целесообразно использовать интерполяцию, поскольку интерполяционная функция будет послушно воспроизводить причудливые осцилляции, обусловленные случайной компонентой в массиве {у,}. Более естественным является подход, основанный на процедуре сглаживания, призванной как-то уменьшить элемент случайности в результате измерений. Обычно в таких задачах требуется найти функцию, значения которой при х = ж, * = 0, 1,.... т, попадали бы в соответствующие интервалы и которая обладала бы, кроме того, достаточно хорошими свойствами. Например, имела бы непрерывные первые и вторые производные, или же ее график был бы не слишком сильно искривлен, то есть не имел бы сильных осцилляций. Задача подобного рода возникает и тогда, когда по заданному (точно) массиву требуется построить функцию, которая проходилабы нечереззаданныеточки, а вблизи них и к тому же изменялась достаточно плавно. Другими словами, искомая функция как бы сглаживала заданный массив, а не интерполировала его. Пусть заданы сетка ш и два набора чисел ТЕОРИЯ СПЛАЙНОВ примеры решения Задача. Построить гладкую на отрезке [а, А] функцию, значения которой в узлах сетки и» отличались от чисел у,- на заданные величины -Зшочтио. Сформулированная задача сглаживания состоит в восстановлении гладкой функции, заданной таблично. Ясно, что такая задача имеет множество различных решений. Накладывая на конструируемую функцию дополнительные условия, можно добиться необходимой однозначности. Определение сглаживающего кубического сплайна Сглаживающим кубическим сплайном S(x) на сетке ш называется функция, которая 1) на каждом из отрезков представляет собой многочлен третьей степени, 2) дважды непрерывно дифференцируема на отрезке [а, 6], то есть принадлежит классу С2 [а, Ь], 3) доставляет минимум функционалу где - заданные числа, 4) удовлетворяет граничным условиям одного из трех указанных ниже типов. Граничные (краевые) условия Граничные условия задаются в виде ограничений на значения сплайна и его производных в граничных узлах сетки ш. А. Граничные условия 1-го типа. - наконцах промежутка [а, Ь) задаются значения первой производной искомой функции. Граничные условия 2-го типа. - вторые производные искомой функции на концах промежутка (а, Ь] равны нулю. В. Граничные условия 3-го типа. называются периодическими. Теорема. Кубический сплайн S(x), минимизирующий функционал (4) и удовлетворяющий краевым условиям одного из указанных трех типов, определен однозначно. Определение. Кубический сплайн, минимизирующий функционал J(f) и удовлетворяющий граничным условиям i-готипа, называется сглаживающим сплайном i-готипа. Замечание. На каждом изотрезков(,сплайн 5(х) является миоючасном третьей степени и определяется на этом отрезке четырьмя коэффициентами. Всего отрезков - т. Значит, для того, чтобы полностью определять сплайн, необходимо найти 4т чисел Условие означает непрерывность функции 5(аг) и се производных во всех внутреннж узлах сетки о». Число таких узлов - m - 1. Тем самым, для отысивния коэффициентов всех многочленов получается 3(m - 1) условий (уравнений). Построение сглаживающего кубического сплайна Опишем способвычисления коэффициентов кубическогосплайна, при котором число величин, подлежащих определению, равно 2т + 2. На каждом из промежутков сглаживающая сплайн-функция ищется в следующем виде Здесь а числа и, являются решением системы линейных алгебраических уравнений, вид которой зависитот типа краевых условий. Опишем сначала, как находятся величины п*. Для краевых условий 1-го и 2-го типов система линейных уравнений для определения величин Hi записывается в следующем виде где известные числа). Коэффициенты зависят от выбора граничных условий. Граничные условия 1-го типа: Граничные условия 2-го типа: В случае граничных условий 3-го типа система для определения чисел записывается так: причем все коэффициенты вычисляются по формулам (5) (величины с индексами к и т + к считают я равными: Важно* замечание. Матрицы систем не вы рождены и потому каждая из этих систем имеет единственное решение. Если числа п,- найдены, то величины легко определяются по формулам где В случае периодических граничных условий Выбор еесоеш коэффициентов Выбор весовых коэффициентов р,-, входящих в функционал (4), позволяете известной степени управлять свойствами сглаживающих сплайнов. Если все и сглаживающий сплайн оказывается интерполяционным. Это, в частности, означает, что чем точнее заданы величины, тем меньше дошкн ы быть соотпетствуюшие весовые коэффициенты. Если же необходимо, чтобы сплайн прошел через точку (х^, Ук), то отвечающий ем у весовой множитель р\ следует поломить равным нулю. В практический вычислениях наиболее важым является выбор величин pi-Пусть Д, - погрешность измерения величины у,. Тогда естественно потребовать, чтобы сглаживающий сплайн удовлетворял условию или, что то же, В простейшем случае весовые коэффициенты pi можно задать, например, форму- где с - некоторая достаточно малая постоянная. Однако такой выбор весов р, не позволяет использовать «коридор», обусловленный погрешностями величин у,-. Более рациональный, но и более трудоемкий алгоритм определения величин р,- может выглядеть следующим образом. Если на fc-й итерации величины найдены,то полагают где е - малое число, которое выбирается экспериментально с учетом разрядной сетки компьютера, значений Д, и точности решения системы линейных алгебраических уравнений. Если на fc-й итерации в точке я, нарушилось условие (6), то последняя формула обеспечит уменьшение соответствующего весового коэффициента р,. Если же то на следующей итерации Увеличение р, приводит к более полному использованию «коридора» (6) и, в конечном счете, более плавно изменяющемуся сплайну. Немного теории А. Обоснование формул для вычисления коэффициентов интерполяционного кубического сплайна. Введем обозначения где m, - неизвестные пока величины. Их число равно m + 1. Сплайн, записанный в форме, где удовлетворяет условиям интерполяции и непрерывен на всем промежутке [а, Ь\: положив в формуле, получим соответственно Кроме того, он имеет на промежутке [а, 6] непрерывную первую производную: продифференцировав соотношение (7) и положив, пОлучим соответ-. ственно. Покажем, что числа т, можно выбрать так, чтобы сплайн-функция (7) имела на отрезке [а, 6] непрерывную вторую производную. Вычислим на промежутке вторую производную сплайна: В точке х, - 0 (при t = 1) имеем Вычислим на промежутке вторую производную сплайна В точке имеем Из условия непрерывности второй производной во внутренних узлах сетки а; получаем m - 1 соотношение где Добавляя к этим т - 1 уравнениям еще два, вытекающих и з краевых условий, получаем систему из m+ 1 линейного алгебраического уравнения с т + I неизвестной miy i = 0, 1. ... , m. Система уравнений для вычисления величин гщ в случае краевых условий 1-го и 2-го типов имеет вид где (краевые условия 1 -го типа), (краевые условия 2 -го типа). Для периодических краевых условий (краевыеусловия 3-го типа) сетку о; удлиняют еще на один узел и полагают Тогда система для определения величин го* будет иметь вид Для того чтобы получить систему уравнений для определения чисел го, в случае краевых условий 4-го типа, найдем на отрезке [ третью производную сплайна (7) и потребуем ее непрерывности во втором и (го - !)-м узлах сетки. Имеем Из последних двух соотношений получаем недостающие два уравнения, отвечающие краевым условиям 4 -го типа: Исключая из уравнений неизвестное гоо, а из уравнений неизвестное пц, в результате получим систему уравнений Отметим, что число неизвестных в этой системе равно го - I. 6. Обоснование формул дм вычисления юэффиие кто« сглаживающего субичессого сплайна. Введем обозначения где Zi и nj - неизвестные пока величины. Их число равно 2т + 2. Сплайн-функиия, записанная в форме непрерывна на всем промежутке (а, 6]: положив в этой формуле, получим соответственно Покажем, что числа z, и п, можно выбратьтак, чтобы сплайн, записанный в форме (8), имел на промежутке [а, 6] непрерывную первую производную. Вычислим первую производную сплайна S(x) на промежутке : В точке х^ - 0 (при t = 1) имеем Вычислим первую производаую сплайна 5(х) на промежутке : В точке имеем Из условия непрерывности первой производой сплайна во внутренних узлах сетки и --> получаем m - 1 соотношение Эту связь удобно записать в матричной форме Здесь использованы следующие обозначения Кроме того, сплайн на промежутке [а, 6} имеет непрерывную вторую производную: продифференцировав соотношение (8) и положив, получим соответственно Еше олю матричное соотношение получается из условия минимума функционала (4). Имеем Два последних матричных равенства можно рассматривать как линейную систему 2т+2 линейных алгебраических уравнений относительно 2т + 2 неизвестных. Заменяя в первом равенстве столбец г его выражением, полученным из соотношения (9), приходим к матричному уравнению ТЕОРИЯ СПЛАЙНОВ примеры решения для определения столбца М. Это уравнение имеет единственное решение вследствие того, что матрица A + 6HRH7 всегда невырождена. НаЙдяего, мылегко определяем г. Эамсшине. Элементы трелдмаголальн ых матриц А и Н определяющие я только параметрами сетки и (сс шагами hi) и не зависят от величин у^. Линейное пространство кубических сплайн-функций Множество кубических сплайнов, построенных на отрезке [а, 6) по сетке wcra+l узлом, является линейным пространством размерности т + 3: 1) сумма двух кубических сплайнов, построенных по сетке и>, и произведение кубического сплайна, построенного по сетке и>, на произвольное число тайнее являются кубическими сплайнами, построенными по этой сетке, 2) любой кубический сплайн, построенный по сетке и из узла, полностью определяется т + 1 значением величин у» в этих узлах и двумя граничными условиями - всего то + 3 параметрами. Выбрав в этом пространстве базис, состоящий из m + 3 линейно независимых сплайнов, мы можем записать произвольный кубический сплайн а(х) в виде их линейной комбинации причем единственным образом. Замечание. Подобное задание сплайна широко распространено в вычислительной практике. Особенно удобным является базнс, состоящий из так называемых кубических В -сплайнов (базовых, или фундаментальных, сплайнов). Применение Д-сплайнов позволяет существенно снизить требования к объему памяти компьютера. Л-сплайны. В -сплайномнулевой степени, построенным на числовой прямой по сетке ш, называется функция вила В -сплайн степени к ^ I, построенный на числовой прямой по сетке иг, определяется посредством рекуррентной формулы Графики В -сплайнов первой В,-1"(ж) и второй в\7\х) степеней представлены на рис. 11 и 12 соответственно. В-сплайн произвольной степени к может быть отличен от нуля только на некотором отрезке (определяемом к + 2 узлами). Кубические В-сплайны удобнее нумеровать так, чтобы сплайн В,-3* (я) был отличен от нуля на отрезке яг,-+2]. Приведем формулу для кубического сплайна третьей степени для случая равномерной сетки (с шагом Л). Имеем в остальных случаях. Типичный график кубического В-сплайна представлен на рис. 13. Займами*. функция а) дважды непрерывно дифференцируема на отрезке то есть принадлежат классу С2[а, »}, к б) отлична от нуля толь ко на четырех последовательных отрезках (Дополним сетку ш вспомогательными узлами взятыми совершенно произвольно. По расширенной сетке ш* можно построить семейство из m + 3 кубических В -сплайнов: Это семейство образует базис в пространстве кубических сплайнов на отрезке (а, Ь]. Тем самым, произвольный кубический сплайн S(z), построенный на отрезке |в, 6] посетке о; изт+1 узла, может быть представлен наэтом отрезке в виде линейной комбинации Условиями задачи коэффициенты ft, этого разложения определяются однозначно. ... В случае, когда заданы значения у* функции в узлах сетки и значения у о и Ут первой производной функции на концах сетки"(задача интерполяций с граничными условиями первого рода), эти коэффициенты вычисляются из системы следующего вида После исключения величин б-i и &m+i получается линейная система с неизвестными 5q, ... , Ьт и трех диаюнальной матрицей. Условие обеспечивает диагональное преобладание и, значит, возможность применения метода прогонки для ее разрешения. 3ММЧМЮ 1. Линейные системы аналогичного вида возникают лрн рассмотрении и других задач интерполяции. Зммчнм* 2. В сравнении с алгоритмами, описанными в раздеде 1.1, применение Я-сплайн в * задачах интерполяции позволяет уменьшит* объем хранимой информации, то есть сушественно снизить требования к объему памяти компьютере, хотя и приводит к увеличению числа операций. Построение сплайноаых кривых при помощи сплайн-функций Выше рассматривались массивы, точки которых были занумерованы так, что их абсциссы образовывали строго возрастающую последовательность. Например, случай, изображенный на рис. 14, когда у разных точек массива одинаковые абсциссы, не допускался. Это обстоятельств о определяло и выбор класса аппроксимирующих кривых (трафики функций), и способ их построения. Однако предложенный выше метод позволяет достаточно успешно строить интерполяционную кривую и в более общем случае, когда нумерация точек массива и их расположение на плоскости, как правило, не связаны (рис. 15). Более того, ставя задачу построения интерполяционной кривой, можно считать заданный массив неплоски м, то есть Ясно, что для решения этой общей задачи необходимо существенно расширить класс допусти мых кривых, включив в него и замкнутые кривые, и кривые, имеющие точки самопересечения, и пространственные кривые. Такие кривые удобно описывать при помощи параметрических уравнений Потребуем. дополнительно, чтобы функции обладали достаточной гладкостью, например, принадлежали классу С1 [а, /0] или классу Для отыскания параметрических уравнений кривой, последовательно проходящей через все точки массива, поступают следующим образом. 1-й шаг. На произвольно взятом отрезке .Df; } set { _points[_points.Length - 1].Df = value; } } public double Ddfn { get { return _points[_points.Length - 1].Ddf; } set { _points[_points.Length - 1].Ddf = value; } } public CSpline(CPoint points) { _points = points; _splines = new CSplineSubinterval; } public void GenerateSplines() { const double x1 = 0; var y1 = BuildSplines(x1); const double x2 = 10; var y2 = BuildSplines(x2); _points.Ddf = -y1 * (x2 - x1) / (y2 - y1); BuildSplines(_points.Ddf); _points[_points.Length - 1].Ddf = _splines[_splines.Length - 1].Ddf(_points[_points.Length - 1].X); } private double BuildSplines(double ddf1) { double df = _points.Df, ddf = ddf1; for (var i = 0; i < _splines.Length; i++) { _splines[i] = new CSplineSubinterval(_points[i], _points, df, ddf); df = _splines[i].Df(_points.X); ddf = _splines[i].Ddf(_points.X); if (i < _splines.Length - 1) { _points.Df = df; _points.Ddf = ddf; } } return df - Dfn; } }

Синие отрезки - это первые производные сплайна в соответствующих его точках. Добавил такой вот графический элемент для большей наглядности.

Достоинства и недостатки алгоритма

Навскидку можно сказать, что сложность алгоритма - O(N), так как, как я уже говорил, вне зависимости от количества точек, достаточно двух прогонов вычислений, чтобы получить правильное значение второй производной на левом конце интервала, и еще одного, чтобы построить сплайн.

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

Так а в чем провинились тесты IQ?

Рассмотрим для начала ряд «2, 4, 6, 8, ?»
Представим себе этот числовой ряд как множество пар значений :

Где в качестве мы берем само число, а в качестве – порядковый номер этого числа. Какое значение должно быть на месте ?

Мысль, к которой я стараюсь плавно подвести – это то, что мы можем подставить абсолютно любое значение. Ведь что по факту проверяют такие задачи? Способность человека найти некое правило, которое связывает все имеющиеся числа, и по этому правилу вывести следующее число в последовательности. Говоря научным языком, здесь стоит задача экстраполяции (задача интерполяции состоит в том, чтобы найти кривую, проходящую через все точки внутри некоторого интервала, а задача экстраполяции – продолжить эту кривую за пределы интервала, «предсказав» таким образом поведение кривой в дальнейшем). Так вот, экстраполяция не имеет однозначного решения. Вообще. Никогда. Если бы было иначе, люди давным-давно бы предсказали прогноз погоды на всю историю человечества вперед, а скачки курса рубля никогда не были бы неожиданностью.

Разумеется, предполагается, что верный ответ в этой задаче все-таки есть и он равен 10, и тогда «закон», связывающий все эти числа, – это

ПОТОЧЕЧНОЕ ОПИСАНИЕ ПОВЕРХНОСТЕЙ.

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

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

Пример : Участки грунта на других планетах, формы небесных тел, информация о которых получена в результате спутниковых съемок. Микрообъекты, снятые с помощью электронных микроскопов.

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

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

o моделирования кривых;

o аппроксимации данных с помощью кривых;

o выполнения функциональных аппроксимаций;

o решения функциональных уравнений.

Рассмотрим задачу проведения гладких кривых по заданным граничным точкам, или задачу интерполяции. Поскольку через две точки можно провести сколь угодно много гладких кривых, то для решения этой задачи необходимо ограничить класс функций, которые будут определять искомую кривую. Математическими сплайнами называют функции, используемые для аппроксимации кривых. Важным их свойством является простота вычислений. На практике часто используют сплайны вида полиномов третьей степени. С их помощью довольно удобно проводить кривые, которые интуитивно соответствуют человеческому субъективному понятию гладкости. Термин “сплайн” происходит от английского spline – что означает гибкую полоску стали, которую применяли чертежники для проведения плавных кривых, например для построения обводов кораблей или самолетов.

Рассмотрим вначале сплайновую функцию для построения графика функции одной переменной. Пусть на плоскости задана последовательность точек ,, причем . Определим искомую функцию , причем поставим два условия:

1) Функция должна проходить через все точки: , ;

2) Функция должна быть дважды непрерывно дифференцируема, то есть иметь непрерывную вторую производную на всем отрезке .

На каждом из отрезков , , будем искать нашу функцию в виде полинома третьей степени:

.

Сплайновая функция

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

Перейдем к более сложному случаю – заданию кривых в трехмерном пространстве. В случае функционального задания кривой возможны многозначности в случае самопересечений и неудобства при значениях производных равных . Ввиду этого будем искать функцию в параметрическом виде. Пусть - независимый параметр, такой что . Кубическим параметрическим сплайном назовем следующую систему уравнений:

Координаты точек на кривой описываются вектором , а три производные задают координаты соответствующего касательного вектора в точке. Например, для координаты :

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

Будем решать задачу нахождения четверки коэффициентов , так как для оставшихся двух уравнений коэффициенты находятся аналогично. Запишем условие для построения сплайна:

Перепишем выражение для в векторном виде:

.

Обозначим вектор строку и вектор столбец коэффициентов , тогда .

Из (*) следует, что , . Для касательных ,

Отсюда получаем векторно-матричное уравнение:

.

Эта система решается относительно нахождением обратной матрицы размером .

.

Здесь - эрмитова матрица, - геометрический вектор Эрмита. Подставим выражение для нахождения : . Аналогично для остальных координат: , .