# Метод Гаусса-Зейгеля, Numerical Modelling
## Задача со слайда 24, лекция 6, найти и показать по какой причине метод Гаусса-Зейгеля итерируется по $x^k$ и $x^{k+1}$.
### Сорокин Евгений Сергеевич, BS4-DS2

Численные методы, решения задач и упражнения (стр. 189) Бахвалов Н.С., Корнев А.А., Чижонков Е.В.

Для метода Гаусса-Зейгеля ($w=\tau=1$)

$A = L + D + R$
$B = D + wL = D + L$ - Гаусса-Зейгеля
$\frac{x_{k+1} - x_k}{\tau} + B^{-1}Ax_k = B^{-1}b$
$x_{k+1} = (D+L)^{-1}f - (D+L)^{-1}(D+L)x_k - (D+L)^{-1}Rx_k + x_k$
$x_{k+1} = (D+L)^{-1}(f - Rx_k)$ - Финальный вид

***
[Forward substitution](https://en.wikipedia.org/wiki/Triangular_matrix#Forward_and_back_substitution)
$(f - Rx_k)$ - это вектор размера [n, 1], $(D+L)$ - нижняя треугольная матрица: таким образом выражение ниже имеет возможность подстановки.
$x_{k+1} = (D+L)^{-1}(f - Rx_k) \equiv (D+L)x_{k+1} = (f - Rx_k) \equiv L^*x_{k+1} = v^k$

$v^k$ - обозначает в этом векторе используются элементы $x$ _поколения_ $k$.
## Forward substitution
$x_1 = \frac{b_1}{l_{11}}$
$x_2 = \frac{b_2 - l_{21}}{l_{22}}$
$x_i = \frac{b_i - \sum^{i-1}_{j=1}l_{ij}x_1}{l_{ii}}$

## Siegel method

Диагональные элементы матрицы R - нулевые

$x^{k+1}_1 = \frac{f_1 - \sum^m_{i=2} a_{1i}x_i^k}{a_{11}}$
$x^{k+1}_i = \frac{f_i - \sum^{i-1}_{j=1} a_{ij}x_i^{k+1} - \sum^{m}_{j=i}a_{ij}x^k_j}{a_{ii}}$, $i \in [1..m]$

Каждый строка с $x^k$ и $f_i$ - это значение вектора $(f - Ux_k)$.

Иная форма записи:
$(f-Ux_k) = v^k$

$v_i = f_i - \sum^m_{j=i} U_ij x_j$ - итерируемся по j, поскольку элементы матрицы U с индексом < i равны 0.

Таким образом выражение выше становится следующим (точно таким же, как и forward substitution):

$x^{k+1}_i = \frac{v_i - \sum^{i-1}_{j=1} a_{ij}x_i^{k+1}}{L^*_{ii}}$, $i \in [1..m]$, где $L^* = (D+L)$