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

В настоящее время в вычислительной практике при решении задач ВМ в арифметике с плавающей запятой преимущественно используются одинарная, двойная и четверная точности МЧ, что позволяет решать широкий круг практических задач. Однако существует множество задач, для решения которых четверной точности МЧ недостаточно по причине ошибок округления, и для их решения необходимо использование машинной арифметики с мантиссой числа, большей длины. Классическим примером такой ситуации является задача, решения систем линейных уравнений с плохо обусловленной матрицей. В настоящее время в бесплатном доступе получила, распространение библиотека, программ GNU GMP [4], реализующая стандарт IEEE 754 [1,9], в которой длина, мантиссы в арифметике с плавающей запятой варьируется в широком диапазоне значений. Библиотека GNU GMP позволяет оперировать числами с длиной мантиссы от mmin = 24 вилоть до mmax = 2³¹ = 2 147 483 648 двоичных знаков, чему соответствует 8 и 646 456 993 десятичных знаков. Верхнее значение длины мантиссы МЧ mmax невообразимо огромно. В указанной библиотеке также реализована возможность динамического изменения длины мантиссы m в различных сегментах программы от mmin до mmax. Появление в свободном доступе программного обеспечения с такими возможностями расширяет границы для получения решений широкого круга, задач ВМ с гарантированной точностью высокого порядка.

Проблема, анализа, влияния погрешностей округления (ВПО) на. решение задач ВМ актуальна. со времени появления ЭВМ и остается таковой по сей день. Научные исследования над указанной темой ведутся в разных направлениях. Отметим классические работы по исследованию ВПО при решении задач линейной алгебры [2,3,7,11]; по исследованию ВПО в рамках интервального анализа. [15,16,18]; по статистическому анализу ВПО [12,19]; исследованию новых моделей по выработке машинного числа. [13]; алгоритмов с автоматической коррекцией ошибок округления первого порядка. — метод CENA [14].

В настоящей работе предлагается новая схема, анализа. ВПО на. решение задачи ВМ. Решение задач ВМ представлено как значение некоторой вектор-функции, определяемой методом решения задачи и его машинным алгоритмом. Последний представляется как алгоритм типа. Маркова, алфавитом которого являются базовые (стандартные) математические функции библиотеки программ, на основе которой реализуется указанный алгоритм. Получена оценка решения задачи в зависимости от аргументов функции и длины мантиссы.

Для выделенного класса погрешностей получена оценка длины мантиссы МЧ, гарантирующей достижение требуемой точности решения.

Напомним определение машинного числа с плавающей запятой согласно стандарту IEEE 754 [1]:

Определение 1. Машинным числом будем называть число вида:

жт,р

— ±0.

t е      । 7^S1  , ^s2 ,        , т_т\ ее , ie

818182...8т • Ь — ± (^ + ^ + ... + — ) • Ь — ±Д • Ь , где Ь € {2, 3,...} — основанне, д — мантисса числа, т — количество знаков в мантиссе (число знаков, длина, размер), s^ € {0, 1, ...Ь — 1}, г € [1,т] — значащие цифры, s1 — 0, е € [emin, emax] — порядок числа, р — размер порядка МЧ или количество знаков в представлении числа е. При заданных Ь, т, р машинные числа образуют конечное множество, обозначаемое далее Мъ,т,р. Очевидно, Мь,т,р С Q, где Q — множество рациональных чисел. Для вещественного числа ж € R ближайшее к нему машинное число жтр есть машинное представление этого числа, т.е. число жт,р есть результат округления числа ж. Число 5р — Ь-т назовем погрешностью (точностью) мантиссы или точностью машинных чисел (машинной арифметики). □

Машинное представление действительного числа ж, полученное в результате его округления, имеет следующий вид [2,3]:

Жт,р — Ж (1 + n) + V,

где n • V — 0.

При v — 0, |n| 6 51 и ж_т,_р — 0; при n — 0, ж_тр — 0 и |ж| 6 5о. Относительная погрешность представления числа ж при ж_тр — 0 не более 51 — 2Ь^1-т, абсолютная погрешность |ж — ж_т,_р| 6 5₁ |ж|. Абсолютная погрешность при ж_тр — 0: |ж — ж_т,_р| — |ж| 6 50, 5о — 1 • Ь^е™ ~ Ь^-ЬР~ погрешность нуля, ближайшее к нулю число. На практике выбираются такие величины тир, что можно всегда считать выполненным соотношение 5о << 51, а если учитывать что р — 64 [4], то 5о — 2^-2⁶4 ил и 5о — ю^-5,554018.

Число 51 также называют машинным эпсилоном или погрешностью единицы.

Учитывая, что величина р обычно подбирается так, чтобы перекрывать все необходимые значения порядков числа, точность машинной арифметики зависит прежде всего от длины мантиссы т, поэтому число ж_т,_р можно считать не зависящим от р и представить как: ж_т,_р = ж_т. Введем определения.

Определение 2. Пусть у : Rⁿ ^ R¹ — некоторая функция, ж € Rⁿ — вектор, ж_т — его машинное покомпонентное представление. Тогда: у (ж), у(ж_т) — значения функции у в точках ж и ж_т, у_т(ж_т) — машинное представление значения у (ж_т); у_т (ж) = у_т(ж_т). Значения функций у (ж) и у (ж_т) в общем случае представляются бесконечным числом знаков; в этом случае будем говорить, что их значения получены в точной арифметике. □ Определение 3. Математические функции и операции, реализуемые в библиотеках программ стандарта С99, назовем базовыми или стандартными. К базовым операциям относятся: округление чисел, арифметические операции, логические операции, операции вычисления математических функций, таких как sin ж, cos ж, tan ж, и их обратные, е^ж, аД жД log_tt ж и т.д.                                                                                         □

Одной из библиотек, реализующих базовые функции стандарта С99, является GNU MPFR [4], в которой при заданной длине мантиссы т для значений базовых функций выполняется округление до последней значащей цифры, т.е.

Ут(жт) — У(жт)(1 + n), |n| 6 51, Ут(жт) — 0,                     (2)

где у(ж_т) и у_т (ж_т) — значение одной из стандартных (базовых) функций, вычисленное в точкежт € М_Ь,т,р. Для случая, когда Ут (жт) — 0, |у (жт) — Ут Дт)| — |у Дт)| 6 5q.

Для функций у (ж), не являющихся базовыми, оценка (2), конечно, в общем случае не верна, и одной из целей настоящей работы является получение оценок погрешностей для этих функций. Появление новых вычислительных возможностей, возникающих при варьировании т — длины мантиссы МЧ, позволяет взглянуть на многие известные задачи и методы их решения по-новому.

Во-первых, появляется возможность постановки задачи о достижении заданной точности решения (или вычисления с гарантированной точностью): для заданного е >  0 найти решение задачи ВМ с погрешностью не более е.

Во-вторых, появляется возможность рассмотреть вопрос о «реабилитации» численных методов решения задач ВМ, признанных в вычислительной практике неустойчивыми по причине влияния ошибок округления.

В-третьих, возникает также вопрос о влиянии повышения точности МЧ на эффективность применяемых на практике методов. Например, можно ли, увеличивая длину мантиссы МЧ, уменьшить общее время вычислений? И если да, то в каких случаях?

В настоящей работе дается вариант ответа на первый вопрос.

2.    Задачи ВМ и алгоритмы их решения

Существует несколько классификаций задач вычислительной (прикладной) математики [8]. Общим для них является то, что процесс численного решения задачи ВМ на ЭВМ представляет собой упорядоченную последовательность конечного числа вычислительных базовых операций, которая определяется алгоритмом решения данной задачи. Этот процесс можно представить как вычисление значения некоторой функции (вектор-функции, отображения) f G R^k в точке ж G G С Rⁿ, где G — область определения этой функции. Определение 4. Задачей вычислительной математики будем называть совокупность понятий и условий F(f,ж,m,E), определяющих возможность вычисления значений вектор-функции f : Rⁿ ^ R^k, г де f (ж) — решение данной задачи в точке ж G G; е — точность решения, т — длина мантиссы. Условие достижения точности означает: найти значение вектор-функции f_m(ж) при за данном ж G G такое, что

^т^{(ж) - f(ж)}|| \\f (ж)|

6 е.

□

Возможны и другие определения задачи ВМ, но для целей настоящей работы определения 4 достаточно. Здесь и далее под нормой ф| понимается евклидова норма ||г| = aJ ^2=1 ^2, г G Rⁿ. Очевидно, что к вычислению значений вектор-функции сводятся, например, следующие задачи: решение системы линейных уравнений, вычисление производных функции разных порядков, задача интегрирования функции, задача Коши для дифференциальных уравнений, задачи поиска экстремума функции у(г), г G G С Rⁿ, и т.д.

Для задач ВМ разработаны численные методы их решения, которые в форме, адаптированной к ЭВМ, представляют собой алгоритмы решения этих задач. По своей природе алгоритмы бывают конечношаговыми (КША) и бесконечношаговыми (ВША). К первым, например, относится метод Гаусса решения систем линейных уравнений, ко вторым — метод Ньютона решения систем нелинейных уравнений. Алгоритмы КША и ВША вычисления значений функции f (ж) в точной арифметике представим в следующем виде:

КША:

ALG(f (ж)) = ^(аД V ^ ² ( q 2 ) V ••• V р ^N 1(a_N -1) V p ^N(a_N ),

БША:

ALG(f (ж)) = ^1(01) V ^2(q2) V • • • V pN 1(aN-1) V pN(aN) V • • • N ^ to, где символ V означает объедипение операций, <Д(аД, г G [1, N] — базовые операции, at G Rs — аргумент г-н операшш. Операшш округления в (3) и (4) отсутствуют, а ALG (f (ж))

представляет собой упорядоченную последовательность базовых операций, определенную алгоритмом решения задачи ВМ. Результатом реализации базовой операции (кроме логической) является действительное число. В (3) N — число шагов КША.

Пусть требуется вычислить значение функции f(ж), ж G Rⁿ, f G R^k при длине мантиссы т. Тогда некоторый КША вычисления значения f_m (ж) представляет собой упорядоченную последовательность N базовых операций Qi) г G [1, N], т.е.

ALG(fm(x)) =^m(°i)^v ^m(°2) v • •• v ^m^-i(^QN -1) v ^m (_QN ).            (5)

В отличие от (3), (4) в (5) присутствуют операции округления чисел.

ВША для вычисления значения f_m (ж) имеет вид

^ALG(fmM) = ^Ы ^v ^Ы ^V • • • ^V Vm-^No-l) ^v Vm ^(aNo ),        (6)

где аналогично (5) No — число шагов алгоритма, которое в (6) определяется по некоторому правилу его окончания. Однако при решении конкретной задачи ВМ для вычисления значений f_m(ж) могут существовать различные алгоритмы. Введем следующее определение. Определение 5. Алгоритм вычисления функции f G R^k (5) в точке ж G Rⁿ при длине мантиссы т будет называться нормальным алгоритмом для решения задач вычислительной математики (НАВМ), если вычисленное значение функции в точной арифметике по алгоритму (5), в котором логические операции не выполняются, дает точное значение функции f (ж), т.е. имеет место алгоритм

ALG(f (ж)) = ^1(ai) v ^ ² ( q 2 ) v ••• v v ^{N - 1} ( qn -1) v v ^N ( «n ).              (7)

□ Замечание. Будем считать, что при построении НАВМ использовались логические операции как из математической библиотеки, так и операции языка программирования, на котором реализуется алгоритм решения задачи ВМ. Структура ALG (f_m (ж)) (5), т.е. упорядоченная последовательность выполнения базовых операций, определяется базовыми логическими операциями и для данного т становится фиксированной. При выполнении ALG (f (ж)) базовые логические операции в (7) д' («г) = 0, т.е. не выполняются, а остальные операции в точной арифметике выполняются в соответствии со структурой алгоритма (5). Отметим также, что в (7) операции округления из (5) представляют собой единичный оператор.

Аргументы «г G R^s в (5) — это либо числа (векторы), являющиеся аргументами функции f (ж), либо числа a*, t G [1,s] — результаты выполнения операции Vm(Qj ), j < г, j G [1,N] нa j-й итерации, полученные в процессе вычислений в (5).

Введенное понятие нормального алгоритма терминологически напоминает понятие нормальный алгоритм Маркова (НАМ) [6]. НАМ содержит понятие алфавит, на основании которого строятся дальнейшие выводы грамматики. Алфавит может быть произвольным. В случае НАВМ алфавитом можно считать базовые функции библиотеки программ. На этом основывается аналогия между НАВМ и НАМ. Таким образом, его можно считать сужением НАМ на класс задач вычислительной математики.

• 3.    Погрешности решений задач ВМ

В настоящем разделе изучаются погрешности решений задач ВМ, возникающие в итерационном процессе НАВМ.

Лемма 1. Пусть ^г ~ базовые вычислительные операции (кроме логических) из некоторой библиотеки программ, г G [1, N1] — номер базовой операции. Тогда значение ^m(oi) можно представить в виде

^m(Qi) = ^г(«г) + «г^1,                                      (8)

где W1 — число базовых операций библиотеки, |а^ 6 |у»(а»)|, 51 = 2 Ь^1-т, а» Е R^s, а» = а_т,» — вектор машинных чисел.

Доказательство.

Сначала рассмотрим операции по вычислению значений базовых функций, для которых справедливо равенство (2): ут(а») = у»(а»)(1 + и»), г де |и»| 6 51, 51 = 2 Ь^1-т. Преобразуем его, и получим равенство (8):

У^гт(аг) = у^а»") + у» (а») • и» = у^г(а») + уЧ^а») ^ 51 = у^г(а») + а»51, г де а» = ^ ^(а») ^ ^Е [-1, 1] и ^|а»| 6 |у»^(а»)|.

Для операции округления числа справедливо:

у 4 ( с » ) = у» (а» )(1 + и» ) + в», г де и» в» = 0, |и» | 6 51, |в» | 6 5о, 5о = b^-em^in(p).

В случае, когда в» = 0, имеем у»(а») = а», т.к. у» — единичный оператор, угт (а») = ат4 = а» (1 + и») = а» + а» 51, г де а» = ^ а», ^ Е [-1,1], т.е. справедливо (8). В случае, когда и» = 0, угт (а») = 0 и угт(а») = у» (а») + в» = а» + V», г де |в| 6 5о, 5о = bemin(p). Здесь значение а» из (8) равно а» = ^, г Де |а» | 6 |° — очень малое число. Для одинарной точности ^0 = 2 • 10-29, для двойной   )А = 2 • 10-308 [1]. Таким образом (8) также справедливо и для операции округления.                                           □

Рассмотрим один частный, но важный случай оценивания погрешности операции деления МЧ на разность двух близких машинных чисел.

Лемма 2. Пусть для чисел d, у, z и их приближенных значений 5_т, у_т, z ₄ выполнены условия Ad = dт - d = ^d, Ау = Ут - у = ау, Az = гт - z = 3z; Ут = Цуb¹, гт = Цгb¹, Цу и ци мантиссы чисел у_т и г_т, t — порядок числа; ц_у - ц . = Т)_т-дb^-q, 1 6 q < т, Т)_т-_д — мантисса числа ц_у - ц., где т - q её длина; £ = 151, а = а51, 3 = /351. Тогда погрешность А = ^ - ' = b^q Х51, г де у = -^ (< - Й \ ^ут ^гт ^у .                      4m-q^u \      ^у . )

Доказательство.

Преобразуем значение погрешности А:

_ d + Ad у - z + Ау - Az

¹    /^d - ^{d (а}у^{- 3z)}

ут - Zm         у - z

d     Ad (у - z) - d (Ау - Az)

— ------ — -----:----------:—:------:----- — у - z       (ут - Zm) (у - z)

) =      f( - 5^-^ i 51 = bq _x51.

) Рт - q^b1 у у ^{- z} у

Значение числа у приведено в условии леммы. □

Отметим, что число у может быть большим, если у - z мало по еравпешпо с ау - 3z. Число q характеризует порядок потери точности вычислений. Желательно, чтобы оно было сутцествсшю меньше т. например q 6 4-

Замечание. Вычисления в НАВМ, в которых будут использованы в качестве промежуточных значений величины у ^т.. , будут иметь оценку погрешности, в которой сомножитель b^q может сохраниться, возможны случаи, когда значение q возрастет, уменьшится или станет равным нулю. Следовательно, при анализе погрешности вычислений необходимо каким-то образом учитывать этот эффект потери точности вычислений. На практике данный эффект возникает при численном дифференцировании функций, при решении плохо обусловленных систем линейных уравнений и т.д.

Лемма 3. Пусть функция у : Rⁿ ^ Л ¹ удовлетворяет условию Липшица:

|у (ж + Аж) - у (ж)| 6 L ||Аж^; ж, ж + Аж Е G,

(Ю)

где G С Rn — компакт. Тогда существуют такие числа I» Е  [-L,L], что у(ж + Аж) - у(ж) = ^”=11»Аж».

Доказательство.

Из (10) следует, что для каждой пары точек ж + А ж, ж существует число L1 Е [—L, L] такое, что у (ж + Аж) — у (ж) = L1 ||А ж|.                            (11)

Представим (И) в виде у (ж + Аж) — у (ж) = ^ |Аж|2 = £=1 ^А ж, = £^=1 L^ж, = £=1(А ж,, где а, Е [—1,1], т,е. 1( Е [—L,L],                                                                           □

Рассмотрим свойства погрешностей конечношаговых алгоритмов.

Теорема 1. Пусть функция / (ж) Е R^k, ж Е G С Rⁿ; базовые функции у⁽(аг) (кроме логических) либо являются функциями округления числа, либо непрерывны по Липшицу, т.е. в некоторой окрестности Q, ( q, ) точки а, Е R^syдoвлeтвopяют условию: у⁽ ( q₍ ) — у⁽ (Ь₍ ) 6 L₍ | q₍ — Ь, |, г Е [1,2V ], а алгоритм (5) вы числения функции / (ж) является нормальным для ж Е G. Тогда существует такой вектор С Е R^k. что

/т(ж) — / (ж) = С 51,                                  (12)

где 51 = 2 Ь^1-т, т - длина мантиссы.

Доказательство.

Для доказательства утверждения достаточно показать, что йт,г = Q + Qi51 и угт(ат,г) = уг(«г) + З(51, V г Е [1, V] ,                (13)

кроме логических операций у,, где а, и З( ^— некоторые константы, а, — точное значение аргумента.

Доказательство проводится индукцией по номеру г Е [1, V] вычислительной операции алгоритма (5) (кроме логической). В качестве базы индукции можно взять операцию округления числа Q1 — первого числа, с которого начинаются вычисления. По Лемме 1: а_тд = ут(°₁) = у¹(°₁) + Q₁5₁ = Q₁ + Q₁5₁, | q₁ | 6 | q₁ |. Предположим, что для некоторого г Е [1, V] выполнено (13). Тогда необходимо доказать, что (13) выполнено и для операции с номером г + 1. Компонента ми аргумента а_т(+1 могут быть либо числа, входящие в условие задачи (аргументы функции /(ж)), либо числа «т₍+₁ = уг^ф), 3 Е [1, s], t 6 г. для которых условие (13) выполнено по условию индукции. Если операция г + 1 есть разность двух близких чисел одинакового порядка, то по Лемме 2 справедливо (9). Если операция г + 1 является округлением, то справедливо (8). Теперь надо показать, что (13) выполнено для функции у⁽⁺¹, удовлетворяющей условию Липшица. По Лемме 1 ут+¹(°т,г+1) = у⁽⁺¹(ат,г+1)(1 + «(+1), где |«г+11 6 5_Ь Учитывая, что Qi+1 Е R^s и Лемму 3, получим

S

(ат,г+1) = у(+1(аг+1 + «г+151)(1 + «(+1) = (у(+1(аг+1) +    а(,+1 ^+151)(1 + «(+1) =

2=1

= у(+1(О(+1) +

5Ду(+у,+1) + (1 + «,+1) £ <1Щ

51 = у^1^^) + A+151,

• ¹                             2=1

где |^2+1| 6 L(+1, 1+ Е [—1,1], т.е. для операции г + 1 выполнено (13). Таким образом, равенства (13) выполнены V г Е [1, V]. Так как компоненты вектор-функции /т — это некоторые числа ут, 2t Е [1, V], t Е [1, fc], значения которых по доказанному представимы в виде ут = у⁴ (a_(t) + 3_(t 5₁, то, переобозначая p_(t в с^, получим /т(ж) = /⁴(ж) + с^5₁ и /т(ж) = /(ж) + С51, где С = (С1,С2, ..., с_к ). □

Таким образом, система уравнений (15) для г Е [1,2V] представляет собой систему условий для рекуррентного оценивания погрешностей вычисления значений функции f (ж), ж Е G.

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

Следствие.

• 1)    Вектор С в формуле (12) назовем параметром погрешности (ПП) значения функции. Он является функцией точки ж и размера мантиссы т. Структура его сложна и может включать элементы погрешности вида (9). Тогда погрешность С51 можно представить в виде С 51 = (АД⁹¹, А2№2 ,...,Akb^yk^ 51. Возьмем компоненту вектора At₀, для

  которой |Лг₀ b^qi0 |

  
  

  max lAib^yi |. Обозначим qj₀ = q. Тогда существуют С такие, что

  
  

С51 = (Сх,...,Ск) b- 5 = (СЧ,.., С_к ) (5Д“ = С(5Д“, г де а = 1 - ,, 51 = 2 5^.

Таким образом, теперь формулу погрешности (12) можно представить в виде

Af, (ж) = fm (ж) - f (ж) = С (5Д“ , 0 <а 6 1.                  (15)

Когда, q = 0. то а = 1 и Af_m (ж) = f_m (ж)-f (ж) = С5_Ц. где С = ^С. Опенка погрешности (15) дана, для одной точки. Её обобщением является определение 9.

• 2)    Из Теоремы 1 можно получить следующие выводы.

Во-первых, Ц с Ц < то, т.е. компоненты с^, г Е [1Д], для фиксированного достаточно большого т, ограниченные сверху и снизу числа. Этот вывод следует из того, что каждая компонента а получена по рекуррентной формуле (14) за конечное число шагов.

Во-вторых, значение параметра 6 может быть таким, что ||С|| ^ то при т ^ то. Например, если q = (1 - а) т при фиксированном значении а. т ^ то. Известно [7]. что погрешность значения функции f величина случайная, зависящая от длины мантиссы т. Но так как при увеличении длины мантиссы т модуль погрешности значений базовых функций уменьшается, то и величина колебаний значений параметра ||С||, при определенных условиях, также может уменьшаться и следует ожидать, что его значения будут иметь колебания около некоторой средней его величины. В определении (9) приведено понятие, удовлетворяющее этим условиям.

Рассмотрим теперь свойства бесконечношаговых алгоритмов вычисления f (ж). Для ВША имеет место следующее определение:

Определение 6. Пусть в бесконечношаговом алгоритме выполнено V первых базовых операций и для f (ж) получено приближение значения вычисляемой функции fm(ж). БША вычисления функции f называется нормальным, если для всех V алгоритм вычисления значения fN(ж) будет нормальным.                                                □

Определение 7. Бесконечношаговый алгоритм называется сходящимся, если f (ж) = lim f^N (ж).                                                                            □

N -\

Теорема. 1 может быть уточнена, на. случай сходящегося бесконечношагового алгоритма.

следующим образом:

Теорема 2. Пусть для вычисления значения функции f, (ж) БША является нормальным и выполнены условия Теоремы 1. Тогда существуют векторы С Е Rk, у Е Rk такие, что V Е > 0 : ||у|| 6 Е, имеет место представление fN (ж)=f (ж)+С 51 + у.

Доказательство

Из сходимости бесконечношагового алгоритма следует, что V е >  0 3 V : ||f ^N (ж) - f (ж) | 6 е

II f ^N (ж) - f(ж) = у. |у| 6 Е. Из Теоремы 1 для чанного V имеем равенство f^N (ж) = f^N (ж) +С51. где С Е R^k. Тогда для значения f, (ж) получим

С (ж) = f (ж) - f (ж) + f^N (ж) + С 51 = f (ж) + 651 + у.

Теорема доказана.

4.    О гарантированной точности решений задач ВМ

В этом разделе для случая, когда значение параметра погрешности ||С|| ограничено, получена оценка длины мантиссы МЧ, гарантирующая достижение требуемой точности решения задачи ВМ.

Определение 8. Будем говорить, что метод (алгоритм) вычисления значения функции / G R^k называется корректным (КМ), если для любого е > 0 найдется такой размер мантиссы т. что

△ = II/(х) - /т(х)|| 6 е,или

А

х

6 е,прИ ||/т(х)|| = 0.

Величину е в (17) будем называть требуемой то'тостъю. □

Обратимся к вопросу определения достаточной (гарантированной) точности, которую должно обеспечить ВУ — вычислительное устройство, т.е. ЭВМ, имеющая необходимое программное обеспечение.

Пусть В У имеет переменную длину мантиссы т, т.е. пользователь может выбрать размер мантиссы, необходимый для проведения вычислений. Пусть / : G С Rⁿ ^ R^k, а /_т(х) — значение функции /, вычисленное в точке х_т с помощью данного ВУ.

Определение 9. Будем говорить, что значение функции /_т(х) имеет погрешности порядка а, 0 < а 6 1, относительно погрешности мантиссы 8^, если существуют константы С л Со такие а что V х G G;

А = ||/(х) — /_т(х) | 6 С (8^)“ , для абсолтотисш погрешности;

^{I J/ т ( х ) |} =          6 Со (5д)“п1>11 |/т(х)| = 0, для относительной погрешности,

||/т(х)Н          ||/т(х)|| где 8^ = Ь-т.                                                                           □

Приведем без доказательства простое, но полезное утверждение, в котором гарантируется погрешность значения /_т (х) порядка а.

Лемма 4. Пусть для функции / (х) в некоторой точке х G П С G, где П — компакт, выполнены условия Теоремы 1, а в равенстве (15) а удовлетвориет условию 0 < а 6 1-Тогда значение функции /_т (х) имеет погрешность порядка ао, 0 < ао 6 1, V х G П. □ Докажем теперь теорему о длине мантиссы МЧ, гарантирующей требуемую точность решения задачи ВМ.

Теорема 3. Пусть погрешности А значения функции /_т(х) ил и ^ ^ц имеют порядок а. Тогда для любого е > 0 данный метод вычисления функции будет корректным при т >  [1 — “ log_b (J пли т >  |_1 — “ log_b (J . где L AJ — целая часть числа А.

Доказательство.

Докажем теорему для абсолютной погрешности А. Доказательство для относительной погрешности аналогично.

Зададим число е > 0. Так как для достаточно больших т чис-.то (8^ )“ = Ь^-ат может быть достаточно малым, то выберем т такое, что (8Д“ = Ь^-“^т 6 (• Подставляя в (18) значение ( вместо (8Д“ , получим, что А = ||/(х) — /_т(х) | 6 е, т.е. выполнено (17) и метод вычисления будет корректным при выбранном т. Теперь из неравенства Ь^-“^т 6 ( найдем значение т; —ат 6 log^ (, откуда т >  — “ log_b (. Так как т — целое число, то очевидно: т >  [1 — “ log_b (_|. Значение мантиссы т для относительной погрешности определяется по формуле ^т > ^ ^— “ k>g_b (mJ.                                                    □

Замечание.

• 1.    В важном частном случае, когда а = 1, оценки для т из Теоремы 3 имеют ^т > [1 - kg f J и ^т >   - kg ^10 J .

  вид

  
  
  
  

• 2.    Константы С и Со связаны следующими условиями:

5.    Вывод

А , \f (x) - №)\\ < С (5^ \fm(x)\         \fm(x)\     6 \fm(x)\ где Со = СтСГ или Со = у, т.е. уС^ 6 f = Со, f = min\fmCz)\, г € И, И С G -компакт. В случае, когда fm(x) = 0, относительная погрешность не рассматривается.

Ввиду особой важности Теоремы 3 для прикладных исследований переформулируем её в следующем виде:

Теорема 4. (правило гарантированной точности решений задач ВМ). Пусть погрешность (абсолютная или относительная) вычисленного значения функции f имеет порядок а, 0 < а 6 1. Тогда для любой требуемой точности е >  0 существует такой размер мантиссы т, при котором достигается заданная точность е решения задачи.                    □

На практике Теоремы 3, 4 применимы до максимального значения мантиссы mmax, которую обеспечивает данная библиотека программ. В частности, для библиотеки GNU GMP mmax = 646456993 десятичных знаков.

В работе введено понятие нормального алгоритма решения задач вычислительной математики (НАВМ). Для НАВМ получена оценка погрешности решения задачи ВМ, зависящая от значений её аргументов и длины мантиссы числа. Для задач ВМ, в которых значение параметра погрешности ограничено, получена оценка длины мантиссы, гарантирующая достижение требуемой точности решения. В продолжении настоящей работы будут предложены и обоснованы эмпирические правила оценки точности решений задач ВМ.