2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Решение больших разреженых матриц
Сообщение26.05.2011, 12:34 


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

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

 Профиль  
                  
 
 Re: Решение больших разреженых матриц
Сообщение26.05.2011, 13:30 
Заслуженный участник


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

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


06/05/11
8
Спасибо большое, nestoklon!

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

 Профиль  
                  
 
 Re: Решение больших разреженых матриц
Сообщение26.05.2011, 15:51 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Решение больших разреженых матриц
Сообщение26.05.2011, 17:01 


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

 Профиль  
                  
 
 Re: Решение больших разреженых матриц
Сообщение26.05.2011, 17:20 
Заслуженный участник


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group