Un sistema di equazioni lineari è un insieme di equazioni lineari la cui soluzione è un vettore incognito che soddisfa a tutte le equazioni contemporaneamente. Un sistema \( m \times n \) si presenta nel modo seguente:
$$ \begin{cases}
a_{11}x_1 + a_{12}x_2 + \ldots + a_{1n}x_n = b_1\\
a_{21}x_1 + a_{22}x_2 + \ldots + a_{2n}x_n = b_2\\
\ldots \\
a_{m1}x_1 + a_{m2}x_2 + \ldots + a_{mn}x_n = b_m\\
\end{cases}
$$
Scritto in forma matriciale il sistema si puo scrivere in forma più compatta
$$ Ax = b $$
Dove \(A\) è la matrice dei coefficienti, \(x\) il vettore incognito e \(b\) il vettore dei termini noti. In sostanza si tratta della versione vettoriale di una semplice equazione lineare di primo grado, possiamo infatti scrivere tutto nella forma per vettori colonna:
$$\small \begin{pmatrix} a_{11} \\ a_{21} \\ \ldots \\ a_{m1} \end{pmatrix} x_1 + \begin{pmatrix} a_{12} \\ a_{22} \\ \ldots \\ a_{m2} \end{pmatrix} x_2 + \ldots + \begin{pmatrix} a_{1n} \\ a_{2n} \\ \ldots \\ a_{mn} \end{pmatrix} x_n = \begin{pmatrix} b_{1} \\ b_{2} \\ \ldots \\ b_{m} \end{pmatrix} $$
Se la matrice \( A\) è invertibile, la soluzione del sistema è analitica:
$$ A^{-1}Ax = A^{-1}b $$
$$ Ix = A^{-1}b \rightarrow x = A^{-1}b $$
Se \( n = m \) il sistema è quadrato.
Vogliamo comunque risolvere numericamente un sistema lineare, per avere un procedimento computazionale in casi di sistemi con un grande numero di equazioni ed incognite.
Complessita e Regola di Cramer
Un metodo classico per risolvere un sistema quadrato analiticamente è il metodo di Cramer
$$ x_i = {detA_i \over detA} $$ dove \( |A_i|\) è il determinante della matrice ottenuta sostituendo il vettore \(b\) alla colonna i–esima e \(|A|\) il \(det(A)\). E' facile verificare che questo procedimento su \(n!\) termini del determinante, ciscuno dei quali include \(n\) prodotti per \(n+1\) incognite, ha una complessita pari a: $$ O\biggl( n!(n+1)n\biggr) $$Sistemi triangolari
Un sistema si dice triangolare superiore o triangolare inferiore, se la matrice dei coefficienti del sistema ha componenti tutte nulle sopra la sotto la diagonale principale o sotto rispettivamente. In formule (ad esempio nel caso di sistemi 3x3);
- Triangolare Inferiore (LT) \(a_{ij} = 0, j>i \) $$\begin{pmatrix} * & 0 & 0 \\ * & * & 0 \\ * & * & * \\ \end{pmatrix} $$
- Triangolare Superiore (UT) \(a_{ij} = 0, j< i \) $$\begin{pmatrix} * & * & * \\ 0 & * & *\\ 0 & 0 & * \\ \end{pmatrix} $$
