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 in the basis with coefficients :

If we perturb a single coefficient by , we have

or using (1.29)

If is a root of the perturbed polynomial , then

or

Now let us Taylor expand (1.33) about , where is a root of , i.e. ,

If is a simple root of , then , and in the limit of infinitesimal perturbations the above equation gives:

The absolute value of the right hand side of the above equation

is called the condition number of the root with respect to the single coefficient . For perturbations in each coefficient, , , the condition number of the root becomes:

If is an -fold root, , then a multiple-root condition number for perturbations in each coefficient , is defined as

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

Theorem 1.3.1. For an arbitrary polynomial with a simple root , let and denote the condition numbers (1.37) of the root in the power and Bernstein bases on , respectively. Then for all . In particular , while for we have the strict inequality .

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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

The condition numbers for each root with respect to a perturbation in the single coefficient of 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).