Главная > Алгоритмы машинной графики и обработки изображений
НАПИШУ ВСЁ ЧТО ЗАДАЛИ
СЕКРЕТНЫЙ БОТ В ТЕЛЕГЕ
<< Предыдущий параграф Следующий параграф >>
Пред.
След.
Макеты страниц

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

Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике

ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO

11.5. ИНТЕРПОЛЯЦИОННЫЕ В-СПЛАЙНЫ

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

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

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

Всего имеется таких уравнений с к неизвестными. Каждое из уравнений содержит членов и, следовательно, соответствующая матрица разделена на слои, определяемые, по меньшей мере, нижними и верхними диагоналями. с примером 11.1.] Точное описание кривой зависит от взаимного расположения точек склеивания и экспериментальных точек. Если точки склеивания расположены равномерно и, кроме того, совпадают с ординатами экспериментальных точек, то кривая имеет достаточно простую форму. Каждая точка задается значениями лишь ненулевых В-сплайнов, которые определяются уравнениями (11.10) или (11.11). В случае квадратичного сплайна уравнения для параметров имеют вид

в случае кубического сплайна

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

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

Теорема 11.2. Задача отыскания интерполяционного сплайна имеет единственное решение в том и только том случае, если

Мы опустим доказательство этой теоремы (см. работу [11.15]) и остановимся лишь на ее интерпретации. На каждом подынтервале между точками склеивания имеется лишь ненулевых В-сплайнов, и, следовательно, чтобы условия теоремы выполнялись, такой подынтервал не может включать больше экспериментальных точек. Это гарантирует против переопределенности системы уравнений (11.20). Известно также, что В-сплайн не равен нулю лишь на подсегменте , следовательно, это единственный подсегмент, который может содержать экспериментальную точку Поскольку число В-сплайнов в уравнении (11.12) равно числу экспериментальных точек возникают дополнительные ограничения. Первый из В-сплайнов является ненулевым только на первом подсегменте и, следовательно, этот подсегмент должен содержать какую-либо экспериментальную точку. То же самое относится к последнему подынтервалу. Если первый подынтервал содержит две экспериментальные точки, второй может вообще не содержать ни одной. В противном случае он должен содержать, по меньшей мере, одну экспериментальную точку и т. д.

Алгоритм 11.1 проверяет выполнение условий теоремы 11.2, задает систему уравнений вида (11.20) и затем решает ее, используя соответствующую библиотечную программу. На шаге 0 в концевых точках вводятся кратные узлы. Это необходимо для того, чтобы на каждом сегменте, содержащем экспериментальную точку, иметь В-сплайнов. Кратность точек можно всегда задавать равной , не прибегая к проверкам. Некоторые из индексов массивов, используемых на шаге 4 алгоритма, могут оказаться отрицательными. Если программа, реализующая данный алгоритм, записывается на таком машинном языке, который не допускает использования отрицательных индексов, то алгоритм можно видоизменить, предусмотрев увеличение значений нижних индексов массива на

Алгоритм 11.1. Интерполирование с помощью В-сплайнов

Обозначения, - множество экспериментальных точек. — множество точек склеивания, — степень сплайна, — вспомогательная переменная. — матрица системы уравнений (11.20):

(см. скан)

(см. скан)

Пример 11.2. Для экспериментальных точек (1 1), (31) (42) и (60) требуется построить интерполяционный сплайн первой степени на сегменте [0,7] с точками склеивания В этом случае обе концевые точки должны быть двойными Нетрудно убедиться в том что интерполяционный сплайн первой степени состоит из прямой, соединяющей точки (31) и (42) (на сегменте прямой, соединяющей точки (1,1) и (20) (на сегменте и прямой, соединяющей точки (53) и (60) (на сегменте [57]) (рис 115) Читателю предлагается формальное обоснование этого результата найти самостоятельно в качестве упражнения (см задачу 11.6)

Рис. 11.5 Линейный интерполяционный сплайн проходящий через четыре экспериментальные точки и имеющий две точки склеивания Взаимное расположение экспериментальных то чек и точек склеивания иллюстрируют утверждение теоремы 11.2.

1
Оглавление
email@scask.ru