La risoluzione numerica delle equazioni¶

Sappiamo risolvere alcuni tipi di equazioni: quelle algebriche di 1° e 2° grado e alcune equazioni fondamentali trascendenti: con funzioni circolari, esponenziali, logaritmiche. Sappiamo anche che per molte equazioni non esiste una formula risolutiva, come avviene per le equazioni di 2° grado. In questo capitolo impareremo alcune tecniche che consentono di affrontare con successo equazioni di ogni tipo, che altrimenti sarebbero non risolvibili.

Iniziamo da un’equazione algebrica di 3° grado: $x^3-8x+1=0$ . Sappiamo che può avere al massimo tre soluzioni. Ma siamo sicuri che esista una soluzione? Su questo possiamo essere sicuri. Consideriamo infatti la funzione $f(x)=x^3-8x+1$ . Risolvere l’equazione significa cercare gli zeri della funzione e possiamo affermare con certezza che almeno uno zero esiste perché la funzione è continua, è asintoticamente indistinguibile da $x^3$ e, essendo negativa per $x$ infinito negativo e positiva per $x$ infinito positivo, non può che annullarsi per almeno un valore di $x$ .

$f(x)=x^3-8x+1$

Il primo modo per risolvere è quello tutto tecnologico. Visualizzando il grafico della funzione si vede che ci sono tre intersezioni con l’asse $x$ . Basta allora ingrandire opportunamente la scala orizzontale e si trovano approssimativamente le soluzioni: una soluzione pari a circa $-2.9$ , un’altra è circa $0.1$ e l’ultima circa $2.8$ . Anche le calcolatrici moderne danno un valido aiuto, basta immettere, oltre alla funzione, anche l’intervallo entro il quale ci si aspetta la soluzione: per esempio la soluzione compresa fra 2 e 3, calcolata in questo modo, fornisce il valore $2.76372382$ .

Questo sistema, comodo e efficace, non è sempre usabile. Pur ammettendo l’uso della calcolatrice, abbiamo comunque bisogno di stimare quali siano gli intervalli all’interno dei quali cercare le soluzioni e non è detto che, una volta tracciato il grafico, ci sia facile osservare il piano nei punti giusti e al giusto ingrandimento.

Se si opera solo con carta e matita, una prima ricerca degli intervalli che contengono una soluzione si può fare spezzando la funzione in due: $f(x)=x^3-8x+1=g(x)-h(x)$ , con $g(x)=x^3\mbox{ e } h(x)=8x-1$ . In questo modo $f(x)=0$ diventa $g(x)=h(x)$ , cioé $x^3=8x-1$ . Scritta così, l’equazione chiede di cercare i valori di $x$ per i quali le due funzioni $h(x)\mbox{ e }g(x)$ sono uguali. I grafici delle due funzioni possono essere tracciati anche a mano

$h(x)=g(x)\ \to \ x^3=8x-1$

Si vede bene che fra 0 e 1 c’è un’intersezione e poi si intuisce che ne esistono altre due perché la cubica si impenna più rapidamente della retta. A mano si costruisce una tabella per verificare in quali intervalli i valori di una funzione scavalchino l’altra.

x	h(x)	g(x)
2	8	15
3	27	23
-2	-8	-17
-3	-27	-25

Poiché negli intervalli fra 2 e 3 e fra -2 e -3 i valori di una funzione superano i valori dell’altra, sicuramente in questi intervalli vi sarà almeno un valore di $x$ che rende le due funzioni uguali.

Note

In un caso semplice come questo, si può anche evitare di spezzare $f(x)$ in due funzioni. La tabella allora serve a evidenziare in quali intervalli la funzione cambia i suoi valori, da positivi a negativi o viceversa.

Il metodo dicotomico¶

A questo punto cerchiamo di migliorare la precisione, cioè individuiamo intervalli più stretti nei quali cercare le soluzioni. Un modo facile è spezzare in due gli intervalli precedenti: per esempio invece di $[2,3]$ utilizziamo $[2,2.5]$ e $[2.5,3]$ . Con una tabella simile alla precedente possiamo verificare che la soluzione è contenuta nel secondo dei due intervalli. Allora agiremo (con la calcolatrice) su $[2.5,3]$ allo stesso modo, cioè dividendolo per il suo punto medio e verificando i risultati con la tabella. Ogni volta la precisione aumenterà e potremo ripetere il procedimento a piacere, fermandoci quando avremo raggiunto il grado di precisione desiderato, cioè quando l’ampiezza dell’ultimo intervallo sarà minore dell’errore prefissato.

Tutta questa serie di operazioni sempre uguali definisce l’algoritmo dicotomico, così detto perché gli intervalli vengono ogni volta spezzati in due. L’algoritmo si può anche descrivere con un linguaggio di programmazione:

inizio

leggi 
ripeti
se 
allora 
altrimenti 
fino a che 
scrivi 

fine

Nel listato si prevede che la funzione sia già data. Il controllo sulla differenza di segno agli estremi dell’intervallo avviene moltiplicando i valori (quinta riga). $e$ è l’errore massimo consentito.

L’algoritmo dicotomico restringe progressivamente l’intervallo in cui si trova la soluzione. Fissato il massimo errore accettabile, possiamo restringere l’intervallo fino a farlo diventare più piccolo di questo errore. Se ripetiamo infinite volte l’algoritmo, gli estremi arriveranno ad appartenere alla sua monade dello zero della funzione e quindi la parte standard di un estremo è lo zero della funzione. Modificando leggermente il programma possiamo stampare i valori degli estremi dell’intervallo e osservare così come quest’ultimo si restringe attorno ad un valore che possiamo considerare lo zero della funzione a meno di un errore prefissato. Ricordiamo che la funzione era definita a parte e l’errore massimo previsto era $10^{-8}$ .

k	$a_k$	$b_k$
0	2	3
1	2.5	3
2	2.75	3
3	2.75	2.875
4	2.75	2.78125
5	2.75	2.765625
6	2.75	2.765625
7	2.7578125	2.765625
8	2.76171875	2.765625
9	2.76367187	2.765625
10	2.76367187	2.76464884
...	...	...
25	2.76372379	2.76372382
26	2.76372381	2.76372382
27	2.76372382	2.76372382

Come si vede, in 27 cicli, l’algoritmo ha racchiuso la soluzione in un intervallo i cui estremi sono passati dal differire di una unità al differire meno di un centomilionesimo.

È possibile stabilire a priori quante iterazioni occorre fare per ridurre l’intervallo a un’ampiezza minore dell’errore $e$ prefissato, infatti ad ogni passo l’intervallo viene dimezzato e quindi, dopo $n$ iterazioni, l’ampiezza è diventata: $\frac{b-a}{2^n}$ . Si tratta allora di determinare il più piccolo valore di $n$ per cui $\frac{b-a}{2^n} \le e$ . Risolvendo la disequazione abbiamo: $2^n \ge \frac{b-a}{e}$ e $n \ge \log_2 \frac{b-a}{e}$

Applicando la formula al caso dell’equazione cubica che abbiamo appena risolto otteniamo $n \ge \log_2 {\frac{b-a}{e}}=\log_2 {\frac{1}{10^{-8}}}=\log_2 {10^8}= \approx 27$

Per riassumere la sequenza delle operazioni:

1. Si separano le soluzioni, cioè si definisce per ogni soluzione un intervallo che la contenga. Questo si fa per via grafica, cercando le intersezioni del grafico con l’asse $x$ . Spesso è comodo riscrivere la funzione come uguaglianza fra due altre funzioni e cercare i punti di ascissa che corrispondono alle intersezioni fra i loro due grafici.

2. Individuati gli intervalli, si applica l’algoritmo dicotomico, controllando che agli estremi dell’intervallo $f(x)$ abbia segno diverso, oppure che $g(x)$ e $h(x)$ nell’intervallo “si scavalchino”.

$f(x)=0$ oppure $g(x)=h(x)$

Tutto ciò si basa su due premesse: la funzione deve essere continua e deve assumere valori di segno opposto agli estremi di ogni intervallo. Lo precisiamo nel prossimo teorema.

Teorema degli zeri di una funzione continua¶

Il procedimento del metodo dicotomico può essere esteso infinitamente, individuando intervalli sempre più piccoli. In questo modo si giunge a dimostrare un’importante proprietà delle funzioni continue.

Se $[a,b]$ , con $a<b$ , è l’intervallo da suddividere, le divisioni successive generano due successioni di estremi $\left \langle a_k \right \rangle$ e $\left \langle b_k \right \rangle$ , la prima non decrescente e la seconda non crescente. L’ampiezza del k_esimo intervallo sarà $b_k-a_k=\frac{b-a}{2^k}$ . Le due successioni sono monotone e limitate, quindi convergenti, e all’infinito vale $b_N-a_N=\frac{b-a}{2^N}\approx 0$ , cioè la differenza fra i due termini diventa infinitesima e quindi essi appartengono alla stessa monade e individuano lo stesso numero standard che chiameremo $\overline {x}$ .

Immaginiamo $f(a)<0$ e $f(b)>0$ (ma il ragionamento non cambia nel caso contrario); grazie al nostro algoritmo avremo per ogni $k$ : $f(a_k)\le 0$ e $f(b_k)\ge 0$ , che vale ovviamente anche con indici infiniti. Quindi $f(a_N)\le 0$ e $f(b_N)\ge 0$ . Ma abbiamo visto che $a_N\approx \overline{x}\approx b_N$ . Qui entra in gioco la continuità della funzione, per cui $a_N\approx \overline{x} \to f(a_N)\approx f(\overline{x})\le 0$ e $b_N\approx \overline{x} \to f(b_N)\approx f(\overline{x})\ge 0$ . Non potendo essere contemporaneamente maggiore e minore di zero, $f(\overline{x})=0$ .

Il Teorema degli zeri quindi assicura che una funzione continua nell’intervallo $[a,b]$ , che assume valori di segno diverso agli estremi, ha certamente almeno uno zero in un punto interno all’intervallo.

Note

Si potrebbe dare una dimostrazione analoga anche nel caso che $f(x)$ venga spezzata in due funzioni $f(x)=h(x)-g(x)$ , ma preferiamo cogliere l’occasione per approfondire il discorso sulle funzioni continue e pervenire in modo diverso allo stesso risultato.

Proprietà delle funzioni continue¶

Se due funzioni $f(x),\ g(x)$ sono continue nel punto $c$ , allora è continua in $c$ anche la loro somma, la loro differenza, il loro prodotto e il loro quoziente, purché esista in $c$ . Quindi vale:

Se per $x\approx c \to f(x)\approx f(c) \mbox{ e } g(x)\approx g(c)$ , allora sempre per $x\approx c$

$&f(x)\pm g(x)\approx f(c)\pm g(c)\\ &f(x)g(x)\approx f(c)g(c)\\ &\frac{f(x)}{g(x)}\approx \frac{f(c)}{g(c)}$

Queste proprietà sono intuitive e discendono direttamente dalle proprietà della parte standard di un iperreale. Infatti $c=st(x)$ perché è standard e $x\approx c$ . $f(c)$ è standard e $f(x)\approx f(c)$ , allora $f(c)=st[f(x)]$ .

La continuità in $c$ si può anche esprimere dicendo che $f[st(x)]=st[f(x)]$ .

In riferimento alla nota precedente, la continuità della differenza consente di dimostrare il Teorema degli zeri anche nella versione in cui $f(x)=g(x)-h(x)$ .

Il metodo delle tangenti¶

Nel suddividere l’intervallo $[a,b]$ alla ricerca dello zero della funzione, il metodo delle tangenti è più efficiente del metodo dicotomico, cioè raggiunge l’obiettivo più rapidamente. L’idea è di sostituire al grafico della funzione la sua tangente in un punto $c$ vicino alla soluzione $\overline{x}$ . L’intersezione della tangente con l’asse $x$ determina il valore $a_k$ , oppure $b_k$ , che restringe l’intervallo $[a,b]$ attorno a $\overline{x}$ .

L’equazione della tangente in $c$ è data dal Polinomio di Taylor del primo ordine, sviluppato per $x=\overline{x}$ :

$f(\overline{x})=f(c)+f'(c)(\overline{x}-c)$

Poiché $x=\overline{x}$ è lo zero della funzione, $f(\overline{x})=0$ quindi si ricava il valore (approssimato al primo ordine)

$\overline{x}=c-\frac{f(c)}{f'(c)}$

Il metodo delle tangenti

Come si vede da questo primo disegno, non è detto che la posizione di $c$ garantisca che la tangente intersechi l’asse orizzontale in modo da restringere l’intervallo $[a,b]$ . Perché questo avvenga occorre controllare che il grafico della funzione in tutto $[a,b]$ abbia la stessa concavità. Esaminiamo i quattro casi possibili:

L’intervallo attorno a $\overline{x}$ si restringe se le tangenti successive partono da un grafico con la concavità dello stesso tipo.

Questi quattro grafici appartengono a funzioni che hanno

valori di segno diverso agli estremi dell’intervallo
monotone
concave sempre verso l’alto o sempre verso il basso.

La prima condizione è necessaria perché esista almeno una soluzione (Teorema degli zeri), la seconda perché la soluzione sia unica (stiamo cercando di separare le soluzioni e ci occupiamo solo di $[a,b]$ ), la terza perché le tangenti successive restringano l’intervallo approssimando la soluzione.

Ragioniamo sul primo disegno in fig.16.5, come esempio: la prima tangente è tracciata in $B(b_0,f(b_0))$ e, a causa della concavità, intercetta l’asse delle ascisse in un punto $b_1$ più vicino alla soluzione, e così avverrà con le tangenti successive, che restringeranno l’intervallo unicamente da destra.

Iterando il procedimento, si definisce una successione $\left\langle b_k \right\rangle$ decrescente, con

$b_{k+1}=b_k-\frac{f(b_k)}{f'(b_k)}$

È una successione monotona e limitata, che converge a un numero standard $s$ . Per le proprietà viste sulle funzioni continue, se prendiamo le parti standard, abbiamo

$st\left(b_{k+1}\right)=st\left(b_k-\frac{f(b_k)}{f'(b_k)}\right)\ \to\ s=s-\frac{f(s)}{f'(s)}$

da cui $f(s)=0\ \to\ s=\overline{x}$ .

Gli altri casi della figura 16.5 si trattano in modo analogo, perché le formule date per $b_{k+1}$ valgono anche per $a_{k+1}$ . Ma come scegliere quale fomula sviluppare, cioé le tangenti vanno tracciate a partire da $a$ o da $b$ ? Se la concavità è rivolta verso l’alto sceglieremo l’estremo con ordinata positiva, altrimenti quello con ordinata negativa.

E come faremo a controllare dove si rivolge la concavità? Qui interviene una regola che svilupperemo più avanti: se la derivata seconda è positiva nell’intervallo dato, allora la concavità è rivolta verso l’alto, altrimenti è rivolta verso il basso.

Dunque i controlli preliminari da effettuare prima di applicare il metodo delle tangenti sono:

Il segno agli estremi dell’intervallo: deve essere diverso.
La monotonia: $f'(x)$ costantemente positiva o negativa.
La concavità: $f^{''}(x)$ costantemente positiva o negativa.
La scelta dell’estremo a cui applicare l’algoritmo, in base ai punti 1. e 3.

Un esempio¶

Applichiamo il metodo delle tangenti alla funzione già usata nel paragrafo del metodo dicotomico: $f(x)=x^3-8x+1$ , anche qui per cercare la soluzione nell’intervallo $[2,3]$ .

$f(x)$ agli estremi: $f(2)=-7\mbox{ , }f(3)=4$
$f'(x)=3x^2-8$ , positiva nell’intervallo: la funzione è crescente.
$f^{''}(x)=6x$ , positiva nell’intervallo: concavità verso l’alto.
Le tangenti si tracciano a partire da $B(3,4)$ .

Anche in questo caso, per accelerare il calcolo usiamo un algoritmo:

inizio

leggi $(b,n)$ ;

per $k \leftarrow 1..n$ esegui

$b \leftarrow b-\frac{f(b)}{f'(b)}$ ;

scrivi $(b)$ ;

fine

Supponiamo che i controlli siano fatti, $f(b)\ ,\ f'(b)$ siano date e lanciamo il programma con 5 iterazioni. Ecco l’output

k	$b_k$
0	3
1	2.78947368
2	2.76408434
3	2.76372389
4	2.76372382
5	2.76372382

Già con quattro interazioni si perviene alla soluzione con la stessa precisione raggiunta in 27 iterazioni col metodo dicotomico.

Il metodo delle contrazioni¶

Nei metodi precedenti, la soluzione viene ricavata partendo da alcune considerazioni geometriche relative alla forma del grafico.

Ma un altro metodo permette di trovare la soluzione di un’equazione $f(x)=0$ in modo automatico, senza dover fare considerazioni geometriche. Cioè data una equazione $f(x)=0$ è possibile trovare una funzione $F(x)=0$ e un valore iniziale $x_0$ tali che la successione definita da $x_{k+1} = F(x_k)$ converga alla soluzione $\overline{x}$ La soluzione dell’equazione sarà il numero $\overline{x}$ con $\overline{x} = F(\overline{x})$ .

Partiamo dal significato geometrico dell’iterazione della funzione $x_{k+1}=F(x_k)$ : partendo dal valore $x_0$ calcoliamo $y_0=F(x_0)$ , usando la retta $y=x`riportiamo in ascissa il valore appena trovato: :math:`x_1=y_0$ e a questo punto iteriamo il procedimento.

significato geometrico del metodo di contrazione.

Se partissimo dal punto $x_0=\overline{x}$ iterando il procedimento otterremmo sempre lo stesso valore. Questo valore si chiama punto di equilibrio della funzione $F$ . Questo nome è dovuto ad una analogia con gli oggetti che possono essere in equilibrio stabile o instabile. Se il punto di equilibrio è stabile, partendo da un punto leggermente diverso da $\overline{x}$ la successione tenderà a convergere a $\overline{x}$

mentre se il punto di equilibrio è instabile, partendo da un punto leggermente diverso da $\overline{x}$ , la successione tenderà a divergere.

Riassunto¶

Esercizi¶

#. Applica il metodo delle tangenti per calcolare la radice quadrata di un numero cercando lo zero positivo della funzione $f(x)=x^2-c$ . #. Applica il metodo delle tangenti per calcolare la radice cubica di un numero.