метод Стоуна
 | В этой статье есть несколько проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти шаблонные сообщения )
|
В численном анализе метод Стоуна , также известный как строго неявная процедура или SIP , представляет собой алгоритм решения разреженной линейной системы уравнений . Метод использует неполное LU-разложение , которое аппроксимирует точное LU-разложение , чтобы получить итеративное решение проблемы. Метод назван в честь Гарольда С. Стоуна , предложившего его в 1968 году.
LU-разложение является отличным решением линейных уравнений общего назначения. Самым большим недостатком является то, что матрица коэффициентов не может быть разреженной матрицей. LU-разложение разреженной матрицы обычно не является разреженным, поэтому для большой системы уравнений LU-разложение может потребовать непомерно большого объема памяти и количества арифметических операций .
В с предобуславливанием итерационных методах , если матрица предобуславливателя M является хорошим приближением матрицы коэффициентов A , то сходимость происходит быстрее. подводит нас к идее использования приблизительной факторизации LU A M. в качестве итерационной матрицы Это
Версия метода неполного нижнего-верхнего разложения была предложена Стоуном в 1968 году. Этот метод предназначен для системы уравнений, возникающей в результате дискретизации уравнений в частных производных , и впервые был использован для пятидиагональной системы уравнений, полученной при решении эллиптического уравнения в частных производных в двумерное пространство методом конечных разностей . Рассматривалось приближенное разложение LU [ нужны разъяснения ] в той же пятидиагональной форме, что и исходная матрица (три диагонали для L и три диагонали для U ), как наилучшее соответствие семи возможных уравнений для пяти неизвестных для каждой строки матрицы.
Алгоритм
[ редактировать ]method stone is
For the linear system Ax = b
calculate incomplete LU factorization of matrix A
Ax = (M-N)x = (LU-N)x = b
Mx(k+1) = Nx(k)+b , with ||M|| >> ||N||
Mx(k+1) = LUx(k+1) = c(k)
LUx(k) = L(Ux(k+1)) = Ly(k) = c(k)
set a guess
k = 0, x(k)
r(k)=b - Ax(k)
while ( ||r(k)||2 ≥ ε ) do
evaluate new right hand side
c(k) = Nx(k) + b
solve Ly(k) = c(k) by forward substitution
y(k) = L−1c(k)
solve Ux(k+1) = y(k) by back substitution
x(k+1) = U−1y(k)
end while
Сноски
[ редактировать ]Ссылки
[ редактировать ]- Стоун, HL (1968). «Итерационное решение неявных аппроксимаций многомерных уравнений в частных производных». SIAM Journal по численному анализу . 5 (3): 530–538. Бибкод : 1968SJNA....5..530S . дои : 10.1137/0705044 . hdl : 10338.dmlcz/104038 . - оригинальная статья
- Ферцигер Дж. Х. и Перич М. (2001). Вычислительные методы гидродинамики . Шпрингер-Верлаг, Берлин. ISBN 3-540-42074-6 .
{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка ) - Акоста, Дж. М. (2001). Численные алгоритмы для решения трехмерных вычислительных задач гидродинамики. Кандидатская диссертация . Политехнический университет Каталонии.
- Эта статья включает текст из статьи Stone's_method на CFD-Wiki , которая находится под лицензией GFDL .