В чем преимущество LU-преобразования перед методом Гаусса?

[vajsaforutube]

Всем привет! Подскажите пожалуйста, в чем преимущество по времени LU-преобразования перед методом Гаусса при решении Систем Алгебраических Линейных Уравнений ?

Правильно ли я понимаю, что суть LU в следующем: при прямом проходе метода Гаусса, матрица сводится к верхнетреугольной вычитанием строк, притом каждая операция вычитания строк в матричном виде представляется как умножение исходной матрицы на нижнетреугольную трансвкцию, например умножение исходной матрицы A на трансвекцию T слева:

A=
1 4 7
2 5 8
3 6 9

T=
1 0 0
-2 1 0
-3 0 1

TA=
1 4 7
0 -3 -6
0 -6 -12

соответствует уничтожению всех элементов первого столбца, кроме первого.

В таком случае, прямой проход метода Гаусса можно представить как произведение всех этих трансвекций, что дает нижнетреугольную матрицу. Эта нижнетреугольная матрица - и есть L, а верхнетреугольная, которая получилась в ходе прямого прохода Гаусса - и есть U?

Везде утверждают, что если вы решаете много уравнений AX=B, где A одна, а правых частей B - много разных (в частности, при поиске обратной матрицы), то LU быстрее Гаусса. Почему? Ведь, если вы нашли LU-разложение за O(N^3), то вы могли бы найти и обратную матрицу A^-1 Гауссом за тот же O(N^3) и просто умножать на нее вектор B в правой части, чтобы искать каждый вектор решений X, что занимает O(N^2) что с LU, что без?

[Евгений Машеров]

Там та же кубическая зависимость от порядка матрицы, но примерно вдвое меньше коэффициент при кубическом члене.

[vajsaforutube]

Спасибо, Евгений, вы уже второй раз мне помогаете! Однако, у меня баланс не сходится: вот народ тоже пишет, что с LU преимущество по скорости в вычислении обратной матрицы в 2/3 раза (и ради этого стоило огород городить! :)), но у меня выходит только проигрыш:

Прямой проход Гаусса требует ~N^3/3 на то, чтобы свести входную матрицу к диагональному виду и порядка N^2 на синхронное применение тех же операций к единичной, чтобы свести ее к нижнетреугольной, а обратный проход займет N^2 на то, чтобы верхнетреугольную, в которую превратилась входная матрица, превратить в диагональную, плюс N^3/2 на окончательное вычисление обратной.

LU же требует тот же прямой проход, но вместо обратного умножает N векторов на LU, что требует вдвое больше - N^3 времени.

Вот индийский товарищ получил те же расчеты для отдельных этапов, но обманывает человечество, требуя в Гауссе зачем-то N раз повторить прямой проход. Из-за этого у него в чистом Гауссе вылезло N^4.
http://numericalmethods.eng.usf.edu/vid ... hylu2.html

Не пойму, где я ошибся.