Algoritmo di de Casteljau
# Algoritmo di de Casteljau

In matematica e in particolare in analisi numerica, 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_0$ 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_0$ 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_0.$

Si avvia la ricorsione con:

    Errore del parser (SVG (MathML può essere abilitato tramite plug-in del browser): risposta non valida ("Math extension cannot connect to Restbase.") dal server "http://localhost:6011/it.wikipedia.org/v1/":): {\displaystyle \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.

