Appunti di Analisi Numerica

Appunti di Analisi Numerica

∗

Giuseppe Profiti

23 ottobre 2006

1

Base dei polinomi di Bernstein

p(x) =

n

X

i=0

biBi,n(x) x ∈ [a, b]

La base `e costruita sull’intervallo di interesse. Bi,n(x) = n i ! (b − x)n−i_{(x − a)}i (b − a)n Esempio p(x) = 100 − x (1) = −1 · (x − 100) (2) = b0B0,1(x) + b1B1,1(x) (3)

Le diverse rappresentazioni sono

• base delle potenze (1), a0+ a1xcon a0 = 100, a1 = −1

• base delle potenze con centro (2), c0+ c1(x − 100) con c0 = 0, c1 = −1

• base di Bernstein (3), da calcolare

B_0,1(x) = 1 0

!

(101 − x)1−0_{(x − 100)}0

(101 − 100)1 = (101 − x)

B1,1(x) = 1 1 ! (101 − x)1−1_{(x − 100)}1 (101 − 100)1 = (x − 100) p(x) = b0(101 − x) + b1(x − 100) Quindi b0 = 0 e b1 = −1.

La base centrata e quella di Bernstein sono diverse ma in questo caso capita che la rappresentazione coincida.

Errore inerente EIN = c1ǫ1+ c2ǫ2+ c3ǫ3 = b₀ p(x)(101 − x)ǫ1+ b₁ p(x)(x − 100) | {z } ∼ =1 ǫ2+ x p(x)p ′_(x) | {z } ∗ ǫ3

* non dipende dalla rappresentazione, gli altri coef. sono dell’ordine di 1 come per la base delle potenze con centro.

La base di bernstein `e interessante perch´e permette di intervenire anche sul cuoef. di ǫ3.

1.1

Cambio di variabile

x∈[a, b] → t ∈ [0, 1] t = x− a

b− a x= a + t(b − a)

A p(x) sostituisco la x dalla formula precedente in modo da ottenere q(t). q(t) `e uguale a p(x) ma traslato e scalato, per t e x che corrispondono p(x) = q(t).

q(t) `e un polinomio con dei nuovi coef. che dovr`o calcolare. In bernstein i coef restano uguali quindi evito gli eventuali errori di calcolo nel cambio di variabile. p(x) = n X i=0 biBi,n(x) = n X i=0 bi n i ! (b − x)n−i_{(x − a)}i (b − a)n cambio variabile = n X i=0 bi n i ! [b − a − t(b − a)]n−i_{[a + t(b − a) − a]}i (b − a)n = n X i=0 bi n i !

[(b − a)(1 − t)]n−i_{[t(b − a)]}i

= n X i=0 bi n i ! (1 − t)n−i_ti = n X i=0 biBi,n(t) t ∈[0, 1]

La base ha assorbito il cambio di variabile. La base di bernstein in [0,1] pu`o simulare qualsiasi intervallo.

Esempio p(x) = b0(101−x)+b1(x−100) = b0(1−t)+b1(t−0) x∈[100, 101], t ∈ [0, 1] EIN = b₀ p(x)(101 − x)ǫ1+ b₁ p(x)(x − 100) | {z }

questi sono uguali

ǫ₂+ x p(x)p ′_(x) | {z } ∗ ǫ₃

Vediamo come `e cambiato * col cambio di variabile.

Prima era x ∈ [100, 101], ora t ∈ [0, 1]. p′_{(t) = (b − a)p}′_(x)1 _{resta uguale}

perch´e (b − a) = (101 − 100) = 1. t

p(t)p′(t) sar`a dell’ordine dell’unit`a.

Esempio (continuazione)

p(t) = −t t ∈ [0, 1] b0 = 0 b1 = −1

Perturbazione su t (voglio vedere come il cambio di variabile influisce sull’errore, lasciando fermo il resto).

t = 1 ¯t= 0.99 p(1) = −1 q(0.99) = 0.99      p(1) − q(1) p(1)      ∼ = 1 · 1 100

Posso fare alcune operazioni in [0,1] senza il cambio di variabile: non ho il problema di calcolarlo (es. disegno del polinomio).

1.2

Propriet`

a dei polinomi di Bernstein

• Bi,n(t) ≥ 0 ∀i= 0, . . . , n ∀t ∈ [0, 1]

• Pn_i=0Bi,n(t) = 1 ∀t ∈ [0, 1]

Il fatto che siano tutte positive `e buono: si lavora con termini dello stesso segno e quindi si evitano casi di cancellazione numerica.

Esempio Con n = 2 B0,2(t) = 2 0 ! (1 − t)2−0t0 = (1 − t)2 B1,2(t) = 2 1 ! (1 − t)2−1t1 = 2(1 − t)t B2,2(t) = 2 2 ! (1 − t)2−2t2 = t2

La prima e l’ultima funzione base sono simmetriche rispetto al centro dell’intervallo.

La somma in qualsiasi punto `e 1, si vede anche analiticamente: Bi,n `e la

rappresentazione del binomio [(1 − t) + t]n_{= 1.}

Dato che la somma `e 1, p(x) `e una combinazione affine, essendo anche sempre positiva `e una combinazione convessa. Da questo si deriva che

minbi ≤ p(x) ≤ maxbi

Il segno dei bi indica quante radici ci sono:

• se sono tutti positivi o tutti negativi non ci sono radici

• se alcuni sono positivi e altri negativi in base ai cambiamenti di segno posso trovare il numero di radici

1.3

Definizione ricorrente dei pol. di Bernstein

Bi,n(t) = t · Bi−1,n−1(t) + (1 − t) · Bi,n−1(t)

Con B0,0(t) = 1 e Bi,n = 0 ∀i 6∈ 0, n.

1.4

Algoritmo 1

Input: b0, . . . , bn, ¯t, output: valutazione di p(¯t)

1. calcolo l’array di valori [B0,n(¯t), . . . , Bn,n(¯t)] Contiene l’ultima riga dello

schema precedente. 2. Pn

i=0biBi,n(¯t)

`

E stabile ma ha complessit`a O(n2₎

1.5

Algoritmo 2 (de Casteljeau)

p(t) = n X i=0 biBi,n(t) = n X i=0 bi[t · Bi−1,n−1(t) + (1 − t)Bi,n−1(t)] = n X i=0 bit· Bi−1,n−1(t) + n X i=0 bi(1 − t)Bi,n−1(t) = n X i=1 bit· Bi−1,n−1(t) + n−1 X i=0 bi(1 − t)Bi,n−1(t) = n−1 X i=0 bi+1t· Bi,n−1(t) + n−1 X i=0 bi(1 − t)Bi,n−1(t) = n−1 X i=0 [bi+1t+ bi(1 − t)] · Bi,n−1(t) = n−1 X i=0 b[1]_i · Bi,n−1(t) = n−1 X i=0 b[2]_i · Bi,n−2(t) = ... = n−1 X i=0 b[n]i · Bi,0(t) = b[n]₀ = p(t) Input: b0, . . . , bn, ¯t

Con uno schema simile al precedente, ma invertito, dagli n bi possiamo

ricavare gli n - 1 b[1]i e cos`ı via fino a ottenere b [n]

0 = p(¯t).

`

1.6

Curve di Bezier

E un’applicazione nel piano, ogni coef `e un punto che delimina una po-ligonale. Il numero di punti indica il grado: P0, . . . , P3 per una cubica, in

generale Pn indica un un grado n − 1.