Progettazione e valutazione di una applicazione ed un applet Java per l’interpolazione polinomiale

 3
Nella tesi ci siamo occupati dell’interpolazione polinomiale nella formu- 
lazione di Lagrange e di Newton.  
Abbiamo  richiamato i risultati più importanti come l’esestenza e l’unicità 
del polinomio interpolante di grado n su n+1 nodi diversi. 
Se però, n è molto grande il polinomio può avere un andamento troppo 
oscillante per rappresentare adeguamente la funzione . 
In questo caso si ricorre a polinomi a tratti e  tra questi , imponendo 
condizioni di regolarità, le splines. 
Le splines oramai sono di larghissimo inpiego nei settori più disparati dal 
design automobilistico da cui traggono origine alle nuove frontiere 
dell’architettura  organica passando ovviamente  attraverso l’informatica. 
Nel campo informatico  vengono utilizzate per la grafica digitale (ad 
esempio i caratteri che stiamo utilizzando ora) nonché nella realizzazione 
dei motori grafici 3D dei videogiochi di ultima generazione come Quake 
3 Arena. 
In questo lavoro di tesi abbiamo progettato e valutato un software per  
l’interpolazione tramite polinomio di Newton e splines. 
Abbiamo codificato l’algoritmo utilizzando il linguaggio Java,  creando 
sia l’applet fruibile attraverso un browser che una applicazione eseguibile 
. 
 4
Abbiamo ripercorso la storia del linguaggio java e ne abbiamo  analizzato 
le principali caratteristiche e versioni. 
Nella parte conclusiva della tesi , infine , abbiamo documentato il codice  
e lo abbiamo valutato su diversi esempi.  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 5
§ 1.1 - Interpolazione:  problema generale 
Definizione (Interpolazione)  
Sia    Y ,  Y spazio lineare e  nY   dim ; 
sia
*
Y spazio duale 
1
 di Y     
n
lll .,.........,
21
*
Y      funzionali lineari 
n
fff
~
2
~
1
~
.,.........,       scalari 
trovare un Yy     tale che : 
(1.1.0)                        
~
ii
fyl      per .,.........2,1 ni    
 
Es.1:   Dati n+1 reali 
n
xxx ,.......,,
10
   con 
ji
xx  ζ  e dati, n+1 scalari 
n
fff
~
1
~
0
~
.,........., ; i funzionali    yl
i
,  per  
n
Py     ed 
*
Yl
i
   
definiti da: 
(1.1.1)                        ,
1  ii
xyyl  per   1.,.........2,1     ni  
Il problema  (1.1.0) e la (1.1.1), con N=n+1, (problema                        
dell’interpolazione di Lagrange), consiste nel  determinare   il     polinomio   
                                                 
1
  spazio duale : insieme dei funzionali lineari su Y  
 6
algebrico di grado non superiore ad N,  che nei nodi 
i
x
 assume i valori  
i
f
~
 per   
ni ,........,2,1,0  
. 
 
Es.2:     Scelto 
12   
  
n
PY
nn
ffffff
~
1
~
0
~~
1
~
0
~
'.,.........',',.,........., ,  
assegnati    12   n  reali distinti 
n
xxx ,.......,,
20
ed assegnanti      22   n  
scalari; 
nn
ffffff
~
1
~
0
~~
1
~
0
~
'.,.........',',.,........., ;   i funzionali     yl
i
 che 
definiamo nel seguente modo: 
(1.1.2)             ,
1  
  
ii
xyyl      per  1,.......2,1     ni                      
(1.1.2)             ,'
2    
  
nii
xyyl   per  ,22.,,.........3,2         nnni    
   dove 
                   
j
xx
j
xy
dx
d
xy
  
 ' . 
 
Il problema (1.1.0) e (1.1.2) con ,22     nN  (problema    dell’interpolazione  
di Hermite),  consiste nel  determinare  il polinomio algebrico di grado 
non superiore a     12   n  che nei punti    
i
x  per ni ,......2,1,0   assume i 
valori    
i
f  e la cui derivata assume negli stessi  punti, i valori 
i
f '
~
  
),......1,0( ni   . 
 7
§ 1.2 - Interpolazione 
In generale:  
Dati i nodi ),(
ii
yx  (i=0….n)  con 
m
i
x    , 1 τm , 
ji
xx  ζ  per ji  ζ,  
e la classe di funzioni : 
),....,(
0 n
zzxf  
 dobbiamo  trovare 
n
zz ......
0
(gradi di libertà) t.c   
ini
yzzxf   ),....,(
0
  per  ni .......1,0  . 
Quindi è necessario trovare una classe di funzioni approssimanti ed 
utilizzare un criterio per trovare il polinomio approssimato. 
Se la funzione è linearmente dipendente dai  
n
zz .........
0
: 
)(......)()(),......,(
11000
xfzxfzxfzzzxf
nnn
      ; 
parleremo di interpolazione lineare. 
Le classi più comuni sono: 
1) Classe      xP
n
:  {Polinomi algebrici di grado n}. 
Sia    x , e sia     xf  continua su intervalli chiusi e limitati:  allora si può 
parlare di interpolazione polinomiale con:  
n
n
1
10n0
x......zxzz),......zzf(x,       
 
ed )(xf  continuo in ],[  Ε ∆ . 
 8
Per il teorema di Weierstrass  
2
   
  
      xP
n
 t.c.   )()( xPxf
n
   Η δ        >  ≅ Ε∆,   x . 
2) Classe      ωT
n
: {Polinomi  trigonometrici}. 
Sia    x , e sia     xf  continua e periodica, parleremo in questo caso  di 
interpolazione trigonometrica   
            
ƒ
  
   
n
k
kk
kxbkxaaxf
1
0
sincos
dove:  
n = grado del polinomio trigonometrico 
n
a , 
n
b  di cui almeno uno diverso da zero 
Dalla formula di Eulero 
3
 abbiamo  che  : 
    
ƒ
    
n
nk
ikx
kn
exf  ∆ ; 
ossia         
nxi
n
xi
n
eexf  ∆ ∆∆         ........
10
 
Per un teorema simile a quello di  Weierstrass    
 
                                                 
2
 Teorema di Weierstrass    
Ogni funzione definita e continua in un insieme chiuso e limitato è dotata di minimo e di massimo. 
                                                                                                                                                                                               
3
 Formule di Eulero     (usate per esprimere seno e coseno mediante esponenziali complessi) 
      
i
ee
x
ixix
2
sin
  
  
 ,         
2
cos
ixix
ee
x
  
  
,   
 
 9
Teorema 1.2.0 
Data una funzione     xf  continua e periodica,  di periodo  
 Ζ
 Σ2
     
           
0 !  Η
   ( tolleranza ) 
  
  un polinomio trigonometrico       Ζ,xT
n
     t.c. :  
       ΗΖ   ,xTxf
n
       
.     x
. 
 
3) Classe      xR
mn,
 : {Funzioni razionali}. 
Nel caso di punti all’infinito, fenomeni non periodici su intervalli infiniti; 
allora, possiamo procedere con una approssimazione mediante funzioni 
razionali  la cui funzione interpolante è data dal rapporto di due 
polinomi di grado rispettivamente n ed m :   
    
m
m
n
n
n
xx
xx
xf
 Ε Ε Ε
 ∆ ∆ ∆
      
      
.......
.......
10
10
 
 
con  2    nm  parametri. 
Questa approssimazione fornisce algoritmi più efficienti  per valutare sul 
calcolatore funzioni trascendenti. 
Molto importante nelle applicazioni grafiche (da cui il nome) sono le  
polinomi di grado n, tale che, unendo tali tratti abbiamo  la continuità 
 10
della funzione. In caso di polinomi di grado troppo elevato, le spline 
rivestono una  certa importanza in quanto consentono di avvicinarsi alla 
precisione desiderata riducendo l’errore. 
 
 
§ 1.2.1 - Unicità della soluzione 
In questo paragrafo parleremo  dell’approssimazione in un  dato 
intervallo  >  ≅ba, ,  di dati numerici  o di funzioni, ottenuti utilizzando 
polinomi  (eventualmente unici) scelti seguendo i criteri 
dell’interpolazione polinomiale . 
Sia > ≅ba,  un intervallo limitato, e dati 1  n  nodi     
ji
yx ,  per 
ni ..........0  ,  tale che :  
 (1.2.1)                           
ii
yxf     con  
ji
xx  ζ    per ji  ζ;   
troviamo il polinomio di grado minimo che passa per tali nodi. 
Se considerino il polinomio di grado n 
 (1.2.2)                              
n
non
xaxaxaaxP ........
2
21
              
nelle  n+1 incognite   
n
aa .............
0
,  otteniamo imponendo la  (1.2.1)   
il  sistema :   
 11
(1.2.3)                        
 ÷
 ÷
 ÷
 ÷
 ÷
 ≠
 •
 ♦
 ♦
 ♦
 ♦
 ♦
 ♥
 ♣
n
nn
n
n
xx
xx
xx
1
1
1
11
00
 ÷
 ÷
 ÷
 ÷
 ÷
 ≠
 •
 ♦
 ♦
 ♦
 ♦
 ♦
 ♥
 ♣
n
a
a
a
1
0
= 
 ÷
 ÷
 ÷
 ÷
 ÷
 ≠
 •
 ♦
 ♦
 ♦
 ♦
 ♦
 ♥
 ♣
n
y
y
y
1
0
    
le cui incognite sono gli 
n
aa .............
0
.     
Per determinare gli 
i
a  utilizziamo il  Metodo dei coefficienti 
indeterminati. 
Sia quindi : 
(1.2.4)                           V=
 ÷
 ÷
 ÷
 ÷
 ÷
 ≠
 •
 ♦
 ♦
 ♦
 ♦
 ♦
 ♥
 ♣
n
nn
n
n
xx
xx
xx
1
1
1
11
00
  ,                         
la matrice del sistema,  detta matrice di Vandermonde 
4
. 
 Nel caso i nodi siano tutti distinti, ossia: 
ji
xx  ζ   per  ji  ζ, allora  la 
matrice dei coefficienti  del sistema è non singolare. Infatti in   questo 
caso abbiamo: 
(1.2.5)                             
  
  
       !
÷
 ≠
 •
 ♦
 ♥
 ♣
     
1
01
det
n
j
n
Ji
ji
ji
ji
xxxxV .    
   
                                                 
4
 Matrice di Vandermonde: La matrice di Vandermonde è la matrice dei coefficienti di un 
problema di interpolazione, e dipende solamente dalla disposizione dei nodi di griglia, 
m
xxx .....,
10
 
E’ la matrice (m+1) * (n+1) definita da:     
j
i
xjiA   ,  
 
 12
Teorema 1.2.1 
Dati  n+1 punti: 
       
ii
yx ,   ni ......0      con  
ii
yx  ζ  se ji  ζ 
esiste un unico polinomio 
n
Pp    t.c.:  
(1.2.6)                          
ii
yxp    per  i=0…..n      
Dim 
Supponiamo che per assurdo esistano due polinomi  interpolanti di 
grado n :      xL
n
  e    xP
n
,  entrambi interpolanti  la funzione     xf ,
si ha:   
          
iinin
xfxPxL        per   ni ......0   
Consideriamo il polinomio di grado al più n   differenza dei due 
polinomi : 
         xPxLxH
nnn
   ; 
il valore di     xH
n
 negli   1  n  nodi sarà:  
                0       
iinnn
xfxfxPxLxH  
e quindi     xH
n
 ammette 1  n zeri .Ma, qua troviamo l’assurdo, infatti il 
teorema fondamentale dell’algebra ci dice che un polinomio di grado n  
ammette al più n zeri. Quindi     0 {xH
n
.  
 ξ
 
 13
Il sistema precedente è utile per stabilire che il polinomio interpolante 
esiste ed è unico, quando 
ji
xx  ζ    per ji  ζ; ma,  riguardo alla soluzione 
è sconsigliabile procedere visto il mal condizionamento dei sistemi con  
matrice di Vandermonde. Occorrerà cercare altre soluzioni più stabili.   
 
 
§ 1.3 - Interpolazione di Lagrange  
Abbiamo visto che per trovare i coefficienti del polinomio interpolante  
basta risolvere il sistema: 
 ÷
 ÷
 ÷
 ÷
 ÷
 ≠
 •
 ♦
 ♦
 ♦
 ♦
 ♦
 ♥
 ♣
n
nn
n
n
xx
xx
xx
1
1
1
11
00
 ÷
 ÷
 ÷
 ÷
 ÷
 ≠
 •
 ♦
 ♦
 ♦
 ♦
 ♦
 ♥
 ♣
n
a
a
a
1
0
= 
 ÷
 ÷
 ÷
 ÷
 ÷
 ≠
 •
 ♦
 ♦
 ♦
 ♦
 ♦
 ♥
 ♣
n
y
y
y
1
0
 
L’indice di condizionamento della matrice , però  cresce in misura 
esponenziale al crescere di n.  
L’interpolazione di Lagrange serve per aggirare il mal condizionamento 
del problema lineare con la matrice di Vandermonde come matrice dei 
coefficienti.  La  tecnica di Lagrange si può considerare come una 
alternativa  a quella di Newton che, anch’essa  come vedremo nei para- 
grafi successivi ci  permette di calcolare il polinomio interpolante senza  
 14
cadere in problemi di mal condizionamento. 
Definiamo polinomio fondamentale di Lagrange : 
    
    
   
  
 
 ζ
  
  
  
  
  
n
ji
oi
ij
n
ji
i
i
j
xx
xx
xL
0
. 
La condizione fondamentale che si richiede è che:  
ji
xx  ζ   per ji  ζ 
Vediamo come si arriva a questa formula: 
Consideriamo 
n
P  ( classe dei polinomi di grado n), e andiamo ad introdurre 
quindi una base in tale polinomio:     
  
  
 nj ......1,0    introduciamo  il polinomio    xL
j
 associato  ai dati : 
    
jii
x
,
, Γ   per ni ......1,0   
dove   
ji ,
Γ
 °
 ↓
 °
→
 ↑
  
 ζ
jise
jise
1
0
      per    nj ..........1,0  . 
La 
a
1
  condizione dice :   
ji ,
Γ 0   se  ji  ζ, ossia si annulla negli n nodi e 
quindi occorre che : 
 15
(1.3.0)                                    
  
 ζ
  
  
n
ji
i
ijj
xxcxL
0
, 
con la 
a
2  condizione :    
ji ,
Γ 1  se  ji   , abbiamo: 
       1
0
      
 
 ζ
  
n
ji
i
ijjjj
xxcxL ,  
da cui otteniamo: 
(1.3.1)                              
    
 
 ζ
  
  
  
n
ji
oi
ij
j
xx
c
1
 ;    
sostituiamo  ed abbiamo  la rappresentazione: 
(1.3.2)                         
   
    
 
   ζ
  
 ζ
  
    
  
n
ji
i
in
ji
oi
ij
j
xx
xx
xL
0
1
             
quindi: 
(1.3.3)                              
    
    
 
 
 ζ
  
  
  
  
  
n
ji
oi
ij
n
ji
i
i
j
xx
xx
xL
0
;          
siamo cosi arrivati alla base cercata.