Criteri di arresto per metodi iterativi stazionari, alcuni dubbi?

[Moralizzatore]

Salve gente, oggi (in realtà in parte anche ieri) mi sono ritrovato ad affrontare il problema dei criteri di arresto per i metodi iterativi stazionari per la risoluzione di sistemi lineari, per intenderci i metodi di Jacobi e Gauss-Seidel (quelli più moderni sono trascurati). Se nella parte di teoria, e anche nella applicazione pratica mi ci sono trovato bene, il mio libro è pessimo quando si tratta di affrontare l'argomento da cui proviene il titolo. Riporto, andando a memoria dal mio studio, quello che ho appreso:

$\cdot \text{ Salvaguardia}:$ Conviene fissare un tetto massimo di iterazioni, cioè prevedere un controllo del tipo $k < k_{\text{max}}$. Questo non garantisce in nessun modo la vicinanza dell'iterata $x_k$ alla soluzione esatta $x$ del sistema, ma permette di non rimanere intrappolati in un loop infinito nel caso in cui il particolare sistema a cui il metodo viene applicato non converga comunque si scelga la approssimazione iniziale della soluzione, e questa sia stata scelta con scarsa cura (magari a caso), e permette anche di porre rimedio ad una scelta sconsiderata delle tolleranze per i rimanenti criteri di arresto. Ad esempio se una o più tolleranze vengono scelte più piccole di $\epsilon_m$ (precisione di macchina) si avrebbe l'assurda pretesa di fermare il procedimento quando si raggiunge una accuratezza più alta rispetto a quella con cui si memorizzano i dati, che non permetterebbe mai al metodo di fermarsi.

$\cdot \text{ Residuo piccolo}:$ Un altra idea potrebbe essere quella di interrompere il metodo nel momento in cui il residuo, definito come $r = Ax_k - b$ è prossimo allo zero, dove con questo si intende dire che è minore di una data tolleranza, più grande di $\epsilon_m$ e fissata a priori o data dall'utente, e di realizzare dunque un controllo del tipo

\(\begin{Vmatrix} Ax_k - b \end{Vmatrix} < \text{t}_r\begin{Vmatrix} b \end{Vmatrix} + \text{t}_a\).

Questo tipo di controllo consiste in un ibrido tra un controllo sul residuo relativo ed assoluto; infatti se \(\begin{Vmatrix} b \end{Vmatrix}\) è piccolo il termine \(\text{t}_r\begin{Vmatrix} b \end{Vmatrix}\) diviene trascurabile e l'unica parte significativa rimane $\text{t}_a$, rendendo il confronto di fatto, un controllo sul residuo assoluto. Viceversa se \(\begin{Vmatrix} b \end{Vmatrix}\) è grande $\text{t}_a$ diventa ininfluente e il controllo equivale a quello sul residuo relativo.

Il difetto di questo tipo di criterio risiede nel fatto che un residuo piccolo da solo non riesce a garantire da solo che l'errore sia piccolo. Infatti si potrebbe avere che $Ax_k$ è vicino a $b$ anche se $x_k$ è lontano dalla soluzione effettiva del sistema. Per rendersi conto di quando è conveniente utilizzare questo criterio ripropongo la seguente relazione (che ho compreso e so dimostrare):

[size=150]\(\frac{1}{\text{k(A)}}\frac{\begin{Vmatrix} r \end{Vmatrix}}{\begin{Vmatrix} b \end{Vmatrix}} \leq \frac{\begin{Vmatrix}e \end{Vmatrix}}{\begin{Vmatrix} x \end{Vmatrix}} \leq \text{k(A)}\frac{\begin{Vmatrix} r \end{Vmatrix}}{\begin{Vmatrix} b \end{Vmatrix}} \)[/size]

A questo punto, ricordando di aver definito \(\begin{Vmatrix} e \end{Vmatrix} = \begin{Vmatrix} x_k-x \end{Vmatrix}\) si ha che quando il criterio è soddisfatto (supponendo $\text{t}_a = 0$ ) vale la seguente relazione:

[size=150]\(\frac{\begin{Vmatrix}x_k-x \end{Vmatrix}}{\begin{Vmatrix} x \end{Vmatrix}} \leq \text{k(A)}\text{t}_r \)[/size]

da cui si deduce che l'affidabilità di questo criterio dipende sia dalla scelta della tolleranza che dal condizionamento del sistema. Conviene allora usarlo quando si sa di lavorare con problemi ben condizionati.

$\cdot \text{ Vicinanza tra iterate}:$ Si può pensare di arrestare il metodo nel caso che due iterate siano vicine tra di loro più di una certa tolleranza fissata e maggiore della accuratezza di macchina. Il fatto che due iterate successive siano vicine tra loro può essere sintomo che il metodo sta convergendo alla soluzione, come può anche essere sintomo del fatto che, invece, il metodo sta convergendo con lentezza. Il controllo si presenta nella forma, ibrida come nel caso precedente,

\( \begin{Vmatrix} x_k - x_{k-1} \end{Vmatrix} < \text{t}_r\begin{Vmatrix} x_{k-1} \end{Vmatrix} + \text{t}_a \)

Dopo un bel po' di calcoli che vi risparmio, si raggiunge questa conclusione:

[size=150]\(\begin{Vmatrix} e_k \end{Vmatrix} \leq \frac{\begin{Vmatrix}M \end{Vmatrix}}{1 - \begin{Vmatrix} M \end{Vmatrix}}\begin{Vmatrix} x_k - x_{k-1} \end{Vmatrix}\) [/size].

Supponendo il criterio soddisfatto, e per semplicità $\text{t}_r = 0$ si giunge alla seguente conclusione (<< non capisco perché):

[size=150]\(\begin{Vmatrix} e_k \end{Vmatrix} \leq \frac{\begin{Vmatrix}M \end{Vmatrix}}{1 - \begin{Vmatrix} M \end{Vmatrix}}\text{t}_a\) [/size].

dalla quale si evince facilmente che, affinché questo criterio sia efficace, è necessario che \(\begin{Vmatrix} M\end{Vmatrix} < \frac{1}{2}\) e cioè il denominatore sia più grande del denominatore. Se questo non avviene $x_k$ può distare dalla soluzione più di $\text{t}_a$, e questa distanza aumenta all'avvicinarsi di \(\begin{Vmatrix} M\end{Vmatrix}\) a $1$ (infatti il denominatore tenderebbe a 0 e la frazione a $+oo$.

A questo punto vi propongo i mie dubbi:

Come si arriva a definire in quel modo i criteri di arresto per gli ultimi due? Nel senso, a me verrebbe di verificare ad esempio il fatto che il residuo sia piccolo richiedendo che una delle sue norme sia più piccola di una data tolleranza, ad esempio:

\(\begin{Vmatrix} Ax_k - b \end{Vmatrix} < \text{t}_r\)

Il libro non fornisce alcuna spiegazione su come si arrivi a questa forma ma ne dà solamente una giustificazione...
Che vantaggio fornisce impiegare un controllo che funge sia da relativo che assoluto?

Inoltre, come si passa dalla penultima relazione nello spoiler all'ultima?

Grazie!

[Raptorista1]

Ciao, puoi specificare più chiaramente quali formule non hai capito?

[Moralizzatore]

Semplicemente non mi è chiaro come si arriva a dire che \(\begin{Vmatrix}Ax-b\end{Vmatrix} < t_r\begin{Vmatrix}b\end{Vmatrix}+t_a\). Nel senso che constatare la sua correttezza in casi particolari mi torna facile. Non mi è invece immediato immaginarmi che qualcuno si sia svegliato dal sonno partorendo questa formula a caso e constatando che "funzionava". Sono interessato a capire come nasce questa formulazione.

[Raptorista1]

È il classico concetto di errore assoluto e relativo: è tanto un errore di un millimetro? Se stai misurando un raggio atomico, sì; se stai misurando la distanza terra-sole, no. Il primo pezzo è importante quando \(b\) è grande in norma, e ti dice esattamente questo.

[Moralizzatore]

Su questo c'ero: il modo in cui funziona mi è chiaro. Se all'esame mi viene chiesto di esporre i criteri di arresto mi sembra semplicemente brutto spiattellare in faccia la formula e spiegare perché è così. Il mio approccio tipicamente è invece costruttivo, cioè arrivo alla formula spiegando le motivazioni che portano a costruirla così e non in altri modi. È questo che mi interesserebbe capire.

[Raptorista1]

Sicuramente ci sono altri modi possibili - e validi. Secondo me ti stai arrovellando il cervello per niente: è un criterio d'arresto, si sceglie arbitrariamente con un po' di buon senso.
Una soluzione è buona quando il residuo è "piccolo". Però di nuovo se \(||b||\) è grande può essere troppo restrittivo che il residuo sia minore di un numero piccolo scelto da te, cioè
\[
||Ax-b|| \le t_a.
\]
È allora meglio chiedere che il residuo normalizzato sia minore di un numero piccolo scelto da te, cioè
\[
\frac{||Ax-b||}{||b||} \le t_r.
\]

Un modo di mettere insieme le due cose è il criterio con la somma delle due, che tenta di essere una cosa che va bene più o meno in tutti i casi.