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

РГ6 од

" ' а^ОСГ-ПЕГЕРБУРГСШЙ 1«£ДдРСгаЕНЬ1!Я УНИВЕРСИТЕТ

Ка правах рукшнсз

ЛАДОШ ЖШ ШССАЯЛОКИ

АППРСКСИМАШЙ 0ЯЩЗ! ШОШ ПЕРЕЙННЫХ С ПСГ!СЩ> АФИННЫХ ПРЕОБРАЗОВАНИЙ ЕЕ СЕЯЕШЯ '

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

АВТОРЕФЕРАТ диссертация на ссвскзнне учзнс! степени кандидата (¡лзяко-иатсчатическн! наук

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

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

Научный руководитель - доктор {езико-матомагических наук.

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

Офптшя&э сшсненты:

доктор СязЕКо-иатештичэских каук, профессор Гаральд Исидорович Натансон

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

Ведущая организация - Вычислительный центр РАН

Защита состоится "сМ" ¿/м?/^* 1993 г. в "Ж" часов на заседании специализированного совота К-063.57,16 по присуждению ученой степени кандидата физико-математических наук в Санкт-Петербургском государственном университете по адресу : г.Санкт-Петербург, В.О., 10-я линия, д.33.

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

Автореферат разослан А^^сР 1993 г.

Ученый секретарь специализированного ровета К-063.57.16 , кандидат физико-математических наук, доцент

В.Ф.Горьковой

о

ОБЩ ХА РАКТГРИСТШЦ РАБОТЫ

АКТУАЛЬНОСТЬ ТЕШ. Широкое распространенно математического моделирования в самых различных областях наука и техники щидазт актуальность дальнейшему развитию соответствущего алгоргтячес-кого и программного обеспечения.

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

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

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

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

ЦЕЛЬ РАБОТЫ состоит в разработке новых методов представления (точного или приближенного) функции многих переменных с помощью композиций функций одной переменной, имещих определенный геометрический смысл, н простых операций типа слогення и умножения.

МЕТОДЫ ИССЛЕДОВАНИЯ. В качестве основных инструментов исследования использовались метода вычислительной математики, математического анализа, высшей алгебры.

НАУЧНАЯ НОВИЗНА. Предложена новая форма аппроксимирующей функции, позволяющая при аппроксимации функций многих переменных использовать, кроме информации о значениях функции в отдельных точках, еще и экспертную оценку поведения функции вдоль отдельных переменных л взаимного влияния отдельных переменных. При этом, исследование функции многих переменных сводится к исследованию функций одной переменной, имеющих ясный геометрический смысл.

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

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

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

ПРАКТИЧЕСКАЯ ЦЕШЬСТЬ. Предложен подход, дающий математический .аппарат для представления и аппроксимации функции многих переменных в удобной форме , формализации и использования предварительной информации о поведении исходной функции. Чем более полна и точна эта информация, тем меньше потребуется экспериментальных точек для аппроксимации функции.

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

АПРОБАЦИЯ РАБОТЫ. Основные положения диссертации докладывались на семинарах кафедры математической теории моделирования систем управления-факультета. ПМ-ПУ СПбГУ; в ходе работы Всесоюзной научно-технической конференции "Надежность машин, математическое и машинное моделирование задач динамики. Моделирование-91 (г.Кишинев, 1991) и 11-ой всесоюзной школы "Системы программного обеспечения решения задач оптимального планирования"

(г.Кострома, 1990).

ПУБЛИКАЦИИ. Основные результаты по теме диссертации опубликованы в работах [1-3] .

СТРУКТУРА И ОБЪЕМ РАБОТЫ. Диссертация состоит из введения, трех разделов и списка литературы из 70 наименований. Объем работы составляет 107 страниц.

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

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

В разделе 1 вводится понятие »Минных преобразований функции многих переменных.

Для случая функции одной переменной задается следующее преобразование :

L Af(x)} = р f(xr +■ з) + q , (1)

( р, q , г , в ) r* ^

где параметры р, q, г, з имеют смысл:

р - коэффициент растякения-сжатия функции вдоль оси ординат; q - коэффщиент сдвига функции вдоль оси ординат; г - коэффициент растяжения-сжатия функции вдоль оси абсцисс, г*0;

з - коэффициент сдвига функции вдоль оси абсцисс.

Определение. Преобразование (1) называется аффинным преобразованием функции одной переменной.

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

Определение. Преобразование L г переводит точку с координатами (х,у)' в точку (х',у) , если

х'= х ~rs , у= ру + q .

Таким образом, если (х,у) - точка графика функции f , то (х',у) -точка графика преобразованной фушсции L r a)lf(x)l.

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

ь

На шхкоствэ С(Ю задвется отношение : /(х) £(х), если существуют такие числа р. д. г, а, (г*0), что

Теораиа 1. Отношение является отношением эквивалентности на множестве непрерывных функций одной переменной.

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

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

(р.Ч.г,«) * г

степени. Мноаество полиномов третьей степени " ах + Ьх + сх + й распадается на три класса в зависимости от знака величины (Зас-ЪМножество полиномов четвертой степени распадается на бесконечное множество классов эквивалентности. Признаком такого ргзбиения для полиномов вида аг4+ Ьх3+ сх2+ йх + е является ¿¿личина Л = 8ас - ЗЬ2 и значение коэффициента й .

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

Определение. Аффинным преобразованием непрерывной функции, п переменных называется преобразование вида :

^р.Ч.г,.)1^1!'^.....Хп)] =

= р ДхЛ+ ¿1§гага+ зз.....хпгп+ э^ + д

с помощью чисел р, д; г гп; з зп; имеющих следую-

щий смысл:

р - коэффициент растяжения-сжатия функшш вдоль оси ординат;

q - коэффициент сдвига функции вдоль оси ординат;

г1..... г - коэффициенты растяжения-сжатия функции вдоль

осей Ох,, Ох,.....Ох соответственно (г* О, г .....г *0) ;

1 2 п 1 2 п

31.....зп - коэффициенты сдвига функции вдоль осей

Ох. Ох......Ох соответственно.

12 п

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

Леыыз. Пусть сечения функции

¿{х,,...,х ) = /гг,.....х ,х° ......Х°1

1 ш 1 м т* 1 п

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

/ представима с помощью функций, зависящих от я и (п-т) переменных.

Рассматриваются различные многомерные сечения функции / , удовлетворяющие условиям леммы.

Фиксируется некоторая точка х°=(х°,х°.....х°). Сечения,

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

Общий вид такого представления : /(х) = Р (и ){...{Р(и){Р(и) Н(и (и ))+С1 (и ))...)+<! (и )

ПП £ £ Л А \ Л ¿, ¿Л ПП

и = х , (2)

п п

и = Я , (и ) х , + 5 , (и ) ,

п-1 п-1,п п п-1 п- 1 » п п

и =Я „ Аи )(Я , (и ) х (и )) +Б „ (и )

п - 2 п - 2 , п - I п-1 п-2,п п п - 2 п - 2 , п п п - <2, п - 1 п -1

б

При ЭТОМ X = ("2 ; ,

* 1 2 п

яг«,; = ;(х^х°г,...,х°) ,

Р1(х°} = 1 ' С11(х°) = 0 • 1 = 2,3.....п •

= 1 , = О , 1 = 1,2.....п-),: = 1+1.£+2.....п.

Общее количество функций, участвующих в данном представлении равно (пг+ п-1; , где п - количество переменных .

Условие Я^Си^ * 0 является необходимым и достаточным для существования обратного преобразования

"Г

Х~ -- , I = 1.....П-1,

п к (и ) ]«1»1 1 1

(3)

где Л = 'п Н (и ) .

1 к->*1

Наряду с описанной полной формой представления функции многих переменны можно использовать- любое усеченное представление, положив некоторые из функций Р(, Яи; <3,. соответственно равными 1 или 0.

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

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

f(x,.x,.....X ) = П P.(xj .

12 n i»i 1 1

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

сечения этой функции вдоль переменных х ,х ,...,х , т < п, эквивалентны между .собой относительно преобразования L р для любого т= 1,2,...,п-1. Тогда функция /<= SPgRg .

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

Теореыз 3. Для того, чтобы заданная функция / е ,

необходимо и достаточно, чтобы она удовлетворяла равенству :

f(x) = Е А^х^ , где 1*1

А^ /Гх°..........X°J ~ 1(г°} • i=2.....n'

Л — f(х ' iX t»».9x)»

l 1 e n

Следствие. Если функция / e З^о и непрерывна (дифференцируема), то.все функции Q , 1=1,...,п, также непрерывны (дифференцируемы).

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

Теореыа 4. Для того, чтобы заданная функция / е ,5Рд10 . необходимо и достаточно, чтобы она удовлетворяла равенству :

f(x) = П М (х ) , где' i=i -

f(Xi*»'tX ,х,х,..., х )

а = -—!-bi—!—Lii-2- , {=2.....п,

1 f(z°)

М — , • • • 9х ) *

Следствие. Если функция / е 2р^10 и непрерывна (дифференцируема), то все функции Р , 4=1,...,п, также непрерывны (дифференцируемы).

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

- - Теорема 5. Для того, чтобы непрерывная дваады дифференцируемая по любой паре переменных функция./е 2Р010. необходимо и достаточно, чтобы выполнялось условие :'

зЯТ(Ю д!(т) в/ги - 1

Дх; - =--- , V и, .

ЗХ^Х^ ЭХ1 ЭХ ^ , •

Для любого номера А , й=2,3.....п, можно построить

многомерные сечения заданной функции

-О „о.

НX^ ш •»• ~ »• • • +1'""" '^п^ "

Пусть Нк имеет представление : -

№.....V = .....+ К<хъ> ■

Для каждого значения хк фиксируются два набора' переменных

(ф! «г/ ) /т" Т" ) •

НЫ~*(Х1.....'

г; ,

такие, что й'* /г" ., и рассматривается система уравнений-¡¡¿Хк) К' + 4кгхк; = ук(х'1Ч.\..х'к^.хк) . '

тогда функции Мк, А можно определить следующим образом :

Н 9 • • • »ЗГ' . ) ~ 9 • • • . )

М (X ) = —*—^-^—*-—5-^—, (4)

к "к ' й'- П"

Н (X",... ,Х" .,х.) П'- Н(Х'.....X' .,х.) П"

А (X ) = _ _ _к-1 к_

к к К'- п»

Теореиа 6. Для того, чтобы заданная функция / е Зр£10 , необходимо и достаточно, чтобы она удовлетворяла равенству

Дх) = Мп(хН...Шх)(ИГх) Н(х)+А(х))+АГх))...)+А (х )

п Л Л Л 4 1 ¿2 о *э ПП

где функции Ак,Мк,.к = 2.....п, определяются по формулам (4).

Следствие. Если функция / € 5Р010 и непрерывна (дифференцируема), то все функции Рк,<2к, к = 2.....п, также непрерывны

(дифференцируемы).

Снова для любого номера к , к = 2,3,...,тг, рассматривается функция '

Нк(х1,...,хк) = Дх1,...,'хк,х°+1.....х°) .

Пусть Нк имеет представление :

Я (х.,...,х.) = к 1 к

. =' Н Ах ВГх ■) + С(х ,Гх ) + С

к-1 1 1 к 1 .к к-1 к-1 к к-1 к

Выбираются константы 'с1* с^ такие, что следующие 2(к-1) уравнений - относительно х , {=1,...,к-1,

Нк(х°,...,х°_1.х1,х°^1.....Х1.Л'Х1) ~ с\

Н (Х°' ■ Х° ' X Х° Т° - с3

имеют решения ,у°, г", 1=1,...,к-1.

Для • каждого .значения '. хк .строится система 2(к- и уравнений :

которые определяют 2(к-\) неявно заданные функции :

.....= У,.,.

г1(хк.В1,С1.....В1.1>С1_1.В1Ф1>С1Ф1.....5к_1,Ск-1> =

и 2СЙ-1) уравнений относительно В( и с : у0 -

" 1 1

у - £

1 , к 1 , к

= ------^ "

и полагается

к к

"г + • 4=1.....■

Данный алгоритм последовательно применяется для каждой функции Нк от Ь=п до &=2 .

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

Теорема 7. Для того, чтобы заданна? дифференцируемая функция f € З^дз , необходимо и достаточно, чтобы она удовлетворяла равенству

где .о.', 1=2.....п, В1 С4 к ,й=2,...,п, определяются в процессе работы описанного выше,алгоритма.

Следствие. Если функция / е З^д непрерывна и дифференцируема, причем * 0 , 1=1,...,п, тогда функции Я и ~ 1

5 1=1.....п, й=1+1.....п,также непрерывны и дифференцируемы.

Пусть на каждом шаге предложенного алгоритма решаются одновременно две задачи : построения функций и к.

Тогда, основываясь на всех доказанных выше теоремах, при'условии дафференцируемости заданной функции, можно сделать вывод о дафференцируемости всех функций одной переменной, входящих в представление (2).

В разделе 3 рассматривается задача равномерного приближения функции многих переменных на некотором п-мерном множестве о е Я" функциями £ е 3РдВ(}:

тх - г(х) | —► и I п - (5)

X € О Р,0,К,$

*

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

Задача (5) легко сводится к общей задаче математического программирования введением дополнительной, переменной с°. А именно, поставленная задача эквивалентна задаче минимизации по вектору с = (с°, с) функции 5 ) = с° при ограничениях \/(х) - - с"« 0 , I е й.°

При численном решении поставленной задачи следует учитывать следующие особенности :

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

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

Для решения поставленной задачи предлагается следующий алгоритм.

1. Задаются начальное приближение вектора с и пределы точности вычислений : .

1 2 Э " 4 5

Пусть получено с^.

2. Проверка оптимальности полученного приближения :

II P'rcjll s

3. Из решения задачи линейного программирования

найти F ( cj = min F ( с ) при ограничениях id.с0;

' F(xl,c) + (р'(х*,с), й) ~ с° s О , i^i.....т,

- a,s 5 ,

J .5)0, J=1,...,n ,

5 «

где Fix,с) = -¡-(/(xj - Z(x.с))2 ,

при с=ск находится вектор dk=d(ckJ, определяющий направление убывания целевой функции.

4. Определение шага «к в направлении dk осуществляется методом "золотого сечения". При этом выбор длины полуинтервала (ак,£>к], на котЬ^йм ищется <*к определяется следующим образом :

если |Vr bkJ < |Ь Ч а | , тогда Ьк= 2 ь^, 1 к - 1 к - 1 1

если |Vr аь_х| < -|Ь Ч а j . тогда Ьк= 2.

1 к - I к - 1 '

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

5. Проверка на "овраг".

Если "овраг" еще не зафиксирован, тогда вычисляется

ь li d || d = z <*.. если -й—£ ff и II A F II s в ,

г , i 1С d k 5

1*к-n* 1

то перейти к п.6, иначе п.2.

Если "овраг" зафиксирован, то Ц д f || £ es- условие выхода -»п.2.

6. "Овражный" метод: очередная точка с; = ск.,+ пгйг< гДе

п - "овражный" шаг, и переход к п.3,4, результат - следущее

значение с,", к

С"- С

Тогда dk= g , переход к п.;.

к к 1

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

Основные результаты диссертации опубликованы в следующих работах :,

1. Александрова И.М. Аппроксимация функщш многих переменных с помощью аффинных преобразований ее сечений. Вестник СПбГУ, сер.математика, 1992, вып.4, с.101-103.

2. Александрова И.М., Проурзин В.А. Построение областей безотказной работы технических систем методом аффинных преобра-1 зований -эталонных сечений. Материалы Всесоюзной науч.-тех.кояф."Надежность машин, математическое и машинное моделирование задач динамики. Моделирование-91. Кишинев, 1991, с.42-44.

3. Александрова И.М., Проурзин В.А. Аппроксимация функции многих' переменных методом аффинных преобразований эталонных сечений. Материалы 11-ой всесоюзной школы "Системы программного 'обеспечения решения задач .оптимального планирования', Москва, 1990, с.39-40. ' ' , .