Теория сплайнов примеры решения

Содержание:

  1. Теорема:
  2. Сплайн-интерполяция
  3. Определение сглаживающего кубического сплайна

Теория сплайнов примеры решения

Теория сплайнов примеры решения

Теория сплайнов примеры решения

Теория сплайнов примеры решения

Теория сплайнов примеры решения

Теория сплайнов примеры решения

Теория сплайнов примеры решения

Теория сплайнов примеры решения

Теория сплайнов примеры решения

Теория сплайнов примеры решения

Теория сплайнов примеры решения

Теория сплайнов примеры решения

Теория сплайнов примеры решения

Теория сплайнов примеры решения

Теория сплайнов примеры решения

Теория сплайнов примеры решения

Теория сплайнов примеры решения

Теория сплайнов примеры решения

Теория сплайнов примеры решения

Теория сплайнов примеры решения

Теория сплайнов примеры решения

Теория сплайнов примеры решения

Теория сплайнов примеры решения

Теория сплайнов примеры решения

Теория сплайнов примеры решения

 

По этой ссылке вы найдёте полный курс лекций по математике:

Решение задач по математике

 

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

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

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

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

Сплайн-функции Пусть на отрезке [a, 6J задана сетка и> Точки а?о и хт называются граничными у злами сетки о;, а точки внутренними узлами (рис. 1). Сетка называется равномерной, если расстояния между любыми двумя соседними узлами одинаковы. Функция S(s), заданная на отрезке (а, 6), называется сплайном порядка р 1 (степени р), если эта функция 1) на каждом из огрезков является многочленом заданной степени р ^ 2, то есть может быть записана в виде 2) p - 1 раз непрерывно дифференцируема на отрезке [a, 6], то есть Замечание.

Индекс (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) на промежутке [zi-i, х,]: В точке х^ - 0 (при t = 1) имеем Вычислим первую производаую сплайна 5(х) на промежутке [xj, х,»]: В точке имеем Из условия непрерывности первой производой сплайна во внутренних узлах сетки и --> получаем 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-й шаг. На произвольно взятом отрезке [a, /3( изменения параметра t вводится вспомогательная сетка число узлов которой совпадает с числом точек в массиве Р. 2-й шаг.

По заданному массиву Р строятся три новых вспомогательных массива (в плоском случае два) (рис. 16 (плоский случай)). 1-й шаг. Для каждого из массивов X, У и Z находятся соответствующие интерполяционные сплайн-функции x(t), y(t) и z(t). В результате мы получаем параметрические уравнения кривой, проходящей через точки (см. рис. 17 для плоского случая). Замечание 1. Предложенный подход позволяет строить замкнутые интерполяционные кривые (при Р0 = Р«); для этого при _, построении координатных функций x(t), у(<) и z(t) нужно ис- О1 пользовать граничные условия 3-го типа. Рис 17 Замечен ие 2.

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