Esercizi sui metodi del punto fisso

Esercizio 8.8

Ricondurre approssimativamente la divisione ${\frac {b}{\bar {a}}}$ ${\frac {b}{\bar {a}}}$ a un'operazione di moltiplicazione, cioè scrivere ${\frac {b}{\bar {a}}}$ ${\frac {b}{\bar {a}}}$ come $b({\bar {a}})^{-1}$ $b({\bar {a}})^{-1}$ .

Poniamo ${\bar {a}}=(\mathrm {sgn} {\bar {a}}.{\bar {a}}_{1}\dots {\bar {a}}_{t})*10^{\beta }$ ${\bar {a}}=(\mathrm {sgn} {\bar {a}}.{\bar {a}}_{1}\dots {\bar {a}}_{t})*10^{\beta }$ . Sia $a=(0.a_{1}\dots a_{t})\in [0,1]$ $a=(0.a_{1}\dots a_{t})\in [0,1]$ , con

({\bar {a}})^{-1}=(\mathrm {sgn} {\bar {a}}.a^{-1})*10^{\beta }

cioè il problema si riconduce a calcolare l'inverso di un numero.
Risolvere l'equazione

ax=1

equivale a trovare gli zeri della funzione

f(x)=ax-1

. Sappiamo che

f'(x)=a

quindi

x_{k+1}=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}=x_{k}-{\frac {ax_{k}-1}{a}}=x_{k}-x_{k}+1/a=1/a

e devo fare nuovamente una divisione, quindi questa soluzione non porta al risultato desiderato.
Consideriamo quindi la funzione

f(x)={\frac {1}{ax}}-1

(che deriva dall'equazione

1/(ax)=1

). Tenendo presente che

f'(x_{k})=-{\frac {1}{ax^{2}}}

, applicando il metodo di Newton si ha:

x_{k+1}=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}

=x_{k}-{\frac {1/(ax_{k})-1}{-1/(ax_{k}^{2})}}

=x_{k}-{\frac {1-ax_{k}}{-1/(ax_{k}^{2})ax_{k}}}

=x_{k}-{\frac {1-ax_{k}}{-1/x_{k}}}

=x_{k}+(1-ax_{k})*x_{k}=2x_{k}-ax_{k}^{2}=x_{k}*(2-ax_{k})

e in questo caso ho solo moltiplicazioni.
Consideriamo quindi il metodo

x_{k+1}=x_{k}*(2-ax_{k})

dove

x_{k+1}=\phi (x_{k})

con

\phi (x)=x*(2-ax)

.

ricerca dei punti fissi:L'equazione
$x_{f}=x_{f}(2-ax_{f})$
$x_{f}=x_{f}(2-ax_{f})$
è risolta quando $x_{f}=0$ $x_{f}=0$ o $x_{f}=1/a$ $x_{f}=1/a$ .
Studio dell'ordine di convergenza: $\phi$ $\phi$ è di classe $C^{\infty }$ $C^{\infty}$ , inoltre
$\phi '=2(1-ax)\in C^{\infty }$
$\phi '=2(1-ax)\in C^{\infty }$
$\phi '(1/a)=0<1$
$\phi '(1/a)=0<1$
Allora in un intorno di $1/a$ $1/a$ il metodo converge. $\phi ''(1/a)=-2a\neq 0$ $\phi ''(1/a)=-2a\neq 0$ e $\phi ^{(n)}=0\forall n>2$ $\phi ^{(n)}=0\forall n>2$ , quindi il metodo ha ordine di convergenza 2.
Studio della convergenza nei vari casi: Disegno la $\phi (x)$ $\phi(x)$ passante per $(0,0)$ $(0,0)$ e per $(2/a,0)$ $(2/a,0)$ (è una parabola rivolta verso il basso con vertice in $(1/a,1/a)$ $(1/a,1/a)$ ) e la bisettrice del primo e del terzo quadrante.;Caso 1: $x_{0}<0$ $x_{0}<0$ . Pongo $x_{1}=\phi (x_{0})$ $x_{1}=\phi (x_{0})$ , mi sposto sulla bisettrice per recuperare l'ascissa di $x_{1}$ $x_{1}$ e risalgo sulla funzione per determinare $x_{2}=\phi (x_{1})$ $x_{2}=\phi (x_{1})$ . Itero poi il procedimento. Siccome $x>\phi (x)$ $x>\phi (x)$ ottengo una successione monotona decrescente, e divergo a $-\infty$ $-\infty$ .;Caso 2: $x_{0}=0$ $x_0=0$ . $x_{k}=0\forall k$ $x_{k}=0\forall k$ e il metodo non itera.;Caso 3: $0<x_{0}<1/a$ $0<x_{0}<1/a$ . $x_{0}\in (0,1/a)$ $x_{0}\in (0,1/a)$ implica che
$x_{k+1}=\phi (x_{k})$
$x_{k+1}=\phi (x_{k})$
$x<\phi (x)$ $x<\phi (x)$ e la successione è monotona crescente, e si ferma raggiunto il punto fisso $1/a$ $1/a$ .;Caso 4: $x_{0}\in (1/a,2/a)$ $x_{0}\in (1/a,2/a)$ . Qui la retta si trova sopra la parabola, $x>\phi (x)$ $x>\phi (x)$ e il metodo converge perché dopo la prima iterata $\phi (x_{0})$ $\phi (x_{0})$ si trova sulla parte di parabola con ordinata compresa tra $0$ $0$ e $1/a$ $1/a$ e ci si avvicina di nuovo al punto fisso.;Caso 5: $x_{0}=2/a$ $x_{0}=2/a$ , allora $x_{1}=0$ $x_{1}=0$ e non itero.;Caso 6: $x_{0}>2/a$ $x_{0}>2/a$ . Si ha divergenza, infatti $x>\phi (x)$ $x>\phi (x)$ e la successione è decrescente e diverge a $-\infty$ $-\infty$ .
Analisi dell'errore e della velocità di convergenza:
$E_{k}=x_{k}-1/a$
$E_{k}=x_{k}-1/a$
Al passo successivo
$E_{k+1}=x_{k+1}-1/a=2x_{k}-ax_{k}^{2}-1/a=-a*(x_{k}^{2}-2/ax_{k}+1/a^{2})=-a(x_{k}-1/a)^{2}=-a*E_{k}^{2}$
$E_{k+1}=x_{k+1}-1/a=2x_{k}-ax_{k}^{2}-1/a=-a*(x_{k}^{2}-2/ax_{k}+1/a^{2})=-a(x_{k}-1/a)^{2}=-a*E_{k}^{2}$
e quindi per ogni k, la riduzione dell'errore è di tipo quadratico, $p=2$ $p=2$ e $\gamma =|-a|<1$ $\gamma =|-a|<1$ . Quindi
$|E_{k+1}|=-a|E_{k}|^{2}=|a|*|e_{k}|^{2}\leq |E_{k}|^{2}$
$|E_{k+1}|=-a|E_{k}|^{2}=|a|*|e_{k}|^{2}\leq |E_{k}|^{2}$

Questo risultato si può estendere al calcolo dell'inversa di una matrice, infatti, risolve.

AX=I

X=A^{-1}I

I=X^{-1}A^{-1}

quindi

F(X)=X^{-1}A^{-1}-I

. Applico Newton a

F(x)

.

Esercizio 8.9

Dato il metodo del punto fisso

x_{k+1}=(1-a)x_{k}+1

Analizzare convergenza e velocità di convergenza.

Punti fissi: $x_{f}=(1-a)x_{f}+1$
$x_{f}=(1-a)x_{f}+1$
$x_{f}=x_{f}-ax_{f}+1$
$x_{f}=x_{f}-ax_{f}+1$
$-ax_{f}+1=0$
$-ax_{f}+1=0$
$x_{f}=1/a$
$x_{f}=1/a$
e questo è l'unico punto fisso.

Ordine di convergenza: $\phi '(x)=(1-a)$
$\phi '(x)=(1-a)$
quindi il metodo converge se $|1-a|<1$ $|1-a|<1$ , cioè
$-1<1-a<1$
$-1<1-a<1$
$1-az1,\,\longrightarrow \,a>0$
$1-az1,\,\longrightarrow \,a>0$
$-1<1-a\,\longrightarrow \,a<2$
$-1<1-a\,\longrightarrow \,a<2$
quindi il metodo converge se $a\in (0,2)$ $a\in (0,2)$ .

In particolare, se $a\neq 1$ $a\neq 1$ , l'ordine di convergenza è 1.

Analisi dell'errore

E_{k}=x_{k}-1/a

E_{k+1}=|x_{k+1}-\alpha |=f(x_{k})-\alpha =(1-a)x_{k}+1-1/a

=x_{k}-1/a-ax_{k}+1=E_{k}k-a(x_{k}-1/a)=(1-a)E_{k}

e se

|1-a|<1

l'errore si riduce.

Studio della convergenza nei vari casi

$f$ $f$ è una retta, che interseca la bisettrice del primo e terzo quadrante nel punto fisso $(1/a,1/a)$ $(1/a,1/a)$ . Inoltre la retta interseca l'asse delle ascisse nel punto $(1/(a-1),0)$ $(1/(a-1),0)$ .

il comportamento del metodo dipende dal valore di $a$ $a$ :

se $a<1$ $a<1$ , la retta ha coefficiente angolare positivo e minore di quello della bisettrice, e si ha che il metodo converge per ogni scelta di $x_{0}$ $x_0$ , infatti, se $x_{0}<1/a$ $x_{0}<1/a$ si ha $\phi (x_{k})>x_{k}$ $\phi (x_{k})>x_{k}$ e la successione è monotona crescente e limitata da $17a$ $17a$ , invece se $x_{0}>1/a$ $x_{0}>1/a$ la successione è monotona decrescente e limitata.
Se $a>1$ $a>1$ , la retta ha coefficiente angolare negativo e minore di quello della bisettrice ( $a<2$ $a<2$ ). Per ogni $x_{0}$ $x_0$ , si ha la convergenza alternata.