Арифметика рухомої коми

Відносні помилки і ulp'и

Обчисленням з рухомою комою властиві помилки заокруглення, тому важливо мати змогу вимірювати їх. Розглянемо формат рухомої коми з основою ($\beta$) 10 і мантисою ($p$) 4. Якщо результат обчислень з рухомою комою $3.143\times10^{-1}$,а результат із використанням нескінченної точності $0.3141$, тоді помилка рівна 2 одиницям в останній позиції (units in last place - ulp). \begin{equation} 1\mbox{ulp} = \beta\times \beta^{-p}\label{eq:ulp} \end{equation}

Якщо результат обчислень з рухомою комою лежить найближче до справжнього результата, то помилка все ще може становити $0.5$ ulp. Якщо дійсне число наближене за допомогою числа з рухомою комою, то помилка може бути завбільшки з $0.0005$ ($p=4, \beta=10$), або $\beta/2\times \beta^{-p}$.

Щоб обчислити відносну помилку, що відповідає $0.5$ ulp, зауважимо, що коли дійсне число наближається за допомогою числа з рухомою точкою $$d.\underbrace{d\dots d}_{p \mbox{ раз}}\times \beta^e,$$ то помилка може бути завбільшки з $$0.\underbrace{0\dots 0}_{p \mbox{ раз}}\beta'\times\beta^e,$$ де $\beta' = \beta/2$. Ця помилка рівна $(\beta/2)\times\beta^{-p}\times\beta^e$. Числа у вигляді $d.d\dots d\times\beta^e$ набувають значень в діапазоні $[\beta^e,\beta\times\beta^e)$. Отже, діапазон відносної помилки простягається від $\frac{(\beta/2)\times\beta^{-p}\times\beta^e}{\beta\times\beta^e}$ до $\frac{(\beta/2)\times\beta^{-p}\times\beta^e}{\beta^e}$. Скорочуючи, отримуємо такий діапазон для відносної помилки, що відповідає половині ulp \begin{equation} (\frac{1}{2}\times\beta^{-p}, \frac{\beta}{2}\times\beta^{-p}].\label{eq:re_ulp_diap} \end{equation} Таким чином відносна помилка, що відповідає одному ulp може відрізнятись на множник $\beta$. Встановлюючи $\varepsilon=(\beta/2)\times\beta^{-p}$ у значення більшої межі діапазону \eqref{eq:re_ulp_diap}, ми можемо сказати, що коли дійсне число заокруглене до найближчого числа з рухомою точкою, то відносна помилка завжди обмежена $\varepsilon$, яке ми називаємо машинним епсілон.

З того, що $\varepsilon$ може переоцінити ефект заокруглювання до найближчого числа з рухомою комою у $\beta$ разів, оцінки помилок у формулах будуть тугішими на машинах із маленьким $\beta.$

Відносна помилка при відніманні

У цьому прикладі ми використаємо той самий формат рухомої коми з основою ($\beta$) 10 і мантисою ($p$) 4. Припустимо нам потрібно порахувати різницю між $1$ і $0,9999$, в заявленому форматі вони виглядатимуть так $1.000\times 10^0$ та $9.999\times 10^{-1}$. Але для виконання арифметичних дій нам потрібно, щоб порядок у чисел був однаковим, тому друге число втратить одну цифру \begin{equation*}\begin{array}{c} \phantom{-}1.000\times 10^0\\ \underline{-0.999\times 10^0}\\ \phantom{-}0.001\times 10^0\\ \end{array}\end{equation*} Тоді як відповідь у випадку з нескінченною точністю становить $0.0001$, отже відносна помилка $\eta$, яка дорівнює різниці між двома значеннями поділеній на справжнє значення, така $$ \frac{|0.0001-0.001|}{0.0001} = \frac{0.0009}{0.0001} = 9 $$ Отже, відносна помилка може сягати $9 = \beta - 1.$

Вартові числа

Для подолання такої великої відностної помилки використовують вартові цифри (guard digits).

Теорема

Якщо $x$ і $y$ - це числа з рухомою комою у форматі з параметрами $\beta$ і $p$, і віднімання виконується із використанням одного вартового числа, тобто з $p+1$ цифрами, тоді помилка заокруглення результату менша ніж $2\varepsilon$.

Відкидання

Тут ми можемо підсумувати, що без використання вартових чисел, відносна помилка утворена через віднімання двох близьких величин може бути дуже великою. Інакше кажучи, обчислення будь-якого виразу, що містить віднімання (або додавання величин з різним знаком) може у висліді дати відносну помилку настільки вилику, що всі цифри беззмістовні. Ми розрізняємо два типи відкидання: катастрофічне і доброякісне.

Катастрофічне відкидання трапляється коли операнди були заокруглені. Наприклад, воно відбуваєтсья у виразі $b^2-4ac$. Покладемо $b = 3.345; a = 1.219; c = 2.294$. Точне значення $b^2-4ac$ рівне $0.003481$. Але $b^2 = 11.189025$ і $4ac = 11.185544$, а з урахуванням заокруглення, $b^2 = 11.19$ і $4ac = 11.19$, і їх різниця це $0$. Тобто, ми отримали помилку в розмірі 35 ulp, див. \eqref{eq:ulp}.

Доброякісне відкидання відбувається коли віднімаюємо дві точно відомі величини. Про це нам каже теорема з попереднього розділу.

Іншим прикладом формули де відбувається катастрофічне відкидання є $x^2 - y^2$, але ми можемо уникнути цього ефекту замінивши її на $(x-y)(x+y)$. Обчислення $(x-y)(x+y)$ і $x^2-y^2$ потребує приблизно однакової кількості дій, тому очевидно якій формі варто віддавати перевагу. Однак, на загал, заміна катастрофічного на доброякісне відкидання не варта зусиль якщо витрати на це занадто великі, бо входові дані часто (хоча й не завжди) є наближеними. Але повне виключення видкидання має сенс навіть якщо дані не точні.

Іншим прикладом заміни катастрофічного на доброякісне відкидання слугує формула обчислення площі трикутника через довжини сторін.

\begin{equation} A = \sqrt{s(s-a)(s-b)(s-c)}, \mbox{де} s=(a+b+c)/2\label{eq:tr_area_catas} \end{equation} Припустимо, що трикутник дуже тонкий; тобто, $a\approx b+c$. Тоді $s\approx a$, а множник $s-a$ віднімає два майже однакових числа, одне з яких містить помилку заокруглення. Але ми можемо переписати формулу \eqref{eq:tr_area_catas} так, що вона повертає акуратні результати навіть для тонких трикутників: \begin{equation} A = \frac{\sqrt{(a+(b+c))(c-(a-b))(c+(a-b))(a+(b-c))}}{4}, a\ge b\ge c \label{eq:tr_area_benign} \end{equation}