NASA/TM–2012–217557

Translation of Bernstein

Coefficients Under an Affine

Mapping of the Unit Interval

J. A. Alford II

Langley Research Center, Hampton, Virginia

March 2012
NASA STI Program . . . in Profile

Since its founding, NASA has been

dedicated to the advancement of

aeronautics and space science. The

NASA scientific and technical

information (STI) program plays a key

part in helping NASA maintain this

important role.

The NASA STI Program operates

under the auspices of the Agency Chief

Information Officer. It collects,

organizes, provides for archiving, and

disseminates NASA’s STI. The NASA

STI Program provides access to the

NASA Aeronautics and Space

Database and its public interface, the

NASA Technical Report Server, thus

providing one of the largest collection

of aeronautical and space science STI

in the world. Results are published in

both non-NASA channels and by

NASA in the NASA STI Report Series,

which includes the following report

types:

• TECHNICAL PUBLICATION.

Reports of completed research or a

major significant phase of research

that present the results of NASA

programs and include extensive data

or theoretical analysis. Includes

compilations of significant scientific

and technical data and information

deemed to be of continuing reference

value. NASA counterpart of

peer-reviewed formal professional

papers, but having less stringent

limitations on manuscript length and

extent of graphic presentations.

• TECHNICAL MEMORANDUM.

Scientific and technical findings that

are preliminary or of specialized

interest, e.g., quick release reports,

working papers, and bibliographies

that contain minimal annotation.

Does not contain extensive analysis.

• CONTRACTOR REPORT.

Scientific and technical findings by

NASA-sponsored contractors and

grantees.

• CONFERENCE PUBLICATION.

Collected papers from scientific and

technical conferences, symposia,

seminars, or other meetings

sponsored or co-sponsored by NASA.

• SPECIAL PUBLICATION.

Scientific, technical, or historical

information from NASA programs,

projects, and missions, often

concerned with subjects having

substantial public interest.

• TECHNICAL TRANSLATION.

English- language translations of

foreign scientific and technical

material pertinent to NASA’s

mission.

Specialized services also include

creating custom thesauri, building

customized databases, and organizing

and publishing research results.

For more information about the NASA

STI Program, see the following:

• Access the NASA STI program home

page at http://www.sti.nasa.gov

• E-mail your question via the Internet

to help@sti.nasa.gov

• Fax your question to the NASA STI

Help Desk at 443-757-5803

• Phone the NASA STI Help Desk at

443-757-5802

• Write to:

NASA STI Help Desk

NASA Center for AeroSpace

Information

7115 Standard Drive

Hanover, MD 21076–1320
NASA/TM–2012–217557

Translation of Bernstein

Coefficients Under an Affine

Mapping of the Unit Interval

J. A. Alford II

Langley Research Center, Hampton, Virginia

National Aeronautics and

Space Administration

Langley Research Center

Hampton, Virginia 23681-2199

March 2012
Acknowledgments

I would like to thank C ́esar Mu ̃noz and Anthony Narkowicz for introducing me to this

subject and for their encouragement.

The use of trademarks or names of manufacturers in this report is for accurate reporting and

does not constitute an offical endorsement, either expressed or implied, of such products or

manufacturers by the National Aeronautics and Space Administration.

Available from:

NASA Center for AeroSpace Information

7115 Standard Drive

Hanover, MD 21076-1320

443-757-5802
Abstract

We derive an expression connecting the coefficients of a polynomial expanded in the Bernstein basis to the coefficients of an equivalent expansion of the polynomial under an affine mapping of the domain. The

expression may be useful in the calculation of bounds for multi-variate

polynomials.

1 Introduction

The set of Bernstein basis polynomials of degree n can be used to form

a basis for a vector space of polynomials of degree less than or equal to

n. These polynomials take the form

Bν,n(x) = 

n

ν

!

x

ν

(1 − x)

n−ν

, ν = 0, . . . , n (1)

where 

n

ν

!

is a binomial coefficent. It is known that the coefficients

of a given polynomial expressed using the Bernstein basis provide guaranteed bounds on the global minimum and maximum of the polynomial [1,2]. This result extends from the fact that these basis polynomials

are non-negative over the unit interval and the values at the end points

are simply

Bν,n(0) = δν0 and Bν,n(1) = δνn (2)

where δ is the Kronecker delta function. Furthermore, such bounds may

be improved by calculating and comparing the various expansion, or

Bernstein, coefficients for the polynomial over subdivisions of the domain interval, i.e. the coefficients that result from an affine mapping of

a subdivision of the domain back to the original domain. The de Casteljau algorithm [3] is a method for calculating the Bernstein coefficients

that are generated via a repeated halving of the domain. Mu ̃noz and

Narkawicz [4] have provided a simpler variant of this algorithm, by explicitly calculating the analytical expressions that relate the coefficients

on the original and halved domains. We present here an expression connecting the Bernstein coefficients on the unit domain to those for an

affine mapping of the domain. This is in a sense a generalization of the

formulas given by Mu ̃noz and Narkawicz [4]. The formula here reduces

to their result in the special case of dividing the domain into halves. We

also show how to apply the equation to a division of the domain into any

number of intervals of equal size.

2 Derivation of the General Formula

We derive here the relationship between the coefficients of a single variable polynomial in Bernstein form on the unit interval x ∈ [0, 1] , Bν,n(x),

1
and those of the corresponding Bernstein polynomial generated by the

mapping x −→ αx+β. This result holds for the multivariate case as can

be easily shown using Smith’s representation [5]. The derivation makes

use of two results: 1) the connection between the coefficients of an expansion in Bν,n(αx) to those of an equivalent expansion in Bν,n(x) and

2) the identity

Bν,n(1 − x) = Bn−ν,n(x) (3)

The three steps shown below create the mapping x −→ αx+β. The first

result is used in the first and third steps, and the second result is used

for the second step.

x1 = α1x (4)

x2 = 1 − x1 = 1 − α1x (5)

x3 = α2x2 = α2(1 − α1x) (6)

where β = α2 6= 0 and α = −α1β. The derivation of the relationship

proceeds similarly to the procedure in Section 2.3 of Ref. [4], and begins

by determining the appropriate partition of the argument 1 − αx.

Bν,n(αx) = 

n

ν

!

α

νxν

(1 − x + (1 − α)x)

n−ν

=

 

n

ν

!

α

νxν

nX−ν

k=0

 

n − ν

k

!

(1 − α)

kxk

(1 − x)

n−ν−k

(7)

=

 

n

ν

!

α

ν Xn

k=ν

 

n − ν

k − ν

!

(1 − α)

k−νxk

(1 − x)

n−k

(8)

Using the trinomial revision formula

 

k

i

! n

k

!

=

 

n

i

! n − i

k − i

!

(9)

we have that

Bν,n(αx) = α

ν Xn

k=ν

 

k

ν

!

(1 − α)

k−νBk,n(x) (10)

Equating two equivalent expansions for the same polynomial, one in the

Bernstein basis with argument x, and one in the Bernstein basis with

argument αx, Xn

ν=0

c

α

ν,nBν,n(αx) = Xn

k=0

ck,nBk,n(x) (11)

gives the following identity involving the Bernstein coefficients c

α

ν,n and

ck,n

ck,n =

X

k

ν=0

c

α

ν,n 

k

ν

!

α

ν

(1 − α)

k−ν =

X

k

ν=0

c

α

ν,nBν,k(α) (12)

2
where the α in c

α

k,n is not an exponent but a notational superscript. Using

this result, the identity in Eq. (3), and representing now the Bernstein

coefficients of an expansion in the arguments x, x2, and x3 as bk,n, b

2

k,n,

and b

3

k,n respectively, the coefficients corresponding to Eqs. (4),(5), and

(6) have the following relationships:

Xn

ν=0

b

3

ν,nBν,n(α2x2) = Xn

k=0

b

2

k,nBk,n(x2) (13)

b

2

k,n =

X

k

ν=0

b

3

ν,nBν,k(α2) (14)

Xn

ν=0

b

2

ν,nBν,n(x2) = Xn

ν=0

b

2

ν,nBν,n(1 − x1) (15)

=

Xn

ν=0

b

2

ν,nBn−ν,n(x1) (16)

=

Xn

ν=0

b

2

n−ν,nBν,n(x1) (17)

=

Xn

k=0

bk,nBk,n(x) (18)

The coefficients in the last expression can thus be written as

bk,n =

X

k

ν=0

b

2

n−ν,nBν,k(α1)

=

X

k

ν=0

nX−ν

ν

′=0

b

3

ν

′

,nBν,k(−

α

β

)Bν

′

,n−ν(β) (19)

This equation obviously holds only for β 6= 0. When β = 0, we can

simply apply Eq. (12) instead.

3 Specific Cases

It is straightforward to compute the coefficients for the case where the

unit domain is divided into halves. This division is equivalent to the

mapping x −→ αx + β, where α = 1/2, β = 0, for the left half, and

α = −1/2, β = 1 for the right half. In the former case, we use Eq.(12)

bk,n =

X

k

ν=0

b

3

ν,nBν,k(

1

2

) = 1

2

k

X

k

ν=0 

k

ν

!

b

3

ν,n (20)

and in the latter, Eq.(19) yields

3
bk,n =

X

k

ν=0

nX−ν

ν

′=0

b

3

ν

′

,nBν,k(

1

2

)Bν

′

,n−ν(1) (21)

=

X

k

ν=0

b

3

n−ν,nBν,k(

1

2

) (22)

=

1

2

k

X

k

ν=0 

k

ν

!

b

3

n−ν,n (23)

which are the same formulas given in Eq.(14) of Ref. [4].

These equations can be used to calculate the Bernstein coefficients

corresponding to domains that are created by repeated halving of the

unit domain. Alternatively, we may from the outset define a linear division of the domain into M equal size windows by simply setting

α = −1/M, β = m/M, m = 1, . . . , M (24)

Such a scheme allows one to repeatedly divide the unit domain into

smaller pieces faster and perhaps in a non-even fashion if one so chooses.

4 Conclusions

We have derived an expression relating the Bernstein coefficients of a

polynomial on the unit domain x ∈ [0, 1] to those for the mapped domain x −→ αx + β. The expression provides a generalization of the

method implemented by Mu ̃noz and Narkawicz [4]. The full implications of this work are still being determined; for example, one may study

the aforementioned linear division of the domain in the limit of infinitely

small divisions, M → ∞.

References

1. G. Lorentz, Bernstein Polynomials, Chelsea Publishing Company,

New York N.Y., Second Edition (1986)

2. J. Garloff, Application of Bernstein Expansion to the Solution of

Control Problems, Reliable Computing 6, 303-320 (2000)

3. J. Garloff, The Bernstein Algorithm, Interval Computations 4, 154-

168 (1993)

4. C. Mu ̃noz and A. Narkawicz, Formalization of an Efficient Representation of Bernstein Polynomials and Applications to Global Optimization, submitted to Journal of Automated Reasoning (2011)

5. A. P. Smith, Fast Construction of Constant Bound Functions for

Sparse Polynomials, J. of Global Optimization 43, 445-458 (2009)

4

REPORT DOCUMENTATION PAGE Form Approved

OMB No. 0704–0188

The public reporting burden for this collection of information is estimated to average 1 hour per response, including the time for reviewing instructions, searching existing data sources,

gathering and maintaining the data needed, and completing and reviewing the collection of information. Send comments regarding this burden estimate or any other aspect of this collection

of information, including suggestions for reducing this burden, to Department of Defense, Washington Headquarters Services, Directorate for Information Operations and Reports

(0704-0188), 1215 Jefferson Davis Highway, Suite 1204, Arlington, VA 22202-4302. Respondents should be aware that notwithstanding any other provision of law, no person shall be

subject to any penalty for failing to comply with a collection of information if it does not display a currently valid OMB control number.

PLEASE DO NOT RETURN YOUR FORM TO THE ABOVE ADDRESS.

Standard Form 298 (Rev. 8/98)

Prescribed by ANSI Std. Z39.18

1. REPORT DATE (DD-MM-YYYY)

01-03-2012

2. REPORT TYPE

Technical Memorandum

3. DATES COVERED (From - To)

12/2011–03/2012

4. TITLE AND SUBTITLE

Translation of Bernstein Coefficients Under an Affine Mapping of the Unit

Interval

5a. CONTRACT NUMBER

5b. GRANT NUMBER

5c. PROGRAM ELEMENT NUMBER

5d. PROJECT NUMBER

5e. TASK NUMBER

5f. WORK UNIT NUMBER

031102.02.07.05.9D65.12

6. AUTHOR(S)

J. A. Alford II

7. PERFORMING ORGANIZATION NAME(S) AND ADDRESS(ES)

NASA Langley Research Center

Hampton, Virginia 23681-2199

8. PERFORMING ORGANIZATION

REPORT NUMBER

L–20124

9. SPONSORING/MONITORING AGENCY NAME(S) AND ADDRESS(ES)

National Aeronautics and Space Administration

Washington, DC 20546-0001

10. SPONSOR/MONITOR’S ACRONYM(S)

NASA

11. SPONSOR/MONITOR’S REPORT

NUMBER(S)

NASA/TM–2012–217557

12. DISTRIBUTION/AVAILABILITY STATEMENT

Unclassified-Unlimited

Subject Category 64

Availability: NASA CASI (443) 757-5802

13. SUPPLEMENTARY NOTES

An electronic version can be found at http://ntrs.nasa.gov.

14. ABSTRACT

We derive an expression connecting the coefficients of a polynomial expanded in the Bernstein basis to the coefficients of an

equivalent expansion of the polynomial under an affine mapping of the domain. The expression may be useful in the

calculation of bounds for multi-variate polynomials.

15. SUBJECT TERMS

Bernstein Polynomials, Global Optimization, Polynomial Bounds, LFM

16. SECURITY CLASSIFICATION OF:

a. REPORT

U

b. ABSTRACT

U

c. THIS PAGE

U

17. LIMITATION OF

ABSTRACT

UU

18. NUMBER

OF

PAGES

12

19a. NAME OF RESPONSIBLE PERSON

STI Help Desk (email: help@sti.nasa.gov)

19b. TELEPHONE NUMBER (Include area code)

(443) 757-5802