Метод Гаусса и линейная алгебра (12 мая)

1. Реализация метода Гаусса над полем
1. Что можно делать: менять строки и столбцы местами, складывать строки и столбцы
2. Подсчёт определителя (только меняем местами и вычитаем строки, поддерживаем треугольность матрицы)
3. Треугольность = n³(1/3), диагональность = n³(1/3 + 1/6) = n³(1/2).
4. Решение системы уравнений: случай диагональной матрицы, случай треугольной матрицы.
5. Свободные переменные. Количество решений, базис решений.
6. Решение нескольких систем одним махом (b₁, b₂, ... b_m)
7. Вещественные числа: борьба с погрешностью. Матрица Гильберта. Выбираем максимум по модулю в подматрице, long double.
8. Поддерживаем базис векторов, инкрементальная версия Гаусса. Поддерживаем выражение базиса через исходные вектора.
2. Гаусс над Евклидовым кольцом
1. Вычисление определителя по непростому модулю (нужны только вычитания и домножения) алгоритм Евклида. Нельзя привести к Диагональному виду.
2. Решение системы уравнений, i-е уравнение дано по модулю p^k_i
3. Решение системы уравнений, i-е уравнение дано по m (все модуля одинаковые, но не простые)
4. Решение системы уравнений, i-е уравнение дано по модулю m_i (свести к одному из предыдущих пунктов, решение без LCM и факторизации)
3. Базисы
1. Дополнение произвольного базиса до полного
2. Ортогонализация Грамма-Шмидта: произвольный базис → ортогональный базис
3. Дополнение ортогонального базиса до полного
4. Вероятности и матожидания
1. В конечном графе задан Марковский процесс. В каком состоянии он стабилизируется?
2. Моделирование. Когда-нибудь сойдётся.
3. Решение возведением матрицы в степень (сойдётся быстрее!)
4. Решение Гауссом
5. Сравнение трёх методов (Гаусс − быстрее, но имеет большую погрешность)
5. Анонс: алгоритм Видеманна для решения Ax = 0 за O(nk)