Машинная арифметика в рациональных числах

1.

Лекция №7
по курсу
«Машинная арифметика в рациональных числах»
Москва, 2020

2.

Устранение причины возможной ошибки
Задача.
Составить программу решения квадратного уравнения
a2 + bx + c = 0
Формулы корней квадратного уравнения достаточно сложны по числу и набору
действий:
b b 4ac
x1
2a
2
b b 4ac
x2
2a
2
Поэтому естественно предположить, что при решении поставленной задачи
возможна ситуация, при которой произойдет потеря точности.
2

3.

Из анализа формул корней, видно, что в одной из формул в числителе
обязательно будет разность чисел.
Пусть b>0, тогда при ac<<b2 числа b и
может привести к грубой ошибке.
b2 4ac
близки и формула для x2
Здесь можно полностью устранить причину возможной ошибки за счет
тождественного преобразования для х2
b b 2 4ac ( b b 2 4ac )(b b 2 4ac )
x2
2
2a
2a(b b 4ac )
b 2 4ac b 2
2a(b b 4ac )
2
2c
b b 2 4ac
Получили другую формулу для одного из корней квадратного уравнения
x2
2c
b b 2 4ac
Эта формула уже не содержит вычитания близких чисел, тем самым устранена
причина возможной грубой ошибки.
3

4.

Если b<0, то разность близких чисел возможна в формуле для х1.
Соответствующими преобразованиями можно и ее привести к виду:
x1
2c
b b 2 4ac
Очевидно, что новые формулы для корней квадратного уравнения пригодны
и для «нормальных случаев», когда разность близких чисел не возникает.
Т.о. проводить анализ близости соответствующих чисел нет необходимости.
Достаточно, определив знак b, выбрать для вычисления каждого корня ту
формулу, в которой разности чисел нет.
4

5.

Примеры вычислительно неустойчивых алгоритмов
Рассмотрим задачу вычисления функции ex . Известно, что эта задача хорошо обусловлена.
x
Обусловленность вычислительного алгоритма при x<0
xk
x 2 x3
xn
e
1 x
...
... .
k
!
2
!
3
!
n
!
k 0
x
e 2 x
при x<0
Пример.
Найти значение функции ex при x= -15.
Верное значение e-15 =1 / e15 0.000000305902
1. Традиционные вычисления
После выполнения 82 итераций было
получено: e-15 0.000000256502
2. Решение
e-x = 1/ ex
Относительная погрешность
составила 19,2%.
5

6.

Применение высокоточных вычислений для численного решения
уравнения теплопроводности с разномасштабными
коэффициентами
Нестационарное уравнение теплопроводности:
2
U
2 x
a
,
t
t
0 x l, t 0
u (0, t ) 0 (t ), t 0;
u (l , t ) l (t ), t 0,
u ( x,0) ( x ) , 0 x l
a - коэффициент температуропроводности
Уравнение теплопроводности описывает
распространение тепла вдоль стенок труб
теплообменных устройств, поверхностей нагрева
.
котлов, и других объектов.
wh {x j jh, j 0,1,..., N ;
t k k , k 0,1,..., K }
h l / N, T / K
a 2
,
h2
k 0:
Система конечно-разностных линейных уравнений:
0 (1) ( 2 1) u11 u12 (1),
1
1
1
u1 ( 2 1) u 2 u3 ( 2),
u1 ( 2 1) u1 u1 (3),
2
3
4
1
1
1
u3 ( 2 1) u 4 u5 ( 4),
...
u1N 3 ( 2 1) u1N 2 u1N 1 ( N 2),
u1N 2 ( 2 1) u1N 1 l (1) ( N 1),
4
При a 0.044, h 10 3 , 10 , N 1000, максимальная относительная погрешность решения
системы методом Гаусса-Зейделя составила около 100% при числе итераций порядка 5000.
Физическая интерпретация этих параметров может быть такой: ищется распределение температуры
магистрального трубопровода длиной 1 км через каждые 1 метр, каждые 3 часа.
Применение высокоточных вычислений позволило получить решение системы с требуемой точностью
6

7.

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

8.

Схема вычислений с исключением ошибок
округления
Рост числителей и знаменателей!
8

9.

ВОЗМОЖНЫЕ ПРИЛОЖЕНИЯ ВЫЧИСЛЕНИЙ С ИСКЛЮЧЕНИЕМ ОШИБОК
ОКРУГЛЕНИЯ
1. Точное вычисление обобщенных обратных матриц.
Например, таких как, g-обратная матрица Мура-Пенроуза. Многие алгоритмы
требуют умения распознавать значение численного ранга, а это является трудной
задачей при наличии ошибок округления.
2. Целочисленное решение систем линейных уравнений.
Примером могут служить построение оптимальных решений в задачах
целочисленного программирования.
3. Точное вычисление характеристического многочлена матрицы.
Вследствие ошибок округления будут получены приближенные значения
коэффициентов. Если многочлен плохо обусловлен, то корни "приближенного»
характеристического уравнения могут быть плохими приближениями к корням
истинного уравнения.
4. Обращение матриц Гильберта, Адамара и др. особо чувствительных к
ошибкам округления.
5. Для решения промежуточных между классами корректных и некорректных
задач.
Класс задач, изменяющих корректность при решении. Это расчет устойчивости
систем управления, выч. собств. знач. систем лин. одн. урав. и др.
9

10.

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

11.

Высокоточные вычисления с иррациональными числами
Модулярная система счисления позволяет представлять:
- целые числа,
- рациональные числа
- комплексные числа с рациональной мнимой и вещественной частью
Иррациональные числа представлять в виде цепных дробей.
Вычисления с иррациональными
числами с контролируемой
точностью.
Точное значение 10/7 это [1,2,3].
Приближенное значение [1,2]
11

12.

Способы нахождения обратного по модулю
1.
2.
3.
Подбор
С помощью малой теоремы Ферма
С помощью расширенного алгоритма Евклида
12

13.

13

14.

Алгоритм Евклида
14

15.

15

16.

16

17.

Алгоритм Евклида
17

18.

18

19.

19

20.

Алгоритм нахождения обратного
20

21.

Алгоритм обратного преобразования чисел в
дроби Фарея
21

22.

Алгоритм обратного преобразования чисел в
дроби Фарея
22

23.

Преимущество модулярной арифметики
- отсутствие переносов при сложении, вычитании и умножении чисел
- единое представление чисел различной природы (целых, комплексных)
Задачи на модулярную арифметику
Найти последние 2 цифры числа 4^30.
23

24.

Табличная реализация модулярная арифметики
Таблица умножения по
модулю m = 11
24

25.

Китайская теорема об остатках и обратное преобразование
X ( x1 , x2 ,..., xn ),
x1 x mod m1 ,
x2 x mod m2
...
xn x mod mn ,
m1 , m2 ,..., mn модули
Китайская теорема об остатках –
существует только одно число,
имеющее остатки по модулям в
диапазоне до произведения модулей
минус один
25

26.

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