Метод учета инструментальной и методической погрешности вычисления некоторых трансцендентных функций тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

Санкт-Петербургский Государственный У н и вер с иге т

На правах рукописи ВИНОГРАДОВ Евгений Владимирович

Метод учета инструментальной и методической

погрешности вычисления некоторых трансцендентных функций

01.01.07 - Вычислительная математика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Санкт-Петербург 2006

Работа выполнена на кафедре математической теории микропроцессорных систем управления факультета прикладной математики - процессов управления Сапкт-Петербургского государственного университета.

Научный руководитель: доктор технических наук, профессор, Заслуженный деятель науки и техники РФ Меньшиков Григорий Григорьевич

Официальные оппоненты:

Ведущая организация:

доктор физико-математических наук, профессор Демьянович Юрий Калим ирович кандидат физико-математических наук, доцент Куприянова Людмила Викторовна

Институт Вычислительных Технологий СО РАН, Новосибирск

Защита состоится "21 "2006 г. вч.^ мин. на заседании дпссертациопного совета К-212.232.07 по защитам диссертаций на соискание ученой степени кандидата физико-математических наук при Санкт-Петербургском государственном университете по адресу: 199034, Санкт-Петербург, Средний проспект ВО, д. 41/43 ¿суд • $ О

С диссертацией можно ознакомиться в научной библиотеке им. А. М. Горького Сапкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., 7/9.

Автореферат разослан 9 " Ао ¿> — 2006 г.

Ученый секретарь диссертационного совета, доктор фю.-мат. наук, профессор

^¿Н

Горьковой В.Ф.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

В таком случае традиционные методы вычислений предусматривают ответ на вопрос "чему приблизительно равно?". Однако точность полученного результата в большинстве случаев определить методами традиционных вычислений весьма проблематично в связи с тем, что количество погрешностей возрастает вместе с количеством вычислительных операций.

В 1985 году Институтом IEEE был принят стандарт на вычисления с плавающей точкой IEEE Standard Std 764-1985. В этом документе указаны требования, предъявляемые к округлению чисел, выполняемому в операциях сложения, умножения, вычитания, деления и извлечения корня, что позволило сделать компьютерные вычисления более корректными и доказательными. Однако указанный стандарт никак не регламентирует вычисление элементарных функций (таких как синус, косинус, логарифм, и т.д.). Более того, по той же причине в некоторых случаях такие функции могут вычисляться некорректно.

Одним из способов получения гарантированного результата служат так называемые «интервально-локализующие» вычисления. Термины -«интервал», «интервальный» впервые появились в работе Теруо Сунаги «Theory of Interval Algebra and its Application to Numerical Analysis» в 58-м году, двумя годами раньше была опубликована работа Мечислава Вармуса «Calculus

of approximations». В этих работах была предложена классическая интервальная арифметика и намечены ее приложения. Кроме того, Т.Сунага заложил основы интервального алгебраического формализма и дал весьма нетривиальные примеры применений новой техники, к примеру, в численном решении задачи Коши для обыкновенных дифференциальных уравнений

В 1962-м году в одном из первых выпусков «Сибирского математического журнала» появилась Леонида Витальевича Канторовича «О некоторых новых подходах к вычислительным методам и обработке наблюдений», обозначившего эту тематику как приоритетную для нашей вычислительной науки.

Дальнейшее развитие интервальные методы получили в СССР в работах академика Николая Николаевича Яненко и его ученика Юрия Ивановича Шокина, а также ряда других авторов. Множество работ на эту тему опуликовано и в иностранной литературе.

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

Например, А. Зив в 1991 году опубликовал статью "Fast evaluation of elementary mathematical functions with correctly rounded last bit". Методы, примененные им, были основаны на вычислении значения функции не на всей области определения, а лишь на некотором сравнительно узком базовом промежутке. При этом для вычисления требовалось использование так называемой "двойной "арифметики (т.е. величин, составленных из двух чисел типа double).

В дальнейшем эти методы получили свое развитие в работах многих западных ученых, например, К. Лотера, Д. Дефо, Б. Дитера, и др.

В диссертации изучается задача оценки точности вычисления и получения интервала, гарантированно содержащего точный результат, функций, представимых (хотя бы кусочно) положительными хотя бы на некотором интервале полиномами или рядами с неотрицательными коэффициентами в условиях реальных вычислительных систем без введения дополнительных типов данных (положительность полинома или ряда, а также неотрицательность коэффициентов требуется для получения оцен-

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

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

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

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

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

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

Основное внимание в работе уделяется следующим направлениям исследований:

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

• Получение аналитического представления полной погрешности вычисления.

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

• Разработка вычислительных алгоритмов.

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

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

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

Апробация работы. Результаты диссертации докладывались автором на XXXV Конференции "Процессы управления и устойчивость" (Санкт-Петербург, Петергоф, 14-16 апреля 2004 г.), XXXVI Конференции "Процессы управления и устойчивость"

(Санкт-Петербург, Петергоф, 11-14 апреля 2005 г.), XXXVII Конференции "Процессы управления и устойчивость"(Санкт-Петербург, Петергоф, 10-13 апреля 2006 г.), Всероссийском (с международным участием) совещании по интервальному анализу и его приложениям Интервал-Об (Санкт-Петербург, Петергоф, 1-4 июля 2006 г.). , а также на семинарах кафедры математической теории микропроцессорных систем управления СПбГУ.

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

Структура работы. Диссертационная работа состоит из введения, трех глав, заключения, списка литературы, включающего 87 наименований, и двух приложений. Объем работы составляет 149 страниц машинописного текста.

СОДЕРЖАНИЕ РАБОТЫ

Во введении рассматривается краткая история вопроса, актуальность темы, приводится сжатое описание исследования.

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

Предполагается, что машинная арифметика удовлетворяет следующим гипотезам:

Гипотеза 1. Не равные нулю машинные числа имеют вид:

где

а - знак числа,

ft - основание внутренней системы счисления,

s - порядок числа, целое,

т - мантисса числа.

Для мантиссы принимается условие нормировки 1 < m < fi.

Гипотеза 2. Пусть у - точный результат арифметической операции, у - полученный на ЭВМ аналог, Rm - множество машинных чисел. Тогда

у б Ям =

Гипотеза 3. Пусть f(x) - некоторая функция, f(x) - интервальное ее расширение. Тогда

-Яша, < /Н < f(x") < Ятю f{x') < f(x"),

где Нтпах - наибольшее машинное число.

Гипотеза 4, Операции сравнения всегда работают надежно.

Далее в работе рассматривается вопрос реализуемости этих Гипотез, а также доказывется, что они не противоречат стандарту 1ЕЕЕ-754 на вычисления с плавающей точкой.

Из Гипотезы 1 выводится следующее соотношение, определяющее вариацию рассчитанного на компьютере результата р от точного для одной арифметической операции (здесь и далее знаком «тильда» отмечаются потенциально неточные машинные операции):

Р = вр, в € © = тгрЪР = V*. (1)

При этом вводится константа качества машинной арифметики Л, определяемая максимальной величиной округления реальной вычислительной системы.

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

Дх) е [(1 - аЩх) + г{ж), (1 + а)!р{х) + = (2)

где а - относительная погрешность (или ее мажоранта), а г (ж), г(з) - соответственно нижняя и верхняя оценки остатка.

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

Для увеличения точности расчетов предполагается, что вычисление проводится не на всей области определения функции, в некотором базовом промежутке аргумента X3 = [0, доопределение. Отображение X —* Р(Х) типа отрезок-отрезок называется интервальным расширением функции /(X), если для некоторого условленного класса отрезков X выполняется включение

а л*).

Определение. Интервальное расширение называется монотонным по включению, если для всех вилок X' и Xна которых определено Г(Х) выполняется

X' с X" Р(Х') с F(X").

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

Х\ = X

22 = ¥>2(^1)

Зз = фя(х1,х2) (3)

Для последовательности (3) получена следующая

Теорема 1.1.2. Отображение <р(х) монотонно по включению, если правые части рабочих формул

• сохраняют тот же характер монотонности по всем вхождениям аргумента х{= Х\)

• не убывают по промежуточным переменным XI, ...хп.

Далее рассматривается полином с неотрицательными коэффициентами

(р(х) = а0 + 01Я + ... + а„а:". (4)

Вначале предполагается, что они точно заданы машинными числами. Для этого случая получена и доказана

Теорема 1.2.1. При вычислении по схеме Хорнера относительная погрешность вычисления полинома (4) оценивается с оотнош ением

ф(х) - <р{х) <р{х)

где обозначено

, ч 2то +1 „ 2п -1 „_,

Ф) = (1 — ¡3)2пй + {1~0)^ап~1 + - +

Доказательство строится по следующей схеме.

Для полинома строится алгоритм вычисления по схеме Гор-нера с учетом погрешности каждой операции:

^ 0 Ф) - (1 -тФ)У

(здесь знак тильда отмечает потенциально неточную операцию).

Далее арифметическая погрешность выражается через 0 в соответствии с (1). Тогда для фиксированного х > 0 будет справедливо следующее (наименьшее и наибольшее значения у? по параметрам в):

апХп , а,,-!®""1 а0 ^ , ...

■ + - + Т~Г7* < 4>(х) < (б)

(1 + 0)2п+1 (1 + £)2п-1 - 1+0

ОпЯ" Оп-^""1 , ар

Отсюда выводится оценка погрешности

^ да < да) - да < /-, (в)

(1 — 0) Г У"/

где обозначено

, , 2п +1 „ 2п — 1 ,

= (1 - + (9)

Отсюда оценка относительной погрешности

да)-<да! „ 0 да

(10)

да 1~(1-^|даг

Далее доказывается следующая Лемма 1.2.1. При неотрицательных коэффициентах полинома <р функция

да

возрастает.

Она позволяет избавиться от х и найти максимум правой части (10).

В разделе «Различные случаи задания коэффициентов вычисляемого полинома» приводятся модификации вышеуказанной схсмы рассуждений для различных вариантов задания коэффициентов, в том числе доказывается следующая теорема:

Теорема 1.2.2. В случае, когда коэффициенты а* при вычислении полинома (4) задаются приближенно, оценка относительной погрешности вычисления принимает форму

¡да)-<р(х)\ а

—в

ф(х) 1-&0

л , А да) \ \2 + (1-0)*

и

где обозначено

б-З^1-«*.

а <р*(х) - результат вычисления полинома с использованием приближенных значений коэффициентов.

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

Рассматривается неубывающая неотрицательная функция f(x). Пусть для нее строится степенной ряд для х > 0 на основе разложения

f(x) = К аьз*, ак > 0. (11)

fc=i

Пусть

п

Ь=1

для некоторого п (а„+1 > 0). Тогда методической погрешностью будет остаток ряда

+ОС

= /(я) - tp(x) = akxk.

k=n+l

Предполагается, что ряд сходится в БП = [0, и подчинен при этом признаку Даламбера:

sup 2S±l££_y»<1.

fc>n+l ftfc

Вводится также

7о= inf

fc>n+l Ofc

Далее выводится выражение .для нижней оценки:

Гп+1 S г„+1 = -зг.

1 - 70—

Аналогично для верхней оценки, т.к. ofc+i/ojt < "у0/х$, при к > п + 1

._ an+iXn+i

rn+l i i"n+l — -ЭГ*

1

Xs

На основании этих соображений формулируется и доказывается

Теорема 1.3.1. В случае, когда ряд (11) сходится в некотором промежутке = [0, х&\ и выполняется признак Да-ламбера, справедливы следующие границы для учета методической погрешности вычисления ряда при расчете суммы первых п членов ряда:

/(*) е 1Л(а:),Д(аг)], М*) = ф) +

1-7." (12)

71 = Уа/хб, 72 = 7°/Х$1

т.е.

71 = 1п£л>п+1 ак+11ак ..

7Й — зир(.>п+1 ам/ак,

Выражение (12) является оценкой методической погрешности вычисления ряда.

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

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

Х-2

1 + ат + ^- + ..., (ас>0)

1 (14) -¡-12-. (*<0)

Базовым промежутком предлагается взять х = [0,1], а погрешность входа и выхода из него учитывать интервальными методами.

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

гм+1 ^

«М-ЗГП5Г- 'М-згля"" (15)

В соответствии с результатами Главы 1, выводится формула

е =

для расчета погрешности вычисления экспоненты:

- <Р(Х) < 0

ф) - (1-^Их)!'

(16)

где

<т{х) = 2(

п.+ 2 -П + 1 п"

+... +1)

(1 - (3)2»+^ (п + 1)! + (1 - /З)2" п!

В разделе 2.2 приводится анализ натурального логарифма. В качестве основы алгоритмики используется аппроксимация

Так как благодаря представлению числа с плавающей точкой отделить мантиссу т от порядка р можно точно (Гипотеза 1), а также условию нормировки мантиссы (в соответствии со Стандартом на вычисления с плавающей точкой), предлагается назначить базовым промежутком ш е [1, у/р\. Тогда при т б [1, у/р\ считать логарифм надо будет по формуле

а при ш е [д/Д, (¿] будет использоваться логарифмирование обратной величины

В качестве 1п /г может быть использовано табличное значение. Так как х > 0, далее вводится промежуточная переменная

Тогда расчет границ логарифма от промежуточного аргумента предлагается проводить по формуле:

1пг = р1п|4 + 1пш,

(17)

1п а; = (р + 1) — 1п т', т.' —

ш

и(ж) = --

4 ' Я + 1

(18)

1пх е \1р1{х),<р2{х)\>

где обозначено

^(х) = 2

и

2к-1

и

2п+1

2к-X 2п + 11 _

и2

щ/

(19)

Далее анализируется погрешность вычисления промежуточного аргумента и ее влияние на общую погрешность, В итоге выводится следующее неравенство для границ логарифма:

(1 -

+ а„хп01п+3 + ... < ¡р{х) <

5 (1-7х9+)в. +апХ

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

В разделе 2.3 рассматривается представление функции арктангенса рядом (формула А 641.3 из книги Градштейн И.С., Рыжик И.М. Таблицы интегралов, сумм, рядов и произведений)

, __ х ^ (2&)| , х3 „

8* ~ ¿Й (2к + 1)Ч + '

(20)

Члены правой части одинаково монотонны для всех вхождений аргумента х, выражение (20) переписывается в виде:

где обозначено

«С*») =

О

(21) (22)

и

■■ «(ж) —

(23)

1+х2'

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

=

(20),

х € [0,1]

т . 1

- - аг<^-, х > 1

А X

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

Таким образом, в качестве базового помежутка выбирается [0,1]. .

Для границ у(и) справедливо неравенство:

Ч{Щ = X, аки + -¡"3

1—п -I

71+1

к=0 - ^ 1»« Далее оценивается арифметическая погрешность аргумента степенного ряда. Для нее выводятся следующие соотношения

ДО+/?)(!+ 7гА^)>

и (1-Й2

ИЛИ

\и — и\

--- < т(3,

и 2 (24) т-(1 + ^(1 + ^-^5)

После этого выводится оценка относительной погрешности вычисления арктангенса следующего вида:

<7? (и) + -

<р(и) 0<и<иа <р(и)

где

аЦи) =

= (2(п+1)(т/3'+1)е2+ +[7«(2п + 1) + 2(тД' + 1)]г/ +7и(2п + 3) - 2(п + 2)(т(3' + 1))!*

1

(25)

(о-

/9)2п+3(1 + т0')(1 - (1 + т(3')(3 + тр' - 7и)2У2

Последний раздел Главы 2 посвящен сравнению полученных в этой работе методов с предложенными ранее в работах различных авторов (Н. Böhm, J. Garloff, J. Rokne, и др.), а также реализованных в популярных математических программных библиотеках {INTLAB, GAOL, filib++, boost). В нем обосновывается вывод о том, что для специализированных сред существуют алгоритмы, которые позволяют в некоторых случаях получить более точные результаты, чем средства, предложенные в данной работе, ценой высокой сложности портирования этих библиотек на другие вычислительные системы, отсутствием гибкости относительно используемых программных средств, введением ряда ограничений (например, табличные методы), а также использованием типов данных с увеличенной точностью. Однако результаты данной работы представляют собой универсальный механизм, имеющий возможность гибко подстраиваться под новые вычислительные машины, который может использоваться в комбинации с другими методами и библиотеками, а также позволяет оценивать погрешность проведения вычислений до получения гарантированного результата.

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

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

ЗАКЛЮЧЕНИЕ

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

• Сформулирована и доказана Теорема 1.2.1 об оценке относительной погрешности вычисления полинома. Получена формула для расчета относительной погрешности вычисления, разработаны способы применения теоремы к различным случаям задания исходного полинома, в том числе сформулирована и доказана Теорема 1.2.2 о случае приближенного задания коэффициентов вычисляемого полинома.

• Сформулирована и доказана Теорема 1.3.3 об оценке методической погрешности вычисления ряда

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

• Предложены применимые на практике методы расчета с гарантированной точностью экспоненциальной функции, натурального логарифма и арктангенса.

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

По теме диссертации опубликованы следующие работы:

1. Виноградов Б.В., Меньшиков Г.Г, Дистрибутивность операций П и V в курсе "Локализующие вычисления"// Процессы управления и устойчивость. Труды XXXVII Межвузовской научной конференции аспирантов и студентов 14-16 апреля 2004 года. / Под редакцией Н.В.Смирнова, А.В.Платонова. СПб: Издательство СПбГУ, 200В. с. 300-305.

2. Виноградов Е.В. Методика учета инструментальной и методической погрешности вычисления положительного полинома // Процессы управления и устойчивость. Труды XXXVII Межвузовской научной конференции аспирантов и студентов 10-13 апреля 2006 года. / Под редакцией Н.В.Смирнова, А.В.Платонова. СПб: Издательство СПбГУ, 2006. с. 300-305.

3. Виноградов Е.В. Погрешность вычисления ряда, оцениваемого геометрической прогрессией, на примере натурального логарифма // Всероссийское {с международным участием) совещание по интервальному анализу и его приложениям Интервалов, 1-4 июля 2006 года, Петергоф, Россия, Расширенные тезисы докладов. - СПб.: НИИ Химии СПбГУ, 2006 г. с. 26-29

4. Виноградов Е.В. Стандарт IEEE Std 754-1985 и версия постулируемых свойств машинной арифметики для обеспечения интервально-локализующих вычислений. // Процессы управления и устойчивость. Труды XXXVI Межвузовской научной конференции аспирантов и студентов 11-14 апреля 2005 года. / Под

редакцией Н.В.Смирнова, В.Н.Старкова. СПб: Издательство СПб-ГУ, 2005. с. 256-260.

5. Виноградов Е.В. Погрешность вычисления ряда при полуинтервальной организации вычислений. // Вестник Санкт-Петербургского Государственного Университета. Сер. 1. 2006. Вып. 3. с. 148-152.

6. Виноградов Е.В. Зубов П.А., Меньшиков Г.Г. Реализуемость и доказательность гипотез о машинной арифметике, положенных & основу интервальных вычислений // Всероссийское (с международным участием) совещание по интервальному анализу и его приложениям Интервал-06, 1-4 июля 2006 года, Петергоф, Россия. Расширенные тезисы докладов. - СПб.: НИИ Химии СПбГУ, 2006 г. с. 30-33

Отпечатано копировал ъно-множительным участком отдела обслуживания учебного процесса физического факультета СПбГУ. Приказ № 571/1 от 14.05.03. Подписано в печать 20.ll.0ti с оригинал-макета заказчика. Ф-т 30x42/4, Усл. иеч. л. 1. Тираж 100 экз^ Заказ № 454/с 198504, СПб, Ст. Петергоф, ул. Ульяновская, д. 3, тел. 428-43-00.

Введение

1 Алгоритмика вычислений

1.1 Основные определения.

1.1 1 Варианты организации интервальной стандартной процедуры.

1.1.2 Базовый промежуток.

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

1.2 Применение рациональных аппроксимаций.

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

1.2.2 Формирование локализующего интервала для значения функции на базовом промежутке.

1.2.3 Выбор параметров, от которых зависит точность.

1.2.4 Различные случаи задания коэффициентов вычисляемого полинома.

1.3 Погрешность вычисления ряда.

1.3.1 Введение

1.3.2 Оценка относительной величины арифметической погрешности.

2 Исследование некоторых элементарных функций

2.1 Вариант процедуры для экспоненты.

2.1.1 Общие соображения, выбор базового промежутка.

2.1.2 Аппроксимация и локализующий промежуток для вычисляемой функции.

2.2 Вариант процедуры для натурального логарифма.

2.2.1 Общие соображения, выбор базового промежутка.

2.2.2 Границы для логарифма в базовом промежутке.

2.2.3 Алгоритм нахождения и: сохранение монотонности. . 51 2 2.4 По1 решнос 1 ь нахождения и.

2.3 Вариант процедуры для арктангенса.

2.3.1 Общие соображения, выбор базового промежутка.

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

2 3.3 Арифметическая погрешность аргумент степенною ряда.

2.4 Сравнение предлагаемых методов с разрабошнными ранее.

3 Реализация программных модулей.

3.1 Общие сведения.

3.2 Общие программные модули.

3.2.1 Библиохека вспомогааельных меюдов.

3.3 Базовый класс вычислителя.

3 3.1 Методы, реализующие общую для всех функций логику вычисления.

3 3.2 Меюды, нуждающиеся в переопределении.

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

3.4 Базовый класс вычислителя для рядов.

3.5 Программная реализация вычисления экспоненты.

3.5 1 Численные результаты работы программы для экспоненты.

3.6 Программная реализация вычисления натурального логарифма.

3.6.1 Численные результаты работы программы для натурального логарифма.

3.7 Программная реализация вычисления арктангенса.

3.7.1 Численные результаты работы программы для арктангенса.

В настоящий момент акшвное развшие вычисли 1ельной техники и использование ее в научных исследованиях и различных областях производства требу-юг наличия алгоритмов, гарантирующих получение результата с точностью, не меньшей наперед заданной.

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

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

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

В таком случае традиционные методы вычислений предусматривают ответ на вопрос «чему приблизительно равно?». Однако точность полученного результата в большинстве случаев определить методами традиционных вычислений весьма проблематично в связи тем, что количество возникающих в процессе расчета погрешностей увеличивается BMecie с количес1вом вычислительных операций.

В 1985 году Институтом IEEE был принят стандарт на вычисления с плавающей точкой [58]. В этом документе указаны требования, предъявляемые к округлению чисел, выполняемому в операциях сложения, умножения, вычитания, деления и извлечения корня, что позволило сделать компьютерные вычисления более корректными и доказательными [64].

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

Основной причиной для такого результата является Table Maker's Dilemma [77]: если есть число х и некоторая элементарная функция /, вычисление правильно округленного к формату числа с плавающей точкой результата у = }{х) может потребовать слишком большой точности промежуточных вычислений (причем требуемая точность промежуточных вычислений заранее неизвестна).

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

• Традиционные вычисления.

• Интервальные вычисления.

• «Гибридные» вычисления.

• Другие методы.

Рассмотрим перечисленные методы.

Традиционные вычисления Этот метод предусматривает использование классических способов вычисления, т.е. использование компьютера в качестве калькулятора, идентично копируя вычисли:ельный процесс так, как он происходил без использования автоматизированных систем. Обработка ошибок либо не предусмотрена вообще, либо крайне ограничена. Однако точность результата никак не гарантируется.

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

Сравнительно недавно в литературе стали появляться описания алгоритмов, которые умею г «подстраиваться» под требуемую точность Один из них был предложен в работе [57]. Он предусматривает увеличение точности вычислений в случае необходимости. Для этого в процессе вычислений проводятся тесты на точность, и если они не выполняются, точность вычисления увеличивается путем использования переменных большей длины. Однако критерии, используемые для сигнализации о необходимости увеличения точности, представляются не совсем надежными.

Интервальные вычисления. Другой метод поиска решения, так называемые интервально - локализующие вычисления [48], ищут ответ на дру1 ой вопрос - «в чем содержится?», т.е. вместо того, чтобы искать результат вычисления в виде одного числа, он ищется в виде вилки - ин!ерва-ла вида [а, 6], в котором гарантировано будет лежать точный результат. Этот способ как правило довольно дешев - в большинстве случаев он может использоваться на тех аппаратных и программных средствах, которые имеются в наличии (в отличие от традиционных методов, которые требуют минимум создания собственных типов данных), а кроме того, позволяет манипулировать точностью полученных результатов, и требует минимум программирования - в некоторых случаях фебуется только переопределение стандартных функций.

Термины «интервал», «интервальный» впервые появились в работе Те-руо Сунаги [83] в 1956-58-м, двумя годами раньше была опубликована работа Мечислава Вармуса [85]. В этих работах была предложена классическая интервальная арифметика и намечены ее приложения. Кроме того, Т. Су нага заложил основы интервального алгебраического формализма и дал весьма нетривиальные примеры применений новой техники, к примеру, в численном решении задачи Коши для обыкновенных дифференциальных уравнений [70].

Первая систематическая монография [70], посвященная локализующим вычислениям, была написана Раймоном Э. Муром 1966-м году.

В СССР у исюков развития этого направления еще в 20-х годах прошлого века стоял В.М. Брадис, предложивший использование «метода границ» ([6], [7]).

В 1962-м году в одном из первых выпусков «Сибирского математического журнала» появилась статья Лауреата Ленинской, Сталинской и Нобелевской премии Леонида Витальевича Канторовича [22], обозначившего эту тематику как приоритетную для нашей вычислительной науки.2

Дальнейшее развитие интервальные методы получили в СССР в рабохах академика Николая Николаевича Яненко и ею ученика Юрия Ивановича Шокина, а также ряда других авторов ([11], [21],[50]). В иностранной литературе также было опубликовано множество работ, посвященных интервальному анализу, например [2]

В настоящий момент разви!ие интервально - локализующих вычислений продолжается, и эти методы находят применение во все большем количестве отраслей науки и производства (медицинская техника, экономика [10], распознавание изображений, задачи классификации и регрессии (в том числе и с нечеткими множествами) [28], металлургия [9], задачи управления [8], и т.д.).

В рамках интервального подхода разработано большое количество методов, позволяющих получать различные интервальные расширения стандартных функций (например, через декомпозицию графика [43]).

Существуют библиотеки интервальных функций для различных языков программирования ([72], [74]), а также для специализированных вычислительных сред типа MATLAB ([25], [66]).

К недостаткам этого метода можно отнести слишком большое в некоторых случаях расширение локализующего интервала.

Гибридные» вычисления. К э'юй группе относятся вычислительные алгоритмы, использующие как традиционные, так и интервальные методы.

Например, А. Зив в 1991 году опубликовал работу «Fast evaluation of elementary mathematical functions with correctly lounded la&t bit» [86]. Методы, примененные им, были основаны на вычислении значения функции не на всей области определения, а лишь на некоюром сравни! ель-но узком базовом промежутке. При этом для вычисления требовалось использование так называемой «двойной» арифметики (т.е. величин, составленных из двух чисел типа double)

В настоящий момент резулыаты, полученные А. Зивом, активно используются для построения алгоритмов доказательных вычислений ([55], [56]).

Другие. Существует еще некоторое количество подходов к вычислению на компьютере. Например, ме!Од, основанный на использовании таблиц заранее посчитанных констант. Одной из первых работ в этом направлении была [65]. Такие алгоритмы получили распространение в связи со значительным удешевлением оперативной памяти, требуемой ими (например, в алгоритме АТА-М в упомяну!ой pa6oie используются таблицы размером 2Мб). Однако эют алгоритм предназначен для приближенного вычисления (хотя и достаточно быстрого), а не для получения гарантированных оценок.

Конечно, существуют и другие, менее распространенные методы.

Кроме общей идеологии процесса вычисления, на точность результата оказывают влияние методы получения мащинно-представимого числа из точного (иначе говоря, методы округления).

Известно, что в случае получения в качестве результата интервала в явной (указаны границы) или неявной (указан результат, и извеспю, чю точное решение отличается от него не более чем на г, где с может вычисляться, например, как где Л - максимальное значение oiношения абсолютной величины округления к единице младшего разряда, fi~s - величина единицы младшего разряда переменной результата) форме наиболее часто встречакн-ся три указанных далее способа.

Пусть значение какой-то переменной х содержится в некотором интервале [a,b],a < b. Предположим, что надо оценить значение е-'. Очевидно, что оно содержится в интервале [ert,pft], но поскольку числа еа, еь могут оказаться не машинно-представимыми, для оценки значения ех используют следующие интервалы:

1. Интервал, границы которого - приближенные значения чисел еа и еь. Для вычисления приближенных значений можно использовать, например, функции стандартных математических библиотек.

2. Интервал, полученный так же, как и первый, расширенный на некоторое заранее сосчитанное е (например, таким значением может быть Х/-Гь).

3. Гарантированный интервал, т.е. интервал, нижняя граница которого - максимальное машинно-представимое число, не превосходящее е", а верхняя граница - минимальное машинно-представимое число, не меньше еь

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

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

Трешй способ называв!ся вычислением с гарантированной точностью Несмотря на то, что при его использовании в итерационном процессе будет происходить постепенное расширение интервала, этот способ позволяет гарантировать, что истинное значение некоторого выражения лежит в ишер-вале, которым это значение представлено.

Анализ доступных интервальных математических библиотек ([26]) показал, что они производят вычисления либо первым (например, [63]), либо вторым способом (например, [71]).

Нередко хороших результатов удается достичь в построении алгоритмов для вычисления некоторого класса функций (например, в данной работе рассматриваются неубывающие элементарные трансцендентные функции). Так как у этого класса функций можно выделить специфичные свойства, есть возможность сузить результирующий интервал с помощью введения некоторых ограничений, про которые известно, что для данного класса функций они будут выполняться. В связи с тем, что на насюящий момент накоплен обширный материал как по аппроксимации функций, в том числе и трансцендентных ([3],[4],[5], [45],[46], [51]) так и но их свойствам ( [18], [23]), такой подход представляется достаточно продуктивным.

Целью данной работы является создание вычислительных алгоритмов для получения максимально узкой оценки погрешности результат вычисления для заданного формата переменных, и интервала такой ширины, таранти-рованно содержащею точный результат, без использования расширенных (удвоенных) типов данных для некоторого класса функций, представимых полиномом (или рядом) с неотрицательными коэффициентами. Иначе говоря, строятся методы, позволяющие получить как можно меньший по ширине результирующий интервал в имеющемся формате переменных, для элементарных трансцендентных функций (например, экспоненциальная функция, логарифм, арктангенс). В связи с тем, что при построении алгоритмов учитываются различные свойства вычислительной системы (величина единицы младшего разряда в определенном формам, «точность» арифметики, и т.д.), они применимы на большинстве используемых сейчас вычислительных машин, и позволяют провести быструю адаптацию к новым.

Вычисления проводятся в некотором базовом промежутке [0, т$], что, с одной стороны, требует дополнительных исследований вычисляемой функции, но с другой стороны позволяет повысить качество вычислений. Для рассматриваемых функций приводятся критерии выбора базового промежутка, способы приведения аргумента к базовому промежутку (входа в базовый промежуток) и получения значения функции для исходного аргумента по результату для аргумента в базовом интервале (выхода из базового промежутка).

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

Диссертационная работа состоит из введения, трех глав, заключения и двух приложений, включает в себя семь иллюстраций и четыре таблицы. Общий объем работы - 149 страниц.

Заключение

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

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

Кроме того, в работе приводятся некоторые дополнительные аналитические рассуждения, прямая необходимость в которых для построения алгоритмов расчета экспоненты, натурального логарифма и арктангенса отсутствует. Однако эти рассуждения позволяют проводить расчеты для других классов функций, которые тут не рассматриваются (одним из примеров такого анализа служит раздел «Различные случаи задания коэффициентов вычисляемого полинома»)

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

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

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

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

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

1. Абрамовиц М., С1иган И. Справочник по специальным функциям с формулами, графиками и математическими таблицами. - М: Физмат-гиз, 1963.

2. Алефельд Г., Херцбергер Ю. Введение в интервальные вычисления. -М.: Мир, 1987. 260 с.

3. Бейтмен Г., Эрдейи А. Том 1. Высшие трансцендентные функции. Гипергеометрическая функция. Функции Лежандра // пер. г английского Н.Я. Виленкина. М.: Наука, 1973. 295 с.

4. Бейтмен Г., Эрдейи А. Том 2. Высшие трансцендентные функции. Функции Бесселя, функции параболического цилиндра. Ортогональные многочлены. // пер. с английского Н.Я. Виленкина. М.: Наука, 1974. 2951. С'.

5. Бейтмен Г., Эрдейи А. Том 3. Эллиптические и автоморфные функции. Функции Ламе и Матье. // пер. с английского Н.Я. Виленкина. М.: Наука, 1955. 299 с.

6. Брадис В.М. Опыт обоснования некоторых практических правил действий над приближёнными числами. Тверь, 1927.7J Брадис В.М. Теория и практика вычислений. Пособие для высших педагогических учебных заведений. Москва: Учпедгиз, 1937.

7. Добронец Б.С., Шайдуров В.В. Двусторонние численные методы. Новосибирск. Наука. Сиб. отделение, 1990. 208 с.

8. Виноградов Е.В. Погрешность вычисления ряда при нолуинтервальной организации вычислений. // Вестник Санкт-Петербургского Государственного Университета. Сер. 1. 2006. Вып. 3, 2006. с. 148-152.

9. Выгодский М.Я. Справочник по высшей математике. М: Наука, 1975.

10. Градштейн И.С., Рыжик И.М. Таблицы интегралов, сумм, рядов и произведений. Москва: Физматгиз, 1963.

11. Двайт Б.Г. Таблицы интегралов и другие математические формулы // Пер. с английского Н.В. Леви. М.: Наука, 1973. 228 с.

12. Калмыков С.А., Шокин Ю.И , Юлдашев З.Х. Методы интервального анализа. Новосибирск: Наука. Сиб. отделение, 1986. 221 с.

13. Канторович JI.B. О некоторых новых подходах к вычислительным методам и обработке наблюдений // Сибирский Математический Журнал.- 1962. Т. 3, No. 5. - С. 701-709.

14. Картер А, Франц В. Трансцендентные функции // пер. с английского Н.Я. Виленкина. М.: Издательство иностранной литературы, 1963. 466 с.

15. Корн Г., Корн Т. Справочник по математике. М: Наука, 1974.

16. Лоенко М.Ю. Методы внешнего оценивания множества решений задачи удовлетворения огарничений. Диссертация на соискание ученой степени кандидата физико-математических наук, Новосибирск, 2003. 134 с.

17. Люстерник Л.А., Червоненкис О.А , Янпольский А.Р. Математический анализ. Вычисление элементарных функций. Москва: Физматгиз, 1963.

18. Меньшиков Г.Г. Интервальный анализ и методы вычислений. Вып. 1. Введение в интервальную организхацию вычислений СПб.: НИИ Химии СПбГУ, 1996. - 36 с.

19. Меньшиков Г.Г. Интервальный анализ и методы вычислений. Вып. 2. Двустороннее решение элементарных задач. Проблема грубости композиционного интервального расчета. СПб.: НИИ Химии СПбГУ, 1996. -33 с.

20. Меньшиков Г.Г. Инхервальный анализ и методы вычислений. Выи. 4. Введение в аппроксимацию функций СПб.: НИИ Химии СПбГУ, 1997. -33 с.

21. Меньшиков Г.Г. Интервальный анализ и методы вычислений. Вып. 5. Исследование функций одной переменной. Дифференцирование функций. СПб.: НИИ Химии СПбГУ, 1998. - 72 с.

22. Меньшиков Г.Г. Интервальный анализ и методы вычислений. Вып. 6. Локализующее вычисление интегралов СПб.: НИИ Химии СПбГУ, 1998. - 84 с.

23. Меньшиков Г.Г. Интервальный анализ и методы вычислений. Вып. 7. Аппроксимация функций и верификация приближений СПб.: НИИ Химии СПбГУ, 1998. - 67 с.

24. Меньшиков Г.Г. Инхервальный анализ и методы вычислений. Вып. 8. Итерационные процессы и системы числовых уравнений СПб.: НИИ Химии СПбГУ, 1999. - 82 с.

25. Меньшиков Г.Г. Локализующие вычисления: Конспект лекций. Выпуск 1. Введение в интервально-локализующую организацию вычислений. СПб: ООП НИИХ СПбГУ, 2003. 89 с.

26. Меньшиков Г.Г. Локализующие вычисления: Конспект лекций. Выпуск 1. Введение в интервально-локализующую организацию вычислений Издание второе. СПб: ООП НИИХ СПбГУ, 2003. 89 с.

27. Меньшиков Г.Г. Локализующие вычисления: Конспект лекций. Вып. 2. Задачи композиционного расчет и проблема грубости их интервально-локализующе1 о решения. СПб.: НИИ Химии СПбГУ, 2003. - 59 с

28. Меньшиков Г.Г. Локализующие вычисления. Вып. 3. Интервализация приближенных формул. Численное суммирование рядов. СПб.: НИИ Химии СПбГУ, 2003. - 61 с. Локализующие вычисления

29. Меньшиков Г.Г. Локализующие вычисления. Вып. 4. Введение в аппроксимацию функций. СПб.: ООП НИИХ СПбГУ, 2003. - 41 с.

30. Меньшиков Г.Г. Практические начала интервальных вычислений. Ленинград: Ленинградский Государственный Университет, 1991. 92 с.

31. Морган М. Java 2. Руководство разработчика. : Пер. с английского. :Уч. пос. М.: Издательский дом «Вильяме», 2000. 720 с.

32. Попов Б.А., Теслер Г.С. Вычисление функций на ЭВМ. Киев: Наукова Думка, 1984.

33. Прудников А.П., Брычков Ю.А., Маричев О.И. Интегралы и ряды. Том

34. Элементарные функции М: Наука, 1981. 801 с.

35. Прудников А П., Брычков Ю А , Маричев О.И. Интегралы и ряды. Том

36. Специальные функции М: Наука, 1983. 753 с.

37. Савельев Л.Я. Комбинаторика и вероятность. Новосибирск: Наука (Сибирское отделение), 1975. 434 с.

38. Сайт по интервальному анализу ИВТ СО РАН: http://www.ict.nsc.ru/interval

39. Солонина А.И., Улахович Д.А., Яковлев Л.А. Алгоритмы и процессоры цифровой обработки сигналов. СПб: БХВ-Петербург, 2001, 454 с.

40. Шокин Ю.И. Интервальный анализ. Новосибирск: Наука, 1981.

41. Янке Э., Эмде Ф., Лёш Ф. Специальные функции. Функции, графики, таблицы // Перевод с 6-го переработанного немецкого издания по редакцией Л.И. Седова. М.: Наука, 1964. 344 с.

42. BibTeX bibliography elefunt.bib: http://netlib2.cs.utk.edu/bibnet/journals/elefunt.html53. boost C-H Libraries: http://www.boost.org/

43. Dietz H., Dieter В., Fisher R., Chung K. A Floating-Point Evaluation with Just Enought Accuracy // ICCS2006, Part I, LNCS 3991. Berlin-Heidelberg, 2006. p. 226-233.

44. IEEE Standard for binary floating-point arithmetic: Tec. Rep. IEE Std 7541985. Institute of Electrical and Electronic Engeners, 1985. Reaffirmed, 1990.

45. Goulard F. GAOL, http://sourceforge.net/projects/gaol

46. Gardenes E., Trepat A. The interval computing system SIGLA PL/1(0) // Freiburger Intervall-Berichte. - No. 79/8. - S. 1-57

47. Garloff, J. The Bernstein Algorithm Interval Computations, №2, pp. 154168, 1993.

48. Garloff, J. Application of Bernstein expansion to the solution of control problems. Reliable Computing 6, №2, pp.303-320, 2000.

49. Glibc Library for use with GNU/HURD and GNU/LINUX, http: //www.gnu.org/software/libc

50. Goldberg D. What every computer scientist should know about floatingpoint arithmetic. ACM Computing Surveys, 23(l):5-47, March 1991.

51. Goto E., Wong W.F. Fast evaluation of elementary function in double precision // Proc. of the Twentyt-Seventh Hawaii International Conf/ on System Sciences. Vol. 1; Aichitecture.-Hawaii, 1994. P.349-358.

52. IntLab. Interval Library for MATLAB: http://www.ti3.tu-harburg.de/rump/intlab/

53. Kahan W. Lecture Notes on the Status of IEEE Standerd 754 for Binary Floating-Point Arithmetic. Berkley: Elec. Eng. & Computer Science, University of Califoi nia, 1997. 30 c.

54. Kaucher E. Interval Analysis in the Extended Interval Space HE //Computing, Suppl. 2. (1980), pp. 33-49.

55. Kramer, W.: Evaluation of Polynomial in Several Variables with High Accuracy. IMACS Annals on Computing and Applied Mathematics 12, J,C,Baltzer AG, Scientific Publishing Co., Basel, pp.239-249, 1991

56. Math library filib l |: http://www2.informatik.uni-wuppertal.de/wiswt/software/filib++/filib+ f -dist.tar.gz

57. Nataraj, P.S.V., and Kotecha, K. An algorithm for global optimization using the Taylor-Bernstein form as inclusion function. J.Global Optimization 24, №4, pp.417-436, 2002

58. Math library IAMath: http://interval.sourceforge.net/interval/java/iamath/README.html

59. Moore R. Interval Analysis. Englewood Cliffs: Prentice-Hall, 1966.

60. Muller Л.-М. Elementary Functions, Algorithms and Implementation. Birkhauser, Boston, 1997.

61. Neumaier A. Introduction to Numerical Analysis. Cambridge University Press. Cambridge, UK, 2001, pp. 356.

62. Pineiro J.A., Bruguera J.D., Muller J.M. Powering by Table Look-Up using a second-degree minimax approximation with fused accumulation tree, http://citeseer.ist.psu.edu/399804.html, 2000

63. Rokne, J.: Bounds for an interval polynomial. Computing 18, pp.225-240, 1977

64. Rokne, J.: A note on the Bernstein Algorithm for bounds for interval polynomials. Computing 21, pp.159-170, 1979.

65. Rokne, J.: Optimal Computation of the Bernstein Algorithm for the bound of an interval polynomial. Computing 28, pp.239-246, 1982.

66. Warmus M. Calculus of approximations // Bull. Acad. Polon. Sci 1956. -CI. Ill, vol. IV, No. 5. - P. 253-259.

67. Ziv A. Fa&t evaluation of elementary mathematical functions with correctly rounded la&t bit. // ACM Tarnsactions on Mathematical Software 17(3) September 1991. p. 410-423.

68. XSC software: http://www.xsc.de