Есть так называемый "школьный" способ решения систем линейных уравнений — сначала приводим систему к треугольному виду, а затем вычисляем значения переменных, идём обратно и подставляем уже вычисленные, чтобы получить остальные.
Здравствуйте, Эйнсток Файр, Вы писали:
ЭФ>Мне непонятно — при чём тут перемножение матриц? ЭФ>Каким образом надо использовать быстрое умножение матриц (которое может ускорить вычисление СЛАУ)?
А разве методом Гаусса кто-то СЛАУ решает? Откуда у тебя такая инфа?
Re[2]: Как быстрое умножение матриц ускоряет вычисление СЛАУ?
N> зависит от ситуации: размер матриц, разреженность, насколько точное решение надо получить и т.д. Надо исходить из задачи, а не наоборот.
Размер матриц большой (для ручного счёта конечно, для вас-то может он маленький) — порядка 10^5 уравнений, разряженность высокая. решение нужно точное.
Re[5]: Как быстрое умножение матриц ускоряет вычисление СЛАУ?
Здравствуйте, Эйнсток Файр, Вы писали:
ЭФ>Размер матриц большой (для ручного счёта конечно, для вас-то может он маленький) — порядка 10^5 уравнений, разряженность высокая. решение нужно точное.
А переменных сколько? Матрица переопределённая или нет? Думаю, что тебе надо применить какое-нибудь разложение матрицы. QR или SVD.
Re[6]: Как быстрое умножение матриц ускоряет вычисление СЛАУ?
Я не понимаю, как QR может быть быстрее. Во-первых, он не точный, а итеративный. Во-вторых,
In this crude form the iterations are relatively expensive. This can be mitigated by first bringing the matrix A to upper Hessenberg form (which costs 10/3*n^3 + O ( n^2 ) arithmetic operations using a technique based on Householder reduction)
Здравствуйте, Эйнсток Файр, Вы писали:
ЭФ>Это 10/3*n^3 уже больше, чем n^3/4 у Гаусса...
А зачем тебе QR, если система невырожденная и имеет однозначное решение?
Точные значения ты получишь только в символьной арифметике. Сомневаюсь, что тебе надо именно это.
Re[8]: Как быстрое умножение матриц ускоряет вычисление СЛАУ
Здравствуйте, Эйнсток Файр, Вы писали:
ЭФ>Мне непонятно — при чём тут перемножение матриц?
При том, что LU факторизация — продвинутый вариант алгоритма Гаусса c pivoting, имеющий ту же вычислительную сложность.
Относительно забесплатно (квадрат против куба размера системы) получаем решение многих систем с одинаковой левой частью.
Минусы (что для Гаусса с перестановками, что для LU разложения)
— нет стабильности (даже в случае с перестановками)
— нет учета специфической структуры у матрицы в левой части. Например, если она эрмитова, то нужно факторизацию Холецкого использовать — более вычислительно эффективнее и стабильнее.
