Содержание к диссертации
Введение
1 Введение
1.1 Мотивация 6
1.2 Основные определения 11
1.3 Структура диссертации 16
2 Негладкая оптимизация 19
2.1 Квазидифферснцируемые функции 19
2.2 Условия экстремума 22
2.3 Численные методы негладкой оптимизации 26
2.3.1 Метод дискретного градиента 26
2.3.2 Метод отсекающего угла 26
3 Аппроксимации полиномами наилучшего приближения 28
3.1 Полиномы: необходимые и достаточные условия оптимальности . 28
3.2 Алгоритм Ремеза 30
4 Аппроксимация полиномиальными сплайнами 34
4.1 Спалйны: необходимые и достаточные условия оптимальности . 34
4.2 Обобщение алгоритма Ремеза на случай полиномиальных сплайнов 48
4.2.1 Задача построения линейного сплайна (ломаной), удовлетворяющего условию альтернанса 49
4.2.2 Задача построения полиномиального произвольной векторной степени сплайна, удовлетворяющего условию альтернанса Г>2
Оглавление 4
4.2.3 Замена базиса 56
4,3 Численные примеры 71
5 Численные эксперименты 79
5.1 Обобщенный алгоритм Ремеза: непрерывные функции 79
5.2 Обобщенный алгоритм Ремеза: дискретные функции 81
5.2.1 Базы данных 81
5.2.2 Нагревание Титана 83
5.2.3 База данных Пезака 87
5.2.4 Некоторые важные замечания и рекомендации 90
6 Теория аппроксимации в задачах налогообложения 92
6.1 Постановка задачи 92
6.2 Необходимые и достаточные условия оптимальности 97
6.3 Численные эксперименты с модельными функциями 98
6.3.1 Негладкий случай 99
6.3.2 Гладкий случай 103
7 Сплайны со свободными узлами 106
7.1 Непрерывная и дискретная аппроксимация 106
7.1.1 Приближение непрерывных функций 106
7.1.2 Дискретная аппроксимация (равномерная аппроксимация и критерий наименьших квадратов) 107
7.2 Полиномиальные сплайны со свободными узлами: вычислительные аспекты 108
7.3 Численные эксперименты с непрерывной функцией 109
7.4 Численные эксперименты с дискретными функциями: сравнение алгоритмов 111
7.4.1 Метод Г. Белякова (Алгоритм 1) 111
7.4.2 Конкретизация Алгоритма 1 112
7.4.3 Новый алгоритм (Алгоритм 2) для приближения дискретной функции (базы данных) 112
Оглавление 5
7.5 Сравнение результатов, полученных Алгоритмом 1 и Алгоритмом 2.114
7.6 Заключение 116
8 Заключение и направления для дальнейших исследований
- Основные определения
- Численные методы негладкой оптимизации
- Алгоритм Ремеза
- Задача построения линейного сплайна (ломаной), удовлетворяющего условию альтернанса
Введение к работе
Актуальность темы. В настоящее время интенсивно развиваются компьютерные технологии. Их влияние на развитие науки и техники неоспоримо. Поражает то, как быстро увеличивается мощность компьютеров, при этом цена на соответствующие компоненты падает, что делает привлечение компьютерных технологий все более и более доступным для научных исследований, автоматизации, обучения и многого другого. Разумное использование имеющихся средств помогает сэкономить время и деньги. Работа некоторых современных технических объектов (космический корабль, достигший Сатурн) практически полностью контролируется компьютером очень высокой точности. На компьютере моделируется развитие эпидемий и борьба с ними, также ход предвыборных процессов, погода и даже мода.
Математики, работающие с числами и функциями, пытаются перевести работу некоторых физических объектов на язык математических формул (моделирование). Иногда моделируемый процесс настолько сложен, что его точное моделирование невозможно (недостаток знаний о природе процесса или недостаток компьютерных ресурсов). В таких случаях введение некоторых грамотно построенных аппроксимаций процесса помогает сделать шаг на пути к более детальному пониманию природы процесса и провести соответствующие эксперименты, подгверждающие или отрицающие выдвинутые гипотезы.
Следует помнить, что при работе на компьютере все числа представляются с определенной точностью, то есть с самого начала происходит некоторое аппроксимирование изучаемого процесса.
В некоторых приложениях приходится работать с функциями очень сложной природы, поэтому возникают задачи приближенного представления этих функций более простыми. С простыми функциями намного легче работать при проведении теоретических исследований, более того, при работе на компьютере очень часто "сложные" функции могут быть вычислены весьма приближенно, поэтому при проведении экспериментов может появиться погрешность, которая накапливается на каждой последующей итерации и в конечном итоге приводит к тому, что даже те численные алгоритмы, которые построены на очень элегантной и совершенной теории, к сожалению, не могут быть успешно реализованы численно на компьютере.
Приведем другой практический пример, возникший в связи с развитием компьютерных технологий и их проникновением во многие области науки и техники. Предположим, что требуется изучить природу некоторого процесса, происходящего в некоторой, физической
| РОС. НАЦИОНАЛЬНАЯ
{ БИБЛИОТЕКА J
3! 1&&М\
системе. Допустим, что имеются измерения некоторой физической
величины, записанные в виде таблицы (базы данных). Анализ имею
щихся баз данных представляет большой интерес, так как такое иссле
дование помогает использовать накопленные десятилетиями данные в
прогнозировании (задачи классификации и математической диагно
стики). Некоторые такие таблицы содержат сотни тысяч и даже мил
лионы записей, поэтому иногда бывает рационально хранить в памяти
компьютера не огромные таблицы, а попытаться приблизить данную
таблицу некоторой кривой (аппроксимирующей или интерполирую- *
щей) и хранить в памяти лишь параметры данной кривой. Кроме того, имея такую кривую, изучаемый процесс может быть понят и описан более четко.
В некоторых практических задачах возникает потребность приближения моделируемого процесса функциями определенного класса. Такая проблема возникла в области моделирования налогообложения, где непрерывная модельная функция аппроксимируется ломаной, так как по коэффициентам ломаной может быть легко восстановлена привычная нам налоговая таблица, содержащая диапазоны налогообложения и соответствующие ставки налога.
В настоящей работе разрабатывается и тестируется алгоритм, позволяющий аппроксимировать непрерывные и дискретные функции (базы данных) полиномиальными сплайнами в равномерной метрике. Данное исследование является естественным продолжением известных работ П.Л. Чебышева, Ш.Ж. Валле-Пуссена, Е.Я. Ремеза, ставшими в некотором смысле классикой полиномиального приближения. В данной работе делается попытка обобщения некоторых результатов, полученных в теории приближения полиномами, на случай полиномиальных сплайнов, а также непосредственным продолжением исследований в области полиномиальных сплайнов, проведенных Райсом в 60-х годах и М.Г. Тарашниным в 90-х годах двадцатого века.
Так как аппроксимация полиномиальными сплайнами имеет много практических приложений, то таким образом, проведенное исследование представляет теоретический и практический интерес.
Целью диссертационной работы является численного алгоритма, позволяющего аппроксимировать непрерывные и дискретные функции (базы данных) полиномиальными сплайнами. Большая часть проведенного исследования состоит в обобщении некоторых классических результатов теории приближения полиномами на случай полиномиальных сплайнов.
В частности, разрабатывается численный алгоритм, являющийся обобщением алгоритма Ремеза, для построения полиномиальных сплайнов наилучшего приближения. Выводятся необходимые и доста-
точные условия оптимальности, являющиеся обобщением условий, полученных ранее М.Г. Тарашниным.
Далее проводятся численные эксперименты на тестовых функциях и на функциях, возникающих в некоторых конкретных приложениях. Выведенные необходимые и достаточные условия оптимальности подтверждают, что полученные полиномиальные сплайны являются сплайнами наилучшего приближения.
В одном из приложений (моделирование налогообложения) возникает потребность решения оптимизационной задачи при наличии ограничений (условная оптимизация). Большинство классических результатов полиномиального приближения, а также обобщенный алгоритм Ремеза, разработанный в данной диссертации на случай полиномиальных сплайнов, относятся к задачам безусловной оптимизации. Следовательно, также возникла потребность переформулировать исходную задачу, возникшую в приложении, как задачу безусловной оптимизации. Таким образом, также проводится попытка обобщения ранее полученных результатов на случай условной оптимизации.
Методы исследований. Для решения задач, рассматриваемых в диссертации, привлекаются классические и современные методы анализа. Проведенные исследования опираются на классические результаты П.Л. Чебышева, описывающие необходимые и достаточные условия оптимальности приближения полиномами и М.Г. Тарашнина, описывающие необходимые и достаточные условия оптимальности приближения полиномиальными сплайнами. Также применяются результаты исследований Е.Я. Ремеза и Ш.Ж. Валле-Пуссена, обобщение которых позволило сконструировать алгоритм для построения полиномиальных сплайнов наилучшего приближения. Также работа опирается на исследования В.М. Тихомирова, Г.П. Акилова, Ю.Н. Субботина, Н.П. Корнейчука, П.-Ж. Лорана и других исследователей.
Важную роль в исследовании сыграло использование аппарата негладкой анализа, являющегося в некотором смысле обобщением методов классического (гладкого) анализа. Аппарат негладкой оптимизации, используемый в данной работе, был разработан в исследованиях Т. Рокафеллара, В.Ф. Демьянова, A.M. Рубинова, Ф. Кларка, А. Баги-рова, Н.З. Шора, И.И. Еремина, Б.Н. Пшеничного и многих других исследователей.
Научная новизна результатов состоит в разработке теории и новых вычислительных алгоритмов решения задач приближения полиномиальными сплайнами. Исследование было проведено по следующим направлениям:
получены необходимых и достаточных условий оптимальности полиномиальных сплайнов;
доказан ряд теорем, позволяющих обобщить имеющийся алгоритм построения полиномов наилучшего приближения на случай сплайнов наилучшего приближения;
проведено исследование, позволяющее свести некоторый класс задач условной оптимизации, возникающий в некоторых приложениях, к задаче безусловной оптимизации, решение которой может быть найдено с помощью разработанного алгоритма;
создан пакет исследовательского программного обеспечения, реализующий сформированные в работе алгоритмы на ЭВМ. Работоспособность и эффективность принятого подхода и разработанного алгоритмического программного обеспечения подтверждена решением конкретных задач (тестовые задачи и задачи, возникающие в различных практических приложениях).
Практическая и теоретическая значимость. Полученные в диссертации результаты являются развитием теории аппроксимации непрерывных и дискретных функций (баз данных). Теоретическая значимость работы определяется тем, что данная работа является естественным продолжением классических исследований, проведенных П.Л. Чебышевым, Ш.Ж. Балле-Пуссеном и Е.Я. Ремезом в области приближения полиномами. В данной работе проводится обобщение некоторых результатов, полученных в случае приближения полиномами, на случай полиномиальных сплайнов.
Практическая значимость работы состоит в том, что в ней разрабатывается алгоритм, позволяющий аппроксимировать непрерывные (модельные) функции и дискретные функции (базы данных) функциями из класса кусочно-полиномиальных функций. Такая аппроксимация позволяет в некоторых случаях упростить численные эксперименты, заменив сложные по структуре функции их более простыми аппроксимациями, построенными с высокой точностью.
В одном из практических приложений (задачи налогообложения), изучаемых в данной работе, модельная функция должна быть аппроксимирована функциями определенного класса, а именно ломаными. Отличительная особенность данного приложения состоит в том, что никакие другие функции, кроме ломаных, не могут быть использованы в качестве приближающих функций.
В случае приближения дискретных функций (баз данных) возникает много практических приложений в области классификации, оптимизации хранения информации и других областях, связанных с обработкой и использованием имеющихся баз данных, размеры которых, благода-
ря развитию компьютерных технологий и автоматизации многих процессов, быстро растут.
Полученные практические результаты подтверждаются теоретическими исследованиями. Разработанные в диссертации методы и алгоритмы ориентированы на решение задач на базе широкодоступных персональных компьютеров.
Апробация работы. Диссертация в целом, а также ее отдельные положения и полученные результаты докладывались на XXIX, XXX и XXXI научных конференциях "Процессы управления и устойчивость" факультета прикладной математики и процессов управления (г. Санкт-Петербург), XI Всероссийской конференции "Математическое программирование и приложения" (г. Екатеринбург 1999), на международном симпозиуме Symposium in Industrial Optimization, Western Australia, Curtin University, Perth, Australia, 2003, на семинарах Института проблем машиноведения РАН, а также на семинарах кафедры Математической теории моделирования систем управления и кафедре Исследования операций СПбГУ.
Публикации. По результатам выполненных исследований опубликовано семь печатных работ. Автор также имеет девять печатных работ в области применения методов негладкой оптимизации к задачам исследования баз данных (в соавторстве).
Структура работы. Диссертационная работа состоит из введения, шести глав, заключения, списка литературы, включающего 64 наименования. Объем работы составляет 126 страниц машинописного текста.
Основные определения
Аппроксимация непрерывных на отрезке функций имеет важное значение, причем не только теоретическое, но и практическое. Цель дайной диссертации — исследовать некоторые вопросы приближения непрерывной на отрезке функции полиномиальными сплайнами.
Исходя из того, какие цели преследует исследователь, аппроксимируя ту или иную функцию, он приближает ее функциями определенного класса (полиномы, рациональные дроби, тригонометрические функции и так далее).
Полипомы и рациональные дроби обладают рядом недостатков, основной из которых состоит в том, что их поведение в окрестности какой-либо точки определяет их поведение в целом, поэтому разрабатываются другие аппараты приближения. Одним из таких аппаратов являются сплайны.
Сплайны представляют собой кусочно-полиномиальные функции, которые "склеены" из различных полиномов по заранее оговоренной схеме.
Точки склеивания расположены внутри отрезка, на котором мы приближаем непрерывную функцию.
Определение 1 Функция S(t)t заданная на отрезке [а, Ь], называется полиномиальным сплайном (или просто сплайном) степени т с внутренними узлами ві (г = 1, 2,... ,п— 1; а — $Q 9\ #2 ... вп-і вп = Ь), если па каждом из промежутков [9і-і,ві],і Є 1,...,п функция S(t) есть алгебраический полипом степени, не превышающей т, а в каоїсдой из точек ві некоторая производная 5 " (1 v т) может иметь разрыв.
Определение 1 Границы отрезка [а, Ь] будем называть внешними узлами полиномиального сплайна.
Определение 3 Точки склеивания полиномов, расположенные на сегменте (а,Ь), будем называть внутренними узлами сплайна.
Обычно от сплайнов требуют непрерывности во внутренних узлах. Иногда (при более тонком исследовании) во внутренних узлах требуют непрерывности первых к производных [7]. Определение 4 Разность между степенью сплайна и порядком наивысшей непрерывной на отрезке [а,Ь] производной называют дефектом сплайна. Приведем пример построения полиномиального сплайна. п т SM(A,t) = 00 + Yl Otf( -ft-i)+, С1-2-1) i=l j=m—d+1 где А = (ао;аіь )Яцт) Є Rmn+1 — вектор параметров сплайна, т — степень сплайна, d — дефект сплайна, 8І — внешние и внутренние узлы сплайна, где і — О,..., п, то есть отрезок [а, Ь\ разбит на п промежутков, наконец, Ш) (z), х {), О, х 0. Данный способ построения сплайна используется, например, в [18], при этом дефект исследуемых сплайнов равен единице.
Иногда требуется следующее уточнение к определению 1. Определение 5 Функция S(t), заданная на отрезке [а,Ь], называется полиномиальным спл,айном обобщенной (векторной) степени М = (т т ,... ,тп) с внутренними узлами ві {г = 1, 2,..., п - 1; а = в0 9Г в2 9п-\ &п = Ь), если на каждом из промежутков функция S{t) есть алгебраический полином степени, не превышающей гщ, а в каждой из точек 0;,г = 1,2,... ,п — 1 некоторая производная. S (1 v т) может иметь разрыв.
Если от сплайна требуется непрерывность в узлах, причем производные порядка А; 0 могут иметь разрыв, то полиномиальный сплайн векторной степени может быть построен следующим образом: SM(A,t) = а0 + о;Дгшп{Д} (9 /+, i=l з=і где А — (ао, &п,..., апт!1) Є R +l — вектор параметров сплайна, "/ = в І — внешние и внутренние узлы сплайна (і — 0,... ,п,), наконец,
Несмотря на некоторое усложнение, а именно введение rain{t, #;} вместо t, формулировка (1.2.2) имеет некоторые преимущества перед (1.2.1). При использовании формулировки (1.2.2) модель намного гибче, что позволяет варьирование степеней полиномов от интервалу к интервалу, что особенно важно при построении сплайнов, у которых степень полиномов на предшествующих интервалах превышает степень полиномов на последующих интервалах. Опишем подробнее некоторые преимущества (1-2.2) перед (1.2.1).
При использовании формулировки (1-2.2) для построения сплайна обобщенной степени М = (mi,... ,тп) необходимо у = 1 + S"=i SJ=i коэффициентов. При использовании формулировки (1-2.1) в общем случае необходимо 7i — 1+пт коэффициентов, где m = max{ml,..., m„}. Очевидно, что 7i 7 2. При использовании формулировки (1.2.2) на каждом г—м интервале коэффициенты а у непосредственно представляют коэффициенты соответствующих полиномов ад = оо+5 -б -1) . 3=1 где свободный члены а10,г = 1,... , п определяются по следующему правилу ttj, = а0, «о = Pt-i(9i-i),i 1 При использовании формулировки (1.2.1) коэффициенты соответствующих полиномов на каждом из интервалов являются некоторой комбинацией коэффициентов а0)%д = 1,... ,п, j = 1,... ,т, гдет = max{mi,... ,m„}.
Замечание 1.2.1 Введение попятил дефекта полиномиального сплайна в случае сплайна обобщенной (векторной) степени предсталлет некоторую сложность, так как в этом случае полиномы, представляющие соседние интервалы, не обязательно имеют одну и ту же степень. В данной диссертации изучаются аспекты, не зависящие от дефекта сплайна, поэтому мы опускаем введение понятия дефекта полиномиального сплайна а случае сплайна векторной степени.
Вообще имеется много определений сплайп-фупкций ([7], [8], [6]). Различия между формами представлений возникают из-за несходства задач, решения которых ищется в виде сплайнов (сглаживающие, интерполирующие или аппроксимирующие сплайн-функции).
Численные методы негладкой оптимизации
Одна из основных целей данной диссертации состоит в построении алгоритма для конструирования полиномиального сплайна наилучшего приближения. Данный алгоритм предусматривает работу со сплайнами с закрепленными узлами, В данной работе также приведены результаты некоторых экспериментон на случай сплайнов со свободными узлами (глава 5). Производится сравнение полученных результатов с результатами, полученными в других научных работах. Возникает потребность представить некоторые конкретные методы негладкой оптимизации, используемые в данной работе.
Метод дискретного градиента
Метод дискретного градиента был предложен А, Багировым. В данном алгоритме квазидифференциалы используются для построения направления спуска (направление спуска — приближение направления наискорейшего спуска [23], [31], [32]). Когда направление спуска найдено, необходимо минимизировать функцию вдоль выбранного направления. Методы одномерной минимизации могут быть найдены в [29] или [22].
В данной диссертации используется готовая программа, написанная для метода дискретного градиента. Автор диссертации работает с данной программой, скорректировав ее на случай полиномиальных сплайнов.
Метод отсекающего угла
Данный метод является некоторым обобщением метода отсекающих плоскостей. Первоначально было доказано, что этот метод может быть использо Глава 2. Негладкая оптимизация ван для минимизации возрастающих положительно однородных первой степени функций [20] (Increasing Positively Homogeneous of degree one (IPH) functions), определенных на единичном симплексе. Позже было показано, что процедура может быть обобщена (путем некоторой специальной трансформации функций) на случай липшецевых функций, определенных па единичном симплексе [36].
Метод отсекающего угла является методом глобальной оптимизации. Одним из главных недостатков данного метода является то, что его работа сильно затрудняется, если число переменных велико. Рекомендуется использовать не более чем 10 переменных.
Аппроксимации полиномами наилучшего приближения (чебышевская аппроксимация) 3.1 Необходимые и достаточные условия в задачах аппроксимации непрерывной на отрезке функции полиномом наилучшего приближения Рассмотрим на отрезке [я, Ь] функцию /(/-). Будем аппроксимировать ее полиномом степени ті, который имеет вид Рп(А, t) = аа + агt + ... + antn. Рассмотрим следующую задачу maxF(At) - min, (3.1.1) где F{A, t) = f(t) - Ра-!(А, t), A = (an,..., an) Є Rn+l. Задача (3.1.1) — задача чебышевской аппроксимации, Определение 18 Полином, являющийся решением задачи чебышевской аппроксимации, называется полиномом наилучшего приближения функции f(t) на отрезке \а,Ь]. Глава 3. Аппроксимации полиномами наилучшего приближения Рассмотрим эквиналентную задачу max -F2(A,t) t[a,b] 2 V mm , Обозначим p(A) — max -(F2(J4,)) . Очевидно, функция р(А) является вы (Є[а,Ь] [2 J пуклой па Лп+1. Зафиксируем вектор A = (aj), ...а). Пусть максимум по t функции (F2(A,t)) достигается в точках U, таких, что і Є I,U Є [a, b]. Далее для простоты введем следующие обозначения: F{A,U) = F{ti), ИУІ-F, і Є I. Субдифференциал функции р(А) имеет вид: Qtp{A ) =-со I F \zb(F{U)) ( 1 U ІЄІ V г1 J При этом необходимое условие минимума субдиффсренцируемой функции р(А) имеет вид ОпЄдір(А )- (3.1.2) Функция р(А) — выпуклая, поэтому условие (3.1.2) является одновременно и достаточным условием минимума функции р(А). Условие (3.1.2) означает, что существуют неотрицательные коэффициенты а\ : X ai = 1 a i — 0 такие, что выполняется следующее условие іІ FsignFiU) Е = on +1 ІЄ/ uyj По теореме Каратеодори 0„+i может бытт получен как выпуклая комбинация не более чем n + 2 крайних точек субдифференциала, являющегося выпуклым компактным множеством. Пусть их будет к, тогда переобозначим эти точки, упорядочив их по возрастанию: а ti t2 ... th b.
Алгоритм Ремеза
Доказательство: как и при доказательстве теоремы будем рассматривать сплайн только в пределах минимальной цепочки, предполагая, что данная цепочка известна и состоит из п интервалов. Очевидно, что если первый (последний) интервал не входит в минимальную цепочку, то необходимые и достаточные условия оптимальности полностью совпадают с условиями второй теоремы Тарашнина. Поэтому далее рассматривается случай, когда первый (последний) интервал входит в минимальную цепочку.
Предположим вначале, что закреплен левый конец. Если одной из точек максимального уклонения является точка ( = а, то, очевидно, приближение не может быть улучшено. Теперь перейдем к случаю, когда точка $Q — а не является точкой максимального уклонения. В данном случае сплайн может быть построен следующим образом SM(A,l) = уо + а (тш{гД} - 0 +, І=І j=i где т/о — значение сплайна в точке га, то есть фиксированная величина. Аналогично системе (4.1.7) имеем линейную однородную систему, матрица которой Pj, может быть получена из матрицы Р системы (4.1.7) при вычеркивании первой строки. Мы можем повторить все те же рассуждения, что и при доказательстве второй теоремы Тарашнина, работая с матрицей Р . Действительно, в этом случае поведение сплайна на любом из интервалов (кроме первого) описывается точно так же как и в случае второй теоремы Тарашнина, а поведение па первом интервале происходит по тому же закону, что и на внутренних интервалах. Таким образом, на первом интервале имеется іщ точек максимального уклонения.
Переходим к сплайнам с закрепленным правым концом. Отметим, что сплайн может быть представлен следующим образом (альтернатива формуле (4.1.1)) SM(B,t) = b0 + J] Д-тах{(, ( )- +. (4.1.15) где В = (bQ, ЬЦ, ..., fenm„) Д7+1 — вектор параметров сплайна, -у = =1 ті 8І — внешние и внутренние узлы сплайна, где і = 0,..., п, то есть отрезок [га, Ь] разбит на п промежутков, наконец, «( ))+ = (х), х 0, О, х 0.
Данный сплайн сконструирован по той же схеме, что и (4.1.1), но движение происходит в обратную сторону (от точки Ь к точке а). Очевидно, что марица PR
Аппроксимация полиномиальными сплайнами будет иметь ту же структуру, что и матрица Р , но интервалы перснумеруются в обратном порядке. Повторим те же рассуждения, что и и случае закрепленного левого конца. Таким образом, следствие полностью доказано.
Следствие 4.1.3 Для того, чтобы сплайн д (х) обобщенной векторной степени М = (ті,..., m() с закрепленным левым и правым концом был оптимолъ-иым, необходимо и достаточно, чтобы, выполнялось одно из условий:
1)на одном из отрезков [0i-\.9j\ найдется ЇЇІІ + 2 точки максимального уклонения сплайна д {х) от приближаемой функции f(x), причем функция S(x) = f(x) — д"{х) имеет чередующиеся знаки в этих точках; если і—й интервал является первым или последним, то таких точек nij -4- 1, если это единственный интервал, то таких точек пц.
2)найдутся интервалы такие, что разность {j — г) минимальна, на которых точки максимального уклонения расположены следующим образом: на і м интервале лежит по крайней мере т + 1 точка алътернанса, на j—м интервала лежит по крайней мере mj + 1 точка алътернанса, па всех внутренних интервалах -по крайней мере по т точек шшперианса (к — i + l,...,j — 1), если пРи этом і = 1, то на ъ—м интервале лежит по крайней мере тючек алътернанса, если j = п, то на j—м интервале лежит по крайней мере rrij точек алътернанса.
Доказательство: очевидно, что если минимальная цепочка состоит из более чем одного интервала, то данное утверждение верно (прямое следствие из предыдущего утверждения). Остается рассмотреть случай, когда минимальная цепочка состоит из единственного интервала.
В данном случае сплайн может быть представлен как обычный полином Sm(t) степени m на отрезке [0o,#iL Предположим, что (0о) — Уо 3(ві) = у\, тогда полином Sm(t) может быть где точки tk,k Є I — точки, в которых достигается максимум уклонения приближаемой функции от сплайна. Пусть таких точек будет кт. По теореме Ка-ратеодори, 0m_i всегда можно сформировать с использованием не более чем m крайних точек субдифференциала. Сформируем соответствующую линейную однородную, систему и изучим ее возможные положительные решения
Умножим предпоследнюю ((тта — 2)—ю) строку матрицы Р на {в\ — во) и вычтем из последней ((т— 1)—й), затем умножим ((го — 3)—ю) строку матрицы Р на (#] — во) и вычтем из (т — 1)—й). Продолжим процесс, окончательно получим эквивалентную матрицу (і -ваХі -вг) \ (і -воПі -вг) Хік-воГ-Чк-вг) ... (tk„, - во)т 1(1кт в J
Отмстим, что если одной из точек максимального уклонения является точка #о или точка 8-і, то полученный сплайн является оптимальным (приближение не может быть улучшено). Если ни одна из точек максимального уклонения не совпадает с во или 9\, то на отрезке [ва, ві\ существует по крайней мере т точек максимального уклонения, причем знак уклонения в этих точках чередуется. Таким образом, следствие доказано.
Задача построения линейного сплайна (ломаной), удовлетворяющего условию альтернанса
Так как степень полинома . не превышает тг, то имеем следующее равенство: sign52(02) = signS2(?J. (4.2.25) Продолжим процесс далее, на п—м интервале имеем mn + 1 точку базиса, знак уклонения в точках базиса чередуется. Полипом Sn меняет знак по крайней мерс mn + 2 раза на интервале [0„_і,Ь] : sign (5„(0„_i)) = (-lj sign (ЗД)), і = 1,..., mn + 1. (4.2.26)
Это означает, что полином степени, не превышающей mn, имеет по крайней мере mn + l корень на интернале [0n_i, Ь]. Полученное противоречие доказывает теорему па случай, если замена узла произошла па одном из крайних интервалов.
Предположим теперь, что замена точки базиса произошла на одном из внутренних интервалов. Пусть это будет к ый интервал. Проведя рассуждения, аналогичные тем, что были использованы при доказательстве первой части ТСОреМЫ, ПОЛуЧИМ, ЧТО ПОЛИПОМ Sk = В\ — 5 СТепеПИ, НЄ превышающей ГПк, имеет на интервале (6 -1,6 ) по крайней мере т — 1 корней. Возможны два случая. 1. Выполняются следующие условия: полином Sk меняет знак при переходе от левой граничной точки 0j._i к крайней левой точке базиса l\\ полином Sk меняет знак при переходе от правой граничной точки 6 к крайней правой точке базиса f . В данной ситуации полином Sp., степень которого не превышает т , имеет по крайней мере пік + 1 корень на интервале [0 -і, Ok], что невозможно.
Хотя бы одно из условий случая 1 не выполняется.
Предположим для определенности, что не выполняется второе условие случая 1 (аналогичные рассуждения могут быть приведены, если не выполняется первое условие случая 1). Данная ситуация аналогична той, которая возникла при доказательстве первой части теоремы (случай замены базиса на одном из крайних интервалов, равенство (4.2.25)). Мы можем повторить те же самые рассуждения, двигаясь по цепочке к крайнему правому интервалу, пролучая противоречие.
Данное противоречие доказывает теорему на случай замены точки базиса на одном из внутренних интервалов минимальной цепочки. Таким образом, теорема полностью доказана. Следствие 4.2.5 Если ни одна из точек базиса не совпадает ни с одним из внутренних узлов сплайна, то величина абсолютного уклонения при замене базиса согласно предложенному правилу возрастает. Доказательство: вытекает из доказательства теоремы. Действительно, уже было доказано, что уклонение не убывает, покажем, что оно не может оставаться без изменения.
Вначале предположим, что замена произошла па одном из крайних интервалов. Тогда на другом крайнем старый сплайн совпадет с новым, так как соответствующие старый и новый полиномы степени, не превышающей mi (или т„) совпадают по крайней мере в т + 1 (или тп + 1) точке (уклоняются от приближаемой функции на одну и ту же величину в точках базиса, причем знак уклонения не меняется). Таким образом, полипомы будут совпадать и во внутреннем узле в\ (или 0„_і). На следующем интервале соответствующие полиномы также совпадают, так как они совпадают в точках базиса и во внутреннем узле, не совпадающим ни с одной из точек базиса. Продолжаем процесс далее, пока не достигнем интервала, на котором произошла замена базиса. На данном интернале имеется т„ (или mi) точек базиса, оставшихся неизменными. В этих точках, а также в соответствующем внутреннем узле сплайна, полиномы совпадают, следовательно, полиномы должны совпадать и на всем интервале, что невозможно, так как во введенной в базис точке старый полином уклонялся на большую по абсолютному значению величину, чем новый.
Если замена базиса произошла на одном из внутренних узлов, то предлагается двигаться с двух сторон к данному интервалу, проводя аналогичные рассуждения. В результате также получаем противоречие.
Отметим, что данное следствие справедливо также и в случае, когда уклонение в точках базиса, построенного по начальному сплайну, нулевое.
Таким образом, если в качестве новой точки базиса не выбирается ни один из внутренних узлов, то па каждом шаге получаются новые базисы и новые сплайны, так называемого "зацикливания" не происходит. Требование исключить из рассмотрение базисы, не содержащие внутренние узлы сплайна, естественно, оно продиктовано также условием из следствия 4.1.1.
В теорерии чебышевской аппроксимации (полиномы) важное место занимает теорема Валле-Пуссена [5], [48]. Докажем аналогичную теорему на случай полиномиальных сплайнов, предполагая, что минимальная цепочка известна.
Теорема 4.2.5 (обобщение теоремы Валле-Пуссена). Предположим, что нам известна минимальная цепочка, состоящая из п последовательных интервалов, полиномиалънвй сплайн имеет векторную степень М — (mi,...,mn). Если для некоторого полиномиального сплайна м{і) существует соответствующий базис. nm„+l}i [4.2.27) в точках которого разность Д{1) = f(t) — $ м(і) принимает чередующиеся по знаку значения, то mi\\f-SM\\cM Mn (4-2.28) гдеД{Т) =min{A(timi+i),A(f,im„+1),A(tij), і = 1,..., я, j = 1,..., тщ) Доказательство: предположим противное: выполняется следующее неравенство: Ш/-мсіаЧ Д(Г), (4.2.29) где 5 — полиномиальный сплайна наилучшего приближения.
