Appunti di Analisi Numerica
∗
Giuseppe Profiti
30 ottobre 2006
1
Esempi di curve di Bezier per caratteri
• Differenza tra carattere vettoriale e bitmap in un file PDF
• caratteri pfb in fontforge, modifica delle curve, esempio di riempimento con xccurv
• trasformazione da bitmap a vettoriale con xccurv
• importazione di file postscript in xccurv (il file contiene un’immagine)
2
Interpolazione polinomiale
Date n + 1 osservazioni su n + 1 punti distinti, cio´e (xi, yi)i=0,...,n, cerco una
ϕ∗ ∈ φ (con φ ≡ P n) tale che ϕ∗(xi) = yi i = 0, . . . , n ϕ∗(x) = n X i=0 a∗i · ϕi(x) Sono richieste • esistenza • unicit`a • buona ricostruzione
ϕ∗ dipende dai punti e dalla base. Cerchiamo di provare l’esistenza nella
base 1, x, x2
, . . . , xn.
Una volta dimostrate l’esistenza e unicit`a con una base, vale per tutto lo spazio.
Teorema 1 Dati n + 1 punti (xi, yi)i=0,...,n con xi distinti, ∃!p(x) ∈ Pn che
verifica le condizioni p(xi) = yi per i = 0, . . . , n
Dimostrazione:
i = 0 a0+ a1x0+ a2x20+ . . . + anxn0 = y0
i = 1 a1+ a1x1+ a2x21+ . . . + anxn1 = y1
...
i = n an+ a1xn+ a2x2n+ . . . + anxnn= yn
Formano un sistema di n + 1 equazioni lineari nelle incognite a0, a1, . . . , anil
problema di interpolazione `e quindi equivalente a trovare una soluzione del sistema. 1 x0 x20 . . . xn0 1 x1 x21 . . . x n 1 ... ... ... ... ... 1 xn x2n . . . xnn | {z } V(n+1)×(n+1) a0 a1 ... an | {z } ¯ a = y0 y1 ... yn | {z } ¯ y
Il sistema ammette una e una sola soluzione se V non `e singolare (det(V ) 6= 0). V `e una matrice di Vandermonde per cui
det(V ) = n Y i,j=0 j>i (xj− xi)
`e sempre diverso da zero perch´e nessun fattore sar`a zero (xi 6= xi ∀j)
Risolvendo il sistema trovo p(x), ma la matrice di vandermonde `e mal condizionata.
B0,n(x0) B1,n(x0) . . . Bn,n(x0) B0,n(x1) B1,n(x1) . . . Bn,n(x1) .. . ... . .. ... B0,n(xn) B1,n(xn) . . . Bn,n(xn) b0 b1 .. . bn = y0 y1 .. . yn
`e un sistema molto meglio condizionato del precedente. Generalmente abbiamo xi ∈ [a, b] (con a = x0 e b = xn come intervallo minimo), ma
possiamo fare il cambio di variabile per tornare in [0, 1]: x ∈ [a, b] → t ∈ [0, 1]. Le matrici con x e con t sono uguali, per`o con t semplifichiamo (a livello computazionale).
2.2
Interpolazione polinomiale nella base di Newton
La base di Newton `e una base locale, costituita da
1, (x−x0), (x−x0)(x−x1), (x−x0)(x−x1)(x−x2), . . . , (x−x0) · · · (x−xn−1) p(x) = d0+ d1(x − x0) + d2(x − x0)(x − x1) + . . . + dn(x − x0) · · · (x − xn−1) 1 0 0 · · · 0 1 (x1− x0) 0 · · · 0 1 (x2− x0) (x2− x0)(x2 − x1) · · · 0 .. . ... ... . .. 1 (xn− x0) (xn− x0)(xn− x1) · · · (xn− x0) · · · (xn− xn−1) d0 d1 .. . .. . dn = y0 y1 .. . .. . yn
(gli altri termini si annullano) `
E una matrice triangolare (bassa), ha lo stesso determinante della matrice di Vanbdermonde
d0 = y0
d0+ (x1− x0)d1 = y1
2.2.1 Implementazione per k=0,n d(k)=y(k) per i=1,n per k=n,i d(k)=(d(k)-d(k-1))/(x(k)-x(k-i)) 2.2.2 Valutazione dei polinomi di Newton
Si applica lo stesso metodo di Horner, si valuta dall’interno verso l’esterno: p(x) = d0+ (x − x0)[d1+ (x − x1)(d2+ (x − x2)(d3+ . . .)]
2.3
Interpolazione nella base di Lagrange
L0,n(x) L1,n(x) . . . Ln,n(x) p(x) = n X i=0 ? · Li,n(x)
vogliamo abbattere il costo computazionale. p(x) = n X i=0 yi· Li,n(x) Li,n(x) = ( 1 se i = j 0 se i 6= j 2.3.1 Costruzione di Li,n(x) `
E un polinomio con radici x0, . . . , xi−1, xi+1, . . . , xn, grazie al teorema
fonda-mentale dell’algebra abbiamo che:
Li,n= k(x − x0)(x − x1) · · · (x − xi−1(x − xi+1) · · · (x − xn)
Li,n = (x − x0)(x − x1) · · · (x − xi−1)(x − xi+1) · · · (x − xn) (xi− x0)(xi− x1) · · · (xi− xi−1)(xi− xi+1) · · · (xi− xn) = n Y j=0 j6=i (x − xj)/ n Y j=0 j6=i (xi − xj)
Nota: con Lagrange e Newton posso interpolare qualsiasi siano gli yi una
volta trovata la base. Esempio/esercizio Dati gli x {0,1,3}
1. trovare i polinomi di lagrange su x0, x1, x2 e rappresentarli graficamente
2. dati y0 = 0 y1 = 1 y2 = 2 esplicitare il polinomio interpolante nella
