Графы вычислительных процессов

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

Рис. 1.3. Графы вычислительных процессов основных арифметических операций.

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

В качестве примера рассмотрим выражение и задачу оценки общей погрешности результата его вычисления с учетом ошибок округления результатов выполнения арифметических операций. Предположим, что , и – относительные погрешности округления чисел , и при представлении их в памяти ЭВМ, а и – относительные ошибки округления соответственно результатов операций сложения и умножения. Учитывая последовательность операций, для рассматриваемого выражения граф вычислительного процесса будет иметь вид, представленный на рис. 1.4.

Рис. 1.4. Граф вычислительного процесса для выражения .

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

.

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

.

Поскольку причина ошибок округления и представления чисел в памяти ЭВМ одна – ограниченность ее разрядной сетки, – то для относительных ошибок можно положить . Тогда формулу расчета общей погрешности вычисления значения можно упростить:

.

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

Вопросы для самопроверки

1. Перечислите основные этапы исследования и математического моделирования явлений реального мира, раскройте их содержание.

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

3. Дайте определение численных методов, охарактеризуйте аналитические и приближенные методы.

4. Перечислите основные этапы решения математических задач с применением ЭВМ, раскройте их содержание и взаимосвязь.

5. Сформулируйте и поясните основные проблемы вычислительной математики.

6. Сформулируйте общую постановку задачи вычисления, дайте определение корректной задачи, раскройте ее содержание.

7. Охарактеризуйте понятие устойчивости решения задачи.

8. Перечислите основные источники погрешностей и раскройте их сущность.

9. Дайте определение абсолютной и относительной погрешности, приведите примеры.

10. Дайте определение значащих и верных цифр в записи чисел, приведите примеры.

11. Запишите формулы расчета абсолютной и относительной погрешности результата сложения чисел и , где и – их погрешности.

12. Запишите формулы расчета абсолютной и относительной погрешности результата вычитания чисел и , где и – их погрешности.

13. Запишите формулы расчета абсолютной и относительной погрешности результата умножения чисел и , где и – их погрешности.

14. Запишите формулы расчета абсолютной и относительной погрешности результата деления чисел и , где и – их погрешности.

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

16. Объясните принцип представления чисел с плавающей точкой в памяти ЭВМ.

17. Каковы особенности выполнения арифметических операций над машинными числами?

18. Что является вершинами и дугами графа вычислительного процесса, значения каких параметров соответствуют его вершинам и дугам?

19. Приведите примеры графов вычислительных процессов основных математических операций, какие параметры соответствуют их дугам?

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