Sostituzione in avanti e a ritroso

La sostituzione in avanti risolve il sistema () in tempo $\Theta(n^2)$. Si può scrivere l' eq. () come

$$\begin{matrix}y_1 &&&&&&& =& b_1 \\ l_{2,1} y_1 & + & y_2 &&&&& =... ...& + & l_{n,2} y_2 & + & l_{n,3} y_3 & + \dots + & y_n & = & b_n \\ \end{matrix}$$ (2.21)

$y_{1}$ si trova direttamente dalla prima equazione del sistema, una volta trovato $y_1$ si sostituisce nella seconda equazione ottenendo $y_2$. In generale, sostituendo $y_1, \dots, y_{i-1}$ in avanti nella $i$-esima equazione si trova $y_i$.

$$y_i = b_i - \sum_{j = 1}^{i-1} l_{i,j}y_j$$ (2.22)

La sostituzione a ritroso è analoga alla sostituzione in avanti, con l' unica differenza che viene risolta prima l' $n$-esima equazione, poi si opera a ritroso fino alla prima equazione. Questo metodo serve per risolvere le equazioni di tipo (). Riscrivendo il sistema come

$$\begin{split}u_{1,1}x_1 + u_{1,2}x_1 + \cdots + u_{1,n-1}x_n ... ...+ u_{2,n}x_n &= y_2\\ & \vdots\\ u_{n,n}x_n & = y_n \end{split}$$ (2.23)

si possono calcolare $x_n, x_{n-1}, \cdots, x_1$ una dopo l' altra come segue:

$$\begin{split}x_n & = y_n / u_{n,n}\\ x_{n-1} & = (y_{n-1} - u... ...n-1}x_{n-1} + u_{n-2,n}x_n))/u_{n-2,n-2}\\ & \vdots \end{split}$$ (2.24)

La formula generale è la seguente:

$$x_i = \left ( y_i - \sum_{j = i+1}^n u_{i,j}x_j \right ) / u_{i,i}.$$ (2.25)

Entrambi i metodi, implicito e esplicito, vengono implementati nella funzione LUsolve() spiegata nel paragrafo .