• Krylov
• matrici
• precondizionamento
• saddle point problem
• sistema lineare

L'argomento di questa tesi \`e la risoluzione del \emph{saddle point problem}, o \emph{problema KKT} (Karush-Khun-Tucker). Esso consiste nella risoluzione di un sistema lineare $\mathcal{A} u=b$ in cui la matrice dei coefficienti si pu\`o partizionare come
\begin{equation}\label{PrefSist}
\mathcal{A} = \left[\begin{array}{cc} {A} & {B_1^T} \\ {B_2} & {-C} \end{array}\right],
\end{equation}
dove
$$A\in\mathbb{R}^{n\times n},\quad B_1,B_2\in\mathbb{R}^{m\times n},\quad C\in\mathbb{R}^{m\times m},\quad \textrm{con}\quad n\ge m,$$
in modo che valga \emph{almeno una} delle quattro condizioni seguenti:

\begin{center}
\begin{minipage}[]{11cm}
\begin{tabular}{ll}
C1: $A$ \`e simmetrica & C2: $H=\frac{1}{2}(A+A^T)$ \`e semidefinita positiva \\
C3: $B_1=B_2$ & C4: $C$ \`e simmetrica e semidefinita positiva.
\end{tabular}
\end{minipage}
\end{center}

L'interesse per questo problema \`e dovuto al fatto che in una gran quantit\`a di applicazioni ci si riconduce alla risoluzione di un sistema lineare della forma (\ref{PrefSist}).

Esiste un'ampia letteratura riguardante il problema (\ref{PrefSist}) in cui vengono sviluppati sia gli aspetti modellistici e applicativi sia gli aspetti teorici, algoritmici e computazionali. In questi ultimi l'accento \`e posto sul progetto e l'analisi di metodi di risoluzione dotati di elevata efficienza e adatti a trattare problemi di grandi dimensioni. Il progetto di metodi efficienti richiede l'analisi approfondita delle propriet\`a teoriche del problema per poter sfruttare a fini computazionali ogni particolare propriet\`a specifica presente nel modello matematico. La metodologia pi\`u frequentemente utilizzata per il problema KKT, grazie alla possibilit\`a di adattarsi alla struttura del problema, \`e quella del precondizionamento. Con la parola ``precondizionamento'' si indica la trasformazione del sistema lineare $\mathcal{A} u=b$ in un sistema lineare equivalente ma con propriet\`a pi\`u favorevoli alla risoluzione numerica. Questo passaggio viene solitamente effettuato tramite un matrice non singolare $\mathcal{P}$ (detta ``precondizionatore'') che permette di passare dal sistema
$$\mathcal{A} u=b$$
al sistema equivalente
\begin{equation}\label{precondizionato}
(\mathcal{P}^{-1} \mathcal{A}) u = \mathcal{P}^{-1} b.
\end{equation}

In questa tesi vengono raccolte e a trattate le diverse metodologie computazionali presenti in letteratura, assieme agli strumenti teorici necessari, per poter affrontare la risoluzione algoritmica dei problemi KKT nelle loro diverse formulazioni. Parte del nostro interesse ha riguardato anche la realizzazione software dei metodi principali studiati ed un confronto sperimentale condotto per verificare e convalidare le conclusioni scaturite dall'analisi teorica.

Il lavoro si propone come una descrizione dello stato dell'arte della ricerca sui problemi KKT con una trattazione autocontenuta degli strumenti teorici ed algoritmici di base necessari, e fornisce inoltre un confronto algoritmico sperimentale. Infatti dei principali metodi descritti \`e stata data una implementazione in linguaggio Matlab e i programmi sono stati applicati a diversi problemi di varia difficolt\`a computazionale. Di tutti i metodi trattati \`e stata data una descrizione in forma algoritmica in modo da permettere al lettore di realizzare facilmente la propria implementazione. Per i metodi che non sono stati trattati in dettaglio, perch\'e ritenuti pi\`u marginali o di limitata applicabilit\`a, abbiamo dato indicazioni bibliografiche che permettono al lettore un maggior approfondimento.

Particolare accento viene messo sui metodi di precondizionamento che costituiscono lo strumento pi\`u efficace per risolvere i problemi
KKT. Infatti nella tesi viene dedicato ampio spazio alla teoria dei sottospazi di Krylov e ai metodi associati quali il GMRES il MINRES, il gradiente coniugato con le loro propriet\`a di convergenza, i risultati classici quali il teorema di Axelsson-Lindskog e ai risultati pi\`u recenti ed avanzati.

La tesi \`e suddivisa in quattro capitoli. Il primo \`e introduttivo e contiene le definizioni, i risultati e gli algoritmi di base che saranno utili nel resto della tesi. In particolare si trattano i metodi per risolvere i sistemi lineari, in particolare i metodi di proiezione su sottospazi di Krylov, con tutte le loro propriet\`a, ma anche l'iterazione di Richardson e i metodi di Uzawa e di Arrow-Hurwicz.

Nel secondo capitolo si definisce il problema KKT e, dopo aver descritto alcuni modelli del mondo reale da cui esso scaturisce, se ne dimostrano alcune propriet\`a di struttura (ad esempio, alcune fattorizzazioni in casi particolari), quindi si passa alle propriet\`a spettrali e infine si trattano i metodi attualmente pi\`u usati per la risoluzione dei problemi KKT, con particolare attenzione ai metodi di Krylov.

Nel terzo capitolo si trattano le metodologie di precondizionamento. Si introducono e si analizzano alcuni precondizionatori per i casi pi\`u
significativi, in particolare i casi in cui valgono le propriet\`a seguenti:
\begin{center}
\begin{minipage}[]{12cm}
\begin{center}
$A$ simmetrica e definita positiva; $B_1 = B_2=B$ di rango massimo; $C = 0$.
\end{center}
\end{minipage}
\end{center}
Queste condizioni includono un'ampia classe di problemi importanti provenienti dalle applicazioni e sono trattati in letteratura in numerosi articoli. Principalmente come precondizionatori per un problema KKT si scelgono matrici $\mathcal{P}$ che abbiano la stessa struttura a blocchi della matrice $\mathcal{A}$. In particolare, dopo aver approssimato $A$ con una matrice $D$ invertibile con un basso costo computazionale, si considerano ad esempio precondizionatori {\em diagonali}, in cui
$$\mathcal{P}= \left[\begin{array}{cc} {D} & {0} \\ {0} & {B D^{-1} B^T} \end{array}\right].$$
Altri precondizionatori considerati sono quelli {\em triangolari} e quelli {\em simmetrici}. Per ogni precondizionatore considerato vengono trattate le propriet\`a sue e del relativo sistema (\ref{precondizionato}).

Nel quarto ed ultimo capitolo, infine, vengono illustrati i risultati di alcuni esperimenti numerici sugli algoritmi trattati evidenziandone pregi e difetti. I precondizionatori descritti nel terzo capitolo sono stati testati in linguaggio MATLAB 6 su alcuni problemi KKT di varia difficolt\`a. Gli esperimenti sono stati eseguiti su un calcolatore con processore Intel Pentium-M 770 (2.13Ghz) Centrino e memoria RAM 512 Mb. Per ogni problema test, per ogni algoritmo e per ogni precondizionatore sono stati riportati i tempi di esecuzione in secondi, il numero di iterazioni effettuate e l'errore di approssimazione ottenuto.

Dai risultati \`e emerso che il precondizionamento \`e sempre utile e talvolta indispensabile per risolvere questi problemi. Inoltre risulta chiaro come per avere un buon preocondizionamento si debbano coniugare buone propriet\`a computazionali di $\mathcal{P}$ con buone propriet\`a spettrali del sistema (\ref{precondizionato}): questo bilanciamento, che dipende molto dal problema concreto che si sta affrontando, \`e la parte pi\`u complessa nella costruzione dei precondizionatori.