EQUAZIONI non LINEARI
Francesca PelosiDipartimento di Matematica, Universita di Roma “Tor Vergata”
CALCOLO NUMERICO e PROGRAMMAZIONE
http://www.mat.uniroma2.it/∼pelosi/
EQUAZIONI non LINEARI – p.1/44
EQUAZIONI NON LINEARIData una funzione f : R → R consideriamo il problema dideterminare i valori x tali che
f(x) = 0
Tali valori sono solitamente chiamati zeri o radici dellafunzione f .
Esempi:− Equazioni algebriche: Pn(x) =
∑ni=0 aix
i = 0
− x + 4 sin(x) = 0, ex + x2 = 0,√
x − log(x) = 3
EQUAZIONI non LINEARI – p.2/44
EQUAZIONI NON LINEARI
In generale non sono disponibili formule esplicite per ladeterminazione delle radici di una funzione (per esempioequazioni algebriche n > 4)
⇒ metodi iterativi
Tecniche che consentono di approssimare le soluzionicon un prestabilito grado di precisione
A partire da una approssimazione iniziale x0 sicostruisce una successione x1, x2, . . . che, sottoopportune ipotesi, risulta convergere alla radicecercata
EQUAZIONI non LINEARI – p.3/44
Procedimenti iterativiSia P un problema ed α una soluzione del problema P .Supponiamo di utilizzare un procedimento iterativo per ladeterminazione di α che genera una successione{xi}i=0,1,... convergente ad α.È importante tener presente tre questioni fondamentali:1. Scelta del valore di innesco e convergenza
Supponiamo di considerare procedimenti iterativiricorrenti ad un passo xi+1 = φ(xi) è necessario perpoter innescare il procedimento un punto di innesco x0
DEF: Un metodo converge localmente ad α se la convergenza
della successione {xi} dipende in modo critico dalla vicinanza dix0 ad α. Il procedimento e globalmente convergente quando laconvergenza non dipende da quanto x0 e vicino ad α.
Per i metodi a convergenza locale la scelta del punto diinnesco è cruciale.
EQUAZIONI non LINEARI – p.4/44
Procedimenti iterativi2. Velocità di convergenza:
DEF: data una successione {xi} convergente ad un limite α, siponga ei := xi − α. Se esistono due numeri reali p e C tali che sia
limi→∞
|ei+1||ei|p
= C
si dice che la successione ha ordine di convergenza p efattore di convergenza C .
Per p = 1 la convergenza si dice lineare
Per p = 2 la convergenza si dice quadratica.
Nel caso p = 1 si deve necessariamente avere C < 1.
Un metodo iterativo è convergente di ordine p se tale è lasuccessione da esso generata.
EQUAZIONI non LINEARI – p.5/44
Procedimenti iterativi3. Criteri di arresto
Chiaramente non è possibile generare infinite iterate dellasuccessione. Il procedimento dovrebbe arrestarsi quando
|ei| = |xi − α| < toll
Non disponendo della soluzione è necessario procurarsiuna stima di ei. Una possibile strategia è quella diapprossimare ei con |xi+1 − xi|. Si ottiene il criterio diarresto assoluto
|xi+1 − xi| < tollA
Il criterio di arresto assoluto può fallire:se tollA = 10−6 e |α| ' |xi| ' 10−12 tolleranza troppo grande
se tollA = 10−6 e |α| ' |xi| ' 1012 tolleranza troppo piccola
EQUAZIONI non LINEARI – p.6/44
Procedimenti iterativi3. ... criteri di arresto
conviene usare un criterio di arresto relativo dato da
|xi+1 − xi||xi+1|
< tollR
OSS: la tolleranza utilizzata nel criterio di arrestorelativo NON deve essere minore della precisione dimacchina, ma
tollR > εm
(due numeri macchina non possono avere distanzarelativa minore di εm)
EQUAZIONI non LINEARI – p.7/44
Procedimenti iterativi3. ... criteri di arresto
Per equazioni non lineari si può anche utilizzare ilcontrollo del residuo:
|f(xi+1)| ≤ toll
se |f ′(α)| << 1: è inaffidabile( |ei| potrebbe essere molto grande)se |f ′(α)| >> 1: troppo restrittivose |f ′(α)| ' 1: produce un indicazione soddisfacente
Quando non si ha la certezza della bontà dei tests(su xi e su f ), conviene includerli entrambi,In pratica se il criterio di arresto funziona, non si ha lasoluzione α, ma solo una sua approssimazione
EQUAZIONI non LINEARI – p.8/44
Metodo di bisezioneIl metodo di bisezione è il metodo iterativo più sempliceper approssimare gli zeri reali di una funzione.
Ipotesi:1) f(x) continua nell’intervallo [a, b]
2) f(a)f(b) < 0
per il teorema degli zeri ammette almeno una soluzione α
di f(x) = 0, in (a, b).
Si procede suddividendo ad ogni passo l’intervallo [a, b] ametà e determinando in quale dei due sottointervalli sitrova la soluzione, dimezzando così l’ampiezzadell’intervallo che contiene α.
EQUAZIONI non LINEARI – p.9/44
Metodo di bisezioneALGORITMO
1. Si pone a0 := a e b0 := b
2. Per i = 0, 1, . . . , nmax si calcolano
xi :=ai + bi
2, e f(xi)
1. Se f(xi) · f(ai) < 0 ⇒ ai+1 := ai, bi+1 := xi
2. Altrimenti se f(xi) · f(bi) < 0 ⇒ ai+1 := xi, bi+1 := bi
3. altrimenti se f(xi) = 0 ⇒ xi := α
3. Il procedimento viene arrestato se per un indice i risulta
|f(xi)| ≤ toll e/o
|ai − bi| ≤ toll
EQUAZIONI non LINEARI – p.10/44
Metodo di bisezionePer costruzione ad ogni passo l’ampiezza dell’intervallo èdimezzata, dopo n passi arriviamo all’intervallo [an, bn] diampiezza:
bn − an =bn−1 − an−1
2=
bn−2 − an−2
22= · · · =
b0 − a0
2n
Se come stima di α prendiamo xn = an+bn
2 abbiamo
|en| = |xn − α| ≤ b0 − a0
2n+1
Se poniamo b0−a02n+1 ≤ ε otteniamo n da
2n+1 ≥ b0 − a0
ε⇒ n ≥ log2
(
b0 − a0
ε
)
− 1
EQUAZIONI non LINEARI – p.12/44
Metodo di bisezioneIl metodo di bisezione converge globalmente allasoluzione con la sola ipotesi che f sia continuanell’intervallo [a, b].
La convergenza è però lenta e questo costituisce il limitedel metodo: ad ogni passo si riduce l’errore di 1/2, perridurlo di 1/10 (1 cifra decimale) occorrono circa 3.3 passi.
Una spiegazione può essere ricercata nel fatto che non sitiene conto dei valori della funzione ma soltanto dei segni.
Geometricamente il metodo costruisce ad ogni passol’approssimazione della radice calcolando l’intersezionecon le ascisse della retta passante per i punti
(a, segn f(a)) , (b, segn f(b))
EQUAZIONI non LINEARI – p.13/44
Metodo della regula falsiUn modo naturale per migliorare il metodo di bisezione èquello di considerare anche i valori che la funzioneassume negli estremi dell’intervallo
Si prende come nuova approssimazione della soluzionel’intersezione delle ascisse con la retta passante per
(a, f(a)) , (b, f(b))
{
y − f(a) = (f(b)−f(a))b−a (x − a),
y = 0,
da cui si ottiene
x = a − f(a)(b − a)
f(b) − f(a)
EQUAZIONI non LINEARI – p.14/44
Metodo della regula falsiIl metodo risultante è noto come metodo della regula falsio della falsa posizione1. Dato [a0, b0] tale che f(a0)f(b0) < 0
2. Finche non sia verificato un criterio di arresto, poni
1. xi := ai − f(ai)(bi − ai)
f(bi) − f(ai)2. Se f(xi) · f(ai) < 0 ⇒ ai+1 := ai, bi+1 := xi
3. Altrimenti ⇒ ai+1 := xi, bi+1 := bi
4. i = i + 1Il metodo genera una successione di intervalli in cui ècontenuta la radice: la scelta dell’intervallo in base alsegno della funzione, comporta una convergenza globale
è più veloce rispetto al metodi di bisezione, anche se ingenerale [ai, bi]i→∞ 6→ 0 pertanto il criterio di arrestobasato sull’ampiezza dell’intervallo non è applicabile.
EQUAZIONI non LINEARI – p.15/44
Altre idee . . .Data f(x), x0 f(x0): si approssima la funzione con unaretta per (x0, f(x0))
y = f(x0) + m(x − x0)
Si ottiene una versione linearizzata del problema f(x) = 0,{
y = 0,
y = f(x0) + m(x − x0),da cui x1 = x0 −
f(x0)
m
In generalexi+1 = xi − f(xi)
mi
A seconda della scelta di mi si ottengono:metodo delle corde (mi = m = costante),metodo delle secanti e metodo di Newton
EQUAZIONI non LINEARI – p.16/44
Metodo delle secantimi: coefficiente angolare della retta per (xi, f(xi)) e
(xi−1, f(xi−1))
mi =f(xi) − f(xi−1)
(xi − xi−1)
xi+1 = xi − f(xi)(xi − xi−1)
f(xi) − f(xi−1)
Può essere visto come una variante della regula falsi incui sono richieste due approssimazioni iniziali senzaalcun’altra condizione e senza la necessità di controllare ilsegno di f(x)
La convergenza del metodo è garantita se leapprossimazioni iniziali sono “abbastanza vicine” allaradice α: convergenza locale
EQUAZIONI non LINEARI – p.17/44
Metodo di Newtonmi: derivata prima di f in xi
mi = f ′(xi)
xi+1 = xi −f(xi)
f ′(xi)
Geometricamente si prende come nuovaapprossimazione l’intersezione delle ascisse con la rettatangente a f in (xi, f(xi))
Alla i−esima iterazione questo metodo richiede duevalutazioni funzionali
f(xi), f ′(xi)
L’aumento del costo computazionale è compensato dalfatto che la convergenza (locale) è di ordine superiore alprimo. In generale è quadratica
EQUAZIONI non LINEARI – p.18/44
Metodi di iterazione funzionaleLa ricerca degli zeri di una funzione f è ricondotta allostudio dei punti fissi di un’opportuna funzione g:
f(α) = 0 ⇔ g(α) = α
La successione delle approssimazioni sarà definitaassegnto x0 come:
xi+1 = g(xi), i = 0, 1 . . .
La funzione di iterazione g non è unica e può esserecostruita nei modi più diversi, ma non tutti daranno luogoa strumenti efficienti.
Bisogna studiare sotto quali condizioni la successionedelle iterate appartenga sempre al dominio di f e siaconvergente ad α.
EQUAZIONI non LINEARI – p.20/44
Metodi di iterazione funzionaleEX: Corde
f(x) = 0 ⇔ −f(x)
m= 0 ⇔ x − f(x)
m= x
⇒ g(x) = x − f(x)
m
EX: Newton
f(x) = 0 ⇔ − f(x)
f ′(x)= 0 ⇔ x − f(x)
f ′(x)= x
⇒ g(x) = x − f(x)
f ′(x)
EQUAZIONI non LINEARI – p.21/44
ConvergenzaRisultato importante teoricamente, ma nella pratica èdifficile stabilire a priori l’intervallo in cui sono soddisfattele ipotesi.
TEO (Ostrowski): Sia α un punto fisso di g ∈ C1[α − ρ, α + ρ]. Se
|g′(x)| < 1, ∀x ∈ [α − ρ, α + ρ]
allora ∀x0 ∈ [α − ρ, α + ρ] la successione delle iterate generata dag e tale che
1. xi → α unico punto fisso di g
2. xi ∈ [α − ρ, α + ρ]
DIM: Per ipotesi g è una contrazione per cui il punto fisso èunico (si dimostra per assurdo).
EQUAZIONI non LINEARI – p.24/44
ConvergenzaPer dimostrare che la successione converge si considera
xi+1 − α = g(xi) − g(α) (Teo della media)= g′(ηi)(xi − α)
dove ηi ∈ (α, xi). Per 2. |g′(ηi)| < M < 1 per cui
|xi+1 − α| < M |xi − α| < · · · < M i+1|x0 − α|
⇒ limi→∞
|xi+1 − α| = 0
Inoltre dalla continuità di g′ si ha
limi→∞
|xi+1 − α||xi − α| = lim
i→∞g′(ηi) = g′(α)
�
EQUAZIONI non LINEARI – p.25/44
ConvergenzaLa convergenza può esserci in insiemi molto più grandi diquelli in cui |g′(x)| < 1: condizione sufficiente,
convergenza locale
x0
x1 x
3x
4x
2
α
α
x0
x1
x2
g(x)
x3
−1 < g′(α) < 0: 0 < g′(α) < 1:convergenza alternata convergenza monotona
xi+1 − α = g′(ηi)(xi − α), con ηi ∈ (α, xi)
EQUAZIONI non LINEARI – p.26/44
ConvergenzaSe |g′(α)| > 1 allora |α − xi+1| > |α − xi|:
locale divergenza
x1
x3
x4
x2
x0
x1
x0
α
g′(α) < −1 g′(α) > 1
EQUAZIONI non LINEARI – p.27/44
Ordine di convergenzaPer i metodi di iterazione funzionale è possibile anchedare una relazione tra ordine del metodo e molteplicità diα rispetto a g′
TEO: Sia α ∈ I (opportuno intervallo) punto fisso di g ∈ Cp[I] con p ≥ 2.Se per un punto x0 ∈ I la successione {xi} e convergente e se
g′(α) = g′′(α) = · · · = g(p−1)(α) = 0 e g(p)(α) 6= 0
allora il metodo ha ordine di convergenza p e risulta
limi→∞
|xi+1 − α||xi − α|p =
g(p)(α)
p!
EQUAZIONI non LINEARI – p.28/44
Ordine di convergenzaDIM: Dallo sviluppo di Taylor si ha in generale
(tenuto conto che xi+1 = g(xi)):
xi+1 − α = g(xi) − g(α)
= g′(α)(xi − α) + g′′(α)(xi − α)2
2!+ · · ·
· · · + g(p−1)(α)(xi − α)p−1
(p − 1)!+ g(p)(ξ)
(xi − α)p
p!
dove ξ ∈ (xi, α). Quindi se valgono le hp del teorema si hala tesi. �
A parità di ordine di convergenza p, quanto più piccola
risulterà la quantità g(p)(α)p! tanto più veloce sarà la
convergenza delle iterate ad α.
EQUAZIONI non LINEARI – p.29/44
Convergenza metodo di NewtonIl metodo di Newton può essere visto come un metodo diiterazione funzionale con la funzione g data da
g(x) = x − f(x)
f ′(x)
Osservando che se f ∈ C2 e f ′(α) 6= 0 (ovvero α radicesemplice)
g′(x) =f ′′(x)f(x)
(f ′(x))2⇒ g′(α) = 0
quindi il metodo è localmente sempre convergente e laconvergenza è almeno quadratica. Per radici doppie(f ′(α) = 0), o multiple in generale, la convergenza siriduce a lineare.
EQUAZIONI non LINEARI – p.30/44
Convergenza metodo di NewtonRisultati di convergenza globale
TEO:Sia f ∈ C2[α, α + ρ] tale che
(i) f(x)f ′′(x) > 0 in (α, α + ρ]
(ii) f ′(x) 6= 0 in (α, α + ρ]
allora ∀x0 ∈ (α, α + ρ] la successione originata dal metodo diNewton DECRESCE monotonicamente ad α. Per gli intorni sinistri[α − ρ, α] si ottiene una successione che converge in modomonotono CRESCENTE ad α.
EQUAZIONI non LINEARI – p.31/44
Esecizio 1.Posto f(x) = x8 − 2:
1) analizzare la convergenza di Newton per approssimare la radice positiva di f ;
1) f(x) = 0 ⇔ x8 − 2 = 0, per x = ± 8√
2, si studia la convergenza ad α = 8√
2. Costruiamo
la g del metodo di iterazione funzionale associata ad f , consideriamo le derivate f ′(x) = 8x7,
f ′′(x) = 56x6:
g(x) = x − f(x)
f ′(x)= x − x8 − 2
8x7=
7x8 + 2
8x7
g′(x) =f(x)f ′′(x)
(f ′(x))2=
56x6(x8 − 2)
64x14=
7
8
x8 − 2
x8
g′(α) = g′(8√
2) = 0 ⇒ convergenza locale
Vediamo se possiamo applicare il teorema di convergenza del metodo di Newton:
a) per (α, α + ρ] : si ha f(x) > 0, f ′′(x) > 0 ∀x > α per cui f(x)f ′′(x) > 0, e inoltre
f ′(x) 6= 0 ∀x > α ⇒ convergenza per x > α (monotona decrescente)
b) per [α − ρ, α) : si ha f(x) < 0, f ′′(x) > 0 ⇒ l’ipotesi (i) del teorema non e soddisfatta.
EQUAZIONI non LINEARI – p.33/44
Esecizio 1 (segue ...)Studiamo |g′(x)| < 1 ⇔
78
x8−2x8
< 1,
78
x8−2x8
> −1⇔
∀x,
x < − 8
√
1415
, x > 8
√
1415
Qunidi per x > 8
√
1415
si ha la convergenza (Per il Teorema di Ostrowski la condizione
|g′(x)| < 1 deve essere verificata in un intorno di α, ma poiche per x > α si ha 0 < g′(x) < 1
la convergenza e monotona, posso estendere l’intorno a tutto (α, +∞))
0.5 1 1.5 2
0
50
100
150
200
250
Newton
x0=2
0 0.5 1 1.5 2
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2
Iterate
x0=2
EQUAZIONI non LINEARI – p.34/44
Esecizio 1 (segue ...)2) indicare quante iterazioni del metodo di bisezione sono necessarie per approssimare la radice positiva
di f con una precisione ε < 10−2, considerando [a, b] =[
12, 32
]
.
2) Si vuol trovare k per cui |ek| = |xk − α| < 10−2
|ek| ≤ |bk − ak|2
=b − a
2k+1< 10−2
⇒(
3
2− 1
2
)
· 1
2k+1< 10−2 ⇒ 2k+1 > 100
⇒ k > log2(100) − 1 ' 5.64
⇒ almeno 6 iterazioni
EQUAZIONI non LINEARI – p.35/44
Esecizio 2.L’equazione f(x) = x3 − 3x2 + 2x = 0 puo immediatamente essere trasformata nel seguente
problema di punto fisso g(x) = x con g(x) = x3 − 3x2 + 3x. Analizzare la convergenza e l’ordine del
metodo delle iterate in un introrno delle 3 soluzioni.
f(x) = 0 ⇔ x3 − 3x2 + 2x = 0 ⇔ x(x − 1)(x − 2) = 0, per α = 0, β = 1, γ = 2.
g′(x) = 3x2 − 6x + 3, la convergenza e garantita in un intorno della soluzione se |g′(x)| < 1 :
g′(α) = g′(0) = 3 ⇒ divergenza locale
g′(β) = g′(1) = 0 ⇒ convergenza locale (almeno di ordine p = 2)
g′(γ) = g′(2) = 3 ⇒ divergenza locale
Analizziamo solo la convergenza per β = 1 e studiamo dove vale |g′(x)| < 1 ⇔
|g′(x)| = |3(x − 1)2| = 3(x − 1)2 < 1 ⇒ convergenza locale
per x ∈(
1 − 1√3
, 1 +1√3
)
.
Inoltre
g′′(x) = 6x − 6 ⇒ g′′(1) = 0 ⇒ convergenza almeno di ordine p = 3
g′′′(x) = 6 6= 0 ⇒ convergenza esattamente di ordine p = 3.
EQUAZIONI non LINEARI – p.36/44
Esecizio 3.Studiare la convergenza del metodo di Newton applicato a f(x) = 2
3√
3x3 + x2 − 1.
a) Si fa uno studio della funzione per capire dove sono gli zeri:
f ′(x) =2√3
x2 + 2x = 2x
(
x√3
+ 1
)
= 0, per x = 0, x = −√
3,
con f(0) = −1, f(−√
3) = 0, ⇒ α = −√
3 radice doppia
f ′(x) > 0 (f crescente) per x > 0 e x < −√
3.
Si osserva che poiche per x > 0 la funzione e crescente con f(0) = −1 < 0 e
f(1) = 2√3
> 0 ⇒ c’e un ’altra radice β ∈ (0, 1), tale radice e semplice in quanto
f ′(x) 6= 0, per x > 0. Studiamo la derivata seconda:
f ′′(x) =4√3
x + 2 = 0 ⇔ x = −√
3
2
f ′′(x) > 0 (f convessa) per x > −√
32
.
b) Convergenza a β ∈ (0, 1): Per x > β si ha f(x) > 0 e f ′′(x) > 0 con f ′(x) 6= 0 quindi per il
teorema del metodo di Newton si ha convergenza monotona decrescente. Da un esame grafico si
vede che la convergenza si puo estendere ∀x0 > 0 (eventualmente dopo la prima iterazione).
L’ordine e almeno 2 in quando la radice e semplice.
EQUAZIONI non LINEARI – p.37/44
Esecizio 3 (segue ...)Convergenza a β ∈ (0, 1)
−2 −1 0 1 2 3
0
2
4
6
8
10
12
14
16
18
x0=0.2
−2 −1 0 1 2 3
0
2
4
6
8
10
12
14
16
18
x0=3
Convergenza ad α = −√
3: f(x) < 0 e f ′′(x) < 0 per x < −√
32
con f ′(x) 6= 0 per x 6= α
quindi per il teorema sul metodo di Newton si ha convergenza monotona crescente in (−∞,−√
3)
e monotona decrescente in (−√
3,−√
32
). Da un esame grafico si vede che c’e convergenza
∀x0 < 0, eventualmente dopo la prima iterazione. Ordine p = 1 per radice doppia.
−4 −3 −2 −1 0 1 2 3
−5
0
5
10
15
x0=−4
EQUAZIONI non LINEARI – p.38/44
Esecizio 4.Assegnata l’equazione f(x) = 5
2x3 − 15
2x2 + 6x − 1 = 0 analizzare la convergenza del metodo di
Newton dopo un breve studio analitico dell’andamento della funzione.
Si ha:
f ′(x) =15
2x2 − 15x + 6 = 0, per x1 = 1 − 1√
5' 0.5, x2 = 1 +
1√5' 1.5
f ′(x) > 0 per x ∈ (−∞, 1 − 1√5) ∪ (1 +
1√5
, +∞)
con f(x1) =1√5' 7
16, f(x2) = − 1√
5' − 7
16,
inoltre limx→−∞
f(x) = −∞, limx→+∞
f(x) = +∞- f ′(x) > 0 (f crescente) per x < x1 e poiche f(x1) > 0 e f(0) = −1 < 0 ⇒ c’e una radice
semplice α ∈ (0, x1).
- f ′(x) > 0 (f crescente) per x > x2 e poiche f(x2) < 0 e f(x) tende a +∞ per x che tende a
+∞⇒ c’e una radice semplice β ∈ (x2, +∞).
- Inoltre poiche f(x1)f(x2) < 0 c’e una terza radice γ ∈ (x1, x2) = (1 − 1√5, 1 + 1√
5).
Studiamo la derivata seconda:
f ′′(x) = 15x − 15 = 0 ⇔ x = 1, con f(1) = 0 ⇒ γ = 1
f ′′(x) > 0 ⇔ x > 1
EQUAZIONI non LINEARI – p.39/44
Esecizio 4 (segue ...)a) Convergenza ad α in (−∞, 1 − 1√
5): per x < α si ha f(x) < 0 e f ′′(x) < 0 con f ′(x) 6= 0
quindi per il teorema sul metodo di Newton si ha convergenza monotona crescente per
x0 ∈ (−∞, α). L’ordine e almeno 2 in quando la radice e semplice. Per x > α si ha f(x) > 0
e f ′′(x) < 0, le ipotesi del teorema non sono soddisfatte.
b) Convergenza a β in (1 + 1√5, +∞): per x > β si ha f(x) > 0 e f ′′(x) > 0 con f ′(x) 6= 0
quindi per il teorema sul metodo di Newton si ha convergenza monotona decrescente per
x0 ∈ (β, +∞). L’ordine e almeno 2 in quando la radice e semplice. Nel’intorno sinistro di β le
ipotesi del teorema non sono soddisfatte.
c) Convergenza a γ = 1 in (1 − 1√5, 1 + 1√
5). Le condizioni del teorema sul metodo di Newton non
sono soddisfatte: per x > 1 si ha f(x) < 0 e f ′′(x) > 0 mentre per x < 1 si ha f(x) > 0 e
f ′′(x) < 0. Quindi il teorema non puo essere applicato.
0 0.5 1 1.5 2−1
−0.8
−0.6
−0.4
−0.2
0
0.2
0.4
0.6
0.8
1
α γ β
EQUAZIONI non LINEARI – p.40/44
Esecizio 5.Assegnata l’equazione f(x) = (ex − 1)2 = 0
i) analizzare la convergenza del metodo di Newton per approssimarne le radici e in caso di
convergenza determinare l’ordine.
ii) Stabilire se il metodo iterativo xi+1 = g(xi) con g(x) = x − ex−1ex
e convergente e in caso
affermativo determinarne l’ordine.
Si ha:f(x) = (ex − 1)2 = 0, per x = 0 ⇒ α = 0, f(x) > 0 ∀x 6= 0
f ′(x) = 2ex(ex − 1) = 0 per x = 0 ⇒ α radice doppia
f ′(x) > 0 per x > 0
f ′′(x) = 2ex(2ex − 1) = 0 per ex =1
2⇒ x = ln
1
2< 0
f ′′(x) > 0 per x > ln1
2- in (0, +∞) : si ha f(x)f ′′(x) > 0 e f ′(x) 6= 0 quindi per il teorema del metodo di Newton si ha
convergenza monotona decrescente ∀x0 ∈ (0, +∞)
- in (ln( 12), 0) : si ha f(x)f ′′(x) > 0 e f ′(x) 6= 0 quindi per il teorema del metodo di Newton si ha
convergenza monotona crescente ∀x0 ∈ (ln(1/2), 0) (o in ogni intervallo chiuso della forma [α− ρ, α)
contenuto in (ln(1/2), 0))
⇒ convergenza monotona ∀x0 > ln(1/2), del primo ordine in quanto la radice e doppia.
EQUAZIONI non LINEARI – p.41/44
Esecizio 5.Assegnata l’equazione f(x) = (ex − 1)2 = 0
i) analizzare la convergenza del metodo di Newton per approssimarne le radici e in caso di
convergenza determinare l’ordine.
ii) Stabilire se il metodo iterativo xi+1 = g(xi) con g(x) = x − ex−1ex
e convergente e in caso
affermativo determinarne l’ordine.
−1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 1−1
−0.5
0
0.5
1
1.5
2
2.5
x0=1
y=f(x)
EQUAZIONI non LINEARI – p.41/44
Esecizio 5 (segue ...)ii) Sia il metodo delle iterate con:
g(x) = x − ex − 1
exe g(x) = x per α = 0,
g′(x) = 1 − ex ex − ex(ex − 1)
ex ex= 1 − 1
ex
g′(0) = 0 ⇒ convergenza locale (almeno) del secondo ordine
g′′(x) =1
ex6= 0 ∀x ⇒ (esattamente) del secondo ordine
Analizzando la condizione |g′(x)| < 1 si trova che vale per x > ln(1/2) e quindi si ha convergenza in
ogni intorno di α contenuto in (ln(1/2), +∞)
−1 −0.5 0 0.5 1−1
−0.8
−0.6
−0.4
−0.2
0
0.2
0.4
0.6
0.8
1
y=g(x)
x0=1
−1 −0.5 0 0.5 1−1
−0.8
−0.6
−0.4
−0.2
0
0.2
0.4
0.6
0.8
1
y=g(x)
x0=0.8
Si nota graficamente convergenza anche per x0 < ln(1/2).
EQUAZIONI non LINEARI – p.42/44
Esecizio 6.Assegnata l’equazione f(x) = e1−x − 1 = 0
i) analizzare la convergenza del metodo di Newton per approssimarne le radici e in caso di
convergenza determinare l’ordine.
ii) Stabilire se il metodo iterativo xi+1 = g(xi) con g(x) = x + e1−x − 1 e convergente e in
caso affermativo determinarne l’ordine.
i) Si ha:f(x) = e1−x − 1 = 0, per x = 1 ⇒ α = 1, f(x) > 0 per x < 1
f ′(x) = −e1−x < 0, ∀x ⇒ α radice semplice
f ′′(x) = e1−x > 0 ∀x
- in (1, +∞) : si ha f(x) < 0, f ′′(x) > 0 quindi il teorema del metodo di Newton non e applicaile
- in (−∞, 1) : si ha f(x)f ′′(x) > 0 e f ′(x) 6= 0 quindi per il teorema del metodo di Newton si ha
convergenza monotona crescente ∀x0 ∈ (−∞, 1) o in ogni intervallo chiuso della forma [1 − ρ, 1) ivi
contenuto (secondo ordine per radici semplici).
EQUAZIONI non LINEARI – p.43/44
Esecizio 6.Assegnata l’equazione f(x) = e1−x − 1 = 0
i) analizzare la convergenza del metodo di Newton per approssimarne le radici e in caso di
convergenza determinare l’ordine.
ii) Stabilire se il metodo iterativo xi+1 = g(xi) con g(x) = x + e1−x − 1 e convergente e in
caso affermativo determinarne l’ordine.
0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2−1
−0.5
0
0.5
1
1.5
y=f(x)
EQUAZIONI non LINEARI – p.43/44
Esecizio 6 (segue ...)ii) Sia il metodo delle iterate con:
g(x) = x + e1−x − 1 e g(x) = x per α = 1,
g′(x) = 1 − e1−x = 0 per x = 1 = α ⇒ convergenza locale (almeno) del secondo ordine
g′′(x) = e1−x 6= 0 ∀x ⇒ (esattamente) del secondo ordine
|g′(x)| < 1 per x > 1 − ln(2) ' 0.3
quindi si ha convergenza in ogni intorno di α contenuto in (1 − ln(2), +∞)
0 0.5 1 1.5 2
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2
y=g(x)
x0=2
0 0.5 1 1.5 2
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2
y=g(x)
x0=0
Si nota graficamente convergenza ∀x0 ∈ R.
EQUAZIONI non LINEARI – p.44/44