Кафедра Вычислительных машин систем и сетей

ВЫЧИСЛЕНИЙ Лекция на тему : «Высокоточные вычисления»
Москва 2019 г.

И.И., д.т.н., Оцоков Ш.А)
Геометрическое моделирования (к.т.н., Орлов Д.А.)
Технология виртуальной реальности

(к.т.н., Харитонов В.Ю)

Паблик в соц сети: http://vk.com/club50059448

Направления по курсу ПОВ

с машиной
трудоёмкость выполнения арифметических операций
экономичность системы (количество элементов, необходимых для

представления многоразрядных чисел)
удобство аппаратной реализации

Требования к системам счисления

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

Формат с плавающей

точкой

Нарушение законов алгебры (коммутативности, дистрибутивности и др.)
x ≠ (х+х)-х

…

Значения математических эквивалентных выражений могут быть не равными друг другу (вычислительные аномалии)

…

последствия

…

3

результаты на различных аппаратных платформах.
Сложность использования численных методов (требуются экспертные

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

порядок от 0 до 4.)
Истинный результат

= 8779
Вычисленный в формате с плав. точкой один. точн. равен 4.6E+0020.

Пример.

3

С точностью 2 знака после запятой
С точностью 3 знака

после запятой

Макс. относ. погрешн. более 100%.

Макс. относ. погрешность более 100%.

Матрица Гильберта

Точный результат:

разр, 60-233 МГц
Рост разрядности и тактовой частоты процессоров по годам
Гипотеза:

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

ZREAL(Россия), MPARITH(Германия), GMP(США)
и др.
Основная проблема
Резкое увеличение времени

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

К настоящему времени модулярная арифметика

использовалась как средство повышения быстродействия в криптографии, нейронных сетях, цифровой обработке сигналов и др.
Проведенные исследования показали качественно новые возможности применения модулярной арифметики в повышении точности вычислений и ослаблении зависимости времени вычислений от точности, для некоторых частных задач:
решение дифференциальных уравнений методами Рунге-Кутта,
нахождение скалярного произведения векторов,
решения систем линейных уравнений методами Гаусса-Зейделя,
релаксации,
дискретном преобразовании Фурье .

t0=0
Шаг интегрирования:
E – относительная
погрешность

решения

Результат решения методом Эйлера

0

0,00005

0,0001

0,00015

0,0002

0,00025

11

12

13

14

15

16

17

18

19

20

21

q

E,%

Точное решение:

Число обусловленности:

задачу вычисления функции ex . Известно, что эта задача хорошо

обусловлена.

при x<0

Пример.
Найти значение функции ex при x= -15.
Верное значение e-15 =1 / e15  0.000000305902

1. Традиционные вычисления
После выполнения 82 итераций было получено: e-15  0.000000256502
Относительная погрешность
составила 19,2%.

2. Вычисления с исключ. ошибок окр.
После выполнения 60 итераций было получено:

e-15 

1822987410130384149007132206840681602541990778449289

59593604795584246682595675324534356863378751133750157901824

или e-15 0.000000305903159. Отн. погр. равна 0,0001%

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

- время вычислений в

модулярной
арифметике при той же точности.

АРИФМЕТИКИ
ось целых чисел Z
Преобраз. в многомодульную модулярную систему
Дробь
Фарея

Многомод.

модулярная арифметика

mod m1 mod mn

ось рациональных чисел Q

...

...

Обрат.
преобр

Порядок дробей Фарея

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

для нее выполняется неравенство «равнобедренного треугольника»
Любое рациональное число  имеет единственное р-адическое разложение:

Код Гензеля H(p,r,) - отрезок длины r бесконечного р-адического разложения числа .
Теорема

где m=p r

ГЕНЗЕЛЯ
множество
p-адических чисел
Преобразование в коды Гензеля (Hensel code)
Дробь
Фарея

Арифметика Обратн.

кодов преобр
Гензеля

Условие псевдопере- полнения

ось рациональных чисел

Код Гензеля - конечно-разрядное р-адическое число для которого
выполняется неравенство:
, где порядок дроби
Фарея, простое число,
количество цифр в коде, дробь.
Операции сложения, вычитания, умножения и деление выполняются “слева направо”.
Цифры кода Гензеля в обратном порядке образуют ичное представление дроби по модулю

КОДОВ ГЕНЗЕЛЯ
множество p-адических чисел
Преобразование в многомодул. коды Гензеля с

модулями и порядками

соответственно.

Дробь
Фарея

Параллельная
арифметика кодов Гензеля

Условие псевдопере- полнения

ось рациональных чисел

...

...

Обратн.
преобр.

...

...

Сложность арифметических операций в кодах Гензеля в двоичной системе счисления:




Коды

Гензеля могут применяться:
Для реализации вычислений с полиномами (полиномиальная арифметика)

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

Maple
Коды Гензеля
Средний коэфф.
абс. ускорения:

Kабс  1,5

к двум величинам и

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


При симметричном округлении максимальная относительная погрешности выразится так:



Формулы относительных ошибок при 4-х арифметических операциях имеют вид:







где ошибка округления.

ФОРМУЛЫ ОТНОСИТЕЛЬНЫХ ОШИБОК ОКРУГЛЕНИЯ

Граф вычислительного процесса имеет следующий вид:





ВЫДЕЛЕНИЕ ГРАФ-СХЕМЫ ВЫЧИСЛИТЕЛЬНОГО

ПРОЦЕССА

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

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


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

+1

+1

. Полная ошибка результата операции умножения выразится следующим образом:





Если

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


Поэтому

АНАЛИЗ РАСПРОСТРАНЕНИЯ ОШИБОК ОКРУГЛЕНИЯ

оба неотрицательные, то

Не может быть больше 1, и окончательно имеем:

обратных матриц. Например, таких как, g-обратная матрица Мура-Пенроуза. Многие

алгоритмы требуют умения распознавать значение численного ранга, а это является трудной задачей при наличии ошибок округления.
2. Целочисленное решение систем линейных уравнений. Примером могут служить построение оптимальных решений в задачах целочисленного программирования.
3. Точное вычисление характеристического многочлена матрицы. Вследствие ошибок округления будут получены приближенные значения коэффициентов. Если многочлен плохо обусловлен, то корни "приближенного» характеристического уравнения могут быть плохими приближениями к корням истинного уравнения.
4. Обращение матриц Гильберта, Адамара и др. особо чувствительных к ошибкам округления.
5. Для решения промежуточных между классами корректных и некорректных задач.
Класс задач, изменяющих корректность при решении. Это расчет устойчивости систем управления, выч. собств. знач. систем лин. одн. урав. и др.

неустойчивые алгоритмы
Вычисления
с исключением
ошибок округления

и ядерного синтеза (МЭИ)

Динамическая устойчивость энергосистем
...