Войти
В численном анализе, метод Стоун, также известный как сильно неявная процедура или SIP, представляет собой алгоритм для решения разреженной линейной системы уравнений. Метод использует неполное разложение LU, которое приближает точное разложение LU, чтобы получить итеративное решение проблемы. Метод назван в честь Гарольда С. Стоуна, предложившего его в 1968 году.
LU-разложение - отличное средство решения линейных уравнений общего назначения. Самый большой недостаток заключается в том, что он не может использовать матрицу коэффициентов как разреженную матрицу. LU-разложение разреженной матрицы обычно не является разреженным, поэтому для большой системы уравнений LU-разложение может потребовать чрезмерно большого количества памяти и количества арифметических операций.
В итерационных методах с предобусловливанием, если матрица предобуславливателя M является хорошей аппроксимацией матрицы коэффициентов A, то сходимость происходит быстрее. Это приводит один к идее использования приближенной факторизации LU из A в качестве итерации матрицы М.
Версия метода неполной нижней-верхней декомпозиции была предложена Стоуном в 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|| gt;gt; ||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
