En el subcamp matemàtic de l'anàlisi numèrica, l'algorisme de De BoorC. de Boor , "Subroutine package for calculating with B-splines", Techn.Rep. LA-4728-MS, Los Alamos Sci.Lab, Los Alamos NM; p. 109, 121. és un algorisme de temps polinòmic i numèricament estable per avaluar corbes spline en forma B-spline. És una generalització de l'algorisme de De Casteljau per a corbes de Bézier. L'algorisme va ser ideat pel matemàtic germano-americà Carl R. de Boor. S'han creat variants simplificades i potencialment més ràpides de l'algorisme de De Boor, però pateixen una estabilitat comparativament menor.
Introducció Una introducció general a les B-splines es troba a l'article principal. Aquí discutim l'algorisme de De Boor, un esquema eficient i numèricament estable per avaluar una corba spline. a la posició La corba es construeix a partir d'una suma de funcions B-spline multiplicat per constants potencialment vectorials , anomenats punts de control, B-splines d'ordre són funcions polinòmiques connexes a trossos de grau definit sobre una quadrícula de nusos (sempre utilitzem índexs de base zero en el següent). L'algorisme de De Boor utilitza operacions O(p²) + O (p) per avaluar la corba spline. Nota: l'article principal sobre B-splines i les publicacions clàssiquesC. de Boor , "Subroutine package for calculating with B-splines", Techn.Rep. LA-4728-MS, Los Alamos Sci.Lab, Los Alamos NM; p. 109, 121. utilitzen una notació diferent: la B-spline s'indexa com a amb .
Suport local Les B-splines tenen suport local, és a dir, que els polinomis només són positius en un domini compacte i zero en altres llocs. La fórmula de recursió de Cox-de Boor ho mostra:
Deixa que l'índex defineix l'interval de nusos que conté la posició, Podem veure a la fórmula de recursió que només les B-splines amb són diferents de zero per a aquest interval de nusos. Per tant, la suma es redueix a:
Es desprèn de això De la mateixa manera, veiem en la recursió que la ubicació del nus més alta consultada és a l'índex Això significa que qualsevol interval de nusos que realment s'utilitza ha de tenir com a mínim nusos addicionals abans i després. En un programa informàtic, això s'aconsegueix normalment repetint la primera i l'última ubicació del nus utilitzada vegades. Per exemple, per a i ubicacions reals dels nusos , s'ampliaria el vector de nusos a .
L'algorisme Amb aquestes definicions, ara podem descriure l'algorisme de de Boor. L'algorisme no calcula les funcions B-spline. directament. En comptes d'això, avalua mitjançant una fórmula de recursió equivalent.
Deixa ser nous punts de control amb per Per a s'aplica la recursivitat següent: Un cop finalitzades les iteracions, tenim , és a dir que és el resultat desitjat.
L'algorisme de De Boor és més eficient que un càlcul explícit de B-splines amb la fórmula de recursió de Cox-de Boor, perquè no calcula termes que es garanteixen que es multiplicaran per zero.
Optimitzacions L'algorisme anterior no està optimitzat per a la implementació en un ordinador. Requereix memòria per a punts de control temporals Cada punt de control temporal s'escriu exactament una vegada i es llegeix dues vegades. Invertint la iteració al llarg de (comptant enrere en comptes de cap amunt), podem executar l'algorisme amb memòria només per a punts de control temporals, permetent reutilitzar la memòria per a De la mateixa manera, només hi ha un valor de s'utilitza a cada pas, de manera que també podem reutilitzar la memòria.
A més, és més convenient utilitzar un índex de base zero per als punts de control temporals. La relació amb l'índex anterior és . Així obtenim l'algorisme millorat:
Sigui per . Iterar per a : Tingueu en compte que s'ha de comptar enrere j. Un cop finalitzades les iteracions, el resultat és .
Implementació d'exemple El següent codi del llenguatge de programació Python és una implementació ingènua de l'algorisme optimitzat.def deBoor(k: int, x: int, t, c, p: int): """Evaluates S(x).
Arguments
k: Índex de l'interval de nusos que conté x. x: Posició. t: Matriu de posicions de nusos, cal omplir-la tal com s'ha descrit anteriorment. c: Matriu de punts de control. p: Grau de la B-spline. """ d = [c[j + k - p] for j in range(0, p + 1)]
for r in range(1, p + 1): for j in range(p, r - 1, -1): alpha = (x - t[j + k - p]) / (t[j + 1 + k - r] - t[j + k - p]) d[j] = (1.0 - alpha) * d[j - 1] + alpha * d[j]
return d[p]
Referències
Categoria:Anàlisi numèrica