Least Squares Approximation by Legendre series
YongMing Li
Unigraphics Solutions, Huntsville, Alabama, USA
Abstract
In this communication, we are concerned with least squares approximation to a given function
using Legendre orthogonal polynomials.
1 Introduction
Polynomial representation of curves and surfaces (e.g., Bspline curves and surfaces) is a
standard in most CAD systems. Unfortunately, some geometric operations on polynomial curves
and surfaces may result in nonrational curves. In order to represent a nonrational curve
in polynomial form, approximation method is usually required. Based on the use of Legendre
series, we presented an approximation method for offsetting planar Bspline curves at the
5th SIAM Conference On Geometric Design (Li and Hsu, 1998). Since then, we have been
asked why our algorithm outperforms other known approximation methods in terms of stability,
the number of control points, and efficiency. The answer lies on the fact that the Legendre
series derived from an analytic function f on [1, 1] converges
absolutely and uniformly to f and its derivatives (Li and Hsu, 1998) so that
the series can be truncated and represented as a Bspline curve. The answer lies also on the
fact that the truncated Legendre series is the least squares approximation to f among all
polynomials of the same degree or less, which is the topic of this communication. Although
least squares approximation by orthogonal polynomials is covered in many numerical analysis
books, the convergence of the Legendre series to f in both the least squares and uniform sense
seems, to the best of our knowledge, not addressed explicitly. Therefore, we would like to
discuss it here.
2 Least squares approximation
We shall need the following definitions.
Definition 1
Let w(x) be a weight function that is integrable, nonnegative and not identically zero on a
given interval [a,b]. We define the inner product of f, g Î C[a,b] as
(f,g)= 
ó õ

b
a

w(x) f(x) g(x) dx. 

Definition 2
A set of factions {f_{0},f_{1},¼,f_{n}}, which does not include zero function, is said to be orthogonal on [a,b] with
respect to the weight function w(x) if
(f_{i},f_{j})= 
ó õ

b
a

w(x) f_{i}(x) f_{j}(x) dx = 
ì í
î

 

We now consider the problem of finding least squares approximations to a continuous function
f on a normalized interval [1, 1] (If f is defined in an
arbitrary interval [a,b], we can reparametrize f(x) by t=(2xb
a)/(ba) such that t
Î [1,1]). As a polynomial representation
of curves/surfaces (e.g., Bézier and Bspline curves and surfaces) is a standard for most
CAD systems, least squares approximations in CAGD applications are usually to seek a linear
combination of polynomial functions f_{0}(x),
f_{1}(x),¼,
f_{n}(x) such that
I= 
ó õ

b
a

w(x) 
é ë

f(x) 
n å
i=0

a_{i}f_{i}(x) 
ù û

2

dx 

is minimized over all choices of a_{0},¼,a_{n}. This is equivalent to solving the following equations for a_{k}:

¶I ¶a_{k}

=2 
ó õ

b
a

w(x) 
é ë

f(x) 
n å
i=0

a_{i}f_{i}(x) 
ù û

f_{k}(x)dx=0, (k=0,1,¼,n) 

or

n å
i=0

(f_{k},f_{i})a_{i}=(f,f_{k}) (k=0,1,¼,n) 

which is a system of linear equations. The simplest form of f_{i} is the monomials {1,x,¼,x^{n}}. However, unless n is quite small, the system of linear equations derived from monomials is illconditioned and hence difficult to calculate an accurate solution. Such numerical problem can be avoided if f_{i} are chosen to be orthogonal polynomials on [1, 1]. For f_{i} being orthogonal, we have (f_{k},f_{i})=0 if i ¹ k. Therefore, a_{k} are given by
a_{k}= 
(f,f_{k}) (f_{k},f_{k})

, k=0, 1, ¼, n. 
 (1) 
The most wellknown orthogonal polynomials are the Tchebyshev and Legendre polynomials,
which are orthogonal on [1,1] corresponding respectively to 1/Ö[(1
x^{2})] and 1. Let [`l]_{k}(x) denote
the Legendre polynomial of degree k whose leading coefficient is
normalized to 1. Then, we have the following lemma.
Lemma 1
Of all polynomials of degree n with unit leading coefficients, the Legendre polynomial
[`l]_{n}(x) deviates least from zero on
[1,1] in the mean square sense.
Proof: Let Q_{n}(x) be a polynomial whose leading coefficient is 1. Then,
we may express Q_{n}(x) as Q_{n}(x)=[`l]_{n}
(x)+å_{k=0}^{n1}
b_{k} [`l]_{k}(x). Thus,
(Q_{n},Q_{n})= 
ó õ

+1
1

Q_{n}^{2}(x) dx=( 
_ l

n

, 
_ l

n

)+ 
n1 å
k=0

b_{k}^{2} ( 
_ l

k

, 
_ l

k

) ³ ( 
_ l

n

, 
_ l

n

). 

The equal sign holds iff b_{0}=b_{1}=¼ = b_{n1}=0, i.e.,
Q_{n}(x) º [`l]_{n}(x).
¨
Since Legendre polynomials are orthogonal and deviates least from zero, it is ideal to choose
f_{k} to be the Legendre polynomials l_{k}(x).
Noting that (l_{k},l_{k})=[2/(2k+1)] (Hildebrand, 1987), from (1) we have:
a_{k}= 
(f,l_{k}) (l_{k},l_{k})

= 
2k+1 2


ó õ

+1
1

l_{k}(x)f(x) dx, k=0,1,¼, n 
 (2) 
The integrated squares error is
R_{n}= 
ó õ

1
1


æ è

f(x) 
n å
k=0

a_{k} l_{k}(x) 
ö ø

2

dx = 
ó õ

+1
1

f^{2}(x)dx 
n å
k=0


2 a_{k}^{2} 2k+1

. 
 (3) 
It is natural to ask whether R_{n}® 0 as n®¥ (If so, the series converges in the least squares sense to f). Due to the difficulty of
integration, it is of little interest in practice to analyze the approximation error based
on equation (3). We thus turn our attention to the behavior of the sequence
E_{n}= 
max
1 £ x £ 1


ê ê

f(x)  
n å
k=0

a_{k} l_{k}(x) 
ê ê

. 

If E_{n}® 0 as n®¥, we say the series converges uniformly to f on [1,1]. Since uniform convergence implies convergence in the least squares sense (the converse
is not true), it is hence of interest to study E_{n} instead of R_{n}.
If f is analytic on [1,1], the Legendre series whose
coefficients are derived from (2) converges absolutely and uniformly to f
(Davis, 1975; Li and Hsu, 1998). In other words, given an arbitrarily small
number e > 0, there always exists M such that when n > M we have

ê ê

f(x) 
n å
k=0

a_{k}l_{k}(x) 
ê ê

= 
ê ê

¥ å
k=n+1

a_{k}l_{k}(x) 
ê ê

< e. 

Since l_{k}(x) £ 1, we have

ê ê

¥ å
k=n+1

a_{k}l_{k}(x) 
ê ê

£ 
¥ å
k=n+1

a_{k}, 

which is an easytocompute formula for approximation error analysis.
3 An example of using Legendre series
We look at an example: Approximating a unit semicircle r(q)=(cosq, sinq) with q Î [0,p] by a finite Legendre series P(t) with t Î [1,1] such that P(t)1 < e for every t
Î [1,1].
Since r(q) is analytic on [0,p] (Flanigan, 1988), it can thus be represented by a vectorvalued Legendre series. Given any
distance tolerance e > 0, we may truncate the Legendre series
so as to obtain a finite Legendre series which is obviously a polynomial curve. The procedures
are given below:
 Compute a_{k} (k=0,1,¼, M) using the method discussed in (Li and Hsu, 1998).
 If P(t)=å_{k=0}^{M} a_{k} l_{k}(t) can be truncated further
with respect to the given e, return the truncated polynomial curve.
Otherwise, halve the original curve r(q) and repeat the
above processes for each halved segment.
We tested our algorithm with respect to e equals 10^{3},10^{4}, 10^{5}, and 10^{10}. The degree of a resulting polynomial curve and the
maximum deviation D obtained by sampling 200 points are given in
table 2. Our approximation accuracy is several orders of magnitude better than that reported
in (Sederberg and Kakimoto, 1991). Recently, a quintic polynomial approximation to a circular
arc is reported in (Fang, 1998). Although Fang's method yields the same accuracy as ours for
a quintic polynomial, it has no flexibility to reach higher approximation accuracy.
e  degree of curve  D 
10^{3}  5  4.205×10^{
4} 
10^{4}  6  1.39×10^{
4} 
10^{5}  7  4.717×10^{
6} 
10^{10}  12  2.543×10^{
11} 

Table 1: Approximating a unit semicircle by polynomial curves. 
In most CAD systems, curves are represented in either Bézier or Bspline form. Although
polynomial basis conversion is simply a linear transformation, an efficient and numerically
stable conversion method between Legendre and Bézier is proposed in (Li and Zhang, 1998).
In table 2, the control points of a quintic Bézier curve that approximates a unit
semicircle are obtained by such basis conversion.
i  x_{i}  y_{i} 
0  +1.000160759692603  1.313455897813134×10^{
3} 
1  +9.983709328571073×10^{1}  6.186999653679961×10^{1} 
2  +5.150628289220347×10^{1}  1.289845895836934 
3  5.150628289220347×10^{1}  1.289845895836934 
4  9.983709328571073×10^{1}  6.186999653679961×10^{1} 
5  1.000160759692603  1.313455897813134×10^{3} 

Table 2: Control points of a quintic Bézier curve. 
References
 [1] Davis, P.J., Interpolation & Approximation (Dover Pub., Inc., 1975).
 [2] Fang, L., Circular arcs approximation by quintic polynomial curves,
Computer Aided Geometric Design 15 (1998).
 [3] Flanigan, F.J., Complex VariablesHarmonic and Analytic Functions (Dover Pub., Inc., 1988)
 [4] Hildebrand, F.B. Introduction to Numerical Analysis (Dover Pub., Inc., 1987).
 [5] Li, Y.M. and Hsu, V.Y., Curve offsetting based on Legendre series, Computer Aided Geometric Design 15 (1998), 711720.
 [6] Li, Y.M. and Zhang, X.Y., Basis conversion among Bézier, Tchebyshev, and Legendre, Computer Aided Geometric Design 15 (1998), 631636.
 [7] Sederberg, T.W. and Kakimoto, M., Approximating rational curves using polynomial curves, in G. Farin eds. NURBS for Curve and Surface Design (SIAM, 1991).
RETURN