Metodo iterativo

Enciclopedia della Matematica (2013)

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 xi dove l’indice i indica il numero delle iterazioni eseguite; la successione {xi} 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 è

formula

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−3, occorre fermare il calcolo quando la differenza tra due successivi valori ottenuti è minore di 10−3:

formula

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 {xn} mediante una formula del tipo xn+1 = φ(xn), a partire da un dato x0 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 en+1 è (approssimativamente) proporzionale a en: en+1 ≅ γen, con γ = φ′(α). Se invece φ′(α) = 0, il metodo è di ordine superiore: in particolare del secondo se en+1 ≅ γ(en)2, con γ = φ″(α)/2 e tale derivata è diversa da zero.

TAG

Sistema di equazioni lineari

Metodo di → gauss-seidel

Metodo delle → secanti

Metodo di → bisezione

Metodo delle tangenti