Ентропійна динаміка похибок округлення в арифметиці чисел з плаваючою точкою: теорія, моделі та алгоритмічні наслідки

Abstract

Анотація Похибки округлення в арифметиці чисел з плаваючою точкою є одним із найбільш прихованих і водночас найнебезпечніших джерел відмов обчислювальних систем. Попри десятиліття досліджень у чисельному аналізі, відсутній загальний кількісний критерій, що дозволяв би апріорно порівнювати числову стійкість різних алгоритмів незалежно від конкретних вхідних даних. Метою статті є побудова такого критерію на основі апарату теорії інформації Шеннона та доведення системи теорем, що описують ентропійну динаміку похибок у числових обчисленнях. Для досягнення мети введено два центральні поняття: ентропія округлення – диференціальна ентропія розподілу похибок квантування, та обчислювальний ентропійний потенціал алгоритму – міра надлишкової невизначеності, яку алгоритмічна реалізація породжує понад неминучий інформаційний шум вхідних даних. Доведено чотири взаємопов’язані теореми. Перша встановлює, що ентропія сумарної похибки монотонно зростає при накопиченні послідовних арифметичних операцій і асимптотично зростає як половина двійкового логарифма числа операцій. Друга дає точний кількісний вираз для ефекту катастрофічного скасування: при відніманні двох близьких чисел ентропія відносної похибки зростає рівно на кількість втрачених значущих двійкових розрядів. Третя доводить, що компенсоване підсумовування Кахана є ентропійно оптимальним алгоритмом із нульовим обчислювальним ентропійним потенціалом, тоді як наївне підсумовування має потенціал, що зростає як половина двійкового логарифма числа доданків. Четверта – теорема-бар’єр – встановлює: обчислювальний ентропійний потенціал будь-якого детермінованого алгоритму не може бути від’ємним, а нульового значення досягає тоді й тільки тоді, коли алгоритм є зворотно стійким у розумінні Вілкінсона. Для ітераційних методів побудовано марковську модель накопичення похибок, з якої виведено нижню межу точності; для методу Ньютона – Рафсона вона еквівалентна квадратичній збіжності. Виявлено зв’язок між обчислювальним ентропійним потенціалом і принципом Ландауера в термодинаміці інформації, а також між похибками округлення в обчисленнях зниженої точності та механізмами диференційної приватності. Теоретичні результати верифіковано числово на задачах підсумовування та обчислення дискримінанту; відхилення від теоретичних прогнозів не перевищує 0,02 відсотка. Отримані результати можуть бути використані для апріорного аудиту числової стійкості алгоритмів, інтеграції у компілятори та обґрунтування методів змішаної точності з гарантіями конфіденційності. Abstract Rounding errors in floating-point arithmetic represent one of the most insidious and consequential sources of failure in computational systems. Despite decades of research in numerical analysis, no general quantitative criterion exists for comparing the numerical stability of algorithms prior to execution, independently of specific input data. The aim of this paper is to construct such a criterion using Shannon information theory and to prove a system of theorems describing the entropy dynamics of errors in numerical computations. Two central concepts are introduced: rounding entropy, defined as the differential entropy of the quantization error distribution, and the computational entropy potential of an algorithm, which measures the excess uncertainty that an algorithmic implementation generates beyond the inevitable information noise of the input data. Four interconnected theorems are proved. The first establishes that the entropy of the cumulative rounding error grows monotonically as arithmetic operations accumulate, and increases asymptotically as one-half the binary logarithm of the number of operations. The second provides an exact quantitative expression for catastrophic cancellation: when two nearly equal numbers are subtracted, the entropy of the relative error increases by precisely the number of significant binary digits lost. The third proves that Kahan compensated summation is an entropy-optimal algorithm with zero computational entropy potential, whereas naive summation has a potential that grows as one-half the binary logarithm of the number of summands. The fourth, the barrier theorem, establishes that the computational entropy potential of any deterministic algorithm cannot be negative, and reaches zero if and only if the algorithm is backward stable in the sense of Wilkinson. For iterative methods, a Markov chain model of error accumulation is constructed, from which the accuracy lower bound is derived; for the Newton–Raphson method, this bound is equivalent to quadratic convergence. A connection is identified between the computational entropy potential and Landauer's irreversibility principle in information thermodynamics, as well as between rounding errors in reduced-precision computations and differential privacy mechanisms. The theoretical results are numerically verified on summation and discriminant computation problems; deviations from theoretical predictions do not exceed 0.02 percent. These results can be applied to a priori auditing of algorithm numerical stability, integration into compilers as stability warnings, and justification of mixed-precision methods with formal privacy guarantees.