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

Сухорукова, Надежда Владимировна

Обобщение алгоритма Ремеза на случай полиномиальных сплайнов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Сухорукова, Надежда Владимировна АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Санкт-Петербург МЕСТО ЗАЩИТЫ

2005 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

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

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

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

На правах рукописи

С^Я^СлПу'

Сухорукова Надежда Владимировна & (/

ОБОБЩЕНИЕ АЛГОРИТМА РЕМЕЗА НА СЛУЧАЙ ПОЛИНОМИАЛЬНЫХ СПЛАЙНОВ

01.01.09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

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

Работа выполнена на кафедре математической теории моделирования систем управления факультета прикладной математики - процессов управления Санкт-Петербургского государственного университета

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

профессор Демьянов Владимир Федорович

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

кандидат физико-математических наук, профессор Васильев Леонид Васильевич;

Ведущая организация: Институт проблем машиноведения РАН

Защита состоится « » 2005г. в мин. на за-

седании диссертационного совета К-212.232.07 по защитам диссертаций на соискание ученой степени кандидата физико-математических наук при Сянкт-Петербургском государственном университете пи адресу: 199034, Санкт-Петербург, Васильевский Остров, 10-я линия, дом 33, ауд

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

Автореферат разослан «

» ОкТЯЪрЛ 2005 г.

Ученый секретарь диссертационного совета, доктор физ.-мат. наук, профессор " Горьковой В.Ф.

Ш Ъ255~

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

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

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

точные условия оптимальности, являющиеся обобщением условий, полученных ранее М.Г. Тарашниным.

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

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

Методы исследований. Для решения задач, рассматриваемых в диссертации, привлекаются классические и современные методы анализа. Проведенные исследования опираются на классические результаты П.Л. Чебышева, описывающие необходимые и достаточные условия оптимальности приближения полиномами и М.Г. Тарашнина, описывающие необходимые и достаточные условия оптимальности приближения полиномиальными сплайнами. Также применяются результаты исследований Е.Я. Ремеза и Ш.Ж. Валле-Пуссена, обобщение которых позволило сконструировать алгоритм для построения полиномиальных сплайнов наилучшего приближения. Также работа опирается на исследования В.М. Тихомирова, Г.П. Акилова, Ю.Н. Субботина, Н.П. Корнейчука, П.-Ж. Лорана и других исследователей.

Важную роль в исследовании сыграло использование аппарата негладкой анализа, являющегося в некотором смысле обобщением методов классического (гладкого) анализа. Аппарат негладкой оптимизации, используемый в данной работе, был разработан в исследованиях Т. Рокафеллара, В.Ф. Демьянова, A.M. Рубинова, Ф. Кларка, А. Баги-рова, Н.З. Шора, И.И. Еремина, Б.Н. Пшеничного и многих других исследователей.

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

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

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

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

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

Практическая и теоретическая значимость. Полученные в диссертации результаты являются развитием теории аппроксимации непрерывных и дискретных функций (баз данных). Теоретическая значимость работы определяется тем, что данная работа является естественным продолжением классических исследований, проведенных П.Л. Чебьппевым, Ш.Ж. Балле-Пуссеном и Е.Я. Ремезом в области приближения полиномами. В данной работе проводится обобщение некоторых результатов, полученных в случае приближения полиномами, на случай полиномиальных сплайнов.

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

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

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

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

Апробация работы. Диссертация в целом, а также ее отдельные по-I ложения и полученные результаты докладывались на XXIX, XXX и

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

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

Структура работы. Диссертационная работа состоит из введения, шести глав, заключения, списка литературы, включающего 64 наименования. Объем работы составляет 126 страниц машинописного текста.

СОДЕРЖАНИЕ РАБОТЫ Во введении приводится формулировка проблемы аппроксимации ( непрерывных и дискретных функций (баз данных) полиномиальными

сплайнами, обоснована актуальность проводимых исследований, кратко описаны возможные области практического применения аппроксимации полиномиальными сплайнами, определены цели работы и приведены общие формулировки задач, рассматриваемых в работе. Также выполнен краткий обзор научных публикаций по теме диссертации. В частности, вводятся следующие определения. Определение 1 Функция S(t), заданная на отрезке [<2,6], называется полиномиальным сплайном (или просто сплайном) степени Ш с внутренними узлами 6t

(i = l,...,n-l;a = 0o <вх <...<вп =Ь),

если на каждом из промежутков [0,^,0], ' = 1 ,•••, и функция есть алгебраический полином степени, не превышающей т , а в каждой из точек 01 некоторая производная некоторого порядка V может иметь разрыв.

Определение 2 Границы отрезка \_а,Ь~\ будем называть внешними узлами полиномиального сплайна.

Определение 3 Точки склеивания полиномов, расположенные на сегменте (а,Ь) будем называть внутренними узлами сплайна.

Определение 4 Разность между степенью сплайна и порядком наивысшей непрерывной на отрезке [а,6] производной называют дефектом сплайна.

Определение 5 Функция 5(7), заданная на отрезке [а, 6], называется полиномиальным сплайном обобщенной (векторной) степени М = (т1 ,...,тп)с внутренними узлами 61

(/ = 1,...,п — 1;а — 0О <0Х < ... < 0п —Ь), если на каждом из промежутков [0,, ' = 1,.•.,и функция 5"(0 есть алгебраический

полином степени, не превышающей ТП1, а в каждой из точек д1 некоторая производная некоторого порядка V может иметь разрыв.

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

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

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

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

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

Теорема 4.1.2 (вторая теорема Тарашнина). Для того, чтобы сплайн g (0 векторной степени М = (miтп ) был оптимальным, необходимо и достаточно, чтобы выполнялось одно из условий: 1) на одном из отрезков \0x l, 0t ] найдется Ш1 + 2 точки максимального уклонения сплайна g (t) от приближаемой функции ДО,

причем функция fit) — g (t) имеет чередующиеся знаки в этих точках;

2) найдутся интервалы [0, л, в, ] и , в^ ] такие, что

1 < i < j < П и разность j — i минимальна, на которых точки максимального уклонения расположены следующим образом: на i — м интервале лежит по крайней мере ntl +1 точка альтернанса,

на j — м интервале лежит по крайней мере +1 точка альтернанса, на всех внутренних интервалах (строго между / — ми j — м интервалами) — по крайней мере по Шк точек альтернанса (i < к < j).

Из представленной теоремы вытекают следующие следствия.

Следствие 4.1.1 Точки максимального уклонения, принадлежащие минимальной цепочке, не могут совпадать ни с одним из внутренних интервалов.

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

Следствие 4.1.2 Для того, чтобы сплайн g (0 обобщенной векторной степени М = (т)тп) с закрепленным левым (правым)

концом был оптимальным, необходимо и достаточно, чтобы выполнялось одно из условий:

1) на одном из отрезков , в1 ] найдется т1 + 2 точки максимального уклонения сплайна ё (0 от приближаемой функции /ХО» причем функция / (/) — g (?) имеет чередующиеся знаки в этих точках; если I — й интервал является первым (последним), то таких точек

т1 +1

2) найдутся интервалы , в1 ] и такие, что

1 </<_/< И и разность у — I минимальна, на которых точки максимального уклонения расположены следующим образом: на / — м интервале лежит по крайней мере ТП1 +1 точка альтернанса,

на j — м интервале лежит по крайней мере т] +1 точка альтернанса, на всех внутренних интервалах — по крайней мере по тк точек альтернанса (I < к < /), если при этом 1 = 1 ] = п , то на / — м интервале лежит по крайней мере т точек альтернанса (на ] — м интервале лежит по крайней мере гп] точек альтернанса).

Следующее утверждение обобщает ранее представленную теорему на случай, когда оба конца сплайна закреплены.

Следствие 4.1.3 Для того, чтобы сплайн g (V) обобщенной векторной степени М = (т[,..., тп ) с закрепленным левым и правым

концом был оптимальным, необходимо и достаточно, чтобы выполнялось одно из условий:

1) на одном из отрезков \01 л, О ] найдется ТП1 + 2 точки максимального уклонения сплайна g (0 от приближаемой функции f(.i)■> причем функция — Я (0 имеет чередующиеся знаки в этих точках; если / — й интервал является первым или последним, то таких точек т1 +1 , если это единственный интервал, то таких точек т(.

2) найдутся ] и , в] ] такие, что 1 - г < У - " и раз-

ность / — i минимальна, на которых точки максимального уклонения расположены следующим образом:

на ? — м интервале лежит по крайней мере т1 + 1 точка альтернанса, на у-м интервале лежит по крайней мере т / +1 точка альтернанса, на всех внутренних интервалах — по крайней мере по тк точек альтернанса (/ < к < / ), если при этом г = 1 , то на / — м интервале лежит по крайней мере т1 точек альтернанса. если _/ = п, то на на _/ — м интервале лежит по крайней мере т} точек альтернанса.

Вводятся следующие определения.

Определение 20 Базисом полиномиального сплайна обобщенной (векторной) степени М = {т],...,тп), заданного на п интервалах,

будем называть совокупность точек t™^+x = \,...ТП1, та-

кую что выполняется следующее неравенство

а < ^ < ... < < <9, < < ... < ^ < в2 < ... <

<вп_1<^п<...<с+1<ь.

Определение 21 Базисом полиномиального сплайна обобщенной (векторной) степени , Шп) с закрепленным левым и

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

М = (тх,..., Шп ) со свободными концами путем вычеркивания одной из точек, соответствующей первому и (или) последнему интервалу соответственно.

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

Теорема 4.2.1 Для любого базиса полиномиального сплайна векторной степени М = (ш1,...,тп) всегда может быть построен единственный полиномиальный сплайн того же порядка, удовлетворяющий условию альтернанса в точках базиса.

Далее приводится несколько следствий к данной теореме.

Следствие 4.2.1 Оптимальный полиномиальный сплайн существует.

Следствие 4.2.2 Для любого базиса полиномиального сплайна

степени М = (т1,..., Шп) с закрепленным левым и (или) правым

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

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

Предположим, что существует интервал точки базиса на котором представлены точками 7^° = ,..., ? ° } , если 1 < / < П, то есть на внутренних интервалах или точками 7]° = + если

/ = 1 или /= П, то есть на одном их крайних интервалов.

Предположим также, что на этом интервале существует точка

^ £ , такая что абсолютное уклонение приближаемой функции от

соответствующего полинома в этой точке больше, чем в точках

альтернанса (мы предполагаем также, что точка ( не является одним из внутренних узлов сплайна). Если при этом на данном интервале

существует точка базиса t е (ближайшая к точке t слева или справа), знак уклонения в которой совпадает со знаком уклонения в точке t. В этом случае предлагается ввести в базис точку I вместо

точки сохраняя остальные точки базиса неизменными.

Далее доказывается важная теорема, определяющая поведение сплайнов, построенных по новым базисам.

Теорема 4.2.2 Знак уклонения в точках базиса не изменится при замене базиса согласно предложенному правилу.

Теорема 4.2.3 Величина абсолютного уклонения при замене базиса согласно предложенному правилу не убывает.

Далее идет важное следствие.

Следствие 4.2.1 Если ни одна из точек базиса не совпадает ни с одним из внутренних узлов сплайна, то величина абсолютного уклонения при замене базиса согласно предложенному правилу возрастает.

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

Приведены также некоторые уточнения на случай, когда уклонение в точках сплайна нулевое.

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

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

сплайна S м (t) существует соответствующий базис

Т — {t\\,•• •»¿Imj+I 5 ^21 '•••'^nl » • • • »'nm„+l } , В ТОЧКЭХ КОТОрОГО

разность A(i) = f(t) — S м (t) принимает чередующиеся по знаку значения, то

Д (Г) = min {Д(flmi +1), Д(tnmn +1), А(/„ ), i = 1,... n, j = 1,... m,}.

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

Обобщенный алгоритм Ремеза

Шаг 1. Выбирается начальный базис.

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

Шаг 3. Обновляем базис согласно сформулированному правилу и повторяем процесс, начиная со второго шага.

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

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

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

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

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

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

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

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

В заключении данной главы приводится численный пример: приближается функция fit) = sin t на интервале [0,6], с внутренними узлами 2 и 4, векторная степень полиномиального сплайна М = (2,2,2) . Работа алгоритма подробно описывается. В результате полученный сплайн удовлетворяет условию оптимальности.

Глава 5 посвящена численным экспериментам по приближению непрерывных и дискретных функций.

Среди непрерывных функций выбраны две функции:

• функция Гаусса у = е 2 , часто встречающаяся во многих приложениях;

• t-939

• функция у = Sin/Я"-— , являющаяся сильно ос-

(¿ + 0.61)2

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

Среди баз банных рассматривались две базы данных (база данных Пеззака и Нагревание Титана). Обе базы данных доступны для загрузки через Интернет.

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

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

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

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

Глава 7 посвящается построению полиномиальных сплайнах в несколько отличающихся условиях:

• рассматриваются сплайны со свободными узлами;

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

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

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

ЗАКЛЮЧЕНИЕ

Основными результатами, вынесенными на защиту, являются следующие.

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

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

3. Создан пакет исследовательского программного обеспечения, позволяющего численно реализовать разработанный алгоритм.

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

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

6. Исследованы некоторые модели (комбинации нескольких методов), позволяющие оптимизировать расположение узлов сплайна.

По теме диссертации опубликованы следующие работы:

1. Сухорукова Н.В.. Применение квазидифференциалов к задачам аппроксимации непрерывных функций // Труды XXIX научной конференции Процессы Управления и Устойчивость: издательство Санкт-Петербургского университета, 1998, с. 388-390.

2. Сухорукова Н.В., Изучение задачи восстановления налоговой шкалы по шкале средних ставок // Труды XXX научной конференции Процессы Управления и Устойчивость: издательство Санкт-Петербургского университета, 1999, с. 499-505.

3. Сухорукова Н.В., Обобщение алгоритма Ремеза на случай ломаных // Труды XXXI научной конференции Процессы Управления и < Устойчивость: издательство Санкт-Петербургского университета,

2000, с. 482-484.

4. Сухорукова Н.В., Восстановление налоговых шкал по модельной шкале средних ставок XI Всероссийская конференция "Математическое программирование и приложения", Екатеринбург, 1999.

5. Сухорукова Н.В., Необходимые и достаточные условия оптимальности приближения непрерывных функций функциями определенного класса // Вестник Санкт-Петербургского университета, 2002, с. 66-73.

6. N. Soukhoroukova, Polynomial splines and data approximation // L. Caccetta, V. Rehbock, Industrial Optimization, Vol 1, Proceedings

of Symposium in Industrial Optimization, Western Australian, Centre of Excellence in Industrial Optimisation (WACEIO), Curtin University, Perth, Australia, 2003, p. 282-291.

Сухорукова H.В., Задача построения полиномиального сплайна, удовлетворяющего условиям чебышевской интерполяции // Вестник молодых ученых, 2'2003, Серия Прикладная матетатика и механика 1 '2003, с. 42-46.

ЛР№ 040815 от 22 05 97 Подписано в печать г Формат бумаги 60x84 1/16 Бумага офсетная

Печатьризографическая Объем 1 пл. Тираж 100экз Заказ№3652. Отпечатано в отделе оперативной полиграфии НИИХ СПбГУ с ориганал-макета заказчика 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 26

»20 0 60

РНБ Русский фонд

2006-4 18584

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Сухорукова, Надежда Владимировна

1 Введение

1.1 Мотивация.

1.2 Основные определения

1.3 Структура диссертации.

2 Негладкая оптимизация

2.1 Квазидифференцируемые функции.

2.2 Условия экстремума.

2.3 Численные методы негладкой оптимизации

2.3.1 Метод дискретного градиента.

2.3.2 Метод отсекающего угла.

3 Аппроксимации полиномами наилучшего приближения

3.1 Полиномы: необходимые и достаточные условия оптимальности

3.2 Алгоритм Ремеза.

4 Аппроксимация полиномиальными сплайнами

4.1 Спалйны: необходимые и достаточные условия оптимальности

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

4.2.1 Задача построения линейного сплайна (ломаной), удовлетворяющего условию альтернанса.

4.2.2 Задача построения полиномиального произвольной векторной степени сплайна, удовлетворяющего условию альтернанса

4.2.3 Замена базиса.

4.3 Численные примеры.

5 Численные эксперименты

5.1 Обобщенный алгоритм Ремеза: непрерывные функции.

5.2 Обобщенный алгоритм Ремеза: дискретные функции.

5.2.1 Базы данных.

5.2.2 Нагревание Титана.

5.2.3 База данных Пезака.

5.2.4 Некоторые важные замечания и рекомендации.

6 Теория аппроксимации в задачах налогообложения

6.1 Постановка задачи.

6.2 Необходимые и достаточные условия оптимальности.

6.3 Численные эксперименты с модельными функциями.

6.3.1 Негладкий случай.

6.3.2 Гладкий случай

7 Сплайны со свободными узлами

7.1 Непрерывная и дискретная аппроксимация

7.1.1 Приближение непрерывных функций.

7.1.2 Дискретная аппроксимация (равномерная аппроксимация и критерий наименьших квадратов).

7.2 Полиномиальные сплайны со свободными узлами: вычислительные аспекты

7.3 Численные экспериметны с непрерывной функцией

7.4 Численные эксперименты с дискретными функциями: сравнение алгоритмов.

7.4.1 Метод Г. Белякова (Алгоритм 1).

7.4.2 Конкретизация Алгоритма 1.

7.4.3 Новый алгоритм (Алгоритм 2) для приближения дискретной функции (базы данных).

7.5 Сравнение результатов, полученных Алгоритмом 1 и Алгоритмом 2.

Введение диссертация по математике, на тему "Обобщение алгоритма Ремеза на случай полиномиальных сплайнов"

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

Заключение и направления для дальнейших исследований

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Сухорукова, Надежда Владимировна, Санкт-Петербург

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

2. В.Ф. Демьянов, A.M. Рубинов, Основы негладкого анализа и квазидифференциальное исчисление. М.: Наука, 1990, 432 с.

3. В.Ф. Демьянов, В.Н. Малоземов, Введение в минимакс. М.: Наука, 1972, 368 с.

4. М.В. Ишханова, С.В. Чистяков, Математические модели выбора налоговых шкал: Учебное пособие, СПбГУ, 1998

5. Н.П. Корнейчук, Экстремальные задачи теории приближения, Наука, М. 1976, 320с.

6. Н.П. Корнейчук, Сплайны в теории приближения. М: Наука, 1984, 352 с.

7. В.Н. Малоземов, А.Б. Певный, Полиномиальные сплайны. СПб: Изд-во Санкт-Петербургского ун-та, 1986, 120 с.

8. B.J1. Макаров, В.В. Хлобыстов, Сплайн-аппроксимация функций. М: Высшая школа, 1983, 80 с.

9. Б.Т. Поляк, Введение в Оптимизацию, Наука, Мовсва, 1985.

10. Е. Я. Ремез, Основы численных методов чебышевского приближения Киев: Наукова думка, 1969.

11. Н.В. Сухорукова, Задача построения полиномиального сплайна, удовлетворяющего условиям чебышевской аппроксимации, Вестник Молодых Ученых, Серия "Прикладная математика и механика", Выпуск 1, 2003, с. 42-46.

12. Н.В. Сухорукова, Необходимые и достаточные условия аппроксимации непрерывных на отрезке функций функциями определенного класса, Вестник СПбГУ, Серия 1, Выпуск 2, с. 66-72.

13. Н.В. Сухорукова, Применение квазидифференциалов к задачам аппроксимации непрерывных функций, Труды XXIX научной конференции Процессы управления и устойчивость: издательство Санкт-Петербургского государственного университета, 1998, с. 388-390.

14. Н.В. Сухорукова, Изучение задачи восстановления налоговой шкалы по шкале средних ставок, Труды XXX научной конференции Процессы управления и устойчивость: издательство Санкт-Петербургского государственного университета, 1999, с. 499-505.

15. Н.В. Сухорукова, Обобщение алгоритма Ремеза на случай ломаных, Труды XXXI научной конференции Процессы управления и устойчивость: издательство Санкт-Петербургского государственного университета, 1999, с. 482-484.

16. Н.В. Сухорукова, Восстановления налоговых шкал по модельной шкале средних ставок, Труды XI Всероссийской конференции Математическое программирование и приложения, Екатеринбург, 1999.

17. Н.В. Сухорукова, Обобщение теоремы Валле-Пуссена и правила замены базисов на случай полиномиальных сплайнов, принята к печати в Труды конференции Процессы управления и устойчивость SCP2005, конференция посвящена 75-летию со дня рождения В.И. Зубова.

18. М.Г. Тарашнин, Применение теории квазидифференциалов к решению задач аппроксимации. Диссертация на соискание ученой степени кандидата физико-математических наук, СПб., 1996, 119 с.

19. П.Л. Чебышев, Теория механизмов, известных под именем параллелограммов, Санкт-Перетбург, 1853.

20. М. Yu. Andramonov, А. М. Rubinov and В. М. Glover, Cutting angle method in global optimization, Applied Mathematics Letters, Vol. 12, 1999, pp 95-100.

21. A. M. Bagirov, Continuous subdifferential approximations and their applications, Research Report 01/22, School of ITMS, University of Ballarat, Nov 2001, http://www.ballarat.edu.au/itms/researchpapers.shtml.

22. A. M. Bagirov, Derivative-free methods for unconstrained nonsmooth optimization and its numerical analysis, Investigacao Operacional, Vol. 19, 1999, pp 75-93.

23. А. М. Bagirov, Numerical methods for minimizing quasidifferentiable functions: a survey and comparison, In: V.F. Demyanov and A.M. Rubinov (eds.), Quasidifferentiability and Related Topics, Kluwer Academics Publisher, pp 33-71, 2000.

24. A. M. Bagirov and A. M. Rubinov, Global minimization of increasing positively homogeneous function over unit simplex. Annals of Operations Research, Vol. 98, 2000, pp 171-187.

25. A. Bagirov, A. Rubinov, N. Soukhoroukova, J. Yearwood, Unsupervised and Supervised Data Classification Via Nonsmooth and Global Optimization, Top, Vol. 11, Number 1, pp. 1-93, Sociedad de Estadistica Operativa, Madrid, Spain, June 2003.

26. A. Bagirov, A. Rubinov, N. Soukhoroukova, J. Yearwood, An algorithm of clustering based on non-smooth optimisation techniques, International Transactions in Operational Research N10, pp 611-617, 2003.

27. A. Bagirov, N. Soukhoroukova, Nonsmooth Optimisation approach to Data Classification, Proceedings of the Post-graduate ADFA Conference on Computer Science, Canberra, ADFA, 2001, pp. 71-74.

28. G. Beliakov, Least squares splines with free knots: Global optimization approach, Applied Mathematics and Computation, Vol 149, pp. 783-798, Elsevier Inc., United States.

29. Armijo, Minimization of functions having continuous partial derivatives, Pacific J. Math. 16, pp 1-13, 1966.

30. Carl de Boor, A Practical Guide to Splines, Springer, New-York, Heidelberg, 1978.

31. V. F. Demyanov and A. M. Rubinov, Constructive Nonsmooth Analysis, Peter Lang, Frankfurt am Main, 1995.

32. V. F. Demyanov and A.M. Rubinov Quasidifferential Calculus Optimization Software Inc., New York, 1986

33. G. Lindfield, J. Penny, Numerical Methods Using Matlab, 1995.

34. J.Rice. Characterization of Chebyshev approximation by splines, SIAM J. Numer. Anal., 1967, vol. 4, N 4, pp. 557-567.

35. A. Rubinov, Abstract Convexity and Global Optimization, Kluwer Academic Publishers, 2000, ISBN 0-7923-6323-X.

36. Martin H. Schultz, Spline Analysis, Prentice-Hall, Series in automatic computation, 1973.

37. N. Soukhoroukova Data classification through nonsmooth optimisation thesis submitted in the fulfillment of the requirements of the degree of Doctor of Philosophy, December 2003, Ballarat, Australia, 224 p.

38. N. Soukhoroukova, Minimisation of the cluster function: numerical experiments using MPI techniques, Proceedings of ICOTA 6 (6th International Conference on Optimisation Techniquecs and Applications), Ballarat,

39. Australia, December 2004, (the Proceedings are published on CD), http://www.ballarat.edu.au/ard/itms/CIAO/ORBNewsletter/ICOTA

40. Marco Frontini and Gradimir V. Milovanovic Moment-preserving spline approximation on finite intervals and Turan Quadratures, FACTA UNIVERSITATIS (NIS), Ser. Math. Inform. 4 (1989), 45-56, gauss.elfak.ni.ac.yu/radovi/f445-56.ps

41. A.K. Jain, M.N. Murty and P.J. Flynn, Data clustering: a review, ACM Computing Surveys 31(3) (1999), 264-323.

42. P.M. Murphy and D.W. Aha, UCI repository of machine learning databases. Technical report, Department of Information and Computer science, University of California, Irvine, 1992. www.ics.uci.edu/mlearn/MLRepository.html.

43. Г.П. Акилов, A.M. Рубинов, Метод последовательных приближений для для разыскания полинома наилучшего приближения, ДАН СССР 157, 1964, с. 503-505.

44. И.И. Еремин, Н.Н. Астафьев, Введение в теорию линейного и выпуклого программирования, М: Наука, 1976, 192 с.

45. П.-Ж. Лоран, Аппроксимация и оптимизация, М: Мир, 1975, 496 с.

46. Ф. Кларк, Оптимизация и негладкий анализ, М: Наука, 1988, 280 с.

47. В.Н. Пшеничный, Необходимые условия экстремума, М.: Наука, 1969, 151 с.

48. В.Н. Пшеничный, Метод линеаризации, М.: Наука, 1983, 136 с.

49. В.Н. Пшеничный, Ю.М. Данилин Численные методы в экстремальных задачах, М.: Наука, 1975, 320 с.

50. Ю.Н. Субботин, it Применение сплайнов в теории приближений, Linear operators and applications, JSNM, 20, 1972, с. 405-418.

51. Ю.Н. Субботин, Н.И. Черных, Порядок наилучших сплайн-приближений в некотором классе функций, Математические заметки, 7, 1970, с. 31-42.

52. Н.З. Шор Методы минимизации недифференцируемых функций и их приложения, Киев: Наукова думка, 1979, 199 с.

53. В.М. Тихомиров, Наилучшие методы приближения и интерполирования дифференцируемых функций в пространстве С1д], Математический сборник, 80 (10), 1969, с. 290-304.