Calcolo di uno zero di una funzione
In matematica si presentano spesso problemi che richiedono di calcolare uno zero (o radice) di una funzione di variabile reale .
La risoluzione del problema dipende strettamente dalla forma della funzione : ad esempio, se essa è un polinomio o una funzione razionale esistono, per i gradi più bassi (cioè fino al quarto grado o solo in casi particolari di grado maggiore, si veda Teoria di Galois), formule che permettono di determinare in modo preciso tutti gli zeri, senza approssimazioni. In tutti gli altri casi, come ad esempio per una funzione esponenziale o trigonometrica (più in generale trascendente), a parte alcuni casi elementari risolvibili attraverso le definizioni, ma anche per un polinomio di grado maggiore di 4, non esistono metodi algebrici per ricavare con esattezza i valori degli zeri. Di questi casi si occupa la presente voce.
Per questo tipo di problema si preferisce parlare di algoritmi per la soluzione di equazioni, sottintendendo che questi metodi possono applicarsi sia ad equazioni lineari che ad equazioni non lineari. Taluni algoritmi per il calcolo di uno zero di una funzione reale possono essere direttamente generalizzati per risolvere equazioni non lineari.
Definendo il problema con un'equazione della forma , dove il parametro della funzione è un vettore -dimensionale (vedi funzione vettoriale), il problema si generalizza con la ricerca di un vettore -dimensionale che sia soluzione della suddetta equazione.
Descrizione generale
[modifica | modifica wikitesto]I metodi per calcolare in modo approssimato le radici di un'equazione (valori dell'incognita che soddisfano l'equazione) si articolano in due fasi: nella prima fase si separano le radici, ovvero si determinano gli intervalli della retta reale che contengono una sola radice dell'equazione (si può utilizzare il metodo grafico); nella seconda fase si calcola un valore approssimato della radice dell'equazione applicando uno dei metodi di seguito descritti.
Quando si sono separate le radici, ad esempio, si è trovato che la radice è compresa nell'intervallo abbiamo due valori approssimati, uno per difetto ed uno per eccesso della radice. Si tratta di restringere l'intervallo in modo da ottenere valori più approssimati, secondo una approssimazione fissata. I procedimenti sono iterativi.
Alcuni algoritmi specifici
[modifica | modifica wikitesto]Il metodo di ricerca della radice più semplice è il metodo di bisezione (metodo dicotomico / di Bolzano). Si parte conoscendo un intervallo reale che considerazioni precedenti garantiscono contenere una e una sola radice. Per esempio, dovendo ricercare una radice di una funzione continua, e saranno valori presi in maniera tale che e assumano segno opposto; infatti, per il teorema degli zeri, l'intervallo conterrà sicuramente una radice per l'equazione. Definito l'intervallo, con successive iterazioni si procede a progressivi dimezzamenti dello stesso. Alla prima iterazione si sceglie fra i sottointervalli e , dove è il punto a metà tra e , attraverso la valutazione del segno di . La convergenza del procedimento è garantita, ma è lenta in quanto ha andamento lineare. Questo metodo può essere in parte paragonato all'algoritmo di ricerca binaria dell'informatica, per la ricerca di un determinato valore all'interno di un insieme ordinato di dati. La ricerca binaria ha tuttavia andamento logaritmico, cioè molto più rapido, perché opera su interi (le posizioni degli elementi nell'insieme).
Il metodo delle tangenti (chiamato anche metodo di Newton o metodo di Newton - Raphson) si serve della approssimazione lineare (mediante la tangente) della funzione f in un intorno di una approssimazione corrente della radice. Questo porta alla relazione di ricorrenza
- .
Questo metodo potrebbe non convergere se si parte da un valore della variabile troppo lontano da una radice. Se però viene bene avviato converge più rapidamente del metodo di bisezione (la convergenza è quadratica). Inoltre questo metodo si generalizza facilmente ai problemi multidimensionali.
Se nel metodo delle tangenti si rimpiazza la derivata della funzione con una differenza finita, si ottiene il metodo delle secanti. Esso è caratterizzato dalla relazione di ricorrenza
- .
Questo metodo quindi non richiede il calcolo della derivata della funzione, ma presenta una convergenza più lenta (il suo ordine è circa 1,6).
Il metodo di falsa posizione in Fibonacci, chiamato anche metodo della regula falsi, è simile al metodo di bisezione, ma ad ogni iterazione invece di tagliare l'intervallo di appartenenza della radice in due parti uguali, lo bipartisce nel punto suggerito dalla formula del metodo delle secanti. Questo metodo eredita la robustezza del metodo della bisezione e la convergenza sovralineare del metodo delle secanti.
Applicabilità dei metodi di calcolo
[modifica | modifica wikitesto]Si noti come non tutti i metodi possono essere applicati in tutti i casi. Ad esempio, l'equazione
ha soluzione per ; se volessimo applicare il metodo della bisezione a questa equazione dovremmo innanzitutto determinare, per iniziare l'iterazione, due punti e tali che e abbiano segni opposti (vedi teorema degli zeri).
Nel caso in oggetto, qualunque valore di si prenda, il valore calcolato sarà sempre maggiore o uguale a . L'algoritmo della bisezione risulta quindi non applicabile.
Elenco dei metodi numerici
[modifica | modifica wikitesto]- Metodo della bisezione o di dicotomia
- Metodo delle tangenti o di Newton-Raphson
- Metodo delle secanti
- Metodo Regula Falsi
- Metodo di doppia falsa posizione in Fibonacci
- Metodo di Muller
- Metodo di Brent
- Metodo di Laguerre
- Iterazione di punto fisso
Bibliografia
[modifica | modifica wikitesto]- G. Poncini Le equazioni numeriche, intiere e razionali ad una incognita (Milano: U. Hoepli, 1877)
- (FR) E. Carvallo Méthode pratique pour la résolution numérique complète des équations algébriques ou transcendantes (Paris: Nony, 1896)
- (EN) E. T. Whittaker e G. Robinson The Calculus Of Observations (London: Blachie & sons, 1924) capitolo 6
- (DE) C. Runge e H. Konig Vorlesungen über numerisches Rechnen (Berlin: Springer, 1924) capitolo 6
Collegamenti esterni
[modifica | modifica wikitesto]- Animazioni delle iterazioni in diversi casi di convergenza/divergenza, su math.fullerton.edu. URL consultato l'11 marzo 2007 (archiviato dall'url originale l'11 marzo 2007).
- (EN) Calcolo delle radici complesse di un polinomio a coefficienti reali (free online solver)
- (EN) Numerical Recipes Homepage, su nr.com. URL consultato il 13 agosto 2019 (archiviato dall'url originale il 25 agosto 2018).