Дж. Деммель - Вычислительная линейная алгебра, страница 3

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

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

Это свойство, называемое обратной устойчивостью, определяется следующим образом. Обозначим через а13(х) наш алгоритм для Дх); в вычисляемый алгоритмом результат включены эффекты округлений. Будем говорить, что а13(х) является обратно устойчивым алгоритмом для Дх), если для всякого х найдется «малое» бх, такое, что а13(х) = Дх + бх).

Величина бх называется обратной ошибкой На неформальном уровне можно сказать, что мы получаем точный ответ ( 1'(х+ бх)) для слабо возмущенной задачи (х+ бх). Сказанное означает, что для погрешности можно предложить такую оценку: погрешность = (а)3(х) — Дх)( = ~Дх+ бх) — Дх)) (1'(х)! (бх(, т.е. произведение абсолютного числа обусловленности ~~'(х) ~ и величины обратной ошибки 1бх(. Итак, если алгоритм а13( ) обратно устойчив, то величина )бх! всегда мала, поэтому, если абсолютное число обусловленности не слишком велико, мала будет и погрешность.

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

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

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

К примеру, умножение матриц на рабочей станции 1ВМ В.86000/590 можно ускорить с 65 мегафлопов (миллионов операций с плавающей точкой, выполняемых за секунду) до 240 мегафлопов, т.е. почти в четыре раза, посредством разумного переупорядочения операций в стандартном алгоритме (и правильного выбора оптимизирующего транслятора).

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

Чтобы ответить на этот вопрос, нужно прежде всего определить, является ли сходимость линейной (на каждом шаге погрешность умножается на постоянное число 0 < с < 1, т.е. ) погрешность,. ( < с) погрешность, ! 1) или более быстрой, например, квадратичной (! погрешность; ) < с ~ погрешность; 1з). Если сравниваются два итерационных алгоритма, и оба линейны, то можно спросить, какой из них имеет меньшую константу с.

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

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

Это собрание наисовременнейших программ, существующее в двух версиях: на языках Рогггап и С. Как и многие другие подобные библиотеки, ЬАРАСК распространяется бесплатно (см. г!ЕТЫВ на %%%!). 1 АРАСК обеспечивает надежность и скорость вычислений (например, в нем реализована отмеченная выше возможность ускорения матричных умножений), однако от пользователя требуется внимательное отношение к выбору структур данных ! Напоминаем, что в книге 1ЧЕТь1В используется кнк сокращение для ОН!-префикса М!р:!/интспес1!Ь.огх. 15 1.4. Пример: вычисление многочлена и построению последовательностей вызова подпрограмм.

На протяжении всей книги мы будем информировать читателя о программном обеспечении этого типа. Второй формой являются программные среды, значительно более дружественные к пользователю по сравнению с библиотеками типа ЬАРАСК; это достигается, правда, ценой некоторой утраты производительности. Эту форму представляют коммерческая система МанаЬ [184] и ряд подобных ей систем. Маг)аЬ можно рассматривать как простую интерактивную программную среду, где все переменные интерпретируются как матрицы (при этом скаляры суть 1 х 1-матрицы) и большинство операций линейной алгебры реализованы как встроенные функции.

Например, оператор «С = А * В» присваивает переменной С значение произведения матриц А и В, а оператор «А = 1пч(В)» делает значением А матрицу, обратную к В. В среде Мас1аЬ можно легко и быстро реализовать алгоритм-прототип, а затем, запустив его, проверить, как он работает. Так как, однако, МанаЬ принимает ряд алгоритмических решений автоматически, не консультируясь с пользователем, то получаемые этим путем программы могут работать медленнее, чем удачно выбранные библиотечные программы. Третья форма — это шаблоны или, иначе говоря, рецепты для сборки сложных алгоритмов из более простых «строительных блоков». Шаблоны полезны в ситуации, когда алгоритм можно построить многими разными способами, но при этом отсутствует простое правило выбора наилучшей конструкции для конкретной входной задачи; таким образом, значительная роль в конструировании должна быть оставлена пользователю.