Finite-budget successive over-relaxation stationary iteration

Input $n\ge 1$, $A\in M_n(\mathbb{C})$, $b,x^{(0)}\in {\mathbb{C}}^n$, a real relaxation parameter $\omega$, and an iteration budget $m\in {\mathbb{N}}_0$. Check dimensions; on a mismatch return invalid-input. If $\omega =0$, return invalid-relaxation. Form $D,L,U$ by Diagonal, lower, and upper parts in the stationary-iteration convention. If some diagonal entry of $A$ is zero, return pivot-failure(i) for the least such index $i$.

Otherwise set

$M_{\omega }={\omega }^{-1}D-L,N_{\omega }=({\omega }^{-1}-1)D+U,$

so $A=M_{\omega }-N_{\omega }$. For each $k=0,\dots ,m-1$, solve

$M_{\omega }{x}^{(k+1)}=N_{\omega }{x}^{(k)}+b$

by forward substitution in increasing index order. The lower-triangular coefficient matrix has diagonal entries $a_{ii}\mathrm{/}\omega$, which are nonzero after the checks. Return completed with $x^{(m)}$. The solve is unique by Forward and backward substitution for triangular linear systems and Forward and backward substitution are correct, unique, and quadratic in scalar operations. A zero budget returns $x^{(0)}$. This procedure is defined for every real $\omega \mathrm{\ne }0$; it reports no convergence or accuracy certificate.