BC/NW 2006, №2, (9) :7.1

О ВОЗМОЖНОСТИ ПРИМЕНЕНИЯ «БЕЗОШИБОЧНЫХ» ВЫЧИСЛЕНИЙ ДЛЯ РЕШЕНИЯ ЗАДАЧИ КОШИ

Д.А. Орлов, Ш.А. Оцоков

(Москва, Московский энергетический институт (технический университет), Россия)

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

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

Другое направление – это применение вычислений с исключением ошибок округления на основе модулярной арифметики [1].

Известно, что в модулярной системе счисления (МСС) любое целое число представляется в виде остатка от деления на выбранный модуль (простое число), а несократимые дроби (дроби Фарея) представляется в виде целых чисел, причем выполняется следующее неравенство [1]:

, (1)

где модуль МСС, порядок дробей Фарея или максимальное значение числителя и знаменателя несократимой дроби, представимой в МСС.

Например, при модуле , в МСС представляются дроби Фарея порядка 2, т.е. это следующие дроби:

Если в ходе вычислений в МСС получен результат, выходящий за пределы допустимого диапазона, определяемого неравенством (1), то такая ситуация называется псевдопереполнением.

Рассмотрим модель вычислений с исключением ошибок округления на основе модулярной арифметики (рисунок 1).

Рисунок 1 – Модель вычислений с исключением ошибок округления

В соответствии с этой моделью исходные данные (дроби) преобразуются в модулярную систему счисления (МСС) и представляются в ней в виде целых чисел, с которыми проводятся все вычисления с использованием модулярной арифметики[2].

Если нет ошибок псевдопереполнения, результаты преобразуются в искомые дроби Фарея [1].

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

x'(t)=t, x₀=0, t₀=0, (2)

поскольку в процессе его решения нет стремительного роста разрядностей операндов в МСС.

Затем, зная аналитическое решение, вычислим погрешности для каждого типа вычислений. При решении задачи Коши методом Эйлера с использованием вычислений с плавающей точкой существует некоторое оптимальное значение шага интегрирования, при котором обеспечивается наибольшая точность получаемого решения, дальнейшее уменьшение шага из-за накопления ошибок округления снижает точность [3]. Предполагается, что при использовании «безошибочных» вычислений подобный эффект наблюдаться не будет.

Для оценки погрешностей вычислений разработана программа. В разработанной программе вычисления реализованы следующим образом. Прежде всего, все числа, которыми оперирует программа – рациональные, представленные в модулярной системе. Для обеспечения требуемого диапазона их значений модуль должен быть достаточно большим, поэтому для его представления необходимо использовать целые числа большой разрядности. Задача Коши решается многократно с различным шагом интегрирования. Значение погрешности для данного шага вычисляется для конечной точки решения, так как в этом случае может быть накоплена максимальная погрешность округления. В качестве шага интегрирования были выбраны числа 1/2ⁿ, где n – натуральное. Такой шаг представим точно в формате с плавающей точкой, используемом в вычислительных машинах.

Результаты работы программы представлены на рисунке 2. На нём показаны зависимости погрешности решения задачи Коши E от числа n (показателя степени 2 в знаменателе шага интегрирования). Верхняя кривая представляет собой зависимость при использовании вычислений с плавающей точкой, нижняя – при использовании «безошибочных» вычислений.

Рисунок 2 – Зависимости погрешностей от шага интегрирования

Из графика видно, что при уменьшении шага интегрирования точность решения задачи Коши при использовании вычислений с плавающей точкой возрастает при n<19. Затем начинается резкий рост погрешности. При решении задачи с использованием «безошибочных» вычислений точность решения возрастает при уменьшении шага, кроме того в данном случае при n>12 они обеспечивают меньшую погрешность. Несовпадение зависимостей обусловлено наличием эффекта накопления ошибок округления при вычислениях с плавающей точкой. Исходя из полученных экспериментальных данных можно заключить, что при n>16 погрешность получаемого решения при безошибочных вычислениях будет стремится к нулю (пунктирная линия). Полученный результат говорит о возможности применения «безошибочных» вычислений для повышения точности решения задачи Коши.

ЛИТЕРАТУРА

1. Грегори Р., Кришнамурти Е. Безошибочные вычисления. Методы и приложения: Пер. с англ. – М.: Мир, 1998 – 208 с., ил.

2. Дзегелёнок И.И., Оцоков Ш.А. Экспериментальное исследование модели безошибочных вычислений на ПМК-сети КУРС 2000 // Сб. трудов международной научной конференции "Информационные средства и технологии" М.:МЭИ (ТУ), 2003.- C.103-106.

3. Амосов А.А., Дубинский Ю.А. Вычислительные методы для инженеров, 2003