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

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

ргв од

2 НОЯ 1336

ЕВНЕВИЧ Елена Людвиговна

АВТОМАТИЗАЦИЯ ВЫБОРА И СИНТЕЗА КОМБИНИРОВАННЫХ АЛГОРИТМОВ

05.13.16 - применение вычислительной техники,

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

АВТОРЕФЕРАТ

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

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

Работа выполнена в С.-Петербургском институте информатики и автоматизации РАН

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

доктор технических наук Воробьев В.И.

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

доктор физико-математических наук, профессор Хованов Н.В. доктор технических наук, профессор Румянцев И.А.

Ведущая организация: Санкт-Петербургский государственный институт точной механики и оптики. Технический университет

Защита состоится 1996г. в *{0 часов

на заседании диссертационного совета Д.003.62.01 при Санкт-Петербургском институте информатики и автоматизации РАН по адресу: 199178, С.-Петербург, 14-я линия, д.39

С диссертацией можно ознакомиться в библиотеке диссертационного совета Д.003.62.01

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

Ученый секретарь диссертационного совета

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

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

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

Опыт эксплуатации стандартных программ и пакетов ПП, и накопленный за 20 лет в С1ШИРАН, показывает, что перенос программ с одной платформы на другую требует повторного анализа ошибок округлений и в ряде случаев может приводить к необходимости разработки новых устойчивых алгоритмов.

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

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

Цель работы.

Разработка статистического метода синтеза комбинированного алгоритма на основе различных критериев устойчивости с учетом требований пользователей и опыта работы эксплуатируемых пакетов ПЛ.

Методы исследования.

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

Научная новизна.

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

- разработаны рекомендации по использованию пакетов прикладных программ на основании статистического обследования задач пользователей;

- разработано функциональное наполнение пакетов прикладных программ "Вычислительная математика" и "Математическая физика";

- предложен метод получения численных характеристик устойчивости алгоритма к погрешностям исходных данных;

- предложен метод получения численных характеристик подверженности алгоритмов влиянию ошибок машинного округления;

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

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

Практическая ценность.

Разработанные в программе методы использовались при комплектовании библиотек стандартных программ Центра коллективного пользования СПИИРАН. Пакеты "Вычислительная математика" и "Математическая физика" были приняты в ГОСФАП.

Реализация результатов работы.

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

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

Апробация работы.

Результаты проведенных исследований были представлены на:

1. Областной научно-практической конференции молодых ученых и специалистов "Математическое моделирование", Ленинград, 1988.

2.Международной конференции "Качество программного обеспечения", Санкт-Петербург, 1992 г.

3. 4-ой Санкт-Петербургской Международной конференции "Региональная информатика-95".

Основные результаты диссертации опубликованы в 7 работах.

Структура и объем диссертации. Диссертация состоит из введения , 3 глав, заключения, списка литературы и приложений. Объем основного текста диссертации 90 страниц; приложений 15 страниц.

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

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

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

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

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

Пакет "Решения задач вычислительной математики" включил следующие разделы:

1. Интерполяция, аппроксимация, численное интегрирование и дифференцирование.

2. Вероятностные и статистические расчеты, временные ряды.

3. Интегрирование обыкновенных дифференциальных уравнений.

4. Процедуры случайной выборки.

Подбор алгоритмов и программ основывался на требованиях пользователей и качестве алгоритмов и программ. В качестве базовой библиотеки использовалась MSFL1B фирмы CDC. Одной из главных характеристик разрабатываемого пакета должна была быть его мобильность. Функциональное наполнение пакета ориентировалось на решение широкого круга задач фундаментальных и прикладных исследований пользователями РАН.

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

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

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

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

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

Приведем далее необходимые определения вышеназванных показателей, смешанного алгоритма, а также методы вычисления этих пока-

зателей и метод построения смешанного алгоритма.

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

Пусть f - вещественнозначная процедура - функция, действующая в области G с Rn,

x=(xi,... ,xn) е G, £,i,...,£,rT независимые случайные величины, такие, что Es,i = 0, D£,i =1 (i=l,...,n)

Локальной степенью неустойчивости f в точке х назовем

, /ü f (xj + хп + 64n)

Df (х) = lim -

6-0 б

Замечание 1: Uf - функция G -> R+. Замечание 2:

Для процедур общего вида можно использовать варианты обобщения определений:

а) процедура общего вида рассматривается как вещественнозначная вектор-функция нескольких переменных: f=(fi,...,fn):G ->Rn и определения обобщаются с учетом того, что компоненты f i: G -> R можно считать функциями как в первом случае. Следовательно, для каждой из компонент можно определить степень неустойчивости Ufj, а затем получить степень неустойчивости Uf самой процедуры f, осуществив какую-либо свертку;

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

Определение 2: Пусть || . || - некоторая норма в пространстве функций, указанных на G. Глобальной степенью неустойчивости f в области G назовем величину ||Uf||.

В качестве примеров нормы || . || можно рассмотреть норму

пространства непрерывных функций С (||Ufä=sup Uf(x)), тогда гло-

xEG

бальная неустойчивость имеет смысл максимальный локальной неустойчивости; либо норму пространства Li(||l)fD=I|Uf (х) |dx/mes(G)) и

G

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

Формула, приведенная в определении 1, не очень удобна для

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

Лемма: Если Г дифференцируема в окрестности точки х и для достаточно малых б случайный вектор б£, принадлежит этой окрестности, то 1ЛгСх)= ¡ггас! Их)|.

Далее дается определение смешанного алгоритма.

Определение 3: Пусть Г1 и Г2 -алгоритмы, реализующие вычисление функции Г в области бСц. Смешанным алгоритмом назовем

- , ^(х), х

и 00 ={ - -

^(х), х е б

е в\э.

Область э назовем областью предпочтения алгоритма Ъ..

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

пусть ~ те же, Ц...11 - некоторая норма в пространстве функ-

ций £ -> Р. Требуется построить область б с й такую, что Еи^Ц минимальна, причем б должна иметь достаточно простую структуру,

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

Была построена область предпочтения б для частного случая, когда д - прямоугольник вида [а,Ых[с,сЗ]. Рассмотрим функцию двух переменных Иха.хг)^ -> Ви две процедуры-функции 14 и реализующие вычисление Г с некоторыми погрешностями, которые в нашем примере моделируются искусственным добавлением к значению функции небольших возмущений.

Прямоугольник в1 разбивается на ИхЫ одинаковых прямоугольников Пи вида [а1,а1+13х[^,Ьл+1], где

Ь-а

а< = а + - (1-1), 1=1.....N

N

й-с

ь с + - СЗ-1), 3=1.....N

N

Область 5 строится в виде объединения ШКМхИ прямоугольников Пи- Приведем общую схему алгоритма поиска области б, такой, что 1111^1 минимальна, среди всех областей вида Ш^.

1 шаг. Вычисляются глобальные степени неустойчивости ЦипИ и IIиг21 в каждом прямоугольнике Пц (1,Л=1.....Ю-

2 шаг. Формируется массив

/ и ¡И" {

V О,

U lUfil < |Uf2l lUfil > lUfgll

1,3=1,....N

Массиву z ставится в соответствие область Sz = ЦЩ^

1. j: z Ci. j 3=1

которая является областью предпочтения fi.

3 шаг. Подсчитывается число проверок неравенств для установления принадлежности области Sz. Например, проверка принадлежности x=(xj,2) е sz, где область Sz изображена на рис.1, осуществляется по следующему правилу:

(Х2 е [аг,ЬгЗ and xi.e tai а43) or (Х2 £ Шг.Ьз] and xi 6 [aj аэЗ) or (Х2 £ [b3,b43 and (xi 6 [a,ai] or xi £ Саз,84])).

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

ai аг аз а4

Ъх bz Ьз Ь4

хххх хххх хххх хххх

хххх хххх хххх

хххх хххх

хххх хххх

Рис. 1.,, Область S2 состоит из 12 прямоугольников Щ j.

Был проведен численный эксперимент по построению смешанного алгоритма вычисления функции Их^хг) = Х12 + хг В прямоугольнике

Б = [-1..0,1.0]х[-0.2,0.83 из двух алгоритмов й и {2 приближенного вычисления Г с ошибками 61 и 62 соответственно. Результаты, работы программы показаны на рис.2. 0 0 0 0

1

0 0 0 0

1 1 1 1

1 1 1 1

1 1 1 1

О

1

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

Глобальные степени неустойчивости первого и второго алгоритмов соответственно равны 1.483490 и 1.491946. При ограничении на число проверяемых неравенств, равном 12, степень неустойчивости смешанного алгоритма равна 1.477987, а при ограничении, равном 4, составляет 1.478347.

2.Подверженность влиянию ошибок машинного округления

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

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

3. Построение смешанного алгоритма

Можно поставить более общую задачу - не выбор наилучшего по

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

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

Определение 4: Пусть А и В - алгоритмы из g и R, тс - семейство (некоторых) подмножеств g. Тогда класс алгоритмов вида Als+B(l-ls), где s е it, назовем классом смешанных алгоритмов по семейству тс. Обозначим этот класс знаком Mix(А,В|я).

Замечание 3: множество s С g будем называть конструктивным, если указан алгоритм Memb(x,s) проверки принадлежности x6s.

В этом случае смешанный алгоритм С может быть описан так:

0 шаг. input (х)

1 шаг. b <— Memb(x.s)

2 шаг. С(х) <— if b then А(х) else В(х)

Через X обозначим некоторое конструктивное разбиение g, а через я - алгебру множеств, порожденную разбиением X

Л

Определение 5: пусть %. - п-мерный случайный вектор, Р - его распределение, supp Р С g С Rn, D - алгоритм из g в R, реализующий функцию f, Н - некоторое нормированное пространство случайных величин с нормой 1...Ц, f(e,),D(e,) £ Н. Ошибкой алгоритма D назовем число errD=i|D(0-f(ОН-

В качестве нормы будем рассматривать норму пространства Lp.

Тогда:

еггр = E|D(0- f(Olp = E(|D0U-f(Olp/g,es)x

х P(S) + E(|DCO-f(Olp/ <£s)-P(g\s) =

P P

= P(s) err + (1-P(s))err .

Пусть p - семейство подмножеств g, такое, что V s e ^ 3 si,...,sn€p, такие, что si л Sj=0 (i*j) и si и. ..u sn = s.

Определение 6: мерой сложности множества s назовем число

к(х)

Compl(s) = inf sup Е Time(Mb(х,Si)),

(S!----,sn) x£g i=rl

l^J => Si n Sj=0 S=S1 U.. .U sn

где Sj€p, x£sk(x). Time - время работы алгоритма. Для многих случаев Time(Mb(x,s¡) не зависит от х, иди же используется мажоранта, так что Time(Mb(x,Si))=ti и, следовательно,

kíx)

Compl(s) - Inf sup Е ti = Inf E ti (si,----sn) x£g 1-1 (si,...,sn) 1

Определение 7: Пусть С - мера сложности на й . Классом ограниченной сложности назовем подкласс В(С,к) класса М1х(А,В|к) .состоящий из смешанных алгоритмов с переключающими

А

множествами s, удовлетворяющими условию C(s)<k.

Определение 8: Алгоритм D из В(С,к) с минимальным значением erro будем называть оптимальным алгоритмом ограниченной сложности.

Теорема 1: задача поиска оптимального смешанного алгоритма ограниченной сложности эквивалентна задаче целочисленного линейного программирования с одним ограничением в виде неравенства,

т.е., если D£Mix(A,B|K), то задача минимизации р р р

err = P(s) err + (1-P(s))err da в

с ограничением вида C(sX k (k=const)

эквивалентна задаче минимизации линейного функционала п

v(s) =* E pjXj, где Р4= J( lA-fl!?||B-fIP)dP , xj6ío,1>

Si

с ограничением вида n

C(s)= E nijXj<k,

где Шэ=Т(5^) - время проверки принадлежности множеству

Таким образом, исходная задача эквивалентна задаче минимизации

п п

функционала £ р^х^ при условии Е

3=1

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

В заключении формулируются основные результаты работы.

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

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

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

2. Разработано функциональное наполнение пакетов прикладных программ по вычислительной математике и математической физике. Пакеты сданы в ГОСФАП.

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

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

5. Предложен статистический метод синтеза смешанного оти-мального алгоритма по отношению к вышеперечисленным критериям качества.

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

4, СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ.

1. Ляшенко H.H., Евневич Е.Л. "Статистические задачи выбора и синтеза оптимальных алгоритмов". Записки научных семинаров ЛОМИ, т.166, Наука, Лен.отд., 1988. - с.72-90.

2. Евневич Е.Л. "Статистический метод синтеза смешанного алгоритма, оптимального по устойчивости." В сборнике "Математические методы построения и анализа алгоритмов." Л.:Наука, 1990.

3. Евневич Е.Л. " Технология автоматического выбора алгоритмов. " Областная научно-практическая конференция молодых ученых и специалистов "Математическое моделирование",- Ленинград: 1988.

4. Евневич Е.Л. "Некоторые показатели качества программ", Международная конференция по качеству ПО, -С-Пб.:СПИИРАН, 1992.

5. Воробьев В.И., Гаврилова H.H., Колесникова О.Н., Евневич Е.Л., Фотиев Н.В. Пакет прикладных программ "Решение задач вычислительной математики", ВНТИ Центр. "Алгоритмы и программы", информационный бюллетень 1(64), 1985.

6. Воробьев В.И., Макаренко И.П., Евневич Е.Л., Фотиев Н.В. Пакет прикладных программ "Решение задач математической физики", ВНТИ Центр. "Алгоритмы и программы", информационный бюллетень 3(66), 1985.

7. Афанасьев C.B., Воробьев В.И., Евневич Е.Л., Панкова Л.Н., Юсупов P.M. "Проект регионального суперкомпьютерного центра", IV Санкт-Петербургская конференция "Региональная информатика-95", -С.-Пб.,1995.

Подписано к печати 14.II.96. .Заказ 308 Тираж 100 Объем 0,75 п.д. Ц0П СПГУ. 199034, Санкт-Петербург, наб. Макарова,6.