Equazioni non lineari: esempi.

▶ Risoluzione f (x) = 0 con x ∈ [a, b] ⊆ ℝ, f ∈ C([a, b]). ▶ Esempio 1: equazioni polinomiali p_{N}(x) = 0 con p_{N} polinomio

di grado N. Possibili problemi (nessuna soluzione in ℝ, soluzioni multiple).

▶ Esempio 2: f (x) = sin (x) − x. Soluzione unica poichè f decrescente (vedi derivata).

▶ Risoluzione f (x) = 0 con x ∈ [a, b] ⊆ ℝ, f ∈ C([a, b]). ▶ Esempio 1: equazioni polinomiali p_{N}(x) = 0 con p_{N} polinomio

di grado N. Possibili problemi (nessuna soluzione in ℝ, soluzioni multiple).

▶ Esempio 2: f (x) = sin (x) − x. Soluzione unica poichè f decrescente (vedi derivata).

▶ Risoluzione f (x) = 0 con x ∈ [a, b] ⊆ ℝ, f ∈ C([a, b]). ▶ Esempio 1: equazioni polinomiali p_{N}(x) = 0 con p_{N} polinomio

di grado N. Possibili problemi (nessuna soluzione in ℝ, soluzioni multiple).

▶ Esempio 2: f (x) = sin (x) − x. Soluzione unica poichè f decrescente (vedi derivata).

Equazioni non lineari: convergenza e ordine convergenza

▶ Metodo iterativo: genera successione {x_{n}}_{n∈ℕ} che si desidera

convergere a x^{∗} tale che f (x^{∗}) = 0. ▶ Ordine di convergenza del metodo iterativo: sia {x_{k}} una

successione convergente ad x^{∗} e sia e_{k} = x_{k} − x^{∗} l’errore al passo k. Se esiste un numero p > 0 e una costante C ≠ 0 tale che

lim_{k→∞} \frac{|e_{k+1}|}{|e_{k}|^{p}} = C

allora p è chiamato ordine di convergenza della successione e C è la costante asintotica di errore. Per p = 1 la convergenza di dice lineare, per p = 2 si dice quadratica.

Equazioni non lineari: convergenza e ordine convergenza

▶ Metodo iterativo: genera successione {x_{n}}_{n∈ℕ} che si desidera

convergere a x^{∗} tale che f (x^{∗}) = 0. ▶ Ordine di convergenza del metodo iterativo: sia {x_{k}} una

successione convergente ad x^{∗} e sia e_{k} = x_{k} − x^{∗} l’errore al passo k. Se esiste un numero p > 0 e una costante C ≠ 0 tale che

lim_{k→∞} \frac{|e_{k+1}|}{|e_{k}|^{p}} = C

allora p è chiamato ordine di convergenza della successione e C è la costante asintotica di errore. Per p = 1 la convergenza di dice lineare, per p = 2 si dice quadratica.

Equazioni non lineari: esempio ordine di convergenza

Supponiamo

\frac{|e_{k+1}|}{|e_{k}|^{p}} = \frac{1}{10}, |e_{0}| = 1

o equivalentemente

|e_{k+1}| = \frac{1}{10} |e_{k}|^{p}, |e_{0}| = 1.

Il metodo ha ordine di convergenza p visto che

lim_{n→∞} \frac{|e_{k+1}|}{|e_{k}|^{p}} = \frac{1}{10},

▶ p = 1: e_{0} = 1, e_{1} = 1/10, e_{2} = 1/100, e_{3} = 1/1000, . . .. ▶ p = 2: e_{0} = 1, e_{1} = 1/10, e_{2} = 1/1000, e_{3} = 1/10^{7}, ….

Alvise Sommariva  Equazioni nonlineari

Equazioni non lineari: esempio ordine di convergenza

Supponiamo

\frac{|e_{k+1}|}{|e_{k}|^{p}} = \frac{1}{10}, |e_{0}| = 1

o equivalentemente

|e_{k+1}| = \frac{1}{10} |e_{k}|^{p}, |e_{0}| = 1.

Il metodo ha ordine di convergenza p visto che

lim_{n→∞} \frac{|e_{k+1}|}{|e_{k}|^{p}} = \frac{1}{10},

▶ p = 1: e_{0} = 1, e_{1} = 1/10, e_{2} = 1/100, e_{3} = 1/1000, . . .. ▶ p = 2: e_{0} = 1, e_{1} = 1/10, e_{2} = 1/1000, e_{3} = 1/10^{7}, ….

Alvise Sommariva  Equazioni nonlineari

Equazioni non lineari: esempio ordine di convergenza

Figura: Grafico che illustra l’errore di un metodo con convergenza p = 1 (in rosso a rombi) e p = 2 (in nero a cerchietti), per C = 1/10 ed e_{0} = 1.

Alvise Sommariva  Equazioni nonlineari

Metodo bisezione: definizione

Sia f : [a, b] → ℝ una funzione continua e supponiamo f (a) · f (b) < 0. Il metodo di bisezione genera una successione di intervalli (a_{k},b_{k}) con

▶ f (a_{k}) · f (b_{k}) < 0,

▶ [a_{k}, b_{k}] ⊂ [a_{k−1}, b_{k−1}],

▶ |b_{k} − a_{k}| = \frac{1}{2}|b_{k−1} − a_{k−1}|.

Fissate due tolleranze ϵ_{1}, ϵ_{2} si arresta l’algoritmo quando

|b_{k} − a_{k}| ≤ ϵ_{1} oppure |f ((a_{k} + b_{k})/2)| ≤ ϵ_{2}.

Metodo bisezione: esempio

Operativamente dati a ≤ b con f (a) · f (b) < 0 calcola c = (a + b)/2. Se f (a) · f (c) > 0 sostituisce c ad a, viceversa sostituisce c a b, fermandosi se le condizioni d’arresto sono verificate.

Studiamo f (x) = 0 con f (x) = sin (x) − x. Osserviamo che se x < 0 allora f (x) > 0 altrimenti f (x) ≤ 0.

1. a = −0.30000000, b = 0.40000000 → c = 0.05000000.

2. a = −0.30000000, b = 0.05000000 → c = −0.12500000 3. a = −0.12500000, b = 0.05000000 → c = −0.03750000 4. a = −0.03750000, b = 0.05000000 → c = 0.00625000

5….

Operativamente dati a ≤ b con f (a) · f (b) < 0 calcola c = (a + b)/2. Se f (a) · f (c) > 0 sostituisce c ad a, viceversa sostituisce c a b, fermandosi se le condizioni d’arresto sono verificate.

Studiamo f (x) = 0 con f (x) = sin (x) − x. Osserviamo che se x < 0 allora f (x) > 0 altrimenti f (x) ≤ 0.

1. a = −0.30000000, b = 0.40000000 → c = 0.05000000.

2. a = −0.30000000, b = 0.05000000 → c = −0.12500000 3. a = −0.12500000, b = 0.05000000 → c = −0.03750000 4. a = −0.03750000, b = 0.05000000 → c = 0.00625000

5….

Operativamente dati a ≤ b con f (a) · f (b) < 0 calcola c = (a + b)/2. Se f (a) · f (c) > 0 sostituisce c ad a, viceversa sostituisce c a b, fermandosi se le condizioni d’arresto sono verificate.

Studiamo f (x) = 0 con f (x) = sin (x) − x. Osserviamo che se x < 0 allora f (x) > 0 altrimenti f (x) ≤ 0.

1. a = −0.30000000, b = 0.40000000 → c = 0.05000000.

2. a = −0.30000000, b = 0.05000000 → c = −0.12500000 3. a = −0.12500000, b = 0.05000000 → c = −0.03750000 4. a = −0.03750000, b = 0.05000000 → c = 0.00625000

5….

Operativamente dati a ≤ b con f (a) · f (b) < 0 calcola c = (a + b)/2. Se f (a) · f (c) > 0 sostituisce c ad a, viceversa sostituisce c a b, fermandosi se le condizioni d’arresto sono verificate.

Studiamo f (x) = 0 con f (x) = sin (x) − x. Osserviamo che se x < 0 allora f (x) > 0 altrimenti f (x) ≤ 0.

1. a = −0.30000000, b = 0.40000000 → c = 0.05000000.

2. a = −0.30000000, b = 0.05000000 → c = −0.12500000 3. a = −0.12500000, b = 0.05000000 → c = −0.03750000 4. a = −0.03750000, b = 0.05000000 → c = 0.00625000

5….

Operativamente dati a ≤ b con f (a) · f (b) < 0 calcola c = (a + b)/2. Se f (a) · f (c) > 0 sostituisce c ad a, viceversa sostituisce c a b, fermandosi se le condizioni d’arresto sono verificate.

Studiamo f (x) = 0 con f (x) = sin (x) − x. Osserviamo che se x < 0 allora f (x) > 0 altrimenti f (x) ≤ 0.

1. a = −0.30000000, b = 0.40000000 → c = 0.05000000.

2. a = −0.30000000, b = 0.05000000 → c = −0.12500000 3. a = −0.12500000, b = 0.05000000 → c = −0.03750000 4. a = −0.03750000, b = 0.05000000 → c = 0.00625000

5….

Metodo bisezione: alcuni fatti

▶ Non ha una velocità di convergenza nel senso della definizione sopra definita. Esempio: se applico bisezione per risolvere sin (x) − x = 0, in [a, b] = [−3, 2] la successione |e_{n+1}/e_{n}| alterna valori 1.5 e 1/6 e quindi non converge con ordine 1.

▶ Usa solo il segno della funzione. ▶ Se f (a) · f (b) < 0 e f ∈ C([a, b]) allora converge (sempre!!) a

un x^{∗} tale che f (x^{∗}) = 0. ▶ Il test del residuo può essere non adatto a funzioni piatte o

con picchi intorno al punto cui converge. ▶ Fissata una tolleranza ϵ, e due punti iniziali a, b tali che

f (a) · f (b) < 0 (con f ∈ C([a, b])) per avere un’errore assoluto |x_{n} − x^{∗}| sulla soluzione x^{∗} inferiore ad ϵ necessitano al piú

n = ttceil(\frac{log(b − a) − log ϵ}{log 2})

iterazioni del metodo.

Alvise Sommariva  Equazioni nonlineari

▶ Non ha una velocità di convergenza nel senso della definizione sopra definita. Esempio: se applico bisezione per risolvere sin (x) − x = 0, in [a, b] = [−3, 2] la successione |e_{n+1}/e_{n}| alterna valori 1.5 e 1/6 e quindi non converge con ordine 1.

▶ Usa solo il segno della funzione. ▶ Se f (a) · f (b) < 0 e f ∈ C([a, b]) allora converge (sempre!!) a

un x^{∗} tale che f (x^{∗}) = 0. ▶ Il test del residuo può essere non adatto a funzioni piatte o

con picchi intorno al punto cui converge. ▶ Fissata una tolleranza ϵ, e due punti iniziali a, b tali che

f (a) · f (b) < 0 (con f ∈ C([a, b])) per avere un’errore assoluto |x_{n} − x^{∗}| sulla soluzione x^{∗} inferiore ad ϵ necessitano al piú

n = ttceil(\frac{log(b − a) − log ϵ}{log 2})

iterazioni del metodo.

Alvise Sommariva  Equazioni nonlineari

▶ Non ha una velocità di convergenza nel senso della definizione sopra definita. Esempio: se applico bisezione per risolvere sin (x) − x = 0, in [a, b] = [−3, 2] la successione |e_{n+1}/e_{n}| alterna valori 1.5 e 1/6 e quindi non converge con ordine 1.

▶ Usa solo il segno della funzione. ▶ Se f (a) · f (b) < 0 e f ∈ C([a, b]) allora converge (sempre!!) a

un x^{∗} tale che f (x^{∗}) = 0. ▶ Il test del residuo può essere non adatto a funzioni piatte o

con picchi intorno al punto cui converge. ▶ Fissata una tolleranza ϵ, e due punti iniziali a, b tali che

f (a) · f (b) < 0 (con f ∈ C([a, b])) per avere un’errore assoluto |x_{n} − x^{∗}| sulla soluzione x^{∗} inferiore ad ϵ necessitano al piú

n = ttceil(\frac{log(b − a) − log ϵ}{log 2})

iterazioni del metodo.

Alvise Sommariva  Equazioni nonlineari

▶ Non ha una velocità di convergenza nel senso della definizione sopra definita. Esempio: se applico bisezione per risolvere sin (x) − x = 0, in [a, b] = [−3, 2] la successione |e_{n+1}/e_{n}| alterna valori 1.5 e 1/6 e quindi non converge con ordine 1.

▶ Usa solo il segno della funzione. ▶ Se f (a) · f (b) < 0 e f ∈ C([a, b]) allora converge (sempre!!) a

un x^{∗} tale che f (x^{∗}) = 0. ▶ Il test del residuo può essere non adatto a funzioni piatte o

con picchi intorno al punto cui converge. ▶ Fissata una tolleranza ϵ, e due punti iniziali a, b tali che

f (a) · f (b) < 0 (con f ∈ C([a, b])) per avere un’errore assoluto |x_{n} − x^{∗}| sulla soluzione x^{∗} inferiore ad ϵ necessitano al piú

n = ttceil(\frac{log(b − a) − log ϵ}{log 2})

iterazioni del metodo.

Alvise Sommariva  Equazioni nonlineari

▶ Non ha una velocità di convergenza nel senso della definizione sopra definita. Esempio: se applico bisezione per risolvere sin (x) − x = 0, in [a, b] = [−3, 2] la successione |e_{n+1}/e_{n}| alterna valori 1.5 e 1/6 e quindi non converge con ordine 1.

▶ Usa solo il segno della funzione. ▶ Se f (a) · f (b) < 0 e f ∈ C([a, b]) allora converge (sempre!!) a

un x^{∗} tale che f (x^{∗}) = 0. ▶ Il test del residuo può essere non adatto a funzioni piatte o

con picchi intorno al punto cui converge. ▶ Fissata una tolleranza ϵ, e due punti iniziali a, b tali che

f (a) · f (b) < 0 (con f ∈ C([a, b])) per avere un’errore assoluto |x_{n} − x^{∗}| sulla soluzione x^{∗} inferiore ad ϵ necessitano al piú

n = ttceil(\frac{log(b − a) − log ϵ}{log 2})

iterazioni del metodo.

Alvise Sommariva  Equazioni nonlineari

Metodo Newton: interpretazione analitica

Il metodo di Newton richiede che ▶ f sia derivabile con continuità su un intervallo [a, b] di ℝ; ▶ f^{(1)}(x) ≠ 0 in [a, b].

Se x_{k} ∈ [a, b] è l’ultima approssimazione del metodo, allora dalla formula di Taylor centrata in x_{k} abbiamo per ξ_{k} ∈ I(x^{∗}, x_{k})

0 = f (x^{∗}) = f (x_{k}) + f′(x_{k})(x^{∗} − x_{k}) + f′′(ξ_{k})(x^{∗} − x_{k})^{2}/2

Tralasciando i termini di ordine superiore

0 ≈ f (x_{k}) + f′(x_{k})(x^{∗} − x_{k})

e quindi se f^{(1)}(x_{k}) ≠ 0, dopo facili conti

x^{∗} ≈ x_{k+1} := x_{k} − f (x_{k})/f^{(1)}(x_{k}).

Metodo Newton: interpretazione analitica

Il metodo di Newton richiede che ▶ f sia derivabile con continuità su un intervallo [a, b] di ℝ; ▶ f^{(1)}(x) ≠ 0 in [a, b].

Se x_{k} ∈ [a, b] è l’ultima approssimazione del metodo, allora dalla formula di Taylor centrata in x_{k} abbiamo per ξ_{k} ∈ I(x^{∗}, x_{k})

0 = f (x^{∗}) = f (x_{k}) + f′(x_{k})(x^{∗} − x_{k}) + f′′(ξ_{k})(x^{∗} − x_{k})^{2}/2

Tralasciando i termini di ordine superiore

0 ≈ f (x_{k}) + f′(x_{k})(x^{∗} − x_{k})

e quindi se f^{(1)}(x_{k}) ≠ 0, dopo facili conti

x^{∗} ≈ x_{k+1} := x_{k} − f (x_{k})/f^{(1)}(x_{k}).

Metodo Newton: interpretazione geometrica

Se ben definito, il metodo di Newton genera una successione {x_{k}} definita da

x_{k+1} := x_{k} − f (x_{k})/f^{(1)}(x_{k}).

Sia r la retta tangente al grafico della funzione f nel punto (x_{k},f (x_{k})). Allora x_{k+1} è l’intersezione della retta r con l’asse delle ascisse, cioè la retta di equazione y = 0.

Metodo Newton: interpretazione geometrica

Figura: Grafico che illustra geometricamente le iterazioni del metodo Newton per il calcolo dello zero di f (x) = x^{2} − 2.

Alvise Sommariva  Equazioni nonlineari

Metodo Newton: convergenza

Nel caso del metodo di Newton la convergenza non è in generale garantita. Esistono degli esempi in cui il metodo produce una successione non convergente. Ciò nonostante esistono molti teoremi che illustrano quando si è certi che il metodo converga.

▶ Alcuni sono detti di convergenza locale e dicono che se x_{0} è in un intorno I sufficientemente piccolo della soluzione x^{∗} allora il metodo converge ad x_{∗}. Usualmente non sono costruttivi e non permettono di definire chiaramente I .

▶ Altri sono detti di convergenza globale e dicono che se x_{0} appartiene a un ben definito intorno I di x^{∗} allora il metodo converge.

Metodo Newton: convergenza

Nel caso del metodo di Newton la convergenza non è in generale garantita. Esistono degli esempi in cui il metodo produce una successione non convergente. Ciò nonostante esistono molti teoremi che illustrano quando si è certi che il metodo converga.

▶ Alcuni sono detti di convergenza locale e dicono che se x_{0} è in un intorno I sufficientemente piccolo della soluzione x^{∗} allora il metodo converge ad x_{∗}. Usualmente non sono costruttivi e non permettono di definire chiaramente I .

▶ Altri sono detti di convergenza globale e dicono che se x_{0} appartiene a un ben definito intorno I di x^{∗} allora il metodo converge.

Metodo Newton: un teorema di convergenza locale

Uno zero x^{∗} si dice semplice se f (x^{∗}) = 0 e f^{(1)}(x^{∗}) ≠ 0.

Teorema. Sia x^{∗} ∈ (a, b) uno zero semplice di f : [a, b] → ℝ. Si supponga inoltre f ∈ C^{2}([a, b]). Allora per x_{0} ∈ [a, b] sufficientemente vicino a x^{∗} le iterazioni del metodo di Newton

x_{k+1} = x_{k} − f (x_{k})/f^{(1)}(x_{k}), k = 0, 1, 2, …

sono ben definite e convergono quadraticamente a x^{∗}.

Metodo Newton: un teorema di convergenza locale (dim.)

Traccia della dimostrazione.

Sia I_{1} intorno di x^{∗} in cui f^{(1)} ha segno costante (permanenza del segno).

1. Dalla formula di Taylor centrata in x_{∗} e valutata in x_{k} abbiamo per ξ_{k} ∈ I(x^{∗}, ξ_{k}), ricordando la succ. del metodo di Newton

0 = f (x^{∗}) = f (x_{k}) + f^{(1)}(x_{k})(x^{∗} − x_{k}) + f^{(2)}(ξ_{k})(x^{∗} − x_{k})^{2}/2
= f^{(1)}(x_{k})(x^{∗} − x_{k+1}) + f^{(2)}(ξ_{k})(x^{∗} − x_{k})^{2}/2  (1)

Posto e_{k} = |x^{∗} − x_{k}| ricaviamo per M = max_{x,y∈I_{1}} |f^{(2)}(ξ_{k})|/2 · |f^{(1)}(x_{k})|

e_{k+1} = \frac{|f^{(2)}(ξ_{k})|}{2 · |f^{(1)}(x_{k})|}e_{k}^{2} ≤ Me_{k}^{2}

Metodo Newton: un teorema di convergenza locale (dim.)

Sia I_{2} = [x^{∗} − δ, x^{∗} + δ] ⊆ I_{1} con Mδ < 1. Se x_{0} ∈ I_{2} allora e_{0} ≤ δ e

e_{1} ≤ Me_{0}^{2} ≤ Mδ^{2} ≤ δ

da cui per induzione ogni x_{k} ∈ I_{2}. Inoltre

Me_{k} ≤ M^{2}e_{k−1}^{2} = (Me_{k−1})^{2} ≤ … ≤ (Me_{0})^{2^{k}}

e visto che Me_{0} ≤ Mδ < 1 abbiamo e_{k} → 0, cioè il metodo di Newton converge quadraticamente.

Metodo Newton: un teorema di convergenza

Teorema. Sia f ∈ C^{2}([a, b]), con [a, b] intervallo chiuso e limitato. Se

1. f (a) · f (b) < 0;

2. f^{(1)}(x) > 0, per ogni x ∈ [a, b];

3. f^{(2)}(x) > 0 allora le iterate x_{k} fornite dal metodo di Newton sono strettamente decrescenti e convergono all’unica soluzione x^{∗} in [a, b], per x_{0} = b.

Metodo Newton: un teorema di convergenza globale

Teorema. Sia f ∈ C^{2}([a, b]), con [a, b] intervallo chiuso e limitato. Se

1. f (a) · f (b) < 0;

2. f^{(1)}(x) ≠ 0, per ogni x ∈ [a, b];

3. f^{(2)}(x) ≥ 0 o f^{(2)}(x) ≤ 0, per ogni x ∈ [a, b];

4. |f (a)/f^{(1)}(a)| < b − a e |f (b)/f^{(1)}(b)| < b − a, allora il metodo di Newton converge all’unica soluzione x^{∗} in [a, b], per ogni x_{0} ∈ [a, b].

Metodo Newton: un teorema di convergenza globale (dim.)

Traccia della dimostrazione. Supponiamo che

1. f^{(2)}(x) ≥ 0 se x ∈ (a, b).

2. f^{(1)}(x) > 0 se x ∈ (a, b).

Allora:

1. L’ultimo punto garantisce che x_{1} ∈ (a, b).

2. La formula di Taylor valutata in x^{∗}, centrata in x_{k} ∈ [a, b] e troncata al second’ordine, mostra che 0 = f (x^{∗}) ≥ f^{(1)}(x_{k})(x^{∗} − x_{k+1}) e quindi x^{∗} ≤ x_{k+1}.

3. La formula di Newton x_{k+1} = x_{k} − f (x_{k})/f^{(1)}(x_{k}) mostra che se x_{k} > x^{∗} allora x_{k+1} < x_{k}, mentre se x_{k} < x^{∗} allora x_{k+1} > x_{k}.

Traccia della dimostrazione. Supponiamo che

1. f^{(2)}(x) ≥ 0 se x ∈ (a, b).

2. f^{(1)}(x) > 0 se x ∈ (a, b).

Allora:

1. L’ultimo punto garantisce che x_{1} ∈ (a, b).

2. La formula di Taylor valutata in x^{∗}, centrata in x_{k} ∈ [a, b] e troncata al second’ordine, mostra che 0 = f (x^{∗}) ≥ f^{(1)}(x_{k})(x^{∗} − x_{k+1}) e quindi x^{∗} ≤ x_{k+1}.

3. La formula di Newton x_{k+1} = x_{k} − f (x_{k})/f^{(1)}(x_{k}) mostra che se x_{k} > x^{∗} allora x_{k+1} < x_{k}, mentre se x_{k} < x^{∗} allora x_{k+1} > x_{k}.

Traccia della dimostrazione. Supponiamo che

1. f^{(2)}(x) ≥ 0 se x ∈ (a, b).

2. f^{(1)}(x) > 0 se x ∈ (a, b).

Allora:

1. L’ultimo punto garantisce che x_{1} ∈ (a, b).

2. La formula di Taylor valutata in x^{∗}, centrata in x_{k} ∈ [a, b] e troncata al second’ordine, mostra che 0 = f (x^{∗}) ≥ f^{(1)}(x_{k})(x^{∗} − x_{k+1}) e quindi x^{∗} ≤ x_{k+1}.

3. La formula di Newton x_{k+1} = x_{k} − f (x_{k})/f^{(1)}(x_{k}) mostra che se x_{k} > x^{∗} allora x_{k+1} < x_{k}, mentre se x_{k} < x^{∗} allora x_{k+1} > x_{k}.

Quindi, dal primo e secondo punto, comunque sia scelto x_{0} ∈ [a, b] abbiamo che a < x^{∗} ≤ x_{1} ≤ b. Dal secondo e terzo punto, per ogni k, a < x^{∗} ≤ x_{k+1} < x_{k} ≤ b. Quindi la successione {x_{k}} è decrescente e limitata, per cui ha limite L. Dalla formula del metodo di Newton, per continuità

L = lim_{k}x_{k+1} = lim_{k}(x_{k} − f (x_{k})/f^{(1)}(x_{k}))
= lim_{k}x_{k} − lim_{k}f (x_{k})/f^{(1)}(x_{k}))
= L − lim_{k}f (x_{k})/ lim_{k}f^{(1)}(x_{k}))  (2)

da cui lim_{k} f (x_{k}) = 0 cioè x_{k} → x^{∗}.

Metodo Newton: alcuni fatti

1. Il metodo di Newton non è sempre convergente.

2. Se converge, non è detto che l’ordine di convergenza sia p = 2 (conv. quadratica).

3. Se uno zero x^{∗} di f è multiplo cioè f (x) = (x − x^{∗})^{k}g(x) con k > 1 e g ∈ C([a, b]) con g(x^{∗}) ≠ 0 ([a, b] intorno x^{∗})

1. Il metodo di Newton non è sempre convergente.

2. Se converge, non è detto che l’ordine di convergenza sia p = 2 (conv. quadratica).

3. Se uno zero x^{∗} di f è multiplo cioè f (x) = (x − x^{∗})^{k}g(x) con k > 1 e g ∈ C([a, b]) con g(x^{∗}) ≠ 0 ([a, b] intorno x^{∗})

1. Il metodo di Newton non è sempre convergente.

2. Se converge, non è detto che l’ordine di convergenza sia p = 2 (conv. quadratica).

3. Se uno zero x^{∗} di f è multiplo cioè f (x) = (x − x^{∗})^{k}g(x) con k > 1 e g ∈ C([a, b]) con g(x^{∗}) ≠ 0 ([a, b] intorno x^{∗})

Metodi di punto fisso

Consideriamo i problemi di punto fisso

ϕ(x) = x

in cui supponiamo che ϕ : Ω → Ω sia una funzione continua in Ω sia un intervallo compatto di ℝ. Notiamo subito che ogni problema di tipo f (x) = 0 si può ovviamente riscrivere in questa forma, posto ϕ(x) = f (x) + x. Nel metodo di punto fisso, si definisce la successione

x_{k+1} = ϕ(x_{k})

Teorema di punto fisso

Teorema. Si supponga che ϕ : Ω → Ω e ϕ′ siano funzione continue in Ω = [a, b]. Inoltre sia λ = max_{x∈[a,b]} |ϕ′(x)| < 1. Allora:

1. Esiste uno ed un solo \underline{α} tale che ϕ(\underline{x}) = \underline{x} in Ω;

2. Per ogni punto iniziale \underline{x_{0}} ∈ [a, b] le iterate \underline{x_{n+1}} = ϕ(\underline{x_{n}}) convergono ad \underline{α};

3. Si ha

|\underline{α} − \underline{x_{n}}| ≤ \frac{λ^{n}}{1 − λ}|\underline{x_{0}} − \underline{x_{1}}|, n ≥ 0;

4. Infine

lim_{n→∞} \frac{\underline{α} − \underline{x_{n+1}}}{\underline{α} − \underline{x_{n}}} = ϕ′(\underline{α})

Teorema. Si supponga che ϕ : Ω → Ω e ϕ′ siano funzione continue in Ω = [a, b]. Inoltre sia λ = max_{x∈[a,b]} |ϕ′(x)| < 1. Allora:

1. Esiste uno ed un solo \underline{α} tale che ϕ(\underline{x}) = \underline{x} in Ω;

2. Per ogni punto iniziale \underline{x_{0}} ∈ [a, b] le iterate \underline{x_{n+1}} = ϕ(\underline{x_{n}}) convergono ad \underline{α};

3. Si ha

|\underline{α} − \underline{x_{n}}| ≤ \frac{λ^{n}}{1 − λ}|\underline{x_{0}} − \underline{x_{1}}|, n ≥ 0;

4. Infine

lim_{n→∞} \frac{\underline{α} − \underline{x_{n+1}}}{\underline{α} − \underline{x_{n}}} = ϕ′(\underline{α})

Teorema. Si supponga che ϕ : Ω → Ω e ϕ′ siano funzione continue in Ω = [a, b]. Inoltre sia λ = max_{x∈[a,b]} |ϕ′(x)| < 1. Allora:

1. Esiste uno ed un solo \underline{α} tale che ϕ(\underline{x}) = \underline{x} in Ω;

2. Per ogni punto iniziale \underline{x_{0}} ∈ [a, b] le iterate \underline{x_{n+1}} = ϕ(\underline{x_{n}}) convergono ad \underline{α};

3. Si ha

|\underline{α} − \underline{x_{n}}| ≤ \frac{λ^{n}}{1 − λ}|\underline{x_{0}} − \underline{x_{1}}|, n ≥ 0;

4. Infine

lim_{n→∞} \frac{\underline{α} − \underline{x_{n+1}}}{\underline{α} − \underline{x_{n}}} = ϕ′(\underline{α})

Teorema. Si supponga che ϕ : Ω → Ω e ϕ′ siano funzione continue in Ω = [a, b]. Inoltre sia λ = max_{x∈[a,b]} |ϕ′(x)| < 1. Allora:

1. Esiste uno ed un solo \underline{α} tale che ϕ(\underline{x}) = \underline{x} in Ω;

2. Per ogni punto iniziale \underline{x_{0}} ∈ [a, b] le iterate \underline{x_{n+1}} = ϕ(\underline{x_{n}}) convergono ad \underline{α};

3. Si ha

|\underline{α} − \underline{x_{n}}| ≤ \frac{λ^{n}}{1 − λ}|\underline{x_{0}} − \underline{x_{1}}|, n ≥ 0;

4. Infine

lim_{n→∞} \frac{\underline{α} − \underline{x_{n+1}}}{\underline{α} − \underline{x_{n}}} = ϕ′(\underline{α})

Metodi di punto fisso e Newton

Il metodo di Newton è un particolare metodo di punto fisso. Infatti x_{k+1} = ϕ(x_{k}) con ϕ(x) = x − f (x)/f′(x). Supponiamo ϕ suff. regolare. Ora:

ϕ(x_{n}) = ϕ(α) + ϕ′(α)(x_{n} − α) + ϕ′′(c_{n})(x_{n} − α)^{2}/2, c_{n} ∈ I(α, x_{n})

e quindi da ϕ(α) = α e x_{n+1} = ϕ(x_{n}), se ϕ′(α) = 0 abbiamo

x_{n+1} = α + ϕ′′(c_{n})(x_{n} − α)^{2}/2

cioè

|e_{n+1}| = |ϕ′′c_{n}||e_{n}|^{2}/2

da cui

lim_{n→∞}|e_{n+1}|/|e_{n}|^{2} = |ϕ′′(α)|/2

cioè la convergenza è quadratica.

Metodi di punto fisso e Newton

Quindi se f ∈ C^{2}(Ω), f′(x) ≠ 0, f (x) + x : Ω → Ω otteniamo

ϕ′(x) = \frac{f (x)f′′(x)}{[f′(x)]^{2}}

e se f′(α) ≠ 0 (radice semplice) abbiamo ϕ′(α) = 0 da cui deduciamo nuovamente che la convergenza è quadratica.

Alvise Sommariva  Equazioni nonlineari

Cenni alla risoluzione numerica di sistemi nonlineari

Problema. Data una funzione F : Ω ⊆ ℝ^{n} → ℝ^{n} si tratta di trovare gli x^{∗} ∈ Ω tali che F (x^{∗}) = 0.

Esempio:

\{ \begin{matrix}x − \frac{1}{2} cos (y) = 0 \\ y − \frac{1}{2} sin (x) = 0 \end{matrix}  (3)

Soluzione (unica!): x = 0.48640515466592 e y = 0.23372550195872.

Generalizzazione punto fisso e Teorema di Banach

Teorema. Sia (X , d) uno spazio metrico completo ed M un sottospazio non vuoto e chiuso di X . Se ϕ : M → M è L contrattiva allora

1. l’equazione x = ϕ(x) ha una ed una sola soluzione α;

2. la successione x_{k+1} = ϕ(x_{k}) (detta di Banach o di punto fisso) converge alla soluzione α per ogni scelta del punto iniziale x_{0};

3. per k = 0, 1, 2, … si ha

d(x_{k}, α) ≤ L^{k}(1 − L)^{−1}d(x_{0}, x_{1}), a priori
d(x_{k+1}, α) ≤ L(1 − L)^{−1}d(x_{k+1}, x_{k}), a posteriori

4. per k = 0, 1, 2, … si ha

d(x_{k+1}, α) ≤ Ld(x_{k}, α)

Esempio punto fisso per sistemi

\{ \begin{matrix}x − \frac{1}{2} cos (y) = 0 \\ y − \frac{1}{2} sin (x) = 0 \end{matrix}  (4)

si scrive come \underline{x} = ϕ(\underline{x}) con \underline{x} = (x, y) e

ϕ(x) = (\frac{1}{2} cos (y), \frac{1}{2} sin (x)) .

Si dimostra che ϕ è contrazione con L = 1/2.

Esempio punto fisso per sistemi

\{ \begin{matrix}x − \frac{1}{2} cos (y) = 0 \\ y − \frac{1}{2} sin (x) = 0 \end{matrix}  (5)

si scrive come \underline{x} = ϕ(\underline{x}) con \underline{x} = (x, y) e

ϕ(x) = (\frac{1}{2} cos (y), \frac{1}{2} sin (x)) .

Si dimostra che ϕ è contrazione con L = 1/2.

Esempio punto fisso per sistemi

Successione punto fisso: x_{k+1} = \frac{1}{2} cos (y_{k}), y_{k+1} = \frac{1}{2} sin (x_{k})

0.00000000000000 0.00000000000000
0.50000000000000 0.00000000000000
0.50000000000000 0.23971276930210
0.48570310513698 0.23971276930210
0.48570310513698 0.23341513183103
0.48644107261515 0.23341513183103
. . . . . .
0.48640515466592 0.23372550195872
0.48640515466592 0.23372550195872

(6)

Alvise Sommariva  Equazioni nonlineari

Metodo Newton per sistemi

Supponiamo di dover risolvere f (x) = 0 con f : Ω ⊆ ℝ^{d} → ℝ^{d}. La successione di Newton viene descritta come

\{ \begin{matrix}f′(v_{k})) · h_{k+1} = −f (v_{k}), \\ v_{k+1} := v_{k} + h_{k+1} \end{matrix}  (7)

dove f′ è la matrice Jacobiana di f cioè se v = (v_{1}, …, v_{d}) allora (f′(v_{k})))_{i,j} = \frac{∂f_{i}(v)}{∂v_{j}}.

Alvise Sommariva  Equazioni nonlineari

Esempio Newton per sistemi

Consideriamo il precedente esempio, come f (x) = 0. Allora posto v = (x, y) si ha f (x, y) = (f_{1}(x, y), f_{2}(x, y)) con

f_{1}(x, y) = x − \frac{1}{2} cos (y)
f_{2}(x, y) = y − \frac{1}{2} sin (x) = 0
.  (8)

Inoltre

f′(x, y) = ( \begin{matrix}1 & \frac{1}{2} sin (y) \\ −\frac{1}{2} cos (y) & 1 \end{matrix} )  (9)
Alvise Sommariva  Equazioni nonlineari

Esempio Newton per sistemi

Successione Newton:

\{ \begin{matrix}f′(v_{k})) · h_{k+1} = −f (v_{k}), \\ v_{k+1} := v_{k} + h_{k+1} \end{matrix}  (10)
0.000000000000000 0.000000000000000
0.500000000000000 0.250000000000000
0.486463513355199 0.233773076987732
0.486405155145713 0.233725502568820
0.486405154665921 0.233725501958721

(11)

Alvise Sommariva  Equazioni nonlineari

Riferimenti bibliografici

▶ A. Quarteroni, F. Saleri, Introduzione al Calcolo Scientifico,

Springer, (2002).

Alvise Sommariva  Equazioni nonlineari