Конспект: матрицы, системы уравнений и погрешность

Понятия

Матрица системы - таблица коэффициентов; правые части - отдельный столбец. Система - A x = b.

Ведущий элемент - число на диагонали, на которое делят на очередном шаге исключения.

Машинный эпсилон - наименьшая относительная прибавка, которую дробное число замечает: около 2,2 · 10⁻¹⁶; вдвое меньшая уже пропадает.

Невязка - разность A x − b для найденного x. Плохо обусловленная система - та, у которой малая ошибка данных даёт большую ошибку решения.

LU-разложение - A = L · U: множители метода Гаусса и результат прямого хода. Определитель - произведение диагонали U с учётом знака перестановок.

Что унести

ПРЯМОЙ ХОД                                        ОБРАТНЫЙ ХОД
для столбца i от 0 до n − 1:                      для строки i от n − 1 до 0:
    выбрать ведущий: наибольший |a[r][i]|, r ≥ i      x[i] = (b[i] − Σ a[i][c] · x[c]) / a[i][i]
    поменять строки r и i (и b[r], b[i])                              c > i
    для строки j ниже i:
        k = a[j][i] / a[i][i]
        строка j −= k · строка i;  b[j] −= k · b[i]

2  1  1 |  7          2  1  1 |  7          2  1  1 |  7          z = 6 / 2 = 3
4  3  3 | 19    →     0  1  1 |  5    →     0  1  1 |  5    →     y = 5 − 3 = 2
8  7  9 | 49          0  3  5 | 21          0  0  2 |  6          x = (7 − 2 − 3) / 2 = 1

Цена. Исключение - n³, решение треугольной системы - n². Вдвое больше уравнений - в восемь раз дороже. Много правых частей - разложить один раз.

ДРОБНЫЕ ЧИСЛА: 53 двоичных разряда, около 16 десятичных цифр
0.1 + 0.2 = 0.30000000000000004           десять раз по 0.1 = 0.9999999999999999
10¹⁶ + 1 = 10¹⁶                           (1 + 10⁻¹⁵) − 1 = 1.11 · 10⁻¹⁵   ← потеря значащих цифр

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

LU:  множители записываются на место нулей
2  1  1          2  1  1            L: 1 0 0     U: 2 1 1        определитель = 2 · 1 · 2 = 4
4  3  3    →     2  1  1               2 1 0        0 1 1
8  7  9          4  3  2               4 3 1        0 0 2
решение:  L y = b сверху вниз,  U x = y снизу вверх

Точная арифметика. По простому модулю деление - умножение на обратный элемент; погрешности нет. 1/5 по модулю 1 000 003 - это 600 002.

В библиотеках: numpy.linalg.solve, numpy.linalg.cond, scipy.linalg.lu_factor и lu_solve.

Степень перехода: рекуррента порядка k считается за O(k³ log n) обычных арифметических операций; Aᴸ для матрицы смежности считает маршруты из L рёбер.

Ловушки джокера

Деление на диагональ не глядя. Ноль - остановка, почти ноль - неверный ответ без ошибки.

Перестановка «только если ноль». Число 10⁻¹⁷ не ноль. Искать наибольший по модулю.

Обмен строк без обмена правых частей. Решается другая система.

== 0 и == 0.3 для дробных. Сравнивать с допуском.

Обратный ход сверху вниз. Начинать с уравнения, где неизвестное одно.

Вера в невязку. «Подставил - сошлось» не означает, что ответ верен.

Большое плюс маленькие по одному. Тысяча единиц, прибавленных к 10¹⁶, исчезают. Складывать с малых.

Деньги в дробных. Десять раз по 0,1 - не единица.

Обратная матрица ради решения. Втрое дороже разложения и менее точно.

Определитель по школьной формуле. n! слагаемых вместо n³.

Определитель как мера вырожденности. Зависит от масштаба; смотреть на число обусловленности.

Забытый знак определителя. Каждая перестановка строк меняет его.

Испорченные входные данные. После gauss в a и b лежит треугольная система.

Куда это ведёт

Глава закрывает раздел с неожиданной стороны: в целых числах всё было точно и трудность сидела в цене, в дробных цена известна и скромна, а трудность - в доверии к ответу. Конспект раздела собирает обе половины в одну таблицу: какое действие сколько стоит и что в нём может пойти не так.