Esercizio su matrice e Jacobi

[feddy]

Questo è un testo di esame... Il mio problema è il punto due del compito.
$1/6((4,1,0,0,0,0),(1,4,1,0,0,0),(0,1,4,1,0,0),(...,...,...,...,...,...),(0,...,0,1,4,1),(0,0,...,0,1,4))$

1. E' vero che $||A||_2 ||A^-1||_2 <= 3 $? (ho cercato nella guida come scrivere le norma 2 e non l'ho trovato spero sia comprensibile)

2. Qual è il numero di iterazioni k per cui $||e^((k))||_2 <= 2^-12 ||e^((0))||_2 $ (parliamo sempre di norme due) avendo indicato con $e^((k))=x-x^((k))$ l'errore che si commette all'iterata k del metodo di Jacobi

3. Qual è la complessità computazionale per ogni iterazione del metodo di Jacobi applicato ad A?

---------------------------------
Il punto 1 l'ho svolto con i cerchi di Gershgorin.
Il punto 3 è semplicemente una domanda di teoria e la risposta dovrebbe essere $O(n^2/2)$
Il punto due mi sta facendo letteralmente impazzire, vi prego aiutatemi

[feddy]

Ciao Cicorita, benvenuta nel forum.

Dovresti aver visto a lezione una stima sulla norma di $e_k$. Il fatto che $A$ sia simmetrica, e che la norma richiesta sia proprio la norma-2, agevola i conti in questo caso. Alla fine, per rispondere alla domanda si tratta di risolvere una disequazione

[Cicorita]

Ciao feddy!!! Grazie mille sia per il benvenuto e sia per la risposta!
Purtroppo non abbiamo mai trattato questo argomento, tantomeno è presente nelle sue slide... Potresti essere così gentile da spiegarmelo o fornirmi del materiale dove studiarlo?
Ci tengo a precisare, che nessuno nel mio corso è riuscito a farlo per i motivi sopra citati e dalla disperazione ho chiesto qui

[feddy]

Vale che $||e_k|| \leq ||G||^k ||e_0||$ , dove $G$ è la matrice di iterazione del tuo metodo iterativo. Dimostrarlo non è difficile, basta usare ricorsivamente la definizione del metodo iterativo. Vedi ad esempio il capitolo "Risoluzione di sistemi lineari con metodi iterativi" del libro "Matematica Numerica" di Quarteroni. Oppure puoi cercare su google "convergenza metodi iterativi per sistemi lineari", ci sono sicuramente moltissime dispense su questi argomenti.

Detto cio', devi assicurarti che $$||G||^k \leq 2^{-12}$$ . Detto altrimenti, devi risolvere questa disequazione con incognita $k$, usando l'espressione esplicita di $G$

[Cicorita]

Allora, ho trovato il raggio spettrale della matrice G (che io chiamo $ N^-1P $ , che è $ 9/20$)
e ho fatto $ \rho (9/20)^k <= 2^-12 $ e lo faccio perchè la norma 2 di matrici simmetriche è il raggio spettrale.
Svolgendomi i conti, $ k>=11 $

Confermi che è tutto corretto?

Ti ringrazio infinitamente per le risposte e per il tempo dedicatomi, non immagini quanto tempo ci siamo stati dietro!

[feddy]

La disequazione finale per $k$ e' corretta, non so pero' se il raggio spettrale sia effettivamente $\frac{9}{20}$, ma e' solo un conto comunque. Potresti verificarlo empiricamente: prendi un codice che implementa Jacobi e verifica che per quella tolleranza il numero di iterazioni richieste e' effettivamente maggiore o uguale a $11$ !