[Metodi matematici]

[w3ns]

Salve a tutti. Nello svolgere esercizi sul metodo di risoluzione di sistemi con Jacobi o Gauss-Sidel capita spesso che venga chiesto, data una matrice, per quali valori di un certo parametro questa sia definita positiva e per quali altri il metodi GS o J converga. I valori del parametro sono sempre gli stessi. Metto un esempio





Qualcuno mi può spiegare perchè?grazie

[sellacollesella]

Un metodo iterativo per la risoluzione di un sistema lineare costruisce, a partire da un vettore iniziale \(\mathbf{x}^{(0)}\), una successione di vettori \(\mathbf{x}^{(k)}\) ai quali si richiede di convergere alla soluzione esatta per \(k\to\infty\). Condizione necessaria e sufficiente affinché un metodo iterativo converga per ogni possibile scelta di \(\mathbf{x}^{(0)}\) è che il raggio spettrale della matrice di iterazione sia minore di \(1\). I metodi iterativi più classici sono quelli di Jacobi e di Gauss-Seidel, per i quali una condizione sufficiente per la convergenza è che la matrice del sistema sia a dominanza diagonale stretta per righe, oppure simmetrica e definita positiva per il metodo di Gauss-Seidel.

[w3ns]

Grazie per la risposta. Quindi se la domanda fosse la verifica della convergenza del metodo di Jacobi il calcolo della positività col criterio di Sylvester non mi sarebbe di alcun aiuto?

[sellacollesella]

Il metodo di Jacobi seppur converga ogni qual volta la matrice del sistema sia una 2x2 simmetrica e definita positiva, ciò non è garantito per matrici 3x3 o di ordine superiore, per le quali l'unica "scappatoia" sempre valida è quella concernente la dominanza diagonale stretta per righe.

[ingres]

Aggiungo qualche ulteriore considerazione, a quanto già riportato da @sellacollesella
Scritta la successione come

$x_(k+1) = P x_k + C$

La convergenza è garantita se e solo se tutti gli autovalori di $P$ hanno norma inferiore a 1, ovvero se il raggio spettrale (il valore massimo tra i moduli degli autovalori) è inferiore a 1.

Per verificare tale condizione, senza risolvere il polinomio caratteristico, si può ad es. usare il criterio di Jury https://it.wikipedia.org/wiki/Criterio_di_Jury.

Esistono poi dei risultati notevoli quali ad es. quello già riportati per cui se A è una matrice a diagonale dominante per righe allora l'algoritmo converge, oppure che se A una matrice simmetrica, non singolare con elementi principali diversi da zero allora il metodo di Gauss-Seidel è convergente se e solo se A è definita positiva. Qui puoi comunque trovare ulteriori dettagli e risultati a riguardo.

https://www.math.unipd.it/~alvise/AN_20 ... r_j_gs.pdf

https://people.dm.unipi.it/bini/Didatti ... rativi.pdf

[w3ns]

Nel caso della verifica della convergenza del criterio di Jacobi potrei imporre la dominanza stretta per righe al variare del parametro, mentre pe GS la positività stretta e la simmetria.

Grazie ad entrambi per le risposte molto esaustive!

[sellacollesella]

Nel caso della verifica della convergenza del criterio di Jacobi potrei imporre la dominanza stretta per righe

Ok, va bene.

mentre pe GS la positività stretta e la simmetria

Non è detto che sia la via migliore. Ad esempio, se consideri una matrice diagonale con \(\alpha\in\mathbb{R}\) in ogni entrata della diagonale, è chiaro che quella matrice sia simmetrica e definita positiva se \(\alpha>0\) mentre è una matrice a dominanza diagonale stretta per righe per ogni \(\alpha \ne 0\). Quindi, GS converge sicuramente per ogni \(\alpha \ne 0\).

[w3ns]

L'ultimo dubbio è: la dominanza stretta per righe è una condizione sufficiente: va bene comunque per essere sicuri della convergenza?
Ad es in questo esercizio:




la matrice $ A $ non è simmetrica, la dominanza stretta per rige mi darebbe

$ |alpha| <2 $

cioè $ alpha \in (-2,2) $

Giusto? sembra meno stringente della condizione che il prof da come risultato.

[sellacollesella]

Per risolvere un sistema lineare del tipo: \[
A\mathbf{x}=\mathbf{b}
\] possiamo fare riferimento a due semplici metodi iterativi:

• il metodo di Jacobi: \(\mathbf{x}^{(k+1)}=D^{-1}\mathbf{b}-D^{-1}(A-D)\mathbf{x}^{(k)}\);
  
  
• il metodo di Gauss-Seidel: \(\mathbf{x}^{(k+1)}=L_*^{-1}\mathbf{b}-L_*^{-1}(A-L_*)\mathbf{x}^{(k)}\);

dove \(D\) è una matrice diagonale ed \(L_*\) una matrice triangolare inferiore.


Ebbene, individuate le rispettive matrici di iterazione, ossia: \[
B_J := D^{-1}(A-D), \quad\quad\quad B_{GS} := L_*^{-1}(A-L_*)
\] condizione necessaria e sufficiente affinché convergano per ogni scelta di \(\mathbf{x}^{(0)}\) è che risulti: \[
\rho(B) < 1
\] ossia se e soltanto se gli autovalori di \(B\) hanno tutti modulo strettamente minore di \(1\).

Bada bene che tale condizione è necessaria per avere convergenza per ogni scelta di \(\mathbf{x}^{(0)}\), ma questo non vuol dire che se tale condizione non è soddisfatta allora di sicuro quei metodi non convergono, se ti va a culo ogni tanto potrebbero convergere lo stesso, solo che a nessuno piace fare le cose basandosi sulla fortuna!

Inoltre, come scritto da ingres, non è strettamente necessario calcolare gli autovalori di \(B\), bensì
si può risalire al loro modulo in modo indiretto applicando opportuni criteri, come il criterio di Jury.


D'altro canto, dato che calcolare le matrici di iterazione \(B\) potrebbe essere comunque dispendioso, specie se
i conti si fanno a mano, vi sono dei criteri che si basano direttamente sulla matrice del sistema \(A\), che però forniscono solo delle condizioni sufficienti a stabilire la convergenza per ogni scelta di \(\mathbf{x}^{(0)}\), ossia garantiscono la convergenza solo internamente a degli intervalli, mentre esternamente non danno alcuna informazione.

Un primo criterio, valido sia per il metodo di Jacobi che per il metodo di Gauss-Seidel, garantisce la convergenza per ogni scelta di \(\mathbf{x}^{(0)}\) quando \(A\) è una matrice a dominanza diagonale stretta per righe. Un secondo criterio, in generale valido solo per il metodo di Gauss-Seidel, garantisce la convergenza per ogni scelta di \(\mathbf{x}^{(0)}\) quando \(A\) è una matrice simmetrica e definita positiva.

Come già dimostrato in messaggi precedenti, non è dato sapere quale dei due criteri fornisca l'insieme di convergenza più ampio, per cui se sei interessato a ciò non ti rimane che applicarli entrambi e considerare quello più ampio. Se, invece, devi eseguire gli ordini impartiti dal vostro docente, non te ne fregherà minimamente se il criterio imposto sia il migliore o meno, esegui gli ordini e buonanotte!


Circa l'ultimo esempio da te allegato, c'è chiaramente un errore di battitura, dato che a quella matrice non essendo simmetrica non possiamo applicare il secondo criterio, quello valido solo per Gauss-Seidel. Se provi
a mettere uno zero al posto dell'uno vedrai che otterrai gli stessi e identici risultati scritti nella soluzione.

[w3ns]

Grazie mille mi sei stato di grande aiuto!