Лекція 2. Машинна арифметика і погрішності обчислень

Закладаючи щось в пам'ять ЕОМ, пам'ятайте, куди ви це поклали.

Перша комп'ютерна аксіома Лео Бейзера

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

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

Двійкові числа

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

100000
∑ 0,1	=9999,99447	(2.1)

k=1

Маються на увазі складання числа 101 100000 разів. Математична відпо-

відь рівна точно 10000. Наша ціль – розуміння підстав очевидної помилки ком- п'ютерного підрахунку.

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

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

У загальному випадку, коли N – позитивне ціле число, існують однозначні числа a0 , a1 , ..., ak такі, що число N уявно при основі 10 у вигляді:

N =(ak 10k )+(ak−1 10k−1 )+ ...+(a1 101 )+(a0 100 ),

де числа ak приймають значення {0, 1, .., 8, 9}. Таким чином, N в десятко-

	вому записі уявно як
	N = akak−1 ...a2a1a0ДЕС	(десяткове).	(2.2)
	Якщо використовувати ступені 2, то число 1563 можна записати у вигляді:
	1563 = (1 210 )+(1 29 )+(0 28 )+(0 27 )+(0 26 )+		(2.3)
	+(0 25 )+(1 24 )+(1 23 )+(0 22 )+(1	21 )+(1 20 )

Цеможна підтвердити, виконавшипідрахунки:

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

15

У загальному випадку, якщо N – позитивне ціле число, отже існують однозначні числа b0 , b1 , ..., bj , такі, що число N при основі 2 можна представити у вигля-

ді:
N =(bj 2 j )+(bj−1 2 j−1 )+ ...+(b1 21 )+(b0 20	), (2.4)

де кожне число рівне або 0, або 1. Таким чином, N в двійковому позначенні можна виразити у вигляді

N = bjbj−1 ...b2b1b0ДВА

(двійкове)

(2.5)

Використовуючи позначення (2.5) ірезультат (2.3), одержимо:

1563 = 11000011011ДВА

Зауваження. Слово "два" завжди уживатиметься як індекс двійкового числа. Це дозволить відрізняти двійкові числа від звичних чисел із основою 10.

Так, число 111 означає сто одинадцять, тоді як 111ДВА – сім.

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

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

N

=(bj 2 j−1 )+(bj−1 2 j−2

)+ ...+(b1 20 )+

b0

.

(2.6)

2

2

Таким чином, залишок від ділення числа N на 2 і є цифра b0 . Далі визна-

чимо b . Якщо (2.6) записати як

N

=Q +

b0

, то

1

2

0

2

Q0

=(bj 2 j−1 )+(bj−1 2 j−2

)+ ...+(b2 21 )+(b1 20 ).

(2.7)

Розділивши обидві частини (2.7) на 2, одержимо:

Q0

=(bj 2 j−2 )+(bj−1 2 j−3 )

+ ...+(b2 20 )+ b1 .

2

2

Отже, залишок від ділення на 2 рівний цифрі b1 . Продовжуючи цей

процес, одержимо послідовності {Qk } і {bk } відносин і залишків відповідно.

Процес завершиться, коли знайдеться таке ціле число J, що QJ

=0 . Отже,

послідовність задовольняє наступнім рівностям:

N = 2 Q0 + b0

Q0 = 2 Q1 +b1

M

(2.8)

QJ −2 = 2 QJ −1 +bJ −1

QJ −1 = 2 QJ + bJ

(QJ =0)

16

Наукове позначення

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

0,0000747 =7 ,47 10−5

31,4159265 = 3,1415965 10

9700000000 = 9,7 109

Машинні числа

У комп'ютерах для дійсних чисел використовується нормоване двійкове уявлення із плаваючою крапкою. Це означає, що математична величина х насправді не зберігається в комп'ютері. Замість неї в комп'ютері зберігається двійкове наближення х:

			x ≈ ±q 2n	(2.9)
Число q з’являється мантисою, і це кінцеве двійкове уявлення, яке задо-
вольняє нерівності	1	2	≤ q < 1 . Ціле число n називається показником ступеня.
У комп'ютері	використовується			тільки невелика підмножина системи

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

Комп'ютерні числа із плаваючою крапкою

У комп'ютері з’являється як ціла форма представлення чисел, так і форма із плаваючою крапкою. Ціла форма використовується для обчислень із цілими числами і має обмежене вживання в чисельному аналізі. Повинно бути зрозуміло, що будь-який комп'ютер, виконуючи (2.9), обмежує кількість цифр, використовуваних в мантисі q, і можливий діапазон показника ступеня n повинен бути обмежений.

Комп'ютери із 32 двійковими розрядами, представляючи дійсне число із звичною точністю, використовують 8 двійкових розрядів для показника ступеня і 24 двійкові розряди для мантиси. Вони можуть представляти дійсні числа в

інтервалі	2,938736 E − 39	до 1,701412E + 38
від

(тобто від 2-128 до 2127) із шістьма десятковими знаками точності (наприклад,

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

Комп'ютери із 48 двійковими розрядами, представляючи дійсне число із звичною точністю, можуть використовувати 8 двійкових розрядів для показника ступеня і 40 двійкових розрядів для мантиси. Вони можуть представляти

дійсні числа в інтервалі
від	2,9387358771E − 39	до	1,7014118346 E + 38
(тобто від	2-128 до 2127) із 11	десятковими знаками точності (наприклад,

2−39 = 1,8 10−12 ).

17

Якщо у комп'ютера з’являється 64 двійкові розряди для подвійної точності дійсного числа, то він може використовувати 11 двійкових розрядів для показника ступеня і 53 двійкові розряди для мантиси. Вони можуть представляти дій-

сні числа в інтервалі
від	5,562684646268003E − 309 до	8,988465674311580E + 307

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

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

У практиці чисельного аналізу важливо усвідомлювати, що чисельне рішення – це не точне математичне рішення. Точність чисельного рішення зменшується з багатьох причин декількома тонкими способами. Розуміння цих труднощів часто може привести професіонала до правильного виконання та/або удосконалення чисельного алгоритму.

Якщо а – точне значення деякої величини, а а* – відоме наближення до нього, то абсолютною погрішністю наближеного значення а* звичайно нази-

вають деяку величину a* = a −a* (у загальному випадку a має розмір-

ність величини а).

Відносною погрішністю наближеного значення називають деяку величи-

ну, яка виражається відношенням δ =	a* .
	a *

Відносну погрішність часто виражають у відсотках, і тоді вона множиться на сто.

Таким чином, можна помітити, що помилка – це проста різниця між істинним і наближеним значеннями, тоді як відносна помилка – це частка істинного значення.

Оскільки величина а, як правило, невідома, а погрішність необхідно ви-

значити, то в розгляд вводиться гранична абсолютна погрішність

(a*):

a* =

a −a*

≤

(a* ).

(2.10)

Розкриваючи в цій нерівності модуль, одержуємо співвідношення, задаюче

відрізок, якому належить точне значення:

a* −

(a* )≤ a ≤ a* + (a* ).

(2.11)

Таким чином, величина а знаходиться в подвоєній

-околиці (дельта-

околиці), визначуваної величинами а* і

(a* )

і становлячої відрізок [х1, х2]

(рис. 2.1).

x1 = a* −

(a* )

a*

x2 = a* + (a* )

(a* )

(a* )

Рис. 2.1 Область визначення рішення

18