Radici di equazioni

(1)

Radici di equazioni

L’equazione:

f (x) = 0

ha un numero di soluzioni non note a priori

1. isolo la radice

2. calcolo con precisione il valore

Non c’ ` e un metodo universale per 1). Possibili strategie

• parto da un intervallo e lo allargo fino a includere una radice

• divido l’intervallo in cui cerco la radice in intervallini [x

_j−1

, x

_j

] finch´ e

f (x

_j−1

) · f (x

_j

) < 0

Isolata la radice la si pu` o calcolare con il metodo di bisezione

Alternativa: parto da uno o due punti e cerco una suc-

cessione che converga alla radice.

(2)

Bisezione

Se in [x _low , x _hig ] esiste una radice e la voglio calcolare con precisione ε suppongo che:

f (x _low ) < 0 e f (x _hig ) > 0

Prendo allora il punto medio

x _med = 1

2 · (x _low + x _hig )

(3)

e calcolo f (x _med ).

• Se |x

_hig

− x

_low

| < ε termino il ciclo;

• se f (x

_med

) e f (x

_low

) hanno lo stesso segno ; 1. [x

_med

, x

_hig

] come nuovo intervallo;

2.

¹₂

· (x

_med

+ x

_hig

) ` e il nuovo punto medio;

• Se f (x

_med

) e f (x

_hig

) hanno lo stesso segno;

1. [x

_low

, x

_med

] come nuovo intervallo;

2.

¹₂

· (x

_low

+ x

_med

) ` e il nuovo punto medio;

• ripeto il ciclo;

La precisione dopo N passi ` e

₂¹N

volte l’intervallo inizia-

le.

(4)

Metodo di Newton

E applicabile quando si conosce la derivata della ` funzione.

Espando la funzione vicino allo zero

f (x) = f (x ₁ ) + f ⁰ (x ₁ ) · (x − x ₁ )

supponendo quindi che i termini non lineari si possano trascurare. Se la relazione fosse esatta, e non approssimata al primo ordine, avrei per lo zero α:

0 = f (x ₁ ) + f ⁰ (x ₁ ) · (α − x ₁ )

(5)

e quindi

α = x ₁ − f (x ₁ ) f ⁰ (x ₁ )

In generale per` o la successione definita da x _{N +1} = x _N − f (x _N )

f ⁰ (x _N )

pu` o convergere verso un limite finito, e in questo caso il limite ` e una radice dell’equazione.

Inconvenienti

• la convergenza non ` e garantita;

• ` e necessario conoscere la derivata.

(6)

Precisione

Chiamo α la radice, quindi f (α) = 0. Esister` a allora uno ξ _N , con α < ξ _N < x _N tale che:

f (α)−f (x _N ) = (α−x _N )·f ⁰ (x _N )+ 1

2 ·f ⁰⁰ (ξ _N )·(α−x _N ) ² da cui, essendo f (α) = 0:

− f (x _N )

f ⁰ (x _N ) = (α − x _N ) + 1

2 · f ⁰⁰ (ξ _N )

f ⁰ (x _N ) · (α − x _N ) ²

α − x _N = − f (x _N )

f ⁰ (x _N ) − 1

2 · f ⁰⁰ (ξ _N )

f ⁰ (x _N ) · (α − x _N ) ² Ricordando che

(x _{N +1} − x _N ) = − f (x _N ) f ⁰ (x _N ) trovo

α − x _N = (x _{N +1} − x _N ) − 1

2 · f ⁰⁰ (ξ _N )

f ⁰ (x _N ) · (α − x _N ) ²

α−x _{N +1} = − 1

2 · f ⁰⁰ (ξ _N )

f ⁰ (ξ _N ) ·(α−x _N ) ² = C _N ·(α−x _N ) ²

(7)

Per N → ∞ C _N → C purch´ e la derivata non si annulli.

l’andamento dell’errore ` e quindi

|α − x _{N +1} | ≈ C · |α − x _N | ²

(8)

Metodo della secante

• E utile quando non si pu` ` o calcolare la derivata;

• richiede la conoscenza della funzione in due punti per partire.

Attraverso due punti di una curva passa una

secante: la posso prolungare fino al punto dove

(9)

interseca le ascisse. (x ₀ , f ₀ ) e (x ₁ , f ₁ ) siano i due punti iniziali

f ₂ − f ₁

x ₂ − x ₁ = f ₁ − f ₀ x ₁ − x ₀

Imponendo f ₂ = 0 si trova il nuovo punto x ₂ x ₂ = x ₁ − f ₁

f ₁ − f ₀ · (x ₁ − x ₀ )

Analogamente i punti successivi sono dati dalla relazione di ricorrenza:

x _{N +1} = x _N − f _N

f _N − f _{N −1} · (x _N − x _{N −1} ) L’errore ` e dato da

|α − x _{N +1} | ≈ C · |α − x _N | · |α − x _{N −1} |

(10)

Metodi di punto fisso

Un punto x ₀ per cui valga g(x ₀ ) = x ₀

si dice punto fisso di g(x). Posto f (x) = g(x) + x si ha

g(x ₀ ) = f (x ₀ ) + x ₀ = x ₀ ⇒ f (x ₀ ) = 0

Esiste quindi una stretta relazione tra punti fissi e zeri. Un modo per trovare gli zeri di una funzione f (x) ` e trovare i punti fissi di g(x) = f (x) + x.

Il metodo pi` u semplice consiste nel definire la successione

x _{N +1} = g(x _N )

il cui limite ` e un punto fisso (se esiste finito).

questa successione non ` e per` o l’unica scelta possibile: ad esempio, l’equazione

x ² − 3x + 2 = 0

(11)

` e equivalente a

x ² − 2x + 2 = x ma anche a

3 − 2

x = x

che hanno gli stessi punti fissi, ma possono avere diverse propriet` a di convergenza

x _N converge in un intervallo [a, b] se per ogni x ∈ [a, b] g(x) ` e derivabile ed esiste q tale che

|g ⁰ (x)| ≤ q < 1

(12)

Esercizio

Il metodo di punto fisso si presta a calcolare radici quadrate, dato che x = √

a ` e lo stesso (o quasi) che x ² − a = 0 Scrivere un programma per far questo col metodo di Newton (la for- mula che si trova ` e nota come processo di Erone)

Radici di equazioni

Radici di equazioni

L’equazione:

f (x) = 0

ha un numero di soluzioni non note a priori

1. isolo la radice

2. calcolo con precisione il valore

Non c’ ` e un metodo universale per 1). Possibili strategie

• parto da un intervallo e lo allargo fino a includere una radice

• divido l’intervallo in cui cerco la radice in intervallini [x

, x

] finch´ e

f (x

) · f (x

) < 0

Isolata la radice la si pu` o calcolare con il metodo di bisezione

Alternativa: parto da uno o due punti e cerco una suc-

cessione che converga alla radice.

Bisezione

Se in [x low , x hig ] esiste una radice e la voglio calcolare con precisione ε suppongo che:

f (x low ) < 0 e f (x hig ) > 0

Prendo allora il punto medio

x med = 1

2 · (x low + x hig )

e calcolo f (x med ).

• Se |x

− x

| < ε termino il ciclo;

• se f (x

) e f (x

) hanno lo stesso segno ; 1. [x

, x

] come nuovo intervallo;

2.

· (x

+ x

) ` e il nuovo punto medio;

• Se f (x

) e f (x

) hanno lo stesso segno;

1. [x

, x

] come nuovo intervallo;

2.

· (x

+ x

) ` e il nuovo punto medio;

• ripeto il ciclo;

La precisione dopo N passi ` e

volte l’intervallo inizia-

le.

Metodo di Newton

E applicabile quando si conosce la derivata della ` funzione.

Espando la funzione vicino allo zero

f (x) = f (x 1 ) + f 0 (x 1 ) · (x − x 1 )

supponendo quindi che i termini non lineari si possano trascurare. Se la relazione fosse esatta, e non approssimata al primo ordine, avrei per lo zero α:

0 = f (x 1 ) + f 0 (x 1 ) · (α − x 1 )

e quindi

α = x 1 − f (x 1 ) f 0 (x 1 )

In generale per` o la successione definita da x N +1 = x N − f (x N )

f 0 (x N )

pu` o convergere verso un limite finito, e in questo caso il limite ` e una radice dell’equazione.

Inconvenienti

• la convergenza non ` e garantita;

• ` e necessario conoscere la derivata.

Precisione

Chiamo α la radice, quindi f (α) = 0. Esister` a allora uno ξ N , con α < ξ N < x N tale che:

f (α)−f (x N ) = (α−x N )·f 0 (x N )+ 1

2 ·f 00 (ξ N )·(α−x N ) 2 da cui, essendo f (α) = 0:

− f (x N )

f 0 (x N ) = (α − x N ) + 1

2 · f 00 (ξ N )

f 0 (x N ) · (α − x N ) 2

α − x N = − f (x N )

f 0 (x N ) − 1

2 · f 00 (ξ N )

f 0 (x N ) · (α − x N ) 2 Ricordando che

(x N +1 − x N ) = − f (x N ) f 0 (x N ) trovo

α − x N = (x N +1 − x N ) − 1

2 · f 00 (ξ N )

Se in [x _low , x _hig ] esiste una radice e la voglio calcolare con precisione ε suppongo che:

f (x _low ) < 0 e f (x _hig ) > 0

x _med = 1

2 · (x _low + x _hig )

e calcolo f (x _med ).

f (x) = f (x ₁ ) + f ⁰ (x ₁ ) · (x − x ₁ )

0 = f (x ₁ ) + f ⁰ (x ₁ ) · (α − x ₁ )

α = x ₁ − f (x ₁ ) f ⁰ (x ₁ )

In generale per` o la successione definita da x _{N +1} = x _N − f (x _N )

f ⁰ (x _N )

Chiamo α la radice, quindi f (α) = 0. Esister` a allora uno ξ _N , con α < ξ _N < x _N tale che:

f (α)−f (x _N ) = (α−x _N )·f ⁰ (x _N )+ 1

2 ·f ⁰⁰ (ξ _N )·(α−x _N ) ² da cui, essendo f (α) = 0:

− f (x _N )

f ⁰ (x _N ) = (α − x _N ) + 1

2 · f ⁰⁰ (ξ _N )

f ⁰ (x _N ) · (α − x _N ) ²

α − x _N = − f (x _N )

f ⁰ (x _N ) − 1

2 · f ⁰⁰ (ξ _N )

f ⁰ (x _N ) · (α − x _N ) ² Ricordando che

(x _{N +1} − x _N ) = − f (x _N ) f ⁰ (x _N ) trovo

α − x _N = (x _{N +1} − x _N ) − 1

2 · f ⁰⁰ (ξ _N )

f ⁰ (x _N ) · (α − x _N ) ²

α−x _{N +1} = − 1

2 · f ⁰⁰ (ξ _N )

f ⁰ (ξ _N ) ·(α−x _N ) ² = C _N ·(α−x _N ) ²

Per N → ∞ C _N → C purch´ e la derivata non si annulli.

|α − x _{N +1} | ≈ C · |α − x _N | ²

interseca le ascisse. (x ₀ , f ₀ ) e (x ₁ , f ₁ ) siano i due punti iniziali

f ₂ − f ₁

x ₂ − x ₁ = f ₁ − f ₀ x ₁ − x ₀

Imponendo f ₂ = 0 si trova il nuovo punto x ₂ x ₂ = x ₁ − f ₁

f ₁ − f ₀ · (x ₁ − x ₀ )

x _{N +1} = x _N − f _N

f _N − f _{N −1} · (x _N − x _{N −1} ) L’errore ` e dato da

|α − x _{N +1} | ≈ C · |α − x _N | · |α − x _{N −1} |

Un punto x ₀ per cui valga g(x ₀ ) = x ₀

g(x ₀ ) = f (x ₀ ) + x ₀ = x ₀ ⇒ f (x ₀ ) = 0

x _{N +1} = g(x _N )

x ² − 3x + 2 = 0

x ² − 2x + 2 = x ma anche a

x _N converge in un intervallo [a, b] se per ogni x ∈ [a, b] g(x) ` e derivabile ed esiste q tale che

|g ⁰ (x)| ≤ q < 1

a ` e lo stesso (o quasi) che x ² − a = 0 Scrivere un programma per far questo col metodo di Newton (la for- mula che si trova ` e nota come processo di Erone)

radici reali x ^{(N )} ₁ , . . . , x ^{(N )} _N Si pu` o dimostrare che

queste godono della propriet` a che tra x ^{(N −1)} _i e

x ^{(N −1)} _i+1 c’` e una ed una sola radice x ^{(N )} _k . Trovare