Algoritmo di de Casteljau

Da Wikipedia, l'enciclopedia libera.

Nel campo dell'analisi numerica della matematica, l'algoritmo di de Casteljau, che prende il nome dal suo autore Paul de Casteljau, è un metodo ricorsivo per valutare polinomi nella forma di Bernstein o curve di Bézier.

Sebbene l'algoritmo sia più lento per la maggior parte delle architetture se comparato all'approccio diretto, è numericamente più stabile.

Definizione[modifica | modifica wikitesto]

Dato un polinomio B in forma di Bernstein di grado n

B(t) = \sum_{i=0}^{n}\beta_{i}b_{i,n}(t),

dove b è un polinomio base di Bernstein, il polinomio al punto t0 può essere valutato con la relazione di ricorrenza

\beta_i^{(0)} := \beta_i \mbox{ , } i=0,\ldots,n
\beta_i^{(j)} := \beta_i^{(j-1)} (1-t_0) + \beta_{i+1}^{(j-1)} t_0 \mbox{ , } i = 0,\ldots,n-j \mbox{ , } j= 1,\ldots n

con

B(t_0)=\beta_0^{(n)}.

Annotazioni[modifica | modifica wikitesto]

Nel calcolo manuale è utile scrivere i coefficienti in uno schema triangolare del tipo:


\begin{matrix}
\beta_0     & = \beta_0^{(0)}     &                   &         &               \\
            &                     & \beta_0^{(1)}     &         &               \\
\beta_1     & = \beta_1^{(0)}     &                   &         &               \\
            &                     &                   & \ddots  &               \\
\vdots      &                     & \vdots            &         & \beta_0^{(n)} \\
            &                     &                   &         &               \\
\beta_{n-1} & = \beta_{n-1}^{(0)} &                   &         &               \\
            &                     & \beta_{n-1}^{(1)} &         &               \\
\beta_n     & = \beta_n^{(0)}     &                   &         &               \\
\end{matrix}

Nella scelta di un punto t0 per cui calcolare il polinomio di Bernstein, si possono usare le diagonali dello schema triangolare per costruire una divisione del polinomio.

B(t) = \sum_{i=0}^n \beta_i^{(0)} b_{i,n}(t) \qquad \mbox{ , } \in [0,1]

fino a

B_1(t) = \sum_{i=0}^n \beta_0^{(i)} b_{i,n}\left(\frac{t}{t_0}\right) \qquad \mbox{ , } \in [0,t_0]

e

B_2(t) = \sum_{i=0}^n \beta_{n-i}^{(i)} b_{i,n}\left(\frac{t-t_0}{1-t_0}\right) \qquad \mbox{ , } \in [t_0,1]

Esempio[modifica | modifica wikitesto]

Si vuole calcolare il valore del polinomio di Bernstein di grado 2 con i coefficienti:

\beta_0^{(0)} = \beta_0
\beta_1^{(0)} = \beta_1
\beta_2^{(0)} = \beta_2

nel punto t0.

Si avvia la ricorsione con:

\beta_0^{(1)} = \beta_0^{(0)} (1-t_0) + \beta_1^{(0)}t_0 = \beta_0(1-t_0) + \beta_1 t_0
\beta_1^{(1)} = \beta_1^{(0)} (1-t_0) + \beta_2^{(0)}t_0 = \beta_1(1-t_0) + \beta_2 t_0

e alla seconda iterazione la ricorsione termina con:

 
\begin{matrix}
\beta_0^{(2)} & = & \beta_0^{(1)} (1-t_0) + \beta_1^{(1)} t_0      \\
\             & = & \beta_0(1-t_0) (1-t_0) + \beta_1 t_0 (1-t_0) + \beta_1(1-t_0)t_0 + \beta_2 t_0 t_0 \\
\             & = & \beta_0 (1-t_0)^2 + \beta_1 2t_0(1-t_0) + \beta_2 t_0^2         \\
\end{matrix}

che è il polinomio di Bernstein desiderato di grado 2.

Altri progetti[modifica | modifica wikitesto]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica