1.1. Компьютерная алгебра и численный анализ

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

При выполнении численных расчетов на компьютере мы обычно сталкиваемся с проблемой представления бесконечного множества вещественных чисел в компьютере с конечной памятью и данной длиной слова. Наиболее распространенный способ решения этой проблемы в численном анализе — приближать вещественные числа, используя конечное множество чисел с плавающей точкой. Множество F чисел с плавающей точкой характеризуется основанием счисления точностью t и областью значений экспоненты где параметры и U явным образом зависят от компьютера. Каждое число с плавающей точкой из множества F может быть представлено в виде

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

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

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

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

Рис. 1.1.1. Система чисел с плавающей точкой при . (Forsythe, G.E., М.А. Malcolm, С.В. Moler. Computer methods for mathematical computations, 1977, p. 12. Воспроизведено с разрешения издательства Prentice-Hall, Inc., Englewood Cliffs, New Jersey.)

Из сказанного выше следует, что сумма (или произведение) данных чисел из множества F может не принадлежать F и должна быть приближена ближайшим числом с плавающей точкой. Разность между истинным и приближенным значением суммы (или произведения) является ошибкой округления. Следует также отметить, что операции сложения и умножения в F не являются ассоциативными и закон дистрибутивности тоже не выполняется. Рассмотрим, например, в нашем игрушечном -точечном множестве F выражение где числа 5/4, 3/8 и 2 принадлежат F. Однако в этом выражении () поскольку сумма не принадлежит F и должна быть приближена либо числом 3/2, либо числом 7/4. Ошибки округления встречаются не только при использовании чисел с плавающей точкой; они могут возникнуть и при работе с целыми числами, например в случае, когда мы хотим вычислить произведение двух -значных чисел в компьютере, который не может обрабатывать числа, содержащие больше s цифр.

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

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