Minmax Polynomial, Min-max Approximation

MIN-MAX POLYNOMIAL MATH 174 – Numerical Analysis I

INTRODUCTION The goal of Min-Max Approximation is to find an approximating polynomial, called Min-Max Polynomial, that has the smallest maximum absolute error from the true function.  Min-Max Polynomials are hard to find, but they can be approximated by the Chebyshev Polynomials of the first kind. (Min-Max Approximation is also called Chebyshev Approximation)  Comparing the computational expense, it is more practical to use Min-Max Polynomials than to use Taylor Series. 

PROPERTIES OF MIN-MAX POLYNOMIALS 



Existence and Uniqueness Property – there exists a unique Min-Max Polynomial that can approximate any function. Equal-Error Property – given the Min-Max Polynomial P(x) that approximates Y(x), P(x)–Y(x) takes the extreme values of size E, with alternating signs, at least n+2 times. (E is the maximum error)

*The equal-error property is the identifying feature of a min-max polynomial.

THE EXCHANGE METHOD 





This is an algorithm for finding the Min-Max Polynomial through its equal-error property. However, producing a Min-Max Polynomial (a polynomial with equal-error behavior) is not usually within reach, so exchange method can be used just to obtain a polynomial with an acceptable closeness to the Min-Max polynomial. Theoretically, the method assures convergence to the Min-Max Polynomial.

DISCRETE CASE 

The Min-Max Line (also called Equal-Error or Chebyshev line): 

Given any three points (xi,yi) and xi is distinct (i=1,2,3): 

The line must pass through (x1, y1+h1), (x2, y2+h2) and (x3, y3+h3); where h1=h, h2= –h and h3=h. This shows the equal-error property, which is missing all three points by equal amounts with alternating signs.

DISCRETE CASE 

Other Formulas: • B1= x3–x2 , B2= x3–x1 , B3= x2–x1 • h= –(B1y1–B2y2+B3y3)/(B1+B2+B3)



Example 1: Find the equal error line for the data points (0,0), (1,0) and (2,1). Solution: B1=2–1=1 B2=2–0=2 B3=1–0=1 h= –[1(0) –2(0)+1(1)]/[1+2+1]= –1/4

DISCRETE CASE 

Continuation of Example 1: Therefore the line passes through (0,–1/4), (1,1/4) and (2,3/4). By point-slope formula using any two of the points, the equation of the line is P(x) = (1/2)x –1/4.

DISCRETE CASE 

Example 2: The Exchange Method Find the equal error line for the following points: (0,0), (1,0), (2,1), (6,2), (7,3). Step 1. Select an initial triple and find the Chebyshev line for this triple. Let’s choose (0,0), (1,0) and (2,1); and from Example 1, the Chebyshev line is P(x) = (1/2)x – 1/4, where h= –1/4. Step 2: Compute the errors at all data points. Call the absolute value of the largest of these errors as H. If the absolute value of h=H, then the search is over, else go to Step 4.

DISCRETE CASE Continuation of Example 2: The errors at all five data points are –1/4, 1/4, –1/4, 3/4, 1/4, respectively. This makes H=3/4, which is not equal to the absolute value of h=1/4. Step 4: Exchange step: Choose a new triple by adding to the old triple a data point at which H occurs. Then disregard one of the former points, in such a way that the remaining three have errors of alternating sign. The new triple is (1,0), (2,1) and (6,2). By doing Step 1 to 3 again, we will find out that the three points will lead us to the min-max line of the entire data set which is P(x)=(2/5)x – (1/10). 

DISCRETE CASE 



The Min-Max Parabola  The algorithm will start by choosing an initial quadruple.  The equal error parabola of the quadruple is P(x)=a+bx+cx2, where P(xi)–y(xi)=+h.  The same Steps 1-4 of the exchange method will be followed in obtaining the Min-Max Parabola of the entire given data set. Example 3: Find the min-max parabola for (-2,2), (-1,1), (0,0), (1,1) and (2,2).

DISCRETE CASE 

Continuation of Example 3: Solution: Let’s choose (-2,2), (-1,1), (0,0) and (1,1). P(xi) –y(xi)=+h will result to the following systems of equation: (a–2b+4c)–2 = h (a–b+c)–1 = –h a–0=h (a+b+c)–1 = –h Then solve for a, b, c and h. Then do the Exchange Method.

DISCRETE CASE 

Continuation of Example 3: We will find out that the min-max parabola would be P(x)=(1/4)+(1/2)x2 , where the maximum error on our quadruple (or the absolute value of h) = 1/4, and the maximum error on the entire set (or H) = 1/4 also.

CONTINUOUS CASE Chebyshev Polynomials, when truncated, often yield approximations having almost equal-error behavior (or almost min-max).  The first four Chebyshev Polynomials are:  T0(x) = 1  T1(x) = x  T2(x) = 2x2–1  T3(x) = 4x3–3x  Its recurrence relation can be written as  TN(x)=2xTN–1(x) –TN–2(x), for N=2,3,…  Note that the coefficient of xN in TN(x) is 2N–1 when N>1. 

CONTINUOUS CASE 

Trigonometric Representation on [-1,1] TN+1(x)+TN–1(x) =2xTN(x) cos(N+1)θ+cos(N–1)θ=2cosθcosNθ , θ=arccos(x)  Because of the relation TN(x)=cosNθ, it is apparent that the Chebyshev polynomial have a succession of maximums and minimums of alternating signs, each of magnitude 1, N+1 times on the interval [-1,1].

CONTINUOUS CASE 

On the interval [-1,1], the minimum value of the error bound of the Lagrange Interpolation is achieved when the nodes are the Chebyshev abscissas/nodes.

CONTINUOUS CASE For [-1,1], Chebyshev abscissas (zeros of TN(x)) are:

Lagrange Interpolation using Chebyshev abscissas: There are possibilities that the maximum of the error term grows as N→∞ when using equally-spaced nodes (Runge Phenomenon). Because of this, wild and large oscillations may occur. The use of Chebyshev nodes will solve this phenomenon – the error term will go to zero as N→∞.

CONTINUOUS CASE Exercise: Try to compare the maximum absolute errors of the Lagrange Interpolation for f(x)=ex when the following nodes were used: a. equally-spaced: -1, -1/3, 1/3, 1 b. Chebyshev nodes on [-1,1] where N=4 Maximum Absolute Error on [-1,1]: max│ex–P(x)│, -1<x<1, where P(x) is the Lagrange Interpolating Polynomial

CONTINUOUS CASE Transforming the Interval [a,b] to [-1,1] The interpolating nodes on [a,b] are obtained using:

xk

b a tk 2

where tk

a b 2

cos ( 2 N 1 2k )

for k=0,1,…,N

CONTINUOUS CASE LAGRANGE-CHEBYSHEV APPROXIMATION POLYNOMIAL

Assume that PN(x) is the Lagrange polynomial that is based on the Chebyshev nodes given in the previous slide, If f belongs to CN+1[a,b], then N 1

f ( x ) PN ( x )

2( b a ) ( N 1) max{ f (x) } N 1 4 ( N 1 )! a x b

Example: For f(x)=sin(x) on [0,π/4], find the Chebyshev nodes and the error bound for the Lagrange Polynomial P5(x). ( 11 2k ) xk cos k 12

sin( x ) P5 ( x )

0.00000720

CONTINUOUS CASE A direct approach (with the use of the Orthogonal Property of Chebyshev Polynomials): The Chebyshev approximation polynomial PN(x) of degree
CONTINUOUS CASE Exercise: Find the Chebyshev polynomial P3(x) that approximates the function f(x)=ex over [-1,1]. You should get P3(x) =0.99461532+0.99893324x+0.54290072x2+0.17517568x3 as your answer.

-END-