virtual void function() = 0;. class CAbstractProblem. чисто виртуальная функция. class CRealProblem: public CAbstractProblem. входные данные задачи. конструктор. деструктор. функции доступа к переменным класса. class CAbstractResult. чисто виртуальная фун

Числа, получаемые при решении на ЭВМ прикладных вычислительных задач, как правило, являются приближенными. Следовательно, вопрос о точности результатов приобретает особое значение. Напомним, что под абсолютной погрешностью понимается величина D(a*) = | a-a* |, где a – точное (вообще говоря, неизвестное) значение величины, a* - известное приближенное значение той же величины. Относительная погрешность приближенного значения a* (при a¹0) – это d(a*) = D(a*) / | a |. Так как непосредственное вычисление величин D(a*) и d(a*), как правило, невозможно, то реально часто пользуются границами погрешности вида | a-a* | £ (a*), D(a*) / | a | £ (a*). Очевидно, для одного и того же приближенного числа могут быть указаны различные границы точности (т.е. (a*) и (a*) не являются однозначно определенными величинами).

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

Например: 0.0109 (3 значащих цифры) или 0.0109000 (6 значащих цифр). Значащую цифру называют верной, если абсолютная погрешность числа не превосходит единицы разряда, соответствующего этой цифре. Например, для числа a*=0.0109000 при (a*) = 2×10^-6, первые 4 значащие цифры будут верными. Верная цифра приближенного числа, вообще говоря, не обязана совпадать с соответствующей цифрой в записи точного числа. Например, пусть a=1.00000, a*=0.99999. Тогда (a*) = 0.000001, но у числа a* все значащие цифры – верные.

Утверждение 1. Если число a* содержит N верных значащих цифр, то справедливо неравенство

d(a*) £ (10^N-1-1) ^-1.

Утверждение 2. Для того, чтобы число a* содержало N верных значащих цифр, достаточно чтобы выполнялось

d(a*) £ (10^N+1) ^-1.

Таким образом, если число a* содержит ровно N верных значащих цифр, то его относительная погрешность d(a*) будет порядка 10^-N. Иначе говоря, информативность значащих цифр связана именно с относительной погрешностью приближенного числа. Аналогично, если бы мы пользовались двоичными числами из N верных значащих цифр, относительная погрешность была бы порядка 2^-N.

Погрешности простейших операций над приближенными числами.Оценим неустранимую абсолютную погрешность суммы.

Утверждение 3. D(a*±b*) £ D(a*) + D(b*), причем эта оценка достижима.

Таким образом, естественно положить (a*±b*) = (a*) + (b*).

Оценим теперь неустранимую относительную погрешность суммы.

Утверждение 4. Пусть a и b – ненулевые числа одного знака. Тогда

d(a*+b*)£ max{d(a*), d(b*)},

d(a*- b*)£ max{d(a*), d(b*)} × |a+b| / |a-b|,

причем обе оценки достижимы.

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

(a*+b*) = max{ (a*), (b*)},

(a*- b*) = max{ (a*), (b*)} × |a+b| / |a-b|.

Первое из этих неравенств означает, что при суммировании чисел одного знака не происходит потери точности (в смысле относительной погрешности). Как следует из второго неравенства, при вычитании чисел одного знака или сложении чисел разных знаков, граница относительной ошибки возрастает в |a+b| / |a-b| > 1 раз, и возможна существенная потеря точности, особенно если числа a и b близки.

Пример. Пусть решается вычислительная задача, где окончательный результат находится по формуле y = 1-x с помощью найденного ранее x. Пусть найденное приближение x*=0.999997 содержит 6 верных значащих цифр. Тогда y* = 0.000003 и число верных цифр на последней операции упало до 1. Если еще учесть, что по утв. 1 и утв. 2 d(x*) имеет порядок 10^-6, а d(y*) имеет порядок 10^-1, то необходимо будет признать, что произошла катастрофическая потеря точности.

Виновником "катастрофы" здесь является не последняя операция вычитания, а предложенный метод решения, где окончательный результат получается вычитанием двух близких чисел. В действительности полезная информация о значении y уже оказалась потерянной до вычитания. Если нет другого варианта расчета, то для получения приемлемого результата следовало бы предварительно вычислить x с существенно большим числом верных знаков, учитывая, что на последнем этапе 5 старших значащих цифр будут потеряны.

Утверждение 5. Для относительных погрешностей произведения и частного приближенных чисел имеем:

d(a* b*) £ d(a*) + d(b*) + d(a*) d(b*),

d(a* / b*) £ [d(a*) + d(b*)] / [1- d(b*)],

причем во втором случае предполагается, что d(b*) < 1. Обе оценки достижимы.

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

Итак, выполнение арифметических операций над приближенными числами (даже если вычисления выполняются абсолютно точно), как правило, сопровождается потерей точности. Единственная арифметическая операция, при которой потери не происходит – сложение чисел одного знака. Наибольшая потеря точности может происходить при вычитании близких чисел одного знака.

Особенности машинной арифметики. В основе причин появления вычислительной погрешности на ЭВМ лежит сам способ представления вещественных чисел. В большинстве современных ЭВМ принята форма представления вещественных чисел с плавающей запятой:

x = ±(g₀+g₂×2^-1+…+g_t×2^-t)2 ^p,

где g₀,g₁,…,g_t – двоичные цифры из {0,1}. Для нормализованного (наиболее точного) способа хранения x нормализуется так, чтобы g₀=1. При этом в памяти ЭВМ достаточно хранить только значащие цифры, начиная с g₁. Число m = g₀+g₁×2^-1+…+g_t×2^-t называется мантиссой, а p - двоичным порядком (или характеристикой числа).

Итак, на ЭВМ представимы не все вещественные числа, а только конечный набор рациональных чисел специального вида. Для всех остальных чисел возможно лишь их приближенное представление с относительной ошибкой e_M, которую принято называть ошибкой представления (или ошибкой округления), и в случае нормализованного представления она равна единице первого отброшенного разряда, т.е. e_M = (x*)=2^-t-1.

Числа одинарной точности (типа float) записываются в 4 байта, куда входят знаковый бит, 8-битовый двоичный порядок, смещенный на константу, равную 127, и 23-битовая мантисса (в действительности она 24-разрядная, но первый разряд всегда равен 1 и не хранится).

В нормализованном режиме хранения 8-битовый смещенный двоичный порядок принимает значения от 1 до 254 (значения 0 и 255 зарезервированы – об этом поговорим позднее) и обеспечивает диапазон представимых значений от 2^-126»1.18×10^-38 примерно до 2×2¹²⁷»3.40×10³⁸. 23-битовая мантисса обеспечивает до 24 верных двоичных знаков, что дает ошибку представления e_M=2^-t-1 =2^-24 » 5.96×10^-8, т.е. обеспечивает 7-8 значащих десятичных цифр.

Если в процессе вычислений возникают числа по модулю меньше 2^-126, происходит автоматическое переключение на более грубую форму хранения чисел в денормализованном виде. Для индикации денормализованного представления и зарезервировано значение 0. В таком случае удается записать еще более малые по абсолютной величине значения. Отличие этого представления состоит в том, что вместо g₀=1 предполагается g₀=0, а значение порядка фиксировано равным -126. В результате минимальное по модулю число в денормализованном режиме типа float представляет собой 4 нулевых байта и кодирует в точности нуль. Следующее за ним число равно 2^-24×2^-126»1.43×10^-45, и так далее. Не трудно заметить, что в случае денормализованного хранения относительная ошибка представления может достигать ½ (достаточно рассмотреть число x=½×2^-24×2^-126 и его представление x*=2^-24×2^-126).

Заметим, что из-за необходимости округления результата машинные арифметические операции умножения Ä и сложения Å обладают иными свойствами, нежели обычные математические операции. Например, не выполняется правило (a+b)+c = a+(b+c). Рассмотрим пример: a=(1.)₂, b=c=(0.000001)₂, и предположим, что мантисса имеет всего t=6 двоичных разрядов. Тогда a+b = (1.000001)₂, и с учетом округления получаем aÅb = (1.00001)₂. Далее, (aÅb)+с=(1.000011)₂, и после округления получим (aÅb)Åс=(1.00010)₂. Сложение вторым способом дает bÅc=(0.000010)₂, aÅ(bÅс) = (1.00001)₂, таким образом, (aÅb)Åс ¹ aÅ(bÅс). Можно привести примеры, когда неверными оказываются и утверждения (xÅy=x Û y=0) или (xÅy=0 Þ x= -y).