Разработка и исследование статического и динамического методов управления точностью в системе синтеза алгоритмов

• Автор: Кулида, Сергей Владимирович
• Шифр специальности: 01.01.10
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Москва
• Количество страниц: 137 c. : ил

ГЛАВА I. СТАТИЧЕСКИЙ МЕТОД УПРАВЛЕНИЯ ТОЧНОСТЬЮ

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

1.2. Существование решения

1.3. Многошаговый процесс решения

1.4. Обсуждение практических аспектов

ГЛАВА 2. ДИНАМИЧЕСКИЙ МЕТОД УПРАВЛЕНИЯ ТОЧНОСТЬЮ

2.1. Постановка задачи. Достаточные условия

сходимости метода регуляризации

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

2.3. Обсуждение результатов

2.4. Обсуждение практических аспектов

ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА
ПРИЛОЖЕНИЕ I. Описание программной реализации
ПРИЛОЖЕНИЕ 2. Тексты программ и листинги примеров
работы системы САГАТ

ВВЕДЕНИЕ ОБЗОР ИНСТРУМЕНТАЛЬНЫХ СИСТЕМ АВТОМАТИЗАЦИИ ПРОГРАММИРОВАНИЯ
В последнее время происходит широкое внедрение ЭВМ в различные сферы человеческой деятельности. Причиной этого является ряд факторов, среди которых можно вьщелить возрастание количества и сложности современных задач, увеличение значения моделирования, эффективного управления и численного эксперимента. Рост числа пользователей ЭВМ вызывает повышенное внимание к развитию математического обеспечения вычислительных машин. Вместе с разработкой все более мощных и совершенных инструментальных средств работы с машиной наблюдается тенденция к созданию программного обеспечения не только необходимого, но и удобного для человека, позволяющего упростить и в значительной степени облегчить работу пользователя.
Особенно актуальными становятся исследования в области автоматизации программирования. К этому разделу программирования, разрабатывающему методы автоматического составления программ, относится большой круг работ по созданию таких языковых средств и программного обеспечения современных ЭВМ, которые обеспечивали бы реализацию задач пользователей при возможно меньших затратах труда программиста, см. например [ 18 , 22, 24, 46 , 47 , 53, 58, 59, 60-64]. Рассмотрим некоторые вопросы, касающиеся данного направления исследований.
За время эксплуатации ЭВМ создано большое количество научных и прикладных программ. В связи с продолжающимся накоплением программ ставится задача их эффективного использования. Во избе-

жание дублирования работ наиболее употребительные программы собраны в библиотеки программ [53, 54]. Обычно в таких библиотеках имеется несколько различных программ, предназначенных для решения одной и той же задачи. Возникает проблема выбора, при которой пользователь (программист) должен ознакомиться со структурой и семантикой формальных параметров всех программ, относящихся к его задаче, а затем отсеять неприменимые программы и выбрать среди оставшихся наиболее соответствующие, по его мнению, решаемой задаче. Этот выбор субъективен и основан, как правило, на личном опыте и квалификации программиета-математика. Кроме того, описания библиотек обычно очень обширны, а программы, содержащиеся в них,столь разнотипны, что для их изучения требуется немало труда. Этим в значительной мере объясняется недостаточно эффективное использование библиотек программ. Следовательно, естественны попытки в какой-то мере автоматизировать процесс выбора. Данную цель и преследуют различные пакеты прикладных программ и системы синтеза алгоритмов.
Системы автоматизации программирования призваны так же предоставить пользователю максимально удобные средства работы в избранной области, освободить человека от рутинной работы при оформлении программы для счета на ЭВМ. Создаваемая на факультете ВМиК МГУ система автоматизированной генерации алгоритмов с гарантированной точностью результатов (САГАТ) [28, 29, 40-43, 52-54] преследует такие же цели. Первая версия системы называлась САИБ (система автоматизации использования библиотек). Поскольку система осуществляет точностной анализ алгоритмов, она переименована в САГАТ. Система предназначена для синтеза алгоритмов ре-

Предположим, что Ук не пусто. Рассмотрим последовательность (}*~пап, д. (д). Можно ли надеяться хотя бы на выполнение равенства Сип, (£- (г* = (г(а) , при условии, что А(к)(л)-*к (а)
К-*-схэ I/ '
при к-*оэ ? В общем случае ответ на этот вопрос отрицательный, Задачи минимизации на приближенно заданных множествах, вообще говоря, некорректны, и для их решения надо применять специальные методы регуляризации [14, 31, 34, 48 , 49].
Приведем пример из [ 14]
Пусть ищется минимум & (а)=Л на множестве
и={д: ; &(д) = Д-Л+а+^~%40}
Очевидно, (г*= £(2)=-/ и множество и точек мини-

мума состоит из одной точки А--1 . Предположим, что функция к (а) нам точно неизвестна и задана в вцде
ъ%)=аиА-1+кь+1-2, г*е &е<
Может случиться, что ССК >8К>0 и тогда множество
Ц- = ^А■ А 0^: А Ф %{р,К + }К=1г&г~ , функция (г(а) = А в этом случае
будет достигать своей нижней грани (г* на 17к в точке Дк= 0 . Ясно, что (т* = 0Ф-1~(г*; кою Ак Ф д*.
К-*0° Л К-*°о
Этот пример показывает, что при сколь угодно малой погрешности в задании множества (7 и даже при непрерывных к (а) и № (а) нижняя грань функции (г (1) на возмущенном множестве 1/к может значительно-отличаться от нижней грани этой функции на исходном точно заданном множестве. Иначе говоря, погрешности в задании множества V могут привести к неустойчивости даже тогда, когда ищут лишь значение (9* , не