4.ripetoilpuntoprecedentefinch´e j nonraggiungezero p per x eaggiungo a 2.per j chevada N − 1a0scendendounnumeroallavolta3.moltiplico p ( x )ilvalore a N moltiplicazionie N somme.Inpraticadevofareunciclo1.assegnoa ( ( ( )))cherichiedesolo p ( x )= a + x ·

Polinomi

I polinomi della forma

p(x) = a ₀ + a ₁ · x + a 2 · x ² + · · · + a N · x ^N

richiedono N potenze, N somme e N moltiplicazioni per essere valutati Un metodo pi` u efficiente (Horner) ` e

p(x) = a 0 + x · (a 1 + x · (a 2 + · · · + x · (a N −1 + a _N · x))) che richiede solo N moltiplicazioni e N somme.

In pratica devo fare un ciclo 1. assegno a p(x) il valore a _N

2. per j che va da N − 1 a 0 scendendo un numero alla volta

3. moltiplico p per x e aggiungo a _j

4. ripeto il punto precedente finch´ e j non raggiunge

zero

Esempio: N = 3

• P = a 3

• P = P · x + a 2 = a ₃ · x + a 2

• P = P · x + a 1 = a ₃ · x ² + a ₂ · x + a 1

• P = P · x + a 0 = a ₃ · x ³ + a ₂ · x ² + a ₁ · x + a 0

Derivate

p ^′ (x) = a ₁ + 2 · a 2 · x + 3 · a 3 · x ² + · · · + N · a N · x ^{N −1} Si possono calcolare in modo analogo ai polinomi e assieme ad essi con il seguente trucco

1. assegno a p(x) il valore a n

2. assegno a p ^′ (x) il valore 0

3. per j che va da N − 1 a 0 scendendo un numero alla volta

4. moltiplico p ^′ (x) per x e aggiungo p(x) 5. moltiplico p(x) per x e aggiungo a _j

6. ripeto i due punti precedenti finch´ e j non raggiunge

zero

Esempio: polinomio di terzo grado

• D = 0

• P = a 3

• D = D · x + P = a 3

• P = P · x + a 2 = a 3 · x + a 2

• D = D · x + P = 2 · a 3 · x + a 2

• P = P · x + a 1 = a ₃ · x ² + a ₂ · x + a 1

• D = D · x + P = 3 · a 3 · x ² + 2 · a 2 · x + a 1

• P = P · x + a 0 = a ₃ · x ³ + a ₂ · x ² + a ₁ · x + a 0

Divisione di un polinomio

Se x ₀ ` e uno zero di un polinomio dei grado n, p <sub>n</sub> (x), questo si pu` o scrivere come

p n (x) = (x − x 0 ) · p _n−1 (x)

Voglio trovare i coefficienti di p n −1 (x) a partire da quelli di p n (x). Per fare questo esplicito il prodotto

(x−x ₀ )·(a ^′ ₀ +a ^′ ₁ x+a ^′ ₂ x ² +a ^′ ₃ x ³ +. . . )+R = a ₀ +a ₁ x+a ₂ x ² +a ₃ x ³ +a ₄ x ⁴ +. . .

che da’

a 0 = R−a ^′ ₀ x 0 a 1 = a ^′ ₀ −a ^′ ₁ x 0 a 2 = a ^′ ₁ −a ^′ ₂ x 0 . . . a n = a ^′ _n−1 da cui si trova per a ^′ _j :

a ^′ _n−1 = a _n a ^′ _j = a _j+1 + a ^′ _j+1 x 0 R = a ₀ + a ^′ ₀ x 0

In questo modo, partendo da n, ogni a ^′ _j viene calcolato quando a ^′ _j+1 ` e gi` a noto.

Questo procedimento rende particolarmente semplice

trovare le radici di un polinomio dato che, trovata la

prima, si pu` o ridurre di grado il polinomio e trovare

la successiva. Il procedimento si interrompe quando il

polinomio ` e arrivato al grado zero oppure quando non

ci sono pi` u radici reali

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.

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 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 ₂ ¹

volte l’intervallo inizia-

le.

Metodo di Newton

E applicabile quando si conosce la derivata della fun- ` zione. Espando la funzione vicino allo zero

f (x) = f (x 1 ) + f ^′ (x 1 ) · (x − x 1 )

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

0 = f (x ₁ ) + f ^′ (x ₁ ) · (α − x 1 ) 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.

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 ) ² Per N → ∞ C N → C purch´ e la derivata non si annulli.

l’andamento dell’errore ` e quindi

|α − x N +1 | ≈ C · |α − x N | ²

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 interseca le ascisse.

(x ₀ , f 0 ) e (x ₁ , f 1 ) siano i due punti iniziali f 2 − f 1

x ₂ − x 1

= f 1 − f 0

x ₁ − x 0

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

f 1 − f 0

· (x 1 − x 0 )

Analogamente i punti successivi sono dati dalla re- lazione 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 |

Metodi di punto fisso

Un punto x 0 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 ) = 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 succes- sione

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 esem- pio, l’equazione

x ² − 3x + 2 = 0

`

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, y ∈ [a, b]

vale

|g(x) − g(y)| < k · |x − y| k < 1