§ 6. Порядок выполнения операций

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

С точки зрения точного выполнения операций расстановка скобок обычно не бывает однозначной. Это связано в основном с выполнением законов ассоциативности и дистрибутивности для операций. Однако для арифметических операций на ЭВМ указанные законы уже не имеют места. Следовательно, различные расстановки скобок в одном и том же арифметическом выражении будут теперь приводить к различным результатам.

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

Рассмотрим простой, но довольно показательный пример. Пусть вычисляется сумма где все — числа одного знака. Операция сложения коммутативна и ассоциативна. Поэтому точный результат не зависит от того, в каком порядке осуществляется суммирование.

Будем теперь вычислять эту сумму на ЭВМ в режиме плавающей запятой. Прибавим к первому слагаемому второе, к полученной сумме прибавим третье слагаемое и т. д. Согласно (5.4) имеем

Так как числа одного знака, то 1, поэтому

для всех Перепишем теперь формулу (6.1) в таком виде:

На современных ЭВМ величина очень мала. Следовательно, с точностью до

Полученные формулы означают следующее. Как вытекает из (6.2), суммирование чисел на ЭВМ в режиме

плавающей запятой эквивалентно точному суммированию возмущенных чисел с относительным возмущением в слагаемом а. Относительные возмущения неодинаковы. Согласно (6.3) они максимальны в первых слагаемых и минимальны в последних. Абсолютная ошибка вычисленной суммы равна

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

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

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

На первом этапе разобьем слагаемые на пары и сложим каждую из пар. Ясно, что в каждое слагаемое вошедшее в пары, будет внесено относительное возмущение одного порядка. Если четное, то каждое из входит в одну из пар, если нечетное, то одно слагаемое, не вошедшее ни в одну из пар, на первом этапе в суммировании не участвует.

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

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

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

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

УПРАЖНЕНИЯ

(см. скан)