Применение теории квазидифференциалов е решению задач аппроксимации тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Г Б ОД

Ч ИЛИ

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

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

ТАРАШНИН Михаил Геннадьевич

ПРИМЕНЕНИЕ ТЕОРИИ КВАЗИДИФФЕРЕНЦИАЛОВ К РЕШЕНИЮ ЗАДАЧ АППРОКСИМАЦИИ

Специальность: 01.01.09. "Математическая кибернетика"

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

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

Работа выполнена в Санкт-Петербургском Государствен» Университете.

Научный руководитель -

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

Демьянов В.Ф.

Офицальные оппоненты -

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

Чистяков С. В.

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

Васильев Л. В.

Ведущая организация: Вычислительный Центр РАН, Москва.

Защита диссертации состоится 7гЛ 199 в " /У-

часов на заседании диссертационного совета К-063.57.16 по запп там диссертаций на соискание ученой степени кандидата физик! математических наук в Санкт-Петербургском Госуниверситете и адресу: 198904, Петродворец, Библиотечная пл. 2, факультет Пр1 кладной математики - Процессов Управления.

С диссертацией можно ознакомиться в научной библиотеке и» А.М.Горького Санкт-Петербургского Государственного Универсшм та

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

Автореферат разослан Н(?Л№ £ 1996г.

Ученый секретарь

диссертационного совета

д.ф.м.н.

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

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

В математике часто приходится иметь дело с функциями очень сложной природы, вычислять значения которых достаточно трудно. Поэтому возникают задачи приближенного представления этих функций более простыми функциями. Классическими аппаратами таких представлений являются полиномы и рациональные дроби. Теория приближения функций полиномами была разработана в трудах Чебышева П. Л., Вейерштрасса К., Валле-Пуссена Ш., Бернштей-на С. Н. и др. Однако, полиномы и рациональные дроби обладают рядом недостатков, основной из которых состоит в том, что их поведение в окрестности какой-либо точки определяет их поведение в целом. В связи с этим, в последнее время усиленно разрабатываются другие аппараты приближения для функций с особенностями и для не гладких функций. Одним из таких аппаратов являются сплайны. Сплайн-функции, как аппарат приближения функций и решения различных типов задач, появились относительно недавно (история теории сплайнов начинается с работы Шенберга 1946 г.) и, благодаря своим свойствам, получили широкое распространение в приложениях. Интенсивно проводились и проводятся исследования свойств сплайн-функций и этому вопросу посвящена обширная литература, рассматривающая фундаментальные свойства сплайнов: существование, единственность, сходимость, оценки точности приближения различных классов функций, свойства сплайнов как решение различных задач и другие.

В отечественной науке фундаментальные результаты в области теории сплайнов получены в работах Корнейчука Н. П., Малоземо-ва В. Н., Певного А. Б., Стечкина С. Б., Субботина Ю. Н., Тихо-

мирова В. М., и др.

Изначально сплайны были придуманы для интерполяции функций. Поэтому вопросы численного построения сплайнов в основном посвящены интерполяционным сплайнам. Сплайны, как аппарат приближения функций, более гибок и не менее удобен, чем полиномы. Поэтому они широко используются в вычислительной математике (Ал-берг Дж., Нильсон Э., Уолш Дж., Де Бор К., Стечкин С. Б., Субботин Ю. Н.). Изучены и другие области применения сплайнов, например, сплайны и цифровые фильтры, сплайны в инженерной геометрии и др. (Василенко В. А., Зюзин М. В., Ковалков А. В., Завьялов Ю. С., Леус. В. А., Скороспелов В. А., Смоляк С. А.). В работах Корнейчука Н. П., Тихомирова В. М. с помощью совершенных сплайнов решены некоторые экстремальные задачи теории приближения функций.

Задачами сплайн-аппроксимации занимались Малоземов В.Н., Певный А. Б., Райе Дж., Шумейкер Л. и др. В частности, Райсом было получено необходимое и достаточное условие оптимальности сплайна произвольного порядка с фиксированными узлами.

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

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

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

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

4. Создать программное обеспечение разработанных алгоритмов, провести численные эксперименты.

5. Рассмотреть обратную задачу квазилинейной алгебры.

Научная новизна работы. Получено необходимое и достаточное

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

ным благодаря использованию аппарата негладкого анализа (теории квазидифференциалов и кодифференциаяов).

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

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

Рассмотрена обратная задача квазилинейной алгебры.

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

Апробация работы. Основные результаты были представлены на семинарах кафедры Математической Теории Моделирования Систем Управления факультета Прикладной Математики — Процессов Управления СПбГУ (1992-1996 г.г.), на IX-й Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, Институт математики и механики УРО РАН, 1995 г.), на Международном симпозиуме "Set-valued Mappings and Nonsmooth Analysis-95" (СПбИМ им. Стеклова, 1995 г.), на научных конференциях факультета Прикладной Математики — Процессов Управления СПбГУ (1994 г., 1996 г.).

Публикации. По материалам диссертации опубликовано 2 печатные работы. Перечень публикаций приведен в конце автореферата.

Объем и структура работы. Диссертация состоит из введения с аналитическим обзором литературы, главы с предварительными сведениями, глав, содержащих основные результаты, и приложения с программным обеспечением. Работа изложена на 114 страницах, содержит 2 рисунка. Список цитируемой литературы включает 52 наименования.

СОДЕРЖАНИЕ РАБОТЫ

Пусть Хс®п- выпуклое открытое множество. Функция / : X —* К

называется квазидифференцируемой в точке х € X, если она дифференцируема в этой точке по всем направлениям и если существуют выпуклые компакты df(x) С Ж", df{x) С , такие, что

f'(x, g) := lim ~{f(x + ag) - /(г)] = max (v, g) + min (ш, g).

«10 a b€df(x) «В€в/(с)

Множество dj(x) называется субдифференциалом, a df(x) супердифференциалом функции / в точке ж. Пара множеств Vf(x) = Й/С21)! ö/(«?)] называется квазидифферегщиалом функции / в точке х. Квазидифференциал определяется неоднозначно.

Если среди всех квазидифференциалов функции / в точке х имеется квазидифференциал вида ¡df(x), {0„}]; то функция / называется суб-дифференцируемой в точке х, а если среди всех квазидифференциалов есть квазидифференциал вида [{0„}, df(x)}, то / называется супердиф-ференцируемой в точке х.

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

необходимое условие минимума на Ж"

~df{x*)CÜj{x*),

необходимое условие максимума

-dj{x**)Cdf(x**),

достаточное условие строгого локального минимума

~Щх") С intdf(x'),

достаточное условие строгого локального максимума

-£/(*") С int9/(0-

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

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

Сплайны представляют собой функции, которые склеены из различных кусков полиномов по фиксированной системе. Простейший пример — ломаные.

Функция S(A,t), заданная и непрерывная на отрезке [а, Ь], называется полиномиальным сплайном порядка га с узлами 0,- (i G 1: (r¡ - 1)), если на каждом из промежутков [а, 0\], f?,-+i], г £ 1 : (п — 2), [вп-г, S(A,t) есть алгебраический многочлен степени, не превосходящей т, а в каждой из точек 0,- некоторая производная (1 < г/ < ш)

может иметь разрыв.

Рассмотрим произвольную функцию f(t) на интервале [а, 6]. Аппроксимируем ее сплайном, который задан на отрезке [а, 6] и имеет на нем п — 1 внутренний узел. Сплайн имеет вид

S(A, I) — c¡o + «it + a-i max{0, t— + аз max{0, t — #2} + ■ • ■

+ a„max{0, t — вп-г},

где Oí (¡ £ 1 : (n — 1)) — узлы сплайна, А — множество параметров сплайна, т.е. А = {ао, ai, - ■ ■ , ап} € К"*1.

Предположим, что узлы 9¡ фиксированы. Рассмотрим задачу

max \F(t,A)\ min , (1)

где F(t,A) = f(t) - S(A,t). Задача (1) эквивалентна задаче

Ф(Л) = т-ах <p(t,Ä)min , te[o,4 леж-^1

где

v(t,A) = !(/(<) - S{A,t)Y = ±F*(t,A). (2)

Нетрудно видеть, что Ф(Л) — выпуклая функция. Если Ф(Л") = min то сплайн S(A*,t) называется оптимальным.

Пусть максимум (по í) функции <p(t,A) достигается в точках ti, и пусть этих точек к штук. Упорядочим их по возрастанию:

<1 <Í2 <Í3 < ■-• <tk-i <tk-

Допустим также, что в отрезке [а, #1] содержится к\ точек максимального уклонения сплайна от функции /(£), а в любом интервале (#¿,$¿+1] (г £ 1 : (п — 1)) содержится к\+\ точек максимума функции

п

уэ(Л), причем Ь — в„. Очевидно, что к =

¿=1

Пусть = А). Обозначим через ^ абсолютную величину максимума в формуле (1), т. е. F = |.Р(£,-)|.

Введем следующие обозначения: — точки максимального уклонения сплайна от функции /({), которые лежат на г-ом интервале и их к( штук (»' £ 1 : п, 3 6 1 : к^). Интервал (#¡-1, будем называть г-ым интервалом (г £ 1 : гг), причем а = Выпишем субдифференциал функции Ф(Л):

5Ф(Л) = со <

( 1 \

'«Ч

О

о

V о /

( 1 \

42)

о

\ о У

/ 1 ^ Ч

Л") «п

►

К?-'«-!/ /

где € 1 : к;, ; £ 1 : п.

Необходимое условие минимума субдифференцируемой функции Ф : Жп+1 —» ® имеет вид

Оп+1 € дФ(А*). (3)

Теорема. 1. Для того, чтобы сплайн Б(А^) был оптимальным, необходимо и достаточно, чтобы выполнялось одно из условий:

1) на одном из отрезков [0!_ь @г], где а = во, Ь = вП1 найдется 3 тонки максимального уклонения сплайна ¿>(Л,4) от функции f(t), причем функция F(í,Л) имеет чередующиеся знаки в точках1\, и ¿з/

О

2) найдутся интервалы ,0,] и (в]-1, такт, что 1 < г < < п и разность — г) минимальна, на которых точки максимального ■уклонения расположены следующим образом;

на г-ом и ]-ом интервалах лежат по крайней мере по две точки алътерианса, а на всех внутренних интервалах — по крайней мере по одной точке алътернанса.

Пусть произвольная функция £(1) задана на интервале [а, Ь]. Введем функцию

О, г <

Нетрудно видеть, что

(4 _ а\г _ Г max{0, (t - 0)Г}, если г — нечетное,

\(i — #)max{0,(i — 0)г-1}, если г — четное,

где г — натуральное число.

Аппроксимируем функцию f(t) сплайном порядка s, который также задан на отрезке [а, 6] и имеет на нем п — 1 внутренний узел. Такой сплайн имеет вид

s п—1 S

S(A,t) = + £ £>„(* - 0iY+, 1=0 1 = 1 j = 1

где в, (t G 1 : (п — 1)) — узлы сплайна а < 91 < 62 < ■ • • < ^n-i < Ь, А — множество параметров сплайна, т.е.

А — {а0,... , а5,ац,... ,als,... ,a„_i;i,... ,an-i,s} 6 M"s+1.

Предположим, что узлы б,- фиксированы. Рассмотрим задачу

шах \F(A,t)\ —► rain , (4)

tg[a,i] A6K"'+t

где F(A,t) = f(t) - S(A,t).

Задача (4) эквивалентна задаче

Ф(у1) = max <р(А, t) —+ min ,

где

<p{A,t) = %(f(t)-S(A,t))3 = ^F2(A,t). (5)

Нетрудно видеть, что Ф(Л) —■ выпуклая функция. Если Ф(А*) — min Ф(Л), то сплайн S(A*,t) называется оптимальным.

Пусть максимум (по t) функции у(А, t) достигается в точках f:-, и пусть этих точек к штук. Упорядочим их по возрастанию:

ti <t2 <t3 < ... < tk-1 <tk-

Допустим также, что в отрезке [а, 0{\ содержится к\ точек максимального уклонения сплайна S(A,t) от функции f(t), а в любом интервале (#t-,0t-+i] (г £ 1 : (я — 1)) содержится kt-+i точек максимального уклонения сплайна S(A,t) от функции /(i), причем 6 = 0п. Очевидно, что

к = £ h.

»=1

Пусть -F(i,) = F(A,ti). Обозначим через F абсолютную величину максимума в формуле (4), т. е. F = |F(ij)j.

Введем следующие обозначения: tij — точки максимального уклонения сплайна от функции f(t), которые лежат на г-ом отрезке и их h штук (г £ 1 : п, j € 1 : Интервал (¿"¿-хД-] будем называть г-ым интервалом (г € 1 : п), причем, а — во.

Введем в рассмотрение функцию сц — Fsign(F(itj)) (г £ 1 : п, j £ 1 : ki).

Выпишем субдифференциал функции Ф(Л):

(1) hl t2 гп /1 \ h fei i2

ЩА) = со < стц i' ni 0 V о ) 'lifc! 0 ^ о y

°т1

1

1711 1т 1

(¿т1 — 1) - ^т-1)2

(¿т1 ~ ^т-О® О

I ' '" 1 ткг,

1

Й

''тк,,

тк„

(1ткт — От-1) {1ткт ~ ^т-г)2

(¿го*™ ~ "т-х)*

О

1п1 п 1

'пХ

\

(^1 - 0П-1)'

о о

Г ' " >апкп

\

1пкп

/2 пкя

V

(*п*. - 0П-О Оп«г„ - ^п-а)5

о о

/

Необходимое условие минимума субдифференцируемой функции Ф : ®П8+1 Ж имеет вид

0„5+1 € дФ(А*).

(6)

Эта же задача рассматривалась в работах В. Н. Малоземова, А. Б. Певного и Д. Райса. Приведенное ниже утверждение уточняет результат о количестве точек максимального уклонения сплайна

V

о

1

Б(А*, I.) от функции f(t) на каком-нибудь внутреннем подынтервале (г <.?)•

Теорема. 2. Для того, чтобы сплайн З(А^) был оптимальным, необходимо и достаточно, -чтобы выполнялось одно из условий:

1) на одном из отрезков 1,0,-], где а = в о, Ь — 9п, (¿61: п) найдется в+2 точки максимального уклонения сплайна от функции /(¿), причем функция F(í1Л) имеет чередующиеся знаки в точках ¿¿2, • • • (^¡,¿+2/

2) найдутся интервалы и {О^-х, 0,-] такие, что 1 < г < j < п и разность — г) минимальна, на которых точки максимального уклонения расположены следующим образом:

на г-ом и ]-ом интервалах лежат по крайней мере по з + 1 точке альтернанса, а на всех внутренних интервалах — по крайней мере по 5 точек альтернанса.

Будем по-прежнему рассматривать произвольную функцию /(<) на интервале [а,Ь]. Аппроксимируем ее сплайном, который задан на отрезке [а, 6] и имеет на нем один свободный внутренний узел. Такой сплайн имеет вид

S(A,t) = ао + a\t + 02 max{0,i - 0\},

где — узел сплайна, А — множество параметров сплайна, т.е. А = {ао,01,02,01} еМ4.

Будем также рассматривать задачу

max |F0,.i4)l -+ min. (7)

16[a,b] 14 Л АЕЕ«' V '

где F(t,A) = f(t) — S(A,t). Задача (7) эквивалентна задаче

ФЬ4) = max (p(t,A) —»■ min, ' te[a,6] v Am*

где

<p{t,A) = \ {f(t)-S(A,i))2 = \f%A). (8)

Так как узел не является фиксированным, то Ф(Л) - невыпукла. Функция Ф(А) является квазидифференцируемой. Если Ф(А*) =

min Ф(Л), то сплайн S(A* , t) называется оптимальным. лек4

Пусть максимум (но I) функции Л) достигается в точках и пусть этих точек к штук. Упорядочим их по возрастанию:

Допустим также, что в отрезке [a,<?i] содержится fei точек максимального уклонения сплайна 5 (А, t) от функции f(t), а в интервале , 6] содержится ¿2 точек максимума функции <p(Ä). Очевидно, что к = ki+k^-Пусть F(ti) = F(t{,A). Обозначим через F абсолютную величину максимума в формуле (7), т. е. F =

Введем следующие обозначения: ¿у — точки максимального уклонения сплайна S(A,t) от функции f{t), которые лежат на отрезке [a,<?i] и их к\ штук, t-zj — точки максимального уклонения сплайна S(A, t) от функции f(t), которые лежат на интервале (öj., 6] и их ¿2 штуки.

Выпишем квазидифференциал функции <p(t). Он зависит от знака произведения F(9i)a-2- Так как F(91) ф 0, то равенство F(ßi)a2 = О возможно только если аз = 0. В этом случае получаем сплайн, заданный на отрезке [а, 6] в виде прямой ао + ait. Пусть сначала F(0i)û2 > 0, тогда имеем если t < 0i, то

<1 <Î2 <Î3 < ■■• < 4-1 < tk.

/1\

8!P(t) = ntij) J , = Ко)

0

о '

если t > в 1, то

если t = 9i, то

— vw g ;

\[0, -a2]J

Пусть теперь F(6i)a2 < 0, тогда имеем

d<p(9i) = F(9i)

( 1 \

если i < то

МО =

¿wo = Hhj)

/о\

о о

\о/

если t > 61, то

МО = П^)

1 \

t

Î -01 — Й2 /

о о

\о/

если i = 01, то

/1 V о

/ 0 \

о

о

\[0,-а2]/

Используя свойство квазидифференцируемых функций, имеем

£Ф(Л) = со{§!р(Ь) - Yl ЫЬ)\к € 0Ф(Л) = ^ âtft*),

k£R(t)

R(t) = {¿61: iVHi;) = Ф(А)}.

Необходимое условие минимума квазидифференцируемой функции имеет вид

-8Ф(Л) С ¿)Ф(Л).

Утверавдение. Для того чтобы сплайн S(A, t) наилучшим образом аппроксимировал функцию f(t) необходимо, чтобы на одном из отрезков [a,0i] или [0i,6] лежало три точки (в том числе может бить и узел сплайна в\) максимального уклонения сплайна S(A,t) от функции f(t) с поочередной переменой знака функции F(t). При этом, если узел

в\ является точкой максимального уклонения сплайна 5(Л,<) от функции то необходимо выполнение неравенства:

F(0l)a2 > 0.

Пусть функция / : Мп —► ® липшицева и дифференцируема по направлениям. Тогда производная по направлениям

= (9)

aio a

непрерывна и положительно однородна по д. Поэтому по теореме Стоуна-Вейерштрасса ее можно с любой наперед заданной точностью аппроксимировать функцией

шах(г), д) + min(it;, д), (10)

v£A w£B

где

А — со{аг}, a; € Ж", » € I, I = l:Nlt

В = co{bj}, bj £ Ж", je J, J = 1 : N2,

N\, N2 - числа, зависящие от точности аппроксимации. Для любого д при достаточно малом а величина Ag+or^)~Ag) будет близка к f'(x, д). Выберем некоторое К, векторы дк и найдем

f(x + agh)-f(x) k€l: _

a

Если бы функция f'(x,g) точно представлялась в виде (10) при некоторых {at}, {6j}, то вьшолнялись бы равенства

тах(а,',я*) + min(63-, дк) = f'(x, дк) Чк € 1 : К. (12)

J €/ !£J

Iio поскольку f'(x, gt) нам известны (по формуле (11)) лишь приближенно и заранее неясно, представима ли f'(x,g) в виде (10) точно, то естественно попытаться найти {а,} и {bj} так, чтобы система (12) (где f'(x,9k) заменены ск) выполнялась "как можно точнее". Можно сформулировать следующие три задачи минимизации, соответствующие описанной выше задаче:

УЧтах^ьд*) + min(6;-, я*) - с*)2 -»• min, (13)

' t ] a,.bj

У)|тах(о,-,^) +mxn(bj,gk) -ck\ -f min, (14)

~ г 3 "i,bj

max|max(aj,ffjs;) + min(6,-,дь) - cjj| min . (15)

к j j <4,ij

Задачи (13)-(15) называются обратными задачами квазилинейной алгебры.

Лемма. Задача (13) сводится к задаче лтнимизации функции вида max(v,g) + mm(tu,0). (16)

В свою очередь для минимизации (16) требуется решить несколько задач линейного программирования.

ВЫВОДЫ

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

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

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

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

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

1. Тарашнин М. Г. Об обратной задаче квазилинейной алгебры, Вестник СПб Ун-та, 1995, Серия N 1, Вып. N 2, стр. 100-102.

2. Тарашнин М. Г. Об одной из обратных задач квазилинейной алгебры. - Информационный бюллетень Ассоциации математического программирования. Вып. 5, Екатеринбург; УРО РАН, 1995; стр. 182-183.