• Non ci sono risultati.

SOLUZIONI APPROSSIMATE DI EQUAZIONI

N/A
N/A
Protected

Academic year: 2021

Condividi "SOLUZIONI APPROSSIMATE DI EQUAZIONI"

Copied!
21
0
0

Testo completo

(1)

CAPITOLO 14

SOLUZIONI APPROSSIMATE DI EQUAZIONI

Le equazioni (e disequazioni) sono uno strumento base della modellizzazione matematica, come si può constatare in [BS base].

Una equazione è una relazione del tipo

( ) 0 f x  ove f Dom f :  R è una funzione.

Così risolvere un’equazione equivale a determinare gli zeri della funzione f . La risoluzione di un’equazione si articola in tre fasi principali.

Esistenza La prima fase è la discussione dell'esistenza delle soluzioni.

Il teorema degli zeri (Capitolo 5) fornisce una utile risposta al problema dell'esistenza di soluzioni (reali) di un’equazione.

Unicità La seconda fase è la valutazione dell'unicità della soluzione.

L’unicità della soluzione è assicurata, ad esempio, in ipotesi di stretta monotonia.

Il grafico di f può essere un valido aiuto per stabilire il numero delle soluzioni dell’equazione.

Calcolo La terza fase riguarda il calcolo delle soluzioni, che può essere affrontato per via esatta e/o mediante algoritmi di approssimazione.

Calcolo esatto E’ ben noto (cfr. ad esempio [BS base]) che solo un ristretto numero di equazioni ammette una formula risolutiva. In [BS base] sono presentate alcune tecniche di carattere generale per la risoluzione (esatta) di equazioni di vario tipo.

Calcolo approssimato

Localizzazione soluzioni

In genere si affronta lo studio di soluzioni approssimate quando non si è in grado di calcolare la soluzione esatta. In questo paragrafo affronteremo il calcolo approssimato delle soluzioni, illustrando alcuni algoritmi iterativi.

Come vedremo, prima di implementare un qualunque algoritmo di approssimazione è necessario aver stabilito l’esistenza di almeno una soluzione ed averla localizzata.

Inoltre la maggior parte degli algoritmi di approssimazione agisce in ipotesi di

unicità della soluzione.

(2)

14.1 Equazioni algebriche

Ricordiamo che un’equazione algebrica di grado n

(14.1) P x    x na n 1 x n 1   a x a 1  0  0 ammette n radici in campo complesso (cfr. [BS base]) .

Una formula risolutiva esiste solo per le equazioni di grado inferiore al quinto e comunque, le formule risolutive per le equazioni di III e IV grado sono di non facile applicazione (cfr. [BS base]).

E’ quindi necessario e opportuno affrontare il problema della risoluzione approssi- mata delle equazioni algebriche. In altri termini ci prefiggiamo l’obiettivo di determinare algoritmi di approssimazione delle soluzioni reali dell’equazione (14.1).

La prima questione da porsi è: quante sono le soluzioni reali?

Algoritmo di Sturm

L’algoritmo di Sturm 1 consente di determinare il numero delle soluzioni reali di un’equazione algebrica comprese in un dato intervallo   a b , .

L’algoritmo è di tipo iterativo, analogo al metodo delle successive divisioni di Euclide per MCD fra polinomi.

Algoritmo Descrizione dell’algoritmo:

Start

Posto S 0P ed S 1P '

Stadio 1 - si divide S per

0

S 1S x 0 ( )  q x S x

1

( ) 1 ( )  r x

1

( ) e si pone S 2   r 1

Stadio 2 - si divide S per 1 S 2S x 1 ( )  q x S x 2 ( ) 2 ( )  r x 2 ( ) e si pone S 3   r 2

Stadio 3 - si divide S per

2

S 3S x 2 ( )  q x S x 3 ( ) 3 ( )  r x 3 ( ) e si pone S 4   r 3

Ultimo stadio - si procede in questo modo fino ad ottenere l’ultimo polinomio non nullo S k .

Si osservi che S k è il MCD fra P e P , analogamente a quanto si verifica per ' l’algoritmo di Euclide.

La successione di polinomi (di grado decrescente)

Sequenza di

Sturm S 0P S 1P ' S 2   r 1 S 3   r 2 ... S k

è detta sequenza di Sturm.

Fissato un numero reale a , denotiamo con var( ) a il numero delle variazioni (cambiamenti di segno) la successione

0 1 2 3

'

( ), 0 ( ), ( ), ( ), ( ), ,

k

( )

S a S a S a S a S a S a .

1

M.Impedovo-S. Pavanelli, L’algoritmo di Sturm, LetteraMatematica PRISTEM, 10 (1993) 29-32.

(3)

Funzione var

pertanto la funzione

 

var : RN  0,1, 2,

associa ad ogni numero reale a  R il numero (eventualmente zero) delle variazioni della successione di Sturm valutata in a .

Si può dimostrare che è monotona non decrescente, costante a tratti e subisce un salto in corrispondenza alle soluzioni reali dell’equazione. Sussiste infatti il seguente risultato.

Teorema

Sturm Il numero delle radici reali e distinte dell’equazione

  0   ,

P xxa b (con ( ) P a  0 P b ( )  0 ) è pari a

var( ) var( ) ab .

Esercizio 14.1.1

Adottando l’algoritmo di Sturm, determinare il numero delle soluzioni reali dell’equazione

4 3 1 0

xx  

Svolgimento E’ facile verificare che la successione di Sturm è la seguente

 

4

 

3

   

0 1 2 3

9 2443

3 1 4 3

4 729

S xxxS xxS xx S x

Tabulando la funzione var sui numeri interi compresi nell’intervallo  2, 3 si

ottiene la tabella

a -2 -1 0 1 2 3

S

0

21 3 -1 -3 9 71

S

1

-35 -7 -3 1 29 105

S

2

-7/2 -5/4 1 13/4 11/2 31/4

S 2443/729 2443/729

3

2443/729 2443/729 2443/729 2443/729

var 2 2 1 1 0 0

Il teorema di Sturm consente di affermare che (cfr.

anche grafico a lato)

- in    2, 1  non ci sono zeri - in  1,0  c’è uno zero - in   0,1 non ci sono zeri - in   1, 2 c’è uno zero - in   2,3 non ci sono zeri.

Inoltre si deduce che

- non ci sono altri zeri in  2,   , in quanto la funzione var non può essere negativa

- potrebbero esserci zeri in    , 2.

(4)

Molteplicità degli zeri

Il teorema di Sturm fornisce anche informazioni sulla molteplicità delle radici.

A questo proposito, si osservi infatti che, se xc è uno zero di molteplicità maggiore di 1, allora

( ) ( )

2

( ) P xxc g x da cui

'( ) 2( ) ( ) ( )

2

'( ) ( )[2 ( ) ( ) '( )]

P xx c g x    x c g xx cg x   x g x in altri termini xc è uno zero anche del polinomio derivata P’.

In questo caso, l’ultimo polinomio S della successione di Sturm (che ricordiamo è

k

il MCD fra P e P’) non è costante, ma è un polinomio almeno di primo grado e i suoi zeri coincidono con quelli di P di molteplicità maggiore di 1.

Precisamente, se S è di primo grado, allora P ammette uno zero doppio, se

k

S è

k

di secondo grado, allora P ammette due zeri doppi o uno zero triplo, e così via.

Osservazione Nel caso dell’equazione dell'Esercizio 4.1.1

4

3 1 0

xx  

l’ultimo polinomio della sequenza di Sturm è la costante 2443/729, perciò P e P’

sono primi fra loro e l’equazione ammette solo zeri semplici.

Possiamo concludere che l’equazione

4

3 1 0

xx  

ammette due radici reali   1 x

1

 0 e 1  x

2

 2 e due complesse coniugate.

Localizzazione delle soluzioni

Presentiamo ora alcuni risultati sulla localizzazione delle soluzioni di una equazione algebrica

1

1 1 0

( ) n n n 0

P xxa x   a x a  

Denotiamo con S R l’insieme delle soluzioni reali dell’equazione.

Teorema Localizzazio- ne di Sturm

Risulta

1, 1

S R     MM    ove M  max  a n 1 , a n 2 , , a 0  .

Dimostrazione Proviamo innanzi tutto che

per ogni xM  1  P x ( )  0 .

Essendo a

i

  M i  0,1, , n  1 ed x  1 , ricordando un ben noto prodotto notevole si ha

-1

1 1

( ) 1

1 1

n n

n n n

x x x M M

P x x M x x M

x x

  

      

 

da cui segue l’asserto.

(5)

Consideriamo ora il caso x  M 1.

Applicando la tecnica precedente al polinomio P (  x ) (i coefficienti in valore assoluto dei due polinomi coincidono), si prova che P (   x ) 0 . Poiché i due polinomi avrebbero radici opposte, necessariamente risulta ( ) P x  0 . In definitiva

1 ( ) 0

x   M   P x  che prova l'asserto

Osservazione Il teorema di Sturm consentirebbe di localizzare le soluzioni reali dell’equazione dell'Esercizio 4.1.1

4

3 1 0

xx  

(cfr. grafico a lato) nell’intervallo  4, 4.

La localizzazione di Sturm può essere migliorata.

Un primo risultato è il seguente, di cui omettiamo la dimostrazione.

Teorema Localizzazio- ne di Mc Laurin

Risulta

, 1

S R   Kdove Kmaxa

i

: a

i

0, i0,1, , n1  .

Un secondo risultato si ottiene dividendo P per il binomio x k  , con k  0 fissato

( ) ( ) ( ) ( )

P xxk Q xR x

ove Q ed R denotano rispettivamente il quoziente ed il resto della divisione.

Teorema Localizza- zione di Laguerre

Se i coefficienti dei polinomi Q ed R sono non negativi, allora si ha

,

S R   k

Dimostrazione Dalle ipotesi segue immediatamente che

per ogni x   k 0  P x ( )  0.

(6)

Esercizio 14.1.2

Localizzare le soluzioni reali delle equazioni

1) x 4  3 x 3  0.75 x 2  3.25 x  1.5  0 2) x 4  5 x 3  2.75 x 2  3.25 x  1.5  0 3) x 5x 4  10 x 3  3 x 2    x 1 0 4) x 4  5.2 x 3  5 x 2    x 7 0

Svolgimento

1) Secondo Sturm le soluzioni reali dell’equazione 1) (cfr. Fig. 14.1) sono comprese nell’intervallo   4, 4  . Come si può verificare facilmente, Mc Laurin non migliora la stima.

2) Secondo Sturm le soluzioni reali dell’equazione 2) (cfr. Fig. 14.2) sono comprese nell’intervallo   6, 6  . Mc Laurin consente di affermare che nessuna radice supera 4, così la precedente stima si migliora S R    6, 4  .

3) Secondo Sturm le soluzioni reali dell’equazione 3) (cfr. Fig. 14.3) sono comprese nell’intervallo   11,11  .

Mc Laurin consente di affermare che nessuna radice supera 2, così la stima si aggiorna S R    11, 2  .

Osserviamo inoltre che, se applichiamo Mc Laurin al polinomio P   x (che ha radici opposte a quelle di P x )  

5 4 3 2 5 4 3 2

10 3 1 0 10 3 1 0

x x x x x x x x x x

             

otteniamo che le radici non superano 4. Di conseguenza le soluzioni del polinomio assegnato P x sono superiori a –4 e la stima diventa  

4, 2

S R   .

4) Secondo Sturm le soluzioni reali dell’equazione 4) (cfr. Fig. 14.4) sono comprese nell’intervallo   8, 8  . Per Mc Laurin nessuna radice supera 6,2 .

Inoltre, applicando il teorema di Mc Laurin al polinomio ausiliario

4 3 2

5 5 7 0

xxx    x

otteniamo che le radici non superano 1. Di conseguenza le soluzioni del polinomio assegnato sono superiori a –1.

In definitiva, Mc Laurin migliora la stima di Sturm nel modo seguente

1, 6.2

S R   .

Fig. 14.1 Fig. 14.2

(7)

Fig. 14.3 Fig. 14.4

Esercizio 14.1.3

Localizzare le soluzioni reali dell’equazione

4 3 2

10 20 1 0

xxx    x

Svolgimento Secondo Sturm le soluzioni reali dell’equazione sono comprese nell’intervallo

21, 21  , Mc Laurin fornisce invece la limitazione  2,11 .

Utilizzando Laguerre si possono migliorare entrambe le stime. Precisamente si ha

k Coefficienti di Q R 8 1, -2, 4, 33 263 9 1, -1, 11, 100 899 10 1, 0, 20, 201 2009

La migliore maggiorazione che si può dedurre da questi dati è la seguente

,10

S

R

  .

Par ottenere una limitazione inferiore applichiamo il teorema al polinomio P   x .

Osserviamo che risulta

k Coefficienti di Q R 1 1, 11, 31, 30 29 0.5 1, 10.5, 25.25, 11.625 4.813 0.25 1, 10.25, 22.6, 4.6 0.16 0.2 1, 10.2, 22.04, 3.4 -0.32

Di conseguenza la migliore limitazione inferiore che si può dedurre da questi dati è la seguente

0.25,

S

R

   .

Concludendo la migliore stima della localizzazione delle soluzioni dell’equazione

4 3 2

10 20 1 0

xxx    x

è l’intervallo  0.25,10.

(8)

14.3 Metodo di bisezione (o dicotomico)

Esistenza della soluzione

Proponiamo un primo algoritmo molto elementare per l’approssimazione delle soluzioni di una equazione

  0   ,

f xxa b

Assumiamo che f sia continua ed assuma valori di segno discorde nei due punti a e b

( ) ( ) 0 f af b

cosi che l’equazione ammette almeno una soluzione (per il teorema degli zeri).

Descrizione

dell’algoritmo Iniziamo con una descrizione qualitativa dell’algoritmo dicotomico: si tratta di un processo iterativo che procede per successive suddivisioni dell’intervallo   a b , .

Step 1

Il punto medio 2 ab

dell’intervallo   a b ,

individua due sottointervalli , 2

a b a

 

 

  e ,

2 a b

b

 

 

 

Si osservi che la funzione f assume valori di segno concorde negli estremi dell’intervallo di sinistra, mentre assume valori di segno discorde in quello di destra. Così la soluzione è sicuramente

compresa in questo ultimo intervallo. Fig. 14.5

Poniamo

1 1

, ,

2 a b

b a b

   

 

 

e procediamo alla bisezione dell’intervallo  a b .

1

,

1

Step 2 Questa volta (cfr. immagine a lato) la funzione assume valori di segno discorde agli estremi dell’intervallo di destra.

Così poniamo

 

1 1

1

,

2

,

2

2 a b

aa b

  

 

 

e proseguiamo bisecando l’intervallo  a b .

2

,

2

Procedendo iterativamente per successive suddi- visioni, a partire dall’intervallo   a b , si genera , una successione di intervalli (uno contenuto

nell’altro) Fig. 14.6

Step n a b n , n    a n 1 , b n 1  nN ciascuno dei quali contiene almeno la radice dell’equazione.

Trasformazione intervallo- intervallo

Il processo iterativo è quindi generato da una trasformazione T che opera su

sottointervalli di   a b , cioè , T :     ,     , .

(9)

Descrizione della trasformazione

Precisamente, fissato un sottointervallo     , tale che f       f   0 si valuta la funzione nel punto medio

f     2 

 

  .

Supposto 2 che 0

f    2

  

 

  , si hanno due possibilità:

- se   0

f   f       2     si pone    ,,

T           2    (cfr. Fig.14.5)

- se   0

f   f       2     si pone    ,,

T          2     (cfr. Fig.14.6) In altri termini, suddiviso l’intervallo     , in due sottointervalli (mediante il punto medio) la trasformazione T seleziona quello ove la funzione assume valori di segno discorde agli estremi.

Formalizzazione del processo iterativo

Di conseguenza T associa all’intervallo     , , (che

contiene una soluzione dell’equazione) il sottointervallo dicotomico che contiene ancora una soluzione.

Il processo generato dalla trasformazione T è il seguente

   

0 0

  

1 1

  1, 2, 3,

, ,

, ,

n n n n

n

a b a b start

a b T a

b

 

Teorema Convergenza algoritmo dicotomico

Se f :   a b , R è una funzione continua tale che f a     f b 0 , le successioni   a

n n

e   b

n n

generate con il processo dicotomico

   

0 0

  

1 1

  1, 2, 3,

, ,

, ,

n n n n

n

a b a b start

a b T a

b

 

convergono ad una soluzione dell’equazione x .

Inoltre le successioni   a

n n

e   b

n n

sono monotone e costituiscono approssima- zioni rispettivamente per difetto e per eccesso di x

1 1

n n n n

aa

  x b

b

Sussiste infine la seguente stima dell’errore di approssimazione

0 0

n

2

n

b a

en N

  .

Dimostrazione Proponiamo un cenno della dimostrazione.

2

Se 0

2 f

  

  

 

  , allora il punto medio è soluzione dell’equazione e l’algoritmo si arresta.

(10)

Attrattore del

processo Si dimostra facilmente che la trasformazione T è una contrazione, quindi, in virtù del Teorema di Caccioppoli, il processo ammette come attrattore una soluzione x dell’equazione.

Inoltre, essendo gli intervalli dicotomici, le successioni degli estremi   a

n n

e   b

n n

sono monotone (la prima non decrescente, la seconda non crescente) e costituiscono approssimazioni rispettivamente per difetto e per eccesso di x .

In forza della dicotomia, che è la chiave del processo, è facile stimare l’ampiezza di ciascun intervallo

0 0

n n

2

n

b a

b a

  .

Stima errore di

approssimazione Si ottiene così una stima esplicita dell’errore di approssimazione in funzione del passo

 

0 0

max ,

n n n n n

2

n

b a

e x a x b a

     

Ordine di

convergenza Per valutare l’ordine di convergenza della successione delle approssimanti, consideriamo il limite seguente

1

1

lim 2

n

n n

e e



L’ordine di convergenza dell’algoritmo è pertanto apri ad 1.

Il metodo dicotomico ha quindi una convergenza “lenta”, infatti guadagna una cifra binaria ad ogni passo e quindi occorrono 3 o 4 passi per guadagnare una cifra decimale..

Nei prossimi paragrafi presenteremo metodi più veloci, che però sussistono sotto

ipotesi più restrittive.

(11)

Esercizio

14.3.1 Discutere esistenza, unicità e calcolo approssimato delle soluzioni dell’equazione

10 x 1 0

x  

Svolgimento Esistenza e localizzazione della soluzione

Unicità della soluzione

Posto

  10

x

1

f xxxR

risulta

  0 1

f   ed f   1 9

di conseguenza, per il teorema degli zeri, l’equazione ammette almeno una soluzione nell’intervallo   0,1 .

La soluzione è unica in quanto f è crescente.

Calcolo approssimato della soluzione

Utilizzando il metodo dicotomico determiniamo una stima di tale soluzione

stadio estremi dell’intervallo

0 f   0 0 f   1 0 a 0  0 b

0

 1

1 f   0.5 0 f     0 f 0.5 0 a 1  0 b 1  0.5

2 0 0.50.250

f     2     f  

0.25    0.5 0

ff2

0.25

ab 2  0.5

10 a 10  0.39875 b 10  0.3994

Soluzione approssimata

Sulla base dei dati riportati in tabella, possiamo assumere il valore

  0.39

come approssimazione della soluzione, esatta fino alla seconda cifra decimale.

(12)

14.4 Metodi di linearizzazione

I metodi di linearizzazione sono algoritmi iterativi che consistono nell’approssimare le soluzioni dell’equazione

(14.1) ( ) f x  0 con quelle di una successione di equazioni lineari (14.2) m x nq n  0 nN .

Assumiamo che f :   a b , R sia continua con valori di segno discorde agli estremi ( ( ) f af b ( )  0 ), cosi l’equazione (14.1) ammette almeno una soluzione (per il Teorema degli zeri).

Modello

generale Le trasformazioni T che generano i vari processi di linearizzazione sono tutte dello stesso tipo, ne diamo qui una descrizione in termini geometrici.

L’idea base è la seguente: fissato un punto c   a b ,

Step 1

Step 2

Step 3

- si considera il punto P

c

  c f c ,    sul grafico di f ed il fascio di rette di centro P

c

   

ym x   c f c mR

- si seleziona (secondo una legge che varia in funzione del metodo) una retta di tale fascio

   

*

ym x   c f c

- si determina la soluzione della equazione

     

* 0

*

c c

m x c f c x c f x

      m

Trasformazione La trasformazione T associa a c il punto T c    x

c

.

Processo iterativo

Il processo iterativo generato da T

(14.3) 0

1 ( ) 0,1, 2,

n n n

x start

x T x

  

consente di individuare una successione   x

n n

che (come vedremo) sotto opportune ipotesi converge alla soluzione di (14.1).

La successione   x

n n

delle iterate assume la forma

Successione

delle iterate (14.4)

1

(

n

)

n n

n

x x f x

  m

ove m è il coefficiente angolare della retta selezionata al passo n nel fascio

n

 

n

n

yf xm xx

(13)

Presentiamo ora i principali algoritmi di approssimazione delle soluzioni di una equazione che si basano su un processo di linearizzazione.

Come vedremo, per individuare ciascun metodo è sufficiente assegnare i suoi elementi caratteristici

lo start e la legge che seleziona la retta del fascio (assegna cioè il coefficiente angolare m n ).

Regula falsi

Elementi caratterizzanti

start

passo n

retta selezionata

si fissano come prima coppia di iterate x ed

0

x gli estremi dell’intervallo

1

  a, b

la retta selezionata (al passo n  2 ) è quella che congiunge il punto

x

0

, f x  

0

 con il punto  x

n1

, f x  

n1

 individuato al passo precedente, il cui coefficiente angolare è

 

1

 

0

1 0

n

2

n

n

f x f x

m n

x x

  

La successione delle iterate è quindi

Algoritmo

regula falsi  

     

0 1

1 0

0

1, 2, ,

n

n n n

n

n x x start

x x f x x x

f x f x

 

 

   

 

Teorema convergenza regula falsi

Supponiamo che

- f :   a b , R sia una funzione di classe C

2

tale che f a     f b 0

- f sia di segno costante "

Allora la successione   x

n n

fornisce un’approssimazione dell’unica soluzione x dell’equazione

  0   ,

f xxa b che migliora ad ogni passo.

Dimostrazione Diamo solo un cenno della dimostrazione.

Esistenza ed

unicità Le ipotesi assunte assicurano che l’equazione ( ) f x  0 ha un’unica soluzione x .

Convergenza

del metodo Si prova che la trasformazione T è una contrazione, quindi ammette un (unico) punto fisso x T x   , attrattore del processo; così lim

n

n

x x



 .

Inoltre la successione delle iterate è monotona, di conseguenza l’errore di

approssimazione e

n

x

n

x diminuisce ad ogni passo.

(14)

Algoritmo delle Secanti

Elementi caratterizzanti

start

passo n

retta selezionata

si assegnano come prima coppia di iterate x 0 e x 1 gli estremi dell’intervallo

  a, b .

la retta selezionata al passo n  2 è la secante passante per i punti

x

n1

, f x  

n1

 e  x

n2

, f x

n2

 

calcolati nei due passi precedenti di coefficiente angolare

 

1

2

1 2

n n

2

n

n n

f x f x

m n

x x

 

 

  

Quindi l’algoritmo iterativo è il seguente

Algoritmo

secanti  

     

0 1

1 1

1

1, 2, ,

n

n n n n

n n

n x x start

x x f x x x

f x f x

 

 

   

 

Teorema Convergenza metodo delle secanti

Nelle stesse ipotesi adottate per la regula falsi, la successione   x

n n

fornisce un’approssimazione dell’unica soluzione dell’equazione

  0   ,

f xxa b che migliora ad ogni passo.

Dimostrazione Diamo solo un cenno della dimostrazione.

Esistenza ed

unicità Le ipotesi assicurano l’esistenza e l’unicità della soluzione.

Convergenza del metodo

A differenza della regula falsi, entrambi i punti che individuano la retta si aggiornano con il procedere del passo.

Le ipotesi assunte assicurano che la trasformazione T ammette un unico punto fisso x . La successione   x

n n

delle iterate (fornita dalla 14.4) non è in generale monotona, tuttavia anche in questo caso, l’approssimazione migliora ad ogni passo.

Velocità di

convergenza Il metodo delle secanti è un algoritmo con velocità di convergenza più alta rispetto a quella della bisezione.

Precisamente, si prova che l’ordine di convergenza è (cfr. [Co])

1  5 / 2 1.618   .

(15)

Metodo delle tangenti o di Newton 3

Elementi caratterizzanti

start

passo n

Si assegna il punto x coincidente con uno degli

0

estremi dell’intervallo   a b ,

la retta selezionata è la tangente al grafico di f nel punto  x

n1

, f x  

n1

 individuato al passo precedente di coefficiente angolare

 

-1

1

n n

mfx n  Quindi l’algoritmo iterativo è il seguente

Algoritmo Newton

   

0

1 1, 2,

'

n

n n

n

n x start

x x f x

f x

 

 

  

 

Teorema

Newton Supponiamo 4 che

- f :   a b , R sia una funzione di classe C tale che

2

f a     f b 0

- f   x 0 per ogni x   a b ,

- f    x sia di segno costante

Allora la successione   x

n n

fornisce un’approssimazione dell’unica soluzione dell’equazione

  0   ,

f xxa b che migliora ad ogni passo.

Dimostrazione Esistenza ed unicità

Le ipotesi (più restrittive di quelle dei metodi precedenti) assicurano ovviamente esistenza ed unicità della soluzione in   a b . ,

Convergenza del

metodo Proponiamo una dimostrazione elementare della convergenza della successione

  x

n n

.

Consideriamo uno dei quattro casi possibili (cfr. immagine precedente) e assumiamo f ' 0 f " 0 f a   0 f b   0

La funzione è quindi crescente e convessa.

3

L’algoritmo è noto anche come metodo di Newton-Raphson-Fourier

Newton introduce l’idea del metodo in Analysis per Aequationes Numero Terminorum Infinotas (1666) e lo descrive quindi in Method of Fluxions (1671) per risolvere l’equazione x

3

 2 x   5 0 . Il metodo fu pubblicato dall’autore solo nel 1736.

Joseph Raphson (1648 – 1715) è noto per aver pubblicato nel 1690 il volume Analysis Aequationum Universalis ove è illustrato il metodo delle tangenti di Newton. In Questiones d’analyse Algebrique (1818) Fourier (1772 - 1837) propone un’estensione di tale metodo.

4

In alcuni testi compare anche l’ipotesi f a     f ' a   b a ed f b     f ' b   b a che assicura che le rette tangenti

negli estremi dell’intervallo intersecano l’asse delle ascisse all’interno dell’intervallo   a b , .

(16)

Sia  l’unica soluzione dell’equazione f x   0 .

Fissato uno start 5 x con

0

  x

0

b ed f x  

0

 0 , consideriamo la successione delle iterate

   

0

1 1, 2,

'

n

n n

n

n x start

x x f x

f x

 

 

  

 

Proviamo, per induzione, che (1)

1 n

n n

n N

x

x

x

  

 

 da cui segue

(2)   x

n1

x

n

nN Step 1 Proviamo innanzi tutto che la (1) sussiste per n  0 .

Per posizione   x

0

, inoltre essendo  

 

00

0

' f x

f x  , si ha

   

0

1 0 0

'

0

x x f x x

f x

   .

Step 2 Assunta quindi (1) vera per n, proviamola per n+1.

Essendo per ipotesi   x

n

, in virtù del teorema di Lagrange applicato nell’intervallo

  , x

n

 , esiste un elemento   x *  x

n

tale che

 

n

  '   *  

n

 

n

  

n

   ' *

n

f x f

f x f x f x f x f x

x

 

       

 

Da cui, tenuto conto della monotonia crescente di f (conseguenza dell’ipotesi '

" 0

f  ) si ottiene

       

'  

'

n

n n n n

n

f x x f x f x x

f x

      

e quindi

     

1

'

n

n n n n

n

x x f x x x

f x

       

Abbiamo così provato che   x

n1

, proviamo ora che x

n2

x

n1

. Essendo   x

n1

, ovviamente risulta f x

n1

  0 da cui segue che

 

1

2 1 1

'

1 n

n n n

n

x x f x x

f x

  

   .

Abbiamo così provato la (1).

Poiché la successione   x

n n

è monotona, esiste il limite lim

n

inf

n

n

x

n

x x



   

5

Come start si considera l'estremo di Fourier, che è quello (fra a e b ) in cui il segno della funzione è concorde con quello

della derivata seconda.

(17)

Ricordando l’algoritmo iterativo, si ha

 

-1

 

-1

-1

( ) ( )

lim lim

' '

n

n n

n n

n

f x f x

x x x x

f x f x

 

 

      

 

da cui si conclude che

 

xT x ed f x   0 x   .

Velocità di

convergenza L’algoritmo ha un ordine di convergenza pari a 2 essendo

1

lim

n 2 n

n

e R

e

 



Dimostrazione Si osservi che, in virtù della formula di Taylor, esiste   x

n

,   tale che

        1  

2

 

0 ' "

n n n

2

n

f f x x f x x f

         

da cui

     

2

   

1

1 " / '

' 2

n

n n n n

n

x x f x x f f x

f x

 

         cioè

   

2 1

1 " / '

n

2

n n

e

  e ff x e quindi

   

1

   

2

1 2

1 1

" / ' " / '

2 2

n

n n n

n

e e f f x e f f

e

     

Il metodo di Newton ha quindi un ordine di convergenza doppio rispetto la regula falsi 

Applichiamo il metodo di Newton a due casi di particolare interesse.

Esempio

14.4.1 Nel caso dell’equazione x

2

 2 , l’algoritmo di Newton diventa

1

1 2

n

2

n

n

x x

x

 

   

 

che corrisponde all’algoritmo babilonese per il calcolo della radice quadrata (cfr.

Capitolo 13).

Esempio

14.4.2 Nel caso f x   1 c c 0

  x  , l’algoritmo diventa

 

1

2

n n n

x

xc x

che permette un calcolo approssimato del reciproco di c attraverso addizioni e

moltiplicazioni, senza divisioni.

(18)

14.5 Metodi iterativi a confronto

Proponiamo alcuni esempi per illustrare i metodi iterativi di approssimazione.

Esercizio 14.5.1

Confrontare gli algoritmi di approssimazione per l’equazione

10 -1 0 x

x

Svolgimento Si può controllare che i quattro metodi presentati nel paragrafi precedenti sono applicabili nell’intervallo   0 , 2 .

La tabella seguente sintetizza le approssimazioni ottenute

Passo Bisezione Secanti Tangenti Regula falsi

1 0 0 0 0

2 1 1 0.99 1

3 0.5 0.1 0.7 0.1

4 0.25 0.17 0.50 0.17

5 0.375 0.5 0.4 0.24

6 0.4375 0.33 0.3999 0.28

7 0.40625 0.3797 0.399014 0.32

8 0.390625 0.40 0.39901297825 0.34

9 0.398435 0.398 0.3990129782600 0.36 10 0.40234375 0.3990126 0.3990129782600 0.37

I dati della tabella evidenziano che la velocità di convergenza del metodo di Newton è superiore a tutte le altre.

Esempio

Keplero Il modello del moto dei pianeti, ottenuto in accordo con la legge di gravitazione universale di Newton e alle leggi di Keplero, conduce a studiare la così detta equazione di Keplero.

 

sin 0 0,

e       b    ove , e bR .

Esercizio 14.5.2

Discutere l’approssimazione delle soluzioni dell’equazione di Keplero, comprese nell’intervallo0, 2, nel caso particolare b   1 ed e  1

sin     -1 0

Svolgimento Il grafico della funzione

  sin -1

f     

(cfr. figura a lato) “mostra” che l’equazione studiata ammette una sola soluzione in  0, 2.

Come prova di questa affermazione è facile verificare che sussistono le ipotesi del metodo della tangenti.

La tabella seguente sintetizza le approssimazioni con i

diversi metodi descritti nei paragrafi precedenti.

(19)

Passo Bisezione Secanti Tangenti Regula falsi

1 0 0 0 0

2 1 1 0.5 1

3 0.5 0.54 0.51095 0.54

4 0.75 0.50 0.51097342935 0.512

5 0.625 0.51098 0.5109734293882 0.511

6 0.5625 0.51097343 0.5109734293882 0.510976

7 0.53125 0.5109734293882 0.5109734293882 0.5109735 8 0.515625 0.5109734293882 0.5109734293882 0.51097343 9 0.5078125 0.5109734293882 0.5109734293882 0.5109734296 10 0.51171875 0.5109734293882 0.5109734293882 0.51097342939 Esempio

Crescite esponenziale e polinomiale a confronto

Come è noto, la crescita esponenziale supera quella polinomiale, in altri termini risulta

 

- 0

e

x

p xper valori di x sufficientemente grandi.

Sorprendentemente però, in alcuni casi le funzioni polinomiali (quadratiche, cubiche, etc.) sorpassano al finito la funzione esponenziale.

Precisiamo il senso dell’affermazione, limitandoci a considerare la funzione esponenziale e la cubica

 

x

f xe g x   x

3

.

Nonostante nel punto iniziale  x

0

 0 

l’esponenziale sia sopra la cubica

  0 1 (0) 0

f   gdopo solo cinque unità è già avvenuto il sorpasso.

È infatti

5 3 5 3

(5) - (5) - 5 3 - 5 0

f ge   .

Il grafico delle funzioni f e g nell’intervallo [0,10] illustra chiaramente il loro reciproco comportamento.

Aggiungere i metodi di punto fisso

Traslochi difficoltosi caso con spessore

Il Ragioniere Mario Rossi deve cambiare ufficio, ma conservare l’arredo. La sua preoccupazione è il trasferimento dell’armadio: egli pensa di trascinarlo orizzontal-mente lungo due corridoi, larghi rispettivamente 1,15 m e 75 cm, che si intersecano ad angolo retto.

Discutere la fattibilità dell’operazione in funzione delle dimensioni dell’armadio (a base

rettangolare; larghezza=65 cm, lunghezza=1,25 m).

(20)

Svolgimento Valutiamo la lunghezza massima L di un mobile dello spessore s che possa compiere una rotazione di 90 gradi.

Denotato con  l’angolo SCD e indicata con ˆ L ( )  la lunghezza massimale corrispondente all’angolo  , dallo schema a lato si deduce

115 75

65 tan( ) 65 cotan( ) = ( ) sin cos

LABAPSB       L

 

min ( )

LL

 

Discutiamo quindi l'esistenza e calcolo del minimo

0 min /2 L ( )

  

 

ove

115 75 65

( ) sin cos sin cos

L    

   

Per risolvere la questione individuiamo gli intervalli di crescenza/decrescenza.

A questo proposito, calcoliamo la derivata:

5

2

  

3

 

2

'( ) 23 cos 15sin 26 cos 15sin 13

sin cos

L                 

risulta

  

3

 

2

'( ) 0 23 cos 15sin 26 cos 15sin 13 0

L            

Si tratta di una disequazione difficile da trattare!

Se operiamo un cambiamento di variabile, adottando le formule parametriche, si ottiene:

 

6 4 3 2

2 2

'( ) 5 18 67 60 2 5 tan

1 2

L t t t t t t

t t

      

 da cui la disequazione fratta

6 4 3 2

2

18 67 60 2 5

'( ) 0 0

1

t t t t

L t t

   

  

Anche quest'ultima disequazione non è agevole da trattare vista l'impossibilità di scomporre in fattori il numeratore. Così dobbiamo arrenderci, ma solo per il momento!

Riprenderemo la questione nel Capitolo 14.

(21)

14.6 Esercizi proposti

14.6.1 Newton illustrò il suo metodo attraverso l’equazione

3

2 5 0

xx   . Quali risultati avrà trovato?

14.6.2 Nel 1225 Leonardo Pisano (detto Fibonacci) studiò l’equazione

3 2

2 10 20 0

xxx   e ricavò la seguante soluzione x  1.368808107 .

Non è noto il procedimento che adottò, ma il risultato è notevole per il suo tempo.

Dopo aver discusso esistenza, unicità e localizzazione delle soluzioni dell’equazione, determinare un processo iterativo di approssimazione della soluzione e confrontare il risultato con quello di Fibonacci.

14.6.3 Dopo aver discusso esistenza, unicità e localizzazione delle soluzioni reali dell’equazione di Abel-Ruffini

5 - 4 2 0

x x  

determinare, utilizzando i metodi di linearizzazione, le prime 6 cifre decimali esatte di tali soluzioni.

14.6.4 Dopo aver discusso esistenza, unicità e localizzazione delle soluzioni delle equazioni seguenti, stimare tali soluzioni con una precisione di 10 2

1) xe x  5 2) 2 x  4 x 3) x e 1/ x  3

4) x 5   x 3 0.1 0  5) 2 x  log x  4

14.6.5 Applicando il metodo di Newton, determinare un algoritmo di approssimazione per

3

2 . Calcolare i prime 5 passi, con start x

0

 1 e stimare l’errore.

14.6.6 Calcolare un’approssimazione della soluzione delle equazioni

1) cos xx 2) sin x   x 1 3) e x    x 2 0 .

14.6.7 Adottando il metodo di Newton, dare una stima di

6

2 esatta alla ottava cifra decimale .

14.6.8 Utilizzando un metodo iterativo di approssimazione esposto in questo capitolo, determinare i punti di sorpasso.

Discutere esistenza, unicità e calcolo dei punti di sorpasso fra la funzione esponenziale e e la funzione potenza

x

x , con k intero positivo.

k

14.6.9 Adottando il metodo di Newton, approssimare il reciproco del numero e.

14.6.10 Dopo aver localizzato una soluzione dell’equazione

4

12 34 0

xx  

determinare una sua approssimazione adottando il metodo delle secanti (utilizzare

almeno 4 passi).

Riferimenti

Documenti correlati

Essa è una funzione continua, in quanto differenza di funzioni continue... Infatti, il viceversa di questo teorema vale anche per le

equazioni passaggi passaggi passaggi passaggi soluzioni soluzioni soluzioni soluzioni

Conseguentemente il rapporto risulta essere un infinitesimo in +∞ di ordine minore di 3/2 e maggiore di 3/2 − ε per ogni ε ∈]0, 3/2[; considerando, ad esempio, ε = 1/4 si ottiene

Soluzione Scritto di Analisi Matematica I (A) Ingegneria Edile & Gestionale, 18 Febbraio 1999.. Per- tanto sar` a dotata di minimo e di

Teoremi sulla continuit` a: teorema di esistenza degli zeri, teorema di esistenza di soluzioni di equazioni a termini continui (con dimostrazione), monotonia di funzioni invertibili

Abbiamo infatti visto nel caso di traiettorie illimitate che la shock wave che si forma nel moto asintotico acquista una sua propria “autonomia” e continua a propagarsi in

Allora, la funzione (che, con un piccolo abuso di notazione, denoteremo ancora f ) I −→ J `e invertibile.. In questo modo si dimostra che in [0, +∞) esistono tutte le radici

[r]