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

  1. Метод Гаусса над полем
    1. Задача: решить систему уравнений Ax = b
    2. Гаусс: приводим матрицу к трапецивидному виду. Нужно менять местами строки и столбцы. O(n3). Псевдокод .
    3. Также можно приводить матрицу сразу к диагональному виду.
    4. Свободные переменные. Восстановление решения из диагонального вида за O(n) и треугольного вида за O(n2).
    5. Базис решений. Любое решение вырожается, как x0 + sum αizi, где αi − произвольные коэффициенты, x0 − начальное решение, zi − базис
      Чтобы получить x0, подставим в свободные переменные нули. Чтобы получить zi, подставим в i-ю свободную переменную 1, в остальные нули.
    6. Задача: найти det A. Она проще, так как не нужно менять местами столбцы и поддерживать перестановку индексов столбцов.
      И тем, что если встретим нулевую строку или столбец, ответ 0. Swap строк или столбцов меняет знак det A.
    7. Решение нескольких систем одним махом (b1, b2, ... bm).
      Мы уже умеем для удобства приписывать столбец b к матрице A. Давайте припишем все m столбцов, приведём матрицу к диагональному виду. Получили решение за O(n2(n+m) + nm).
    8. Вещественные числа: борьба с погрешностью.
      Пример, когда пограшность зашкаливает − матрица Гильберта aij = 1/(i+j). Для n=20 типа double уже не хватает.
      Чтобы уменьшить погрешность ставим на диагональ максимум по модулю элемент в подматрице, исползьуем long double / BigDecimal. В любом случае пограшность экспоненциальна.
      Отсюда задача: дана целочисленная матрица, как найти её ранг? Надо считать не в R, а по модулю случайного большого простого.
    9. Задача: в online по одному добавляются вектора vi ∈ Rn. Нужно поддерживать базис простарнства {v1, v2, ... vk}.
      Решение: смотри прошлогодний конспект , страница 110.
    10. Задача: координаты вектора в базисе за O(n3).
      Достаточно решить Ax = b, где столбец матрицы A − вектор базиса, b − вектор, координаты, которого мы ищем. x − координаты.
    11. Задача: обращение матрицы за O(n3).
      Решение: i-й столбец единичной матрицы обозначим bi, решим системы Ax = b1, Ax = b2, ..., Ax = bn за O(n3) одним Гауссом.
    12. Гаусс над F2n x n работает за O(n3/w).
      Над F2n (бинарные вектора) операции сложение и вычитание (оно же сложение!) работают за O(n/w).