Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.abitu.ru/en2002/closed/viewwork.html?work=200 Дата изменения: Fri May 5 15:25:14 2006 Дата индексирования: Tue Oct 2 02:34:40 2012 Кодировка: koi8-r Поисковые слова: с р с р с р с с р р с с

Статистические методы оценки погрешности округления при сложении


Виноградова Екатерина Вячеславовна

Н.Новгород, шк.?2, кл.11
Современные информационные технологии, научные и инженерные исследования
требуют обработки больших объемов числовой информации. При этом возникают
вопросы об искажении и ошибках в исходной информации, о погрешностях при
вычислениях, о передаче и хранении числовой информации. Используемые, ранее
традиционные методы оценки погрешностей вычислений практически неприменимы
к современным объемным вычислительным процедурам, т.к. приводят к
завышенным оценкам [1]. Один из подходов к решению этой проблемы связан с
использование интервальных методов оценки погрешностей. Надо заметить, что
эти методы достаточно трудоемки и также приводят к завышенным оценкам [2].
При выполнении объемных вычислений, происходит обработка большого числа
погрешностей, которые могут принимать самые различные значения. Это
позволяет поставить вопрос о применения статистических методов анализа
накопления погрешности вычислений [3,4].
В данной работе показано, возможность статистической оценки погрешности
округления при сложении нескольких чисел, погрешности которых равномерно
распределены.
Погрешность округления суммы двух положительных
однозначных чисел.

Погрешность округления определяется последними цифрами числа, которые
получаются, как правило, либо при проведении экспериментальных
исследований, либо в процессе округления предыдущих операций. Следуя теории
младшего разряда [3], можно предположить, что эти цифры имеют равномерное
распределение.

При выполнении операции сложения с плавающей точкой на компьютере, на
первом этапе выравниваются порядки чисел, а затем складываются мантиссы.
Заметим, что число значащих цифр мантиссы задано и не изменяется в процессе
сложения. Операция округления проводится до количества значащих цифр. Для
упрощения исследования будем рассматривать суммы чисел содержащих мантиссу
из одной цифры.
При этом, анализ погрешности суммы двух чисел, может быть сведен к
анализу сложения двух однозначных чисел образующих погрешность. Будем
полагать, что данные цифры имеют равномерное распределение.

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


[pic][pic],

где [pic] - генерация 0, [pic] - генерация 1,. [pic] -[pic] генерация 9.
События [pic], [pic] - это появление соответственно чисел ( и ( из
множества [pic]. Заметим, что события [pic] и [pic] равновероятны.
Вероятность события [pic] [pic]. Число исходов, благоприятствующих событию
[pic], [pic], а полное число равновозможных исходов множества [pic] равно
N=10. Поэтому, [pic].
Событие С - это появление суммы двух однозначных чисел [pic]. Событие С
будет происходить тогда, когда одновременно происходят оба события [pic] и
[pic], т.е. [pic]. Очевидно, что события [pic] и [pic] независимые.
Применяя теорему о вероятности двух совместных независимых событий
получаем, что вероятность события С
[pic]
Необходимо определить вероятности события С для различных значений суммы
[pic]. Например, [pic] можно получить при [pic]. [pic], [pic] - событие,
при котором [pic], а B0 - событие, при котором [pic]. Следовательно,
вероятность события C запишется в виде:
[pic]
[pic]
[pic]: [pic]
[pic]
[pic]: [pic]
[pic]
[pic]
. . . . . . . . . . . . [pic]
[pic][pic]
[pic]: [pic]
[pic][pic]
[pic]: [pic]
[pic][pic]
Следовательно, [pic], где [pic].
Так как [pic]то вероятность события С в зависимости от значений суммы
[pic] будет вычисляться по следующим формулам:
[pic]
[pic]

Вероятности события С для каждого из возможных значений [pic] приведены в
табл.1., а соответствующее распределение на рис.1.
Таблица 1.



|((( | P(((() | ((( | P(((() |
|0 | 1/100 |10 |9/100 |
|1 |2/100 |11 |8/100 |
|2 |3/100 |12 |7/100 |
|3 |4/100 |13 |6/100 |
|4 |5/100 |14 |5/100 |
|5 |6/100 |15 |4/100 |
|6 |7/100 |16 |3/100 |
|7 |8/100 |17 |2/100 |
|8 |9/100 |18 |1/100 |
|9 |10/100 | | |



[pic]

Рис.1

Запишем вероятность получения суммы двух чисел меньше некоторого числа
[pic]:[pic]

Если сумма чисел [pic], тогда с вероятностью [pic] погрешность округления
суммы [pic]:

[pic][pic].


Если [pic], то с вероятностью [pic]погрешность округления суммы [pic],
т.е. [pic]


Возможные значения погрешности округления [pic] и соответствующих им
вероятности [pic] приведены в табл. 2.


Таблица 2.

| ( | Р(() | ( | Р(() |
| -4 |5/100 | 2 | 1/100 |
|-3 |6/100 |3 |2/100 |
|-2 |7/100 |4 |3/100 |
|-1 |8/100 |5 |4/100 |
|0 |64/100 | | |


График зависимости вероятности погрешности округления [pic] от [pic]
приведён на рис.2.
[pic]
Рис. 2.
Приведем график показывающий вероятность появления некоторой суммы после
округления. Округление осуществляется до одной цифры.

[pic]
Рис.3
Аналогичным образом можно рассмотреть сумму двух двухзначных чисел каждая
цифра которых равномерно распределена и двух n-значных чисел. Однако для
практики вычислений интересны многократные сложения чисел.
Вероятность округления суммы трёх положительных
однозначных чисел.
Определим вероятность округления суммы трёх положительных однозначных
чисел [pic]. Сложение трёх чисел [pic] можно осуществлять двумя способами:
1) Сложить три числа [pic] и произвести округление полученной при этом
суммы.

2) Сложить два первых числа [pic] и произвести процедуру округления,
после чего прибавить третье число [pic] и произвести вторичное округление.
Заметим, что при втором сложении могут складываться числа разного порядка.


Рассмотрим первый способ сложения трёх положительных однозначных
чисел[pic].

Событие С((( - это появление суммы трёх однозначных чисел [pic]. С(((
будет происходить тогда, когда одновременно происходят три события K(, B( и
D(: [pic]. Очевидно, что события K(, B( и D( независимые. Вероятность С(((
будет равна:
[pic]
[pic] - событие, при котором сумма двух однозначных чисел [pic].
Вероятности события [pic] для различных значений ( будут равны вероятностям
события С для различных значений суммы однозначных чисел [pic].
Следовательно, для определения вероятности события [pic] для различных
значений можно воспользоваться табл. 1.
Определим вероятности события С((( для различных значений суммы [pic].
Вероятность события D( для различных значений ( будет одинаковой и равной
1/10 ([pic]).
Например, [pic] можно получить при [pic] и [pic][pic] Значит,
вероятность события [pic]: [pic]
[pic]:
[pic]
[pic]
[pic]

[pic]:[pic]
[pic]
[pic]
. . . .
[pic]:[pic] [pic]
[pic]
[pic]:[pic][pic]
[pic]

. . . . . . . . . . . .

[pic]:[pic][pic]
[pic]

[pic]:[pic][pic]
[pic]
. . . . . . . . . . . . .
[pic]:[pic][pic]
[pic]

[pic]:
[pic]
[pic]
[pic].
Приведем общие формулы для определения вероятности суммы трех чисел
[pic] (9)
[pic].(10)
[pic]. (11)
В таблице 3 приведены вероятности различных значений суммы [pic].
Таблица 3.

| ((((( |P((((( (%)|((((( |P((((( (%)|
| 0 |0,1 |14 |7,5 |
|1 |0,3 |15 |7,3 |
|2 |0,6 |16 |6,9 |
|3 |1 |17 |6,3 |
|4 |1,5 |18 |5,5 |
|5 |2,1 |19 |4,5 |
|6 |2,8 |20 |3,6 |
|7 |3,6 |21 |2,8 |
|8 |4,5 |22 |2,1 |
|9 |5,5 |23 |1,5 |
|10 |6,3 |24 |1 |
|11 |6,9 |25 |0,6 |
|12 |7,3 |26 |0,3 |
|13 |7,5 |27 |0,1 |


График соответствующего распределения приведен на рисунке 4а.

[pic][pic]
а.
б
рис.4
На рисунке 4б. показана вероятность округления суммы трех чисел.
По данным из таблицы 3 определим вероятности для каждого из возможных
значений погрешности округления суммы [pic]. Если сумма[pic] или [pic], то
погрешность округления [pic] Если, например, [pic], то погрешность
округления будет равна [pic]. Определим таким образом вероятность каждого
из возможных значений погрешности округления [pic].
В таблице 4 приведены возможные значения погрешности округления [pic] и
соответствующие им вероятности Р(().
Таблица 4
| ( | Р(() (%) | ( | Р(() (%) |
| -5 | 0,6 | 1 | 4,5 |
|-4 |8,5 |2 |5,5 |
|-3 |9 |3 |6,4 |
|-2 |9,4 |4 |7,2 |
|-1 |9,7 |5 |7,3 |
|0 |31,9 | | |

График соответствующей вероятности приведен на рисунке 5.
[pic]
Рис.5

Рассмотрим второй способ сложения трёх положительных однозначных
чисел[pic].

Если [pic], то вероятности каждого из значений суммы [pic] будут равны
вероятностям, полученным при первом способе сложения чисел [pic].
Вероятности сумм будут равны, т.к. при [pic] сумма данных чисел округляться
не будет и тогда этот способ сложения будет равносилен первому способу
сложения (Как и в первом способе сложения, будет производиться единичное
округление). Значит, для определения вероятности суммы трёх складываемых
чисел при [pic], можно воспользоваться данными табл. 1.
Например, если [pic], то в этом случае событие [pic] равно:
[pic] где [pic].
Сумма [pic] будет округлена до 10 и поэтому при прибавлении к этой сумме
[pic]сумма [pic].
Вероятность события [pic] будет равна:
[pic]
[pic][pic]: [pic][pic]
[pic]
Если [pic], причём, если [pic] то ( будет изменятся от [pic] до 14, т.е.
[pic]. Для [pic] ([pic]) можно в общем виде записать формулу для вычисления
вероятности события :
[pic]
[pic]:
[pic],
где [pic].
Сумма [pic] будет округлена до 20 и поэтому при прибавлении к этой
сумме (=0 сумма [pic].

Вероятность события [pic] будет равна:
[pic]
[pic]

[pic]:
[pic],
[pic]
[pic]

Для [pic] ([pic]) можно в общем виде записать формулу для вычисления
вероятности события
[pic], [pic].


В табл. 5 приведены возможные значения суммы трёх положительных целых
чисел [pic] и соответствующие им вероятности [pic]. График [pic] приведен
рис. 6 а график после второго округления на рис.6 б.


Таблица 5.

|((((( |P((((( (%)|((((( |P((((( (%)|
| 0 |0,1 |16 |6,2 |
|1 |0,3 |17 |5,4 |
|2 |0,6 |18 |4,5 |
|3 |1 |19 |3,5 |
|4 |1,5 |20 |1 |
|5 |2,1 |21 |1 |
|6 |2,8 |22 |1 |
|7 |3,6 |23 |1 |
|8 |4,5 |24 |1 |
|9 |5,5 |25 |1 |
|10 |8,9 |26 |1 |
|11 |8,7 |27 |1 |
|12 |8,4 |28 |1 |
|13 |8 |29 |1 |
|14 |7,5 | | |
|15 |6,9 | | |


[pic][pic]
а
б

Рис.6


Вероятность погрешности сложения нескольких чисел

По данным табл. 5 определим вероятности каждого из возможных значений
погрешности округления суммы [pic]. Если сумма[pic] или [pic], то
погрешность округления ( =0.Если, например, [pic], то погрешность
округления соответственно будет равна [pic].
Значения каждой из возможных погрешностей округления [pic] и
соответствующие им вероятности [pic] приведены в табл. 6.
Таблица 6.
|( |Р(() (%) |( |Р(() (%) |
|-5 |1 |1 |4,5 |
|-4 |8,5 |2 |5,5 |
|-3 |9 |3 |6,4 |
|-2 |9,4 |4 |7,2 |
|-1 |9,7 |5 |6,9 |
|0 |31,9 | | |

Если теперь рассмотреть сумму четырех, пяти и т.д. слагаемых и
последовательно после каждого суммирования производить округления, то можно
получить следующие рекуррентные формулы для вероятностей
[pic],
[pic],
[pic].
На рисунке 7 приведено распределение значений суммы шести однозначных
чисел без округления.
[pic]
Рис.7
Можно видеть, что полученное распределение близко к нормальному.
Действительно, если сравнить его с нормальным распределением построенным по
среднему значению [pic] и дисперсии [pic], то для среднеквадратичного
отклонения этих графиков получим (=0,62(10-3.
На рисунке 8 приведено распределение значений суммы шести чисел при
последовательном округлении после каждого сложения.
[pic]
Рис.8
Можно видеть, что наиболее вероятное значения суммы значительно меньше
предельного значения. В таблице 7 приведены вероятности погрешностей при
сложении с последовательным округлением
Таблица 7.
| |((10 |((20 |((30 |((40 |((50 |((60 |
|[pic] |90% | | | | | |
|[pic] |63% |96% | | | | |
|[pic] |38,2% |82% |97,5% | | | |
|[pic] |21% |64,7% |89,9% |99% | | |
|[pic] |11% |47,2% |77,3% |95,3% |99,5% | |


Из таблица 7 следует, что погрешность округления суммы шести чисел будет
((40 с вероятностью 95,3%, такие значения доверительной вероятности приняты
при инженерных измерениях, а погрешность получаемая простым суммированием
дает значение ((60 с вероятностью [pic].
Заключение.

В работе проведён статистический анализ округления суммы чисел. При
анализе были рассмотрены суммы двух и трех и т.д. положительных однозначных
чисел. Полученны значения вероятностей погрешностей округления сумм и
соответствующие функция распределения. Все вычисления были проведены с
помощью пакета Maple.
Проведённые исследования указывают на принципиальную возможность
получения статистических оценок погрешности вычислений.
Литература

1. Ляхов А. Ф. Элементарная теория погрешностей. - Математическое
образование, ? 3-4, 1998г., с.84-104.
2. Ляхов А. Ф. Определение погрешностей вычислений и решение задач с
параметрами методами интервальной математики. - Математическое
образование, ? 4, 2000, с.56-75.
3. Хемминг Р. В. Численные методы. - М. Наука, 1968, с.400.
4. Дональд Э. Кнут «Искусство программирования». т.2 «Получисленные
алгоритмы». Москва, изд. дом «Вильямс», 2000г., с. 832.
5.
Научный руководитель доцент кафедры теоретической механики механико-
математического факультета ННГУ им. Н.И. Лобачевского Ляхов Александр
Федорович