[Artikel] Bernstein - Polynome und CAD

09.10.2008, 19:01

tigerbine

[Artikel] Bernstein - Polynome und CAD

Die Bernstein-Polynome bis zum Grad n bilden eine Basis des Vektorraums $\begin{eqnarray*} \Pi_n \end{eqnarray*}$ . In den Workshops [Polynominterpolation] und [Orthogonale Polynome] findet man zum Beispiel die Monom-Basis, die Newton-Basis oder die Tschebyscheff-Basis. Jede hat unter einem bestimmten Blickwinkel ihre Vorzüge. Welche Vorzüge bieten die Bernsteinpolynome?

Zunächst einmal betrachtet man sie nur das Intervall [0,1]. Die ersten Basen lauten dann wie folgt:

$\begin{eqnarray*} B_{0,0}(t)=1 \end{eqnarray*}$
$\begin{eqnarray*} B_{0,1}=-t+1 \end{eqnarray*}$

$\begin{eqnarray*} B_{1,1}=t \end{eqnarray*}$
$\begin{eqnarray*} B_{0,2}=(t-1)^2 \end{eqnarray*}$

$\begin{eqnarray*} B_{1,2}=-2(t-0.5)^2+0.5 \end{eqnarray*}$

$\begin{eqnarray*} B_{2,2}=t^2 \end{eqnarray*}$
$\begin{eqnarray*} B_{0,3}=-t^3+3t^2-3t+1 \end{eqnarray*}$

$\begin{eqnarray*} B_{1,3}=3t^3-6t^2+3t \end{eqnarray*}$

$\begin{eqnarray*} B_{2,3}=-3t^3+3t^2 \end{eqnarray*}$

$\begin{eqnarray*} B_{3,3}=t^3 \end{eqnarray*}$

Es fällt auf, dass der n-te Basisvektor identisch mit dem n-ten Basisvektor der Monom-Basis ist. Schauen wir uns dazu die allgemeine Definition an:

$\begin{eqnarray*} B_{i,n}=\binom n i t^i \cdot (1-t)^{n-i},~t\in [0,1] \end{eqnarray*}$

Durch lineare Transformation kann man die verallgemeinerten Bernsteinpolynome erklären:

$\begin{eqnarray*} B_{i,n}^{[a,b]}=\frac{1}{(b-a)^n} \cdot \binom n i (t-a)^i \cdot (b-t)^{n-i},~t\in [a,b] \end{eqnarray*}$

Applet zum Plotten
[attach]8815[/attach] [attach]8816[/attach] [attach]8817[/attach]

09.10.2008, 22:16

tigerbine

Auf diesen Beitrag antworten »

Zerlegung der Eins, Rekursionsformel, Basiswechsel
Zerlegung der Eins

Betrachtet man die obigen Bilder und addiert jeweils die Funktionswerte der Bernsteinpolyme für festes n, so erhält man immer den Wert 1. Daher spricht man auch davon, dass diese Polynome eine Zerlegung der Eins bilden.

$\begin{eqnarray*} \sum_{i=0}^n B_{i,n}(t) = \sum_{i=0}^n{n \choose i} t^i (1-t)^{n-i} = 1 ,~t \in [0,1] \end{eqnarray*}$

Dies ergibt sich aus dem binomischen Lehrsatz, denn mittels diesem kann man schreiben

$\begin{eqnarray*} \sum_{i=0}^n{n \choose i} t^i (1-t)^{n-i} = (t+(1-t))^n = 1 \end{eqnarray*}$

Rekursionsformel (Dreit-Term-Rekusion)

$\begin{eqnarray*} B_{i,n}(t) = (1-t) \cdot B_{i,n-1}(t) + t \cdot B_{i-1,n-1}(t) \end{eqnarray*}$

dabei erweitert man die Indizes wie folgt:

$\begin{eqnarray*} B_{i,n}: = 0 \text{ für } i < 0 \text{ oder } i > n \end{eqnarray*}$

$\begin{eqnarray*} B_{0,0}: = 1 \end{eqnarray*}$

D.h. aus 2 Basisvektoren des $\begin{eqnarray*} \Pi_{n-1} \end{eqnarray*}$ läßt sich ein Basisvektor des $\begin{eqnarray*} \Pi_n \end{eqnarray*}$ berechnen. Überprüfen wir dies anhand der im ersten Post aufgelisteten Basen. Dann wird auch schnell klar, warum die Indexerweiterung nötig ist. Wir wollen bis n=3 rechnen, also stocken wir den Startdatensatz entsprechend auf, um in einem Schema rechnen zu können. Notieren wir sie in einer Matrix.

$\begin{eqnarray*} \begin{pmatrix} 0 & 0 & 0 & 0 \\ B_{0,0} & B_{0,1} & B_{0,2} & B_{0,3} \\ 0 & B_{1,1} & B_{1,2} & B_{1,3} \\ 0 & 0 & B_{2,2} & B_{2,3} \\ 0 & 0 & 0 & B_{3,3} \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} B_{0,1}=(1-t) \cdot 1 + t \cdot 0 = 1-t \end{eqnarray*}$

$\begin{eqnarray*} B_{1,1}=(1-t) \cdot 0 + t \cdot t = t \end{eqnarray*}$

$\begin{eqnarray*} B_{0,2}=(1-t) \cdot (1-t) + t \cdot 0 = (1-t)^2 \end{eqnarray*}$

$\begin{eqnarray*} B_{1,2}=(1-t) t + t \cdot (1-t) = 2t(1-t) \end{eqnarray*}$

$\begin{eqnarray*} B_{2,2}=(1-t) \cdot 0 + t \cdot t = t^2 \end{eqnarray*}$

$\begin{eqnarray*} B_{0,3}=(1-t) \cdot (1-t) ^2+ t \cdot 0 = (1-t)^3 \end{eqnarray*}$

$\begin{eqnarray*} B_{1,3}=(1-t)2t(1-t) + t \cdot (1-t) ^2= 3t(1-t)^2 \end{eqnarray*}$

$\begin{eqnarray*} B_{2,3}=(1-t) \cdot t^2 + t \cdot 2t(1-t)=3t^2(1-t) \end{eqnarray*}$

$\begin{eqnarray*} B_{3,3}=(1-t) \cdot 0 + t \cdot t^2 = t^3 \end{eqnarray*}$

Die Dreitermrekursion zur Berechnung weiterer Basisvektoren findet man z.B. auch bei den Tschebyscheff-Polynomen. Im Gegensatz zu den anderen Basen - vgl. auch die Monombasis - sind hier die Schnitte der einzelnen Basen leer, haben doch die einzelnen Basispolynome den gleichen Maximalgrad n. Bestimmen wir einmal den Basiswechsel zwischen diesen Basen. Theoretische Tipps gibt es hier [Artikel] Basiswechsel.

n=1

$\begin{eqnarray*} M_1 \to B_1: \quad 1 \to 1-x,~x \to x \end{eqnarray*}$

$\begin{eqnarray*} S_1^T=\begin{pmatrix} 1 & -1 \\ 0 & 1\end{pmatrix},~S_1=\begin{pmatrix} 1 & 0 \\ -1 & 1\end{pmatrix},~T=\begin{pmatrix} 1 & 0 \\ 1 & 1\end{pmatrix} \end{eqnarray*}$

Somit gilt für die Koordinatenumrechnung des Polynoms $\begin{eqnarray*} p(x)=(1) \cdot 1+(1) \cdot x \end{eqnarray*}$

$\begin{eqnarray*} \begin{pmatrix} 1 & 0 \\ 1 & 1\end{pmatrix} \begin{pmatrix}1 \\ 1 \end{pmatrix}_M = \begin{pmatrix} 1 \\ 2 \end{pmatrix}_B \end{eqnarray*}$

$\begin{eqnarray*} p(x)=(1) \cdot (1-x) + (2) \cdot (x) \end{eqnarray*}$
n=2

$\begin{eqnarray*} M_2 \to B_2: \quad 1 \to 1-2x+x^2 ,~x \to 2x-2x^2,~x^2 \to x^2 \end{eqnarray*}$

$\begin{eqnarray*} S_1^T=\begin{pmatrix} 1 & -2 & 1 \\ 0 & 2 & -2 \\ 0 & 0 & 1\end{pmatrix},~S_1=\begin{pmatrix} 1 &0 & 0 \\ -2 & 2 & 0 \\ 1 & -2 & 1 \end{pmatrix},~T=\begin{pmatrix} 1 & 0 &0 \\ 1 & \frac{1}{2} & 0 \\ 1 & 1 & 1\end{pmatrix} \end{eqnarray*}$

Somit gilt für die Koordinatenumrechnung des Polynoms $\begin{eqnarray*} p(x)=(1) \cdot 1+(1) \cdot x + (1) \cdot x^2 \end{eqnarray*}$

$\begin{eqnarray*} \begin{pmatrix} 1 & 0 &0 \\ 1 & \frac{1}{2} & 0 \\ 0 & 1 & 1\end{pmatrix} \begin{pmatrix}1 \\ 1 \\ 1 \end{pmatrix}_M = \begin{pmatrix} 1 \\ 1.5 \\ 3\end{pmatrix}_B \end{eqnarray*}$

$\begin{eqnarray*} p(x)=(1) \cdot (1-2x+x^2) + (1.5) \cdot (2x-2x^2) + (3) \cdot x^2 \end{eqnarray*}$

Die Darstellung eines Elemtentes von $\begin{eqnarray*} \Pi_n \end{eqnarray*}$ bezüglich der Berstein-Basis nennt man Bezier-Darstellung

$\begin{eqnarray*} p_n=\sum_{i=0}^n~\beta_iB_{i,n} \end{eqnarray*}$

10.10.2008, 02:09

tigerbine

Auf diesen Beitrag antworten »

Approximation stetiger Funktionen
Im Workshop Polynominterpolation sieht man, dass dieser Ansatz - Lagrange Interpolation - im Allgemeinen nicht zur Konvergenz des interpolierenden Polynoms gegen die Funktion f führt.

Mit den Bernsteinpolynomen gelingt dies:

Zitat:

wikipadia
Für jede Funktion $\begin{eqnarray*} f: [0,1] \to \mathbb R \end{eqnarray*}$ heißt das durch $\begin{eqnarray*} B_n(f)(t) = \sum_{i=0}^n B_{i,n}(t)\cdot f\left(\frac{i}{n}\right) \end{eqnarray*}$ definierte Polynom $\begin{eqnarray*} B_n(f) \end{eqnarray*}$ das „n-te Bernsteinpolynom der Funktion f“.

Wenn f eine stetige Funktion ist, dann konvergiert die Folge der Bernsteinpolynome von f gleichmäßig gegen f.

03.11.2008, 00:53

tigerbine

Auf diesen Beitrag antworten »

CAD, Bezierkurven, NURBS
Im [WS] Spline-Interpolation - Theorie haben wir gesehen, wie man mittels B-Splines versuchen kann Funktionen zu reproduzieren. Dabei wurde die Funktion an gewissen Stellen interpoliert und der Spline s als Linearkombination der Basisvektoren angegeben.

$\begin{eqnarray*} s=\sum_{j=0}^{n+k-2}~a_j\cdot B_{j,k-1}(t),~a_j \in \mathbb R,~t \in \mathbb R \end{eqnarray*}$

Auf Seite 16 im angehängten Vortrag kann man eine weitere Verwendung dieser Darstellung sehen. Wieder summiert man die Basispolynome, "gewichtet" sie nun aber mit den Koordinaten der Eckpunkte eines Kontrollpolygons, in dem die gesuchte Freiformkurve liegen soll.

Neue Frage »

Antworten »

[Artikel] Bernstein - Polynome und CAD

Verwandte Themen