2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Решение больших разреженых матриц
Сообщение26.05.2011, 12:34 
Немного не по теме, конечно, (хотя, столкнулся с этим при создании программы для расчета методом МКЭ) но здесь есть обсуждения по этому вопросу, может кто подскажет.

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

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

 
 
 
 Re: Решение больших разреженых матриц
Сообщение26.05.2011, 15:04 
Спасибо большое, nestoklon!

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

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

 
 
 
 Re: Решение больших разреженых матриц
Сообщение26.05.2011, 17:01 
Другими словами, рассчитывать необходимые слагаемые из K и b непосредственно в цикле итерационного метода, так?

 
 
 
 Re: Решение больших разреженых матриц
Сообщение26.05.2011, 17:20 
Именно. Внутри итерационного цикла решать уравнение с $K$ в три этапа -- считая умножение на $A$, а потом два раза решая простенькую систему уравнений. Как ни парадоксально, это получается очень эффективно.

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group