Algoritmo di de Casteljau

Template:F In matematica e in particolare in analisi numerica, lTemplate:'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\text{ , }i=0,\dots ,n,$

${\beta }_i^{(j)}:={\beta }_i^{(j-1)}(1-t_0)+{\beta }_{i+1}^{(j-1)}{t}_0\text{ , }i=0,\dots ,n-j\text{ , }j=1,\dots n,$

con

$B(t_0)={\beta }_0^{(n)}.$

Annotazioni

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

$\begin{array}{ccccc}{\beta }_0& ={\beta }_0^{(0)}& & & \\ & & {\beta }_0^{(1)}& & \\ {\beta }_1& ={\beta }_1^{(0)}& & & \\ & & & \ddots & \\ ⋮& & ⋮& & {\beta }_0^{(n)}\\ & & & & \\ {\beta }_{n-1}& ={\beta }_{n-1}^{(0)}& & & \\ & & {\beta }_{n-1}^{(1)}& & \\ {\beta }_n& ={\beta }_n^{(0)}& & & \end{array}$

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)\text{ , }\in [0,1],$

fino a

$B_1(t)=\sum _{i=0}^n{\beta }_0^{(i)}{b}_{i,n}\left(\frac{t}{t_0}\right)\text{ , }\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)\text{ , }\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{array}{ccc}{\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{array}$

che è il polinomio di Bernstein desiderato di grado 2.