Обобщение алгоритма Ремеза на случай полиномиальных сплайнов

1.1 Мотивация.

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

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

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

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

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

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

В настоящей работе разрабатывается и тестируется алгоритм, позволяющий аппроксимировать непрерывные и дискретные функции (базы данных) полиномиальными сплайнами в равномерной метрике. Данное исследование является естественным продолжением известных работ П. Л. Чебышева (знаменитый ме-муар «Теория механизмов, известных под именем параллелограммов», опубликованный в 1853 году, [19], [53]), Валле-Пуссена [48], Е. Я. Ремеза [10|, [49], ставшими в некотором смысле классикой полиномиального приближения. В данной работе делается попытка обобщения некоторых результатов, полученных в теории приближения полиномами, на случай полиномиальных сплайнов, а также более поздних результатов, полученных М. Г. Тарашниным в 90-х годах двадцатого века [18].

Аппроксимация полиномиальными сплайнами имеет много практических приложений, таким образом, проведенное исследование представляет теоретический и практический интерес.

Целью диссертационной работы является проведение исследований, направленных на построение численного алгоритма, позволяющего аппроксимировать непрерывные и дискретные функции (базы данных) полиномиальными сплайнами. Большая часть проведенного исследования состоит в обобщении некоторых классических результатов теории приближения полиномами [19], [53], [48], [35], [10], [49] на случай полиномиальных сплайнов.

В частности, разрабатывается численный алгоритм, являющийся обобщением алгоритма Ремеза, для построения полиномиальных сплайнов наилучшего приближения. Выводятся необходимые и достаточные условия оптимальности, являющиеся обобщением условий, полученных ранее М. Г. Тарашниным [18].

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

В одном из приложений (моделирование налогообложения, [4]) возникает потребность решения оптимизационной задачи при наличии ограничений (условная оптимизация). Большинство классических результатов полиномиального приближения относятся к задачам безусловной оптимизации, полученные обобщения на случай полиномиальных сплайнов также разработаны для решения задач безусловной оптимизации. Следовательно, также возникла потребность переформулировать исходную задачу, возникшую в приложении, как задачу безусловной оптимизации. Таким образом, также проводится попытка обобщения ранее полученных результатов на случай условной оптимизации.

Для решения задач, рассматриваемых в диссертации, привлекаются классические и современные методы анализа. Проведенные исследования также опираются на классические результаты П. Л. Чебышева [19], [53], Д. Райса [35], описывающие необходимые и достаточные условия оптимальности полиномами и М. Г. Тарашнина [18], описывающие необходимые и достаточные условия оптимальности полиномиальными сплайнами. Также применяются результаты исследований Е. Я. Ремеза [10], [49] и Валле-Пуссена [48], обобщение которых позволило сконструировать алгоритм, позволяющий строить полиномиальные сплайны наилучшего приближения.

Важную роль в исследовании сыграло использование аппарата негладкого анализа, являющегося в некотором смысле обобщением методов классического (гладкого) анализа. Аппарат негладкой оптимизации, используемый в данной работе, был разработан в исследованиях В. Ф. Демьянова [2], A.M. Рубинова [32], А. Багирова [22], [23], [21], [31], [32], Ф. Кларка [57], Н. З. Шора [63], И. И. Еремина [55], Б. Н. Пшеничного [58], [59], [60] и многих других исследователей.

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

• получены необходимые и достаточные условия оптимальности полиномиального сплайна;

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

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

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

Теоретическая значимость работы определяется тем, что данная работа является естественным продолжением классических исследований, проведенных П. Л. Чебышевым, Валле-Пуссеном и Е. Я. Ремезом в области приближения полиномами. В данной работе проводится попытка обобщения некоторых результатов, полученных в случае приближения полиномами, на случай полиномиальных сплайнов. Также работа опирается на исследования В. М. Тихомирова [64], Г. П. Акилова [54], Ю. Н. Субботина [61], Н. И. Черных [62], B. J1. Макарова, В. В. Хлобыстова [8], Н. П. Корнейчука [5], [6], В. Н. Малоземова [3], А. Б. Певного [7], П.-Ж. Лорана [56] и других исследователей.

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

В случае приближения дискретных функций (баз данных) возникает много практических приложений в области классификации, оптиматизации хранения информации и других областях, связанных с обработкой и использованием имеющихся баз данных, размеры которых, благодаря развитию компьютерных технологий и автоматизации многих процессов, быстро растут [25], [26], [27|, [30], [34], [37], [38], [39], [40], [41], [43], [44].

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

Диссертация в целом, а также ее отдельные положения и полученные результаты докладывались на XXIX, XXX и XXXI научных конференциях Процессы управления и устойчивость факультета прикладной математики и процессов управления (г. Санкт-Петербург), XI Всероссийской конференции «Матетати-ческое программирование и приложения» (г. Екатеринбург 1999), на международном симпозиуме Symposium in Industrial Optimization, Western Australian, Curtin University, Perth, Australia, 2003, на международной конференции Устойчивость и процессы управления, посвященной 75-летию со дня рождения В. И. Зубова, на семинаре Института проблем машиноведения РАН, а также на семинарах кафедры Математической теории моделирования систем управления (факультет ПМ-ПУ) и кафедры Исследования операций (математико-механичсский факультет) СПбГУ.

По результатам выполненных исследований опубликовано восемь печатных работ ([11]-[17], [42], [43]). Автор также имеет девять печатных работ в области применения методов негладкой оптимизации к задачам исследования баз данных ([25], [26], [27], [34], [37], [38], [39], [40], [44]).

7.6 Заключение.

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

В случае приближения непрерывной функции предлагалось использовать метод дискретного градиента (локальный метод негладкой оптимизации). Основной недостаток данного метода состоит в том, что разные начальные точки ведут к разным решениям (разные локальные минимумы), кроме того, нет гарантии, что полученное решение является глобальным минимумом. Структура данного метода такова (см. [22], [23]), что он уходит из точек перегиба, а также из относительно неглубоких точек локального минимума. В одном из наших экспериментов метод дискретного градиента нашел точку глобального минимума. В случаях, когда найденная точка являлась лишь локальным минимумом, результаты также были довольно точными.

В случае дискретной аппроксимации сравниваются полученные результаты (новый алгоритм, предлагаемый автором данной диссетации) с результатами, полученными ранее (метод Г. Белякова).

Предлагаемый алгоритм определяет автоматически необходимое количество интервалов. Данный алгоритм использует комбинацию метода дискретного градиента и метода Qi^-декомпозиции. Во всех изучаемых примерах результаты, полученные новым алгоритмом лучше, чем результаты, полученные ранее.

Рис. 7.2: Сплайн пятой степени: Пеззак.

Рис. 7.3: Сплайн третьей степени: Титан.

Глава 8.

Заключение

и направления для дальнейших исследований.

Подведем итоги проделанной работы и обозначим возможные направления по продолжению исследований.

В данной диссертации изучаются теоретические и практические аспекты приближения непрерывных и дискретных функций полиномиальными сплайнами. Работа начинается с построения необходимых и достаточных условий оптимальности полиномиального сплайна обобщенной (векторной) степени. Приведенное исследование использует аппарат негладкой оптимизации и негладкого анализа, разработанные во второй половине двадцатого века. Построение необходимых и достаточных условий оптимальности является продолжением и обобщением работ П. Л. Чебышева (необходимые и достаточные условия оптимальности приближения полиномами) и М. Г. Тарашнина (необходимые и достаточные условия оптимальности приближения полиномиальным сплайном, обычной (невекторной) степени), кроме того, получены необходимые и достаточные условия оптимальности на случай закрепленного правого и (или) левого конца сплайна.

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

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

Исследуемые функции можно разделить на несколько групп:

• приближение непрерывных на отрезке функций (безусловная оптимизация), приведены примеры с двумя группами функций (функция Гаусса, часто используемая в математическом моделировании и приложениях, а также осциллирующая функция, приближение таких функций, как правило, представляет некоторую сложность, особенно в случае построения полиномов наилучшего приближения);

• приближение дискретных функций (безусловная оптимизация);

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

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

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

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

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

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

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

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