23  Iterazioni di punto fisso

Autore/Autrice
Affiliazione

Enrico Bertolazzi

University of Trento, Department of Industrial Engineering

Vogliamo ora dare una formulazione più generale alle iterazioni del tipo Newton-Raphson1.

Definizione 23.1 (Punto fisso) Data una funzione g:\mathbb{R}\mapsto \mathbb{R}, diremo che \alpha è un punto fisso se:

\alpha = g(\alpha).

Cercare gli zeri di una funzione f(x) è equivalente a cercare i punti fissi della funzione g(x) = x-f(x).

Un modo molto naturale per cercare i punti fissi è quello di usare delle iterazioni. Ad esempio dato un punto iniziale x_0 costruendo la successione

\boxed{ x_{k+1} =g(x_k),\qquad k=1,2,\ldots } \tag{23.1}

possiamo chiederci quando la successione \{x_{i}\}_{i=0}^{\infty} è convergente e se converge a \alpha. Ad esempio lo schema di Newton~20.3 può essere messo nella forma 23.1 ponendo

g(x) = x-\dfrac{f(x)}{f'(x)},

fondamentale per lo studio di schemi iterativi della forma 23.1 è il seguente teorema:

Teorema 23.1 (Convergenza punto fisso) Sia g(x) una funzione continua e sia \alpha un suo punto fisso, cioè \alpha=g(\alpha). Sia g(x) soddisfacente la seguente condizione

\left\lvert g(x)-g(x')\right\rvert \leq L \left\lvert x-x'\right\rvert, \tag{23.2}

per ogni x, x' in un intervallo chiuso I\equiv[\alpha-\rho,\alpha+\rho], dove la costante L soddisfa:

0 \leq L < 1,

allora

  • (i)\quad Posto x_0\in I allora tutte le iterate x_k definite da 23.1 stanno in I, cioè \alpha-\rho \leq x_k \leq \alpha+\rho, \qquad k=1,2,\ldots

  • (ii)\quad (esistenza) le iterate convergono ad \alpha, \lim_{k\mapsto\infty} x_k = \alpha.

  • (iii)\quad (unicità) \alpha è l’unico punto fisso di g(x) in [\alpha-\rho,\alpha+\rho].

Dimostrazione.

  • (i)\quad basta osservare che \begin{aligned} \left\lvert\alpha-x_k\right\rvert & = \left\lvert g(\alpha)-g(x_{k-1})\right\rvert, \\ & \leq L \left\lvert\alpha-x_{k-1}\right\rvert = L \left\lvert g(\alpha)-g(x_{k-2})\right\rvert, \\ & \leq L^{2} \left\lvert\alpha-x_{k-2}\right\rvert = L^{2} \left\lvert g(\alpha)-g(x_{k-3})\right\rvert,\\ & \vdots \\ & \leq L^{k} \left\lvert\alpha-x_0\right\rvert \leq \rho, \end{aligned} \tag{23.3} e quindi x_k è nell’intervallo [\alpha-\rho,\alpha+\rho].

  • (ii)\quad sempre dalla 23.3 e dal fatto che 0\leq L<1 segue che \lim_{k\mapsto\infty}\left\lvert\alpha-x_k\right\rvert=0.

  • (iii)\quad siano \alpha e \beta due punti fissi allora dalla 23.2 abbiamo \left\lvert\alpha-\beta\right\rvert = \left\lvert g(\alpha)-g(\beta)\right\rvert \leq L \left\lvert\alpha-\beta\right\rvert < \left\lvert\alpha-\beta\right\rvert. Questa contraddizione implica che \alpha=\beta.

NotaOsservazione

Se la funzione g(x) è differenziabile, si può scrivere

\begin{aligned} g(x)-g(x') &= g'(\eta)(x-x'),\qquad \eta \in (x,x') \\ \left\lvert g(x)-g(x')\right\rvert &\leq \left\lvert g'(\eta)\right\rvert\left\lvert x-x'\right\rvert, \end{aligned}

Di conseguenza, se vale

\left\lvert g'(\zeta)\right\rvert\leq L < 1, \qquad \zeta\in [\alpha-\rho,\alpha+\rho],

dove \alpha è un punto fisso di g(x) allora per il teorema precedente le iterazioni 23.1 convergono ad \alpha.

Esempio 23.1 (Esempio) Considerando il metodo di Newton-Raphson come uno schema a punto fisso abbiamo

g(x) = x-\dfrac{f(x)}{f'(x)}, \qquad g'(x) = \dfrac{f(x)f''(x)}{(f'(x))^{2}},

Se \alpha è una radice semplice di f(x) cioè f'(\alpha)\neq 0 allora

g'(\alpha) = \dfrac{f(\alpha)f''(\alpha)}{(f'(\alpha))^{2}} = 0,

se f(x) è una funzione C^{2} allora g'(x) è continua nell’intorno di \alpha e scegliendo un intorno sufficientemente piccolo di \alpha avremo

\left\lvert g'(x)\right\rvert \leq L < 1, \qquad x\in [\alpha-\rho,\alpha+\rho]

Per il teorema precedente, lo schema di Newton-Raphson è quindi convergente, purché si parta da un’approssimazione sufficientemente vicina alla radice e la radice sia semplice.

NotaOsservazione

Se \alpha è un punto fisso di g(x) e inoltre g'(\alpha)=0 è chiaro che nella iterazione 23.1 più ci avviciniamo alla radice \alpha più piccola è la costante L e quindi l’avvicinamento al punto fisso è più rapido. Supponiamo ora che g''(x) esista e sia continua, allora sviluppando con Taylor2 attorno al punto fisso \alpha la funzione g(x) otteniamo:

g(x) = g(\alpha) + 0 + \dfrac{(x-\alpha)^{2}}{2}g''(\eta),

e da questa

\left\lvert x_{k+1}-\alpha\right\rvert = \left\lvert g(x_k)-g(\alpha)\right\rvert = \left\lvert\dfrac{(x_k-\alpha)^{2}}{2}g''(\eta_k)\right\rvert\leq \left\lvert\dfrac{g''(\eta_k)}{2}\right\rvert\left\lvert x_k-\alpha\right\rvert^{2}. \tag{23.4}

Da questa equazione segue che l’errore alla iterata successiva è proporzionale al quadrato dell’errore precedente. In tal caso diremo che il metodo è del secondo ordine. Quindi in particolare il metodo di Newton-Raphson è del secondo ordine nel caso di radici semplici.

Sia ora I\equiv [\alpha-\rho,\alpha+\rho] un intervallo in cui lo schema è convergente e

\left\lvert\dfrac{g''(x)}{2}\right\rvert \leq M, \qquad x\in I

allora dalla 23.4

\begin{aligned} \left\lvert x_k-\alpha\right\rvert & \leq M\left\lvert x_{k-1}-\alpha\right\rvert^{2}, \\ & \leq M\left( M\left\lvert x_{k-2}-\alpha\right\rvert^{2}\right)^{2}= M\cdot M^{2} \left\lvert x_{k-2}-\alpha\right\rvert^{4}, \\ & \leq M\cdot M^{2} \left( M \left\lvert x_{k-3}-\alpha\right\rvert^{2}\right)^{4} = M\cdot M^{2}\cdot M^{4} \left\lvert x_{k-3}-\alpha\right\rvert^{8}, \\ & \vdots \\ & \leq M^{1+2+4+8+\cdots+2^{k-1}} \left\lvert x_0-\alpha\right\rvert^{2^{k}}, \end{aligned}

osserviamo che 1+2+4+\cdots+2^{k-1}=2^{k}-1 e quindi

\left\lvert x_k-\alpha\right\rvert \leq \left(M\left\lvert x_0-\alpha\right\rvert\right)^{2^{k-1}}\left\lvert x_0-\alpha\right\rvert.

Scegliamo x_0 sufficientemente vicino ad \alpha in modo che

M\left\lvert x_0-\alpha\right\rvert < 1,

allora possiamo calcolare il numero di iterazioni necessarie per ridurre l’errore iniziale \left\lvert x_0-\alpha\right\rvert di ad esempio 10^{-m} ponendo

\left(M\left\lvert x_0-\alpha\right\rvert\right)^{2^{k-1}} \approx 10^{-m}, \tag{23.5}

e prendendo il logaritmo da entrambe le parti

k \approx \dfrac{1}{\log_{10}{2}}\log\left( \dfrac{m}{-\log_{10}(M\left\lvert x_0-\alpha\right\rvert)} \right),

osserviamo che sempre dalla 23.5 otteniamo

m \approx 2^{k} \log_{10}\left(1/(M\left\lvert x_0-\alpha\right\rvert)\right), \tag{23.6}

m è proporzionale al numero di cifre esatte nella approssimazione di \alpha. quindi la 23.6 significa che ad ogni iterazione un metodo al secondo ordine circa raddoppia le cifre esatte.

NotaOsservazione

Supponiamo che sia \alpha un punto fisso di g(x) e inoltre g\in C^{p} con

g'(\alpha) = g''(\alpha)= \cdots = g^{(p-1)}(\alpha) = 0,

per il teorema di Taylor

g(x) = g(\alpha) + \dfrac{(x-\alpha)^{p}}{p!}g^{(p)}(\eta),

anche qui avremo

\left\lvert x_{k+1} -\alpha\right\rvert = \left\lvert g(x_k)-g(\alpha)\right\rvert \leq \dfrac{\left\lvert g^{(p)}(\eta)\right\rvert}{p!} \left\lvert x-\alpha\right\rvert^{p}.

Da questa equazione segue che l’errore alla iterata successiva è proporzionale alla p-esima potenza dell’errore precedente. In tal caso diremo che il metodo è di ordine p.

Esempio 23.2 (Esempio) Nel metodo di Newton-Raphson se \alpha è una radice multipla di f(x) cioè

f(x) = (x-\alpha)^{n} h(x), \qquad n>1

dove h(\alpha)\neq 0 segue che

\begin{aligned} f'(x) &= n(x-\alpha)^{n-1} h(x)+(x-\alpha)^{n} h'(x) \\ f''(x) &= n(n-1)(x-\alpha)^{n-2} h(x)+2n(x-\alpha)^{n-1} h'(x)+(x-\alpha)^{n} h''(x), \end{aligned}

e di conseguenza

\begin{aligned} g'(x) &= \dfrac{f(x)f''(x)}{(f'(x))^{2}} = \dfrac{h(x)\left( n(n-1)h(x)+2n(x-\alpha) h'(x) +(x-\alpha)^{2} h''(x) \right)}{\left(nh(x)+(x-\alpha) h'(x)\right)^{2} }, \\ g'(\alpha) &= \dfrac{n(n-1)h(\alpha)^{2}}{n^{2}h(\alpha)^{2}}= 1-\dfrac{1}{n}, \end{aligned}

quindi

\left\lvert g'(\alpha) \right\rvert = 1-\dfrac{1}{n} < 1

e lo schema iterativo converge localmente anche se ora la convergenza è solo al primo ordine.

23.1 Elenco metodi numerici per zeri di funzione

Newton-Raphson

Ordine 2

\boxed{ x_{k+1} = x_k - \dfrac{f(x_k)}{f'(x_k)},\qquad k=1,2,\ldots }

Newton per radici multiple. Basta applicare Newton alla funzione F(x) = f(x)/f'(x) ottenendo:

\boxed{ x_{k+1} = x_k - \dfrac{F(x_k)}{F'(x_k)}=x_k -\dfrac{f(x_k)f'(x_k)}{f'(x_k)^2-f(x_k)f''(x_k)} ,\qquad k=1,2,\ldots }

  • R. L.Burden & J. D. Faires
    Numerical Analysis (9th ed.)
    Brooks Cole (2010)

Secanti

Ordine \dfrac{1+\sqrt{5}}{2}=1.618\ldots

\boxed{ x_{k+1} = \dfrac{f(x_k)x_{k-1}-f(x_{k-1})x_k} {f(x_k)-f(x_{k-1})}, \qquad k=1,2,\ldots }

Secanti (variante Brent)

\boxed{ x_{k+1} = x_k - \dfrac{f(x_k)}{D_k},\quad D_k=\begin{cases} \dfrac{f(x_k)-f(x_{k-1})}{x_k-x_{k-1}} & \left\lvert x_k-x_{k-1}\right\rvert > h \\ \dfrac{f(x_k)-f(x_k-h)}{h} & \left\lvert x_k-x_{k-1}\right\rvert \leq h \end{cases} \qquad k=1,2,\ldots }

Parabole tangenti

Ordine 3 (si veda Sezione 20.11)

\boxed{ x_{k+1} = x_k -2\dfrac{f(x_k)}{f'(x_k)}\bigg/ \left( 1+\sqrt{1-2\dfrac{f(x_k)f''(x_k)}{f'(x_k)^2}} \right) \qquad k=1,2,\ldots }

Da non confondere con il metodo di Müller3 (Sezione 20.10), che interpola una parabola per tre punti, non usa derivate e ha ordine \approx 1.84:

  • D. E. Müller
    A method for solving algebraic equations using an automatic computer
    Mathematical Tables and Other Aids to Computation, Vol. 10, No. 56, 208-215, (1956)

Metodo di Halley

Ordine 3

\boxed{ x_{k+1} = x_k -\dfrac{f(x_k)f'(x_k)}{f'(x_k)^2-\dfrac{1}{2}f(x_k)f''(x_k)} \qquad k=1,2,\ldots }

  • J. F. Traub4
    • Iterative Methods for the Solution of Equations*
      Prentice-Hall, 1964.

Metodo di Steffensen

Ordine 2

\boxed{ x_{k+1} = x_k -\dfrac{f(x_k)^2}{f(x_k+f(x_k))-f(x_k)} \qquad k=1,2,\ldots }

  • J. F. Steffensen5
    Remarks on Iteration
    Skandinavisk Aktuarietidskrift, 1933, 16(1), 64-72.

Metodo delle corde tangenti

\boxed{ z = x_k -\dfrac{f(x_k)}{f'(x_k)},\qquad x_{k+1} = z -\dfrac{f(z)}{f'(x_k)}, \qquad k=1,2,\ldots }

Metodo di Ostrowski

Ordine 4

\boxed{ z = x_k -\dfrac{f(x_k)}{f'(x_k)},\qquad x_{k+1} = z -\dfrac{f(z)(z-x_k)}{2f(z)-f(x_k)}, \qquad k=1,2,\ldots }

  • A. M. Ostrowski6
    Solution of equations and systems of equations
    Academic Press, New York, 1960

In sintesi

  • Ogni metodo iterativo per f(t)=0 si riscrive come t_{k+1}=g(t_k): la radice diventa un punto fisso di g.
  • Se g è una contrazione (|g'|\leq\lambda<1) in un intorno invariante, l’iterazione converge all’unico punto fisso, con errore che decade come \lambda^{k}.
  • L’ordine di convergenza è determinato dalla prima derivata non nulla di g nel punto fisso: g'(\xi)=0 dà ordine almeno due, ed è esattamente il caso di Newton.
  • |g'(\xi)|>1 rende il punto fisso repulsivo: la stessa equazione, riscritta male, produce un metodo divergente.

  1. Isaac Newton (1642-1727) e Joseph Raphson (1668 ca.-1715 ca.)↩︎

  2. Brook Taylor (1685-1731)↩︎

  3. David Eugene Muller (1924-2008)↩︎

  4. Joseph Frederick Traub (1932-2015)↩︎

  5. Johan Frederik Steffensen (1873-1961)↩︎

  6. Alexander Markowich Ostrowski (1893-1986)↩︎