Введение к работе
глціій I
Актуальность темы. Анализ ошибок округления является одной из самых трудных проблем в процессе конструирования и изучения численных алгоритмов. До сих пор известны три подхода к этой проблеме- прямой анализ,' обратный анализ и интервальный анализ.
Идеи прямого и обратного анализа оказались неконструктивными, требующими изобретательности для каждого отдельного алгоритма. Обратный анализ, рассмотренный Уилкинсоном (Алгебраическая проблема собственных значений, М., Наука, 1970) и Воеводиным (Вычислительные основа линейной алгебры, И., Наука, 1977), не дает ответ на такие вопросы, как например, когда возможен глобальный обратный анализ, почему получались разные оценки для одного и того же алгоритма, где узкие места алгоритма, в чем заключается похожесть или непохожесть процессов оценивания ошибок округления, какова связь между прямым и обратным анализом и т.д. Прямой анализ Штумеля (Stunmel F., Hatn. Сотр., v. 37(156), 1981. pp. 435-473) не дает меру обратной устойчивости алгоритмов, потому что не оценивается суммарное влияние всех ошибок округления. Кроме того, иногда обратный анализ дает лучшие оценки чем прямой.
В интервальном анализе ничего не говорится о времени реализации алгоритма. Для этого подхода алгоритм является черным ящиком и ничего не ясно о качественных характеристиках алгоритма. Этот подход улучшает арифметику компьютера, выполнение элементарных машинных операций, а не исследует каковы особенности алгоритма в целом.
По этим причинам интересной является задача гостроения общего подхода к оценкам ошибок округления отдельных методов и объяснения некоторых из перечисленных выше вопросов.
Цель работы состоит в построении нового метода исследования ошибок округления, который бил бы тесно связан с графом алгоритма и его параллельными формами, а также в приложении этого метода к различным алгоритмам.
Методика ис еле давания. В диссертации используются в основном математические методы исследования. графов алгоритмов и их
-2-параллельше формы, а также некоторые результаты линейной алгебры.
Научная новизна. Предложен новый метод исследования ошибок округления, который позволяет поставить исследование ошибок округления на алгоритмическую основу. Метод тесно связан с параллельной струкутурой графа алгоритма. Сделаны вывода о возможности оОратного анализа для алгоритма и для' задачи.
Новый метод применяется к некоторым алгоритмам линейной алгебры. Проведено сравнение графов алгоритмов Гаусса и Иордана и влияние этих графов на оценивание ошибок округления. Исследование метода вращений показывает, что разные по порядку оценки для этого метода получались из-за того, что неявно были использованы разные параллельные формы графа алгоритма. Показано, что обратный анализ возможен для одного шага метода окаймления и для метода циклической редукции для линейных систем с трехдиагональными матрицами, з также получены соответствующие оценки эквивалентных возмущений. С общих позиций получаются.оценки для двух алгоритмов суммирования чисел, метода отражений, прямого треугольного разложения и разложения Холецкого, для некоторых алгоритмов, основные части которых являются рекуррентными последователльностями: явные разностные схемы, метод треідаагональной и пятадиагональной прогонки, треугольное разложение для трехдиагонзльных матриц и т.п.
Практическая ценность. Полученный метод исследования ошибок округления может быть применен и к другим алгоритмам для получения теоретических оценок прямого вли обратного анализа по графу алгоритма. Поскольку этот метод ставит исследование ошибок округления на алгоритмическую основу, полученные результаты могут быть использованы для автоматизации всего процесса оценивания ошибок в аналитическом или численном виде.
Апробация работа. Результаты выполненнх исследований докладывались:
Workshop оа Parallel and Distributed Processing, Sofia, March 27-30. 1990.
на семинарах Отдела вычислительной математики АБ СССР.
на семинарах Координационного центра информатики и
вычислительной техники Болгарской АН.
Публикации. По теме диссертации опубликовано 3 работ, список которых приведен в конце автореферата.
Структура и объем работы. Диссертация изложена на 143 страницах и состоит из введения и двух глав (16 параграфов). Список литературы содержит 50 наименований. Число рисунков 21.
