Algoritmo di de Casteljau

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

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 t₀ 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

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 t₀ 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

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 t₀.

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

• Commons

• Commons contiene immagini o altri file su Algoritmo di de Casteljau

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