Федченко Г.М. Лекции. Численные методы

Подождите немного. Документ загружается.

ТЕОРИЯ ПОГРЕШНОСТЕЙ

a, , характеризующей скорость уменьшения вероятности появления

погрешности с ростом величины этой погрешности.

Кроме того, средняя квадратическая погрешность результата серии n

равноточных независимых измерений вычисляется следующим образом:

S = = . (3.7)

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

арифметического в раз меньше средней квадратической погрешности

отдельного измерения. Величина S является оценкой дисперсии 

распределения случайной величины a;\s\up8(–. Зная оценку дисперсии,

можно вычислить границы доверительного интервала (a;\s\up8(– – ; a;\s\

up8(– + ), в который попадает истинное значение измеряемой величины с

заданной вероятностью. Надежностью результата серии измерений

называется вероятность  того, что истинное значение измеряемой величины

попадает в данный доверительный интервал.

 = t·S , (3.8)

где t – коэффициент, зависящий от вероятности  и числа измерений n.

Таким образом: A = a;\s\up8(–   и относительная погрешность результата

серии измерений  = , или в процентах –  = ·100%.

3.4. Основная и обратная задачи теории погрешностей

Основная задача теории погрешностей заключается в следующем: известны

погрешности некоторой системы величин, требуется определить

погрешность заданной функции от этих величин.

Пусть вычисляется значение функции f(X) = f(x, x, …, x) в некоторой

точке A(A, A, …, A), координаты которой известны лишь приближенно; a и

(i=1, 2, …, n) – приближенные значения и их погрешности для координат

точки A. Требуется определить погрешность вычисления значения функции

| U – u | = | f(A, A, …, A) – f(a, a, …, a) |

Существует несколько подходов для решения основной задачи теории

погрешностей.

1. Метод интервалов.

Так как известны погрешности , ,…,  приближений a, a, …, a для

точных значений аргументов, A, A, …, A лежат соответственно на отрезках , ,

…, . Строгий учет вычислительных погрешностей можно провести в рамках

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

значения функции f, над интервалами.

ТЕОРИЯ ПОГРЕШНОСТЕЙ

2. Метод оценки главной части погрешности.

В случае дифференцируемой функции f, применяя теорему Лагранжа

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

абсолютной величины разности точного и приближенного значений:

| U – u | = | f(A, A, …, A) – f(a, a, …, a) |  , (3.9)

где , D – область возможных значений координат :

D =

Используя малость области D, можно положить , i=1, 2, …, n.

. (3.10)

Таким образом, функция f приближенно заменяется на малой области

n-мерной плоскостью, касающейся поверхности в точке (a, a, …, a).

Отсюда легко получается формула оценки относительной

погрешности приближенного значения u= f(a, a, …, a).

= = =. (3.11)

Если величины a – случайные, например получены с помощью

многократных измерений, подверженных лишь воздействию случайных

погрешностей, и S– соответствующие средние квадратические погрешности

(i=1, 2, …, n), то средняя квадратическая погрешность величины u = f(a, a, …,

a) вычисляется по формуле

S = . (3.12)

3. Технический подход.

Этот подход связан с именем известного русского кораблестроителя,

математика и механика академика А.Н.Крылова и может быть использован

при ручном счете. Он основан на оценках погрешностей арифметических

действий и связи погрешности приближенного числа с количеством верных

значащих цифр.

Принцип А.Н.Крылова: приближенное число должно записываться так, чтобы

в нем все значащие цифры, кроме последней, были верными и лишь

последняя была бы сомнительна, и притом не более чем на одну единицу.

Чтобы результаты арифметических действий, совершаемых над

приближенными числами, записанными в соответствии с принципом

А.Н.Крылова, также соответствовали этому принципу, нужно

придерживаться следующих простых правил:

1. при сложении и вычитании приближенных чисел в результате

следует сохранять столько десятичных знаков, сколько их в

приближенном данном с наименьшим количеством десятичных знаков;

ТЕОРИЯ ПОГРЕШНОСТЕЙ

2. при умножении и делении в результате следует сохранять

столько значащих цифр, сколько их имеет приближенное данное с

наименьшим числом значащих цифр;

3. результаты промежуточных вычислений должны иметь один-

два запасных знака, которые затем должны быть отброшены.

4. Статистический подход.

При больших количествах однотипных вычислений вступают в силу

уже вероятностные или статистические законы формирования погрешностей

результатов действий. Фактически погрешности отдельных данных, как

правило, имеют различные знаки и, следовательно, частично компенсируют

друг друга. Поэтому итоговая погрешность результата получается меньше

ожидаемой теоретической предельной погрешности.

Методами теории вероятностей показано, что математическое

ожидание абсолютной погрешности суммы n слагаемых с одинаковым

уровнем абсолютных погрешностей, при достаточно большом n,

пропорционально . Также математическое ожидание относительной

погрешности произведения n множителей с одинаковым уровнем

относительных погрешностей, при достаточно большом n, пропорционально .

В частности, при n>10 можно применять правило Чеботарева для

оценки абсолютной погрешности суммы npслагаемых с одинаковой

абсолютной погрешностью :

, (3.13)

и относительной погрешности произведения n сомножителей с одинаковой

относительной погрешностью :

. (3.14)

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

погрешность исходных данных для получения результата заданной точности.

В такой постановке задача является неопределенной, поскольку

требуется найти по известному значению множество значений . Поэтому

необходимо наложить дополнительные требования на искомые величины ,

диктуемые конкретной ситуацией.

Рассмотрим один из подходов решения этой задачи в случае

дифференцируемой функции f и оценки главной части абсолютной

погрешности (3.10). Потребуем, чтобы вклад в суммарную погрешность

каждого слагаемого правой части (3.10) был одинаков, то есть

. (3.15)

Это условие часто называют принципом равных влияний.

Тогда:

ТЕОРИЯ ПОГРЕШНОСТЕЙ

откуда

(i=1, 2, …, n). (3.16)

Иногда допускают, что абсолютные погрешности всех аргументов

одинаковы (принцип равных абсолютных погрешностей), тогда

(i=1, 2, …, n). (3.17)

Наконец, естественно предположить, что точность измерения всех

аргументов a одинакова (принцип равных относительных погрешностей),

т.е. относительные погрешности всех аргументов равны: (i=1,2,…,n). Тогда )

и на основании (3.10)

, следовательно .

На основе этого получаем границы абсолютных погрешностей аргументов:

(i=1, 2, …, n). (3.18)

3.5. Контрольные вопросы и упражнения

1. Проиллюстрируйте геометрически метод оценки главной части

погрешности для дифференцируемой функции одной переменной.

2. Как частные случаи формул (3.10), (3.11) получите правила оценивания

абсолютных погрешностей суммы и разности приближенных значений,

относительных погрешностей произведения, частного и степени

приближенных значений.

ПОГРЕШНОСТИ МАШИННОЙ АРИФМЕТИКИ

Лекция 4

ПОГРЕШНОСТИ МАШИННОЙ АРИФМЕТИКИ

Все вычисления на компьютере в силу конечной разрядной сетки

выполняются с конечной точностью, обусловленной используемыми

техническими решениями. Возникающие при этом погрешности называют

вычислительными или машинными.

Существуют ситуации, когда вычислительные погрешности

проявляются существенным образом. Поэтому необходимо знать причины

вычислительных погрешностей, уметь их распознавать и знать способы их

устранения. Вообще говоря, необходимо представлять, какими

возможностями располагают компьютеры в плане решения вычислительных

задач, уметь их грамотно использовать и знать границы этих возможностей.

4.1. Форматы записи чисел в памяти компьютера

Существует два основных формата представления чисел в памяти

компьютера:

 с фиксированной точкой (запятой),

 с плавающей точкой (запятой).

В типах данных, использующих представление чисел с

фиксированной запятой, все разряды, кроме знакового, служат для

изображения разрядов чисел. Причем каждому разряду в памяти всегда

соответствует всегда один и тот же разряд числа, что и фиксирует место

запятой. Такой формат упрощает выполнение арифметических действий, но

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

таком типе.

Целые числовые типы представлены в формате с фиксированной

запятой. Положение запятой зафиксировано после самого правого разряда.

Диапазон представляемых чисел определяется отрицательным и

положительным числами с наибольшими цифрами во всех разрядах.

Абсолютная точность представления числа с фиксированной запятой

зависит от способа округления: отсечением или дополнением.

Абсолютная точность представления чисел с фиксированной запятой

одинакова в любой части диапазона. В то же время относительная точность

значительно отличается в зависимости от того, берется число близким к 0

или к границе диапазона.

Замечание: Числа с фиксированной запятой имеют равномерную абсолютную

плотность распределения на всем отрезке числовой оси, определяемом

ПОГРЕШНОСТИ МАШИННОЙ АРИФМЕТИКИ

границами диапазона; и неравномерную, возрастающую к границам отрезка,

относительную плотность распределения.

В основе значительно чаще употребляемого представления

вещественных чисел в формате с плавающей запятой лежит нормализованная

форма записи.

Определение 4.1. Нормализованная запись отличного от нуля вещественного

числа – это запись вида a=m·p, где m – дробь с нулевой целой частью, у

которой первая цифра после запятой отлична от нуля, т.е.  m < 1.

Ноль нельзя представить в нормализованном виде, поэтому

принимается соглашение 0p(m=0, n=0) – нормализованная запись нуля.

Таким образом, при хранении вещественного числа в ячейке памяти

необходимо выделить разряды под знаки и значения мантиссы и порядка.

Часто применяются форматы, в которых не хранится знак порядка. Для этого

порядок всегда записывают положительным числом и от истинного значения

его отличает некоторое смещение.

Например, если под порядок отведено 7 разрядов, то в них

помещаются двоичные числа в диапазоне от 0000000 до 1111111, или

десятичные – от 0 до 127, всего 128 значений. Разумно эти 128 значений

разделить поровну между положительными и отрицательными значениями

порядка. В таком случае между машинным порядком и истинным

устанавливается следующее соответствие:

Порядок числа

–64 –63 –62 –63 … 0 1 … 61 62 63

Порядок со смещением

0 1 2 3 64 65 125 126 127

p= p + 64.

В разных типах компьютеров применяются различные форматы

представления чисел в форме с плавающей запятой. Они отличаются

способами записи порядка, а также количеством и расположением разрядов,

отводимых под мантиссу и порядок. Основание степени p может быть равно

2, 4, 8, 16.

4.2. Стандарт IEEE-754

До 80-х годов каждый производитель имел свой собственный формат

чисел с плавающей точкой. Все они отличались друг от друга. Более того, в

некоторых из них арифметические действия выполнялись неправильно,

поскольку арифметика с плавающей точкой в ограниченном числе разрядов

ПОГРЕШНОСТИ МАШИННОЙ АРИФМЕТИКИ

имеет некоторые тонкости и отличается от обычной арифметики

вещественных чисел.

Чтобы изменить ситуацию, в конце 70-х годов Институт инженеров по

электротехнике и электронике (The Institute of Electrical and Electronics

Engineers, IEEE), осуществляющий техническую поддержку Международной

организации по стандартизации (International Organization for Standardization,

ISO), учредил комиссию для стандартизации арифметики с плавающей

точкой. Целью было не только дать возможность переносить данные с одного

компьютера на другой, но и обеспечить разработчиков аппаратного

обеспечения заведомо правильной моделью. В результате получился

стандарт IEEE-754 Floating Point Standard.

Стандарт был принят в 1985г. Автором стандарта является профессор

математики Калифорнийского университета (г.Беркли) Вильям Кахан

(William Kahan). IEEE-754 определяет:

 стандарт хранения вещественных чисел различной точности,

 стандарт выполнения арифметических действий,

 как должно выполняться округление,

 что следует делать в исключительных ситуациях: переполнение порядка,

исчезновение порядка, извлечение корня из отрицательного числа.

Этот документ позволил производителям вычислительной техники

наладить выпуск эффективных и надежных чипов, реализующих арифметику

с плавающей запятой. В настоящее время большинство процессоров

содержат команды с плавающей точкой, которые соответствуют этому

стандарту.

Стандарт определяет три формата вещественных чисел: с одинарной

точностью – 32 бита (single), с удвоенной точностью – 64 бита (double) и с

повышенной точностью – 80 битов (extended). Порядок и мантисса

записываются в двоичной системе счисления и основание возведения в

степень равно 2. Общий вид форматов представлен на рисунке:

Все форматы начинаются со знакового бита; 0 указывает на

положительное число, а 1 – на отрицательное. Затем следует смещенный

порядок. Для формата одинарной точности смещение равно 127, для

удвоенной точности – 1023, для повышенной – 16383. Минимальное (0) и

максимальное (255, 20047, 32767) значения смещенного порядка не

используются для нормализованных чисел. У них есть специальное

предназначение, о котором будет сказано ниже. в конце идут мантиссы по 23,

52 и 64 бита соответственно.

Нормализованная мантисса в двоичной системе счисления всегда

знак порядок со смещением мантисса

ПОГРЕШНОСТИ МАШИННОЙ АРИФМЕТИКИ

начинается с бита, заполненного 1. Следуя практике, начатой с компьютера

PDP-11, первый бит не сохраняют, поскольку можно просто предполагать,

что он есть. Следовательно двоичная мантисса состоит из скрытого бита, за

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

ячейке памяти. Стандарт IEEE-754 определяет дробную часть вещественного

числа следующим образом: она состоит из неявного бита, равного 1, неявной

двоичной запятой, за которыми идут 23, 52 или 64 бита. Если все явные биты

заполнены 0, то это число имеет значение 1.0. Если же все явные биты равны

1, то это числовое значение несколько меньше, чем 2.0. Во избежания

путаница для обозначения комбинации из неявного бита, неявной двоичной

запятой и последующих явных битов вместо термина «мантисса» (mantissa)

используется термин significand. Все нормализованные числа имеют

significand s в диапазоне 1s<2.

Самое маленькое нормализованное число одинарной точности

содержит 1 в смещенном порядке, 0 – в мантиссе и представляет значение

1.0·2=2=10=1010. Самое большое нормализованное число одинарной

точности содержит 254 в смещенном порядке, единицы – в мантиссе и

представляет значение, чуть меньшее 2.0·2=2=10=1010.

Одна из проблем представления вещественных чисел в конечном

числе разрядов – потеря значимости, которая возникает при получении

результата арифметических действий, модуль которого меньше самого

маленького нормализованного числа. Раньше аппаратное обеспечение

действовало одним из двух способов: либо устанавливало результат на 0,

либо вызывало ошибку из-за потери значимости. В стандарт IEEE введены

ненормализованные числа. Эти числа имеют смещенный порядок 0 и

ненулевую мантиссу. Неявный бит слева от двоичной точки превращается в

0. Ненормализованные числа легко отличить от нормализованных, поскольку

у последних не может быть записан в порядке 0. Самое большое

ненормализованное число содержит 0 в порядке, в мантиссе единицы,

скрытый бит равен 0. Таким образом представлено значение несколько

меньшее 2, т.е. в два раза меньшее, чем самое маленькое нормализованное

число.

По мере уменьшения результата при дальнейших вычислениях

смещенный порядок остается равным 0, а первые несколько битов мантиссы

превращаются в нули, что сокращает и значение, и число значимых битов

мантиссы. Самое маленькое ненормализованное число содержит в мантиссе

в крайнем правом бите 1, а все остальные биты равны 0. Так в типе

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

2·2=2=2=10=10. Такая схема предусматривает постепенное

исчезновение значимых разрядов, а не перескакивает на 0, когда результат

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

ПОГРЕШНОСТИ МАШИННОЙ АРИФМЕТИКИ

Числовые характеристики стандарта IEEE-754 для чисел с плавающей

точкой приведены в таблице.

Параметр

Одинарная

точность

Удвоенная

точность

Повышенная

точность

Количество битов в знаке

1 1 1

Количество битов в порядке

8 11 15

Количество битов в мантиссе

23 52 64

Общее количество битов

32 64 80

Смещение порядка

127 1023 16383

Область значений порядка

от –126

до +127

от –1022

до +1023

от –16382

до +16383

Самое маленькое нормализованное

число

2 2 2

Самое большое нормализованное

число

2 2 2

Диапазон десятичных дробей

– – –

Самое маленькое

ненормализованное число

  

Также в этой схеме присутствуют 2 нуля, положительный и

отрицательный, определяемые по знаковому биту. Оба имеют порядок 0 и

мантиссу 0. Скрытый бит также равен 0.

С переполнением нельзя справиться постепенно. Вместо этого

существует специальное представление бесконечности: с порядком,

содержащим все единицы, и мантиссой, равной 0. Это число можно

использовать в качестве операнда. Оно подчиняется обычным правилам для

бесконечности. Например, бесконечность и любое число в сумме дают

бесконечность. Конечное число разделит на бесконечность равно 0.

А что получится, если бесконечность разделить на бесконечность? Результат

не определен. Для этого случая существует другой специальный формат,

NaN (Not a Number – не число). Его тоже можно использовать в качестве

операнда.

Нормализованное число



0 < n < max Любой набор битов

Ненормализованное число



0 Любой ненулевой набор битов

Ноль



0 0

Бесконечность



11…1 0

Не число



11…1 Любой ненулевой набор битов

Пример 4.1. Пусть значение переменной a типа single представлено в

ПОГРЕШНОСТИ МАШИННОЙ АРИФМЕТИКИ

шестнадцатеричной системе счисления: a=42BE8000. Найдем десятичное

значение вещественного числа a. В двоичном виде представление значения

числа a имеет вид:

0100 0010 1011 1110 0100 0000 0000 0000

p = 10000101–127 = 2+2+2–127 = 128+4+1–127 = 6

s = 1.01111101

|a| = s·2 = 1.01111101·2 = 1011111.01 = 2+2+2+2+2+2+2 = 32+16+8+4+2+1+ =

63.25

Знаковый бит содержит 0, следовательно, число a – положительное. Итак,

a=63.25.

Пример 4.2. Найдем представление в типе single десятичного числа a = –6.5.

Найдем представление |a| в двоичной системе счисления: 6.5 = 2+2+ = 110.1.

Нормализуем это представление: |a| = 1.101·2.

s = 1.101, p=2, p= 2 + 127 = 129 = 10000001.

1100 0000 1101 0000 0000 0000 0000 0000

Или в шестнадцатеричной системе счисления внутреннее представление

числа a в типе single имеет вид: C0D00000.

4.3. Основные числовые характеристики системы вещественных

чисел конечной разрядности

Пределы изменения порядка n ограничивают абсолютную величину

используемых вещественных чисел:

В качестве характеристик этого диапазона используют константы , : – это

минимально представимое число в данном вещественном типе, называемое

машинным нулем; – это максимально представимое число в данном

вещественном типе (машинная бесконечность):

Для системы вещественных чисел с плавающей точкой одинарной

точности =,  –1.

Количество разрядов, отводимых под мантиссу, ограничивает

знаковый

бит

порядок со

смещением

мантисса со

скрытым битом

скрытый

бит

знаковый

бит

порядок со

смещением

мантисса со

скрытым битом