Распечатать запись Распечатать запись

Ошибки, о которых мало кто задумывается

Относительная погрешность метода Эйлера в зависимости от числа шагов

Казалось бы, компьютер считает довольно точно и вычислить на нем можно все, что угодно. И это верно, однако компьютер — всего лишь инструмент, и как всякий инструмент, он допускает некоторые погрешности вычислений.

Теперь очень поучительный пример. В 1991 году ракета “Patriot”, запущенная в Саудовской Аравии, не смогла сбить иракский снаряд “Scud” из-за проблемы точности. “Scud” попал в армейскую казарму, и погибло 28 американцев.

Самое важное, наверное, то, что компьютеры имеют дело, вообще говоря, с конечным числом цифр и символов. В силу этого мы не можем выполнять арифметические действия в классе вещественных чисел так, как привыкли в чистой математике. Арифметические операции, выполняемые ЭВМ аппаратно, ограничены конечным числом разрядов, в то время как численное представление большинства вещественных чисел требует бесконечного числа разрядов. Например, численное представление таких фундаментальных констант, как \pi и e, требует бесконечного числа цифр и никогда не может быть введено в ЭВМ абсолютно точно. Более того, даже если наши исходные данные допускают точное представление в ЭВМ, в результате выполнения арифметических операций мы в конце концов допустим некоторые погрешности. Например, для численного представления частного от деления двух четырехзначных чисел может потребоваться бесконечное число цифр. И даже произведение двух четырехзначных чисел в общем случае требует для представления восьми цифр, так что после нескольких умножений число разрядов, необходимое для точного запоминания результата, быстро выйдет за разумные пределы. Если, например, предположить, что на ЭВМ реализована четырехразрядная десятичная арифметика, то результат операции 0{.}8132\cdot0{.}6135=0{.}49889820 будет, в зависимости от компьютера, представлен либо как 0{.}4988, либо как 0{.}4989. Мы не в состоянии выполнять арифметические действия на ЭВМ абсолютно точно. В результате выполнения очень большого числа операций полученная ошибка может достаточно сильно сказаться на результате вычислений.

Чтобы более точно описать то, о чем сказано выше, давайте вспомним, что такое бит и байт. Компьютер имеет дело только с двумя состояниями: ток есть (один) и тока нет (ноль). Каждый символ — один и ноль — занимает 1 бит информации. Бит по-английски — bit (=binary digit) — двоичная цифра. Один байт содержит 8 битов.

Каждая вычислительная машина характеризуется длиной слова, т.е. количеством двоичных разрядов, составляющих каждое слово памяти. Эта длина слова и определяет число цифр, с которыми в машине выполняются обычные арифметические действия, называемые арифметикой с одинарной точностью. В большинстве используемых для научных расчетов ЭВМ это число эквивалентно от 6 (Intel x86: 4 байта) до 16 (Intel x86: 8 байт) десятичным знакам. Возможна также реализация арифметики более высокой точности. На многих машинах арифметика с двойной точностью, в которой, по существу удваивается число цифр, реализуется аппаратно. В этом случае выполнение программ, использующих арифметику с двойной точностью, если и увеличивает время счета по сравнению с вариантами одинарной точности, то весьма умеренно, и только в редких случаях время счета увеличивается вдвое. Большинство современных крупных ЭВМ с короткими длинами слов имеют очень эффективную арифметику двойной точности или “чуть более” (Intel x86 — 18, 10 байт). В то же время на некоторых машинах арифметика двойной точности реализована с помощью программного обеспечения и в несколько раз увеличивает время счета по сравнению с вариантами одинарной точности. Арифметика более высокой точности, чем аппаратная, реализуется только с помощью программного обеспечения и с увеличением порядка точности становится все более неэффективной. В практических задачах арифметика высокой точности используется редко.

Большинство вычислений на компьютере производится в арифметике с плавающей точкой. Число a в форме с плавающей точкой представляется в виде a=Mr^p, где r — основание системы счисления, p — порядок числа a, M — мантисса числа a, причем должно выполняться условие нормировки r^{-1}\le|M|<1. Все персональные компьютеры и большинство рабочих станций поддерживают IEEE-стандарт двоичной арифметики (этот стандарт принят Institute of Electrical and Electronic Engineers). Стандарт предусматривает два типа чисел с плавающей точкой: числа обычной точности (представляются 32 битами — 4 байтами, мантисса занимает 23+1 бита, порядок — 8 битов, знак — 1 бит, наибольшее представимое нормализованное число 3.40282\cdot10^{38}, наименьшее по модулю 1.17549435\cdot10^{-38}) и числа двойной точности (представляются 64 битами — 8 байтами, мантисса занимает 52+1 бит, порядок — 11 битов, знак — 1 бит, наименьшее представимое нормализованное число 1.79769313486232\cdot10^{-308}, наибольшее по модулю 2.2250738585072014\cdot10^{308}). Здесь +1 бит в мантиссе обозначает один бит (первый значащий бит), который всегда в нормализованной мантиссе равен 1, и он не сохраняется (за исключением субнормальных чисел, для которых этот бит равен 0).

Пример. Запишем представление числа 0.375 в форме с плавающей точкой (одинарная точность). Сначала переведем это число в двоичную систему счисления:

\overline{0.375}_{10}=3/8=1/2+1/2^2=\overline{0.11}_{2}=\overline{1.1}_{2} \cdot2^{-1}.

Таким образом, сохраняется мантисса 10000000000000000000000 и порядок -1.

Знак “плюс” представляется 0 в знаковом бите, “минус” — 1.

А теперь объяснение того, что произошло в Саудовской Аравии. Компьютер, который контролировал полет ракеты “Patriot”, был создан на основе разработок 1970-х годов и использовал 24-битную арифметику. В отслеживающих вычислениях время записывалось системными часами в секундах, однако оно преобразовывалось в 24-битное число с плавающей точкой. Ошибки округления во времени стали причиной ошибки в слежении за ракетой. После 100 часов выполняемых операций вычисленное время в секундах было 359999{.}6567 вместо точного значения 360000, ошибка в 0{.}3433 секунды повлекла ошибку в 687 метров в расстоянии. Позднее было установлено обновленное оборудование.

Литература:

Bj\ddot{{\rm o}}rk A., Dahlquist G., Numerical mathematics and scientific computations, SIAM, Philadelphia, 2008. V. 1

Higham N.J., Accuracy and stability of numerical algorithms, SIAM, Philadelphia, 1996

Комментариев: 4

  1. 1 Pavel Holoborodko:

    Для полноты картины я бы еще посоветовал известную статью What Every Computer Scientist Should Know About Floating-Point Arithmetic by David Goldberg и Why and how to use arbitrary precision by Paul Zimmermann.
    А также другие книги и статьи этого же автора, особенно Modern Computer Arithmetic – черновик где-то бродит по сети.

    P.S.
    Мне нравится ваш сайт и его содержание.
    Как автор, я бы посоветовал вам обновить плагин WP-QuickLaTeX до последней версии (ему нужен Wordpress => 2.7) – там добавлен функционал для математических сайтов (e.g. подключение пакетов LaTeX) и многое другое.

    [Ответить]

  2. 2 Елизавета Александровна Калинина:

    Спасибо, Павел, за ссылки! Modern Computer Arithmetic нашла здесь.

    Плагин обновила. За него Вам отдельное спасибо, вещь очень нужная и полезная!

    [Ответить]

  3. 3 Pavel Holoborodko:

    После обновления у вас перестали показываться формулы.
    Я кажется понял в чем проблема. Вы используете теги <tex> для вставки inline формул и !$$…$$ для выносных.

    Новый QuickLaTeX позволяет вставлять формулы двумя способами:
    1. как раньше – используя теги ![latex]…[/latex]. От тегов <tex> пришлось отказаться во избежание коллизий с множеством других плагинов которые используют этот же тег для отображения исходных кодов.

    2. можно использовать родную нотацию LaTeX прямо в тексте поста. Т.е. текстовую формулу можно вставить посредством !$…$, выносную !\[...\] или !$$…$$. Также поддерживаются окружения для нумерованных формул (с авто-нумерацией и ссылками на формулы в стиле LaTeX), графика tikz и т.д. Фактически это делает совместимыми offline документы LaTeX и страницы на сайте – достаточно текст из статьи скопировать и вставить на сайт и наоборот. Нет необходимости в дополнительных тегах. Но, для совместимости, в этом режиме также будут продолжать работать и теги ![latex]…[/latex].

    По умолчанию, включен первый режим. Второй – можно включить для конкретной страницы на сайте поместив на ней команду ![latexpage] или глобально для всех страниц на сайте: администраторская панель плагина ->Advanced->Use LaTeX Syntax Sitewide->ON.

    Возможно наиболее простым решением проблемы является – заменить <tex> … </tex> на ![latex]…[/latex] на существующих страницах (это должно быть просто через глобальную замену). Плюс включить поддержку родной нотации LaTeX на всем сайте. Таким образом, все существующие страницы будут отображаться адекватно, и вы сможете использовать родную нотацию LaTeX в новых постах.

    Я очень сожалею о причиненных неудобствах с <tex>….

    [Ответить]

  4. 4 Елизавета Александровна Калинина:

    Павел, спасибо, буду разбираться. Пока не знаю, как поменять все глобально, поэтому поставила обратно старую версию плагина.

    [Ответить]

Оставьте свой отзыв

Добавить изображение