Risoluzione numerica di equazioni non lineari

Dario Fasino

D. Fasino f (x) = 0
Esempio: Equazione di Colebrook

L’equazione di Colebrook quantifica la perdita di pressione di

un fluido turbolento che attraversa una tubatura circolare:
 
1 ε/D 2.51
√ = 2 log10 + √
f 3.71 Re f

f = numero di Fanning (coefficiente di attrito)

ε/D = rugosità relativa della tubatura
Re = numero di Reynolds del fluido.

Problema
Dati Re, ε, D calcolare f .

̸ ∃ soluzione analitica, serve un metodo numerico

D. Fasino f (x) = 0
Forma del problema

Problema
Data f : D ⊂ R 7→ R continua, trovare x̄ ∈ D tale che

f (x̄) = 0.

Risolvibile con formule esplicite solo in casi semplici

I metodi numerici costruiscono successioni x1 , x2 , x3 . . .
che sotto ipotesi opportune convergono a x̄:

lim xk = x̄.
k →∞

Un elemento di tale successione viene scelto come approssimazione

di x̄ mediante un criterio di stop.

metodo iterativo + criterio di stop = algoritmo

D. Fasino f (x) = 0
Ordine di convergenza
Sia x0 , x1 , x2 . . . → x̄ ∈ R, ek = |xk − x̄|

Definizione: ordine di convergenza di {xk }

ek+1 /ek → 1 sublineare

ek+1 /ek → c, 0<c<1 lineare
ek+1 /ek → 0 superlineare
ek+1 /ekp → ℓ, 0<ℓ<∞ ordine p ⩾ 1

D. Fasino f (x) = 0
Ordine di convergenza
Sia x0 , x1 , x2 . . . → x̄ ∈ R, ek = |xk − x̄|

Definizione: ordine di convergenza di {xk }

ek+1 /ek → 1 sublineare

ek+1 /ek → c, 0<c<1 lineare
ek+1 /ek → 0 superlineare
ek+1 /ekp → ℓ, 0<ℓ<∞ ordine p ⩾ 1

Esempi
Se 0 < c < 1,
√
k
ek = c : convergenza sublineare
k
ek = c : convergenza lineare (p = 1)
2
ek = c (k ) : convergenza superlineare
k
ek = c (2 ) : convergenza quadratica (p = 2)

D. Fasino f (x) = 0
Ordine di convergenza
Sia x0 , x1 , x2 . . . → x̄ ∈ R, ek = |xk − x̄|

Definizione: ordine di convergenza di {xk }

ek+1 /ek → 1 sublineare

ek+1 /ek → c, 0<c<1 lineare
ek+1 /ek → 0 superlineare
ek+1 /ekp → ℓ, 0<ℓ<∞ ordine p ⩾ 1

Sia nk = numero di cifre corrette in xk . Vale

ek
nk ≈ − log10 .
|x̄|

Se l’OdC di {xk } è lineare allora nk+1 ≈ nk + log10 (1/c)

Se l’OdC di {xk } è p > 1 allora nk+1 ≈ pnk .

D. Fasino f (x) = 0
Metodo di bisezione
Teorema degli zeri
Se f ∈ C([a, b]) e f (a)f (b) < 0 allora ∃x̄ ∈ (a, b) : f (x̄) = 0.

Intervallo di separazione
Un intervallo [a, b] tale che f (a)f (b) < 0 è un intervallo di
separazione.

a -
x̄ b

D. Fasino f (x) = 0
Metodo di bisezione
Teorema degli zeri
Se f ∈ C([a, b]) e f (a)f (b) < 0 allora ∃x̄ ∈ (a, b) : f (x̄) = 0.

Intervallo di separazione
Un intervallo [a, b] tale che f (a)f (b) < 0 è un intervallo di
separazione.

a c -
x̄ b

D. Fasino f (x) = 0
Metodo di bisezione

Procedimento
Sia c il punto medio dell’intervallo attuale
Se f (c) = 0 allora stop
Altrimenti scegli il nuovo intervallo di separazione,
[a, c] oppure [c, b]
Ripeti il procedimento sul nuovo intervallo di separazione.

Convergenza globale. Se l’intervallo iniziale è [a0 , b0 ], al

k -esimo passo l’ampiezza dell’intervallo di separazione è

|b0 − a0 |
|bk − ak | = .
2k

D. Fasino f (x) = 0
Metodo delle secanti

Scelti due punti iniziali, x0 , x1

x1 x̄ -
x0

D. Fasino f (x) = 0
Metodo delle secanti

Scelti due punti iniziali, x0 , x1

tracciamo la retta secante. . .








x1  x̄ -
x0








D. Fasino f (x) = 0
Metodo delle secanti

Scelti due punti iniziali, x0 , x1

tracciamo la retta secante, calcoliamo il nuovo punto. . .








x1 x2  x̄ -
x0








D. Fasino f (x) = 0
Metodo delle secanti

Scelti due punti iniziali, x0 , x1

tracciamo la retta secante, calcoliamo il nuovo punto e ripetiamo
il processo: tracciamo la nuova secante. . .








x1 x2  x̄
 -

x0

 
 







D. Fasino f (x) = 0
Metodo delle secanti

Scelti due punti iniziali, x0 , x1

tracciamo la retta secante, calcoliamo il nuovo punto e ripetiamo
il processo: tracciamo la nuova secante, calcoliamo il prossimo
punto. . .








x1 x2  x̄
 -

  x3 x0

 







D. Fasino f (x) = 0
Metodo delle secanti

Iterazione
Fissati x0 , x1 punti iniziali,
xk − xk−1
xk+1 = xk − f (xk ) .
f (xk ) − f (xk−1 )

L’equazione della retta secante per i punti xk−1 e xk è

f (xk ) − f (xk−1 )
y = f (xk ) + (x − xk ).
xk − xk−1

Ponendo y = 0 e risolvendo la x si trova la formula del metodo.

D. Fasino f (x) = 0
Metodo delle secanti

Iterazione
Fissati x0 , x1 punti iniziali,
xk − xk−1
xk+1 = xk − f (xk ) .
f (xk ) − f (xk−1 )

La convergenza globale non è garantita:




x3 ? x1 x
2 
 x̄ -
hh 
 x0
hhhh

D. Fasino f (x) = 0
Metodo delle secanti

Iterazione
Fissati x0 , x1 punti iniziali,
xk − xk−1
xk+1 = xk − f (xk ) .
f (xk ) − f (xk−1 )

Sia ek = |x̄ − xk |.
Se f ∈ C 2 e gli errori iniziali e0 , e1 sono “piccoli” allora
ek
lim ek = 0, lim = 0.
k→∞ k→∞ ek−1

Convergenza locale e superlineare

D. Fasino f (x) = 0
Metodo delle tangenti (Newton)
Iterazione
Scelto x0 punto iniziale,

f (xk )
xk+1 = xk − .
f ′ (xk )



x̄  -
x2 x1 x0

D. Fasino f (x) = 0
Metodo delle tangenti (Newton)
Iterazione
Scelto x0 punto iniziale,

f (xk )
xk+1 = xk − .
f ′ (xk )

Sia ek = |x̄ − xk |.
Se f ∈ C 2 e l’errore iniziale e0 è “piccolo” allora
ek
lim ek = 0, lim = ℓ > 0.
k→∞ k→∞ ek2−1

Convergenza locale e quadratica.

D. Fasino f (x) = 0
Metodo delle tangenti (Newton)
Iterazione
Scelto x0 punto iniziale,

f (xk )
xk+1 = xk − .
f ′ (xk )

Teorema
Sia f ∈ C 2 in un intorno sufficientemente ampio di x̄.
Supponiamo che in tutti i punti di tale intorno valga
|f ′ (x)| ⩾ m > 0 e |f ′′ (x)| ⩽ M. Allora vale

M
|xk+1 − x̄| ⩽ L|xk − x̄|2 dove L = .
2m
In particolare, se η = L|x0 − x̄| < 1 allora il metodo è
convergente.
D. Fasino f (x) = 0
Metodo delle tangenti (Newton): Esempio

√
Calcolo di a
f (x) = x 2 − a = 0 Iterazione: xk+1 = . . . = 12 (xk + a/xk )
Punto iniziale: x0 = max{1, a}
Richiede solo operazioni aritmetiche!

Per a = 2 e x0 = 2 si ha

n xn fl(xn )
1 3/2 1.50000000000000
2 17/12 1.41666666666667
3 577/408 1.41421568627451
665857
4 470832 1.41421356237469
√
Nota: x̄ = 2 = 1.414213562373095 . . .

D. Fasino f (x) = 0
Iterazioni di punto fisso

Problema di punto fisso

Data g : D ⊂ R 7→ R trovare x̄ tale che g(x̄) = x̄.

Idea: Trasformare il problema di partenza f (x) = 0 in un

problema di punto fisso g(x) = x equivalente:

f (x̄) = 0 ⇐⇒ g(x̄) = x̄.

Iterazione di punto fisso

Scelto x0 costruire la successione xk+1 = g(xk ).

Sotto condizioni opportune, limk→∞ xk = x̄.

D. Fasino f (x) = 0
Iterazioni di punto fisso

Definizione: funzione contrattiva

g : D 7→ D è contrattiva se ∃ 0 ⩽ c < 1 tale che

|g(x) − g(y )| ⩽ c|x − y | ∀x, y ∈ D.

Una funzione contrattiva è una funzione Lipschitziana con costante di

Lipschitz minore di 1 che manda il suo dominio dentro se stesso.

Esempio
Se g : D 7→ D è derivabile e |g ′ (x)| ⩽ c < 1 allora g è contrattiva.

D. Fasino f (x) = 0
Iterazioni di punto fisso

Teorema (convergenza globale)

Se g : D 7→ D è contrattiva, allora ∃!x̄ ∈ D : x̄ = g(x̄).
Inoltre, ∀x0 ∈ D
xk+1 = g(xk ) → x̄
c ck
|xk − x̄| ⩽ 1−c |xk − xk−1 | ⩽ 1−c |x1 − x0 |.
Inoltre, se g ∈ C 1 allora
|xk+1 − x̄|
lim = |g ′ (x̄)|.
k→∞ |xk − x̄|

La convergenza è generalmente lineare.

D. Fasino f (x) = 0
Iterazioni di punto fisso

Teorema (convergenza locale)

Sia g : D ⊂ R 7→ R, g ∈ C 1 (D), tale che g(x̄) = x̄, |g ′ (x̄)| < 1.
Allora esiste I = [x̄ − δ, x̄ + δ] ⊂ D tale che
g è contrattiva in I. Inoltre, ∀x0 ∈ I,
xk+1 = g(xk ) → x̄
limk →∞ |xk+1 − x̄|/|xk − x̄| = |g ′ (x̄)|.

D. Fasino f (x) = 0
Interpetazione grafica di xk +1 = g(xk )

6g(x) 6g(x)

-
 
 

- -
x3 x2 x1 x0 x1 x3 x2 x0

convergenza monotona convergenza alternante

D. Fasino f (x) = 0
Condizionamento del problema f (x) = 0

Problema
Data f : D ⊂ R 7→ R derivabile trovare x̄ ∈ D tale che f (x̄) = 0.

Sia f̃ una perturbazione di f : |f (x) − f̃ (x)| ⩽ ε

Sia x̃ una soluzione del problema perturbato: f̃ (x̃) = 0
Vale |f (x̃)| ⩽ ε.

f (x)
6 f (x)
6

+ε - +ε -
−ε −ε
x̄ x̄

D. Fasino f (x) = 0
Condizionamento del problema f (x) = 0

Problema
Data f : D ⊂ R 7→ R derivabile trovare x̄ ∈ D tale che f (x̄) = 0.

Sia f̃ una perturbazione di f : |f (x) − f̃ (x)| ⩽ ε

Sia x̃ una soluzione del problema perturbato: f̃ (x̃) = 0
Vale |f (x̃)| ⩽ ε.

Facendo tendere ε → 0
|x̄ − x̃| 1 ε
≈ ′ ⇝ |x̄ − x̃| ≲
|f (x̄) − f (x̃)| |f (x̄)| |f ′ (x̄)|

Numero di condizionamento di x̄: κabs = 1/|f ′ (x̄)|

D. Fasino f (x) = 0
Influenza degli errori algoritmici

Teorema di quasi-convergenza
Sia g contrattiva, |g(x) − g(y )| ⩽ c|x − y |, con g(x̄) = x̄.
Supponiamo che il calcolo di g(x) sia affetto da errori:

x̃k+1 = g(x̃k ) + εk , |εk | ⩽ η.

Allora
1 − ck
|x̃k − x̄| ⩽ c k |x̃0 − x̄| + η .
1−c

Intervallo di indeterminatezza
L’iterazione ristagna in un intorno di x̄ di raggio δ = η/(1 − c).

D. Fasino f (x) = 0
Influenza degli errori algoritmici

2
10

0
10
e r r or e assolut o

−2
10

−4
10
η = 10 − 4
−6
10
η = 10 − 6
−8
10
η=0
−10
10
0 5 10 15 20 25 30
it e r az ione

Le linee tratteggiate mostrano il livello δ = η/(1 − c).

D. Fasino f (x) = 0
Sistemi non lineari

Sistemi non lineari

Sia f : D ⊂ Rn 7→ Rn . L’equazione f (x) = 0,

 f1 (x1 , . . . , xn ) = 0

.. .. ..
 . . .
fn (x1 , . . . , xn ) = 0


è un sistema non lineare.

Ipotesi: le derivate parziali prime e seconde di f esistono e

sono continue. Metodi numerici:
Iterazioni di punto fisso
Metodo di Newton-Raphson
Metodo di Gauss-Newton.

D. Fasino f (x) = 0
Sistemi non lineari: Iterazioni di punto fisso

Definizione: funzione contrattiva

Sia D ⊂ Rn . Una funzione g : D 7→ D è contrattiva se
∃ 0 ⩽ c < 1 tale che

∥g(x) − g(y)∥ ⩽ c∥x − y ∥ ∀x, y ∈ D.

Esempio
Sia Jg (x) la matrice Jacobiana di g. Se g(D) ⊂ D e
∥Jg (x)∥ ⩽ c < 1 allora g è contrattiva.

Iterazione di punto fisso: Scelto x0 ∈ D, calcola xk+1 = g(xk ).

Se g è contrattiva allora l’iterazione è convergente e vale
∥xk+1 − x̄∥ ⩽ c∥xk − x̄∥.

D. Fasino f (x) = 0
Sistemi non lineari: Iterazioni di punto fisso

Definizione: funzione contrattiva

Sia D ⊂ Rn . Una funzione g : D 7→ D è contrattiva se
∃ 0 ⩽ c < 1 tale che

∥g(x) − g(y)∥ ⩽ c∥x − y ∥ ∀x, y ∈ D.

Teorema (convergenza globale)

Se g : D 7→ D è contrattiva, allora ∃!x̄ ∈ D : x̄ = g(x̄).
Inoltre, ∀x0 ∈ D
xk+1 = g(xk ) → x̄
∥xk +1 − x̄∥ ⩽ c∥xk − x̄∥
c ck
∥xk − x̄∥ ⩽ 1−c ∥xk − xk−1 ∥ ⩽ 1−c ∥x1 − x0 ∥.

D. Fasino f (x) = 0
Sistemi non lineari: Iterazioni di punto fisso

Definizione: funzione contrattiva

Sia D ⊂ Rn . Una funzione g : D 7→ D è contrattiva se
∃ 0 ⩽ c < 1 tale che

∥g(x) − g(y)∥ ⩽ c∥x − y ∥ ∀x, y ∈ D.

Teorema (convergenza locale)

Sia g : D ⊂ Rn 7→ Rn , g ∈ C 1 (D), tale che g(x̄) = x̄.
Se ∥Jg (x̄)∥ < 1 allora esiste un intorno I di x̄ tale che
g è contrattiva in I
∀x0 ∈ I, xk +1 = g(xk ) → x̄ .

D. Fasino f (x) = 0
Sistemi non lineari: Iterazioni di punto fisso

Definizione: funzione contrattiva

Sia D ⊂ Rn . Una funzione g : D 7→ D è contrattiva se
∃ 0 ⩽ c < 1 tale che

∥g(x) − g(y)∥ ⩽ c∥x − y ∥ ∀x, y ∈ D.

Teorema di quasi-convergenza
Sia g contrattiva, ∥g(x) − g(y )∥ ⩽ c∥x − y ∥. Supponiamo che il
calcolo di g(x) sia affetto da errori:

x̃k+1 = g(x̃k ) + εk , ∥εk ∥ ⩽ η.

Allora
1 − ck
∥x̃k − x̄∥ ⩽ c k ∥x̃0 − x̄∥ + η .
1−c

D. Fasino f (x) = 0
Sistemi non lineari: Metodo di Newton-Raphson

Sia Jf (x) la matrice jacobiana di f . Vale

f (x) = f (xk ) + Jf (xk )(x − xk ) + O(∥x − xk ∥2 ).

Metodo di Newton-Raphson

xk+1 = xk − Jf (xk )−1 f (xk ).

Scelto un punto iniziale x0 ∈ D,

risolvi il sistema lineare Jf (xk )h = −f (xk )
calcola xk+1 = xk + h.
Ipotesi: Jf (x) è invertibile in tutto un intorno di x̄.

D. Fasino f (x) = 0
Sistemi non lineari: Metodo di Newton-Raphson

Sia Jf (x) la matrice jacobiana di f . Vale

f (x) = f (xk ) + Jf (xk )(x − xk ) + O(∥x − xk ∥2 ).

Metodo di Newton-Raphson

xk+1 = xk − Jf (xk )−1 f (xk ).

Teorema
Se f ∈ C 2 in un intorno sufficientemente ampio di x̄
e ∥Jf−1 (x)∥ ⩾ m > 0 allora
il metodo è localmente convergente e inoltre

∥xk+1 − x̄∥ ⩽ c∥xk − x̄∥2 .

D. Fasino f (x) = 0
Sistemi non lineari: Metodo di Gauss-Newton

Ipotesi: f : D ⊂ Rn 7→ Rm com m ⩾ n. L’equazione f (x) = 0 è

un sistema non lineare sovraspecificato.
Problema ai minimi quadrati non lineare

min ∥f (x)∥22
x∈D

Metodo di Gauss-Newton: Scelto un punto iniziale x0 ∈ D,

risolvi il problema ai minimi quadrati

minh ∥Jf (xk )h + f (xk )∥22

calcola xk+1 = xk + h.

D. Fasino f (x) = 0
Sistemi non lineari: Metodo di Gauss-Newton

Ipotesi: f : D ⊂ Rn 7→ Rm com m ⩾ n. L’equazione f (x) = 0 è

un sistema non lineare sovraspecificato.
Problema ai minimi quadrati non lineare

min ∥f (x)∥22
x∈D

Teorema
Se f ∈ C 2 in un intorno sufficientemente ampio di x̄
e Jf (x̄) ha rango massimo allora il metodo di Gauss-Newton è
localmente convergente.

La convergenza è generalmente di tipo lineare.

D. Fasino f (x) = 0