1. Introduction
Finding the min-max, or best
, polynomial approximation to a function, in some standard interval, is of the greatest interest in numerical analysis [1] [2] . For a polynomial function the least error distribution is a Chebyshev polynomial [3] [4] [5] .
The usual procedure [6] [7] to find the best
approximation to a general function is to start with a good approximation, say in the
sense, easily obtained by the minimization of a quadratic functional for the coefficients, then iteratively improving this initial approximation by a Remez-like correction procedure [8] [9] that strives to produce an error distribution that oscillates with a constant amplitude in the interval of interest.
In this note, we bring ample and varied computational evidence in support of the novel, worthy of notice, empirical numerical observation that taking the error distribution of a least squares,
, best polynomial fit to a function, squared, as weight in a second, weighted, least squares approximation, results in an error distribution that is remarkably close to the best
, or uniform, approximation.
2. Fixing Ideas; The Best Quadratic in [−1, 1]
The monic Chebyshev polynomial
(1)
is the solution of the min-max problem
(2)
This min-max solution, the least function in the
sense, is a polynomial that has two distinct roots, and oscillates with a constant amplitude in
Indeed, say
is such a polynomial, and
is another quadratic polynomial, then
in the interval, for otherwise
and
would intersect at two points, which is absurd;
is either an identity, or has but the one solution
.
Thus, the monic Chebyshev polynomial of degree n is the least, uniform, or pointwise, error distribution in approximating
by a polynomial of degree
.
To obtain a least squares, a best
, approximation to
we first minimize
(3)
to have the value
.
Minimizing next
, under the weight
#Math_28# (4)
now with respect to p, we obtain
, which is surprisingly much closer to the optimal value of one half.
We may replace the difficult
measure by the computationally easier
measure with an even
. Let a0 be a good approximation, and
be an improved one. Minimization cum linearization produces the equation
(5)
where
is odd.
Starting with
, we obtain from the above equation, for
, the value
, as compared with the optimal
.
3. Optimal Cubic in [−1, 1]
Seeking to reproduce the optimal monic Chebyshev polynomial of degree three
(6)
we start by minimizing
(7)
and have
.
Then we return to minimize the weighted
with respect to
(8)
and obtain
, which is considerably closer to the optimal value of 0.75. See Figure 1.
We are ready now for a Remez-like correction to bring the error function closer to optimal. The minimum of
occurs at m = 0.50687. We write a new tentative
and request that
, by which we have
(9)
as compared with the Chebyshev optimal value of
.
4. Optimal Quartic in [0, 1]
Starting with
(10)
we minimize
(11)
and obtain the best, in the
sense,
shown in Figure 2.
Then we return to minimize
(12)
weighted by the previous
squared, and obtain the new, nearly perfectly uniform
of Figure 3.
By comparison, the amplitude of the monic Chebyshev polynomial of degree four in [0,1] is 1/128 = 0.0078125.
Figure 1. (a) Least squares cubic. (b) Weighted least squares cubic.
Figure 3. Weighted least squares quartic.
5. Best Cubic Approximation of ex in [0, 1]
To facilitate the integrations we use the approximation
(13)
and minimize
(14)
with respect to
. The best
obtained from this minimization is shown in Figure 4.
Then we use the square of the minimal
just obtained, as weight in the next minimization of
(15)
with respect to
.
The nearly perfect result of this last minimization is shown in Figure 5.
6. Best Cubic Approximation of sinx in [0, 1]
To facilitate the integrations we take
(16)
and obtain the least squares error distribution as in Figure 6.
The subsequent nearly perfect weighted least squares error distribution is shown in Figure 7.
Figure 4. Least squares cubic fit to ex.
Figure 5. Weighted least squares cubic fit to ex.
Figure 6. Least squares cubic fit to sinx.
Figure 7. Weighted least squares cubic fit to sinx.
7. Best Quadratic Fit to
in [0, 1]
We start with
(17)
under the condition
(18)
and minimize
(19)
with respect to
and
, to have
(20)
shown as curve a in Figure 8.
Next we minimize
Figure 8. (a) Least squares quadratic fit to
. (b) Weighted least squares quadratic fit to
.
(21)
and obtain
(22)
shown as graph b in Figure 8, as compared with the optimal, in the
sense
(23)
8. Best Cubic Fit to x1/4 in [0, 1]
We start with
(24)
under the restriction
, or
, and minimize
(25)
with respect to
to have the minimal
shown in Figure 9.
Then we minimize
(26)
and obtain the nearly optimal error distribution as in Figure 10.
9. Another Difficult Function
We now look at the error distribution
(27)
under the condition that
, or
Least squares minimization of
yields the error distribution in Figure 11.
Next we minimize
#Math_100# (28)
Figure 9. Least squares cubic fit to
.
Figure 10. Weighted least squares cubic fit to
.
Figure 11. Least squares cubic fit to
.
Figure 12. Weighted least squares cubic fit to
.
under the restriction that
, and obtain the nearly perfect error distribution shown in Figure 12.
10. Conclusion
We experimentally demonstrate, on a variety of continuous, analytic and nonanalytic functions, the remarkable observation that if the least squares polynomial approximation is taken as weight in a repeated, now weighted, least squares approximation, then this new, second, approximation is nearly perfect in the sense of Chebyshev, barely needing any further correction procedure.