Metodo di Halley per la Ricerca delle Radici di un Polinomio

La ricerca degli zeri di una funzione è un problema centrale in matematica applicata e ingegneria. Esistono vari metodi per affrontare questa sfida, dal più semplice metodo della bisezione al più avanzato metodo di Newton-Raphson. In questo articolo, ci concentreremo sul metodo di Halley, un’estensione del metodo di Newton-Raphson, che presenta una convergenza più rapida sotto determinate condizioni. Dopo una presentazione teorica del metodo, forniremo un’implementazione in Python utilizzando la libreria NumPy, con particolare attenzione alla vettorizzazione per aumentare l’efficienza computazionale.

Formula del Metodo di Halley

Il metodo di Halley è definito dalla seguente formula iterativa:

$$x_{n+1}=x_n-\frac{2f(x_n)f^{\prime }(x_n)}{2[f^{\prime }(x_n){]}^2-f(x_n)f^{″}(x_n)}$$

Il metodo di Halley utilizza un’approssimazione della funzione $f(x)$ basata sulla sua serie di Taylor troncata al secondo ordine:

$f(x)\approx f(x_n)+f^{\prime }(x_n)(x-x_n)+\frac{f^{″}(x_n)}{2}(x-x_n{)}^2$

Risolvendo per $x$ quando $f(x)$ è approssimato a zero, otteniamo la formula iterativa del metodo di Halley.

La forza di Python risiede nella sua ampia gamma di librerie di supporto. In questo caso, useremo NumPy per la manipolazione di array e per l’implementazione vettorizzata del nostro algoritmo.

Ecco un estratto del codice Python che implementa il metodo di Halley:

import numpy as np
import matplotlib.pyplot as plt
import matplotlib.colors as colors

# Generazione del polinomio
p = np.polynomial.Polynomial(np.random.choice([-1., 1., 1.j, -1.j], 30))
dp = p.deriv()
ddp = dp.deriv()

def halley_method(z):
    return z - p(z) / (dp(z) - ddp(z) * p(z) / (2 * dp(z))), z

Dettagli dell’Implementazione

1. Generazione del Polinomio: Utilizziamo la classe Polynomial di NumPy per generare un polinomio con coefficienti casuali.

2. Calcolo delle Derivate: dp e ddp sono le prime e seconde derivate del polinomio. NumPy fornisce un metodo deriv() per questo scopo.

3. Metodo di Halley Vettorizzato: La funzione halley_method(z) implementa il metodo di Halley in modo vettorizzato. Grazie a NumPy, l’operazione viene eseguita su ogni elemento dell’array z simultaneamente.

La vettorizzazione è un concetto chiave per migliorare l’efficienza. Invece di utilizzare un ciclo per applicare la formula di Halley a ciascun punto, operiamo su tutto l’array z contemporaneamente. Questo è possibile perché NumPy è ottimizzato per eseguire operazioni vettorizzate in modo efficiente.

Il metodo di Halley, in conclusione, offre un modo efficace per trovare gli zeri di una funzione con una velocità di convergenza generalmente superiore a quella del metodo di Newton-Raphson, a costo di una maggiore complessità computazionale dovuta al calcolo della seconda derivata. L’implementazione in Python sfrutta la potenza della vettorizzazione tramite NumPy, offrendo un codice sia efficiente che conciso.

L’immagine generata dal codice rappresenta una visualizzazione delle radici del polinomio in questione nel piano complesso. In particolare, l’immagine è costruita usando il metodo di Halley per trovare le radici, e il colore di ciascun punto nel piano complesso è determinato dal numero di iterazioni necessarie per arrivare a una soluzione approssimata entro una certa tolleranza.

In termini tecnici:

• L’asse x rappresenta la parte reale del numero complesso, mentre l’asse y rappresenta la parte immaginaria.

• Ogni punto del piano complesso inizia con un valore iniziale (z), che è iterativamente aggiornato usando il metodo di Halley fino a quando non si raggiunge una soluzione approssimata o si supera un numero massimo di iterazioni.

• Il colore del punto rappresenta il numero di iterazioni effettuate. Un colore che rappresenta un numero minore di iterazioni indica che il punto iniziale era più vicino a una radice del polinomio. In altre parole, regioni dell’immagine con colori simili sono vicine alla stessa radice del polinomio.

In pratica, questa visualizzazione fornisce un modo intuitivo per vedere dove si trovano le radici di un polinomio nel piano complesso e come la convergenza al valore della radice varia a seconda del punto di partenza. Essa può fornire intuizioni utili sulla distribuzione delle radici e sulla robustezza del metodo di Halley nel trovare tali radici da diverse condizioni iniziali.