Least Squares Approximation by Legendre series

Yong-Ming 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., B-spline curves and surfaces) is a standard in most CAD systems. Unfortunately, some geometric operations on polynomial curves and surfaces may result in non-rational curves. In order to represent a non-rational curve in polynomial form, approximation method is usually required. Based on the use of Legendre series, we presented an approximation method for offsetting planar B-spline 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 B-spline 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, non-negative 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 {f0,f1,,fn}, which does not include zero function, is said to be orthogonal on [a,b] with respect to the weight function w(x) if

(fi,fj)=
b

a 
w(x) fi(x) fj(x) dx =

0,    i j
dj > 0,    i=j

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=(2x-b -a)/(b-a) such that t [-1,1]). As a polynomial representation of curves/surfaces (e.g., Bézier and B-spline 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 f0(x), f1(x),, fn(x) such that

I=
b

a 
w(x)
f(x)- n

i=0 
aifi(x)
2
 
dx
is minimized over all choices of a0,,an. This is equivalent to solving the following equations for ak:

I
ak
=2
b

a 
w(x)
f(x)- n

i=0 
aifi(x)
fk(x)dx=0,     (k=0,1,,n)
or

n

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

ak= (f,fk)
(fk,fk)
,     k=0, 1, , n.
(1)

The most well-known orthogonal polynomials are the Tchebyshev and Legendre polynomials, which are orthogonal on [-1,1] corresponding respectively to 1/[(1- x2)] 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 Qn(x) be a polynomial whose leading coefficient is 1. Then, we may express Qn(x) as Qn(x)=[`l]n (x)+k=0n-1 bk [`l]k(x). Thus,

(Qn,Qn)=
+1

-1 
Qn2(x) dx=( _
l
 

n 
, _
l
 

n 
)+ n-1

k=0 
bk2 ( _
l
 

k 
, _
l
 

k 
) ( _
l
 

n 
, _
l
 

n 
).
The equal sign holds iff b0=b1= = bn-1=0, i.e., Qn(x) [`l]n(x).

Since Legendre polynomials are orthogonal and deviates least from zero, it is ideal to choose fk to be the Legendre polynomials lk(x). Noting that (lk,lk)=[2/(2k+1)] (Hildebrand, 1987), from (1) we have:

ak= (f,lk)
(lk,lk)
= 2k+1
2

+1

-1 
lk(x)f(x) dx,     k=0,1,, n
(2)
The integrated squares error is

Rn=
1

-1 

f(x)- n

k=0 
ak lk(x)
2
 
dx =
+1

-1 
f2(x)dx- n

k=0 
2 ak2
2k+1
.
(3)
It is natural to ask whether Rn 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

En=
max
-1 x 1 

f(x) - n

k=0 
ak lk(x)
.
If En 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 En instead of Rn.

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 
aklk(x)
=


k=n+1 
aklk(x)
< e.
Since |lk(x)| 1, we have




k=n+1 
aklk(x)


k=n+1 
|ak|,
which is an easy-to-compute formula for approximation error analysis.

3  An example of using Legendre series

We look at an example: Approximating a unit semi-circle 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 vector-valued 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:

  1. Compute ak (k=0,1,, M) using the method discussed in (Li and Hsu, 1998).
  2. If P(t)=k=0M ak lk(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 semi-circle by polynomial curves.

In most CAD systems, curves are represented in either Bézier or B-spline 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 semi-circle are obtained by such basis conversion.

i xi yi
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 Variables-Harmonic 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), 711-720.
[6] Li, Y.M. and Zhang, X.Y., Basis conversion among Bézier, Tchebyshev, and Legendre, Computer Aided Geometric Design 15 (1998), 631-636.
[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