De la Wikipedia, enciclopedia liberă.
În matematică și în special în analiza numerică , algoritmul de Casteljau , numit după autorul său Paul de Casteljau , este o metodă recursivă pentru evaluarea polinoamelor sub forma curbelor Bernstein sau Bézier .
Deși algoritmul este mai lent pentru majoritatea arhitecturilor în comparație cu abordarea directă, este mai stabil din punct de vedere numeric.
Definiție
Dat fiind un polinom B în forma Bernstein de grad n
- {\ displaystyle B (t) = \ sum _ {i = 0} ^ {n} \ beta _ {i} b_ {i, n} (t),}
unde b este un polinom Bernstein de bază , polinomul din punctul t 0 poate fi evaluat cu relația de recurență
- {\ displaystyle \ beta _ {i} ^ {(0)}: = \ beta _ {i} {\ mbox {,}} i = 0, \ ldots, n,}
- {\ displaystyle \ beta _ {i} ^ {(j)}: = \ beta _ {i} ^ {(j-1)} (1-t_ {0}) + \ beta _ {i + 1} ^ { (j-1)} t_ {0} {\ mbox {,}} i = 0, \ ldots, nj {\ mbox {,}} j = 1, \ ldots n,}
cu
- {\ displaystyle B (t_ {0}) = \ beta _ {0} ^ {(n)}.}
Adnotări
În calculul manual este util să scrieți coeficienții într-o schemă triunghiulară, cum ar fi:
- {\ displaystyle {\ 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}}}
În alegerea unui punct t 0 pentru care să se calculeze polinomul Bernstein, diagonalele schemei triunghiulare pot fi utilizate pentru a construi o diviziune a polinomului.
- {\ displaystyle B (t) = \ sum _ {i = 0} ^ {n} \ beta _ {i} ^ {(0)} b_ {i, n} (t) \ qquad {\ mbox {,}} \ în [0,1],}
![{\ displaystyle B (t) = \ sum _ {i = 0} ^ {n} \ beta _ {i} ^ {(0)} b_ {i, n} (t) \ qquad {\ mbox {,}} \ în [0,1],}](https://wikimedia.org/api/rest_v1/media/math/render/svg/31d0ba5cd1e22ab53d9a22594b7a722e9e931c9e)
până la
- {\ displaystyle 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}]}
![{\ displaystyle 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}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9e5b29a84f7ddedd9a759e438af4a7ae190cc2a1)
Și
- {\ displaystyle B_ {2} (t) = \ sum _ {i = 0} ^ {n} \ beta _ {ni} ^ {(i)} b_ {i, n} \ left ({\ frac {t- t_ {0}} {1-t_ {0}}} \ right) \ qquad {\ mbox {,}} \ în [t_ {0}, 1].}
![{\ displaystyle B_ {2} (t) = \ sum _ {i = 0} ^ {n} \ beta _ {ni} ^ {(i)} b_ {i, n} \ left ({\ frac {t- t_ {0}} {1-t_ {0}}} \ right) \ qquad {\ mbox {,}} \ în [t_ {0}, 1].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d70b319c386ca4fc3ec89018b2fcb419f5d35004)
Exemplu
Vrem să calculăm valoarea polinomului Bernstein de gradul 2 cu coeficienții:
- {\ displaystyle \ beta _ {0} ^ {(0)} = \ beta _ {0}}
- {\ displaystyle \ beta _ {1} ^ {(0)} = \ beta _ {1}}
- {\ displaystyle \ beta _ {2} ^ {(0)} = \ beta _ {2}}
la punctul t 0 .
Recursivitatea începe cu:
- {\ displaystyle \ beta _ {0} ^ {(1)} = \ beta _ {0} ^ {(0)} (1-t_ {0}) + \ beta _ {1} ^ {(0)} t_ {0} = \ beta _ {0} (1-t_ {0}) + \ beta _ {1} t_ {0}}
- {\ displaystyle \ beta _ {1} ^ {(1)} = \ beta _ {1} ^ {(0)} (1-t_ {0}) + \ beta _ {2} ^ {(0)} t_ {0} = \ beta _ {1} (1-t_ {0}) + \ beta _ {2} t_ {0}}
iar la a doua iterație recursivitatea se termină cu:
- {\ displaystyle {\ 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}}}
care este polinomul Bernstein dorit de gradul 2 .
Alte proiecte
Wikimedia Commons conține imagini sau alte fișiere în Algoritmo de la Casteljau 
