next up previous contents index
Next: 1.3.4 Definition of Bézier Up: 1.3 Bézier curves and Previous: 1.3.2 Arithmetic operations of   Contents   Index


1.3.3 Numerical condition of polynomials in Bernstein form

Polynomials in the Bernstein basis have better numerical stability under perturbation of their coefficients than in the power basis. We will introduce the concept of condition numbers for polynomial roots investigated by Farouki and Rajan [105].

Let us consider a polynomial $ f(t)$ in the basis $ \phi_i(t)$ with coefficients $ f_i$ :

$\displaystyle f(t)=\sum_{i=0}^n f_i \phi_i(t)\;.$     (1.29)

If we perturb a single coefficient $ f_j$ by $ \delta f_j$ , we have
$\displaystyle {\tilde f}(t)=f_0\phi_0(t) + f_1\phi_1(t) + \ldots + (f_j + \delta f_j)\phi_j(t) + \ldots + f_n\phi_n(t)\;,$     (1.30)

or using (1.29)
$\displaystyle {\tilde f}(t) = f(t) + \delta f_j\phi_j(t)\;.$     (1.31)

If $ t+ \delta t$ is a root of the perturbed polynomial $ {\tilde f}(t)$ , then
$\displaystyle {\tilde f}(t+ \delta t) = f(t+ \delta t) + \delta f_j\phi_j(t+ \delta t) =0\;,$     (1.32)

or
$\displaystyle f(t+ \delta t) =- \delta f_j\phi_j(t+ \delta t)\;.$     (1.33)

Now let us Taylor expand (1.33) about $ t_0$ , where $ t_0$ is a root of $ f(t)$ , i.e. $ f(t_0)=0$ ,

$\displaystyle \sum_{i=1}^n \frac{(\delta t)^i}{i!}\frac{d^if}{dt^i}(t_0)=-\delta f_j \sum_{i=0}^{n} \frac{(\delta t)^i}{i!} \frac{d^i\phi_j}{dt^i}(t_0)\;.$     (1.34)

If $ t_0$ is a simple root of $ f(t)$ , then $ \dot{f}(t_0)\neq 0$ , and in the limit of infinitesimal perturbations the above equation gives:
$\displaystyle \lim_{\delta f_j \rightarrow 0} \frac{\delta t}{\frac{\delta f_j}{f_j}} = -\frac{f_j \phi_j(t_o)}{\dot{f}(t_0)}\;.$     (1.35)

The absolute value of the right hand side of the above equation
$\displaystyle C=\vert f_j \phi_j(t_o)/\dot{f}(t_0)\vert\;,$     (1.36)

is called the condition number of the root $ t_0$ with respect to the single coefficient $ f_j$ . For perturbations in each coefficient, $ f_j$ , $ j=0,1,\ldots,n$ , the condition number of the root $ t_0$ becomes:
$\displaystyle C=\frac{\sum_{j=0}^{n}\vert f_j \phi_j(t_o)\vert}{\vert\dot{f}(t_0)\vert}\;.$     (1.37)

If $ t_0$ is an $ m$ -fold root, $ m\geq 2$ , then a multiple-root condition number $ C^{(m)}$ for perturbations in each coefficient $ f_j$ , $ j=0,1,\ldots,n$ is defined as

$\displaystyle C^{(m)}=\left(\frac{m!}{\vert\frac{d^mf(t_0)}{dt^m}\vert}\sum_{j=0}^n \vert f_j \phi_j(t_0)\vert\right)^{1/m}\;.$     (1.38)

The following theorem is due to Farouki and Rajan [105].

Theorem 1.3.1. For an arbitrary polynomial $ f(t)$ with a simple root $ t_0 \in [0, 1]$ , let $ C_p(t_0)$ and $ C_b(t_0)$ denote the condition numbers (1.37) of the root in the power and Bernstein bases on $ [0, 1]$ , respectively. Then $ C_b(t_0) \leq C_p(t_0)$ for all $ t_0 \in [0, 1]$ . In particular $ C_b(0)=C_p(0)=0$ , while for $ t_0 \in (0, 1]$ we have the strict inequality $ C_b(t_0) < C_p(t_0)$ .


Table 1.3: Condition numbers for Wilkinson polynomial (adapted from [105])

$ i$ 		$ C_p(x_0)$ $ C_b(x_0)$

1		 $ 2.100 \times 10^1$ $ 3.413 \times 10^0 $

2		 $ 4.389 \times 10^3$ $ 1.453 \times 10^2 $

3		 $ 3.028 \times 10^5$ $ 2.335 \times 10^3 $

4		 $ 1.030 \times 10^7$ $ 2.030 \times 10^4 $

5		 $ 2.059 \times 10^8$ $ 1.111 \times 10^5 $

6		 $ 2.667 \times 10^9$ $ 4.153 \times 10^5 $

7		 $ 2.409 \times 10^{10}$ $ 1.115 \times 10^6 $

8		 $ 1.566 \times 10^{11}$ $ 2.215 \times 10^6 $

9		 $ 7.570 \times 10^{11}$ $ 3.321 \times 10^6 $

10		 $ 2.775 \times 10^{12}$ $ 3.797 \times 10^6 $

11		 $ 7.822 \times 10^{12}$ $ 3.321 \times 10^6 $

12		 $ 1.707 \times 10^{13}$ $ 2.215 \times 10^6 $

13		 $ 2.888 \times 10^{13}$ $ 1.115 \times 10^6 $

14		 $ 3.777 \times 10^{13}$ $ 4.153 \times 10^5 $

15		 $ 3.777 \times 10^{13}$ $ 1.111 \times 10^5 $

16		 $ 2.833 \times 10^{13}$ $ 2.030 \times 10^4 $

17		 $ 1.541 \times 10^{13}$ $ 2.335 \times 10^3 $

18		 $ 5.742 \times 10^{12}$ $ 1.453 \times 10^2 $

19		 $ 1.310 \times 10^{12}$ $ 3.413 \times 10^0 $

20		 $ 1.378 \times 10^{11}$ $ 0 $

As an illustration of the above theorem, let us consider Wilkinson's polynomial in which twenty real roots are equally distributed on $ [0, 1]$ :

$\displaystyle f(t)=\prod_{i=1}^{20}(t-i/20)\;.$     (1.39)

The condition numbers for each root with respect to a perturbation in the single coefficient of $ t^{19}$ are shown in Table 1.3 [105]. We can clearly observe that the condition numbers of the root in the Bernstein basis are several orders of magnitude smaller than in the power basis. This serves to illustrate the attractiveness of using the Bernstein basis in computations in CAD/CAM systems. Although not a panacea, Bernstein basis when used properly in a floating point environment increases reliability of computations (see also detailed discussions in Chaps. 4 and 5).

next up previous contents index
Next: 1.3.4 Definition of Bézier Up: 1.3 Bézier curves and Previous: 1.3.2 Arithmetic operations of   Contents   Index
December 2009