§ 8. Суммарный эффект влияния ошибок округления.

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

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

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

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

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

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

В этом случае ошибку вычисленного решения характеризует и элемент который принято называть эквивалентным возмущением. Если формулу (8.1) переписать в виде

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

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

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

Даже в случае математически точного задания входных данных ошибки в них почти неизбежно появляются за счет округления чисел при вводе в ЭВМ. Это минимальные из возможных ошибок.

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

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

и матрицы невырожденные. Если то

Следовательно, матрица получается в результате точного умножения матрицы А на матрицу

Реальный вычислительный процесс приводит в общем случае к построению такой последовательности:

Здесь матрицы, реально получаемые в процессе вычислений, — матрица ошибок от умножения на Имеем

Обозначим кроме этого, положим

тогда

Сравнивая (8.2), (8.6), заключаем, что реально вычисленная матрица может рассматриваться как полученная в результате точного умножения возмущенной матрицы на матрицу при этом для эквивалентного возмущения имеется явная формула (8.5). Если вычисленные матрицы асимптотически близки к унитарным, то

для -нормы или евклидовой нормы.

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

УПРАЖНЕНИЯ

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