Новый метод исследования ошибок округления и его приложения тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

АКАДЕМИЯ НАУК СССР ОТДЕЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ

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

ЯЛЫМОВ Пламен Йорданов

НОВЫЙ МЕТОД ИССЛЕДОВАНИЯ ОШИБОК ОКРУГЛЕНИЯ И ЕГО ПРИЛОЖЕНИЯ

01.01.07— Вычислительная математика

АВТОРЕФЕРАТ

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

МОСКВА- 1 990

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

Научный руководитель член-корреспондент АН ССС Воеводин В. В.

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

доктор физико-математических наук Третьяков А. А.; кандидат физико-математических наук Финогенов С. 1

Ведущая организация Научно-исследовательский вычисл! тельный центр Московского государственного университет им. М. В. Ломоносова

Защита состоится 1990 г. в-Жйас

на заседании специализированного совета К 003.47.01 в О" деле вычислительной математики АН СССР по адресу: 11903-Москва, ул. Рылеева, 29.

С диссертацией можно ознакомиться в библиотеке Отдел вычислительной математики АН СССР.

Автореферат разослан » 1990 г.

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

Агошков В. V

/

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

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

Идеи прямого и обратного анализа оказались неконструктивными, требующими изобретательности для каждого отдельного алгоритма. Обратный анализ, рассмотренный Уилкинсоном (Алгебраическая проблема собственных значений, М., Наука, 1970) и Воеводиным (Вычислительные основа линейной алгебры, И., Наука, 1977), не дает ответ на такие вопросы, как например, когда возможен глобальный обратный анализ, почему получались разные оценки для одного и того же алгоритма, где узкие места алгоритма, в чем заключается похожесть или непохожесть процессов оценивания ошибок округления, какова связь между прямым и обратным анализом и т.д. Прямой анализ Штумеля (Бгите 1 ?., Ыагь. Сотр., V. 37(156), 1981, рр. 435-473) не дает меру обратной устойчивости алгоритмов, потому что не оценивается суммарное влияние всех ошибок округления. Кроме того, иногда обратный анализ дает лучше оценки чем прямой.

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

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

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

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

яараллельше формы, а также некоторые результаты линейной алгебры.

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

Новый метод применяется к некоторым алгоритмам линейной алгебры. Проведено сравнение графов алгоритмов Гаусса и Иордана и влияние этих графов на оценивание ошибок округления. Исследование метода вращений показывает, что разные по порядку оценки для этого метода получались из-за того, что неявно были использованы разные параллельные формы графа алгоритма. Показано, что обратный анализ возможен для одного шага метода окаймления и для метода ШпиШэской редукции для линейных систем с трехдиагональными матрицами, а также получены соответствующие оценки эквивалентных возмущений. С общих позиций получаются.оценки для двух алгоритмов суммирования чисел, метода отражений, прямого треугольного разложения и разложения Холецкого, для некоторое алгоритмов, основные части которых являются рекуррентными последователльтастями: явные разностные схемы, метод трехдиагональной и пятидиагональной прогонка, треугольное разложение для трехдиагональнш матриц и т.п.

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

Апробация работа. Результаты выполнены* исследований докладывались:

- Workshop on Parallel and Distributed Processing, Soils, March 27-30, 1990.

- на семинарах Отдела вычислительной математики АБ СССР.

- на семинарах Координационного центра информатики и

вычислитвльной техники Болгарской АН.

Публикации. По теме диссертации опубликовано 3 работ, список которых приведен в конце автореферата.

Структура и объем работы. Диссертация изложена на 143 страницах и состоит из введения и двух глав (16 параграфов). Список литературы содержит 50 наименований. Число рисунков 21.

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

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

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

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

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

1-2

массива А. Гем саммым устанавливается взаимнооднозначное соответстиэ между используемыми

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

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

Ч

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

А(к) = Р^СА^ .А^,...^ ), к = 1,2.....т. (1)

Формула (I) отражает точное вычисление векторов При

реальных вычислениях имеет место равенство

А(К) = Гк^.А^,...;^ ) = У^А^.А^.....А^ ) +

+ Т)(к), к -1.2.....ш. (2)

Здесь "приближенная" к ^ функция в реальных вычислениях, А^-реально вычисленный д-й элемент массива А, г)^'- вектор абсолютных ошибок- вычисления Считается, что т}^- известны. Потом

вычислительный процесс (2) представляется в виде

¿(Ю + е(к) _ р (д + е Г + е + ),

к Ч *2 *2 *гк Ч

к = 1,2,...,ш, (3) где е^- векторы таких не размеров, как и А^, е^..... е^ -

числа. Если представление (3) возможно, оно имеет очень простой смысл. Существует некоторый набор чисел е^ для всех элементов А^ массива А. Если реализовать алгоритм по точным формулам (I) с входными данными А^ + е^, то в каждом 3-м элементе массива А Судет

получаться значение + е^. По этой причине е^ и е^ называются

эквиваленгннми возмущениями.

Из формул (2) и (3) исключаются векторы А^' и получается система векторных уравнений:

ТЛЬ* Си + ¿1,.....1%, + е,. ) -

I

1УС АК

- Р^са^-.а^....,!^ ) = е(к) + т)(1с). к-1,2....т (4)

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

Если эквивалентные возмущения для каких-то груш оказались малыми, то можно надеется, что и эквивалентные возмущения очередной группы также будут малыми. В основе данного предположения лежит малость ошибки т/^) и произвольность эквивалентных возмущений для получаемых результатов, в силу чего эти возмущения также можно взять малыми. Пренебрегая членами второго порядка малости, из (4) получается, что

Р^е(гк) - е(к) = -т)(к), к * 1,2.....в, (5)

где е^к^Се^ .е^.....е^ и ^¿^¿(А^ .А^,.. ..А^ ) есть

производная Фреше вектор функции Р^. С точностью до членов второго порядка малости мэжно считать также, что производная и правая часть т]^ вычисляются в соответствии с точным выполнением алгоритма. Система (5) является линейной и имеет ввд

Ве = т). (6)

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

Размножение информации мешает обратному анализу. В параграфе 1.3 рассмотрен способ исключения размножения. Описан гомоморфизм, при котором из графа С получается макротраф С, в котором вершины

1-3

могут быть более крупными, дуги могут быть кратными и размножения информации нег.

Матрица В тесно связана с матрицей инциденции графа в. В параграфе 1.4 описывается эта связь.

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

В =

(7)

Это есть правая блочно-треугольная матрица, на главной диагонали которой стоят блочно-диагональные матрицы с блоками Каждая блочно-диагональная матрица соответствует одному ярусу параллелной формы. В заштрихованной части матрицы стоят элементы, равные либо 0, либо -I. На практике матрица В оказывается либс блочно-двухдиагональвой, либо Слочно-ленгочной с небольшой пшрино® ленты. Из (7), в частности, следует, что возможность проводит! локальный обратный анализ для каждой отдельной операции приводит к возможности проводить глобальный обратный анализ. Действительно, возможность всегда цроводить локальный анализ, по существу, означает, что ранг матриц ^ совпадает с числом их строк. Интересно отметить, что прямой анализ получается из той же системь (6), если заданы эквивалентные возмущения входных данных, а ищек эквивалентные возмущения выходных данных. В этом случае системг (6) всегда имеет решение.

Каждая задача может быть решена разными алгоритмами. В зраграфе 1.6 дано разложение эквивалентных возмущений входных энных е^:

е<°> = е<°>4 е<°>. %в зависит от алгоритма решения задачи, а е^- только от эдачи. Отмечено, что, если вычисления проводятся точно, то где не зависит от локальных ошибок т/1^, а зависит злько от эквивалентных возмущений выходных данных, которые Зозначены через если имеются Ь ярусов параллельной формы,

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

В параграфе 1.7 рассматривается связь мевду прямым и обратным зализом. Пусть С есть оператор, отображающий входные данные А*0* з выходные данные к^К т.е. . Тогда получено соот-

эшение

С'е^ е(1), (8)

це С- производная Ореше оператора С в точке А*-0', ззультат обратного анализа, а е^- результат прямого анализа, ак как прямой анализ всегда возможен, то из (8) видно, что озможность глобального обратного енализа определяется эвместностыо системы (8). Из (8) приходим к следующему выводу: лобальный обратный анализ возможен тогда и только тогда, когда анг матрицы С* равен числу строк этой матрицы. Это означает, что лобальный анализ может Сыть возможен, но неосуществим как процесс ешения системы типа (6) последовательно по вершинам. Такую итуацию определяет, например, невозможность локального обратного нализа для некоторой операции алгоритма.

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

машинной арифметики, ошибки основных арифметических операций.

В параграфе 2.2 исследуется обратный анализ двух алгоритм суммирования L чисел- классический и рекурсивное сдваиваии Рассматривается также экстремальная задача

|e(0)j2 -» пш,

где е^0*- вектор эквивалентных возмущений входных данных. В обе алгоритмах экстремальная задача имеет следующее решение:

Х-1

где локальные абсолютные ошибки. Алгоритм рекурсивно

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

В параграфе 2.3 рассмотрен метод Гаусса. Оценки обратно анализа совпадают с уже полученными.

Б. параграфе 2.4 исследуется метод Хордана. Использова. разные подходы. Обратный анализ прямо по графу дает оцен экспоненциально зависящие от размерности задачи. Поэта используе.тся другой подход, при котором выделяется подграф, ; которому вычисляется одна компонента решения и проводится обрати анализ для этого подграфа. Потом через связь (8) между прямым обратным анализом можно получить обратный анализ всего алгоритм Полученные оценки зависят уже линейно или квадратично < размерности задачи. Сравнивание графов метода Гаусса и мзто, Кордана показывает, что разные оценки получаются из-за того, ч не используется специфика этих графов. В методе Гауе размножаются только выгодные данные и это облегчает обрати анализ, а в методе Жордана размножаются входные данные и поэта нужно использовать другие подходы, чтобы получить хороший обрати анализ.

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

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

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

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

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

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

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

и =

и1 а1 ^2

аН-1

и нижний индекс буквы е обозначает соответствующее эквивалент] возмущение, то поллучены такие оценки, в случае, когда е< диагональное преоблаадание по строкам или по столбцам:

ЮвьСИ+и

(е^! -|С1|р м,

|е„ | * 0(Н)|Ь1|р-и1, Це^И! ^ 0(аЯ1ов^Н)|<1|1р-и1. а =. ЦТ^рГ1!,,

В случае, когда 0 есть М-матрица, третью оценку можно улучшить:

1^1 * 0(ЮЙ| К). Здесь р- осыование системы счисления, I- число разрядов мантиса

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

1. Предложен • новый метод исследования ошибок округлен который тесно связан с графом алгоритма и его параллель] структурой.

2. На основе этого метода сделан анализ ошибок некото] прямых методов для решения систем линейных уравнений, исходя

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

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

1. Воеводин В.В., Ялымов П.И., Новый метод исследования 1бок округления, М., ОВМ АН СССР, 1990, Препринт Но 231, 1989.

2. Ялымов П.И., Некоторые замечания об ошибках округления.// штектура ЭВМ и численные методы, М., ОВМ АН СССР, 1990, стр. 5-II6.

3. YalamoT P.Y., A new method of round-oH error analysis and j applications, Доклади на БАН, No 3, 1990.