8. Zeri di equazioni non lineari

Definizione del problema

Data $f : (a, b) \to R$ si affronta il problema di determinare eventuali $α \in (a, b)$ tali che $f (α) = 0$ . Per evitare che l'algoritmo oscilli tra una soluzione e l'altra, si restringe la ricerca in sottointervalli in cui è presente un solo zero. Partendo da una guess iniziale, l'algoritmo iterativo genera una successione di soluzioni che (si spera) convergano alla soluzione reale. I metodi possono essere chiusi (bracketing methods), ovvero si richiede un intervallo su cui cercare la soluzione, oppure aperti, che possono divergere ma sono generalmente più veloci.

Ordine di convergenza

Un metodo si dice di ordine $p$ se, detta $α$ la radice ed ${x_{n}}$ la successione di soluzioni, si ha: $∣ x_{n + 1} - α ∣ \leq c ∣ x_{n} - α ∣^{p}$ Dove $c < 1$ è detto fattore di convergenza. Se $p = 1$ la convergenza si dice lineare.

Criteri di terminazione

In un metodo iterativo, per decidere quando terminare i calcoli si può stimare l'errore relativo: $∣ E_{r} ∣ = \frac{x _{a tt} - x _{p rec}}{x _{a tt}}$ Ci si ferma quando $∣ E_{r} ∣ < a cc u r a t ezz a$ .

Metodi chiusi

Si richiedono due valori $a$ e $b$ e si ricerca la soluzione $α \in [a, b]$ . Tutti i metodi chiusi, ad eccezione del metodo di bisezione, sono ricavati trovando una pendenza $q_{k}$ di una retta passante per il punto $(x_{k}, f (x_{k}))$ , la cui intersezione con l'asse $x$ fornisce il punto successivo, $x_{k + 1}$ .

Metodo di bisezione

Svantaggio: metodo lento.

Sia $f \in C [a, b]$ tale che $f (a) \cdot f (b) < 0$ , per il teorema di esistenza degli zeri si dimostra che $\exists s \in] a, b [: f (s) = 0$ Valutiamo la funzione $f$ in $x_{1}$ punto medio, ovvero $\frac{a + b}{2}$ e sia $f (x_{1}) \neq = 0$ . Poniamo $x_{0} = a$ e supponiamo che $f (x_{0}) \cdot f (x_{1}) < 0$ . Allora $\exists s \in] x_{0}, x_{1} [: f (s) = 0$ Poniamo $x_{2} = \frac{x _{0} + x _{1}}{2}$ . Iterando tale procedimento $n$ volte, la radice (se non ancora trovata) sarà contenuta in un intervallo di lunghezza $\frac{b - a}{2 ^{n}}$ Quindi l'errore commesso nel considerare $x_{n}$ come radice è $∣ e_{n} ∣ \leq h^{n} (b - a) h = \frac{1}{2}$ E si commette quando la radice è dall'altra parte dell'intervallo. Il metodo di bisezione ha generalmente convergenza lineare dato che: $∣ e_{n + 1} ∣ \leq h ∣ e_{n} ∣$

Metodo della falsa posizione (regula falsi)

Il metodo della falsa posizione divide iterativamente l'intervallo come fatto dal metodo di bisezione, ma sfrutta le informazioni date dai valori della $f$ per determinare la soluzione successiva. Supponiamo di essere tra $a$ e $b$ , calcoliamo $f (a)$ ed $f (b)$ , dopodiché tracciamo la retta $r$ che passa tra i punti $A = (a, f (a))$ e $B = (b, f (b))$ $r : \frac{y - f ( b )}{f ( a ) - f ( b )} = \frac{x - b}{a - b}$ Ponendo $y = 0$ troviamo l'intersezione con l'asse $x$ : $x_{1} = \frac{a \cdot f ( b ) - b \cdot f ( a )}{f ( b ) - f ( a )}$ Si sostituisce $a$ o $b$ con $x_{1}$ a seconda se è $a$ o $b$ ad avere la $f$ con lo stesso segno di $f (x_{1})$ . In generale quindi si ha: $x_{n + 1} = \frac{x _{n - 1} \cdot f ( x _{n} ) - x _{n} \cdot f ( x _{n - 1} )}{f ( x _{n} ) - f ( x _{n - 1} )}$ Il rate di convergenza è lineare.

Metodo delle corde

Se anziché determinare la pendenza della retta ad ogni iterazione, ponessimo la pendenza costante $q = \frac{f ( b ) - f ( a )}{b - a}$ E determinassimo la retta che passa da $(x_{k}, f (x_{k}))$ con pendenza $q$ per determinare $x_{k + 1}$ , allora avremmo il metodo delle corde. Le rette di iterazioni successive sono parallele tra loro.

$\includegraphics[width=0.75\textwidth]{secantif_e.eps}$

Metodi di punto fisso

Dato il problema principale di trovare $α : f (α) = 0$ , si costruisce una funzione ausiliaria $g$ tale che $g (α) = α$ , ovvero tale che $α$ è un punto fisso di $g$ . La costruzione non è unica, può essere fatta in molteplici modi. Per trovare il punto fisso di $g$ che corrisponde allo zero di $f$ si sfrutta il teorema del punto fisso.

Teorema del punto fisso

Sia $g ([a, b]) \subseteq [a, b]$ ed inoltre valga che $\forall x, y \in [a, b] \Rightarrow ∣ g (x) - g (y) ∣ \leq k ∣ x - y ∣ 0 < k < 1$ Una funzione $g$ con tale proprietà è detta contrazione (il più piccolo $k$ per cui vale tale relazione è detto costante di Lipschitz). Allora vale che:

Esiste unico un punto fisso $α : g (α) = α$
Per ogni $x_{0} \in [a, b]$ , se $x_{n + 1} = g (x_{n})$ allora la successione ${x_{n}} \to α$ tende al punto fisso
Per l'errore vale che $∣ α - x_{n} ∣ \leq \frac{k ^{n}}{1 - k} (x_{1} - x_{0})$

Spiegazione:

Esiste un unico punto fisso
La successione definita converge al punto fisso
L'errore sarà minore uguale di un valore proporzionale all'errore commesso all'inizio $x_{1} - x_{0}$ . La costante di proporzionalità dipende dal fattore $k$ .

Significato geometrico del teorema

La successione di soluzioni è $x_{n + 1} = g (x_{n})$ In pratica la successione si collega ad ogni iterazione alla retta bisettrice e determina il punto successivo. Abbiamo 4 casi possibili, mostrati nella figura in alto, che variano a seconda del valore della derivata $g^{'} (α)$ nel punto fisso $α$ . Vediamoli:

[alto a sx] Funzione crescente e concava $\to$ l'algoritmo converge a gradini
[alto a dx] Funzione decrescente e convessa $\to$ l'algoritmo converge a spirale
[basso a sx] Funzione crescente e convessa $\to$ l'algoritmo diverge a gradini
[basso a dx] Funzione decrescente e concava $\to$ l'algoritmo diverge a spirale

Velocità di convergenza del punto fisso

Sotto le ipotesi:

$g \in C^{k + 1} [a, b]$
$x^{*} = g (x^{*})$
$e_{n} = x_{n} - x^{*}$
$g (x_{n}) = x_{n + 1}$

Osserviamo che l'errore: $e_{n + 1} = x_{n + 1} - x^{*} = g (x_{n}) - g (x^{*}) (espandiamo entrambe) = g^{'} (x^{*}) (x_{n} - x^{*}) + g^{''} (x^{*}) \frac{( x _{n} - x ^{*} ) ^{2}}{2} + \dots + g^{(k)} (x^{*}) \frac{( x _{n} - x ^{*} ) ^{k}}{k !} + O (k + 1)$ Se $g^{'} (x^{*}) \neq = 0$ (quindi non si arriva al punto fisso con pendenza nulla) allora si ha: $e_{n + 1} = g^{'} (ξ_{n}) e_{n}$ Dove $ξ_{n} \in] x_{n}, x^{*} [$ ed essendo $g^{'}$ continua in $x^{*}$ per ipotesi, abbiamo: $n \to \infty lim \frac{e _{n + 1}}{e _{n}} = g^{'} (x^{*})$ Tale rate di convergenza è detto lineare.

Se g'(x^)=0 \and g''(x^) \ne 0 allora $n \to \infty lim \frac{e _{n + 1}}{e _{n}^{2}} = \frac{g ^{''} ( x ^{*} )}{2}$ Tale rate di convergenza è detto quadratico.

In generale: più derivate si annullano in $x^{*}$ , più veloce è il metodo.

Il termine a destra del limite $\frac{g ^{(k + 1)} ( x ^{*} )}{( k + 1 )!}$ è detto fattore asintotico di convergenza.

Numero di iterazioni

Il numero di iterazioni $r$ da eseguire affinché l'errore sia minore di $1 0^{- m} e_{n - 1}$ è calcolato come segue.

Siano

$E_{0}$ l'errore iniziale
$E_{r}$ l'errore dopo $r$ iterazioni

Sia $C = \frac{∣ e _{n} ∣}{∣ e _{n - 1} ∣ ^{p}}$ Tramite vari passaggi si può dimostrare che: $∣ E_{r} ∣ \approx {C^{r} ∣ E_{0} ∣ C^{(p^{r} - 1) / (p - 1)} ∣ E_{0} ∣^{p^{r}} p = 1 p > 1$ Da cui si può ricavare $r$ (per semplicità ricaviamo solo per $p = 1$ ) $r \geq \frac{m}{- lo g C}$

Metodo di Newton o delle tangenti

Se $q_{k} = f^{'} (x^{(k)})$ si ha il metodo di Newton. Consideriamo la tangente alla $f (x)$ nel punto $(x_{0}, f (x_{0}))$ $y - f (x_{0}) = f^{'} (x_{0}) (x - x_{0})$ E sia $f^{'} (x_{0}) \neq = 0$ . Il successivo punto $x_{1}$ sia dato dalla intersezione della retta tangente con l'asse $x$ $x_{1} = x_{0} = \frac{f ( x _{0} )}{f ^{'} ( x _{0} )}$ Ripetendo iterativamente si ha: $x_{n + 1} = x_{n} - \frac{f ( x _{n} )}{f ^{'} ( x _{n} )}$ Con $f^{'} (x_{n}) \neq = 0$ . Se la radice è semplice, il metodo è quadratico.

Metodo di Newton come metodo di punto fisso

Se vogliamo trovare uno zero di $f$ attraverso il metodo del punto fisso, una scelta comune per la funzione ausiliare $g$ è $g (x) = x + c f (x)$ Con $c \neq = 0$ , cosicché quando troviamo $α : f (α) = 0$ allora $g (α) = α$ . Abbiamo visto che il metodo del punto fisso è tanto più veloce quante più derivate si annullano nel punto fisso. Se deriviamo la $g$ otteniamo: $g^{'} (x) = 1 + c f^{'} (x)$ La derivata prima di $g$ si annulla sul punto fisso $α$ ad una condizione $g^{'} (α) = 0 ⟺ c = - \frac{1}{f ^{'} ( α )}$ A questo punto poniamo genericamente: $g (x) g^{'} (x) = x + h (x) f (x) = 1 + h^{'} (x) f (x) + h (x) f^{'} (x)$ Calcoliamo la derivata prima $g^{'}$ su $α$ ricordando che $f (α) = 0$ $g^{'} (α) = 1 + h (α) f^{'} (α)$ La derivata si annulla su $α$ se e solo se $h (α) = - \frac{1}{f ^{'} ( α )}$ Quindi sostituiamo la funzione $h$ in $g$ : $g (x) = x + h (x) f (x) ⟹ g (x) = x - \frac{f ( x )}{f ^{'} ( x )}$ Dato che l'aggiornamento della soluzione nel metodo del punto fisso è $x_{n + 1} = g (x_{n})$ , allora: $x_{n + 1} = x_{n} - \frac{f ( x _{n} )}{f ^{'} ( x _{n} )}$ Che è esattamente il metodo di Newton.

Radici multiple

Se lo zero che stiamo trovando ha una molteplicità $p > 1$ allora la convergenza del metodo non è quadratica, bensì ma lineare. Ponendo però $x_{n + 1} = x_{n} - p \frac{f ( x _{n} )}{f ^{'} ( x _{n} )}$ Il metodo torna ad essere quadratico (scarsa utilità, spesso non si conosce la molteplicità della radice).

Metodo delle secanti

Deriva dalla difficolta di calcolare la derivata di $f$ nel metodo di Newton.

La pendenza $q_{k}$ è data dal rapporto incrementale anziché dalla derivata: $q_{k} = \frac{f ( x _{k} ) - f ( x _{k - 1} )}{x _{k} - x _{k - 1}}$ Sostituendo la tangente con la secante si ha un metodo più lento ma meno complesso. L'aggiornamento è quindi: $x_{n + 1} = x_{n} - f (x_{n}) \frac{x _{n} - x _{n - 1}}{f ( x _{n} ) - f ( x _{n - 1} )}$ Da cui: $x_{n + 1} = \frac{f ( x _{n} ) x _{n - 1} - f ( x _{n - 1} ) x _{n}}{f ( x _{n} ) - f ( x _{n - 1} )}$ Poiché $x_{n + 1}$ dipende esplicitamente da $x_{n}$ ed $x_{n - 1}$ non è né una iterazione del punto fisso, né un metodo chiuso (non è richiesto il cambio di segno di $f$ ). Tale metodo può divergere. La sua convergenza è superlineare, ovvero l'ordine di convergenza è compreso tra 1 e 2. Risulta più veloce del metodo di bisezione, ma meno veloce del metodo di Newton.

Secanti contro Newton

Il metodo delle secanti è più veloce del metodo di Newton se la frazione di tempo del calcolo della derivata $f^{'}$ è maggiore del 44% del tempo di calcolo della $f$ .

NumericalAnalysis