Математика

Численное решение линейных систем

Итерации, трёхдиагональные решатели и вычислительная сходимость Ax=b.

Как выбрать подходящий материал

Сначала учтите структуру матрицы. Для трёхдиагональной системы подходит прогонка при выполнении её условий, для итераций нужна проверка сходимости.
Критерием точности служит невязка вместе с обусловленностью, а не только изменение соседних приближений. Параметр релаксации выбирают для конкретной матрицы.

5 формул

Формулы темы

Метод Якоби для системы линейных уравнений

Метод Якоби строит новое приближение к решению Ax=b, одновременно пересчитывая все неизвестные из значений предыдущего шага. Он удобен для разреженных систем и хорошо показывает, зачем проверять сходимость, а не только выполнять заданное число итераций.

$x_i^{(k+1)}=\frac{b_i-\sum_{j\ne i}a_{ij}x_j^{(k)}}{a_{ii}},\quad i=1,\ldots,n$

Метод Гаусса—Зейделя для системы линейных уравнений

Метод Гаусса—Зейделя решает Ax=b последовательными проходами: новая компонента сразу участвует в вычислении следующих. Это обычно ускоряет простую итерацию, но делает результат одного прохода зависимым от порядка переменных.

$x_i^{(k+1)}=\frac{b_i-\sum_{j<i}a_{ij}x_j^{(k+1)}-\sum_{j>i}a_{ij}x_j^{(k)}}{a_{ii}}$

Метод SOR: последовательная сверхрелаксация

Метод SOR добавляет к проходу Гаусса—Зейделя параметр релаксации ω. При 0<ω<2 он дозирует поправку; ω=1 возвращает обычный метод, а удачный выбор ω>1 способен ускорить сходимость.

$x_i^{(k+1)}=(1-\omega)x_i^{(k)}+\frac{\omega}{a_{ii}}\left(b_i-\sum_{j<i}a_{ij}x_j^{(k+1)}-\sum_{j>i}a_{ij}x_j^{(k)}\right)$

Метод прогонки для трёхдиагональной системы

Метод прогонки решает трёхдиагональную систему за линейное число операций, используя прямой расчёт коэффициентов связи и обратную подстановку. Он сохраняет ленточную структуру вместо работы с полной матрицей.

$c_i x_{i-1}+a_i x_i+b_i x_{i+1}=d_i;\quad \alpha_i=-\frac{b_i}{a_i+c_i\alpha_{i-1}},\;\beta_i=\frac{d_i-c_i\beta_{i-1}}{a_i+c_i\alpha_{i-1}}$

Метод Ричардсона: стационарная итерация для Ax=b

Метод Ричардсона прибавляет к текущему приближению невязку, умноженную на параметр τ. Для симметричной положительно определённой матрицы разумный τ превращает эту простую формулу в сходящуюся стационарную итерацию.

$x^{(k+1)}=x^{(k)}+\tau(b-Ax^{(k)}),\qquad r^{(k)}=b-Ax^{(k)}$