Appunti di Analisi Numerica

(1)

Appunti di Analisi Numerica

∗

Giuseppe Profiti

16 ottobre 2006

1 Polinomi

1.1 Richiami sui polinomi

p: ℜ → ℜ p(x) = a0+ a1x+ a2x 2

+ · · · + anx n

Con ai ∈ ℜ assegnati. Se an6= 0 il polinomio ha esattamente grado n.

p(x) ∈ Pn`e uno spazio di funzioni di grado al pi`u n (contiene tutti quelli

di grado ≤ n).

Si usano i polinomi perch´e possono essere calcolati esattamente sul cal-colatore (sono composti soolo da addizioni e moltiplicazioni).

Teorema 1 (fondamentale dell’algebra) Sia p(x) un polinomio di gra-do n > 1. L’equazione algebrica p(x) = 0 ha almeno una radice reale o complessa.

Corollario 1 Ogni equazione algebrica di grado n ha esattamente n radici reali o complesse. Cio´e p(x) = an(x − x1) m₁ (x − x2) m₂ · · · (x − xk) m_k

Con x1. . . xk radici distinte e mi molteplicit`a tale che Pmi = n

Teorema 2 (del resto) Siano a(x) e b(x) polinomi con b(x) 6= 01

allora esistono e sono unici i polinomi q(x) e r(x) per cui

a(x) = q(x) · b(x) + r(x) Con r(x) = 0 o r(x) di grado minore al grado di b(x)

(2)

1.2 Valutazione numerica di un polinomio

p(x) = a0 + a1x+ a2x 2 + · · · + anx n = n X i=0 aix i Algoritmo 1

Input: gli ai e x0 (punto in cui valutare il polinomio) Output: p(x0)

s = 1 p = a[0]

per k = 1,...,n s = s*x0 p = p+a[k]*s

Complessit`a 2n moltiplicazioni e n addizioni. Si pu`o migliorare, anche dal punto di vista numerico.

Modifico p(x) per ottenere un altro algoritmo: p(x) = a0+ a1x+ a2x 2 + · · · + anx n = a0+ x(a1+ a2x+ · · · + anxn−1) = a0+ x(a1+ x(a2+ · · · + anxn−2)) ...

= a0+ x(a1+ x(a2+ · · · + x(a_n−1+ anx) . . .)

Complessit`a: n addizioni e n moltiplicazioni. Algoritmo 2

p = a[n]

per k = n-1,...,0 p = a[k] + p*x0 `

E il miglior algoritmo (metodo di Horner) anche dal punto di vista nu-merico (`e pi`u stabile).

1.3 Ruffini e teorema del resto

Dati p(x) x0 (x − x0)

(3)

r(x) ha grado minore a quello di (x − x0), quindi `e una costante.

p(x) = q(x)(x − x0) + r

p(x0) = q(x0)(x0− x0) + r = r

Trovando il resto della divisione ho la valutazione di p(x0): uso Ruffini.

1.3.1 Regola di Ruffini an a_n−1 . . . a0 x0 x0· bn x0· b_n−1 . . . x0 · b1 bn b_n−1 b_n−2 · · · b1 r bn ← an bn−1 ← an−1+ x0bn bn−2 ← an−2+ x0b_n−1 ... b1 ← a1 + x0b2 r ← a0 + x0b1

`e come la formula di Horner ma bi sono i coef del polinomio quoziente che

nell’altro modo non avevo.

q(x) = n−1 X i=0 bi+1x i Esempio p(x) = 1 + x − 2x2 + 3x4 e x0 = 2 3 0 -2 1 1 2 6 12 20 42 3 6 10 21 43 Quindi p(2) = 43. 1.3.2 Derivata

Ci interessa la derivata, ma non in forma analitica: vogliamo valutarla. p(x) = q(x)(x − x0) + r

p′_{(x) = q}′_{(x)(x − x}

0) + q(x)

p′_(x

(4)

Esempio (dal precedente) 3 6 10 21 2 6 24 68 3 12 34 89 Quindi p′_{(2) = 89.} Implementazione p1 = 0 p = a[n] per k = n-1,...,0 p1 = p+x0 * p1 p = a[k]+x0*p p(x) ← p e p′_(x

0) ← p1. Fa le operazioni in parallelo: invece di calcolare

prima p e poi la derivta, ricopia e calcola per colonne.

1.4 Valutazione di un polinomio: errore inerente

Esempio

p(x) = 100 − x con x ∈ [100, 101]. a0 = 100 a1 = −1.

Simuliamo un errore di perturbazione sull’input: modifichiamo a1 di 1 100. q(x) = 100 − 1 − 1 100 x= 100 − 99 100x x= 101 p(101) = −1 q(101) = 0.01 q(101) − p(101) p(101) = 0.01 + 1 −1 = 1.01 = 101 · 1 100

(5)

1.4.1 Valutazione dell’errore inerente f : ℜ3 → ℜ f (a0, a1, x) = a0+ a1x0 EI N = f(˜x) − f (x) f(x) ≃ n X i=1 c1ǫi ǫi = ˜ xi− xi xi ci = xi f(x) ∂f ∂xi EI N = c1ǫ1+ c2ǫ2+ c3ǫ3

ǫ1 errore su a0, ǫ2 errore su a1, ǫ3 errore di x0.

EI N = a0 a0+ a1x0 ǫ1+ a1 a0+ a1x0 x0ǫ2+ x0 a0+ a1x0 a1ǫ3

Basta che uno dei termini sia grande per avere EI N grande.

Esempio (sempre quello di prima) a0 = 100 a1 = −1 x0 = 101 EI N = 100 100 − 101ǫ1+ −1 · 101 100 − 101ǫ2− 101 100 − 101ǫ3 = −100ǫ1 + 101ǫ2+ 101ǫ3 Sono tutti dell’ordine di 100. Nell’esempio precedente ǫ1 = ǫ3 = 0 e infatti

l’errore è 101 volte l’errore sui dati. Anche perturbando gli altri ci sarebbe stato un errore grande. È un errore inerente, si può fare poco per eliminarlo. Generalizzando EI N = EI N 1+ EI N 2 = = n X i=0 ai p(x) ∂p(x) ∂ai ǫi+ x p(x) ∂p(x) ∂x ǫx = n X i=0 aixi p(x)ǫi+ x p(x)p ′_(x)ǫ x

EI N 1 dipende dalla rappresentazione, EI N 2 invece no.

Se esistono differenti rappresentazioni del polinomio posso avere errori differenti in modo da modificare EI N 1

Quando scelgo la rappresentazione p(x) = a0+a1x+. . .+anx n

sto usando la base {1, x, x2

, . . . , xn

(6)

∃ infinite basi di rappresentazione per cui p(x) = n X i=0 biϕi(x) con base {ϕ0, . . . , ϕn} ∈ Pn

Esistono basi ben condizionate, tipicamente {1, x, x2

, . . . , xn

} `e mal condi-zionata soprattutto se devo valutare in [a, b] lontano dall’origine (gli elementi della base sono tutti centrati nell’origine).

Proviamo ad esempio a prendere le funzioni base centrate nell’intervallo, quindi passo da {1, x} a {1, (x − c)} (base delle potenze con centro) per il nostro esempio p(x) = 100 − x, con c = 100.

p(x) = a0+ a1x = b0+ b1(x − 100) = 0 + (−1)(x − 100) Perturbiamo b1 di 1 100 q(x) = (−1 + 1 100)(x − 100) = − 99 100(x − 100) x= 101 p(101) = −1 q(101) = 99 100 = −0.99 q(101) − p(101) p(101) = −0.99 + 1 1 = 0.01 = 1 · 1 100 x= 100.5 p(100.5) = −0.5 q(100.5) = −99 100 · 0.5 q(100.5) − p(100.5) p(100.5) = 0.005 0.5 = 0.01 = 1 · 1 100

Ho un errore relativo dello stesso tipo della perturbazione sui dati 1 100. EI N = c1ǫ1+ c2ǫ2+ c3ǫ3 = b0 b0+ b1(x − 100) ǫ1+ b1 b0+ b1(x − 100) ǫ2+ x b0+ b1(x − 100) b1ǫ3