§ 7. Запись на машинно-независимых языках

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

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

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

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

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

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

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

Рассмотрим некоторые примеры. Пусть в режиме плавающей запятой вычисляется евклидова норма вещественного вектора Согласно определению имеем

Обозначим через со минимальное положительное число, представимое на ЭВМ, и предположим, что для всех . Так как в этом случае

то и евклидова норма вектора окажется равной нулю.

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

Заменим теперь формулу (7.1), переписав ее в следующем эквивалентном виде:

где

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

и окончательно будем иметь

Пусть для определенности Может случиться, что для некоторых либо либо равно — 1. Предположим, что это имеет место для Согласно предположению относительно а величину можно не вычислять, а положить ее равной единице. Следовательно, Но тогда

Тот факт, что либо либо равно —1 для означает выполнение неравенства поэтому

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

округлением, то не превосходят по модулю Таковыми же будут и для Для величин заведомо

Если формулу (7.3) переписать следующим образом:

то теперь для можно получить достаточно простые оценки. С точностью до величин второго порядка малости будем иметь

Принимая во внимание, что и учитывая (4.7), находим

для всех причем эти оценки не зависят от применяемого способа суммирования.

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

где для снова имеет место оценка (7.5). Следовательно, вычисление по формуле (7.2) всегда гарантирует высокую относительную точность результата.

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

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

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

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

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

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

где

Снова видим, что вычисление произведения чисел в режиме плавающей запятой эквивалентно точному вычислению произведения возмущенных чисел с относительными возмущениями удовлетворяющими (7.6).

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

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

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

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

УПРАЖНЕНИЯ

(см. скан)

(см. скан)