metodo iterativo

metodo iterativo

metodo iterativo particolare metodo numerico usato per l’implementazione della maggior parte degli algoritmi di calcolo e basato sulla → iterazione di un insieme di operazioni. È caratterizzato, quindi, dalla ripetizione di una o più operazioni elementari, regolata da un meccanismo di controllo che ne produce l’interruzione o dopo un numero stabilito di volte o al verificarsi di una data condizione. A ogni successiva iterazione del calcolo si ottengono nuovi valori delle variabili. L’utilizzo di un metodo iterativo è particolarmente utile qualora si voglia calcolare approssimativamente il valore di un’espressione che non è possibile determinare con esattezza: si determina un valore approssimato a ogni passo di calcolo e tali valori costituiscono una successione che, se convergente, fornisce valori sempre più precisi dell’espressione. In tal caso il metodo iterativo impiegato è detto convergente, così come è detto algoritmo iterativo convergente la procedura che lo realizza operativamente (→ algoritmo, convergenza di un): all’aumentare del numero di iterazioni diminuisce la differenza tra il valore esatto dell’espressione e il valore approssimato ottenuto. Se, quindi, per calcolare il valore x di un’espressione si utilizza un algoritmo iterativo convergente, si ottiene a ogni successiva iterazione un valore x_i dove l’indice i indica il numero delle iterazioni eseguite; la successione {x_i} può, dopo un certo numero di iterazioni, fornire il valore esatto di x oppure può continuare a fornire sue approssimazioni con un errore sempre minore e il valore esatto di x è

Non sempre tuttavia un metodo iterativo fornisce una successione di approssimazioni convergente; è necessario dunque distinguere i seguenti casi:

• indipendentemente dal punto iniziale di calcolo usato dal metodo iterativo, la successione delle approssimazioni converge al valore esatto: si parla allora di stabilità dell’algoritmo che realizza il metodo iterativo utilizzato. Un tipico esempio è dato dal metodo di → Gauss-Seidel per la risoluzione di un sistema di equazioni lineari;

• la successione diverge all’aumentare del numero delle iterazioni, allontanandosi sempre di più dal valore esatto;

• la successione non converge, ma non si allontana indefinitamente, oscillando perciò tra due valori. La ripetizione dei calcoli del metodo iterativo può essere interrotta attraverso un controllo dell’errore commesso a ogni passo, confrontando la differenza tra due successivi valori ottenuti, detta stima dell’errore. Infatti se si vuole ottenere un risultato con un errore di ordine di grandezza minore di 10⁻³, occorre fermare il calcolo quando la differenza tra due successivi valori ottenuti è minore di 10⁻³:

A seconda del metodo iterativo usato la convergenza può avvenire più o meno velocemente. Per esempio, per la determinazione di uno zero reale di una funzione ƒ(x), cioè di una soluzione reale dell’equazione ƒ(x) = 0, si possono utilizzare diversi metodi iterativi: tra questi, il metodo di → bisezione, il metodo delle → secanti, il metodo di → Newton (o delle tangenti). Qualora per un dato algoritmo convergente l’errore commesso a un passo di iterazione sia proporzionale a quello commesso al passo precedente, si parla di convergenza lineare del metodo iterativo (o dell’algoritmo) utilizzato; se invece, come avviene nel già citato metodo delle tangenti, l’errore è all’incirca proporzionale al quadrato dell’errore precedente, si parla di convergenza quadratica del metodo iterativo (o dell’algoritmo).

Ordine di un metodo iterativo

Un metodo iterativo a un passo si ottiene costruendo per ricorrenza la successione {x_n} mediante una formula del tipo x_n+1 = φ(x_n), a partire da un dato x₀ arbitrario (purché, talvolta, abbastanza vicino alla soluzione cercata). La convergenza della successione a una radice α dell’equazione x = φ(x) è garantita se risulta |φ′(α)| < 1. Se è φ′(α) ≠ 0, il metodo è del primo ordine, nel senso che l’errore e_n+1 è (approssimativamente) proporzionale a e_n: e_n+1 ≅ γe_n, con γ = φ′(α). Se invece φ′(α) = 0, il metodo è di ordine superiore: in particolare del secondo se e_n+1 ≅ γ(e_n)², con γ = φ″(α)/2 e tale derivata è diversa da zero.