[HOWTO] Loc. Zeri Funzione e Metodi Iterativi

[I/O110]

Ciao a tutti,

Sto preparando l'esame di Calcolo Numerico, ma non riesco a trovare abbastanza informazioni da poter comprendere bene la materia (ogni parte ha delle lacune), per il momento vorrei focalizzare l'attenzione sulla localizzazione delle radici di un polinomio di grado n e relativi metodi iterativi.
Al momento utilizzo questo "schema" per risolvere gli esercizi, mi sapete dire se è corretto o meno (e se mancano delle premesse importanti: "derivabilità", ecc)?
Non essendo molto pratico, scriverò passo-passo (anche le cose più ovvie) e vi sarei molto grato se mi potete correggere anche nella forma e nei particolari...

Nota che ho inserito alla fine di tutto:
Man mano che scrivevo mi sono reso conto che il materiale ce n'è, quindi ho deciso di ri-organizzare il tutto come fosse una guida; così ho anche capito meglio alcune lacune... forse ☺
Perdonatemi se non sono molto preciso nei termini e nei modi... non sono matematico ne pretendo di diventarlo, quindi vi prego davvero di aiutarmi nel poter capire al meglio questa materia, dove purtroppo ho diverse lacune nelle basi matematiche (di analisi e algebriche principalmente)... Grazie!

(descriverò mediante un esempio)

[size=125]Localizzazione delle radici di un polinomio di grado n[/size]

$f(x)=3*x^4+4*x^3-12*x^2+5$

Procedo con un piccolo studio di funzione:

1.a) Si calcola la derivata prima di $f(x)$ per capire l'andamento (dove cresce o decresce) e i punti di massimo e minimo.

$f'(x)=12x^3+12x^2-24x=12x(x^2+x-2)$

con $f'(x)>0$

$x_0=0$
$x_(1,2)=(-1+-sqrt(9))/2= 1 , -2$

1.b) Si discute il segno:

[asvg]initPicture(-5.8,5.8,-5.8,9);
noaxes();
strokewidth=2.5;
line([-5.7,5], [3,5]);
strokewidth=2;
line([-2,5.1], [-2,5]);
text([-2,5], "-2", above);
strokewidth=2;
line([0,5.1], [0,5]);
text([0,5], "0", above);
strokewidth=2;
line([1,5.1], [1,5]);
text([1,5], "1", above);

//0
strokewidth=2;
line([0,5], [0,4]);
strokewidth=1;
line([0,4], [0,1.5]);
strokewidth=2;
line([0,4],[3,4]);
marker = "dot";
path( [ [-5.7,4],[-4.56,4],[-3.42,4],[-2.28,4],[-1.14,4],[0,4] ] );
marker = "none";

//1
strokewidth=2;
line([1,5], [1,3]);
strokewidth=1;
line([1,3], [1,1.5]);
strokewidth=2;
line([1,3],[3,3]);
marker = "dot";
path( [ [-5.7,3],[-4.36,3],[-3.02,3],[-1.68,3],[-0.34,3],[1,3] ] );
marker = "none";

//-2
strokewidth=2;
line([-2,5], [-2,2]);
strokewidth=1;
line([-2,2], [-2,1.5]);
strokewidth=2;
line([-2,2],[3,2]);
marker = "dot";
path( [ [-5.7,2],[-4.96,2],[-4.22,2],[-3.48,2],[-2.74,2],[-2,2] ] );
marker = "none";

strokewidth=1;
marker = "arrow";

text([-4,0.9], "-", above);
line([-4.5,1],[-3.5,0]);
text([-1,0.9], "+", above);
line([-1.5,0],[-0.5,1]);
text([0.5,0.9], "-", above);
line([0.2,1],[0.8,0]);
text([2,0.9], "+", above);
line([1.5,0],[2.5,1]);[/asvg]
[size=75](che faticata disegnare il grafico :p)[/size]

2) Si calcola il limite di $x$ che tende a $+-\infty$ per vedere "da dove arriva e dove va" la funzione:

$lim_(x->+-\infty)f(x) = +\infty ->$ la funzione "arriva" dall'alto e "parte" verso l'alto

3) Si calcola convessità e concavità con la derivata seconda:

$f''(x)=36x^2+24x-24$
$x_(1,2)=(-24+-sqrt(4032))/72=-1.215... , 0.548...$ (che si può approssimare con $63 = sqrt(3969) < sqrt(4032) < sqrt(4096) = 64$ quindi $-11/8 < x_1 < 29/24$ e $ 13/24 < x_2 < 5/8$ - NdME il prof aveva fatto così per facilitare i conti, ma è sicuro che sia meglio? penso lo abbia fatto per facilitarli senza calcolatrice, magari con una calcolatrice sotto è un passaggio inutile.)

Ne studio il segno:

[asvg]initPicture(-5.8,5.8,-5.8,9);
noaxes();

strokewidth=2.5;
line([-5.7,5], [5.7,5]);

strokewidth=2;
line([-1.2,5.1], [-1.2,4]);
text([-1.2,5], "x1", above);
strokewidth=1;
line([-1.2,4], [-1.2,2]);

strokewidth=2;
line([0.5,5.1], [0.5,4]);
text([0.5,5], "x2", above);
strokewidth=1;
line([0.5,4],[0.5,2]);

strokewidth=2;
line([-5.7,4], [5.7,4]);
marker = "dot";
path( [ [-1.2,4],[-0.775,4],[-0.35,4],[0.075,4],[0.5,4] ] );
marker = "none";

strokewidth=1;

text([-3.5,1.5], "+", above);
arc([-4.5,1], [-2.5,1], 1.5);

text([-0.4,1.5], "-", above);
arc([0,1], [-0.8,1], 0.1);

text([2.5,1.5], "+", above);
arc([1.5,1], [3.5,1], 1.5);[/asvg]

4) Si procede con lo studio delle radici partendo dalle derivate 1° e 2° (quindi cerco le intersezioni della funzione con le ascisse):

$->$ Tra $-\infty$ e $-2$ la funzione è decrescente (derivata 1°), ma essendo $f(-2)<0$ allora esisterà in questo intervallo, un solo punto di contatto con le ascisse: $f(\alpha)=0$

$->$ Tra $-2$ e $0$ come prima, quindi $f(\beta)=0$ poiché la funzione è crescente in questo intervallo.

$->$ Tra $0$ e $1$, $f(x)$ è decrescente. Essendo $f(1)=0$ si avrà che $f(\gamma)=0$ quindi $\gamma=1 ->$ trovata la 1° soluzione.

Nota: il range $(-\infty,-2)$ si può limitare con $f(-3)>0$

Le radici sono quindi contenute nei seguenti intervalli:

$-3<\alpha<-2$
$-2<\beta<0$
$\gamma=1$

In base a questi dati si abbozza il disegno del grafico (qui preciso grazie al disegno automatico del forum):

[asvg]xmin=-3.5; xmax=3.5;
ymin=-28; ymax=6;
axes(1,5.4,"labels","grid");
stroke="blue";
plot("3*x^4+4*x^3-12*x^2+5");[/asvg]

A questo punto abbiamo localizzato gli zeri di $f(x)$ e dobbiamo trovare la molteplicità di ogni radice.

[I/O110]

[size=125]Molteplicità di una radice[/size]

Per determinare la molteplicità si calcolano k derivate fino alla prima non nulla (che non si annullano nella radice).
La $k-esima$ derivata sarà, quindi, la molteplicità:

$->$ se $f(\alpha)=0, f'(\alpha)=0, f''(\alpha)=0, ..., f^(k-1)(\alpha)=0$ e $f^k(\alpha)!=0$ la molteplicità è proprio $k$.

Quindi la prima derivata non nulla determina la molteplicità della radice.
Per quanto riguarda l'esempio di prima, le molteplicità della radici sono:

$-> \alpha$: essendo $-3 < \alpha < -2$ e $f(\alpha)=0$ e $f'(\alpha)!=0$ la molteplicità di $\alpha$ è 1 (la prima derivata non nulla è la 1°)
(Perché gli unici valori che annullano $f'$ sono 0, 1 e 2 [come visto nello studio della derivata prima fatto in precedenza] e $\alpha$ è minore di $0$, quindi $f'(\alpha)$ non si annulla mai)

$-> \beta$: essendo $-2 < \beta< 0$ e $f(\beta)=0$ e $f'(\beta)!=0$ la molteplicità di $\beta$ è 1 (la prima derivata non nulla è la 1°)
(Perché gli unici valori che annullano $f'$ sono 0, 1 e 2 [come visto nello studio della derivata prima fatto in precedenza] e $\beta$ è minore di $0$, quindi $f'(\beta)$ non si annulla mai - ragionamento analogo al precedente)

$-> \gamma$: essendo $\gamma=1$:

$f(\gamma)=3+4-12+5=0$
$f'(\gamma)=12+12-24=0$
$f''(\gamma)=36+24-24=36!=0$

La molteplicità è 2 (perchè la prima derivata in $\gamma$ diversa da $0$ è la derivata seconda)

[I/O110]

[size=125]Metodi Iterativi[/size]

Non essendo disponibili formule esplicite per la determinazione delle radici di una funzione di grado elevato, si utilizzano dei metodi iterativi per approssimare le soluzioni con un prestabilito ordine di precisione.
A partire da una approssimazione iniziale $x_0$ si costruisce una successione $x_1 , x_2 , ...$ tale che, sotto opportune ipotesi, risulta convergere alla radice cercata.

Metodo di Bisezione
È il metodo iterativo più semplice per approssimare gli zeri reali di una funzione.

Si parte dalle ipotesi del Teorema degli Zeri, e cioè che:[list=1][*:30xx5n29] $f(x)$ è continua in $[a,b] -> f in C[a,b]$[/*:m:30xx5n29]
[*:30xx5n29] $f(a)*f(b)<0$[/*:m:30xx5n29][/list:o:30xx5n29]

Quindi il metodo ammette almeno una soluzione $\alpha$ di $f(x)=0$ in $[a,b]$

Successivamente si divide l'intervallo a metà determinando in quale metà si trova la soluzione:

con $c=(a+b)/2$:[list=1][*:30xx5n29]se $f(c)*f(a) < 0 -> \alpha in (a,c) -> a_2=a, b_2=c[/*:m:30xx5n29]
[*:30xx5n29]se $f(c)*f(a) = 0 -> \alpha=c[/*:m:30xx5n29]
[*:30xx5n29]se $f(c)*f(a) > 0 -> \alpha in (c,b) -> a_2=c, b_2=b[/*:m:30xx5n29][/list:o:30xx5n29]

Il procedimento si arresta per una delle due seguenti condizione (scelte arbitrariamente):[list=1][*:30xx5n29] $|f(c_i)| <= \epsilon[/*:m:30xx5n29]
[*:30xx5n29] $|b_i - a_i| <= \epsilon[/*:m:30xx5n29][/list:o:30xx5n29]

Per quanto riguarda l'esempio con cui ho iniziato sarebbe:

$f(x)=3*x^4+4*x^3-12*x^2+5$

$\alpha$) $-3 < \alpha < -2$

Visto che:[list=1][*:30xx5n29] $f(x)$ è continua in $[a,b]$ con $a=-3$ e $b=-2$ (lo do per scontato perché non so bene come verificarlo)[/*:m:30xx5n29]
[*:30xx5n29] $f(a)*f(b) < 0$ ($-864$)[/*:m:30xx5n29][/list:o:30xx5n29]

il metodo ammette almeno una soluzione $\alpha$ di $f(x)=0$ in [-3,-2]

Scelgo $\epsilon = 0.05$ (arbitrariamente, visto che non ho un testo che me lo impone)

Infine si procede con la bisezione vera e propria:

$a_1=-3$
$b_1=-2$
$c_1=(-3+(-2))/2=-2.5$

$f(c)=-(...)/(...)$
$f(a)=+(...)$

$f(c)*f(a)=-(...) < 0$

_______________________________

$a_2=-3$
$b_2=-2.5$
$\epsilon = 0.05 < 0.5$

$c_2=(-3+(-2.5))/2=-2.75$

$f(c)=+(...)/(...)$
$f(a)=+(...)$

$f(c)*f(a)=+(...) > 0$

_______________________________

$a_3=-2.75$
$b_3=-2.5$
$\epsilon = 0.05 < 0.25$

$c_3=(-2.75+(-2.5))/2=-2.625$

$f(c)=-(...)/(...)$
$f(a)=+(...)/(...)$

$f(c)*f(a)=-(...) < 0$

_______________________________

$a_4=-2.75$
$b_4=-2.625$
$\epsilon = 0.05 < 0.125$

$c_4=(-2.75+(-2.625))/2=-2.6875$

$f(c)=-(...)/(...)$
$f(a)=+(...)$

$f(c)*f(a)=-(...) < 0$

_______________________________

$a_5=-2.75$
$b_5=-2.6875$
$\epsilon = 0.05 < 0.0625$

$c_5=(-2.75+(-2.6875))/2=-2.71875$

$f(c)=-(...)/(...)$
$f(a)=+(...)$

$f(c)*f(a)=-(...) < 0$

_______________________________

$a_6=-2.75$
$b_6=-2.71875$

$\epsilon = 0.05 > 0.03125 ->$ Mi fermo perché ho raggiunto la soglia della tolleranza $\epsilon$ prestabilita.

$\alpha$ converge a $-2.71875$ in 5 passi.

b) Per $\beta$ stesso procedimento di $\alpha$, ma con a e b iniziali, rispettivamente, -2 e 0

Per $\gamma$ non c'è bisogno di calcoli in quanto è già radice della funzione.

[I/O110]

Metodo di Newton (o Metodo delle Tangenti)

È il metodo iterativo più utilizzato in quanto converge più velocemente degli altri. Utilizza, oltre alla funzione vera e propria, anche la sua derivata; questo aumento di calcolo viene compensato da una più rapida convergenza e quindi minore "ripetitività" dei calcoli, in genere si ha una convergenza di ordine quadratico.
Questo metodo, geometricamente parlando, approssima l'intersezione delle ascisse con la retta tangente al punto $x_k$. In altre parole ad ogni iterazione si trova un $x_k$ sulle ascisse, la cui proiezione sulla funzione corrisponde ovviamente ad $f(x_k)$; la tangente a questo punto interseca le ascisse determinando il nuovo $x_k$ e così via fino al raggiungimento/superamento della tolleranza $\epsilon$.
Un buon punto da dove far partire il metodo è un estremo dell'intervallo di localizzazione delle radici del polinomio.

Quindi assumendo $f'(\alpha)!=0$ ed assegnato un valore iniziale $x_0$ il metodo di Newton ha la forma:

$x_(k+1) = x_k-(f(x_k))/(f'(x_k))$

Riguardo al solito esempio, si ha:

Fissato sempre un $\epsilon=0.05$

$f(x)=3*x^4+4*x^3-12*x^2+5$
$f'(x)=12*x^3+12*x^2-24*x=12*x*(x^2+x-2)$

$x_(k+1) = x_k-(f(x_k))/(f'(x_k)) = x_k-(3*x_k^4+4*x_k^3-12*x_k^2+5)/(12*x_k*(x_k^2+x_k-2)) = (9*x_k^4+8*x_k^3-12*x_k^2-5)/(12*x_k*(x_k^2+x_k-12))$ (Si può semplificare oltre? Non sono molto pratico in questo...)

Quindi riguardo alle localizzazioni delle radici di cui sopra:

$\alpha$) Parto da $x_0=-3$

$x_(1) = x_0-(f(x_0))/(f'(x_0)) = -3 - 32/-144 = -25/9 ~ -2.778$
$|x_1 - x_0| = |-2.778 - (-3)| = 0.222 > \epsilon$

____________________________________________________________

$x_(2) = x_1-(f(x_1))/(f'(x_1)) = -25/9 - (11560/2187)/(-23800/243) = -(286/105) ~ -2.724$
$|x_2 - x_1| = |-2.724 - (-2.778)| = 0.054 > \epsilon$

____________________________________________________________

$x_(3) = x_2-(f(x_2))/(f'(x_2)) = -286/105 - (10854551/40516875)/(-33995104/385875) = -24838223/9129120 ~ -2.721$
$|x_3 - x_2| = |-2.721 - (-2.724)| = 0.003 < \epsilon$

Mi fermo in quanto "abbondantemente" sotto alla tolleranza.

$ -> \alpha$ converge a $~ -2.721$ in 3 passi (già nel piccolo si nota il vantaggio rispetto al metodo della bisezione)

[I/O110]

Intervalli di Convergenza del Metodo di Newton

Per determinare gli intervalli di convergenza si sfrutta il teorema della Convergenza in Grande.
Mediante lo studio dei segni di $f$, $f'$, $f''$ si può facilmente determinare se un punto appartenente ad un intervallo $I$ converge in modo monotono decrescente ad $\alpha$.
In particolare, se $f'(x)!=0$ e $f(x)*f''(x)>0$ allora $x_k -> \alpha$ (tende, converge)
[asvg]initPicture(-5.8,5.8,-5.8,9);
noaxes();

strokewidth=2.5;
line([-5.7,5], [5.7,5]);

var P = -4.275;
var P2 = 4;
strokewidth=2;
text([P,5], "ɑ", above);
line([P,5.1],[P,P2]);
strokewidth=1;
line([P,P2],[P,1]);

var P = -2.85;
var P2 = 3;
strokewidth=2;
text([P,5], "-2", above);
line([P,5.1],[P,P2]);
strokewidth=1;
line([P,P2],[P,1]);

var P = -1.425;
var P2 = 2;
strokewidth=2;
text([P,5], "x1", above);
line([P,5.1],[P,P2]);
strokewidth=1;
line([P,P2],[P,1]);

var P = 0;
var P2 = 4;
strokewidth=2;
text([P,5], "ɞ", above);
line([P,5.1],[P,P2]);
strokewidth=1;
line([P,P2],[P,1]);

var P = 1.425;
var P2 = 3;
strokewidth=2;
text([P,5], "0", above);
line([P,5.1],[P,P2]);
strokewidth=1;
line([P,P2],[P,1]);

var P = 2.85;
var P2 = 2;
strokewidth=2;
text([P,5], "x2", above);
line([P,5.1],[P,P2]);
strokewidth=1;
line([P,P2],[P,1]);

var P = 4.275;
var P2 = 3;
strokewidth=2;
text([P,5], "ɣ", above);
line([P,5.1],[P,P2]);
strokewidth=1;
line([P,P2],[P,1]);

strokewidth=2;
line([-5.7,4], [-4.275,4]);
line([0,4], [5.7,4]);
strokewidth=0.5;
line([-4.275,4], [0,4]);
text([-5.9,4], "f", left);

strokewidth=2;
line([-2.85,3], [1.425,3]);
line([4.275,3], [5.7,3]);
strokewidth=0.5;
line([-5.7,3], [-2.85,3]);
line([1.425,3], [4.275,3]);
text([-5.9,3], "f¹", left);

strokewidth=2;
line([-5.7,2], [-1.425,2]);
line([2.85,2], [5.7,2]);
strokewidth=0.5;
line([-1.425,2], [2.85,2]);
text([-5.9,2], "f²", left);

strokewidth=1;
marker="arrow";
line([-5.6,0.5], [-4.4,0.5]);
text([-4.95,0.3], "f¹(x)!=0", below);
text([-4.95,-0.4], "f(x)·f²(x)>0", below);

strokewidth=1;
marker="arrow";
line([-1.3,0.5], [-0.2,0.5]);
text([-0.7125,0.3], "f¹(x)!=0", below);
text([-0.7125,-0.4], "f(x)·f²(x)>0", below);

strokewidth=1;
marker="arrow";
line([2.9,0.5], [4.1,0.5]);
text([3.56,0.3], "f¹(x)!=0", below);
text([3.56,-0.4], "f(x)·f²(x)>0", below);

strokewidth=1;
marker="arrow";
line([5.6,0.5], [4.4,0.5]);
text([5,-0.9], "f¹(x)!=0", below);
text([5,-1.6], "f(x)·f²(x)>0", below);[/asvg]

Quindi:
$->$ per $x_0 in (-\infty,\alpha)$ il metodo converge ad $\alpha$ (ad es. $x_0=-3$)
$->$ per $x_0 in (x_1,\beta)$ il metodo converge a $\beta$
$->$ per $x_0 in (x_2,\gamma)$ il metodo converge a $1$
$->$ per $x_0 in (gamma,+\infty)$ il metodo converge ad $1$

[I/O110]

Ordine di convergenza del Metodo di Newton

Per sapere grossolanamente l'ordine di convergenza del M.d.N. si può vedere la molteplicità delle radici e se:[list=a][*:3o8lffqp]$\alpha$ ha molteplicità 1 il metodo converge con ordine > 2[/*:m:3o8lffqp]
[*:3o8lffqp]$\alpha$ ha molteplicità 2 il metodo converge con ordine > 3[/*:m:3o8lffqp]
[*:3o8lffqp]e così via...[/*:m:3o8lffqp][/list:o:3o8lffqp]

In particolare si segue questo schema:

Dato $f(\alpha)=0$

[*:3o8lffqp]se $f'(\alpha)=0$ il metodo converge con ordine 1[/*:m:3o8lffqp]
[*:3o8lffqp]se $f'(\alpha)!=0$ il metodo converge con ordine $>=$ 2 (e si verifica la derivata seconda)
[*:3o8lffqp]se $f''(\alpha)!=0$ il metodo converge con ordine 2[/*:m:3o8lffqp]
[*:3o8lffqp]se $f''(\alpha)=0$ il metodo converge con ordine $>=$ 3 (e si verifica la derivata terza)
[*:3o8lffqp]e così via...[/*:m:3o8lffqp][/list:u:3o8lffqp][/*:m:3o8lffqp][/list:u:3o8lffqp][/*:m:3o8lffqp][/list:u:3o8lffqp]
Quindi stando all'esempio:

$\alpha$) $x_0$=-3

$f(x_0)=3*x_0^4+4*x_0^3-12_0*x^2+5=32!=0$
$f'(x_0)=12*x_0^3+12*x_0^2-24*x_0=-144!=0 ->$ il metodo converge con ordine $>=$ 2
$f''(x_0)=36*x_0^2+24*x_0-24=228!=0 ->$ il metodo converge con ordine $=$ 2

Questo non l'ho capito molto bene, in quanto va in contrasto con le conclusioni di prima (3 passi)...

Come faccio a trovare un intervallo in cui il metodo di Newton converge (e quindi trovare esplicitamente il punto iniziale)?

Infine dovrei fare i "Metodi di iterazione Funzionale" con relativa convergenza/ordine di convergenza... ma ho meno materiale e non ci sto capendo molto... mi sapete consigliare qualche cosa di buono online (o spiegarmeli voi)?

Grazie per l'attenzione e a presto

[I/O110]

Nessuno mi sa dire niente?