• Iterative methods
• Polynomial
• Root-finding

Il calcolo degli zeri di un polinomio è uno dei più antichi problemi della matematica. Il problema, nella sua più semplice forma, può essere enunciato come segue: dato un polinomio
$$ p(x)=\sum_{i=0}^d a_i x^i, \qquad a_d\neq 0, $$
dove gli $a_i \ i=0,\dots,d $ sono numeri complessi, determinare i valori delle sue radici $x_1,\dots, x_d$.
In analisi numerica, la ricerca delle radici di un polinomio diventa il problema di trovare delle approssimazioni
per gli zeri $x_1 \dots, x_d$ con un errore relativo non più grande di una data precisione $\varepsilon>0$.
Più precisamente, data una tolleranza $\varepsilon>0$, si ricercano delle approssimazioni $y_1,\dots, y_d$ per cui
\begin{equation}
\label{eq1}
|x_i-y_i|<\varepsilon |x_i| \qquad i=1,\dots,d.
\end{equation}
Sono stati introdotti ed implementati molti algoritmi per risolvere il problema della ricerca delle radici di un polinomio.
Questi metodi si basano su risultati di diversa tipologia, sia teorici che pratici, da vari campi della matematica.
La maniera con cui si utilizzano i teoremi per risolvere il problema, conduce a differenti tipi di approccio algoritmico.
Dal punto di vista astratto ci sono alcuni risultati interessanti, che forniscono condizioni e modalità che assicurano di trovare tutte le radici di un polinomio. Purtroppo questi teoremi astratti sono difficili da sfruttare in pratica: la garanzia della risoluzione del problema non tiene conto degli elevati costi computazionali per attuarla, specialmente se il grado $d$ del polinomio è grande. Per questo una loro implementazione risulta di scarso interesse.
Esistono metodi che affrontano il problema da un punto di vista più pratico. Tra questi ve ne sono alcuni che forniscono una soluzione al problema con un ridotto costo computazionale. Ad esempio in \cite{becker2018near} viene riportato un algoritmo dalla complessità quasi ottimale per la ricerca delle radici di un polinomio ed inoltre viene presentata una sua parziale implementazione. Tuttavia spesso l'obiettivo di raggiungere un costo computazionale ottimale non tiene conto delle difficoltà implementative e delle problematiche dovute all'amplificazione dell'errore per la mancanza di stabilità numerica.
Molti degli algoritmi che sono stati implementati e che vengono usati in pratica, spesso non fanno affidamento su teoremi elaborati, ma su sperimentazioni pratiche; sono in genere privi di risultati che garantiscano una bassa complessità computazionale e piuttosto si appoggiano ad approcci euristici. La loro velocità di convergenza è nota in pratica, ma spesso è difficile trovare un risultato teorico che la certifichi.
Un esempio di questo tipo di approccio è fornito dai metodi iterativi, come le iterazioni di suddivisione, metodo di Ehrlich-Aberth, le iterazioni di Weierstrass e anche dal più semplice metodo di Newton. Per questa classe di algoritmi esistono risultati di convergenza locale, ma risulta difficile ed improbabile trovare proprietà di convergenza globale.
Molti algoritmi per la ricerca di zeri di un polinomio si basano su quest'ultima classe di metodi. Tra questi si trova MPSolve (vedi \cite{bini2000design} e \cite{bini1996numerical}), che si basa sulle iterazioni di Ehrlich-Aberth e su altri strumenti, tra cui la poligonale di Newton (per determinare delle buone approssimazioni iniziali), la trasformata discreta di Fourier (FFT) e il Fast Multipole Method (FMM) (sfruttati per accelerare alcuni calcoli). Inoltre l'algoritmo MPSolve usa un'elaborata strategia per adeguare la precisione dell'aritmetica in virgola mobile ai vari calcoli che presentano differenti condizionamenti numerici; alla fine l'accuratezza del calcolo viene garantita dall'applicazione di appositi teoremi di inclusione.
Scopo del lavoro di tesi è di riportare e confrontare alcuni metodi ed algoritmi che costituiscono le componenti principali per il design e l'analisi del problema della ricerca di radici di un polinomio.
Nel primo capitolo verranno fissate le notazioni e saranno richiamati alcuni risultati e nozioni preliminari, i quali saranno utilizzati nei capitoli successivi.
Nel secondo capitolo discuteremo del problema di localizzare le radici di un polinomio in una certa regione del piano complesso fissata ed introdurremo alcuni algoritmi per testare la presenza di zeri in un disco. In particolare tratteremo gli exclusion test.
Nel terzo capitolo presenteremo 3 tra i più conosciuti metodi iterativi per la ricerca di radici di un polinomio: il metodo di Newton, le iterazioni di Weierstrass e le iterazioni di Ehrlich-Aberth. Richiameremo la loro definizione, analizzeremo la loro convergenza locale e discuteremo l'importanza della scelta delle loro approssimazioni iniziali.
Nel quarto capitolo introdurremo alcune tecniche che possono essere utilizzata per migliorare gli algoritmi per la ricerca delle radici di un polinomio.
Nell'ultimo capitolo mostreremo come gli algoritmi e le tecniche descritte possano essere usate in pratica.
In particolare forniremo una descrizione del pacchetto di MPSolve.