Теория полярных форм и полиномиальные сплайны с кратными узлами тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

САНКТ-ПЕТЕРБУРГСКИИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

РГ6 ОД

2 ч НОЙ 1997 На правах рукописи

Сергеев Александр Николаевич

ТЕОРИЯ ПОЛЯРНЫХ ФОРМ И ПОЛИНОМИАЛЬНЫЕ СПЛАЙНЫ С КРАТНЫМИ УЗЛАМИ

01.01.07 — вычислительная математика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Санкт-Петербург 1997 г.

Работа выполнена на кафедре исследования операций

ыатематико-механического факультета Санкт-Петербургского государственного университета

Научный руководитель — доктор физико-математических наук, профессор Малоземов Василий Николаевич

Официальные оппоненты — доктор физико-математических наук, профессор Демьянович Юрий Казимирович,

кандидат физико-математических наук, доцент Певный Александр Борисович

Ведущая организация — Санкт-Петербургский Технологический институт (технический университет)

'«

Защита состоится 1997 г. в N часов

на заседании диссертационного совета Д 063.57.30 по защите диссертаций на соискание ученой степени доктора физико-математических наук в Санкт-Петербургском государственном университете по адресу: 198904, Санкт-Петербург, Петродворец, Библиотечная пл., д. 2, математико-механичсский факультет, ауд. 4526

С диссертацией можно ознакомиться в научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, г. Санкт-Петербург, Университетская наб., 7/9.

Автореферат разослан " " 1997 г.

Ученый секретарь диссертационного совета, доцент

Ю. А. Сушков

Общая характеристика работы

Актуальность темы. Полярная форма введена де Кастельжо Ii Ремшоу в 1985 г. Полярной формой алгебраического полинома

Р(*) = Т,1*С№ (!)

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

= (2) где а*(£i,...,£r) ~ основные симметрические полиномы. Значения полярной формы (2) при конкретных значениях называ-

ются полюсами полинома (1). Полюс р(х,... ,х) называется простым. Очевидно, что р(х,...,х) = Р{х). Алгоритм вычисления значений простых полюсов по полюсам..., fJ+r_i), j — 1,2,..., r+ 1, где <&<...<&• < < Cr+2 < - - ■ < br-, предложил де Кастельжо. Этот алгоритм представляет собой, по существу, метод последовательных линейных интерполяций. Было замечено, что вычислительные формулы алгоритма де Кастельжо идентичны формулам Кокса - де Бора вычисления значений полиномиального сплайна. Тем самым, определилось взаимодействие теории полярных форм и теории полиномиальных сплайнов.

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

Цель работы.

1) Построение аналитических основ теории полярных форм.

2) Развитие теории полярных форм на случай полиномиальных сплайнов со строго упорядоченными (простыми) и повторяющимися (кратными) узлами.

3) Постановка и исследование вопроса о разрешимости задачи сплайн-интерполяцхш по полюсам.

4) Применение теории полярных форм для обоснования понятия характеристического многоугольника полиномиального сплайна и совершенствования алгоритмов геометрического моделирования кривых.

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

Научная новизна. В диссертации получены следующие основные результаты.

1) Доказана однозначная разрешимость задачи интерполяции по полюсам полинома.

2) Получены фундаментальные решения задачи интерполяции по полюсам полинома. В частном случае значений полюсов и расположения узлов интерполяционный по полюсам полином является полиномом Бернштейна.

3) Получен полярный аналог формулы Ньютона для интерполяционного по полюсам полинома.

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

5) Получены необходимые и достаточные условия разрешимости задачи сплайн-интерполяции по полюсам для случаев простых и кратных узлов.

6) Предложен численный метод решения задачи сплайн-интерполяции по простым полюсам.

7) С точки зрения теории полярных форм построен характеристический многоугольник полиномиального сплайна и обоснованы алгоритмы геометрического моделирования кривых.

Практическая ценность. Результаты диссертации могут быть использованы при разработке автоматизированных систем моделирования кривых.

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

Структура и объем работы. Диссертация состоит из введения, трех глав, разбитых на 18 параграфов, и списка литературы. Объем диссертации — 114 страниц. Список литературы насчитывает 37 наименований. В диссертации имеется 10 рисунков.

Содержание работы

Во введении дан краткий исторический обзор и сформулированы основные результаты диссертации.

Глава I посвящена построению аналитических основ теории полярных форм.

В §1-3 приведены важные для дальнейшего технические результаты. В частности, получен полярный аналог формулы Тейлора:

где ш(х) = (х — — £2) • • • (х — &)• Установлена лемма о нулях полярной формы: Пусть Р(х) - полином вида (1) и xq - его корень кратности к. Тогда любой полюс вида р(... ,хр,.. . ...) ра-

(r+1-fc) раз

вен нулю.

В §4 поставлена задача интерполяции по полюсам полинома: найти алгебраический полином Р(х) такой, что

j>(6,...,£+P_i) =yi, г = l,...,r+1, (3)

где 6 <&<■••< Сг < £г+1 < £г+2 < ... < Ьг и у!,...,уг+1 -произвольные фиксированные числа. Доказана однозначная разрешимость задачи (3) при любых правых частях. Установлено, что фундаментальными решениями задачи (3) являются полиномы, значения которых при х £ (£„£4.1) являются значениями нормализованных В-сплайнов

Щх) := -ма - • ■. ,^+р],

где = тах[0, ит]. В частном случае, при 0 = £1 = £2 = • • • = 1 = = £г+2 — ... — (,'2г и У] = /(^г) решением интерполяционной задачи (3) является полином Бернштейна:

Р{*) = ЕЙ / (*т) СГ^-'О- -

В §5 показано, что составная полиномиальная кривая, построенная по полюсам ... ,£,-+г_1), = 1,2,..., г + т + 1, расширенной сеТКИ уЗЛОВ £() < 6 < ' " ' < = а < £г+1 < • • ■ < £г+т < ¡3 = {г+п+1 < ^2г+т+1 есть полиномиальный сплайн =

ЕЙГЧ-ВД-

В §б установлены необходимые для дальнейшего аналитические зависимости между симметрическими полиномами и разделёнными разностями с кратными узлами.

В §7 введены производные полярной формы (2):

= -Л-.). (4)

По определению р^ = аг. Полюсы полярной формы (4) называются производными полюсами полинома Р(х) вида (1). Установлены рекуррентные соотношения для вычисления производных полюсов. Получен полярный аналог формулы Ньютона для интерполяционного по полюсам полинома:

ад = ЕЫ-^&ч ь • • •, Ш - *)%•. • - •, 6].

В частном случае, при 0 = £1 = £2 = • • • = 6-> 1 = £г+1 = £г+2 = ■ • • = Сгг решение интерполяционной задачи (3) принимает вид:

Р(х) = Е1=о^(А4У1)^.

где Д*у1 = Е?=о(—" конечная разность к-то порядка.

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

В §1 для полиномиального сплайна порядка г

ад = ELo С$акхк + Y,T=1 Ч* - ii)V. (5)

простыми узлами ¿,i <&<■■■< (т введена полярная форма юрядка г :

s(ti,...,tr) = ELoak<r*(íь•.■л)+

+E£=l -£,■)+■ (б)

Зслп узлы ii,... ,fr, такие, что интервалы (¿¿, <¿+1), г = 1,2,..., г — 1, ic содержат узлов j = 1,2,...,/н, то значение полярной формы 6) называется полюсом сплайна S(x). Установлена следующая связь к'жду полюсами сплайнов и полюсами составляющих его полиномов: если [ii, ir]n[£;-,£/+i] ф 0, то полюс сплайна s{t,\,... ,tr) есть понос полинома, совпадающего со сплайном S(x) на отрезке f = 1,2,... ,ш — 1. Получен полярный аналог формулы Тейлора для :плайна. Введены производные полюсы сплайна и получены рекур-эентные соотношения для их вычисления.

В §3 вводятся полюсные нули, нуль-интервалы, нуль-интервалы ненулевой индексной длины и их кратности. На основании обобщённой теоремы Ролля для числовых последовательностей, доказанной з §2, получена оценка для числа полюсных нулей и нуль-интервалов : учётом их кратности.

В §4 сформулирована задача сплайн-интерполяции по полюсам: найти сплайн S(x) вида (5), такой, что

= f = 1,2,...,г + т+1, (7)

где г/i,..., уг+т+1 ~ произвольные фиксированные числа, узлы полюсов строго упорядочены по верхнему и нижнему индексам и не содержатся в интервалах (tj^tj^j), /г — 1,2,..., г—1, г = 1,2,... ,г+ т + 1. Получено необходимое и достаточное условие разрешимости задачи (б). Оно имеет вид:

V(j],h) < г+ j2- ii, где V(ji,j2) число полюсов ..., ir'j, i = 1,2,..., г + т + 1, таких, что [^/W] П^ 0.

В §5 предложен численный метод решения задачи сплайн-интерполяции по простым полюсам.

В §6-8 для,полиномиальных сплайнов с кратными узлами получены результаты, аналогичные результатам §1-4.

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

В §1 показано, что характеристический многоугольник графика полинома (1) есть ломаная соединяющая точки

+ ■ • • + Ü+r-i),P&, • • • ,&+r-i)), 3 = 1,2, • • ■,г + 1.

С помощью характеристического многоугольника даётся геометрическая интерпретация алгоритма де Кастельжо, заключающаяся в последовательном применении процедуры деления отрезка в данном отношении. В частном случае, при 0 = = £2 = • • • = 1 = £r+i = £г+2 = ... = £2г по алгоритму де Кастельжо вычисляются координаты точек кривой Везье.

В §2-3 введён характеристический многоугольник полиномиального сплайна и показано, что как полиномиальный сплайн составлен из отрезков полиномов, так и его характеристический многоугольник составлен из характеристических многоугольников этих полиномов. Приведены схема и фрагмент программы разбиения характеристического многоугольника полиномиального сплайна. Доказана важная для геометрического моделирования теорема о том, что в выпуклой оболочке характеристического многоугольника сплайна содержится его разбиение. Устанавлена связь между сплайнами, представленными соответственно в виде разложения по В-сплайнам и по дискретным B-сплайнам с одними и теми же коэффициентами.

Основное содержание диссертации опубликовано в работах:

Сергеев А. Н. Сплайн-интерполяция по полюсам. Деп. в ВИНИТИ от 5 июня 1997г., N. 1817 - В97.

Малоземов В. Н., Сергеев А. Н. Аналитические основы теории полярных форм. Деп. в ВИНИТИ от 21 апреля 1997г., N. 1339 -В97.

Подписано к печати 21.10.97 г. Заказ 076. Тираж 100 экз. Объем 1 п.л. Отдел оперативной полиграфии НИИХ СПбГУ. 198904, Санкт-Петербург, Ст.Петергоф, Университетский пр.2.