Лекция 2. Машинная арифметика и погрешности вычислений

Закладывая что-то в память ЭВМ, помните, куда вы это положили.

Первая компьютерная аксиома Лео Бейзера

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

Закон ошибок Грельба

Двоичные числа

В арифметике обычно используется десятичная система исчисления (с основанием 10). Большинство компьютеров использует арифметику с двоичной системой счисления (основание 2). Может показаться, что это не так, поскольку общение с компьютером (ввод-вывод) происходит в числах с основанием 10. Но это не означает, что компьютеры используют основание 10. На самом деле они приводят входные числа к основанию 2 (или, возможно, к основанию 16), затем выполняют арифметику при основании 2 и наконец преобразовывают ответ к основанию 10 прежде, чем показать результат. Для подтверждения этого требуется несколько экспериментов. Компьютер, который выполняет вычисления с точностью девять десятичных знаков, дает ответ

k=1

Имеются в виду сложение числа 101 100000 раз. Математический ответ ра-

вен точно 10000. Наша цель – понимание оснований очевидной ошибки компьютерного вычисления.

Основание 10 используется в большинстве математических задач. Для иллюстрации представим число 1563 в следующем виде:

1563 =(1 103 )+(5 102 )+(6 101 )+(3 100 )

В общем случае, когда N – положительное целое число, существуют однозначные числа a0 , a1 , ..., ak такие, что число N представимо при основании 10 в

Этоможноподтвердить, выполниввычисления:

1563 = 1024 + 512 + 16 + 8 + 2 + 1

15

В общем случае, если N – положительное целое число, следовательно существуют однозначные числа b0 , b1 , ..., bj , такие, что число N при основании 2 можно

где каждое число bj равно либо 0, либо 1. Таким образом, N в двоичном обо-

Используя обозначения (2.5) ирезультат (2.3), получим:

1563 = 11000011011ДВА

Замечания. Слово "два" всегда будет употребляться в качестве индекса двоичного числа. Это позволит отличать двоичные числа от обычных чисел с основанием 10. Так, число 111 означает сто одиннадцать, в то время как 111ДВА

– семь.

Ясно, что для двоичного представления числа N потребуется больше цифр, чем для десятичного, поскольку известно, что степень 2 растет намного медленнее, чем 10.

Эффективный алгоритм нахождения представления целого числа N с основанием 2 можно вывести из равенства (2.4). Разделив обе части равенства (2.4) на 2, получим:

Таким образом, остаток от деления числа N на 2 и есть цифра b0 . Далее

Разделив обе части (2.7) на 2, получим:

Q20 =(bj 2 j−2 )+(bj−1 2 j−3 )+ ...+(b2 20 )+ b21 .

Следовательно, остаток от деления Q0 на 2 равен цифре b1 . Продолжая этот процесс, получим последовательности {Qk } и {bk } отношений и остат-

ков соответственно. Процесс завершится, когда найдется такое целое число J, что QJ =0 . Следовательно, последовательность удовлетворяет следующим

равенствам:

N = 2 Q0 + b0 Q0 = 2 Q1 +b1

16

Научное обозначение

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

0,0000747 =7 ,47 10−5

31,4159265 = 3,1415965 10

9700000000 = 9,7 109

Машинные числа

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

В компьютере используется только небольшое подмножество системы представления действительных чисел. Типично, что это подмножество содержит только часть двоичного числа, предложенного в (2.9). Количество двоичных знаков ограничено двумя числами q и n.

Компьютерные числа с плавающей точкой

Вкомпьютере имеются как целая форма представления чисел, так и форма

сплавающей точкой. Целая форма используется для вычислений с целыми числами и имеет ограниченное применение в численном анализе. Должно быть понятно, что любой компьютер, выполняя (2.9), ограничивает количество цифр, используемых в мантиссе q, и возможный диапазон показателя степени n должен быть ограничен.

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

2−23 = 1,2 10−7 ).

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

Если у компьютера имеется 64 двоичных разряда для двойной точности действительного числа, то он может использовать 11 двоичных разрядов для показателя степени и 53 двоичных разряда для мантиссы. Они могут представлять действительные числа в интервале

(т.е. от 2-1024 до 21023) приблизительно с 16 десятичными знаками точности (например, 2−52 = 2,2 10−16 ).

Погрешность решения задачи

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

Если а – точное значение некоторой величины, а а* – известное приближение к нему, то абсолютной погрешностью приближенного значения а* на-

зывают обычно некоторую величину a* = a −a* (в общем случае a имеет

размерность величины а).

Относительной погрешностью приближенного значения называют не-

которую величину δ , которая выражается отношением δ = aa** .

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

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

Так как величина а, как правило, неизвестна, а погрешность необходимо

определить, то в рассмотрение вводится предельная абсолютная погрешность

(a*):