Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email:...

202
Metodi Numerici con Elementi di Programmazione (A.A. 2019-2020) Metodi Numerici Appunti delle lezioni: Equazioni non lineari

Transcript of Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email:...

Page 1: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Metodi Numerici con Elementi di Programmazione

(A.A. 2019-2020)

Metodi Numerici

Appunti delle lezioni: Equazioni non lineari

Page 2: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Docente Vittoria Bruni

Email: [email protected]

Ufficio: Via A. Scarpa,

Pal. B, I piano, Stanza n. 16

Tel. 06 49766648

Ricevimento: consultare la sezione Avvisi della pagina web dedicata al corso

Testi consigliati:

Calcolo Numerico, L. Gori, Ed. Kappa, 2006

Esercizi di Calcolo Numerico, L. Gori-M.L. Lo Cascio, F. Pitolli, Ed. Kappa, 2007

Il materiale didattico e disponibile sul sito

http://ingaero.uniroma1.it/

nella pagina dedicata al corso Metodi Numerici con Elementi di Programmazione

1

Page 3: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Equazioni non lineari

2

Page 4: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Problema 1

La traiettoria di un satellite che orbita intorno alla terra e data dallaseguente equazione

R(θ) =C

1 + esin(θ + α)

dove (R, θ) sono le coordinate polari del satellite, C, e ed α sono trecostanti (e e nota come eccentricita dell’orbita).

Sapendo che il satellite e stato osservato nelle seguenti tre posizioni

θ -30o 0o 30o

R(km) 6870 6728 6615

si vuole determinare la distanza minima del satellite dalla terra e l’angolocorrispondente.

3

Page 5: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Si verifica facilmente che il valore minimo di R e C1+e e si realizza in

corrispondenza dell’angolo θ = π2 − α. Infatti, risulta

dR

dθ= 0⇔ − ecos(θ + α)

(1 + esin(θ + α))2= 0⇔ θ =

π

2− α

per sin(θ + α) 6= −1e . Da cui R(π2 − α) = C

1+e.

Per poter determinare il valore minimo di R e l’angolo θ e quindi ne-

cessario determinare il valore delle tre costanti C, e, α usando le tre

posizioni del satellite note, cioe

C1+esin(α−30) = 6870

C1+esin(α) = 6728

C1+esin(α+30) = 6615

che risulta essere un sistema di equazioni non lineari nelle tre inco-

gnite C, e ed α.

4

Page 6: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Problema 2

Si vuole determinare la parte sommersa di una boa sferica di raggio

R = 0.055m e densita ρB = 0.6Kg/m3

Indicando con Fρ la spinta idrostatica, con MB la massa della boa sfer-

ica, g l’accelerazione di gravita e ρw(= 1Kg/m3) la densita dell’acqua,

si ha

MBg = Fρ

e quindi

4

3πR3ρBg = πx2

(R− π

3

)ρwg

5

Page 7: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

da cui

ρwx3 − 3ρwx

2R+ 4R3ρB = 0.

Per calcolare il valore di x e necessario risolvere un’ equazione non

lineare

L’equazione da risolvere, corrispondente al problema particolare con-

siderato, e la seguente

x3 − 0.165x2 + 3.993 · 10−4 = 0.

6

Page 8: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Problema 3

La crescita di una popolazione puo essere modellata, su un periodo di tempopiccolo, assumendo che la popolazione abbia un tasso di crescita proporzionale alnumero di individui presenti in ciascun istante. Se N(t) indica il numero di individui altempo t e λ e il fattore di crescita della popolazione, allora N(t) soddisfa l’equazionedifferenziale

dN(t)dt = λN(t),

la cui soluzione e N(t) = N0eλt, dove N0 indica la popolazione all’istante di tempoiniziale, cioe N0 = N(t0).

Questo modello e valido solo quando la popolazione e isolata e non c’e immigrazionedall’esterno. Se si suppone che ci sia una immigrazione a un tasso costante ν, ilmodello differenziale diventa

dN(t)dt = λN(t) + ν

la cui soluzione e N(t) = N0eλt + ν

λ(eλt − 1).

Supponendo che la popolazione iniziale sia di un milione di individui, che la comunita

cresca di 435·000 immigrati il primo anno e che 1·564·000 individui siano presenti

alla fine del primo anno, determinare il tasso di crescita λ della popolazione.

7

Page 9: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

E’ necessario risolvere l’equazione non lineare

N |t=1 anno = N0eλ +

ν

λ(eλ − 1)

nell’incognita λ, con N |t=1 anno = 1·564·000, N0 = 1·000·000,

ν = 435·000.

q ⇒ f(λ) = eλ + 0.435λ (eλ − 1)− 1.564 = 0

8

Page 10: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Problema 4

Le frequenze naturali ωi di una trave uniforme a sbalzo, di massa m e lunghezza L,sono legate agli zeri βi della seguente funzione

f(β) = cosh(β)cos(β) + 1,

dove

β4i = (2πωi)

2mL3

EIE rappresenta il modulo di elasticita (sforzo applicato/deformazione causata, mis-

urato in GigaPascal) mentre I e il momento di inerzia della sezione trasversale. ωirappresenta la i-esima frequenza naturale misurata in cicli al secondo (cps).

Determinare le due frequenze piu basse di una trave di acciaio lunga 0.9m e avente

una sezione trasversale rettangolare larga (b) 25mm e alta (h) 2.5mm — I = bh3

12. La

densita di massa della trave e 7850Kg/m3 e il modulo di elasticita e 200GPa.

9

Page 11: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Problema 5

Problema: flusso di liquidi e gas attraverso i sistemi di raffreddamento

La resistenza al flusso in tali condotti e parametrizzata da un numero adimensionale,detto coefficiente di attrito. L’equazione di Colebrook definisce il coefficiente diattrito di Darcy f per flussi turbolenti attraverso la seguente equazione

1√f

+ 2log10

3.7D+

2.51

Re√f

)= 0,

dove Re rappresenta il numero di Reynolds (4000 < Re < 108), D il diametro dellacondotta e ε la rugosita della superficie

Oss: f rappresenta un parametro adimensionale

Si vuole stimare f con precisione 10−8 quando Re = 300000 e εD

= 0.0001

10

Page 12: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Problema 6

Orbita del satellite ’Wind’ della NASA In uno dei primi programmi della NASAsi prevedeva di lanciare il satellite Wind che doveva rimanere in una posizione fissalungo la linea che congiunge la terra con il sole in modo che il vento solare potessepassare intorno al satellite. Si vuole determinare la distanza r tra il satellite e laterra.

Si tratta di risolvere la seguente equazione non lineare (ipotesi: orbite circolari)

GMsolem

(R− r)2=GMterram

r2+mω2(R− r),

con R= distanza terra-sole; Msole=massa del sole; Mterra=massa della terra; m=massadel satellite; G = costante gravitazionale; ω = velocita angolare del satellite.

Oss: E’ preferibile riscrivere l’equazione precedente nella forma equivalente

GMsolemr2 = GMterram(R− r)2 +mω2r2(R− r)3

11

Page 13: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Problema 7

La velocita v del razzo Saturno V in volo verticale vicino la superficie terrestre puoessere approssimata come segue

v(t) = ulogM0

M0 −mt− gt

con u = 2510m/s exhaust velocity del razzo

M0 = 2.8 · 106Kg massa del razzo al momento del lancio

m = 13.3 · 103Kg/s tasso di consumo di carburante

g = 9.81m/s accelerazione di gravita

t tempo trascorso dal lancio.

Determinare l’istante di tempo in cui il razzo raggiunge la velocita del suono (≈335m/s) con precisione al millesimo di secondo.

Si tratta di risolvere le seguente equazione non lineare

ulogM0

M0 −mt− gt− 335.

12

Page 14: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Sistemi di equazioni non lineari

Un sistema di equazioni non lineari puo essere scritto nella forma

f1(x1, x2, . . . , xn) = 0f2(x1, x2, . . . , xn) = 0. . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . .fn(x1, x2, . . . , xn) = 0

La soluzione del sistema e il vettore Ξ = [ξ1, ξ2, . . . , ξn]T le cui com-ponenti annullano simultaneamente le n equazioni del sistema.

Supporremo che le funzioni fi : D ⊂ Rn → R, i = 1, . . . , n, siano almenocontinue in D

Oss: Nel Problema 1, n = 3 e [x1, x2, x3]T = [C, e, α]T .

Nei Problemi 2-7, n = 1 e si ha rispettivamente [x1]T = [x]T , [x1]T =[λ]T , [x1]T = [βi]

T , [x1]T = [f ]T , [x1]T = [r]T , [x1]T = [t]T .

13

Page 15: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Caso n = 1: equazioni non lineari

Un’ equazione non lineare e un’equazione del tipo

f(x) = 0

Le soluzioni ξ dell’equazione, cioe quei valori tali che

f(ξ) = 0,

vengono chiamati radici dell’equazione non lineare o zeri

della funzione f .

Ci limiteremo al caso di radici reali.

14

Page 16: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Separazione delle radici

Prima di utilizzare un metodo numerico bisogna sapere:

• quante sono le radici (reali);

• dove si trovano approssimativamente;

• se ci sono delle simmetrie.

Per rispondere a queste domande si puo ricorrere alla tabu-

lazione o al grafico della funzione f .

15

Page 17: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Problema 3: separazione grafica delle radici

f(λ) = eλ + 0.435λ (eλ − 1)− 1.564 = 0

Separazione grafica: si traccia il grafico della funzione

e si individuano gli intervalli in cui la funzione interseca

l’asse delle ascisse.

Richiami: Teorema di esistenza degli zeri per funzioni continue: Se f ∈ C([a, b])

e k ∈ [f(a), f(b)], ⇒ ∃ξ ∈ [a, b] : f(ξ) = k.

16

Page 18: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

In questo caso, la funzione f risulta definita e continua in R − {0}.Inoltre, da uno studio preliminare di f nel semiasse positivo, si ha

• limλ→0f(λ) < 0

• limλ→+∞f(λ) = +∞

• f ′(λ) = eλ(1 + 0.435λ−1

λ2

)+0.435

λ2 > 0, cioe la funzione e monotona

crescente

e quindi si puo concludere che f ha un unico zero ξ nel semiasse

positivo.

17

Page 19: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1−0.5

0

0.5

1

1.5

2

λ

f(λ)

Osservando il grafico tracciato e possibile individuare un intorno di ξ;

per esempio

Intervallo di separazione: I = [a, b] = [0.05,0.15]

qquad⇒ f(a) = −0.0667, f(b) = 0.0672⇒ f(a)f(b) < 0

18

Page 20: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Problema 5: separazione grafica delle radici

1√f

+ 2log10

3.7D+

2.51

Re√f

)= 0,

Si tratta di trovare gli zeri della funzione

g(f) =1√f

+ 2log10

3.7D+

2.51

Re√f

)

Si osserva che: f > 0, limf→0+g(f) = +∞, limf→+∞g(f) = 2log10

3.7D

)< 0

Inoltre, g′(f) = − 1

2f√f

(1 + 2·2.51

Relog10(e)ε

3.7D+ 2.51

Re√

f

)< 0, ∀ f > 0

Ne segue che esiste un unico zero della funzione g(f)

0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1

f

0

10

20

30

40

50

60

70

80

90

g(f)

19

Page 21: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Problema 3: separazione delle radici - tabulazione

f(λ) = eλ + 0.435λ (eλ − 1)− 1.564 = 0

Si valuta la funzione in corrispondenza di valori equidistanti della va-

riabile λ in un certo intervallo e si osserva il segno dei valori ottenuti:

λ f(λ)0.10 -0.001335588295280.12 0.025672938554610.14 0.053195959592180.16 0.081243551500790.18 0.109825990666180.20 0.13895375715854

Intervallo di separazione: I = [a, b] = [0.10,0.12]

qquad⇒ f(a) = −0.0013, f(b) = 0.0257⇒ f(a)f(b) < 0

20

Page 22: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Problema 5: separazione delle radici - tabulazione

1√f

+ 2log10

3.7D+

2.51

Re√f

)= 0,

Si valuta la funzione in corrispondenza di valori equidistanti della va-

riabile f in un certo intervallo e si osserva il segno dei valori ottenuti:

f g(f)0.0050 6.46700.0100 2.08820.0150 0.12350.0200 -1.0580

Intervallo di separazione: I = [a, b] = [0.015,0.02]

⇒ g(a) = 0.1235, g(b) = −1.0580⇒ g(a)g(b) < 0

21

Page 23: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Separazione delle radici: esempio 1

Equazioni polinomiali: p4(x) = x4 + 2x3 + 7x2 − 11 = 0

−10 −5 0 5 10−2000

0

2000

4000

6000

8000

10000

12000

14000

x

p4(x)

−2 −1.5 −1 −0.5 0 0.5 1 1.5 2−20

−10

0

10

20

30

40

50

x

p4(x)

ξ1 ξ

2

• •

Restringendo l’intervallo di osservazione si identificano meglio le due

radici reali

Delle 4 radici di p4(x) due sono reali, ξ1 ∈ [−1.5,−1] eξ2 ∈ [0.75,1.25], mentre due sono complesse coniugate.

22

Page 24: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Separazione delle radici: esempio 2Equazione trascendente: f(x) = tgx(1− cosx)− 2 = 0

L’equazione f(x) = 0 si puo riscrivere come 1− cosx = 2cotgx.

In questo modo e possibile risolvere il problema equivalente

h(x) = g(x)

corrispondente a determinare i punti di intersezione delle funzionih(x) = 2cotgx e g(x) = 1− cosx

00

g(x)=1−cos(x)

h(x)=2cotg(x)

Esistono infinite soluzioni

ξk ∈ (kπ, (2k + 1)π2), k ∈ Z

23

Page 25: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Separazione delle radici: esempio 3 (Problema 4)

Equazione trascendente: f(x) = cosx coshx+ 1 = 0

La funzione f(x) e simmetrica rispetto all’origine

⇒ se ξ e radice lo e anche − ξ

⇒ si considera il caso x > 0 (ξ = 0 e radice banale)

Nota cosh(x) = ex+e−x2 .

24

Page 26: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Metodo di bisezione (o metodo dicotomico)

Il metodo di bisezione e un metodo molto semplice:

una volta individuato un intervallo di separazione in cui sitrova una sola radice, permette di costruire una succes-sione {xk} di approssimazioni di ξ.

25

Page 27: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Ipotesi di applicabilita :

• e stato separato un intervallo I = [a, b] in cui c’e un’unica radice ξ;

• la funzione f e continua in I: f ∈ C0[a, b];

• f(a)f(b) < 0.

x

• ξ

a b

f(x)

26

Page 28: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Metodo di bisezione: algoritmo

Si genera una successione

di approssimazioni {xk} con

xk ∈ [ak−1, bk−1] e

ξ ∈ [ak−1, bk−1].• ξ

a0

b1=b

0

f(x)

x

x1

a2=a

1

• x

2

b2

x3

Algoritmo:

a0 = a, b0 = b

per k = 1,2,3, ...

per xk =ak−1+bk−1

2 (punto medio di [ak−1, bk−1])

per se f(xk) = 0, allora stop

per se f(ak−1)f(xk) < 0, allora [ak, bk] = [ak−1, xk]

per se f(xk)f(bk−1) < 0, allora [ak, bk] = [xk, bk−1]

27

Page 29: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Convergenza del metodo di bisezione

Errore di troncamento: ek = ξ − xke l’errore che si commette approssimando la radice ξ con il k-esimo elemento della

successione costruita usando l’algoritmo descritto precedentemente.

Il procedimento iterativo converge alla radice ξ se la suc-

cessione {xk} converge a ξ per k → +∞

Convergenza: limk→∞xk = ξ ⇔ lim

k→∞|ek| = 0

28

Page 30: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Per il metodo di bisezione si ha

q • • • •q ak−1 xk ξ bk−1

Alla k − esima iterazione ξ ∈ [xk, bk−1] oppure ξ ∈ [ak−1, xk].

Ne segue che |ek| < bk−1−ak−12 .

Inoltre, considerando che l’ ampiezza dell’ intervallo [ak−1, bk−1] e pari

alla meta dell’ampiezza dell’intervallo [ak−2, bk−2] costruito all’iterazione

precedente, si ha

|ek| <bk−1 − ak−1

2=bk−2 − ak−2

22= · · · = b− a

2k

e quindi

0 ≤ limk→∞

|ek| < limk→∞

b− a2k

= 0

29

Page 31: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Ordine di convergenza

Sia {xk} una successione di approssimazioni conver-

gente a ξ. La successione ha ordine di convergenza p e

fattore di convergenza C, se esistono due reali p ≥ 1 e

C > 0 tali che

limk→∞

|ek+1||ek|p

= C

Nota. La convergenza si dice lineare se p = 1,

Nota. quadratica se p = 2.

30

Page 32: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Metodo di bisezione: ordine di convergenza

Per k →∞ si ha|ek+1||ek|1 '

b−a2k+1b−a2k

= 2k

2k+1 = 12.

⇒ Ordine di convergenza: 1 (lineare)

⇒ Fattore di convergenza: 12

La convergenza e lenta, in quanto ad ogni passo l’errore

viene dimezzato, cioe ad ogni passo si guadagna una cifra

binaria

⇒ poiche 2−4 < 10−1 < 2−3, per guadagnare una

⇒ cifra decimale servono 3-4 iterazioni.

31

Page 33: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Metodo di bisezione: criteri di arresto

Nella pratica, a causa degli errori di arrotondamento

e degli errori di troncamento non si verifica mai che

f(xk) = 0. Quando si arrestano le iterazioni?

Criteri di arresto a posteriori

|ek| ' |xk − xk−1| < ε

|f(xk)| < ε

32

Page 34: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Criteri di arresto a posteriori: esempi

|ek| ' |xk − xk−1| < ε oppure |f(xk)| < ε

• ξ

a b

f(x)

x

xk

• ξ

a

f(x)

x b

xk

f(xk) e ”grande” anche se

xk e ”vicino” a ξ

f(xk) e ”piccolo” anche

se xk e ”lontano” da ξ

33

Page 35: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Criterio di arresto a priori:

Usando l’espressione dell’errore di troncamento, e possibile

dare una stima a priori del numero di iterazioni K neces-

sario per ottenere un errore minore di ε. Infatti, risulta

|ek| <b− a

2k< ε ⇒ K >

log(b− a)− log(ε)

log 2

Oss.: Poiche K deve essere un numero intero positivo, puo essere posto uguale

all’intero piu grande e piu vicino alla quantita a secondo membro dell’ultima dise-

quazione.

34

Page 36: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Soluzione Problema 3

Si vuole usare il metodo di bisezione per calcolare la radice dell’equazione

f(λ) = eλ + 0.435λ (eλ − 1)− 1.564 = 0 in I = [a, b] = [0.05,0.15]

k ak−1 bk−1 xk |xk − xk−1| |f(xk)|1 0.05000000000000 0.15000000000000 0.10000000000000 10.00000000000000 10.00000000000000

2 0.10000000000000 0.15000000000000 0.12500000000000 0.02500000000000 0.03250506973938

3 0.10000000000000 0.12500000000000 0.11250000000000 0.01250000000000 0.01548498364220

4 0.10000000000000 0.11250000000000 0.10625000000000 0.00625000000000 0.00704990930651

5 0.10000000000000 0.10625000000000 0.10312500000000 0.00312500000000 0.00285098217571

6 0.10000000000000 0.10312500000000 0.10156250000000 0.00156250000000 0.00075615469668

7 0.10000000000000 0.10156250000000 0.10078125000000 0.00078125000000 0.00029010206821

8 0.10078125000000 0.10156250000000 0.10117187500000 0.00039062500000 0.00023292996053

9 0.10078125000000 0.10117187500000 0.10097656250000 0.00019531250000 0.00002861013771

10 0.10097656250000 0.10117187500000 0.10107421875000 0.00009765625000 0.00010215388987

11 0.10097656250000 0.10107421875000 0.10102539062500 0.00004882812500 0.00003677037077

35

Page 37: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Dalla tabella e possibile osservare che se si sceglie ε = 0.5 · 10−4 e

si usa come criterio di arresto |f(xk)| < ε, il procedimento iterativo si

interrompe quando k = 9.

Scegliendo come criterio di arresto |xk − xk−1| < ε, il procedimento

iterativo si arresta quando k = 11.

E’ possibile osservare che per k = 11 e soddisfatta anche la condizione

|f(xk)| < ε.

Usando, invece, si usa il criterio di arresto a priori, si ha

K > log2(0.10)− log2(0.5 · 10−4) ≈ 10.9658

cioe K ≥ 11,

36

Page 38: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Soluzione Problema 5Si vuole usare il metodo di bisezione per calcolare la radice dell’equazione

1√f

+ 2log10

(0.0001

3.7+ 2.51

300000√f

)= 0 in I = [a, b] = [0.015,0.02]

k ak−1 bk−1 xk |xk − xk−1| |f(xk)|1 0.015000000000000 0.020000000000000 0.017500000000000 0.002500000000000 0.5295939983164872 0.015000000000000 0.017500000000000 0.016250000000000 0.001250000000000 0.2215647509755953 0.015000000000000 0.016250000000000 0.015625000000000 0.000625000000000 0.0541106525369294 0.015000000000000 0.015625000000000 0.015312500000000 0.000312500000000 0.0333689386692915 0.015312500000000 0.015625000000000 0.015468750000000 0.000156250000000 0.0106965846065196 0.015312500000000 0.015468750000000 0.015390625000000 0.000078125000000 0.0112537215871177 0.015390625000000 0.015468750000000 0.015429687500000 0.000039062500000 0.0002580839788518 0.015429687500000 0.015468750000000 0.015449218750000 0.000019531250000 0.0052243553975259 0.015429687500000 0.015449218750000 0.015439453125000 0.000009765625000 0.002484413980264

10 0.015429687500000 0.015439453125000 0.015434570312500 0.000004882812500 0.00111348481891911 0.015429687500000 0.015434570312500 0.015432128906250 0.000002441406250 0.00042778040592712 0.015429687500000 0.015432128906250 0.015430908203125 0.000001220703125 0.00008486821393213 0.015429687500000 0.015430908203125 0.015430297851563 0.000000610351562 0.00008660288187214 0.015430297851563 0.015430908203125 0.015430603027344 0.000000305175781 0.00000086608388515 0.015430603027344 0.015430908203125 0.015430755615234 0.000000152587891 0.00004200137753716 0.015430603027344 0.015430755615234 0.015430679321289 0.000000076293945 0.00002056772495417 0.015430603027344 0.015430679321289 0.015430641174316 0.000000038146973 0.00000985084006918 0.015430603027344 0.015430641174316 0.015430622100830 0.000000019073486 0.00000449238297419 0.015430603027344 0.015430622100830 0.015430612564087 0.000000009536743 0.00000181315076620 0.015430603027344 0.015430612564087 0.015430607795715 0.000000004768372 0.000000473533746

37

Page 39: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Dalla tabella e possibile osservare che se si sceglie ε = 0.5 · 10−8 e si

usa come criterio di arresto |xk− xk−1| < ε, il procedimento iterativo si

arresta quando k = 20.

Al contrario, se si usa come criterio di arresto |f(xk)| < ε, 20 iterazioni

non sono sufficienti per raggiungere la precisione richiesta.

Usando, invece, si usa il criterio di arresto a priori, si ha

K > log2(0.10)− log2(0.5 · 10−4) ≈ 19.931568569324174

cioe K ≥ 20,

38

Page 40: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Esercizio 1

Esempio 3.2.1 (Libro) Stabilire quante radici ammette l’equazione

f(x) = log(x+ 1) +√x+ 2− 1 = 0.

Soluzione La funzione e definita e continua nell’intervallo (−1,+∞).

Inoltre

limx→−1f(x) = −∞ < 0, limx→+∞f(x) = +∞ > 0.

Pertanto, se lo zero esiste, allora e unico.

Poiche f ′(x) = 1x+1 + 1

2√x+2

> 0, la funzione e monotona nel suo

dominio di definizione e quindi ha un unico zero in (−1,+∞).

Infine, si osserva che ∀ x ≥ 0 f(x) > 0, quindi lo zero di f sicuramente

appartiene all’intervallo (−1,0].

Poiche f(−1/2) < 0, si puo scegliere I = [a, b] = [−1/2,0] come inter-

vallo di separazione.

39

Page 41: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Applicando il metodo di bisezione si ha

x1 = a0+b02 = −1/2

2 = −14

f(a0) = −0.468f(b0) = +0.414f(x1) = +0.035

⇒ a1 = a0b1 = x1

x2 = a1+b12 = −1/2−1/4

2 = −38

f(a1) = −0.468f(b1) = +0.035f(x2) = −0.195

⇒ a2 = x2b2 = b1

. . . . . .

k xk f(xk) |ξ − xk|1 -0.2500000 0.0351936 0.02033362 -0.3750000 -0.1952488 0.10466643 -0.3125000 -0.0756553 0.04216644 -0.2812500 -0.0192306 0.01091645 -0.2656250 0.0082212 0.00470866 -0.2734375 -0.0054435 0.00310397 -0.2695313 0.0014040 0.00080238 -0.2714844 -0.0020160 0.00115089 -0.2705078 -0.0003050 0.0001742

40

Page 42: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Dopo 9 iterazioni, l’approssimazione prodotta produce un errore dell’ordine

di 10−3

Il numero di iterazioni K necessarie affinche la soluzione prodotta si-

curamente abbia una certa precisione ε puo essere stimato prima di

eseguire le iterazioni nel modo seguente:

K ≥ log2(b− a)− log2(ε)

con ε = 0.5 · 10−3 da cui

K > log2(0.5)− log2(0.5 · 10−3) ≈ 9.9658

cioe K ≥ 10.

Il valore di K stimato assicura che l’errore tra due approssimazioni

successive sia inferiore alla tolleranza fissata. Ovviamente, poiche K

deriva da una stima superiore dell’errore di troncamento, puo accadere

che il metodo raggiunga la precisione richiesta con un numero di ite-

razioni inferiore al valore K stimato usando la stima a priori.

41

Page 43: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Esercizio 2

Si consideri

f(x) = x3 − 10x2 + 5.

• Verificare che uno degli zeri di f(x) e contenuto nell’intervallo I =

[a, b] = [0.6,0.8].

• Indicando con ξ lo zero isolato al punto precedente, dare una stima

del numero di iterazioni necessarie per avere una approssimazione di

ξ con almeno quattro decimali esatti usando il metodo di bisezione.

• Verificare che ξ ≈ 0.7346.

42

Page 44: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Soluzione

f(x) e una funzione continua in R.

Si verifica facilmente che f(0.6) ≈ 1.616 > 0 e f(0.8) ≈ −0.888 < 0;

inoltre f ′(x) = 3x2− 20x = x(3x− 20) ≥ 0⇔ x ≤ 0∨ x ≥ 203 > 6, quindi

f(x) e sicuramente monotona decrescente in I = [0.6,0.8].

Ne segue che esiste una sola radice di f in I.

Per stimare il numero di iterazioni necessarie K si usa il criterio di

arresto a priori, cioe

K > log2(b− a)− log2(ε)

In questo caso: a = 0.6, b = 0.8, ε = 0.5 · 10−4 e quindi

K > log2(0.2)− log2(0.5 · 10−4) = log2

(2

10

10

5104

)≈ 11.9658

ovvero K ≥ 12

43

Page 45: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Applicando l’algoritmo di bisezione si ha

k ak−1 bk−1 xk xk − xk−1 f(xk)1 0.6000000000 0.80000000000 0.700000000000 0.100000000000000 0.4430000000000012 0.7000000000 0.80000000000 0.750000000000 0.050000000000000 0.2031250000000003 0.7000000000 0.75000000000 0.725000000000 0.025000000000000 0.1248281250000014 0.7250000000 0.75000000000 0.737500000000 0.012500000000000 0.0379316406250015 0.7250000000 0.73750000000 0.731250000000 0.006250000000000 0.0437531738281266 0.7312500000 0.73750000000 0.734375000000 0.003125000000000 0.0029869079589847 0.7343750000 0.73750000000 0.735937500000 0.001562500000000 0.0174533424377458 0.7343750000 0.73593750000 0.735156250000 0.000781250000000 0.0072284598350529 0.7343750000 0.73515625000 0.734765625000 0.000390625000000 0.002119586408138

10 0.7343750000 0.73476562500 0.734570312500 0.000195312500000 0.00043395818024811 0.7345703125 0.73476562500 0.734667968750 0.000097656250000 0.00084273976553212 0.7345703125 0.73466796875 0.734619140625 0.000048828125000 0.000204372205189

44

Page 46: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Esercizio 3

Si consideri

f(x;λ) = e−x − 2x− λ,con λ ∈ R.

• Determinare per quali valori del parametro λ la funzione f(x) am-

mette un unico zero nell’intervallo [0,1].

• Posto λ = −1, dare una stima del numero di iterazioni necessarie

per avere un’ approssimazione dello zero ξ con almeno tre decimali

esatti usando il metodo di bisezione.

45

Page 47: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Soluzione

f(x;λ) ∈ C∞(R). Inoltre, f ′(x;λ) < 0, ∀ x ∈ R. Pertanto, se lo zero

esiste, allora e unico.

Poiche

f(0)f(1) < 0 ⇐⇒ (1− λ)(1/e− 2− λ) < 0

segue che f(x;λ) ammette uno zero per valori di λ ∈ I =(

1e − 2,1

).

Si osserva che −1 ∈ I e che le condizioni di applicabilita del metodo di

bisezione sono verificate; dunque, applicando la condizione di arresto

a priori si ha

K > log2(1− 0)− log2(0.5 · 10−3) ≈ 10.9658.

Pertanto, K ≥ 11.

46

Page 48: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Esercizio 4

La velocita v del razzo Saturno V in volo verticale vicino la superficie

terrestre puo essere approssimata come segue

v(t) = ulogM0

M0 −mt− gt

con u = 2510m/s exhaust velocity del razzo

M0 = 2.8 · 106Kg massa del razzo al momento del lancio

m = 13.3 · 103Kg/s tasso di consumo di carburante

g = 9.81m/s accelerazione di gravita

t tempo trascorso dal lancio.

Determinare l’istante di tempo in cui il razzo raggiunge la velocita del

suono (≈ 335m/s) con precisione al millesimo di secondo.

47

Page 49: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Esercizio 5

• Scrivere il diagramma di flusso dell’algoritmo di bisezione con cri-

terio stima a priori

• Scrivere il diagramma di flusso dell’algoritmo di bisezione con cri-

terio stima a posteriori

48

Page 50: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Metodi di linearizzazione

Metodo babilonese o Metodo di Erone: fornisce un algoritmo ite-rativo (formulato gia intorno al 1700 a.C.) per il calcolo della radicequadrata di un numero a:

1. scegliere un numero x0 prossimo a√a

2. dividere a per x0

3. calcolare la media tra x0 e ax0

, cioe x1 = 12

(x0 + a

x0

)

4. ripetere i passi 2 e 3 dopo aver posto x0 = x1

L’algoritmo si puo schematizzare come seguex0 dato

xn = 12

(xn−1 + a

xn−1

), n ≥ 1

49

Page 51: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Esempio

Si vuole calcolare√

2 = 1.41421356237310 usando il Metodo ba-

bilonese x0 dato

xn = 12

(xn−1 + a

xn−1

), n ≥ 1

In questo caso a = 2 e si sceglie x0 = 1.5

x1 = 12

(1.5 + 2

1.5

)= 17

12 = 1.41666667

x2 = 12

(1.41666667 + 2

1.41666667

)= 1.41421569

x3 = 12

(1.41421569 + 2

1.41421569

)= 1.41421356

50

Page 52: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Esercizio

E’ possibile scrivere un algoritmo per il calcolo del reciproco di un

numero c senza eseguire divisioni?

51

Page 53: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Metodi di linearizzazione

Si approssima la funzione f(x) in un intorno I di ξ con la

sua tangente o con la sua secante, calcolate tramite un

opportuno sviluppo in serie di Taylor.

• Metodo di Newton-Raphson o

• metodo delle tangenti

• Metodo delle secanti

52

Page 54: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Metodo di Newton-Raphson

Approssimazione iniziale: x0

Prima iterazione:

t0 e la retta tangente a f(x)nel punto (x0, f(x0)):

t0→ y = f(x0) + f ′(x0)(x− x0)

Nuova approssimazione x1:

intersezione tra t0 e y = 0x

• ξ

a b

f(x)

x0

t0

(x0,f(x

0)) .

x1

⇒ f(x0) + f ′(x0)(x1 − x0) = 0 → x1 = x0 −f(x0)

f ′(x0)53

Page 55: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Metodo di Newton-Raphson

Nuova approssimazione: x1

Seconda iterazione:

t1 e la retta tangente a f(x)nel punto (x1, f(x1)):

t1→ y = f(x1) + f ′(x1)(x− x1)

Nuova approssimazione x2:

intersezione tra t1 e y = 0,x

ξ

a b

f(x)

x0

t0

(x0,f(x

0)) .

x1

t1

. (x1,f(x

1))

x2

⇒ f(x1) + f ′(x1)(x2 − x1) = 0 → x2 = x1 −f(x1)

f ′(x1)

54

Page 56: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Metodo di Newton-Raphson: algoritmoAd ogni iterazione k = 1,2, . . .

la nuova approssimazione xk e

data dall’intersezione tra la retta

tk−1, tangente a f(x) nel punto

(xk−1, f(xk−1)), e la retta y = 0;

cioe

tk−1→y=f(xk−1)+f ′(xk−1)(x-xk−1)x

ξ

a b

f(x)

xk−1

tk−1

(xk−1

,f(xk−1

)) .

xk

tk

. (xk,f(x

k))

xk+1

e quindi f(xk−1) + f ′(xk−1)(xk − xk−1) = 0↓

Algoritmo:

x0 dato

xk = xk−1 −f(xk−1)

f ′(xk−1), k = 1,2, . . .

55

Page 57: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Metodo di Newton-Raphson: algoritmo

Il calcolo della radice di un numero a e equivalente a trovare gli zeri

della seguente funzione

f(x) = x2 − aSe vogliamo calcolare la radice di a mediante il metodo di Newton-

Raphson, dobbiamo usare il seguente algoritmo

x0 dato

xk = xk−1 −(x2k−1 − a)

2xk−1, k = 1,2, . . .

ovvero

x0 dato

xk = 12

(xk−1 +

a

xk−1

), k = 1,2, . . .

che e proprio l’algoritmo corrispondente al metodo babilonese

56

Page 58: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Metodo di Newton-Raphson: algoritmo

Il calcolo del reciproco di un numero c e equivalente a trovare gli zeri

della seguente funzione

f(x) =1

x− c

Se vogliamo calcolare il reciproco di c mediante il metodo di Newton-

Raphson, dobbiamo usare il seguente algoritmo

x0 dato

xk = xk−1 −1

xk−1−c

− 1x2k−1

, k = 1,2, . . .

ovvero {x0 datoxk = xk−1(2− cxk−1), k = 1,2, . . .

57

Page 59: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Metodo di Newton-Raphson: convergenza

x0 dato

xk = xk−1 −f(xk−1)

f ′(xk−1), k = 1,2, . . .

Ipotesi di applicabilita :

• e stato separato un intervallo I = [a, b] in cui c’e un’unica radice ξ;

• f , f ′, f ′′ sono continue in I: f ∈ C2[a, b];

• f ′(x) 6= 0 per x ∈ [a, b]

⇒ esiste un intorno J ⊆ I di ξ tale che, se x0 ∈ J, la successione

delle approssimazioni {xk} converge a ξ.

• [ • • ]︸ ︷︷ ︸J

a ξ x0 b

Oss: il teorema garantisce solo l’esistenza di J

58

Page 60: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Metodo di Newton-Raphson: ordine di convergenza

Si vuole determinare l’ordine di convergenza del metodo di Newton-

Raphson

Ordine di convergenza p: limk→∞

|ek+1||ek|p = C

L’errore di troncamento alla k+1-esima iterazione si puo scrivere come

segue

ek+1 = ξ−xk+1 =

(ξ − f(ξ)

f ′(ξ)

)−(xk −

f(xk)

f ′(xk)

)= (ξ−xk)−

(f(ξ)

f ′(ξ)− f(xk)

f ′(xk)

)

Il valore di f(xk) si puo stimare considernado i primi tre termini dello

sviluppo in serie di Taylor attorno alla radice ξ, cioe

f(xk) = f(ξ) + f ′(ξ) (xk − ξ)︸ ︷︷ ︸−ek

+1

2f ′′(ξ)(xk − ξ)2 + ...

59

Page 61: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

mentre, supponendo che xk sia molto vicino a ξ, si puo assumere che

f ′(xk) ' f ′(ξ)

Sostituendo i valori di f(xk) e f ′(xk) cosı ottenuti nell’espressione di

ek+1 si ha

|ek+1| '∣∣∣∣∣∣ek −

f(ξ)− f(ξ) + f ′(ξ)ek − 12f′′(ξ)e2

k

f ′(ξ)

∣∣∣∣∣∣=

∣∣∣∣∣∣

12f′′(ξ)e2

k

f ′(ξ)

∣∣∣∣∣∣

da cui risulta

limk→∞

|ek+1||ek|2

=1

2

∣∣∣∣∣f ′′(ξ)f ′(ξ)

∣∣∣∣∣ ⇒ p ≥ 2

e quindi, se f(x) ∈ C3[a, b] la convergenza e almeno quadratica

60

Page 62: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Efficienza computazionale

Per valutare l’efficienza di un metodo iterativo bisogna

tener conto sia dell’ordine di convergenza che del costo

computazionale, cioe della quantita di calcoli richiesta ad

ogni passo.

Efficienza computazionale: E = p1/r

p: ordine di convergenza del metodo

r: numero di valutazioni funzionali (calcolo di

funzioni o derivate) richieste ad ogni passo

Metodo di bisezione: E = 1

(ad ogni passo si richiede una sola valutazione funzionale, f(xk), e quindi r = 1)

Metodo di Newton: E = 21/2

(ad ogni passo si richiedono due valutazioni funzionali, f(xk) e f ′(xk), e quindi r = 2)

61

Page 63: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Metodo di Newton-Raphson: esempio

Approssimare la radice ξ = 0 dell’equazione

f(x) = 4x3 − 5x = 0

con il metodo di Newton-Raphson nell’intervallo I = [−0.5,0.5] e

scegliendo come approssimazione iniziale una volta x0 = 0.5 e una

volta x0 = 0.4.

−0.5 −0.4 −0.3 −0.2 −0.1 0 0.1 0.2 0.3 0.4 0.5−2

−1.5

−1

−0.5

0

0.5

1

1.5

2

f(x)

ξ .

x

t0

a b

qqqqqqq x2k = 0.5

−0.5 −0.4 −0.3 −0.2 −0.1 0 0.1 0.2 0.3 0.4 0.5−2

−1.5

−1

−0.5

0

0.5

1

1.5

2

f(x)

ξ .

x

t0

t1

a b

qqqqqqq x2k+1 = −0.5

62

Page 64: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Si verifica facilmente che f verifica le condizioni di applicabilita del

metodo di Newton-Raphson.

Infatti, f ∈ C2(I), f ′(x) = 12x2 − 5 = 0⇐⇒ x = ±√

5√12

/∈ I.

Scegliendo x0 = 0.5 si ha una situazione di stallo e il metodo non

converge. Infatti, l’algoritmo di Newton per f e il seguente

xk = xk−1 −4x3

k−1 − 5xk−1

12x2k−1 − 5

e quindi

x1 = x0 −4x3

0 − 5x0

12x20 − 5

= 0.5 +2

−2= −0.5

x2 = x1 −4x3

1 − 5x1

12x21 − 5

= −0.5 +2

2= 0.5

63

Page 65: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Al contrario, scegliendo x0 = 0.4, il metodo converge

k xk |xk − xk−1| |f(xk)|

1 -0.16623376623377 0.56623376623377 0.81279423831355

2 0.00787190837207 0.17410567460584 0.03935759066802

3 -0.00000078059303 0.00787268896510 0.00000390296513

4 0.00000000000000 0.00000078059303 0.00000000000000

Infatti, il teorema di convergenza del metodo di Newton-Raphson as-

sicura la convergenza per ogni scelta dell’approssimazione iniziale in

un opportuno intorno J del punto ξ. Scegliendo come approssimazioni

iniziali punti che non appartengono all’intorno J, la convergenza non

puo essere garantita.

Oss: f ′′(x) = 24x = 0⇐⇒ x = 0 ∈ I.

64

Page 66: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Estremo di Fourier

Se f(x) ha concavita fissa in un intervallo I, e possibile

stabilire un criterio di scelta dell’approssimazine iniziale che

garantisce la convergenza del metodo.

Estremo di Fourier:

Data una funzione f continua e convessa in I = [a, b] con

f(a)f(b) < 0, si dice estremo di Fourier di I l’estremo

verso cui f rivolge la convessita .

Se esiste f ′′, allora l’estremo di Fourier e a o b a seconda

che f(a)f ′′(a) > 0 oppure f(b)f ′′(b) > 0.

65

Page 67: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Estremo di Fourier: esempi

f(x)

a b x

Estremo di Fourier

f ′′(x)<0 per x ∈ [a, b]{f(a)f ′′(a) > 0f(b)f ′′(b) < 0

⇒ a e estremo di Fourier

f(x)

a b x

Estremo di Fourier

f ′′(x)>0 per x ∈ [a, b]{f(a)f ′′(a) < 0f(b)f ′′(b) > 0

⇒ b e estremo di Fourier

66

Page 68: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Metodo di Newton-Raphson: convergenza

Ipotesi di applicabilita :

• f(a)f(b) < 0

• f , f ′, f ′′ sono continue in I: f ∈ C2[a, b];

• f ′(x) 6= 0 per x ∈ [a, b];

• f ′′(x) 6= 0 per x ∈ [a, b] e x0 e l’estremo di Fourier di [a, b].

⇒1) esiste un’unica radice ξ ∈ [a, b];

2) la successione delle approssimazioni{xk = xk−1 −

f(xk−1)

f ′(xk−1)

}k = 1,2, ...

e monotona e converge a ξ;

3) se f ∈ C3[a, b], la convergenza e quadratica.

67

Page 69: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Nell’esempio precedente, relativo alla funzione f(x) = 4x3 − 5x, non e

soddisfatta l’ipotesi relativa alla derivata seconda. Al contrario, per la

funzione f(x) = x3 − 10x2 + 5, considerando l’intervallo I = [0.6,0.8],

si ha

f ′′(x) = 6x− 20 = 0⇐⇒ x =10

3/∈ I

Le ipotesi del teorema sono verificate e, poiche

f ′′(0.6) =18

5− 20 < 0 f ′′(0.8) =

24

5− 20 < 0,

mentre

f(0.6) > 0 f(0.8) < 0,

l’estremo di Fourier e l’estremo b = 0.8, che quindi puo essere scelto

come approssimazione iniziale del metodo di Newton-Raphson, cioe

x0 = 0.8.

Esercizio: eseguire le iterazioni e verificare la convergenza monotona.

68

Page 70: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Problema 3: Soluzione con Metodo di Newton

f(λ) = eλ + 0.435λ (eλ − 1)− 1.564 = 0 λ ∈ I = [0.05,0.15]

• Nell’intervallo I e stato separato un unico zero

• f, f ′, f ′′ sono continue in I

• f ′(x) = eλ − 0.435λ2 (eλ − 1) + 0.435

λ eλ 6= 0 per λ ∈ I

⇒ Lo zero puo essere approssimato con il metodo delle tangenti

Inoltre f ′′(x) = eλ + 0.87λ3 (eλ − 1)− 0.87

λ2 eλ + 0.435λ eλ > 0 in I

⇒ esiste l’estremo di Fourier di I:

f(0.15)f ′′(0.15) > 0⇒ x0 = 0.15

69

Page 71: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

k xk |xk − xk−1| |f(xk)|0 0.15000000000000 10.00000000000000 0.067153546640301 0.10211384134812 0.04788615865188 0.001494979889812 0.10099851665312 0.00111532469500 0.000000785943053 0.10099792968591 0.00000058696721 0.000000000000224 0.10099792968575 0.00000000000016 0.000000000000005 0.10099792968575 0.00000000000000 0.00000000000000

Ripetere scegliendo x0 = 0.05

70

Page 72: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Problema 5: Soluzione con Metodo di Newton

Si considera l’equazione gia risolta usando il metodo di bisezione,

ovvero

g(f) =1√f

+ 2log10

3.7D+

2.51

Re√f

),

con Re = 300000, εD = 0.0001 nell’intervallo I = [0.015,0.02].

E’ stato gia osservato che g(f) e continua in questo intervallo; inoltre,

g′(f) = − 1

2f√f

1 +

2 · 2.51

Re

log10(e)ε

3.7D + 2.51Re√f

e una funzione continua in I e risulta g′(f) < 0, ∀ f > 0.

Si verifica anche che g′′(f) e una funzione continua.

Ne segue che e possibile applicare il metodo di Newton.

71

Page 73: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Inoltre, g′′(f) > 0 in I ⇒ esiste l’estremo di Fourier di I:

f(0.015)f ′′(0.015) > 0⇒ x0 = 0.015

k xk |xk − xk−1| |f(xk)|0 0.015000000000000 1.000000005000000 1.0000000050000001 0.015421702705061 0.000421702705061 0.0025023707863082 0.015430602322385 0.000008899617324 0.0000010641338853 0.015430606110170 0.000000003787786 0.000000000000194

Ripetere scegliendo x0 = 0.02

72

Page 74: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Metodi di linearizzazione

Il metodo di Newton-Raphson richiede la conoscenza della f ′(x) che

non sempre e di facile valutazione.

Metodi alternativi sono, per esempio,

• il metodo della tangente fissa: ad ogni iterazione f ′(xn) e approssi-

mato con f ′(x0)

• il metodo delle secanti con estremi variabili: f ′(xn) e approssimato

con il rapporto incrementale

• il metodo delle secanti con estremo fisso: f ′(xn) e approssimato

con il rapporto incrementale in cui un punto rimane fisso ad ogni

iterazione

73

Page 75: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Metodi di linearizzazione

Metodo di Newton-Raphson

x

ξ

a b

f(x)

xk−1

tk−1

(xk−1

,f(xk−1

)) .

xk

tk

. (xk,f(x

k))

xk+1

Ad ogni iterazione k = 1,2, . . . la

nuova approssimazione xk e data

dall’intersezione tra la retta tk−1,

tangente a f(x) nel punto(xk−1, f(xk−1)), e y = 0.

Algoritmo:

x0 dato

xk = xk−1 −f(xk−1)

f ′(xk−1), k = 1,2, . . .

Metodo delle secanti con estremi variabili

x

ξ

a b

f(x)

xk−1

sk−1

(xk−1

,f(xk−1

)) .

xk

(xk,f(x

k))

xk−2

. (x

k−2,f(x

k−2))

.

sk

xk+1

Ad ogni iterazione k = 2,3, . . . la nuova

approssimazione xk e data dalla

intersezione tra la retta sk−1, secante

f(x) nei punti (xk−2, f(xk−2)) e(xk−1, f(xk−1)), e y = 0.

Algoritmo:

x0, x1 dati

xk = xk−1 − f(xk−1)xk−1 − xk−2

f(xk−1)− f(xk−2), k ≥ 2

74

Page 76: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Metodo delle secanti

x0, x1 dati

xk = xk−1 − f(xk−1)xk−1 − xk−2

f(xk−1)− f(xk−2), k = 2, ...

Vantaggi:

• si puo usare quando non si conosce la derivata di

f(x) o quando f(x) e nota per punti

• ad ogni passo richiede una sola valutazione funzionale

Svantaggi:

• servono due approssimazioni iniziali x0 e x1

• la scelta di x0 e x1 deve essere ”accurata”

75

Page 77: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Convergenza del metodo delle secanti

Se

• e stato separato un intervallo I = [a, b] simmetrico intorno allaradice ξ,

• f , f ′, f ′′ sono continue in I: f ∈ C2[a, b],

• f ′(x) 6= 0 per x ∈ [a, b],

⇒ esiste un intorno J ⊆ I di ξ tale che, se x0, x1 ∈ J, la successionedelle approssimazioni {xk} converge a ξ con convergenza superli-neare, cioe 1 < p < 2.

Se f ′′(x) 6= 0 in I, l’ordine di convergenza e p = 1+√

52

⇒ E = p ' 1.62

76

Page 78: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Convergenza del metodo delle secantiSe f ′′(x) 6= 0 in I, allora ek+1 ≈ C

pp+1N e

pk

con p = 1+√

52 e

CN la costante asintotica del metodo di Newton (CN = f ′′(ξ)2f ′(ξ)).

Dim: Sottraendo ξ ad ambo i membri della formula di iterazione del

metodo delle secanti si ha

−ek+1 = −ek −f(xk)(xk − xk−1)

f(xk)− f(xk−1)

poiche ek−1 − ek = ξ − xk−1 − (ξ − xk) = xk − xk−1, l’uguaglianza

precedente puo essere riscritta nel modo seguente

ek+1 = ek −f(xk)(ek − ek−1)

f(xk)− f(xk−1)=f(xk)ek−1 − f(xk−1)ek

f(xk)− f(xk−1).

77

Page 79: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Mettendo a fattor comune la quantita ekek−1 e moltiplicando perxk−xk−1xk−xk−1

, risulta

ek+1 = ekek−1

f(xk)ek− f(xk−1)

ek−1

xk − xk−1

xk − xk−1

f(xk)− f(xk−1)

.

Poiche per xk−1 → xk → ξ

xk − xk−1

f(xk)− f(xk−1)→ 1

f ′(xk)→ 1

f ′(ξ)

f(xk)ek− f(xk−1)

ek−1

xk − xk−1→ −g′(xk)→ f ′′(ξ)

2,

con g(x) = −f(x)−f(ξ)x−ξ ,

e g′(x) = −f ′(x)(x−ξ)−f(x)+f(ξ)(x−ξ)2 = −f ′(x)(x−ξ)−f(x)

(x−ξ)2 → −f ′′(ξ)2

(infatti limx→ξ g′(x) = limx→ξ−f′′(x)(x−ξ)+f ′(x)−f ′(x)

2(x−ξ) = −f ′′(ξ)2 )

78

Page 80: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Quindi, per xk → ξ risulta

ek+1 = CNekek−1.(1)

D’altra parte, il metodo ha ordine di convergenza p se ek+1 ≈ Cepk,

ovvero se ek ≈ Cepk−1.

Per determinare i valori di C e p si considera

ek−1 ≈(ekC

)1p

e lo si sostituisce in eq. (1), da cui

ek+1 ≈ CN(

1

C

)1pe

1+1/pk

e quindi

Cepk ≈ CN

(1

C

)1pe

1+1/pk

79

Page 81: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

da cui

e1+1/p−pk ≈ C1+1/p

CN.

Affinche l’ultima relazione sia vera ∀ k deve accadere che

1 + 1/p− p = 0⇔ p2 − p− 1 = 0⇔ p =1±√5

2,

di cui si considera solo la soluzione positiva.

In corrispondenza del valore di p trovato si ha

1 ≈ C1+1/p

CN,

da cui

C = Cp

1+pN .

80

Page 82: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Esercizio: Quale e l’ordine di convergenza del metodo delle secanti

se usato per il calcolo dello zero di f(x) = x3 − 10x2 + 5 contenuto

nell’intervallo I = [0.6,0.8]?

81

Page 83: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Esercizio 1

Data l’equazione non lineare

f(x) = x3 + α− cosx = 0

1. individuare per quali valori di α ∈ R l’equazione non ammette radici positive

2. per α =1

3separare la radice piu piccola ξ

3. fornire una stima a priori del numero di iterazioni necessarie per approssimare ξcon un errore inferiore a ε = 10−6 tramite il metodo di bisezioni;

4. quante iterazioni sono necessarie per approssimare con la stessa tolleranza ε laradice ξ tramite il metodo di Newton?

82

Page 84: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Traccia della soluzione

1) Tracciando qualitativamente i grafici delle funzioni

y = g(x) = x3 + α y = h(x) = cosx,

si deduce che se α ≥ 1, la funzione f(x) non ha zeri positivi.

−2 −1.5 −1 −0.5 0 0.5 1 1.5 2−0.5

0

0.5

1

1.5

x

h(x) = cos(x) g(x) = x3

g(x) = x3+0.5

g(x) = x3+1

g(x) = x3+1.2

83

Page 85: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

2) L’intervallo [0,1] contiene l’unica radice positiva dell’equazione

f(x) = x3 + 1/3− cosx = 0

Infatti

f(0) = −2/3 < 0, f(1) = 4/3− cos(1) > 0 ⇒ f(0)f(1) < 0

e inoltre

f ′(x) = 3x2 + sin(x) > 0 per x ∈ (0,1]

84

Page 86: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

3) Nell’intervallo [0,1] sono verificate le ipotesi di applica-

bilita del metodo di bisezioni.

Quindi il numero di iterazioni K per cui |eK| ≤ ε si ricava

dalla relazione

|eK| = |ξ − xK| ≤b− a2K

≤ ε

⇒ K >log(b− a)− log ε

log 2.

In questo caso a = 0, b = 1, ε = 10−6

⇒K >log(1)− log 10−6

log 2≈ 19.9320 ⇒K ≥ 20.

85

Page 87: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

4) Nel caso dei metodi di Newton e delle secanti si possono verificarele ipotesi di applicabilita nell’intervallo [0,1]:

• nell’intervallo I e stato separato un unico zero

• f, f ′, f ′′ sono continue in I

• f ′(x) = 3x2 + sin(x) > 0 per x ∈ J ⊂ I, J = [δ,1] con 0 < δ << 1

• f ′′(x) = 6x+ cos(x) > 0 per x ∈ I

⇒ l’estremo b = 1 e l’estremo di Fourier dell’intervallo J.Il numero di iterazioni si puo calcolare eseguendo le iterate.

In alternativa, l’approssimazione iniziale si puo scegliere come la soluzionestimata eseguendo un’iterazione del metodo di bisezione, ovvero x0 =12. (OSS: non e garantita la convergenza!)

86

Page 88: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

k xk (bisez.) |xk − xk−1| xk (Newton) |xk − xk−1| xk (secanti) |xk − xk−1|1 0.500000000 1. 0., 1.2 0.750000000 0.25e+0 0.793560583 0.21e+0 0.456715571 0.54e+03 0.625000000 0.12e+0 0.742925006 0.51e-1 0.658587384 0.20e+04 0.687500000 0.62e-1 0.739971453 0.29e-2 0.775393863 0.12e+05 0.718750000 0.31e-1 0.739961685 0.98e-5 0.736625691 0.39e-16 0.734375000 0.16e-1 0.739961685 0.11e-9 0.739832822 0.32e-27 0.742187500 0.78e-2 0.739962167 0.13e-38 0.738281250 0.39e-2 0.739961685 0.48e-69 0.740234375 0.19e-2

10 0.739257812 0.97e-311 0.739746097 0.49e-312 0.739990234 0.24e-313 0.739868164 0.12e-314 0.739929199 0.61e-415 0.739959717 0.30e-416 0.739974976 0.15e-417 0.739967346 0.76e-518 0.739963531 0.38e-519 0.739961624 0.19e-520 0.739962578 0.95e-6

87

Page 89: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Problema 5: Soluzione con Metodo delle secanti

Si considera l’equazione gia risolta usando il metodo di Newton, ovvero

g(f) =1√f

+ 2log10

3.7D+

2.51

Re√f

),

con Re = 300000, εD = 0.0001 nell’intervallo I = [0.015,0.02].

Sono state gia verificate le ipotesi di applicabilita del metodo in quantocoincidono con quelle del metodo di Newton. Inoltre, poiche g′′(f) 6= 0,l’ordine di convergenza del metodo e p = 1+

√5

2 .

Scegliendo come punti iniziali gli estremi dell’intervallo I = [0.015,0.02],si ha

k xk |xk − xk−1| |f(xk)|1 0.015522705809256 0.004477294190744 0.0257610224161822 0.015410972287190 0.000111733522066 0.0055210698278203 0.015430692469990 0.000019720182800 0.0000242616687104 0.015430606191191 0.000000086278799 0.0000000227617075 0.015430606110170 0.000000000081021 0.000000000000092

88

Page 90: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Il numero di iterazioni necessario per raggiungere la precisione richiesta

e maggiore di quello richiesto dal metodo di Newton ma molto piu basso

di quello richiesto dal metodo di bisezione.

Page 91: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Esercizio 1.6L. Gori, M.L. Lo Cascio, F. Pitolli, Esercizi di Calcolo Numerico, II ed.

Data l’equazione dipendente da un parametro positivo α

f(x, α) = αex√x− 1 = 0

determinare i valori di α per i quali f ha una radice in I = [0.01,1];

detto A l’insieme di tali valori, si consideri α ∈ A e si discuta con quali

modalita va applicato il metodo di Newton-Raphson per approssimare

detta radice.

89

Page 92: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Soluzione Il dominio di esistenza di f e dato da x ≥ 0, ∀ α.

Inoltre, risulta

f(0) = α · e0 · 0− 1 = −1, limx→+∞

f(x) = +∞e

f ′(x) = α

(ex√x+

ex

2√x

)= αex

(2x+ 1

2√x

)> 0 ∀x > 0

Infatti

ex > 0 ∀x, √x > 0 ∀x > 0 e 2x+ 1 > 0 ∀x > −1

2Quindi, f e una funzione monotona crescente.

90

Page 93: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Poiche risulta

f(0.01) = α · e0.01

10− 1 e f(1) = αe− 1

affinche f abbia la sua unica radice in I deve accadere

f(0.01) < 0 mentre f(1) > 0,

(f e monotona crescente) cioe

α · e0.01

10− 1 < 0 e αe− 1 > 0

da cui deriva1

e< α <

10

e0.01

91

Page 94: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Per poter applicare il Metodo di Newton-Raphson e soprattutto per

essere certi che il metodo converga alla radice cercata, e necessario che

f, f ′, f ′′ siano funzioni continue in I, che f ′(x) 6= 0 e f ′′(x) 6= 0, ∀x ∈ I.

Sicuramente f e f ′ sono funzioni continue in I, inoltre la monotonia di

f garantisce che f ′(x) 6= 0 in I.

Per quanto riguarda f ′′, invece, si ha

f ′′(x) = αex(

2x+ 1

2√x

)+ αex

(1

2√x− 1

4x√x

)=

αex

2√x

4x2 + 4x− 1

2x

che risulta continua in I ma

92

Page 95: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

f ′′(x) = 0⇔ 4x2 + 4x− 1 = 0⇔ x =−1±√2

2.

Poiche la soluzione positiva (cioe x = −1+√

22 ) appartiene all’intervallo

I, la convergenza del metodo non e garantita per qualsiasi scelta del

punto iniziale x0.

93

Page 96: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

In questo caso, puo accadere che nella successione delle approssi-

mazioni prodotte siano compresi punti che non appartengono all’intervallo

I, come, per esempio, scegliendo x0 = 0.38 e α = 8.

k xk ek f(xk)1 0.008062568849982 0.371937431150018 0.275850501413549

La tangente alla funzione f nel punto x0 interseca l’asse delle ascisse

nel punto x1 = 0.008062568849982 /∈ I

94

Page 97: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Inoltre, per alcune scelte di α e x0, come per esempio α = 8 e x0 = 0.1,il punto di intersezione puo non appartenere al dominio di esistenzadella funzione stessa!!! x1 = −0.007 < 0

0 0.05 0.1 0.15 0.2 0.25 0.3−1

0

1

2

3

4

5

6f(x)

retta tangente a f in x0

y=0

In questi casi e necessario cambiare la scelta del punto iniziale. Peresempio, si puo calcolare l’approssimazione prodotta dal metodo dibisezione dopo poche iterazioni (o quando si raggiunge una certa pre-cisione) e usarla come punto iniziale per il metodo di Newton.

95

Page 98: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Per esempio, dopo quattro iterazioni del metodo di bisezione (ε =

0.5 · 10−1)

k ak bk xk ek f(xk)1 0.01 0.505000 0.2575000 0.2475000 4.2518151633148022 0.01 0.257500 0.1337500 0.1237500 2.3444427744240023 0.01 0.133750 0.0718750 0.0618750 1.3045908418829054 0.01 0.071875 0.0409375 0.0309375 0.686279560806184

si ottiene x4 = 0.0409375 che, usato come punto iniziale nel metodo

di Newton produce

k xk ek f(xk)1 0.010137854601102 0.030799645398898 0.1862971625761472 0.014687723854149 0.004549869253046 0.0161111616778583 0.015155019259722 0.000467295405573 0.0001151812384804 0.015158408093962 0.000003388834240 0.0000000058642685 0.015158408266516 0.000000000172555 0.0000000000000006 0.015158408266517 0.000000000000000 0.000000000000000

96

Page 99: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Al contrario, per altre scelte sia di α che del punto iniziale x0, come

per esempio x0 = 0.5 e α = 1, il metodo converge alla soluzione in

poche iterazioni

k xk ek f(xk)1 0.428881942480353 0.071118057519647 0.0056108294114382 0.426305773395493 0.002576169084861 0.0000065672828343 0.426302751011004 0.000003022384489 0.0000000000089984 0.426302751006863 0.000000000004141 0.0000000000000005 0.426302751006863 0.000000000000000 0.000000000000000

97

Page 100: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Osserviamo, infine, che scegliendo

α =1

e−1+

√2

2

√−1+

√2

2

,

la radice di f e il suo punto di flesso (la derivata seconda si annulla in

questo punto) e l’ordine di convergenza del metodo di Newton aumenta

essendo almeno 3.

98

Page 101: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Esercizio

Data l’equazione non lineare

h(y; ξ) = (ξ − 1) e√y − 1 = 0 ,

dove ξ e un parametro reale.

1. Determinare i valori di ξ per cui l’equazione ha una radice nell’intervallo

I = [0.02,1.02];

2. per i valori di ξ individuati al punto precedente, verificare se il

metodo delle tangenti e adatto ad approssimare la radice in I.

Specificare la scelta dell’approssimazione iniziale e l’ordine di con-

vergenza del metodo.

99

Page 102: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Soluzione del punto 1)

La funzione e ben definita per y ≥ 0.

Inoltre si osserva che, poiche

e√y > 0 ∀ y ≥ 0

l’uguaglinaza

(ξ − 1) e√y = 1

non puo essere mai verificata per valori di ξ ≤ 1

Si osserva anche che, e√y ≥ 1 ∀ y ≥ 0, e quindi l’uguaglianza

(ξ − 1) e√y = 1 non e mai verificata per ξ > 2.

Infine, per ξ = 2, lo zero di h(y; 2) e proprio y = 0 /∈ I.

Sicuramente gli eventuali valori di ξ per cui la funzione h ammette unozero in I soddisfano la seguente condizione

1 < ξ < 2

100

Page 103: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

D’altra parte,

h′(x; ξ) = (ξ − 1)e√y

2√y> 0, ∀y > 0 ξ > 1,

quindi, h(y; ξ) e una funzione monotona crescente per ∀y > 0 ξ > 1,

e se ammette uno zero in I, questo e anche unico.

Affinche abbia uno zero nell’intervallo I, deve accadere

h(0.02; ξ) < 0 h(1.02; ξ) > 0

cioe

(ξ − 1)e√

0.02 − 1 < 0 (ξ − 1)e√

1.02 − 1 > 0

da cui

ξ <1

e√

0.02+ 1 ≈ 1.8681 ξ >

1

e√

1.02+ 1 ≈ 1.3642.

Possiamo, dunque, concludere che per 1e√

1.02+ 1 < ξ < 1

e√

0.02+ 1 la

funzione h(y; ξ) ammette un unico zero nell’intervallo I = [0.02,1.02].

101

Page 104: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Soluzione del punto 2) In corrispondenza dei valori del parametro ξ

determinati al punto precedente e per y ∈ I e possibile verificare che

h(y; ξ) ∈ C2(I) e che h′(y; ξ) 6= 0. Pertanto, e possibile applicare il

metodo di Newton. Inoltre, poiche

h′′(y; ξ) =ξ − 1

4

e√y

y

(1− 1√

y

),

risulta

h′′(y; ξ) = 0⇔ y = 1 ∈ I.Ne segue che la condizione h′′(y; ξ) 6= 0 non e soddisfatta e, dunque,

non sono verificate le ipotesi del teorema di convergenza scegliendo

l’estremo di Fourier come approssimazione iniziale. Tuttavia, si puo

osservare che y = 1 e lo zero della funzione h(y; 1 + 1/e). In questo

caso l’ordine di convergenza del metodo di Newton e maggiore di 2. Al

contrario, in corrispondenza degli altri valori ammissibili del parametro

ξ, la convergenza e quadratica in quanto sicuramente CN 6= 0

102

Page 105: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

EsercizioSi consideri l’equazione non lineare log(x) + x2 − x = 0.

1. Mostrare che l’equazione ammette un’unica radice e che quest’ultima e con-tenuta nell’intervallo I = [0.7,2.3].

2. Applicare, se possibile, due passi del metodo di bisezione.

3. Detta x0 l’approssimazione prodotta al passo precedente, eseguire, se possibile,un passo dell’algoritmo del metodo di Newton-Raphson e sia x1 l’approssimazioneprodotta.

4. Applicare, se possibile il metodo delle secanti usando x0 e x1, determinate aipunti 2) e 3), come approssimazioni iniziali e interrompere l’esecuzione quandola approssimazione prodotta ha 5 decimali esatti.

5. Calcolare la costante asintotica di convergenza del metodo delle secanti.

103

Page 106: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Esercizi

1. Approssimare la radice negativa piu prossima allo zero dell’equazione

non lineare sin(x)−xex = 0 usando il metodo di Newton-Raphson e

isolando lo zero in modo che si possa scegliere l’estremo di Fourier

come approssimazione iniziale. L’approssimazione prodotta deve

avere almeno due decimali esatti.

2. Scrivere il diagramma di flusso per il metodo di Newton usando le

due condizioni di arresto a posteriori.

3. Ripertere l’esercizio precedente per il metodo delle secanti.

104

Page 107: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Metodi iterativi a un punto (o del punto unito)Un metodo iterativo a un punto in IR ha la forma:{x0 datoxn = ϕ(xn−1), n = 1,2, ...

La funzione ϕ e detta funzione di iterazione.

Nota. Per il metodo di Newton ϕ(x) = x− f(x)

f ′(x)

Convergenza

Il metodo e convergente se la successione delle approssimazioni

{xn = ϕ(xn−1)}n≥1 verifica

limn→∞|ξ − xn| = 0 ⇔ lim

n→∞xn = ξ

Criterio di arresto

Se il metodo e convergente, una buona approssimazione di ξ e data

dal valore xN per il quale |xN − xN−1| ≤ ε

105

Page 108: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Metodo del punto unito

Il metodo del punto unito consiste nel riscrivere l’equazione non

lineare di partenza in una forma equivalente:

f(x) = 0 ⇔ x = ϕ(x)

Se ξ e radice di f allora e punto unito di ϕ:

f(ξ) = 0 ⇔ ξ = ϕ(ξ)

Nota. Trovare il punto unito di ϕ significa trovare l’ascissa del punto

di intersezione tra la retta y = x e la curva y = ϕ(x).

Una funzione puo avere piu di un punto unito, solo uno o nessuno.

106

Page 109: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Metodo del punto unito: Esempio 1

Trovare i punti uniti della funzione di iterazione

ϕ(x) = x2 − 2 per −2 ≤ x ≤ 3.

Si tratta di trovare i valori di x per i quali

ϕ(x) = x2 − 2 = x ⇒ f(x) = x2 − x− 2 = 0

Ci sono due punti uniti:

ξ1 = −1 ⇒ ϕ(−1) = (−1)2 − 2 = −1

ξ2 = 2 ⇒ ϕ(2) = (2)2 − 2 = 2

−3 −2 −1 0 1 2 3−3

−2

−1

0

1

2

3

4

5

6

7

x

ξ1

ξ2

y=φ(x)

y=x

Nota. ξ1 e ξ2 sono anche le soluzioni di f(x) = x2 − x− 2 = 0

107

Page 110: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Convergenza: condizione necessaria

Teorema 1. Se la successione{x0 datoxn = ϕ(xn−1), n = 1,2, ...

e convergente a un valore τ e ϕ e continua in τ ⇒ τ e punto

unito di ϕ, cioe τ = ϕ(τ).

Dimostrazione.

τ = limn→∞ xn = lim

n→∞ ϕ(xn−1) = ϕ(

limn→∞ xn−1

)= ϕ(τ)

↓xn converge

↓ϕ e continua

108

Page 111: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Interpretazione grafica: metodo del punto unito

00

x0

x1

x2ξ

φ(x0)

φ(x1)

y=φ(x)

y=x

x1 e l’ascissa del punto di intersezione della retta y = ϕ(x0) con laretta y = x

x2 e l’ascissa del punto di intersezione della retta y = ϕ(x1) con laretta y = x

. . . . . . . . . . . .

109

Page 112: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Metodo del punto unito: Esercizio

Verificare che l’equazione f(x) = x3 + 4x2 − 10 = 0 ha

un’unica radice in [1,2] e trovare un’opportuna funzione

di iterazione per approssimarla.

Soluzione. f ∈ C∞(R), f ′(x) = 3x2 + 8x > 0 ∀ x ∈ [1,2]

⇒ f(x) emonotona

crescente⇒

min1≤x≤2 f(x) = f(1) = −5 < 0max

1≤x≤2f(x) = f(2) = 14 > 0

⇒ esiste una radice in [1,2] e,

per la monotonia, e unica

1 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 2−6

−4

−2

0

2

4

6

8

10

12

14

f(x)

x ξ

110

Page 113: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Esercizio: funzioni di iterazione

Per trovare una funzione di iterazione bisogna operare sull’equazione

x3 + 4x2 − 10 = 0

1)Isolo il termine in x2

x2 =1

4(10− x3) ⇒ x = +

1

2(10− x3)1/2 = ϕ1(x)

2)Isolo il termine in x3

x3 = 10− 4x2 ⇒ x = (10− 4x2)1/3 = ϕ2(x)

3)Aggiungo− x ad ambo i membrix3 + 4x2 − 10− x = −x ⇒ x = x− x3 − 4x2 + 10 = ϕ3(x)

4)Divido per x e isolo il termine in x2

x3 + 4x2 − 10

x= 0 ⇒ x =

(10

x− 4x

)1/2= ϕ4(x)

5)Metodo di Newton

x− f(x)

f ′(x)= x ⇒ x = x− x

3 + 4x2 − 10

3x2 + 8x= ϕ5(x)

111

Page 114: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Metodo delle approssimazioni successive

{x0 = 1.5xn = ϕ(xn−1) n = 1,2,3, ...

Iter xn = ϕ5(xn−1) xn = ϕ3(xn−1)1 1.50000000000000 1.5000000000002 1.37333333333333 -0.8750000000003 1.36526201487463 6.7324218750004 1.36523001391615 -469.7200120016935 1.36523001341410 1.03× 108

6 1.36523001341410

converge diverge

112

Page 115: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Iter xn = ϕ1(xn−1) xn = ϕ2(xn−1) xn = ϕ4(xn−1)1 1.500000000 1.500000000 1.5000000002 1.286953768 1.000000000 0.8164965813 1.402540803 1.817120593 2.9969088064 1.345458374 -1.474794991 0.000000000 – 2.941235061i5 1.375170253 1.091370196 2.753622388 + 2.753622388i6 1.360094193 1.736427733 1.814991519 – 3.534528790i7 1.367846968 -1.272545596 2.384265848 + 3.434388064i8 1.363887003 1.521542585 2.182771900 – 3.596879228i9 1.365916733 0.904354471 2.296997587 + 3.574104462i

10 1.364878217 1.887879630 2.256510286 – 3.606561220i11 1.365410061 -1.62061324 2.279179049 + 3.601936572i12 1.365137821 -0.79662594 2.271142587 – 3.608371470i13 1.365277208 1.954082914 2.275631311 + 3.607451621i14 1.365205850 -1.74063131 2.274039927 – 3.608725567i15 1.365242384 -1.28446791 2.274928362 + 3.608543344i16 1.365223680 1.503778436 2.274613384 – 3.608795481i17 1.365233256 0.984632264 2.274789213 + 3.608759411i18 1.365228353 1.829353811 2.274726876 – 3.608809311i19 1.365230863 -1.50164877 2.2747616734 + 3.60880217i20 1.365229578 0.993357253 2.274749337 – 3.608812048i...25 1.365230029 -1.373190473 2.274754931 + 3.608812641i...30 1.365230013 1.092266409 2.274754877 – 3.608812723i

converge non converge non converge

113

Page 116: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Convergenza: condizione sufficiente (1)

Teorema 2. Se ϕ e derivabile in I = [a, b] e

i) ϕ : I → I ⇔ a ≤ minx∈I ϕ(x) ≤ maxx∈I ϕ(x) ≤ b

ii) ∃ k ∈ (0,1) tale che |ϕ′(x)| ≤ k, x ∈ I

⇒ α) esiste un unico punto unito ξ ∈ I di ϕ(ξ)

β) la successione xn = ϕ(xn−1) e convergente a ξ

per ogni approssimazione iniziale x0 ∈ I

114

Page 117: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Dimostrazione dell’esistenza

Poiche i) ϕ : I → I ⇒ ϕ(a) ≥ a ϕ(b) ≤ bSe vale una delle uguaglianze

⇒ ∃ almeno un punto unito

Altrimenti si pone F (x) := x− ϕ(x) con F ∈ C(I)

⇒ F (a)= a− ϕ(a) < 0 e F (b)= b− ϕ(b) > 0

⇒ ∃ almeno uno zero di F (x)

(∃ ξ : F (ξ) = 0, cioe ξ − ϕ(ξ) = 0)

⇔ ∃ almeno un punto unito di ϕ

115

Page 118: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Dimostrazione dell’unicita

Supponiamo per assurdo che esistano due punti uniti ξ1 6= ξ2

⇓0 < |ξ1 − ξ2| = |ϕ(ξ1)− ϕ(ξ2)|︸ ︷︷ ︸

punto unito

=

= |ϕ′(σ)(ξ1 − ξ2)|︸ ︷︷ ︸Th. di Lagrange

= |ϕ′(σ)| |ξ1 − ξ2|

≤ k︸︷︷︸ii)|ξ1 − ξ2| < |ξ1 − ξ2|

116

Page 119: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Dimostrazione della convergenza

∀ x0 ∈ I accade che

0 < |en| = |ξ − xn| = |ϕ(ξ)− ϕ(xn−1)| ≤ k |ξ − xn−1| = k|en−1|

⇒ |en| ≤ k |en−1| ≤ k2 |en−2| ≤ . . . ≤ kn |e0| ≤ kn (b− a)

⇒ limn→∞ |en| ≤ lim

n→∞ kn (b− a) =︸︷︷︸

ii)0

117

Page 120: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Osservazione

Dalla dimostrazione del teorema precedente si deduce che l’ipotesi di

derivabilita della funzione di iterazione ϕ nell’intervallo I puo essere

rilassata. Infatti, basta richiedere

∃ k ∈ (0,1) : ∀ x′, x′′ ∈ I ⇒ |ϕ(x′)− ϕ(x′′)| < k|x′ − x′′|,

cioe ϕ deve essere una contrazione.

118

Page 121: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Metodo del punto unito: Esercizio

Tornando all’esercizio proposto precedentemente (f(x) = x3 + 4x2 −10 = 0), possiamo osservare che

• la funzione ϕ5 genera un procedimento iterativo convergente in

quanto sono verificate le ipotesi di applicabilita del metodo di

Newton. Infatti, f, f ′, f ′′ sono funzioni continue in I = [1,2],

f ′(x) 6= 0 ∀ x ∈ I; inoltre anche f ′′(x) 6= 0 ∀ x ∈ I

• la funzione ϕ3(x) = x− x3 − 4x2 + 10, invece, non genera un pro-

cedimento iterativo convergente in I in quanto

ϕ′3(x) = 1− 3x2 − 8x e quindi |ϕ′3(x)| > 1 ∀ x ∈ I(osservare che ϕ′′(x) < 0 ∀ x ∈ I)

119

Page 122: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

• la funzione ϕ4(x) =√

10x − 4x non genera un procedimento itera-

tivo convergente in quanto I non e completamente contenuto nel

dominio di esistenza D della funzione, infatti D = [−∞,−√5/2] ∪(0,√

5/2]

• la funzione ϕ2(x) = (10 − 4x2)1/3 non genera un procedimento i-

terativo convergente in quanto ϕ(I) /∈ I (ϕ(2) = 3√−6 /∈ I); inoltre

|ϕ′2(x)| > 1 in I (basta osservare che ϕ′2(x) non e definita in x =√102 ≈ 1.5811)

120

Page 123: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

• la funzione ϕ1(x) = 12

√10− x3 genera un procedimento iterativo

convergente alla radice dell’equazione non lineare anche se non e

verificata la prima ipotesi del teorema (ϕ(1) = 1.5 mentre ϕ(2) =√2/2).

Tuttavia, poiche

ϕ′1(x) = −3

4

x2√

10− x3

e una funzione monotona decrescente in I e sicuramente |ϕ′1(x)| <1 in I = [1,1.7], il procedimento iterativo risulta convergente in I.

121

Page 124: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Esempio

La funzione ϕ(x) = x− sin(x) ammette piu di un punto fisso in quanto

sin(x) e una funzione periodica.

ϕ(x) = x−sin(x) e stata ottenuta dalla equazione non lineare f(x) = 0,

con f(x) = sin(x).

Nell’intervallo I = [0, 2π], gli zeri di f sono ξ1 = 0, ξ2 = π, ξ3 = 2π.

Tuttavia, la funzione ϕ(x) sicuramente non genera un procedimento

iterativo convergente a ξ2 in quanto non e possibile trovare intervalli

J ∈ I : ξ2 ∈ J per cui sia verificata la condizione |ϕ′(x)| < 1, ∀ x ∈ J.

Infatti, ϕ′(x) = 1−cos(x) e pertanto in prossimita di ξ2 risulta |ϕ′(x)| ≈2 > 1.

122

Page 125: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Convergenza: condizione sufficiente (2)

Teorema 3. Se ϕ e derivabile in I = [a, b] e

i) ϕ(ξ) = ξ ξ ∈ (a, b)

ii) ∃ k ∈ (0,1) tale che |ϕ′(x)| ≤ k, x ∈ I

⇒ esiste un intorno di ξ : ∆ = [ξ − δ, ξ + δ] ⊆ I tale che

α) ξ e l’unico punto unito di ϕ(ξ) in ∆

β) la successione {xn = ϕ(xn−1)}, n = 1,2, . . ., e conver-

gente a ξ per ogni approssimazione iniziale x0 ∈∆

123

Page 126: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Dimostrazione

Basta osservare che se ϕ(∆) ⊆∆, allora valgono le ipotesi del teorema

precedente e quindi il procedimento converge ∀ x0 ∈∆.

Se si pone δ = min(ξ − a, b− ξ) ⇒ ξ ∈∆ := [ξ − δ, ξ + δ] ⊆ I

Se x ∈∆⇒ |ξ − ϕ(x)| = |ϕ(ξ)︸ ︷︷ ︸i)

−ϕ(x)| =

= |ϕ′(σ)| |ξ − x|︸ ︷︷ ︸Th.Lagr.

≤ k|ξ − x|︸ ︷︷ ︸ii)

≤ k δ︸︷︷︸x∈∆

< δ

⇒ ϕ(∆) ⊆∆ ⇒ Si ricade nelle ipotesi del Teorema 2

124

Page 127: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Applicazione al metodo delle tangenti

Teorema 4. Se I = [a, b] e un intervallo di separazione di uno zero

di f e inoltre

i) f , f ′, f ′′ sono continue in I: f ∈ C2[a, b]

ii) f ′(x) 6= 0 per x ∈ [a, b]

⇒ esiste un intorno J ⊆ I di ξ tale che per x0 ∈ J la successione

delle approssimazioni{xn = xn−1 −

f(xn−1)

f ′(xn−1)

}, n = 1,2, ...,

converge a ξ

125

Page 128: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Dimostrazione

Per il metodo delle tangenti

ϕT (x) = x− f(x)

f ′(x)⇒ ϕ′T (x) =

f(x)f ′′(x)

(f ′(x))2 ⇒ ϕ′T (ξ) =f(ξ)f ′′(ξ)(f ′(ξ))2 = 0

Poiche ϕ′T e continua, esiste un intorno [α, β] ⊆ I di ξ tale che

|ϕ′T (x)| ≤ k ∈ (0,1)

⇒ si ricade nelle ipotesi del Teorema 3 con [a, b] = [α, β] ∩ I e

J = ∆

•∆=J︷ ︸︸ ︷

[ • • ] ]︸ ︷︷ ︸[α,β]

a ξ x0 b

126

Page 129: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Proprieta della successione delle approssimazioni

Si vuole caratterizzare la successione delle approssimazioni

Dal Teorema di Lagrange si ha

en = ξ−xn = ϕ(ξ)−ϕ(xn−1) = ϕ′(tn)(ξ−xn−1) = ϕ′(tn)en−1 tn ∈ [xn−1, ξ]

x0 x

1 x

2 x

3

φ(x0)

φ(x1)

φ(x2)

φ(x3)

y=x

y=φ(x)

x

y

ξ o

x3 x

1 x

2 x

0

φ(x0)

φ(x1)

φ(x2)

φ(x3)

y=x

y=φ(x)

x

y

ξ

o

0 ≤ ϕ′(x) < 1 −1 < ϕ′(x) ≤ 0ad ogni iterazione l’errore diminuisce ad ogni iterazione l’errore diminuisce

in valore assoluto e preserva il segno in valore assoluto ma non conserva il segno

127

Page 130: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Proprieta della successione delle approssimazioni

• Se 0 ≤ ϕ′(x) < 1 per x ∈ I la successione {xn = ϕ(xn−1)}, n =

1,2, ..., e monotona crescente (se e0 > 0) o decrescente (se

e0 < 0) ⇒ le approssimazioni sono per difetto (se ξ > x0) o per

eccesso (se ξ < x0)

• Se −1 < ϕ′(x) ≤ 0 per x ∈ I la successione {xn = ϕ(xn−1)},n = 1,2, ..., non e monotona ⇒ le approssimazioni sono alter-

nativamente per difetto e per eccesso

128

Page 131: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Ordine di convergenza

Teorema 5. Se

i) ϕ ∈ Cp(I) con I intorno di un punto unito ξ di ϕ

ii) la successione delle approssimazioni {xn} e convergente

iii) ϕ(ξ) = ξ, ϕ(ν)(ξ) = 0 ν = 1, ...,p− 1

ϕ(p)(ξ) 6= 0

⇒ il metodo ha ordine di convergenza p

129

Page 132: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Dimostrazione

Sviluppo in serie di Taylor:

ϕ(xn) =

ϕ(ξ) + ϕ′(ξ)(xn − ξ) +1

2ϕ′′(ξ)(xn − ξ)2 + ...+

+ 1(p−1)!ϕ

(p−1)(ξ)(xn − ξ)p−1 +1

p!ϕ(p)(tn)(xn − ξ)p

︸ ︷︷ ︸errore nella forma di Lagrange

=

=︸︷︷︸iii)

ϕ(ξ) + 1p!ϕ

(p)(tn)(−en)p tn ∈ [xn, ξ]

130

Page 133: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

en+1 = ξ − xn+1 = ϕ(ξ)− ϕ(xn) = − 1

p!ϕ(p)(tn)(−1)p (en)p

⇒limn→∞

|en+1||en|p

=|ϕ(p)(ξ)|

p!︸ ︷︷ ︸fattore di

convergenza

= C > 0

ordine di

convergenza

131

Page 134: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Esempi

• Se ϕ′(ξ) 6= 0 ⇒ p = 1 la convergenza e lineare:

C = ϕ′(ξ) ≤ k := maxx∈[a,b]

|ϕ′(x)| coefficiente

di contrazione

• Metodo delle tangenti: ϕT (x) = x− f(x)

f ′(x)

ϕ′T (ξ) =f(ξ)f ′′(ξ)(f ′(ξ))2 = 0

ϕ′′T (ξ) =f ′′(ξ)f ′(ξ)

{6= 0 se f ′′(ξ) 6= 0 ⇒ p = 2= 0 se f ′′(ξ) = 0 ⇒ p > 2

Se p = 2 la convergenza e quadratica

132

Page 135: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Criteri di arresto

Se k e il coefficiente di contrazione allora

|en| = |ξ − xn| = |ϕ(ξ)− ϕ(xn−1)| ≤ k |ξ − xn−1|(2)

D’altra parte

|ξ − xn−1| = |ξ − xn + xn − xn−1| ≤≤ |ξ − xn|+ |xn − xn−1| == |ϕ(ξ)− ϕ(xn−1)|+ |xn − xn−1| ≤≤ k |ξ − xn−1|+ |xn − xn−1|

⇒ |ξ − xn−1| ≤1

1− k|xn − xn−1|

Sostituendo questa espressione in (2) si ha

|en| ≤ k

1− k|xn − xn−1| Stima a posteriori

133

Page 136: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Poiche

|en| ≤ k|en−1| ≤ k2|en−2| ≤ . . . ≤ kn−1|e1| ≤ kn−1 k

1− k|x1 − x0|

si ha

|en| ≤ kn

1− k|x1 − x0| ≤kn

1− k(b− a) Stima a priori

da cui e possibile dare una stima del numero di iterazioni N che garan-

tisce |en| < ε, con ε fissata, come segue

N >log

(ε(1−k)b−a

)

logk

134

Page 137: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Esercizio

Stabilire se le funzioni

ϕ1(x) = x3 + 6x2 + x− 8, ϕ2(x) =

√8

x+ 6, ϕ3(x) =

√8− x3

6

generano un procedimento iterativo convergente alla radice dell’equazione

non lineare x3 + 6x2 − 8 = 0 contenuta nell’intervallo I = [1,2].

Per ognuna di esse caratterizzare la convergenza (ordine, monotonia,

scelta dell’approssimazione iniziale).

135

Page 138: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Soluzione Osserviamo che ϕ1(x) = x⇐⇒ x3 + 6x2− 8 = 0. La stessa

condizione e soddisfatta dalle funzioni ϕ2 e ϕ3. Inoltre, ϕ1(x), ϕ2(x), ϕ3(x)

sono funzioni continue e derivabili in I.

ϕ1 non genera un precedimento iterativo convergente nell’intervallo

dato in quanto

ϕ′1(x) = 3x2 + 12x+ 1 > 1 ∀ x ∈ I

ϕ′2(x) = −√

2

(x+ 6)√x+ 6

< 0 ∀x ∈ I

ne segue che ϕ2 e monotona decrescente in I e quindi

∀ x ∈ I, ϕ2(1) ≥ ϕ2(x) ≥ ϕ2(2)

.

136

Page 139: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Poiche ϕ2(1) =√

8/7 > 1 and ϕ2(2) = 1, si ha ϕ2(I) ⊂ I.

Inoltre, si verifica facilmente che |ϕ′2(x)| < 1 ∀ x ∈ I.

Possiamo, dunque, concludere che ϕ2 genera un procedimento iterativo

convergente allo zero di x3 + 6x2− 8 nell’intervallo I = [1, 2] per ogni

scelta dell’approssimazione iniziale x0 ∈ I.

Inoltre, poiche ϕ′2 6= 0 ∀x ∈ I, l’ordine di convergenza e lineare (p = 1)

e la convergenza non e monotona in quanto ϕ′2 < 0 ∀ x ∈ I. Infine il

fattore di convergenza e k2 = maxx∈I |ϕ′2(x)| = |ϕ′2(1)| =√

27√

7.

Cosa si puo dire di ϕ3?

Mostare che ϕ3 non genera un procedimento convergente in I ma lo

genera in I1 = [1, 1.15] e la convergenza e lineare e non monotona.

Scegliendo x0 = 1.15, stabilire quale tra i procedimenti generati da ϕ2

e ϕ3 in I1 converge piu velocemente.

137

Page 140: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Esercizio 1.25L. Gori, M.L. Lo Cascio, F. Pitolli, Esercizi di Calcolo Numerico, II ed.

Dimostrare che il seguente procedimento iterativo

xn+1 = xn + e1−xn − 1

converge qualunque sia il punto iniziale x0 > 1 e calcolarne il limite;

• stabilire se la successione e monotona per ogni x0 > 1;

• studiare il comportamento di {xn+1} se x0 = 1/2;

• stabilire l’ordine di convergenza del procedimento iterativo.

138

Page 141: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Soluzione La funzione di iterazione e ϕ(x) = x+ e1−x − 1.

ϕ e una funzione continua in R e derivabile, inoltre si osserva che

ϕ(x) = x⇔ e1−x − 1 = 0⇔ 1− x = 0⇔ x = 1.

Quindi x = 1 e il punto unito di ϕ. Inoltre,

limx→−∞ϕ(x) = +∞ e lim

x→+∞ϕ(x) = +∞

139

Page 142: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

mentre

ϕ′(x) = 1− e1−x ≥ 0⇔ e1−x ≤ 1⇔ 1− x ≤ 0⇔ x ≥ 1,

con ϕ′(x) funzione continua in R.

ϕ(x) e quindi una funzione monotona decrescente per x < 1 e monotona

crescente per x > 1.

Poiche ϕ′ cambia segno in x = 1, ϕ(x) ha un estremo relativo in

corrispondenza di questo punto.

140

Page 143: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

ϕ′′(x) = e1−x > 0 ∀ x ∈ R,

quindi x = 1 e un punto di minimo relativo per ϕ(x).

Poiche ϕ′′(x) ha segno costante nel dominio di esistenza di ϕ,

ne deduciamo che x = 1 e l’unica radice dell’equazione non lineare

considerata.

141

Page 144: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Poiche ϕ cambia segno proprio in corrispondenza della radice x = 1,

l’eventuale convergenza monotona del metodo potra essere garantita

solo in intervalli I ⊂ [1,+∞) mentre il metodo puo convergere, even-

tualmente non in modo monotono, in intervalli I ⊂ [1 − δ,+∞), con

δ ∈ R+.

Per stabilire tali convergenze e necessario determinare l’intervallo I tale

che ϕ(I) ⊆ I e |ϕ′(x)| ≤ k, k ∈ (0,1) ∀x ∈ I.

142

Page 145: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Si osserva che

|ϕ′(x)| = |1− e1−x| < 1⇔{∀ x se x > 1x > 1− log(2) se x < 1

Ne segue che 0 ≤ δ ≤ log(2).

Inoltre, poiche ϕ(x) e una funzione monotona crescente per x > 1,

scelto un punto x > 1, risulta

ϕ(x) ≤ x⇔ e1−x ≤ 1⇔ x ≥ 1.

143

Page 146: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Quindi, ∀ I = [1, x] accade che

ϕ(I) ⊆ I e |ϕ′(x)| < 1

da cui deduciamo che il metodo converge in modo monotono ∀ x0 > 1.

144

Page 147: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Poiche x = 1 e l’unico punto unito di ϕ, si puo scegliere un intorno

del punto x = 1 in cui il metodo converge per ogni scelta del punto

iniziale x0.

In questo caso, la condizione ϕ(I) ⊆ I implica

e1−(1−δ) − 1 ≥ 0⇔ eδ ≥ 1⇔ δ ≥ 0,

che, confrontata con la condizione sulla derivata, da

0 ≤ δ ≤ log(2).

145

Page 148: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Da quanto detto sopra, poiche

1− log(2) <1

2< 1,

scegliendo x0 = 1/2 il metodo converge in intervalli I = [1− δ, x], con

δ < 0.5 e x ≥ 1 (in particolare, x ≥ ϕ(1− δ)).

Poiche risulta

ϕ(1) = 1 ϕ′(1) = 0 e ϕ′′(1) 6= 0,

l’ordine di convergenza del metodo e p = 2.

OSS: Verificare che il procedimento iterativo corrisponde al metodo

di Newton applicato alla funzione f(x) = ex−1 − 1

146

Page 149: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Esempio

I = [1− log(2), ϕ(1− log(2))] x0 = 1/2 ε = 0.5 · 10−5

Metodo del punto unito

k xk εk2 1.148721270700128 0.6487212707001283 1.010530563626045 0.1381907070740834 1.000055252269219 0.0104753113568275 1.000000001526379 0.0000552507428406 1.000000000000000 0.000000001526379

Metodo di Newton

k xk εk1 1.148721270700128 0.6487212707001282 1.010530563626045 0.1381907070740833 1.000055252269219 0.0104753113568274 1.000000001526379 0.0000552507428405 1.000000000000000 0.000000001526379

147

Page 150: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Esercizio 1.8

Separare le soluzioni dell’equazione

f(x) = (x2 − 2)cos(x) + 2xsin(x) = 0

e stabilire se la funzione

ϕ(x) = arctan

(2− x2

2x

)

genera un procedimento iterativo convergente, con appropriata scelta

di x0, alla radice ξ ∈ (0, π/2).

148

Page 151: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Si procede per separazione grafica individuando i punti di intersezione

delle seguenti funzioni

h(x) = tan(x), g(x) =2− x2

2x.

In particolare, e possibile osservare che la funzione g(x) e antisim-

metrica rispetto all’asse delle ordinate, che rappresenta anche il suo

asintoto verticale (limx→0+g(x) = +∞, limx→0−g(x) = −∞).

g(x) e monotona decrescente ∀ x > 0 e, nel semiasse positivo, risulta

g(x) ≥ 0 per x ≤ √2 < π2.

Pertanto, considerata la periodicita della funzione h(x), le radici dell’e-

quazione data appartengono ai seguenti intervalli:

I0 = (0, π/2) e Ik = (π2 + (k − 1)π, (k)π), k = 1,2, .....

Per le radici negative, basta considerare gli intervalli simmetrici cor-

rispondenti.

149

Page 152: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Si osserva che ϕ(x) = x e equivalente a f(x) = x e che ϕ(x) e continua

e derivabile in I0. Inoltre, poiche ϕ′(x) = −2x2+2x4+4

, risulta

|ϕ′(x)| < 1 ⇔ x < −√

2 oppure x >√

2

mentre la radice ξ ∈ (0, π/2) e ξ ≈ 0.756 ∈ [0,√

2].

Pertanto, ϕ non genera un procedimento iterativo convergente.

Nota: Verificare che il Metodo di Newton genera un procedimento iterativo conver-

gente alla radice ξ ∈ (0, π/2).

150

Page 153: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Esercizio 7.11

Data l’equazioneα(4− x2) = x3, α > 0

1. separare graficamente le soluzioni positive ed individuare per qualivalori di α l’equazione ammette una radice ξ > 1;

2. posto α = 1, introdurre un’opportuna funzione di iterazione x =φ(x), x ∈ [1, 1.5] adatta ad approssimare la radice ξ > 1;

3. in base al comportamento di φ caratterizzare la successione delleapprossimazioni xn = φ(xn−1) (ordine di convergenza, monotonia,etc. ).

4. stimare il numero di iterazioni necessarie affinche il procedimentoiterativo produca un’approssimazione della soluzione con 5 deci-mali esatti e confrontarlo con il numero di iterazioni realmentenecessarie.

151

Page 154: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Soluzione: Si considerano le funzioni h(x) = α(4− x2) e g(x) = x3.

h(x), al variare del parametro α, e una parabola con concavita rivoltaverso il basso e vertice V = (0,4α). Quindi, V si avvicina a 0 manmano che il valore del parametro α decresce.

Inoltre, come mostrato nel grafico, la radice positiva esiste ed eunica

−2.5 −2 −1.5 −1 −0.5 0 0.5 1 1.5 2 2.5−10

−8

−6

−4

−2

0

2

4

6

8

10

x

h con α = 1h con α = 1/2h con α = 1/3gξ = 1

152

Page 155: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Poiche h(1) = 3α mentre g(1) = 1, risulta ξ = 1 se α = 1/3. Ne

deduciamo che la radice positiva e maggiore di 1 se α > 13

Se α = 1, l’equazione diventa 4− x2 = x3.

Nell’intervallo I = [1, 1.5],

x = φ(x) =3√

4− x2

genera un procedimento iterativo convergente.

Infatti, φ e una funzione continua, derivabile e positiva in I.

Inoltre

φ′(x) = −2

3

x

3√

(4− x2)2< 0 ∀ x ∈ I.

153

Page 156: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Quindi φ e decrescente, da cui

φ(1) ≥ φ(1.5).

Poiche φ(1) = 3√3 ≈ 1.44 e φ(1.5) ≈ 1.20, risulta

φ(I) ⊂ I.

Inoltre, si osserva che |φ′(x)| = 23

|x|3√

(4−x2)2.

La funzione a secondo membro e una funzione monotona crescente in

I in quanto e il prodotto di funzioni monotone crescenti e positive in

I e quindi

|φ′(x)| ≤ |φ′(1.5)| = k ≈ 0.69 < 1.

154

Page 157: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Poiche φ′(x) < 0 ∀ x ∈ I, il metodo converge, producendo approssi-

mazioni della radice ξ alternativamente per eccesso e per difetto.

Poiche φ′(x) = 0⇔ x = 0, risulta φ′(ξ) 6= 0

e quindi l’ordine di convergenza del metodo iterativo e p = 1.

155

Page 158: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Per stimare il numero di iterazioni necessarie si usa la seguente disu-

guaglianza

|en| = |xn − ξ| ≤ kn

1− k(b− a)

che nel caso considerato diventa

|en| = |xn − ξ| ≤ 0.69n

1− 0.69(1.5− 1)

156

Page 159: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Richiedendo 5 decimali esatti all’approssimazione prodotta, risulta

|en| < ε = 0.5 · 10−5

cioe0.69n

0.31(0.5) < 0.5 · 10−5

da cui

n >log(2 · (0.31) · 0.5 · 10−5)

log(0.69)≈ 34.18,

ovvero, eseguendo N = 35 iterazioni, l’approssimazione prodotta ha

sicuramente i decimali esatti richiesti.

157

Page 160: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Considerando le iterate si ha

k xk xk − xk−1

2 1.407779816636963 0.3077798166369633 1.263722089604660 0.1440577270323034 1.339424732696048 0.0757026430913885 1.301761199775750 0.0376635329202986 1.321041758493116 0.0192805587173677 1.311311289649813 0.0097304688433038 1.316257901162381 0.0049466115125689 1.313752451659470 0.002505449502911

10 1.315023829271998 0.00127137761252911 1.314379285273200 0.00064454399879812 1.314706203444088 0.00032691817088813 1.314540428132803 0.00016577531128514 1.314624500689312 0.00008407255650915 1.314581866160240 0.00004263452907216 1.314603487493636 0.00002162133339617 1.314592522800411 0.00001096469322518 1.314598083302941 0.00000556050253019 1.314595263428300 0.000002819874641

Oss: La stima del numero di iterazioni e per eccesso; infatti, dopo 19

iterazioni si raggiunge la tolleranza richiesta.

158

Page 161: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Infine, si osserva che le funzioni

φ1(x) =√

4− x3,

φ2(x) =4

x2− 1

φ3(x) = x3 + x2 + x− 4

non sono adatte ad approssimare la radice positiva della funzione

considerata in quanto per esse non sono verificate le condizioni φ(I) ⊆ Ie |φ′(x)| < 1 ∀ x ∈ I.

159

Page 162: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Esercizio

Si considerino le seguenti funzioni

φ1(x) = x2−2; φ2(x) =√

2 + x; φ3(x) = −√

2 + x; φ4(x) = 1+2

x, x 6= 0.

1.1) Specificare quante e quali di esse sono adatte ad approssimarealmeno uno zero della funzione f(x) = x2 − x − 2 con il metododelle approssimazioni successive;

1.2) per ognuna delle funzioni individuate al punto precedente, carat-terizzare la successione delle approssimazioni successive (sceltadell’approssimazione iniziale, coefficiente di contrazione, monoto-nia ordine di convergenza);

1.3) proporre, se possibile, una funzione diversa dalle precedenti che siaadatta ad approssimare almeno lo zero positivo di f con il metododelle approssimazioni successive.

160

Page 163: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Soluzione:

La ricerca del punto unito delle 4 funzioni e equivalente a risolverel’equazione non lineare x2 − x − 2 = 0, la quale ha due radici ξ1 = −1e ξ2 = 2.

La funzione φ1 non puo generare procedimenti iterativi convergenti aduno degli zeri della funzione in quanto risulta φ′1(x) = 2x e quindi

|2x| < 1⇔ |x| < 1/2,

intervallo di valori che non contiene le due radici.

La funzione φ2, essendo positiva, puo convergere solo alla radice posi-tiva ξ2 = 2. Si osserva che

φ′2(x) =1

2√x+ 2

e sicuramente minore di 1 per x ∈ I = [1,3]. In questo intervallo,inoltre, φ′2(x) e monotona decrescente, e poiche φ2(1) =

√3 ∈ I e

φ2(3) =√

5 ∈ I, possiamo concludere che φ2 genera un procedimentoiterativo convergente a ξ2.

161

Page 164: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Inoltre, poiche φ′2 > 0, la convergenza e monotona e l’ordine di conver-

genza e 1 mentre la costante di contrazione vale k = maxx∈I(|φ′2(x)|) =1

2√

3.

Stesse argomentazioni valgono per la funzione φ3 che genera un pro-

cedimento iterativo convergente a ξ1 = −1, per esempio nell’intervallo

I = [−1.5,0].

La funzione φ4 ha come derivata prima la funzione φ′4(x) = −2/x2. Ne

segue che

2

x2< 1⇔ 2− x2 < 0⇔ x < −

√2 ∧ x >

√2,

e dunque il procedimento iterativo non puo convergere alla radice

negativa. Inoltre, poiche φ′4 < 0, φ4 e monotona decrescente e quindi,

scelto I = [1.5,3], risulta φ4(1.5) = 7/3 ∈ I e φ4(3) = 5/3 ∈ I.

162

Page 165: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Concludiamo, dunque, che la φ4 genera un procedimento iterativo

convergente a ξ2 in I, la convergenza non e monotona in quanto

φ′4(x) < 0, l’ordine di convergenza e 1 mentre la costante di con-

trazione e k = maxx∈I |φ′4(x)| = |φ′4(1.5)| = 8/9.

Infine, poiche f(x), f ′(x), f ′′(x) sono funzioni continue in R, f ′(x) =

2x − 1 = 0 ⇔ x = 1/2 e f ′′(x) = 2 > 0, ∀ x ∈ R, e possibile in-

dividuare due intervalli, che non contengono il punto x = 1/2, in cui

il metodo di Newton genera un procedimento iterativo convergente

alle due radici dell’equazione non lineare. L’approssimazione inizia-

le e l’estremo di Fourier dell’intervallo considerato, la convergenza e

monotona e l’ordine di convergenza e p = 2.

163

Page 166: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Esercizio

Si consideri la seguente equazione non lineare dipendente dal parametroreale β :

βx = e−x, ∀ x ∈ R

1. Stabilire per quali valori di β l’equazione non lineare ammetteun’unica radice reale.

2. Scelto β = 1 e detta α la radice, determinare se esistono valori delparamtero reale ω, con ω > 0, per cui il procedimento iterativo

xn+1 =ωe−xn + xn

1 + ω

converge ad α per ogni scelta dell’approssimazione iniziale.

3. Tra i valori di ω determinati al punto precedente, individuare quelloper cui la convergenza e massima.

164

Page 167: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Soluzione Si osserva che la radice corrisponde all’intersezione di una

retta passante per l’origine e la funzione esponenziale (funzione positiva

e decrescente) e quindi se β = 0, l’intersezione sicuramente non esiste

in quanto la funzione esponenziale non assume mai valore zero.

D’altra parte

limx→+∞

(βx− e−x) = ±∞ (+∞ se β > 0,−∞ se β < 0)

limx→−∞(βx− e−x) = −∞

Ne segue che per β > 0 esiste sicuramente una radice ed e anche unica,

mentre non e cosı per i valori di β negativi. Infatti, ∂∂ x(βx − e−x) =

β + e−x = 0⇐⇒ x = −log(−β), che esiste per β < 0, mentre per β > 0

risulta ∂∂ x(βx− e−x) > 0 ∀ x

165

Page 168: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Prima di tutto si osserva che, quando β = 1,

ωe−x + x

1 + ω= x⇐⇒ e−x = x.

Ne segue che la successione xn+1 = ωe−xn+xn1+ω , se converge, sicura-

mente converge ad α.

Inoltre, definita f(x) = x− e−x, risulta

f(0) = −1 < 0 mentre f(1) = 1− 1e > 0,

e quindi l’intervallo I = [0, 1] contiene l’unico zero di f .

La funzione

ϕ(x) =ωe−x + x

1 + ω

e una media pesata, con pesi positivi w1 = ω1+ω < 1 e w2 = 1

1+ω

e tali che w1 + w2 = 1, di funzioni che assumono valori nell’intervallo[0, 1], e quindi ϕ(I) ⊆ I

166

Page 169: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Inoltre, poiche

ϕ′′(x) =ωe−x

1 + ω> 0 ∀ x,

ϕ′(x) = 11+ω(−ωe−x+ 1) e monotona crescente e si verifica facilmente

che

−1 <1

1 + ω(−ωe−x + 1) < 1

e vera in I per tutti i valori di ω > 0

Si conclude che la successione xn+1 = ϕ(xn) genera un procedimento

iterativo convergente ad α in I = [0, 1].

Infine, si osserva che ϕ′(α) = 0⇐⇒ ω = 1α, mentre ϕ′′(α) = 1

1+ω 6= 0

Ne segue che esiste un solo valore di ω (ω = 1α) per cui la conver-

genza del procedimento iterativo e quadratica. In tutti gli altri casi la

convergenza e lineare.

167

Page 170: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Esercizio

Si consideri il seguente procedimento iterativo dipendente dal para-

metro reale α:

zi+1 = f(zi)

con f(z) = αcos(z), z ∈(0, π2

).

1. Studiarne la convergenza in funzione del parametro α, prima nel

caso in cui α ∈(0, π3

)e poi per α ∈

(2π3 , π

).

2. In corrispondenza dei valori di α per cui la successione zi converge,

valutare l’ordine di convergenza.

3. Dare, se possibile, una stima del limite con almeno due decimali

esatti.

168

Page 171: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Esercizio

Data la funzione f(x) = eαx−1 − x2

4 con α ∈ R,

• individuare per quale valore del parametro α la funzione f(x) am-

mette un’unica radice ξ nell’intervallo I = [1.5,2.5];

• detto αo il valore del parametro α per cui ξ = 2, stabilire se la

funzione φ(x) = 2√eαox−1 genera nell’intervallo I un procedi-

mento iterativo convergente a ξ.

In caso di risposta affermativa, indicare il coefficiente di contrazione

k e l’ ordine di convergenza del metodo ottenuto.

Inoltre, dare una stima del numero di iterazioni necessarie affinche

l’approssimazione prodotta abbia almeno 3 cifre decimali esatte.

169

Page 172: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Riferimenti bibliografici

L. Gori, Calcolo Numerico: Cap. 3, §§ 3.1, 3.2, 3.3, 3.4 (escluso metodo di falsaposizione), 3.5, 3.6 (escluso metodo delle secanti con estremo fisso), 3.7, 3.9, 3.10

L. Gori, M.L. Lo Cascio, Esercizi di Calcolo Numerico: Es. 1.1,1.2, 1.3, 1.4, 1.5,

1.8, 1.9, 1.10, 1.11, 1.13, 1.14, 1.19, 1.20, 1.21, 1.25, 1.26, 1.27, 1.28, 1.29, 1.30,

7.11, 7.12, 7.13, 7.14, 7.18, 7.20. 7.22, 7.29, 7.36, 7.40, 7.43, 7.53-7.56, 7.61-7.62

170

Page 173: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Esercizi d’esame

171

Page 174: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

ESERCIZIO 1

Data l’equazione non lineare

f(x;λ) = (1− sinx)2 − λx3 = 0 ,

dove λ e un parametro reale,

1.1 individuare per quali valori del parametro λ l’equazione ammette

un’unica radice nell’intervallo [0,1].

1.2 posto λ = 1/2, determinare quante iterazioni sono necessarie ad

approssimare la radice in [0,1] con il metodo delle tangenti con 3

decimali esatti.

172

Page 175: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Soluzione

1.1) Si ha f(0;λ) = 1 > 0 e f(1;λ) = (1 − sin(1))2 − λ. Affinche

l’equazione abbia una radice nell’intervallo [0,1] deve essere

f(1;λ) = (1−sin(1))2−λ < 0 ⇒ λ > (1−sin(1))2 ≈ 0.0251

Poiche per questi valori di λ si ha

f ′(x;λ) = −2(1− sinx) cosx− 3λx2 < 0 , x ∈ [0,1] ,

la funzione f e monotona decrescente e la radice e unica.

1.2) Per λ = 1/2 l’equazione

f(x;λ) = (1− sinx)2 − 1

2x3 = 0 ,

ha un’unica radice nell’intervallo [0,1] (cfr. punto precedente).

Inoltre la derivata f ′(x) non si annulla in tale intervallo, quindi si

puo utilizzare il metodo delle tangenti per approssimare la radice.

173

Page 176: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Il metodo converge per un’opportuna scelta dell’approssimazione

iniziale. Utilizzando come approssimazione iniziale il punto medio

dell’intervallo, il metodo delle tangentixi+1 = xi − f(xi)

f ′(xi), i = 0,1,2, . . . ,

x0 = 0.5 ,

produce i risultati in tabella

i xi |xi − xi−1|0 0.51 0.661790 0.161792 0.664688 0.002903 0.664687 0.9 · 10−6

Sono sufficienti 3 iterazioni per raggiungere l’accuratezza richiesta.

Page 177: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

ESERCIZIO 2

Data l’equazione non lineare g(y;λ) = e−y − 2y − λ = 0 , dipendente

dal parametro reale λ,

2.1 determinare per quali valori di λ l’equazione ammette un’unica

radice nell’intervallo I = [0,1];

2.2 posto λ = −2, verificare se le funzioni di iterazione

ψ1(y) =1

2e−y + 1 ψ2(y) = y +

e−y − 2y + 2

e−y + 2

sono adatte ad approssimare la radice nell’intervallo D = [1,2] con

il metodo delle approssimazioni successive;

2.3 in caso di convergenza, specificare per ciascuna funzione la scelta

dell’approssimazione iniziale.

174

Page 178: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Soluzione

2.1) La funzione g(y;λ) e monotona decrescente per ogni λ ∈ IR, inoltre

limx→−∞ g(y;λ) = +∞ lim

x→+∞g(y;λ) = −∞

Si deduce quindi che g(y;λ) ha un’unica radice ξ ∈ IR.

Si verifica facilmente che ξ = 0 per λ = 1 mentre ξ = 1 per

λ = 1e − 2 ≈ −1.63, quindi ξ ∈ [0,1] per 1

e − 2 ≤ λ ≤ 1.

Si suggerisce di fare lo studio grafico dell’equazione e−y = 2y + λ.

2.2) Per λ = −2 l’equazione diventa

g(y;−2) = e−y − 2y + 2 = 0 .

Si ha y − ψ1(y) = y − 1

2e−y − 1 = −2 g(y; 2) = 0,

quindi il punto unito della trasformazione ψ1 e anche la radice

dell’equazione g(y; 2) = 0.

175

Page 179: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Per verificare se la funzione ψ1 e adatta ad approssimare l’unica

radice nell’intervallo I = [1,2] bisogna verificare se soddisfa le

ipotesi del teorema del punto unito. La funzione ψ1 e monotona

decrescente per cui ∀ y ∈ [1,2]

1 < 1.068 ≈ ψ1(2) =1

2e−2+1 ≤ ψ1(y) ≤ ψ1(1) =

1

2e−1+1 ≈ 1.184 < 2

Inoltre |ψ′1(y)| = e−y/2 e monotona decrescente per cui

maxy∈[1,2]

|ψ′1(y)| = e−1

2≈ 0.184 < 1

La funzione di iterazione e adatta ad approssimare la radice.

La funzione ψ2 e la funzione di iterazione del metodo di Newton.

La funzione g(y;−2) e infinitamente derivabile, inoltre per ogni

y ∈ IR si ha g′(y;−2) = −e−y − 2 < 0. Quindi il metodo di Newton

converge per un’opportuna scelta dell’approssimazione iniziale.

Page 180: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

2.3) Il metodo delle approssimazioni successive yk+1 = ψ1(yk), k =

0,1, . . ., converge per qualunque y(0) ∈ [1,2]. Poiche g′′(y;−2) =

e−y > 0 per ogni y ∈ IR, il metodo di Newton converge sicuramente

se si sceglie come approssimazione iniziale l’estremo di Fourier

dell’intervallo, cioe l’unico estremo per cui g(y0;−2) g′′(y0;−2) > 0.

Per la funzione in esame si ha y0 = 1.

Si suggerisce di dare una stima a priori del numero di iterazioni ne-

cessarie per approssimare la radice con 3 decimali esatti utilizzando

il metodo delle approssimazioni successive e di verificare tale stima

eseguendo le iterazioni. Eseguire anche le iterazioni del metodo di

Newton. Quale dei due metodi e piu veloce? Perche ?

176

Page 181: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

ESERCIZIO 3

Data la funzione

f(x) = (x2 + α)cosx+ sinx, x ∈ I =[π

2,2

],

dove α e un parametro reale,

• determinare se per α > 0 esiste l’estremo di Fourier dell’intervallo

I;

• posto α = −1, verificare se il metodo delle tangenti e adatto ad

approssimare lo zero di modulo massimo specificando, in caso di

convergenza, la scelta dell’approssimazione iniziale e l’ordine di con-

vergenza.

177

Page 182: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Soluzione:

Per α > 0 la funzione f(x) e monotona decrescente con f(π/2)f(2π/3) <0, quindi f(x) ha un unico zero nell’intervallo I.

L’intervallo I ha l’estremo di Fourier se f ′′(x) 6= 0 per x ∈ I. Poiche

f ′′(x) = (2− x2 − α)cos(x)− (4x+ 1)sin(x)

si ha f ′′(π/2) = −2π − 1 < 0 e f ′′(2π/3) = (2 − 4π2/9 − α)(−1/2) −(8π/3 + 1)(

√3/2) ≈ −6.93 + α/2.

Quindi, f ′′(2π/3) < 0 se α < −2(−6.93) ≈ 13.86.

Poiche f ′′(x) e una funzione convessa in I, per 0 < α < 13.86, f ′′ nonsi annulla in I ed esiste l’estremo di Fourier, cioe x0 = 2π/3.

Per α = −1 e facile verificare che esiste un unico zero in I che puoessere approssimato con il metodo delle tangenti in quanto f ′(x) 6= 0per x ∈ I. Il metodo converge sicuramente se si sceglie come approssi-mazione iniziale l’estremo di Fourier dell’intervallo x0 = 2π/3. Poichef ′′(x) 6= 0 per x ∈ I, il metodo ha ordine di convergenza quadratica.

178

Page 183: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

ESERCIZIO 4

Data la funzione

η(t) =eGt

1 + κ(eGt − 1)− 4 ,

dove G e κ sono due parametri reali non negativi,

4.1 trovare i valori di G e κ per i quali η(t) ha un unico zero nel

semipiano positivo;

4.2 posto G = 1 e κ = 0.1, individuare un intervallo di separazione e

un metodo iterativo adatto ad approssimare lo zero positivo speci-

ficando le proprieta della successione delle approssimazioni (ap-

prossimazione iniziale, ordine di convergenza, monotonia, etc.).

179

Page 184: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Soluzione del punto 4.1 Si osserva che, poiche i parametri sono positivi, lafunzione η(t) e definita sul semiasse positivo. Inoltre, η(0) < 0 indipendentementedal valore dei tre parametri. Pertanto, perche la funzione abbia un unico zero nelsemiasse positivo, deve accadere che

limt→∞η(t) =1

κ− 4 > 0

e che

η′(t) =GeGt(1− κ)

(1 + κ(eGt − 1))2

abbia segno costante.

Dalla prima condizione risulta

κ <1

4mentre, dalla seconda condizione, si ha

η′(t) > 0⇔ κ < 1, η′(t) < 0⇔ κ > 1;

pertanto

κ <1

4.

180

Page 185: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

ESERCIZIO 5

Data la funzione

f(x) = α+ βx2 − cos(πx) ,

dove α e β ≥ 0 sono due parametri reali,

5.1 trovare i valori di α e β per i quali f(x) ha almeno uno zero

nell’intervallo I = [0,1];

5.2 posto α = 0 e β = 1, individuare un intervallo di separazione

di ampiezza non superiore a 0.25 adatto ad approssimare lo zero

positivo con il metodo delle tangenti.

181

Page 186: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Soluzione

f e una funzione continua per ogni x reale, e lo sono anche f ′ e f ′′.Inoltre

f(0) = α− 1 f(1) = α+ β + 1

Quindi f ha almeno uno zero in [0, 1] se

(α− 1)(α+ β + 1) < 0⇐⇒ −(1 + β) < α < 1

Poiche per α = 0 e β = 1 risulta

f ′(x) = 2x+ πsin(πx) > 0 ∀x ∈ Ilo zero e unico in I.

Per trovare un intervallo contenente lo zero e con ampiezza non supe-

riore a 0.25, si valuta f(0.5) = 1/4 > 0 e quindi f(1/4) = 1−8√

216 < 0.

Quindi, l’intervallo cercato e I1 = [0.25, 0.5]. Inoltre, poche f ′′(x) =

2 + π2cos(πx) > 0∀x ∈ I1, si puo scegliere l’estremo di Fourier come

approssimazione iniziale del metodo di Newton-Raphson, cioe x0 = 0.5

182

Page 187: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

ESERCIZIO 6

Data la funzione

f(x) = log(x+ α) +√x+ 4− 1, x ∈ R,

dove α e un parametro reale,

6.1 determinare per quali valori di α la funzione f(x) ha almeno uno

zero positivo;

6.2 posto α = 1/e ( e e il numero di Nepero), verificare se le funzioni

di iterazione

φ1(x) = x−log(x+ e−1) +√x+ 4− 1

1x+e−1 + 1

2√x+4

, φ2(x) = (1−log(x+e−1))2+4

sono adatte ad approssimare la radice nell’intervallo [−0.2,0.2] con

il metodo delle approssimazioni successive.

183

Page 188: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Traccia della soluzione

Il dominio della funzione e D = (−α,∞) ∩ [−4,∞).

Inoltre, f e continua in D, limx→+∞f(x) = +∞ e

f ′(x) =1

x+ α+

1

2√x+ 4

> 0 ∀ x ∈ D − {−4} se α : −4 ∈ D).

Pertanto, per i valori di α per i quali 0 ∈ D deve accadere

f(0) = log(α) + 1 < 0⇔ α <1

e.

(Oss: Se 0 /∈ D, allora deve essere limx→−αf(x) < 0.)

Osservare, infine, che φ1(x) e la funzione di iterazione del metodo delle

tangenti applicato alla funzione assegnata, mentre il punto unito della

funzione φ2(x) non puo essere uno zero della funzione f(x) data.

184

Page 189: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

ESERCIZIO 7

Considerata la successione{uk = euk−1 − 0.5u2

k−1 − uk−1 − 1, k ≥ 1u0 ∈ [−0.5,0.5]

,

determinare il valore limite

λ = limk→+∞

uk.

185

Page 190: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

ESERCIZIO 8

Si consideri la seguente equazione non lineare

√x− 1− eαx = 0

dipendente dal parametro reale α.

8.1 Determinare per quali valori di α l’ equazione ammette radici reali.

8.2 Posto α = −2, proporre almeno due funzioni di iterazione distinte

che generano procedimenti iterativi convergenti, ma con diverso

ordine di convergenza, alla radice piu piccola mediante il metodo

delle approssimazioni successive.

8.3 Per ognuno dei metodi generati al passo precedente, specificare la

scelta dell’approssimazione iniziale e il tipo di convergenza.

186

Page 191: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

ESERCIZIO 9

Stabilire se, scelto un opportuno numero reale x0, le seguenti succes-

sioni convergono e, se possibile, determinarne il limite

xn = xn−1 −e−xn−1 − cos(xn−1)

sin(xn−1)− e−xn−1

xn = −log(cos(xn−1))

xn = arcos(e−(xn−1))

Suggerimento: Verificare che le tre successioni sono costruite mediante funzioni di

iterazione generate da una stessa equazione non lineare

187

Page 192: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

ESERCIZIO 10

Si considerino le seguenti successioni

yn+1 = λ− e−yn, e yn+1 = λ√yn − yn

dipendenti dal parametro reale λ.

10.1 Stabilire quante e quali di esse convergono.

10.2 Per le successioni che convergono, stabilire se e in che modo e

possibile stimare il valore del limite con almeno 5 decimali esatti.

10.3 Per le successioni che convergono piu velocemente, stabilire se e

possibile proporre un procedimento piu efficiente per la stima del

limite con la precisione richiesta al punto precedente.

188

Page 193: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Soluzione

La prima successione e generata dalla funzione di iterazione ϕ1(y) =

λ − e−y, che rappresenta una funzione continua e derivabile in tutto

l’asse reale. Si osserva che

ϕ′1(y) = e−y > 0 ∀ y ∈ R.

Inoltre

|ϕ′1(y)| < 1 ∀ y > 0.

Pertanto la successione puo generare un procedimento iterativo con-

vergente in modo monotono ad un punto appartenente al semiasse

positivo con ordine di convergenza p = 1. Per stabilire per quali valori

di λ esiste il punto unito di ϕ1(y), e necessario studiare l’equazione non

lineare equivalente, ovvero

f(y) = λ− e−y − y = 0.

Da tale studio si deduce facilmente che per λ ≥ 1 la funzione f(y)

ammette un unico zero nel semiasse positivo.

189

Page 194: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Si procede in modo analogo per la seconda successione, la cui funzione

di iterazione e ϕ2(y) = λ√y − y. Si osservi che questa funzione e

definita e continua solo nel semiasse positivo; pertanto, se ammette

punto unito, quest’ultimo apparterra al semiasse positivo. Osservare

che l’equazione non lineare equivalente e

λ√y − 2y = 0

le cui radici sono ξ1 = 0 e ξ2 = λ2

4 . Pertanto, ϕ2(y) non puo generare

un procedimento iterativo convergente a ξ1 = 0 in quanto non e deri-

vabile in tale punto se λ 6= 0. Al contrario, poiche ϕ′2(ξ2) = 0, allora

esiste un intorno di ξ2 nel quale |ϕ′2(y)| < 1. Pertanto, la seconda

successione converge a ξ2 con ordine di convergenza almeno 2. Poiche

ϕ′′2(y) = − λ4y√y 6= 0, ∀ λ 6= 0, la convergenza e quadratica.

190

Page 195: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

ESERCIZIO 11 Si considerino i seguenti procedimenti iterativi dipendenti dalparametro reale e non nullo c e riferiti ad una funzione f ∈ C1(R)

xn = xn−1 − f(xn−1)

c, n ≥ 1

xn = xn−1 − f(xn−1)(xn−1 − c)f(xn−1)− f(c)

, n ≥ 1.

11.1 Stabilire per quale scelta del parametro c almeno uno dei due procedimentiiterativi ha ordine di convergenza 2 quando usato per risolvere numericamentel’equazione non lineare f(x) = 0.

11.2 Stabilire se il metodo individuato al passo precedente e adatto ad approssimarelo zero della seguente famiglia di equazioni non lineari dipendenti dal parametroreale k

e−x − x− k = 0

11.3 In caso di risposta affermativa al punto precedente, discutere la convergenzain termini di monotonia, ordine e scelta del punto iniziale.

191

Page 196: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

ESERCIZIO 12 Stabilire quale dei seguenti procedimenti iterativi

xn = xn−1 − f(xn−1)(xn−1 − xn−2)

f(xn−1)− f(xn−2), n ≥ 2

xn = xn−1 − f(xn−1)

2, n ≥ 1

xn = xn−1 +f(xn−1)

f ′(xn−1), n ≥ 1

converge meno velocemente alla radice positiva piu grande della seguente equazionenon lineare

x3 − 3x2 + 2x = 0.

192

Page 197: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

ESERCIZIO 13 Si considerino le seguenti successioni

xn = λ√xn−1 − xn−1, λ ∈ R

xn = exn−1 − 0.5x2n−1 − xn−1 − 1

xn = xn−1 +cos(xn−1)− exn−1

sin(xn−1)− exn−1

Determinare, se possibile, quelle che convergono piu velocemente al proprio limite.

193

Page 198: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

ESERCIZIO 14

Si consideri la seguente funzione dipendente dalla variabile reale x

g(x) =√

1 + x2.

14.1 Stabilire quale dei seguenti punti

x0 = −3

2, x0 = 1, x0 =

1

2

rappresenta una buona scelta del punto iniziale della successione

xn+1 = φ(xn), n ≥ 0,

con φ(x) pari alla funzione di iterazione del metodo delle tangenti, affinchequest’ultima risulti convergente all’estremo relativo della funzione g(x). Motivarela risposta.

14.2 Indicato con p l’ordine di convergenza del metodo considerato al punto prece-dente, proporre, se possibile, almeno un altro metodo del punto unito conver-gente all’estremo relativo di g(x) con ordine di convergenza non inferiore a p.Discutere la scelta del punto iniziale.

194

Page 199: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

Traccia della soluzione Si richiede di determinare gli zeri della funzione

f(x) = g′(x) =x√

1 + x2.

Si osserva che la funzione e definita e continua in R. Scelto I = [−b, b], poichef(x) > 0⇔ x > 0 e f ′(x) = 1

(1+x2)√

1+x2e continua e > 0 ∀x ∈ R, esiste un unico zero

di f(x) in I.

Inoltre, poiche f ′′ = − 3x

(1+x2)52

e continua, e possibile applicare il metodo di Newton

in I, ∀ b > 0. Poiche risulta f ′′(x) = 0 ⇔ x = 0 ∈ I, non e possibile scegliere comepunto iniziale l’estremo di Fourier.

Osserviamo che la funzione di iterazione del metodo delle tangenti per il problemaconsiderato e

φ(x) = x− f(x)

f ′(x)= x− x(1 + x2) = −x3

da cui si ha che |φ′(x)| < 1 ⇔ 3x2 < 1 ⇔ |x| < 1√3. Pertanto, l’unico punto iniziale

accettabile, tra i tre proposti, e x0 = 12. (Scegliendo b = 1

2, sono verificate le ipotesi

del I teorema sulla condizione sufficiente per la convergenza del metodo del punto

unito.)

195

Page 200: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

D’altra parte si osserva che la successione generata dal metodo delle tangenti e

xn = −3x3n−1

che converge a 0 (zero della funzione considerata) quando |x0| < 1.

Infine, calcolando le derivate fino all’ordine 3 di φ(x), si verifica facilmente che l’ordinedel metodo e p = 3.

14.2 Verificare che il metodo della tangente fissa con c = 1 ha ordine di convergenza

p = 3.

196

Page 201: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

ESERCIZIO 15

Assegnato a ∈ R+, stabilire quale dei seguenti procedimenti iterativi

xn+1 =xn(x2

n + 3a)

3x2n + a

, n ≥ 0,

xn+1 = xn + c(x2n − a), n ≥ 0, c ∈ R,

xn+1 =x2n + a

2xn, n ≥ 0,

converge piu velocemente a√a. Si discuta la scelta del punto iniziale.

197

Page 202: Metodi Numerici con Elementi di Programmazione (A.A ......Docente Vittoria Bruni Email: vittoria.bruni@sbai.uniroma1.it U cio: Via A. Scarpa, Pal. B, I piano, Stanza n. 16 Tel. 06

ESERCIZIO 16

Si consideri la seguente equazione non lineare

λ√y − 2y = 0,

dipendente dal parametro reale λ.

16.1 Stabilire per quali valori del parametro λ e possibile proporre almeno 3 pro-cedimenti iterativi distinti che generano una successione convergente alla radicenon nulla dell’equazione data con ordine di convergenza almeno 2.

16.2 Per ognuno dei procedimenti proposti al punto precedente, dare una stimadell’errore di troncamento che si commette alla centesima iterazione.

16.3 Quale procedimento iterativo e il piu conveniente?

198