Содержание к диссертации
Введение
Глава 1. Ленточные системы уравнений 34
1.1. Определения и обозначения 34
1.2. Оценивание max-нормы обратной матрицы 38
13. Оценки элементов обратных ленточных матриц 44
1.4. Условия нєоірицательности решения трёхдиагоиальной системы уравнений при наличии опального преобладания по столбцам 52
1.5. Условия неотрицательности решения системы уравнений с симметрической циркулянтной матрицей 57
Глава 2. Системы определяющих уравнений для построения интерполяционных сплайнов 67
2 1. В-сплайны и их свойства 68
2 2 Линейные соотношения, связывающие значения сплайна и коэффициенты В-спл айн-разложения ею производных 72
2 3. Системы определяющих уравнений. Периодический случай . 75
2.4. Системы определяющих уравнений. Полный сплайн 76
2 5. Соотношения линейной зависимости между разрывами старшей производной и значениями сплайна 82
2 Вычисление элементов и свойства определяющих синем уравнений . 83
Глава 3 Устойчивые методы построения сплайнов малых 93
3 1 К\бическне сплайны 01
3 2 Сшдйны ігяіон степени 103
Глава 4, Оценки погрешности приближения производных интерполяци онных сплайнов и их сходимость 114
4.1. Оценка е с использованием разложения s по -нормализованным 5-сплайнам 115
4.2. Оценка ес использованием разложения s по нормализованным В-сплайнам 125
4.3. Оценка погрешности приближения старшей производной . 129
4.4. Решение проблемы де Бора 131
4.5. Эквивалентнопь условии еходимосіи процессов иніерполяции
для производных степени к н2п — к ~ 1 133
Глава 5. Условия изогеометрической интерполяции 142
5.1. Монотонность кубических сплайнов 142
5.2. Положительность интерполяционных сплайнов 148
5.3. Условия А;-монотонности кардинальной интерполяции 152
Глава 6. Об инюрполнции сплайнами чётной степени 158
6.1. Задача интерполяции сплайнами чётной степени 158
6.2. Системы определяющих уравнений 160
6.3. Оценки погрешностей приближения производных 169
6.4. Интерполяция сплайнами четвёртой степени 172
Заключение
- Оценки элементов обратных ленточных матриц
- Условия неотрицательности решения системы уравнений с симметрической циркулянтной матрицей
- Системы определяющих уравнений. Полный сплайн
- Оценка погрешности приближения старшей производной
Введение к работе
Рассмотрим задачу интерполяции некоторой функции / по значениям {/J, известным в некоторых точках отрезка [а, Ь]. Ещё совсем недавно стандартным решением такой задачи выступали интерполяционные многочлены Лагранжа, но теперь наиболее распространённым решением являются полиномиальные сплайны, т.е. кусочно-многочленные функции. Сплайнами принято считать функции, являющиеся на подотрезках отрезка [а, Ь] многочленами обычно одной и той же еіенени, называемой степенью сплайна. Точки сопряжения разных многочленов, составляющих сплайн, называют узлами сплайна. Естественно, сплайны одной и той же степени могут различаться гладкостью или дефектом (разностью между степенью и гладкостью).
Кусочно-многочленные функции появились в теории приближений в разных видах очень давно, в современном виде аппроксимация сплайнами появилась в статье И. Шёнберга [164], но началом бурного развития сплайнов, внедрением в вычислительную математику, пожалуй, можно считать 1957 год, открытие Дж. Холлидеем [135] свойства минимума кривизны.
Теорема 0.1 (Дж. Холлидей). Среди всех функций J, имеющих на отрезке [а, Ь] непрерывную вторую производную, и таких, что /(#,) = /,, г = 0,..., N, т. е. принимающих заданные значения, кубический сплайн s с узлами в точках яг,, для которого s"(a) = s"(b) = 0, минимизирует
интеграл
J\l"(r)\'dT. (I)
Раньше инженеры и черіежникн в практической работе для проведения плавных кривых черг і имеющий я точки час то использовали і ибкую репку п пол\чали превосходные резуїьглтьі, что не веема можно бы юдобпгыя шиоп.ди ппіерпошниш чпоюч ієнами пш лгыла О.чан.таеия nsoniy-
тая рейка в первом приближении представляет кубический сплайн с узлами в точках изгиба, вторая производного которою есть аналог кривизны. Открытое Дж. Холлидсем свойство послужило объяснением прекрасного профиля июгнутой рейки.
Если в (1) вместо второй производной использовать производную порядка п,
I,
' Ґ](х)}2 dx, (2)
то функцией, минимизирующей интеграл в классе 1У]'[а,Ь], снова будет кусочно-многочленная функция, а именно сплайн s степени 2п — 1 класса С2п~2[а,Ь] (дефекта 1) опять с узлами в точках интерполяции (см. |179], [96], [102]). Такое свойство сплайна степени 2п — 1 называют свойством минимальной нормы [1].
Сплайн s, минимизирующий (2), принято называть «натуральным», он характеризуется тем, что на концах отрезка [а,Ь] его старшие производные обращаются в 0, а именно
5м (о) = 6м (Ь) = 0, v = п,..., 2п - 2. (3)
Можно при минимизации потребовать чтобы вместе с интерполяцией функции / в узлах сетки осуществлялась ещё интерполяция производных, вновь решением будет сплайн, но, вообще говоря, уже большего дефекта. Также классическим, но более распространённым в приложениях по сравнению с натуральным сплайном, является сплайн .>, который помимо функции интерполирует лишь по п — 1 производных на концах отрезка
а1">И = Г*(я), ^>(Ь) =/И(Ь). "=!,...,"-L (1)
Тлкои сплайн называется «полным», дефект у нею также минимален (дефекта 1) Именно сплайны минимальною дефекіа преде іпв.іяюг наибольший интерес
Одно из направлений развития и обобщения теории сплайнов, называемое вариационной или абстрактной теорией сплайнов, связано с определением сплайнов, как решений некоторых вариационных задач о минимуме функционала (см. [8], [51], [66], [68], [81], [82], [99], [129]).
Сплайны естественным образом возникают и во многих других задачах теории приближения, например, оптимальное восстановление опора-торов, оптимальные квадратуры, поперечники классов функций (см. [38|, [63], [64], [90], [167]).
По всё-таки, как пишет Н.П.Корнейчук в своей монографии [63], "вторжение сплайнов в теорию приближения произошло через задачи интерполирования функций". Преимущества сплайнов перед другими аппаратами приближения обнаружилось именно в задачах интерполяции. Н.П.Корнейчук указывает два аспекта, в которых эти преимущества проявились наиболее убедительно:
"1) Интерполяционные сплайны в ряде важных случаев обеспечивают минимально возможную (при фиксированной размерности) погрешность приближения на классе функций. Интерполяционные многочлены не обеспечивают даже наилучшего порядка.
2) Сплайны - аппарат более удобный, чем многочлены г, вычислительной или — скажем шире — с практической точки зрения. Если говорить о сплайнах минимального дефекта по фиксированному разбиению, обладающих наилучшими аппроксимативными свойствами, то практические удобства связаны с наличием в подпространстве таких сплайнов базиса из В-сплаїінов с конечным носителем. Именно эго обегояюльетво об>слов-ливает локальную гибкойь интерполяционного сплайна, выражающуюся, в частности, — в отличие от пшеріюляционноїо многочлена — в малой чув-сівигельности к поірешностям в исходных данных, небольшое изменение значении функции в одной пли нескольких соседних і очках интерполяции \іа in сказывается па повеление пніерпо іяпнонноіо єн іапна пл некоюром
удалении от этих точек. С этим же связан и тот факт, что интерполяционный сплайн, хорошо приближая функцию, одновременно хорошо приближает и ее производную" [63].
Хогя далее Н П. Корнейчук указывает, что и при вычислении интерполяционного сплайна, "приходится сталкиваться со значительно меньшими трудностями, чем при вычислении многочлена", однако для сплайнов высоких степеней на произвольных неравномерных сетках сколько-нибудь полного исследования о вычислительной устойчивости имеющихся методов построения шпериоляционных сплайнов не г.
Конечно же, в настоящее время сплайны полномасштабно внедрились в вычислительную математику, и, пожалуй, не осталось ни одного раздела вычислительной математики, связанного с аппроксимацией функций, где сплайны не нашли бы применения. Но всё-таки, на наш взгляд, по-прежиему большинство задач связано с интерполяцией функций.
Основным объектом данной диссертации являются интерполяционные сплайны. Именно классические интерполяционные полиномиальные сплайны нечётной степени минимального дефекта, у которых узлы совпадают с ючками интерполяции. (Мы заіронем и интерполяционные сплайны четной степени, но они но своим свойствам существенно отличаются от сплайнов нечётной степени). Нас и первую очередь интересуют два основных вопроса: методы построения интерполяционных сплайнов и изучение сходимости процессов интерполяции для всех производных.
Пусть сетка Д является разбиением отрезка [а,Ь\:
Д : a = Хіі < Х[ < ... <х\ =Ь
Символом З, (Д) или S, будем обозначать множество всех полиномиальных сплайнов на оірезке [п,Ь] порядка г (пли степени г — 1) минимальною дефекта с у і.іамп на сотке Д, т е
:; (Д)=С, = {аеС ~%h] : гт\і Є ?,,/-= 0,1. -А - 1}
где через I?, обозначено множество исех многочленов степени г— 1. Считаем, что в узлах сетки Д заданы значения /, некоторой функции /:
Л = /(х.), i = 0,...,iV.
Мы рассматриваем задачу построения сплайна з 2„(Д), интерполирующего заданные значения. Для однозначного определения сплайна нечётной етепени 2п — 1 при п ^ 2 необходимы дополнительные условия. Обычно дополнительные условия задают на краях отрезка [а, Ь].
Можно, конечно, не задавать никаких условий, а в качестве единственного сплайна брать натуральный сплайн, который минимизирует интеграл (2). Такой сплайн удовлетворяет условиям (3), которые называют «естественными» краевыми условиями. Однако вопреки своему названию натуральный сплайн, т.е. сплайн с естественными краевыми условиями, не очень естественен для приложений и мало пригоден для практического применения. Это связано с тем, что естественные краевые условия, как правило, не согласуются с решаемой задачей. Если производные интерполируемой функции порядка / = п,..., 2п — 2 далеки от нуля на концах отрезка [а, 6], то качество приближения натуральным сплайном вблизи концов будет плохим. Но правильный выбор краевых условий, как правило, даёт замечательные результаты.
На практике существует много рецептов какие краевые условия следует использовагь в зависимости от известной дополнительной информации о функции /. Наилучшие результаты достигаются при использовании на концах 01 резка [а, Ь] значений младших п—1 производных, если они ишест-пы. Как уже отмечалось, эго будет полный спллнп, т с ншерполянпоинып сплайн с краевыми условиями (4)
Распространен еще один иш краевых условий — периодические. Они используются в гам случае, если ингерпо шруемля функция / нвіясня {b — «Э-першцичттп Тогда иніерно іиіиюнньш сп іанн ^ (чіпаєм к»/ке
(Ь - а)-периодичсским.
Нас будет интересовать решение задачи интерполяции полными сплайнами или периодическими.
Практическое построение сплайна заключается в определении каких-либо параметров (коэффициентов) сплайна, участвующих в его представлении. Простейшими сплайнами являются ломаные (п = 1), при их вычислении и исследовании сходимости процессов интерполяции не возникает никаких трудностей, Но уже кубические сплайны (п = 2) и выше являются нелокальными, и для нахождения определяющих параметров необходимо решать систему уравнений, вытекающую из интерполяционных условий. Конкрегный вид системы и её свойства определяются набором параметров, используемых для представления сплайна или, говоря другими словами, базисом в конечномерном пространстве полиномиальных сплайнов.
Наиболее понятный и очевидный метод построения интерполяционного сплайна в базисе из степенных и усеченных степенных функций приводит к системе уравнений с сильно заполненной матрицей. К тому же эта матрица оказывается очень плохо обусловленной даже в случае равномерной сетки. Поэтому посіроение интерполяционного сплайна в базисе из усеченных степенных функций оказалось не приемлемым с практической точки зрения.
Гораздо более удачным оказалось представление сплайна через узловые значения какой-либо из его производных. Получаемые системы уравнений имеют ленточную етрукіуру. А для кубического сплайна системы оінопі-тельно наклонов сплайна {первых производных) в узлах и моментов (іно-рых производных), являясь трехднагональнымн, имеют кроме того еще диагональное преобладание Указанные свойсчиа систем )равнении позволяют использовать очень эффективный и надежный метод решения метод проюнкн (см [1], [5|, [6|, [12J, |81|, [82], |87|)
Привлекателен выбор в качестве опреде інющпч параметров < шли-
на коэффициентов его разложения по базису из нормализованных В-сплаЙиов. 5-силайны имеют конечный носитель, и существует устойчивый мегод вычисления этих базисных функций произвольной степени, основанный на рекуррентном соотношении Хотя В-сплаЙновая коллока-циошіая матрица является вполне неотрицательной ленточной матрицей, и при решении системы уравнений с этой матрицей методом Гаусса отпадает необходимость осуществлять выбор главного элемента для проведения исключения [119], тем не менее этот метод построения имеет ограниченное применение. Его можно с уверенностью использовать только на сетках, близких к равномерным, или специальной структуры, в противном случае обусловленность системы уравнений данного метода может стать сколь угодно плохой [42J. (Под величиной обусловленности мы понимаем произведение равномерных или теж-норм матрицы и её обратной). Заметим, что величина обусловленности не всегда полностью характеризует матрицу в таком вопросе как решение системы линейных уравнений, но относительно малое её значение является гарантией хорошей точности численного решения системы [2{. Конечно, в отдельных случаях система уравнений может устойчиво решаться и при плохой обусловленности, но в данном случае в [108] показано, что при интерполяции кубическим сплайном данных вида ft = йд (фундаментальный сплайн) на сильно неравномерных сетках при значительном удалении от узла сегки хъ возможен неоі раниченпый рост осцилляции сплайна и, следовательно, В-сп л айн- коэффициентов и элементов обратной матрицы. Здесь плохая обусловленность и накопление ошибок округления при решении системы тесно взаимосвязаны.
Если для кубических сплайнов вопрос выбора параметров предшав-лення уже достаточно хорошо проработан, выделены устойчивые, хорошо обусловленные методы пост роения, то для сплайнов более высокой пепсин пег т.пши полной определенней ш Казалось бы мало выбрать пар.иимра-ми представления сп пины шлчеппя В } 5.Ы\ ССІКИ одной їй upon ЇВОЛНЬІЧ
сплайна, но получение соответствующих систем уравнений является довольно непростой задачей. В литературе известна только одна такай система — относительно моментов {относительно (2п - 2)-Й производной, если степень сплайна равна 2п — 1), полученная Дж.Албергом, Э.Нильсоном и Дж. Уолшем [1]. Но ужо для сплайнов пятой степени и выше матрица этой системы не только не имеет диагонального преобладания в общем случае, но и может быть сколь угодно плохо обусловленной при существенно неравномерном размещении исходных данных [10[. Система относительно моментов не получила распространения в силу её громоздкости и плохой обусловленности. Пожалуй единственный способ нахождения сплайнов произвольной степени, который получил распространение, это метод вычисления сплайнов через разложение по В-силайнам. Достоинство этого метода связано с вычислительной простотой определения элементов системы уравнений, основанной на устойчивом рекуррентном соотношении для В-сплайнов,
Однако метод вычисления интерполяционного сплайна через В-сплай-ны нельзя считать лучшим из возможных. Например, в кубическом случае предпочтительной альтернативой выступают1 алгоритмы вычисления сплайна через наклоны или моменты, обусловленность матриц которых на любой неравномерной сетке не превосходит 3. Несмотря па то, что для сплайнов произвольной степени В-сплайновая коллокациоиная матрица является ленточной и вполне неотрицательной, для неё, как и в кубическом случае, обусловленность может быть сколь угодно плохой [18].
Можно упомянуть ещё про некоторые способы решения задачи интерполяции для сплайнов произвольной степени [98], [84], однако какой-либо анализ устойчивости вычисления параметров сплайнов при з том отсутствует. Таким образом, задача поиска хорошо обусловленных способов построения интерполяционных сплайнов вькокнх (тенопги преде гавлястея достаточно акг}а іьноп и во( требованной
Второй вопрос, который мы изучаем в диссертационной работе, это исследование сходимости процессов интерполяции. Впервые вопрос о сходимости процессов интерполяции для сплайнов и их производных при минимальных требованиях гладкости интерполируемой функции был поставлен И. Шёнбергом, которого считают отцом сплайнов, в 1963 году на конференции в Обервольфахе (ФРГ) [157, р. 189].
Задача состоит в следующем. Рассмотрим последовательность сплайнов {ь} степени 2п — 1, интерполирующих некоторую функцию / на носледо-ваіельносіи (сюк {Д} таких, чго
h ~ max (х1+\ — xt) —» 0 при N —* оо.
(KiOV~l '
Будет ли иметь место сходимость s^) к yW для произвольной функции / Ck[a,b] (0 ^ к < Ъг — 1)? Если сходимости в общем случае нет, то каким ограничениям должна удовлетворять последовательность сеток {Д}, чтобы сходимость имела место? Мы будем говорить только про сходимость в равномерной метрике.
Для последовательности сеток с равномерным распределением узлов сходимость для любой производной есть всегда [1], [87], здесь актуален вопрос отыскания точных констант (см. [63]). Для произвольных сеток вопрос значительно сложнее. По началу большинство усилий было направлено на кубические сплайны. Было установлено, что для кубических сплайнов сходимость беч каких-либо ограничений на сотки имеет место при к = 1 пли к = 2 [171J, Л изучение сход и мое і и самих сплайнов в С[а,Ь] и третьих прои вводных в C^cl/j] растянулось ещё на десяток лет.
В 1966 году Л. Шарма и Л. Менр (171( установили, что если ил последовательное^ сеток {Д} наложено 01 раннченне
Яд ^ И < оо, (Г))
Яд = max —
~ глобальная характеристика сети, то сходимость сплайнов имеет место для любой непрерывной функции /. Л в 1967 г. С. Нордом [156] был построен пример расходящегося процесса на последовательности сеток, для которой условие (5) нарушено. С. Б. Стечкин иЮ.Н, Субботин [86] усилили пример С Норда, они пытались определить максимально широкий класс функций, для которых соответствующая последовательность интерполяционных сплайнов безусловно сходилась бы к ним, В результате их рабог [86], [87], и работы Ал. А.Привалова было установлено, что необходимым и достаточным условием является принадлежность функций классу Lip 1. Э. Ченьи и Ф. Шурер [120] показали, что условие (5) не является необходимым для сходимости в С[а,6]. В их примере последовательности сеток Яд —* со, но сходимость имеет место для любой интерполируемой непрерывной функции. Они предложили изучать сходимость процессов интерполяции при ограничениях на локальные характеристики сеток
рд = max -~ ^ р < со. (6)
Исследованию сходимости процесса интерполяции в терминах локальных характеристик сеток был посвящен ряд работ. Вначале А. Меир и А. Шарма [152] показали сходимость кубических сплайнов на любой последовательности сеток, удовлетворяющей 01 раничению (6), если р < у2- Затем Э. Ченьи и Ф. Шурер [121] получили нскоюрое улучшение р < 2. В этом же і оду {1970) Ю С,Завьялов [39] еще усилил результат сходимости р < 1 + \/2, и тгог же результат был повторён в 1973 г. Ч.Холлом [133]. Дальнейшее улучшение установил М Марсден [149[, он показал, чю в классе С[а,Ь] всегда есіь сходимость при выполнении условия (6) с р « 2.439, л при р > //, где
// = ~~г-~ * 2 618.
привел пример последовательности сеток, где процесс может расходиться (последовательность норм соответствующих операторов интерполяции расходится). Во всех этих работах рассматривались кубические сплайны с периодическими краевыми условиями, а Т.Лич и Л.Шумейкср [147| повторили большинство из приведённых результатов и для других краевых условий.
Как пишет Ю. Н. Субботин [90], после знакомства с работой Ю. С. Завьялова [39] у него возникла идея как усилить метод доказательства Ю.С.Завьялова, и вскоре эта идея была блестяще реализована его учеником Н. Л. Зматраковым [43]. Он показал, что если р < р* и последовательность сеток удовлетворяет условию (6), то последовательность интерполяционных кубических сплайнов равномерно сходится к интерполируемой непрерывной периодической функции. Н.Л.Зматраков построил достаточно тонкие и сложные примеры, показывающие, что если р ^ р", то существует непрерывная периодическая функция и последовательность сеток, удовлетворяющая (6), такие, что соответствующая последовательность интерполяционных кубических сплайнов расходится хотя бы в одной точке. Независимо от Н.Л.Зматракова окончательный результат о сходимости при р < р* нов горил К.де Бор [108]. Более простыми способами, чем у Н.Л.Зматракова, эти же результаты о сходимости и расходимости получил В.Л.Мирошниченко [71], [42], причём не только для периодических краевых условий.
Исследование сходимости s'" к /'" в классе С]\а, Ь] в терминах локальной характеристики сеток также изучалось Л. ШармоЙ и А. Ыеиром [171], Ю С.Завьяловым [39], но окончательное решение опять-таки было получено И.Л.Змаграковым [15[. Причем ограничения на последовательность сепж оказались такими же, как и для сходимости самих сплайнов в С[а, Ь\, л именно- при р < р* имеет моею гходимопь, а при р ^ ff егп> ич-М1, на коюрых процесс букт рлехо циься. Отмстим, чш в да іьшч'ішем
Н.Л.Зматраков продолжил изучение сходимосги и сплайнов, и третьих производных в метрике hv (см. [44], [40], [47j, [180J). Упомянем еще об одной характеристике сеток
ЙА,т = max —, т > 1,
\i-j\=m tlj
обобщающей локальную сеточную характеристику. Изучение сходимости интерполяционных процессов для кубических сплайнов в терминах рд,,,, рассматривалось в работах [43[, [48], [138].
Для интерполяционных сплайнов более высоких степеней, чем кубические, результатов не так много и, особенно, окончательных. Первый результат, который можно считать окончательным, это результат К, де Бора [Ш4] о сходимости третьих производных сплайнов пятой степени в классе С3[а,Ь] без каких-либо ограничений на последовательность сеток (небольшая погрешность доказательства была исправлена им в работе [115] и там же указано, что сходятся и четвёртые производные сплайнов седьмой степени в CJ[a,6], указан путь доказательства, по сами вычисления не приведены). Позднее (1973) К.де Бор предположил, что и в общем случае сплайнов s степени In — 1, интерполирующих функцию / Є Сп[а, Ь], имеет место безусловная равномерная сходимость $^ к /'"*. Эквивалентная формулировка этого предположения более известна как знаменитая гипотеза К.де Бора [105J, за которую был объявлен денежный приз, об ограниченное! и нормы операторов наилучшего среднеквадратичною приближения сплайнами степени п — 1 как операторов из С[а,Ь] в С[а,Ь\ константой, зависящей только оі п, но не от сетки.
В 1975 году К.де Бор [107] показал, то сходи мое і ь й^' к /(/>, сели интерполируемая функция / класса 6т'[а,і], беї оіраничений на сотки при к = 0,..., п — 2 невозможна, дополнительно он сказал, чю и при А" = п + 1, . ,2п - 1 бе условная сходимость іакже невозможна, но дока-ілп' іьсгіїа мою факы не прнш* і, л сообщи і, что оно бїдім ои\б шковаио
где-либо еще (об этом доказательстве в более поздних работах К. де Бора нам ничего не известно). В этой же работе было высказано дополнительное предположение о безусловной сходимости s*"-1' к /("_1^ в классе Cn~l[a,b]. Нами [10] в 1984 г. были найдены такие числа рп\ к = 0, ...,п - 2 и к = п + 1,...,2п~1,и при любых р> р„ приведены последовательности сеток, удовлетворяющие условию (6), на которых интерполяционные процессы расходятся для соответствующих к, если / С [а,Ь].
Сходимость процессов интерполяции в общем случае была доказана только для п-й производной при ограничениях (5) опять же К, де Бором [109]. Им же при этих же ограничениях установлена и сходимость самих сплайнов [ПО], а Ю. Н. Субботиным [89) — сходимость s^ к /^ для функций / из Ck[a,b\, 0 ^ к ^ 2я — 1, также при ограниченности глобальных характеристик последовательности сеток Некоторые неокончательные результаты о сходимости при ограничениях на соседние шаги сеток (локальные характеристики) получены только для к = 0 С. Фридлендом и Ч. Мичелли [130] с привлечением специально разработанной и достаточно сложной техники теории осцилляционных матриц. Нам удалось эти условия перенести на случай к = 2п ~\ [11]. Небольшое улучшение условий С. Фридленда и Ч. Мичелли для сплайнов пятой степени, а также некоторые условия на сходимость первых и вторых производных, были получены А. Ю. Шадриным [94], [168].
И, наконец, отметим, чго в 2001 году А.Ю.Шадрин [170] решил знаменитую проблему К. де Бора, установил безусловную сходимость s["] к /("' для функций / из С"[а,6]. Укажем ряд работ, в которых разбирались частые слуып пгтяеш К. де Бора [136], [128], [154], [139].
Приведенный здесь краткий обзор результатов по обозначенным рлт е вопросам — методы построения интерполяционных сплайнов и еходимоеіь шперполяцпошкно процесса при минимальных ipi бонаниях гладкости пн-герпо шри'моп ф\ныши нс нрпендич па по шоп, л щрл/кает лишь
интерес автора к затронутым вопросам. Имеется много работ по изучению сходимости производных интерполяционных сплайнов при повышенной гладкости интерполируемой функции, в частности, если / Є С"[о,Ь], то и сплайны, и п производных сходятся без каких-либо ограничений на сетки (см., например, [1], |87|). За рамками обзора остались вопросы сходимости в других метриках, а также вопросы построения и сходимости интерполяционных сплайнов более высокого дефекта.
Диссертация состоит из оглавления, «ведения, основной части, включающей шесть глав, заключения и списка литературы. Краткое содержание основной части приводится далее. Нумерация разделов внутри главы формируется из номера главы и номера раздела, разделённых точкой.
Первая глава является вспомогательной и включает в себя 5 разделов. Она полностью посвящена вопросам решения систем линейных уравнений и оцениванию норм обратных матриц. Дальнейшее решение вопросов в следующих главах опирается на результаты устанавливаемые в этой главе. Хотя эти результаты и носят вспомогательный характер, однако они могут представлять и самостоятельный интерес, а также могут быть использованы в других разделах математики.
Оценки элементов обратных ленточных матриц
В предыдущем параграфе мы изучали вопросы оценивания норм некоторых классов матриц. Но все оценки и вычисления касались только одной из норм, а именно max-нормы. Ясно, что если матрица А обладает диагональным преобладание не по строкам, а по столбцам, то мы можем привести теоремы, аналогичные теоремам 1.1 и 1.2, но для 1-нормы вместо max-нормы. И сюлбцевое диаюнальное преобладание не позволяет как-то эффективно получить оценку обратной матрицы в тах-норме. Конечно же всем известно, что для любой матрицы А можно установить оценки для любых норм р и q. Но всё дело в том, от чего зависят константы К\ и Кі. В общем случае они зависят от JV — размера матрицы.
Однако, если матрица ленточная, то и сюлбцевого диаіопального преобладания достаточно для получения оценки обраіпоп мацжцы в шах-норме Оценка нормы поручается после оценки элемента обрашоп матрицы Пусть величина характеризует диагональное преобладание в j-u столбце матрицы Л. Наличие диагонального преобладания в этом столбце эквивалентно неравенству а3 1, тем сильнее диагональное преобладание в столбце, тем меньше а3 . Обобщённую характеристику диагонального преобладания по всем столбцам обозначим
В работе [122] С. Дсмко установил, что элементы обратной к любой ленточной матрице экспоненциально убывают, удаляясь от главной диагонали. Однако мы приведем здесь аналогичный результат К. де Бора [110[, отличающийся тем, что явно вынисаниы константы, и которым мы в дальнейшем воспользуемся.
Задачи сплайн-интерполяции, с которыми мы дальше будем иметь дело, сводятся к системам уравнений с ленточными матрицами. А если рассматривается периодический случай, то матрицы будут циклическими ленточными. Для циклических ленточных матриц мы уже не можем утверждать, что элемонш обратной, удаляясь or главной диагонали, экспоненциально jбывают. Оказывается и лом случае -жепоненциальное заіух.шпе при удалении or г. і л іншії диатнали поело .V/2 іпаюв сменяемся на их "-жсии-ненциальный росі, г.е. наблюдается эффект цикличности.
Степень В1 будет останаться циклической ленточной матрицей с шириной ленты тк пока 2тк + 1 будет меньше N, т.е. при к -. Обозначим Ь] элементы матрицы В" . Каждый элемент матрицы D lA [ может быть представлен в виде
В этой сумме несколько первых слаїаемьіх могут быть раины нулю, поскольку 6, j = О при тк \t j\ N — пік для циклической ленючпои матрицы В\ другими словами элемент b(J лежи г на нулевой дпаган.ілп при к - , если \i-j\ 4," при А - = , если -j -j 48 Следствие 1.15. Пусть А — {ыои (еская т-леиточная матрица со стобцевым диагональным преобладанием а \, тогда для тах-пормы обратной матрицы А 1 справедлива оценка (1.24).
Теорема 1.16. Пусть 1 q oo, p mm{q,q/(q — 1)}, A обратимая циклическая ленточная матрица с шириной ленты т. Тогда для элементов обратной матрицы A-1 = (aj,) справедливы оценки { ІСЛІ - І, при \i-j\ N/2, K\N \"A, при \i-j\ N/2, где A=(f1 ШУ ", # =сопс!,,(А). \(i + ) / Дуказатр іьстео. Известно (см., например, [134]), что для сопряжённых у-норм, т е. если числа р и q связаны соотношением \/р -f 1/g = 1, ю А7;, = А(, Поэтому мы можем выбрать наименьшее in чисел q и qj{q 1), обозначив его р (1 р 2).
Зафиксируем нротнольиып индекс j7 1 j JV, выделим j-W полбец маїрпцьі А-1 = (« ;) и обозначим ею х = (rh г_ , , г\) , г. с. г, = я ия г = 1,2,. ,.V и (АГ), = rf. Из вскгора х образуем серию векторов а; " = (х( ,ту ,... ,х )г, 0 п N/2, по следующему правилу п \г — j\ N п, п противном случае. Это означает, что ж " = х, ж 1 отличается от х тем, что х = 0, и т.д. Рассмоірим (труктуру вектора Ах К Поскольку ненулевыми компонентами вектора ж " являются элементы матрицы А-1, то (Аа " ); = О при т + п \i — j\ N т — п. С другой сгороны, если п т, то (Аж " ), = 0 при \г -j\ п — тв силу лспточности матрицы А с шириной ленты т.
Условия неотрицательности решения системы уравнений с симметрической циркулянтной матрицей
Пусть корни многочлена Q(z), связанного с цирку-ляшпной матрицей А вида (1.39), отрицательны и Q{—1) Ф 0. Тогда матрица GA монотонного вида, где G = {-P)-mQ{-P), т. е. G = (-1Г circ((-l)mam,..., -а1( 1Д... Д 1, -аи..., (-1) 4,,-1). Доказательство этих теорем непосредственно вытекает из доказатель ства теоремы 1.21. D
Теорема 1,22 (корни многочлена Q{z), связанного с матрицей системы, только положительны) говорит о том, что решение системы уравнений (1.1) при иеоірицательиой правой чаєш у всегда будет либо неотрицательным (ш четно), либо наоборог неположительным (т нечеіно). Вопрос о положительности (неотрицательности) решения при положительной правой чаї їй у, если у мноючлона Q{z) сечь отрпцакмьные корни, но іак тривиален Мы даем огвет на эюг вопрос в виде оірдннчсшііі на опюшение (осенних компонент вектора правой часін у. Введем следующую характеристику матрицы А q(i)+ (-1)-3(-1) Q(i)-(-i) »Q(-i) у Если все корни мноючлона Q(z) оірицатєльньї, то на основании представления (1 43) и неравенства (1 45) заключаем, что (-1) "0(-1) О.
Таким образом характеристику q , определённую равенством (1.49), можно записать чак nV;Q(i) + lQ(-i)l 4 Q(1)-Q(-1)-IlocKOJtbKy в случае отрицательных корней многочлена Q(z) его коэффициенты неотрицательны, то ясно, что Теорема 1.24. Пусть все корни многочлена Q(z), связанного с цирку-лянтной матрицей А вида (1.39), отрицательны и Q{—1) 0. Вектор Gy будет положительным, если положителен у, и его соседние компоненты отличаются не более, чем в q раз при Ч 4 (1.50) Доказачельсіву предпошлем дне леммы. Лемма 1.25. Пусть enctdnue компоненты положительного вектора у отличаются не более, чем в q раз Тогда при av 2q (1.51) компоненты ыктора Gvy также положитыыш, где (7,, = 1-11(-(0,.-1,0, ,0,-1). Доказательство Для отношения соседних компонент вектора у введём обозначение У. Л, = У/И 1 Тогда (G„y), = -yt-\ + сад, - &+i = ( -A,_i + a„ - д-1 у,. (1-52) Поскольку по условию величины A,_i и А, лежат в промежутке [1/у,у], то выражение {Gt,y), минимально при A,_i = q и A, = \jq и, следовагелыю, всегда положительно при выполнении неравенства (1 51). Лемма 1.26. Пусть выполнены условия леммы 1.25. Тогда отношение соседних компонент вектора Gvy не превосходит величины auq- 2 av — 2q Доказательство. Используя {1.52), запишем отношение соседних компонент вектора GvV f-Aj-i+a,,- — J у, f-Aj+rt,,--—JyH (G,tf). V К) M-Vi+a,)-! Ясно, что это выражение является убывающей функцией по переменным A/+i и A,-i на интервале [l/q,q]. Поэтому справедлива оценка (G,y), A,(-l/g + a,)-l {Gvy)tk\ -\t+av-q А выражение справа максимально при A, = q. Иіак {Gvy), t\vg - 2 (G„y),,i t\tt 2q Докаштелъстьо ісоремьі 1.24 Докачаїельс mo проведем методом мл-іечлшческон ішд\мнт по т. Пусть т = 1. В этом случае матрица А трехдиагональная А — circ(fi], 1,0,... ,0,1), соответственно Q[z) = zl + a{z + 1.
Справедливость теоремы следует из леммы 1.26 па основании эквивалентности неравенств (1 50) и (1 51) Здесь G — G\ с щ = а\ и Q(l)-Q(-i) _сц Q(l)+Q(-1) 2 Теперь предположим, что утверждение теоремы верно для т = к. Покажем, что тогда оно будет справедливым и для m = к + 1. Ясно, что многочлен Q(z), связанный с матрицей А, можем представить в виде Q{z) Q{z) {z2 + aMz + l)) где aul = -zki 2, Zk + l a Zk+i и l/zk+i некоторые из корней многочлена Q(z). Многочлен Q(z) может быть связан с некоторой матрицей А вида (1.39), его степень равна 2к. Матрицу, приводящую А к матрице монотонного вида (см. теорему 1.23), обозначим G. Тогда G = GG/+i, где Gun =circ(a i, -1,0,. ..,0,-1). Прежде всею .шіешм, чго » . (1ЛЗ) В самом деле, по ) ел о вию гооремы q q\ где, согласно (1.49), / t Q(l) + (-l) Q(-l) ()(1)-(-I) Q(-l) Учитывая, что 0(1) = (aui+2)0(1), (i-54) 0(-1) = -( +1-2)0(-1), имеем _ f,_0(l)-(QUi+2) + (-l)fQ(-l)-(aui-2) 4 0(1) («A+i + 2)- (-1) 0(-1) («U і - 2)" Поскольку a i 2 и (—l)/v0(— 1) 0(1)) имеет место неравенство (QU i+2) +(QUI-2) _ а , и 7 (m и + 2) - К+1 - 2) 2 которое и доказывает (1,53). Неравенство (1 53) позволяет применить леммы 1.25 и 1,26 при Gv = G H- В результате чего получаем, что компоненты вектора у GK+ІУ положительны, и отношение соседних компонент этого вектора не превосходит величины ак+1д - 2 Я = 7Г- (1,э5) «Ui-2g По индукционному предположению вектор Gy будет положителен при выполнении условия 0(i)+ (- 0(-1) 0(1)-(-1) 0(-1) С учётом (1.55) последнее неравенство можно переписать в виде ; (ащ + 2)0(1) + (-І)Чалгі - 2)0(-1) (aui + 2)0(1) - ("1)4 +1 - 2)0(-1) когорое, в свою очередь, согласно (1 54), совпадает с неравенсгвом (1.50).
Следовательно вектор Gy — Gd положителен. Теорема 1 24 полностью докачана. [ Отметим, что неравенство (1 50) является необходимым и достаточным условием положительности вектора Gy Однако нельзя сказать, что оно является необходимым и для положительною решения сипемы (1.1), гак как ) шерждеппе теоремы 1 23 тип г лишь догм, і очный \ ірлкіер В рабогс Б. С. Киндалева [60] указано на связь величины Q( 1) с нормой обратной матрицы к А для рагематрипасмого случая. Показано, что если матрица А чётного порядка, то
Если же А нечётного порядка, то норма Л-1 достаточно близка к \Q{—I)!-1, и справедлива оценка iA-Mu t1T Q(-i) Всегда можно считать, что матрица А чётного порядка (в силу цикличности А число уравнений в системе (1.1) можно удвоить), и выполнено равенство (1.56). В этом случае характеристику q", определённую равенством (1-49) и используемую в теореме 1.24, можно выразить через число обусловленности матрицы А. Имеем concUA) +1 4 concWA)-r [h07) Выражение (1.57) говорит о том, что для систем с плохо обусловленными матрицами характеристика q близка к 1, и гарантировать положительность решения можно юлько при правых часіях с "почти" одинаковыми компонентами.
Системы определяющих уравнений. Полный сплайн
В непериодическом случае одним из наиболее распространённых вари-анюв задания краевых условий в задаче интерполяции является задание па концах отрезка [а, Ь\ по п 1 младших производных. Интерполяционный сплайн с такими краевыми условиями принято называть полным сплайном.
В 41 ом случае ечшде.м, чго сеіка Д расширена на концах о і режа необходимым ко.]ичс( гвоч краіньїх узлов расширенно» еіки Л значения функции / (такое задание дополнительных узлов сетки соответствует интерполяции полным сплайном}. Определяемые параметры являются коэффициентами В-сплайпового представления сплайна s . Поскольку s Є Sjn, то для представления s на [а, 6] нам необходимо находить коэффициенты а\]_2пї ,..., -1, {Ясно, что достаточно проводить рассуждения лишь для коэффициентов Q( , поскольку они связаны простыми соотношениями с коэффициентами (і) (см. свойство В1}).
Теперь соотношения (2.28) для і — 1 — k,...,N — 1 вместе с уравнениями (2.30) и (2.31) образуют замкнутую линейную систему уравнений для нахождения неизвестных коэффициентов a\\inhk,. ..,a v.,. Но оказывается, что эту систему уравнений можно преобразовать в систему с матрицей такой же структуры, как и в предыдущем случае к п.
Заметим, что в выражениях (2.28) и (2.31) производные 5-сплайнов можно переписать через 5-сплаины более низких степеней -і afXW o)=/M(a), = ,..., п-1, ,V-1 Е afNjM {xN) - Ґ\Ь), v = к,..., n - 1. Поскольку слева от XQ И справа от х у все узлы кратные, го в этих суммах отличны от 0 всего по одному слшаемому. Следовательно a-L.-n-/ », " = ,- ,л-1, (2 32) « C-i =/ "(Я = ,...,«-1 (2 33) Выражения (2 32) и (2.33) к сожж шюсш с (2 3) позволяюі іииіш ко)ф 70 Если к = п — 1, то это всею два коэффициента «.ЇЇ =/" («.), а«, =/" (6), при /г п — 1 для нахождения всех коэффициентов из (2 3) получаем рекуррентные формулы (i/) М , Х\ -С» {1/+1) г/ = п — 2, п — 3,..., A;, j = —2п + у -f 2,..,, —га; а = а .Л — -ft ., , z/ = n - 2, n - 3,..., k, j = N-2tN 3t...tN n + t/t m которых, с учётом {2 32), {2.33), можем выписать уже явные формулы а% = Е ( ЧР(Л ,..., - o)/(U,,,(«), (2.34) "iv-i-j = Е П8Уті -і - x.v, - - - .XJV-J - Jw)/ ), (2.35) где т = 2п — А — 1, j = 0,... ,п — к — 1. Здесьsym,,(t,... ,/„) суть символы элементарных симметрических функций от v аргументов степени р. Это многочлены, состоящие из С1 слагаемых (С — биномиальные коэффициенты). Они имеют вид symn[tx,...,tu) = 1, sym i,..., ,,) = t[ + ... + tv, sym2( ,..., ) =t\t2 + t\t\+ ..+ t„-xtV) bymy(ti,..., ) Теперь исключим найденные кежрфнцшчпы и і уравнении (2.28) при і = -к + 1...., Л - 1 В результате получаем сш і ему ,V h А- — 1 урлшюпші Ліс\- = с (2 3t ) относительно оставшихся неизвестных сні = (а_„и, . , 1,, ,,)7 г матрицей Af„ = (aftJ) и вектором правой части с1 = (с\,. , c v+(_1)r. Матрица Ai имеет структуру, подобную структуре матрицы системы (2.29). Её элементами также являются интегралы от произведений В-сплайнов Обратим внимание на то, что традиционная система уравнений относительно коэффициентов разложения самого сплайна, часто называемая кол локационной, в силу замечания 2.1 тоже может быть записана в виде (2.36) при А: = 0. Обычно практическое построение интерполяционного сплайна через В-сплайны сопряжено с некоторыми неудобствами использования краевых условий, даже самых употребительных (в кубическом случае помимо первых производных для полного сплайна ещё распространено использование вюрых производных на краях отрезка). Наша запись такой системы для полною сплайна свободна от евойеі венных недостатков: полностью однородная с і рук гурд элементов матрицы. Приводом конкретны» вид этой сисюмы для наиболее час і о практически иеполь емых кубических сплайнов. В зюм случае нсизвесшыми, подлежащими определению, являюмя tt_j,...,t\!\_. По явным формулам (2 34) и (2 35) определяем Of-j, a„j и t\\-z, o\_i, а именно
Аналогичным образом обстоят дела с выводом сисіем уравнений относительно вектора неизвестных /3 = (/3_2K+JL, ... ,/3;v_1)7 , т. е. коэффициентов разложения # по L і-нормализованным 5-сплайиам. При к п система будет иметь вид AL-Фк = d\ (2.38)
Здесь опять же матрица является транспонированной к матрице системы (2.36) для (2п - к)-й производной, а вектор правой части системы dk = (d\,..., dx+2„-i-i)T имеет компоненты
Оценка погрешности приближения старшей производной
Для достаточно гладких функций / можно рассматривать вопрос об оценке производных функции погрешности е s — / Если нас интересует качество приближения к-& производной интерполируемой функции / соответствующей производной интерполяционного сплайна, то считаем, что / Є С [а, 6]. Мы оценим величину Це Цзс через модуль непрерывности производной /( . Теорема 4.1. Если периодический сплайн s интерполирует периодическую функцию f Ck[a,b], 1 к 2п — 1, то справедлива оценка 1е№,» - з{4 - f{K)L [n + (п - 1 + fc)A HJw »; h), (4.1) й?е А — Atampwi a системы (2,26) задачи построения периодического интерполяционного сплайна s.
Доказательство. Функция 6 , величину отклонения которой от / требуется оценить, является периодическим сплайном степени 2п— I — к. Рассмотрим еще один сплайн s , степени 2п — I — к, задаваемый явно в виде разложения по периодическим Loc-нормализованным В-сплайнам с коэффициентами cf-, являющимися компонентами вектора правой части системы (2 26), т.е.
Отметим, что если полный сплайн s степени 2п \ интерполирует функцию/ гладкости С1[а,Ь] при к и —1, то функция/ па краях отрезка [а,Ь] может не иметь нужного количества производных (меньше п — 1), югда считаем, что производные сплайна s на концах отрезка [а, Ь] интерполируют вместо недостающих производных функции / произвольные числовые значения, но мы за ними в этом случае по прежнему сохраним обозначения / (а) или pv\b). И в любом случае дополнительные слагаемые в теореме 4.3 (по сравнению с теоремами 4.1 и 4.2) в оценке погрешности е(Ц _ s(k) __ j{k) не оказывают существенного влияния на сходимость процессов интерполяции, т. к. Kh — 0 при h —» 0. Определяющим оказывается поведение величины H-A lj.
В предыдущем разделе получение оценок погрешности интерполяции основывалось на представлении производных интерполируемою сплайна в виде разложения по L -нормализованным В-сплайнам. 0к ізьпшется для получения подобных оценок величин погрешностей Р(А = 6(,) — /1 можно использовать и Ь[-номализованныс В-силайны, опираясь на спелемы уравнений относительно коэффициентов ti] Теперь требуемое неравенство (4 25) непосредственно следует из (4,26), (4.27) и (4.29). Теорема 4.5. Для к-й производной погрешности е интерполяции полным сплайном s функции f є С "[щb], n—l = k 2n—2, в узлах сетки построения полного интерполяционного сплайна s. Доказательство. В эшм случае доказательство практически полностью повторяет доказательство теоремы 4.4, Для погрешности е( также справедлива оценка (4.26), но, поскольку теперь сплайн s +l не является периодическим, то для нею имеет место представление "-V) = C -wj,,-/-iH-f + :11л/\_1 ,,, .,(/). (Lai)
Для определения коэффициентов в] т мы имеем пкчемы лннеіпнлх уравнении (2 38) и {2 II). При к + \ п те коирфицпгшы находяпя їй гне іеміл (2 38), дальнейшее доказательство повторяє і расе\ждопия іеоре-чл 1 ! Получение в предыдущем параграфе оценки величины погрешности е[Ц — s[i) -у( )) & = 0,..., 2п—2, опиралось па применение теоремы Ролля. При к = 2/і-1 чеорему Ролля ужо применять нельзя, так как функция 5U"-i) является разрывной, однако в этом случае возможно применение расширенной теоремы Ролля. Теорема 4.7. Если периодический сплайн ъ интерполирует периода-чішро функцию f Є C "_l [«,&], то трашдлшм оцінка lk,J,,-1,lk 2n[l + (2ii+l)(A{)-1]-/(/1-, -1J;A), (138) ?д( До /3-і/і laiui-hoj итщиоитя матрица ш)ачи погиіроишя тргюдч-н ( кого иипи ипо іяциолпо/а І п шина ъ 130 Теорема 4.8. Если полный сплайн s интерполирует функцию f Є C2" x[a,b] о умах сетки Д и значения производных /(,, (а) и /(,,,(6), р = 1,..., п — 1, то справедлива оценка l + (2n + l)(Ajr ,(2/.-1) Й2п и (/(2"-1 ;/ ), (4.39) ?де А$ В-сплайн-коллокационная матрица .шдачи построения полного интерполяционного сплайна я. Доказательство Мы докажем лишь тоорему 4 8, другая доказывается аналогично. Так как сплайн s (онпадаег с функцией / и узлах сетки Д, ю в любых последовательных 2га — 2 интервалах сетки существует по меньшей мере одна точка, в которой значения ,s 2" 2 и рін 2 совпадают. Следовательно функция погрешности е 2" = s(-J"-2) _ fi2 1- 1) являющаяся абсолютно непрерывной, в любых последовательных 2п — 1 интервалах сетки по меньшей мере дважды обращается в нуль, тогда по расширенной теореме Ролля (см., например, [167, р. 29]) не далее чем на 2п интервалах сетки or любой точки х [«,6] найдётся точка 0 Є [й,Ь\, в которой либо е(2"-1 (0) — 0, либо е " 1\в — 0) и е 2 1"1\0 + 0) имеют разные знаки. В силу непрерывносги /(2" 4 функция eU i-i) может иметь разрывы только в узлах сегки Д, и их величина равна величине разрывов старшей производной сплайна
