Цитата
ad_dy писал(а) :
Обращаю матрицу (на компутере). Присоединенияю единичную матрицу с правого боку. Потом делаю слева треугольную матрицу. А дальше надо делать обратный ход, чтобы получить слева единичную матрицу.
А теперь вопрос - Мы же матрицу обращаем, значит не одну систему надо решать, а целых n. То есть обратный ход делается за n*O(n^2)=O(n^3) операций. Можно ли сделать быстрее, или это так и должно быть?
Так ведь и прямой ход занимает порядка n^3 операций, так что не волноваться не следует. Есть разные модификации метода Гаусса, но в любом случае порядка n^3 операций.
Штрассен придумал алгоритм, который работает за Cn^p, где p=log_2(7) (потом удалось еще уменьшить p), но эти алгоритмы применяют редко: выигрыш только при очень больших n (так как константы C большие), больше погрешности вычислений, хуже распараллеливаются.
