Решение больших разреженых матриц

[metallica4ever]

Немного не по теме, конечно, (хотя, столкнулся с этим при создании программы для расчета методом МКЭ) но здесь есть обсуждения по этому вопросу, может кто подскажет.

В поиске метода решения больших разреженных матриц (МКЭ) столкнулся с методом сопряженных градиентов с ILU-предобуславливанием. Разобрался как сделать ILU-разложение для исходной матрицы, разобрался в методе сопряженных градиентов. Но мне не понятно, как использовать предобуславливание (ILU-разложение) для итерационных методов... Ведь предобуславливание используется для улучшения и ускорения сходимости (для итерационных методов), но тогда получается две матрицы L и U, как здесь применять метод сопряженных градиентов (им же решаются уравнения вида Ax=f)? Или его надо использовать сначала для прямого хода, а затем для обратного, как в прямых методах? Вопрос для многих элементарный, я уверен, но уже неделю не могу разобраться с этим)

[nestoklon]

Вообще, это в любой статье про ILU написано, но идея в том, что система с полученными разреженными L и U решается за линейное число операций. Алгоритм выдаёт матрицы, произведение которых в некотором смысле похоже на A. Значит произведение $(LU)^{-1}A$ (вычисление которого линейно) в том же смысле похоже на единичную матрицу, а значит уравнения с ним должно очень быстро сходится в любом итерационном методе. Построить из решений уравнения $(LU)^{-1}A$ решения уравнения с $A$ -- дело тривиальное.
Если вы будете читать описание конкретного метода, эта идея может быть несколько закопана в технических деталях.

[metallica4ever]

Спасибо большое, nestoklon!

Т.е., если я правильно понял, то надо найти $K=U^{-1} (L^{-1} (A))$ и $b=U^{-1} (L^{-1} (f))$ и решать уже уравнение $Kx=b$ вместо $Ax=f$ итерационными методами?

[nestoklon]

Что-то вроде того.
Те, кто занимаются расчётами любят говорить, что мы используем LU в качестве preconditioner -- технически на уровне реализации это немного отличается от того, что у вас написано. Но по сути (как они любят говорить "в точной арифметике") это то же самое.
Разница в том, что конечно ни в коем случае не надо искать $K$, а реализовать итерационное решение уравнения $Kx=b$ пользуясь явным видом $K$.

[metallica4ever]

Другими словами, рассчитывать необходимые слагаемые из K и b непосредственно в цикле итерационного метода, так?

[nestoklon]

Именно. Внутри итерационного цикла решать уравнение с $K$ в три этапа -- считая умножение на $A$, а потом два раза решая простенькую систему уравнений. Как ни парадоксально, это получается очень эффективно.