Metodo di eliminazione Gaussiana, Jacobi e Gauss-Seidel

Prima di postare leggi le regole del Forum. Puoi anche leggere le ultime discussioni.

Metodo di eliminazione Gaussiana, Jacobi e Gauss-Seidel #224

avt
thejunker
Frattale
Ciao ragazzi, ho una domanda sul metodo di eliminazione gaussiana e una domanda sul metodo numerico di Jacobi e sul metodo di Gauss-Seidel.

Assegnato il sistema lineare Ax=b

A=\left[\begin{matrix} 3 & -2 & 0 \\ -1 & 3 & 0 \\ 0 & -1 & 3 \end{matrix}\right]\ \ \ b=\left[\begin{matrix}1 \\ 2 \\ 2 \end{matrix}\right]

Calcolare la soluzione del sistema lineare usando il metodo di eliminazione gaussiana con pivoting parziale e scrivere la fattorizzazione PA=LU.

2) Senza effetuare calcoli, stabilire se i metodi di Jacobi e Gauss-Seidel applicati al sistema convergono e in caso di risposta affermativa determinare quale dei due metodi converge più velocemente. Motivare le risposte.

Grazie cari emt
 
 

Metodo di eliminazione Gaussiana, Jacobi e Gauss-Seidel #227

avt
Omega
Amministratore
Ciao Thejunker, il metodo di eliminazione gaussiana prevede di riscrivere la matrice del sistema lineare in forma di matrice triangolare superiore. Lo scopo si raggiunge sostituendo alle equazioni del sistema lineare opportune combinazioni lineari delle equazioni che vi compaiono.

Così facendo infatti si passa ad un sistema equivalente, a patto di modificare, secondo la stessa ratio, anche gli elementi del termine noto b del sistema lineare.

Ax=b


In pratica: per raggiungere la forma triangolare superiore, dobbiamo eliminare (da qui la terminologia eliminazione gaussiana) al primo passo i termini a_{2,1}\mbox{ }a_{3,1} della matrice, al secondo passo il termine \overline{a}_{3,2} della matrice ottenuta al primo passo. L'ho indicato così perché chiaramente dopo il primo passo ottieni una nuova matrice...

Come fare? Ragioniamo sugli elementi che vogliamo eliminare. Per azzerare a_{2,1} sostituiamo alla seconda riga:

II-\frac{a_{2,1}}{a_{1,1}}I

Dove II e I indicano rispettivamente la seconda e la prima equazione. Se è chiaro che così facendo il termine a_{2,1} si elimina, sarà anche chiaro che sostituire la terza equazione con

III-\frac{a_{3,1}}{a_{1,1}}I

eliminerà il termine a_{3,1} della terza riga. Questo in linea generale, qui il termine a_{3,1} è già nullo, dunque, possiamo agire solamente sulla seconda equazione e passare al sistema lineare equivalente:

\left[\begin{matrix}3\mbox{ }-2\mbox{ }0\\0\mbox{ }\frac{7}{3}\mbox{ }0 \\0\mbox{ }-1\mbox{ }3\end{matrix}\right]\left[\begin{matrix}x_{1}\\x_{2}\\x_{3}\end{matrix}\right]=\left[\begin{matrix}1\\\frac{7}{3}\\2\end{matrix}\right]

Ora sostituiamo la terza equazione con

III-\frac{\overline{a}_{3,2}}{\overline{a}_{2,2}II}


Dove II e III sono risp. la seconda e la terza equazione del nuovo sistema lineare. Troviamo

\left[\begin{matrix}3\mbox{ }-2\mbox{ }0\\0\mbox{ }\frac{7}{3}\mbox{ }0 \\0\mbox{ }0\mbox{ }3\end{matrix}\right]\left[\begin{matrix}x_{1}\\x_{2}\\x_{3}\end{matrix}\right]=\left[\begin{matrix}1\\\frac{7}{3}\\3\end{matrix}\right]

Siamo così arrivati alla forma triangolare superiore. Ora possiamo trovare agilmente la soluzione del sistema lineare con un paio di calcoli, cominciando dal basso. Abbiamo che

\left[\begin{matrix}1\\1\\1\end{matrix}\right]


è la soluzione del sistema lineare. Per la fattorizzazione PA=LU, dove L e U stanno per Lower e upper (triangolari inferiore e superiore, risp.) e P è una opportuna matrice di permutazione (che scambia le righe di A in modo da far tornare la fattorizzazione).

Tieni conto che vale un'altra evidentissima regola: scambiare due righe, ovvero equazioni, di un sistema lineare produce un sistema lineare equivalente. Nell'eliminazione si scambiano righe quando si trovano righe con pivot nullo, e si "manda" in basso la riga con l'elemento pivotale nullo (per non trovarsi a dividere per zero).

Come troviamo le matrici? Nella procedura di eliminazione non abbiamo effettuato mai permutazioni, dunque P=I(3) è l'identità rispetto al prodotto riga per colonna. Ci manca la triangolare inferiore!

Questa è semplicemente la matrice con elementi diagonali pari ad uno, elementi nulli sopra la diagonale e elementi sotto la diagonale dati da:

l_{i,j} con i>j


pari al moltiplicatore relativo alla riga i-esima al passo j-esimo. Nel nostro caso:

L\left[\begin{matrix}1\mbox{ }0\mbox{ }0\\-\frac{1}{3}\mbox{ }1\mbox{ }0 \\0\mbox{ }-\frac{3}{7}\mbox{ }1\end{matrix}\right]

Fine della prima richiesta. La seconda richiesta trova risposta nel criterio di convergenza: nei metodi iterativi si ha convergenza alla soluzione se il raggio spettrale della matrice di iterazione, vale a dire il massimo in valore assoluto degli autovalori della matrice di iterazione, è più piccolo di 1.

In alternativa, se ti è più comodo (e qui direi proprio di sì!) ti basta sapere che il metodo di Jacobi come quello di Gauss-Seidel convergono se la matrice di partenza è a diagonale dominante, ossia se per ogni i

|a_{i,i}|>\sum_{j=1,j\neq i}^{n}{|a_{i,j}|}


fatto che qui è indubbiamente verificato!

Provata la convergenza, ti basta sapere che per matrici tridiagonali il metodo di Gauss-Seidel è più veloce di quello di Jacobi, fatto che è vero in generale, ma che nel caso di matrici tridiagonali è sempre verificato.
Ringraziano: thejunker, Fylax
  • Pagina:
  • 1
Os