Commenti sulla Formula Bellia

I commenti che seguono si basano sulle fonti seguenti: Ritengo non corretto mettere a disposizione via rete il programma ed i documenti in "word", che possono essere richiesti direttamente all'autore.

Dall'analisi abbastanza dettagliata di tali fonti emerge che la ricerca delle radici si basa su successive traslazioni orizzontali dell'equazione, p(x) = 0 allo scopo di portare una radice a coincidere con l'origine.

L'entità della traslazione è data dal rapporto tra i coefficienti di grado zero e di grado uno, in altre parole è p(0)/p'(0). È quindi chiaro che si tratta di un passo dell'algoritmo di Newton a partire da x0 = 0.

In definitiva l'algoritmo di Bellia coincide esattamente con l'algoritmo di Newton con valore di innesco 0. La differenza consiste solo nel fatto che invece di spostare l'approssimazione della soluzione, viene traslata l'intera equazione.

Trattandosi dell'algoritmo di Newton, valgono esattamente le stesse considerazioni riguardo ai risultati di convergenza ed alla velocità di convergenza:

  1. Ci si può scordare di avere convergenza in un numero finito di passi, in generale.
  2. La convergenza è garantita solo partendo abbastanza vicino alla radice e sotto opportune condizioni sulla radice (se non è semplice le cose si complicano).
  3. La velocità di convergenza (in caso di convergenza) è quadratica, cioè il numero di cifre corrette nella soluzione raddoppiano (all'incirca) ad ogni iterazione. Si tratta in effetti di un metodo molto efficiente.

Ci sono però differenze per quanto riguarda l'algoritmo. Me ne vengono in mente due:

  1. Il costo computazionale di un passo di Newton coincide con il numero di operazioni necessarie per il calcolo del valore del polinomio e della sua derivata in un punto dato. Utilizzando lo schema di Hörner (a mia conoscenza il più efficiente, per polinomi scritti in forma di potenze), sono richieste n moltiplicazini per il valore del polinomio ed n-1 per la sua derivata, e altrettante somme/sottrazioni. Utilizzando una osservazione astuta non è nemmeno necessario calcolare i coefficienti di p', cosa che comunque potrebbe essere fatta una volta per tutte. Il calcolo della traslazione di Bellia, richiede invece il calcolo del valore di tutte le derivate del polinomio in un generico punto. Anche se fatto in modo astuto, tale calcolo richiede, mi pare, n(n+1)/2 moltiplicazioni (contro le 2n-1 di Newton classico).
  2. In secondo luogo, il calcolo delle traslazioni introduce un errore nell'equazione del polinomio traslato, dovuto all'errore di arrotondamento nell'aritmetica del computer. Questo errore rischia di accumularsi al procedere del processo iterativo.

Nella descrizione dell'algoritmo di Bellia non viene MAI detto che la ricerca della (prima) radice consiste in un processo iterativo, e cioè che se ci si ferma dopo un numero finito di passi si ha inevitabilmente un errore. Anzi, nell'algoritmo si dice: "vediamo, ad ogni traslazione, che la funzione tende ad avvicinarsi all'origine degli assi fino a passarvi,...", lasciando intendere "errore zero dopo un numero finito di passi". Naturalmente non c'è alcun cenno ad un test di arresto, o al numero di iterazioni effettuate. Men che meno ci sono dimostrazioni di convergenza.

Come per l'algoritmo di Newton, per l'algoritmo di Bellia la convergenza non è affatto garantita, essendo fissato a priori il valore di innesco. In effetti non è garantito che l'algoritmo di Bellia trovi tutte le soluzioni reali, anche nel caso in cui queste siano tutte semplici e ben separate. Un esempio (trovato per caso) è l'equazione x5 - x - 1, la cui unica radice reale non viene trovata. In questo caso l'algoritmo di Newton a partire da 0 converge ad un'orbita di ordine 3, che non ha niente a che vedere con la radice e l'algoritmo di Bellia restituisce uno dei tre punti dell'orbita.

Infine è evidente che l'eseguibile fornito da Bellia non corrisponde esattamente all'algoritmo descritto, visto che non si pianta (e in molti casi funziona) anche per polinomi con derivata nulla nell'origine, che produrrebbero quindi una divisione per zero nell'algoritmo descritto. È quindi chiaro che ci sono delle aggiunte successive allo scopo di far funzionare il programma nel maggior numero di casi possibile.

Tanto per fare un confronto, per quanto riguarda le radici reali di un polinomio un algoritmo molto usato è quello basato sulle successioni di Sturm.

Se il polinomio in questione ha solo radici semplici (utilizzando un algoritmo basato sulla divisione di Archimede si può ricondurre qualunque polinomio a coefficienti razionali a questa situazione), è possibile costruire una successione di polinomi di grado via via decrescente (successione di Sturm) la cui valutazione in due punti generici a e b permette di sapere con esattezza quante radici sono comprese nell'intervallo (a,b).

È a questo punto facile isolare ciascuna radice con un metodo tipo bisezione in un numero finito di passi, e poi procedere in ciascun intervallo con un metodo a piacere (ad esempio Newton).

MP