Хорошо обусловленные методы построения сплайнов высоких степеней и сходимость процессов интерполяции тема диссертации и автореферата по ВАК РФ 01.01.07, доктор физико-математических наук Волков, Юрий Степанович

• Волков, Юрий Степанович
• доктор физико-математических наук
• 2006

Оглавление диссертации доктор физико-математических наук Волков, Юрий Степанович

Введение.

Глава 1. Ленточные системы уравнений

1.1. Определения и обозначения.

1.2. Оценивание max-нормы обратной матрицы.

1 3. Оценки элементов обратных ленточных матриц.

1.4. Условия нео1рицательности решения чрёхдиагональной сипе-мы уравнений при наличии диа1 онального преобладания по столбцам

1.5. Условия неотрицательности решения системы уравнений с симметрической циркулянтной матрицей.

Глава 2. Системы определяющих уравнений для построения интерполяционных сплайнов

2 1. Б-сплайны и их свойства.

2 2 Линейные соотношения, связывающие значения сплайна и коэффициенты В-снлайн-разложения ею производных

2 3. Системы определяющих уравнений. Периодический случай

2.4. Системы определяющих уравнений. Полный сплайн.

2 5. Соотношения линейной зависимости между разрывами старшей производной и значениями сплайна.

2 0 Вычисление элементов и свойства Maipini, определяющих сппем уравнений

Глава 3 Устойчивые меюды построения сплайнов малых сiспелей

3 1 Кубические сплайны

3 2 Си тайны пяюи степени

Глава 4. Оценки погрешности приближения производных интерполяционных сплайнов и их сходимость

4.1. Оценка ес использованием разложения по /^-нормализованным Б-сплайнам.

4.2. Оценка е^ с использованием разложения s^ но L[-нормализованным Б-сплайнам.

4.3. Оценка погрешности приближения старшей производной

4.4. Решение проблемы де Бора.

4.5. Эквивалентное! ь условий сходимосi и процессов ин1ерполяции для производных степени к н2п — к —

Глава 5. Условия изогеометрической интерполяции

5.1. Монотонность кубических сплайнов.

5.2. Положительность интерполяционных сплайнов.

5.3. Условия fc-монотонности кардинальной интерполяции.

Глава 6. Об шперполяции енлайнами чётной степени

6.1. Задача интерполяции сплайнами четной степени.

6.2. Системы определяющих уравнений

6.3. Оценки погрешностей приближения производных.

6.4. Интерполяция сплайнами четвёртой степени.

Введение диссертации (часть автореферата) на тему «Хорошо обусловленные методы построения сплайнов высоких степеней и сходимость процессов интерполяции»

Рассмотрим задачу интерполяции некоторой функции / по значениям {/,}, известным в некоторых точках отрезка [а, Ь]. Ещё совсем недавно стандартным решением такой задачи выступали интерполяционные многочлены Лагранжа, но теперь наиболее распространённым решением являются полиномиальные сплайны, т. е. кусочно-многочленные функции. Сплайнами принято считать функции, являющиеся на подотрезках отрезка [а, Ь] многочленами обычно одной и чой же пепени, называемой степенью сплайна. Точки сопряжения разных многочленов, составляющих сплайн, называют узлами сплайна. Естественно, сплайны одной и той же степени могут различаться гладкостью или дефектом (разностью между степенью и гладкостью).

Кусочно-многочленные функции появились в теории приближений в разных видах очень давно, в современном виде аппроксимация сплайнами появилась в статье И. Шёнберга [164], но началом бурного развития сплайнов, внедрением в вычислительную математику, пожалуй, можно считать 1957 год, открытие Дж. Холлидеем [135] свойства минимума кривизны.

Теорема 0.1 (Дж. Холлидей). Среди всех функций /, имеющих на отрезке [а, 6] непрерывную вторую производную, и таких, что f(xt) = /,, i = 0,., N, т.е. принимающих заданные значения, кубический сплайн s с узлами в точках х,, для которого s"(a) = s"(b) = 0, минимизирует интеграл

Раньше инженеры и чорхёжники в практической работе для проведения плавных кривых черг i пмоющисч я точки чн< то использовали i ибкую рейку н иол\чали превосходные результаты, чет не вшда можно бы ю добпгыя in по п> я шперио шито чпоюч тепами и ш лекала Ока илплеи я hsoiiivь

1) it хая рейка в первом приближении представляет кубический сплайн с узлами в точках изгиба, вторая производного которою есть аналог кривизны. Открытое Дж. Холлидеем свойство послужило объяснением прекрасного профиля и вогнутой рейки.

Если в (1) вместо второй производной использовать производную порядка п, ь f/(,°(®) (2) то функцией, минимизирующей интеграл в классе W'2'[a,b], снова будет кусочно-многочленная функция, а именно сплайн s степени 2п — 1 класса С2"~2[а,Ь] (дефекта 1) опять с узлами в точках интерполяции (см. [179], [96], [102]). Такое свойство сплайна степени 2п - 1 называют свойством минимальной нормы [1].

Сплайн s, минимизирующий (2), принято называть «натуральным», он характеризуется тем, что на концах отрезка [a, b] его старшие производные обращаются в 0, а именно

0, и — п,. ,2п — 2. (3)

Можно при минимизации потребовать чтобы вместе с интерполяцией функции / в узлах сетки осуществлялась ещё интерполяция производных, вновь решением будет сплайн, но, вообще говоря, уже большего дефекта. Также классическим, но более распространённым в приложениях по сравнению с натуральным сплайном, является сплайн ь, который помимо функции интерполирует лишь по п — 1 производных на концах отрезка [«,/;]: ГН'О, *И(Ь) = /И(Ь), * = 1, • • •, П - 1. (I)

Такои сплайн называется «полным», дефект у нею также минимален (дефекта 1) Именно сплайны минимальною дефекы преде твлнюг наибольший интерес

Одно из направлений развития и обобщения теории сплайнов, называемое вариационной или абстрактной теорией сплайнов, связано с определением сплайнов, как решений некоторых вариационных задач о минимуме функционала (см. [8], [51], [66], [68], [81], [82], [99], [129]).

Сплайны естественным образом возникают и во многих других задачах теории приближения, например, оптимальное восстановление операторов, оптимальные квадратуры, поперечники классов функций (см. [38], [63], [64], [90], [167]).

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

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

2) Сплайны - аппарат более удобный, чем многочлены с вычислительной или — скажем шире — с практической точки зрения. Если говорить о сплайнах минимального дефекта по фиксированному разбиению, обладающих наилучшими аппроксимативными свойствами, то практические удобства связаны с наличием в нодпространсгве таких сплайнов базиса из Б-сплайнов с конечным носителем. Именно эго обстоя юльство обусловливает локальную гибкоеп> интерполяционного сплайна, выражающуюся, в частности, — в отличие от ншериоляционно1 о многочлена — в малой чув-с1вигельности к по1решностя\! в исходных данных, небольшое изменение значении функции водно!"! или нескольких соседних iочках интерполяции ма ю сказывается па поведение шперпо шцноиною сп мина на некоюром удалении от этих точек. С этим же связан и тот факт, что интерполяционный сплайн, хорошо приближая функцию, одновременно хорошо приближает и её производную" [63].

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

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

Основным объектом данной диссертации являются интерполяционные сплайны. Именно классические интерполяционные полиномиальные сплайны нечётной степени минимального дефекта, у которых узлы совпадают с Iочками интерполяции. (Мы затронем и интерполяционные сплайны четной степени, но они но своим свойствам существенно отличаются от сплайнов нечётной степени). Нас в первую очередь интересуют два основных вопроса: методы построения интерполяционных сплайнов и изучение сходимости процессов интерполяции для всех производных.

Пусть сетка Д является разбиением отрезка [а, Ь]:

Д : а = Х|) < х\ < . <х\ =Ь

Символом 3, (Д) или S, будем обозначать множество всех полиномиальных сплайнов на oiрезке [а,/>] порядка г (или степени г - 1) минимальною дефекта с у иами на сетке Д, т е (Д) =С, = {(Т€С -JM : (т\ ; .А-1}, где через Р, обозначено множество всех многочленов степени г — I. Считаем, что в узлах сетки А заданы значения /, некоторой функции /: h = f{x,), г = 0,., iV.

Мы рассматриваем задачу построения сплайна s € §2и(Д), интерполирующего заданные значения. Для однозначного определения сплайна нечётной степени 2п — 1 при п ^ 2 необходимы дополнительные условия. Обычно дополнительные условия задают на краях отрезка \а,Ь].

Можно, конечно, не задавать никаких условий, а в качестве единственного сплайна брать натуральный сплайн, который минимизирует интеграл (2). Такой сплайн удовлетворяет условиям (3), которые называют «естественными» краевыми условиями. Однако вопреки своему названию натуральный сплайн, т.е. сплайн с естественными краевыми условиями, не очень естественен для приложений и мало пригоден для практического применения. Это связано с тем, что естественные краевые условия, как правило, не согласуются с решаемой задачей. Если производные интерполируемой функции порядка I = тг,., 2п — 2 далеки от нуля на концах отрезка [a, b], то качество приближения натуральным сплайном вблизи концов будет плохим. Но правильный выбор краевых условий, как правило, даёт замечательные результаты.

На практике существует много рецептов какие краевые условия следует использовать в зависимости от известной дополнительной информации о функции /. Наилучшие результаты достшаются при использовании на концах 01 резка [а,/>] значений младших тг — 1 производных, если они швест-ны. Как уже ошечалось, это будет полный сплайн, т е ишерполяциоинып сплайн с краевыми условиями (4)

Распространен еще один тип краевых условий — псриодиче(кие. Они используются в том случае, если ингерпо шруемая функция / явшоия (/; — <г)-иерш>дпчс( коп Тогда шперпо шпионныи сп iann ь (чиыом юле b - а)-исриодичсским.

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

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

Наиболее понятный и очевидный метод построения интерполяционного сплайна в базисе из степенных и усеченных степенных функций приводит к системе уравнений с сильно заполненной матрицей. К тому же эта матрица оказывается очень плохо обусловленной даже в случае равномерной ceiKH. Поэтому nociроение интерполяционного сплайна в базисе из усеченных степенных функций оказалось не приемлемым с практической точки зрения.

Гораздо более удачным оказалось представление сплайна через узловые значения какой-либо из его производных. Получаемые системы уравнений имеют ленточную структуру. А для кубического сплайна системы относительно наклонов сплайна (первых производных) в узлах и моментов (вторых производных), являясь трехдпагональнымп, имеют кроме того еще диагональное преобладание Указанные свойства систем }равнений позволяют использовать очень эффективный и падежный метод решения метод пршонки (см [1|, [5], [б], [12|, |81|, [82], |87|)

Привлекателен выбор в качестве оиреде ииощнч параметров пилина коэффициентов его разложения но базису из нормализованных Я-сплайнов. В-сплайны имеют конечный носитель, и существует устойчивый мегод вычисления этих базисных функций произвольной степени, основанный на рекуррентном соотношении Хотя Б-сплайновая коллока-ционная матрица является вполне неотрицательной ленточной матрицей, и при решении системы уравнений с этой матрицей методом Гаусса отпадает необходимость осуществлять выбор главного элемента для проведения исключения [119], тем не менее этот метод построения имеет ограниченное применение. Его можно с уверенностью использовать только на сетках, близких к равномерным, или специальной структуры, в противном случае обусловленность системы уравнений данного метода может стать сколь угодно плохой [42]. (Под величиной обусловленности мы понимаем произведение равномерных или таж-норм матрицы и её обратной). Заметим, что величина обусловленности не всегда полностью характеризует матрицу в таком вопросе как решение системы линейных уравнений, но относительно малое её значение является гарантией хорошей точности численного решения системы [2]. Конечно, в отдельных случаях система уравнений может устойчиво решаться и при плохой обусловленности, но в данном случае в [108] показано, что при интерполяции кубическим сплайном данных вида /г = 8i,k (фундаментальный сплайн) на сильно неравномерных сетках при значительном удалении от узла сетки ха. возможен neoi раиичениый рост осцилляций сплайна и, следовательно, Б-сплайн-коэффициентов и элементов обратной матрицы. Здесь плохая обусловленность и накопление ошибок округления при решении системы тесно взаимосвязаны.

Если для кубических сплайнов вопрос выбора параметров представления уже достаточно хорошо проработан, выделены устойчивые, хорошо обусловленные методы построения, то для сплайнов более высокой степени нет такой полной определенное ш Казалось бы надо выбрать параметрами представления си тина шачения к у 5.i<i\ ссчки одной in пропшолныч снлайна, но получение соответствующих систем уравнений является довольно непростой задачей. В литературе известна только одна такая система — относительно моментов (относительно (2п — 2)-й производной, если степень сплайна равна 2п — 1), полученная Дж. Албергом, Э.Нильсоном и Дж.Уолшем [1]. Но уже для сплайнов пятой степени и выше матрица этой системы не только не имеет диагонального преобладания в общем случае, но и может быть сколь угодно плохо обусловленной при существенно неравномерном размещении исходных данных [10]. Система относительно моментов не получила распространения в силу её громоздкости и плохой обусловленности. Пожалуй единственный способ нахождения сплайнов произвольной степени, который получил распространение, это метод вычисления сплайнов через разложение по В-силайнам. Достоинство этого метода связано с вычислительной простотой определения элементов системы уравнений, основанной на устойчивом рекуррентном соотношении для В-сплайнов.

Однако метод вычисления интерполяционного сплайна через В-сплай-ны нельзя считать лучшим из возможных. Например, в кубическом случае предпоч!тельной альтернативой выступают алгоритмы вычисления сплайна через наклоны или моменты, обусловленность матриц которых на любой неравномерной сетке не превосходит 3. Несмотря на то, что для сплайнов произвольной степени В-сплайновая коллокационпая матрица является ленточной и вполне неотрицательной, для неё, как и в кубическом случае, обусловленность может быть сколь угодно плохой [18].

Можно упомянуть ещё про некоторые способы решения задачи интерполяции для сплайнов произвольной степени [98], [84], однако какой-либо анализ устойчивости вычисления параметров сплайнов при згом отсутствует. Таким образом, задача поиска хорошо обусловленных способов построения интерполяционных сплайнов высоких (тененей нредс гавляется достаточно акту а шнои и вое требованной

Второй вопрос, который мы изучаем в диссертационной работе, это исследование сходимости процессов интерполяции. Впервые вопрос о сходимости процессов интерполяции для сплайнов и их производных при минимальных требованиях гладкости интерполируемой функции был поставлен И. Шёнбергом, которого считают отцом сплайнов, в 1963 году на конференции в Обервольфахе (ФРГ) [157, р. 189].

Задача состоит в следующем. Рассмотрим последовательность сплайнов {л} степени 2п — 1, интерполирующих некоторую функцию / на иоследо-ва1ельнос1И сеюк {Д} таких, что h = max (агг+1 — хг) —» 0 при N —► со.

Будет ли иметь место сходимость s^ к для произвольной функции / € Ск[а, Ъ] (0 ^ к ^ 2п - 1) ? Если сходимости в общем случае нет, то каким ограничениям должна удовлетворять последовательность сеток {А}, чтобы сходимость имела место? Мы будем говорить только про сходимость в равномерной метрике.

Для последовательности сеток с равномерным распределением узлов сходимость для любой производной есть всегда [1], [87], здесь актуален вопрос отыскания точных констант (см. [63]). Для произвольных сеток вопрос значительно сложнее. По началу большинство усилий было направлено на кубические сплайны. Было установлено, что для кубических сплайнов сходимость без каких-либо ограничений на сетки имеет место при к — 1 или к = 2 [171]. А изучение сходимости самих сплайнов в С[а,Ь] и третьих производных в C^aJi] растянулось ещё на десяток лет.

В 1966 году А. Шарма и А. Меир [171] установили, чю если на последовательность сеток {Д} наложено ограничение

Яд ^ II < оо, где h

Ra = max — кс/v-i h, глобальная характеристика сети, то сходимость сплайнов имеет место для любой непрерывной функции /. А в 1967 г. С. Нордом [156] был построен пример расходящегося процесса на последовательности сеток, для которой условие (5) нарушено. С. Б. Стечкин и Ю. Н. Субботин [86] усилили пример С Норда, они пытались определить максимально широкий класс функций, для которых соответствующая последовательность интерполяционных сплайнов безусловно сходилась бы к ним. В результате их рабог [86], [87], и работы Ал. А. Привалова было установлено, что необходимым и достаточным условием является принадлежность функций классу Lip 1.

Э. Чеиьи и Ф. Шурер [120] показали, что условие (5) не является необходимым для сходимости в С[а,Ь]. В их примере последовательности сеток Яд —> оо, но сходимость имеет место для любой интерполируемой непрерывной функции. Они предложили изучать сходимость процессов интерполяции при ограничениях на локальные характеристики сеток h

Ра = max —^ ^ р < оо. (6) l«-j|=i hj

Исследованию сходимости процесса интерполяции в терминах локальных характеристик сеток был посвящён ряд работ. Вначале А. Меир и А. Шарма [152] показали сходимость кубических сплайнов на любой иоследова!ельно-сти сеток, удовлетворяющей ограничению (6), если р < у/2. Затем Э. Ченьи и Ф. Шурер [121] получили некоюрое улучшение р < 2. В этом же юду (1970) Ю С.Завьялов [39] еще усилил результат сходимости р < 1 + у/2, и этот же результат был повторён в 1973 г. Ч.Холлом [133]. Дальнейшее улучшение установил М Марсден [149], он показал, чю в классе С[а,Ь] всегда ecib сходимость при выполнении условия (6) с р ~ 2.439, а при р > р*, где

3 + у/В р = -2-2!— ~ 2 G18. привел пример последовательности сеток, где процесс может расходиться (последовательность норм соответствующих операторов интерполяции расходится). Во всех этих работах рассматривались кубические сплайны с периодическими краевыми условиями, а Т.Лич и Л.Шумейкер [147] повторили большинство из приведённых результатов и для других краевых условий.

Как пишет Ю. Н. Субботин [90], после знакомства с работой Ю. С. Завьялова [39] у него возникла идея как усилить метод доказательства Ю.С.Завьялова, и вскоре эта идея была блестяще реализована его учеником Н. Л. Зматраковым [43]. Он показал, что если р < р* и последовательность сеток удовлетворяет условию (6), то последовательность интерполяционных кубических сплайнов равномерно сходится к интерполируемой непрерывной периодической функции. Н. Л. Зматраков построил достаточно тонкие и сложные примеры, показывающие, что если р ^ р*, то существует непрерывная периодическая функция и последовательность сеток, удовлетворяющая (6), такие, что соответствующая последовательность интерполяционных кубических сплайнов расходится хотя бы в одной точке. Независимо от Н. Л. Зматракова окончательный результат о сходимости при р < р* повторил К. де Бор [108]. Более простыми способами, чем у Н. Л. Зматракова, эти же результаты о сходимости и расходимости получил В. Л. Мирошниченко [71], [42], причём не только для периодических краевых условий.

Исследование сходимости s'" к /"' в классе С![а,6] в терминах локальной характеристики сеток также изучалось А. Шармой и А. Меиром [171], Ю С.Завьяловым [39], но окончательное решение опять-таки было получено II. Л.Зматраковым [15]. Причем ограничения на последовательность сеюк оказались такими же, как и для сходимости самих сплайнов в С[а, Ь], л именно' при р < р* имеет место сходимость, а при р ^ р* есть <ei-ки, на коюрых процесс б}дет рлсхоцпься. Отметим, чю в да шнеГпием

Н. Л. Зматраков продолжил изучение сходимости и сплайнов, и третьих производных в метрике L{> (см. [44], [40], [47], [180]). Упомянем еще об одной характеристике сеток h< рА,т = max —, т ^ 1, i-j|=m rij обобщающей локальную сеточную характеристику. Изучение сходимости интерполяционных процессов для кубических сплайнов в терминах /?д)Ш рассматривалось в работах [43], [48], [138].

Для интерполяционных сплайнов более высоких степеней, чем кубические, результатов не так много и, особенно, окончательных. Первый результат, который можно считать окончательным, это результат К. де Бора [104] о сходимости третьих производных сплайнов пятой степени в классе СЯ[а, Ь] без каких-либо ограничений на последовательность сеток (небольшая погрешность доказательства была исправлена им в работе [115] и там же указано, что сходятся и четвёртые производные сплайнов седьмой степени в С1[а,Ь], указан путь доказательства, но сами вычисления не приведены). Позднее (1973) К.де Бор предположил, что и в общем случае сплайнов s степени 2п - 1, интерполирующих функцию / € Сп[а,Ь], имеет место безусловная равномерная сходимость sМ к /М. Эквивалентная формулировка этого предположения более известна как знаменитая гипотеза К.де Бора [105], за которую был объявлен денежный приз, об ограниченное! и нормы операторов наилучшего среднеквадратичною приближения сплайнами степени п — 1 как операторов из С[а, Ь] в С[а,Ь] константой, зависящей только oi п, но не от сетки.

В 1975 году К.де Бор [107] показал, чю сходимость ь1-^ к /"\ если ишерполируемая функция / класса С1 [а,Ь], бе? ограничении на сетки при к = (),. ,п — 2 невозможна, дополнительно он сказал, чю и при к = п + . ,2п - 1 безусловная сходимость ткже невозможна, но доказан» ibcnm ною факы не приве i, а сообщи i, что оно б\дсч он}б шковлно где-либо еще (об этом доказательстве в более поздних работах К.де Бора нам ничего не известно). В этой же работе было высказано дополнительное предположение о безусловной сходимости s*"-1) к в классе C"~l[a, b]. Нами [10] в 1984 г. были найдены такие числа рЦ\ к = 0, .,тг - 2 и к = п + 1,.,2п-1, и при любых р > приведены последовательности сеток, удовлетворяющие условию (6), на которых интерполяционные процессы расходятся для соответствующих к, если / G C/l [а, Ь\.

Сходимость процессов интерполяции в общем случае была доказана только для n-й производной при ограничениях (5) опять же К.де Бором [109]. Им же при этих же ограничениях установлена и сходимость самих сплайнов [110], а Ю.Н.Субботиным [89] — сходимость s^ к /М для функций / из Ск[а,Ь], 0 ^ к ^ 2п — 1, также при ограниченности глобальных характеристик последовательности сеток Некоторые неокончательные результаты о сходимости при ограничениях на соседние шаги сеток (локальные характеристики) получены только для к = ОС. Фридлендом и Ч. Мичелли [130] с привлечением специально разработанной и достаточно сложной техники теории осцилляционных матриц. Нам удалось эти условия перенести на случай к = 2п - 1 [11]. Небольшое улучшение условий С. Фридленда и Ч. Мичелли для сплайнов пятой степени, а также некоторые условия на сходимость первых и вторых производных, были получены А.Ю.Шадриным [94], [168].

И, наконец, отметим, чго в 2001 году А.Ю.Шадрин [170] решил знаменитую проблему К.де Бора, установил безусловную сходимость к для функций / из С"[а,Ь]. Укажем ряд работ, в которых разбирались частые случаи шпотеш К.де Бора [136], [128], [154], [139].

Приведенный здесь краткий обзор результаюв по обозначенным pam е вопросам — методы построения интерполяционных сплайнов и сходимость инюрполяционною процесса при минимальных 1р(бованиях гладкости ин-герпо шр\омой ф\нкции не прпендич на iiomoiy, а офажает лишь интерес автора к затронутым вопросам. Имеется много работ но изучению сходимости производных интерполяционных сплайнов при повышенной гладкости интерполируемой функции, в частности, если / G Сп[а,Ь], то и сплайны, и п производных сходятся без каких-либо ограничений на сетки (см., например, [1], [87]). За рамками обзора остались вопросы сходимости в других метриках, а также вопросы построения и сходимости интерполяционных сплайнов более высокого дефекта.

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

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

Заключение диссертации по теме «Вычислительная математика», Волков, Юрий Степанович

Заключение

Сформулируем основные результаты диссертации.

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

2). Обнаружена связь обусловленности возникающих в нредлахаемом подходе систем с вопросами сходимости процессов интерполяции. Положительно решена гипотеза К. де Бора (1975) о безусловной сходимости ещё одной средней производной сплайнов при минимальных требованиях гладкости интерполируемой функции. Установлена симметрия условий сходимости процессов интерполяции для младших и старших производных.

3). Новый подход к получению систем определяющих уравнений и раз-рабоынный аппарат исследования свойств сходимости с успехом перенесён на случай сплайнов чётной степени. Впервые была установлена связь условий сходимости процессов интерполяции двух наиболее распространённых конструкций сплайнов чётной степени по Марсдену и по Суббошну. Для сплайнов четвёртой степени по Субботину обнаружена система уравнений с диагональным преобладанием для нахождения определяющих параметров, тем самым найден хорошо обусловленный способ построения инюрполя-цнонных сплайнов четвертой степени Как следствие, для таких сплайнов установлена равномерная сходимость ь'" к /"' для любой интерполируемо!! функции / 6 6'![«,6] и любой последовательности ссток. А для сплайнов четверти < гепенн по Марсдену по чаем сходимость ь' к /' для любой / 6 C,l[f/,/>] и ыкже любой после шва!елыюс ти с сток

Список литературы диссертационного исследования доктор физико-математических наук Волков, Юрий Степанович, 2006 год

1. Алберг Дж., Нильсон Э., Уолш Дж Теория сплайнов и её приложения. - М. Мир, 1972. - 316 с.

2. Бабенко К. И. Основы численною анализа. — М.: Наука, 1986 — 744 с.3. блатов И. А. Об оценках элементов обратных матриц и о модификации метода матричной прогонки // Сиб. матем. журн. — 1992. — Т. 33, № 2 С. 10-21.

3. ВОЛКОВ 10 С Расчодимос ib интерполяционных сплайнов нечем ной (ichchh // Вычислительные системы. Новосибирск: ИМ СО АН СССР, 1951. - Выи 106: Прпб жжение сплайнами С. 11-)G

4. ВОЛКОВ Ю.С. Равномерная сходимость производных интерполяционных сплайнов нечётной степени. — Новосибирск, 1984. — 11 с. — (Препринт № 62 / ЛН СССР. Сиб. отд-ние. Ин-т математики)

5. ВОЛКОВ Ю. С. Об осцилляционных матрицах в задачах сплайн-интерполяции // Сибирский матем. журн. — 1987. — Т. 28, JV0 3 — С. 5153.

6. ВОЛКОВ Ю.С. О погрешности вычисления интерполяционных сплайнов нечетных степеней на неравномерных сетках // Всесоюз. симпоз по теории приближения функций: Тез. докл. — Уфа, 1987. — С. 38-39.

7. ВОЛКОВ Ю. С. О расходимости интерполяционных сплайнов и их производных // Междунар. конф. по конструктивной теории функций: Тез. докл. София, 1987. - С. 101.

8. ВОЛКОВ Ю.С. Анализ алюритмов построения интерполяционных сплайнов нечетной степени // Актуальные проблемы вычислительной и прикладной математики: Тез. докл. / Всесоюз. конф. — Новосибирск, 1987. С. 48-49.

9. ВОЛКОВ Ю. С. Исследование сходимости интерполяционных процессов для сплайнов нечетных степеней // Дис. .канд физ.-мат. наук. Ин-т математики СО РАН СССР. Новосибирск, 1988 - 85 с.

10. ВОЛКОВ Ю. С. О сходимости интерполяционных сплайнов в терминах локальной сеточной характеристики // Вычислительные системы. Новосибирск- ИМ СО АН СССР, 1988. Вып. 128 Аппроксимация сплайнами С 32 38

11. ВОЛКОВ 10 С Оценки числа обусловленное in /i-силапновоп колло-кационной Мсирицы /, Вычислительные системы. — Новосибирск. ИМ СО РАН, 1992. — Выи. 1 ГГ Интерполяция и аппроксимация сплайнами -С 3-10.

12. ВОЛКОВ Ю С. О построении интерполяционных полиномиальных сплайнов // Вычислительные системы. — Новосибирск: ИМ СО РАН, 1997. — Выи. 159. Сплайн-функции и их приложения. — С. 3-18.

13. ВОЛКОВ Ю С. Наилучшая оценка погрешности производной при интерполяции сплайном четверюй степени // Матем. труды. — 1998 — Т. 1, JY° 2. — С. 68-78.

14. ВОЛКОВ Ю. С. Монотонность и выпуклость кардинальной сплайн-интерполяции // Понтрягинские чтения-IX: Тез. докл. / Воронежская зимн. матем. шк. — Воронеж: ВГУ, 1998. — С. 47.

15. ВОЛКОВ Ю. С. О положительности полиномиальных сплайнов при интерполяции положительных данных // Теория приближения функций и операторов: Тез. докл. / Междунар. конф. — Екатеринбург, 2000. С. 53-54.

16. ВОЛКОВ Ю. С. О неотрицательном решении системы уравнений с симметрической циркулянтной матрицей построении // Матем. заметки. 2001. - Т. 70, вып. 2. - С. 170-180

17. ВОЛКОВ Ю. С. О монотонной интерполяции кубическими сплайнами // Вычисл. технологии. 2001. - Т. 6, 6. - С. 14-21.

18. ВОЛКОВ Ю. С. Некоюрые свойства интерполяционных сплайнов нечетной степени , Me I оды сплаин-функций' Тем докл. / Сиб конф. ноевящ иамяш Ю С.Завьялова (1931 1998) — Новосибирск: тд-ьо ИМ СО РАН, 2001 С. 19 20

19. ВОЛКОВ 10 С Новый способ построения ингерпо шцпонных к\би-че< кп\ си iamioB ЛАН. 2002. Т .N2, Y'2 <' '") 157

20. ВОЛКОГЗ Ю. С. Об оценке элементов матрицы, обратной к циклической ленточной матрице // Сиб жури, вычисл. магем. — 2003. — Т. G, № 3. С. 2G3-267.

21. ВОЛКОВ Ю. С. Безусловная сходимость ещё одной средней производной для интерполяционных сплайнов нечетной степени // ДАН. —2005. Т. 401, Лг° 5. - С. 592-594.

22. ВОЛКОВ Ю. С. Условия ограниченности операторов сплайн-интерполяции. Новосибирск, 2006. - 18 с. - (Препринт № 167 / РАН. Сиб. отд-нпе. Ин-г математики им. С. Л. Соболева).

23. Волков Ю.С. Две конструкции интерполяционных сплайнов чётной степени — Новосибирск, 2006. 32 с. — (Препринт .V' 169 , РАН. Сиб. отд-ние. Пн-г математики им. С. Л. Соболева).

24. Гантмахер ф. Р , КРЕЙН М Г. Осцилляцнонные матрицы и ядра и малые ко юбанпя механических сис тем. — М -Л Госючиздат, 1950. — 359 с37 гребенников А. И. Метод сплайнов н решение некорректных задач теории приближений. — М.: Изд-во МГУ, 1983. — 208 с.

25. ЖЕНСЫКБАЕВ А А Проблемы восстановления операторов. -Москва-Ижевск: Институт компьютерных исследований, 2003. — 412 с.

26. ЗАВЬЯЛОВ Ю.С. Интерполяция кубическими многозвенниками // Вычислительные системы. — Новосибирск: ИМ СО АН СССР, 1970. Вып. 38. - С. 23-73.

27. ЗАВЬЯЛОВ Ю. С. Монотонная интерполяция обобщенными кубическими сплайнами класса С2 // Вычислительные системы. — Новосибирск: ИМ СО РАН, 1992. — Вып. 147: Интерполяция и аппроксимация сплайнами. — С. 44-67.

28. ЗАВЬЯЛОВ Ю.С. О неотрицательном решении системы уравнений с несгрою якобиевой матрицей // Сиб. мат. журн. — 1996. — Т. 37, № 6. С. 1303-1307.

29. ЗМАТРАКОВ И.Л Равномерная сходимость третьих производных интерполяционных кубических сплайнов /, Вычисли тельные системы. Новосибирск ИМ СО АН СССР, 1977. Вып. 72. Методы <н iaiin-фу нкции. - С 10-29

30. ЗМЛТРАКОВ H JI. Сходимость третьих производных интерполяционных кубических сплайнов в Ly, метриках // Матем заметки — 1981 Т. 30, № 1. — С. 83-99.

31. ИЛЬИН В. П. Методы неполной факторизации для решения алгебраических систем. — М.: Наука, 1995. — 288 с.

32. Ильин В. П., Кодачигова Л. К., Пинкина Н А. Анализ устойчивое hi метда циклической редукции Новосибирск, 198825 {. — (Препршн X' 801 АН СССР. Сиб. огд-ние. Вычиелинчь-ный центр).

33. Ильин В П , Кузнецов 10. И. Трёх Uiaiопальные млфицы и их при юления. М На\ка, HRl. 203 с

34. КАЛИТКИН Н.И., Шляхов Н.М. tf-сплайны высоких степеней // Матем. моделирование. 1999. - Т. 11, № 11. - С. 64-74.

35. КАЛИТКИН Н.Н., Шляхов II. М. Интерполяция Я-еилайнами // Матем. моделирование. 2002. - Т. 14, № 4 - С. 109-120.

36. КВАСОВ Б И. Применение параболических В-силайнов для решения задачи интерполяции // Жури, вычиел. матем. и маг. физики. -1983. Т. 23, № 2. - С. 278-289.

37. КИВВА С. Л., СТЕЛЯ О. Б. Об одном параболическом сплайне // Вычиел. технологии. 2001. - Т. 6, № 3. - С. 21 31.

38. КИНДАЛЕВ Б. С. Асимптотика погрешности и сунерсходимость периодических интерполяционных сплайнов чётной степени // Вычисли гельные системы. — Новосибирск: ИМ СО АН СССР, 1986. — Вып. 115: Сплайны в вычислительной математике. — С. 3-25.

39. КИНДАЛЕВ Б. С. Точная оценка нормы обратной матрицы для симметрическою циркулянта // Вычислительные системы. — Новосибирск: ИМ СО АН СССР, 1987. — Вып. 121: Аппроксимация сплайнами. — С. 37-45.

40. КИРУШЕВ В. А., МАЛОЗЕМОВ В. Н. Интерполяция положительных данных при помощи неотрицательных натуральных кубических сплайнов // Вестник СПбГУ. Сер. 1. 1995 - Выи. 2 (Х°8). - С. 2530.

41. КИРУШЕВ В. А., МАЛОЗЕМОВ В. Н. Об одном алгорише построения неотрицательного кубическою сплайна // Журн. вычиел. мат. и матем. физики 1997 - Т. 37, .V 4. - С. 387-391.

42. КОРНЕЙЧУК Н.П. Сплайны в теории приближении. М/ Наука, 1984 - 352 с.

43. Корнейчук Н.П., Баненко В.Ф, Лигун Л. А '-Экстремальные свойства ио шномов и си типов. Киев Нлукова думка, 1992 301 с65 лигун А. А., шумейко А. А. Асимптотические методы восстановления кривых — Киев Изд-во Института математики НАН Украины, 1997. 358 с.

44. ЛОРАН П.-Ж. Аппроксимация и оптимизация. — М. Мир, 1975. — 496 с.

45. РОЖЕНКО А. И. Абстрактная теория сплайнов. Учеб. пособие. — Новосибирск: Изд центр НГУ, 1999. 176 с.82 роженко А. П. Теория и алюригмы вариационной силаин-апироксимацпи. — Новосибирск: Изд. ИВМпМГ СО РАН, 2005. -244 с.

46. РОЖЕНКО А И О расчете скалярных произведении Z?-ch.ihiihob Сиб. жури вычисл матем 2006 Т 9, .V 1 С 55 01

47. СМЕЛОВ В. В. Простой унифицированный метод реализации обобщенных сплайнов с использованием алгоритма матричной прогонки // Сиб. матем. журнал. 1995. - Т. 36, № 3. - С. 650-658.

48. Справочник по специальным функциям. Под ред. М. Абрамовица, И. Стигана. М : Наука, 1979.86. стечкин с. Б. субботин Ю. Н. Добавления // Теория сплайнов и её приложения / Дж.Алберг, Э Нильсон, Дж.Уолш. — М/ Мир, 1972. с. 270-309.

49. СТЕЧКИН С. Б. СУББОТИН Ю. Н. Сплайны в вычислительной математике. — М.: Наука, 1976. — 248 с.

50. Субботин Ю. Н. О кусочно полиномиальной интерполяции // Матем. заметки. 1967. - Т. 1, № 1. - С. 63 70.

51. ШАДРИН Л. Ю. О проблеме К де Бора для мноюмерных D'" сплайнов // Тр. мат. ин-та им. В.А.Сгеклова / РАН. 1997. - Т. 219. Теория приближения и гармонический анализ. — С. 420-452.

52. Ahlberg Л. н., Nilson е. N., walsh Л. l. Best approximation and convergence properties of higher-order spline approximations // Л. Math, and Mech. 1965. - V. 14, n. 2. - P. 231-243.

53. Bezhaev A. YU., Vasilenko V. A. Variational spline theory // Bulletin of the Novosibirsk Computing Center. — Novosibirsk: NCC Pab-lisher, 1993. — Ser.: Numerical Analysis, Special Issue: 3. — 259 p.

54. DE BOOR C. On uniform approximation by splines // Л. Approxim Theory. 1968 - V 1, ii. 2. - P. 219-235.

55. DE BOOR C. On the convergence of odd-degree spline interpolation / Л. Approxim Theory. 1968. - V. 1, n. 1. - P. 452-463.

56. DE BOOR C. The qnabi-interpolant as a tool in elementaiy polynomial spline theory Approxim Theory: Proc couf, Austin, 1973 — New Voik Academic Pre-*, 1973 P 209 270.

57. DE BOOR С. Bounding the error in bphrie interpolation // SIAM Review. 1974 - V. 16, n. 4. - P. 531-544.

58. DE B()()R C. On bounding bphne interpolation // J Approxim. Theory. — 1975. V. 14, n 3. - P. 191-203.

59. DE BOOR С On cubic spline functions that vanish at all knots // Adv. math. -- 1976. V. 20, n. 1 - P. 1 -17

60. DE BOOR C. A bound on the L^-norm of Lj-approxunation by splines in terms of a global mesh ratio // Math. Comput. — 1976. — V. 30, n 136 P. 765-771.

61. DE BOOR C. Total positivity of the spline collocation matrix // Indiana Univ. J. Math. 1976 - V. 28, n 6. - P. 541-551.

62. DE BOOR C. On local linear functionals which vanish at all B-splines but one // Theory of approximation with application: Proc. / Conf., Calgary, 1975 / Eds A.G.Law, B.N.Sahney. New York: Academic Press, 1976. - P. 120-145.

63. DE BOOR C. Quadratic spline interpolation and the sharpness of Lebchgue'b inequality // .1. Approxim. Theory. 1976 V. 17, и 41. P. 318-358

64. DE BOOR C. On a шах-norm bound for the least-squares spline ap-proxnnant '7 Approximation and function bpaies: Proc / Intern <onf., Gdansk, 1979 Amsterdam-New York. North-Holland, 1981. - P 163175

65. DE BOOR С. The exact condition of the /З-spIme basis may be hard to determine // J. Approxim. Theory. 1990. - V. 60, n. 3. - P. 344-359.

66. Cheney E. W., Schurer F. Convergence of cubic spline interpolates // J. Approxim. Theory. 1970. - V. 3, n. 1. - P. 114-116.

67. DEMKO S. Inverses of band matrices and local convergence of spline projections // SIAM J. Numer. Anal. 1977. - V. 14, n. 4. - P. 616619.

68. DeMKO S. Interpolation by quadratic splines // J. Approxim. Theory. — 1978. V. 23, n. 4. - P. 392-400.

69. HALL C. A. Uniform convergence of cubic spline interpolants // J. Approxim. Theory. 1973. - V. 7, n. 1. - P. 71-75.

70. JlA R.-Q. On a conjecture of C. A. Micchelli concerning cubic spline mtei-polation at a bimfmite knot sequence J. Approxim Theory — 1983. -V 3*5, n 3. P 281 291

71. JlA R.-Q. L^-boundedness of /"^-projections on splines for a multiple geometric mesh // Math. Comput. 1987 - V. 48, n. 178 - R 675690.

72. Kammerer W.J., Reddien G.W., Varga R.S. Quadratic interpolator splines // Numerische Mathematik. — 1974. — V. 22, n 2. — P. 241-259.

73. KARLIN S. Total positivity. Vol. 1. Stanford: Stanford University Press, 1968. - 576 p.

74. KERSHAW D. Inequalities on the elements of the inverse of the certain tridiagonal matrix // Math. Comput. 1970. - V. 24, n. 109. - P. 155158.

75. KERSHAW D. A bound on the inverse of a band matrix which occurs in interpolation by periodic odd order splines // J. Inst. Math. Appl. — 1977. V. 20, n. 2. - P. 227-228.

76. KVASOV В. I. Methods of shape-preserving spline approximation. — Singapore: World Scientific, 2000. 338 p.

77. Lee s.L., micchelli C. A., Sharma A., smith P. W. Some properties of periodic B-spline collocation matrices // Proc. Royal Soc. Edinburgh. 1983. - V. 94A, n. 3-4. - P. 235-246.

78. LYCHE T. A note on the condition number of the B-spline basis // J. Approxim. Theory. 1978. - V. 22, n. 3. - P. 202-205.

79. Lyche Т., schumaker L.L. On the convergence of cubic interpolating splines // Spline functions and approximation theory: Proc. / Sym-pos , Edmonton, 1972 / Eds. R Sharma, A.Meir. — Internat Ser. Numer. Math , Vol 21. Basel Birkhauser, 1973. P. 169 189

80. MARSDEN M Quadratic splme interpolation , ' Bull. Airier. Math. Soc 1971. - V. 80, n. 5 - P. 903-906.

81. MARSDEN M. Cubic spline interpolation of continuous function // J. Approxim. Theory. 1974 - V. 10, n. 2 - P. 103-111.

82. MEEK D. Some new linear relations for even degree polynomial splines on a uniform mesh // BIT. 1980. - V. 20, n. 3. - P. 382-384.

83. MEIR A., SHARMA A. On uniform approximation by cubic splines // J. Approxim. Theory 1969. - V. 2, n. 3. - P. 270-274.

84. MlROSHNlCHENKO V. L. Convex and monotone spline interpolation // Constructive theory of function: Proceed. / Intern. Conf., Varna, 1984. — Sofia: Publishing House of Bulgarian Academy of Sciences, 1984. — P. 610-620.

85. MlTYAGIN B. Quadratic pencils and least-squares piecewise-polynomial approximation // Math. Comput. 1983. - V. 40, n. 178. - P. 283-300.

86. M0RKEN K. Some identities for products and degree raising of splines // Constr. Approx. 1991. - V. 7, n. 2. - P. 195-208.

87. NORD S. Approximation properties of the spline fit // BIT. 1967. -V. 7, n. 2. - P. 132-144.

88. On Approximation Theory: Proc conf. Oberwolfach, 1963 / Eds. P. L. Butzer, .J.Korevaar — Basel: Birkhauser, 1964. — 261 p

89. SAKAI M., USMANI R. A. Some new consistency relations connecting spline values and integrals of the spline // BIT. — 1983. V. 23, n 31. P. 399 402.

90. Schumaker L.L. Spline Functions. Basic Theory. New York: Wiley, 1981. - 553 p.

91. SHADRIN A. Yu Convergence of quintie spline interpolants in terms of a local mesh ratio // Bulletin of the Novosibirsk Computing Center -Novosibirsk: NCC Pablisher, 1993 — Ser.- Numerical Analysis, Issue. 1 -P 87-95.

92. SHADRIN' A. Yu. On Lv boundness of the Lj-projector onto ^phtus .1 Approxim Theory. 1991 - V. 77, N. 3. - P 331 Л18.

93. SHADRIN A.YU The Lx-norm of the L2-spline projector is hounded independently of the knot sequence. A proof of de Boor's conjecture // Acta Math. 2001. - V. 187, n. 1 - P. 59-137.

94. SHARMA A., MEIR A Degree of approximation of spline interpolation // J. Math, and Mech. 1966. - V. 15, n. 5. - P 759-767.

95. SWARTZ B. 0(h2n+2~l) bounds on some spline interpolation errors // Bull. Amer. Math. Soc. 1968 - V. 74, n. 6. - P. 1072-1078

96. Vermeulen A. H., Bartels R. II., IIeppler G. R. Integrating products of Я-splincs // SIAM J. Sci. Stat. Comput. 1992 V. 13, n. 4.1. P. 1025-1038.

97. VOLKOV Yu S On <on\ergenee of derivatives of odd-degree spline interpolation and de Воог'м problem , Wavelet and Splines- Attracts , Internat conf. St Peter,Ьигд, 2003 P 100 101

98. Walsh J L , Ahlbkrg J. H., nllson e. N. Bebt approximation properties of the spline fit // Л. Math, and Meeh 1962. - V. 11, n. 2. -P. 225-234.

99. ZMATRAKOV N. L. On the convergence of interpolatory cubic splines and their derivatives // Functions, series, operators: Proc. / Colloq. Math. Soc. Janos Bolyai, 35, Budapest, 1980. — Amsterdam: North-Holland, 1983. P. 1301-1307.