🚀 go-pugleaf

In article <l7a5e0INNkog@almaak.usc.edu> ajayshah@almaak.usc.edu (Ajay Shah) writes:
>I'm trying to use orthogonal polynomials to approximate the value
>function of a dynamic programming problem.  I am having problems
>choosing the right polynomial.
>
>I'm trying to approximate a function f(x), and x generally takes
>values from roughly -10 to +200.  But the theory of this problem says
>that x is unbounded in the +ve direction.
>
>I plan to evaluate the fourier coefficients of the approximation rule
>using quadrature, so if I use N points in the rule, that gives me the
>N values of x at which I need to evaluate f(x).
>
>1. It still seems like black magic to me that out of N values of f(x),
>I am getting a approximation rule which claims to know f(x)
>everywhere.  What are the caveats of such a claim?

The approximation rule does not "know" the function everywhere.  It
merely interpolates the function between the N values of f(x).  You
may be referring to the well-known result that quadrature rules based
on certain classes of orthogonal polynomials can INTEGRATE a certain
degree polynomial EXACTLY.  If your function magically happens to be
truly a polynomial of that order then the quadrature rule will
integrate your function exactly.  Since you are merely choosing to
approximate your unknown function as a polynomial, it is unlikely that
this result will hold for your function exactly.  It will hold for the
approximating polynomial.

This result seems counterintuitive, but the weights are chosen in such
a way to guarantee this property.

>2. What weight function and orthogonal polynomial should I use?  The
>approximation theory says that the error of the truncated summation is
>minimised in a least squares sense with respect to the weight
>function.  Because I may never need to calculate f(x) for x outside
>[-10, 200], is it theoretically correct to just use a Legendre
>polynomial or a Chebyshev polynomial, using a simple scaling to
>convert [-1, 1] into [-10, 200]?

Selection of the weight function is usually made on the basis of some
knowledge of the form of your function.  For example, in the numerical
solution of batch crystallizer models the steady-state solutions take
on decaying exponential form with superimposed transients.  Since the
Laguerre family of polynomials are orthogonal with respect to an
exponential weight they make a good choice for this problem.  The
integrations are much simpler.

In other cases, people merely view the weight function as a means to
affect the placement of the roots of the approximating polynomial.
For example, if your data are concentrated at one end of the x-domain
you may wish to concentrate the roots of the polynomial in the region.

>
>3. How does one choose between Legendre and Chebyshev?  Legendre has a
>weight function w(x) = 1, which makes sense to my approximation needs.
>Chebyshev has the attractive property of lower computational cost and
>smaller error.

For most run of the mill problems, the family of Jacobi polynomials,
of which Legendre and Chebyshev are special cases, are suitable.
Among other considerations, the placement of the roots is different.
See above discussion.
>
>4. What are the pitfalls of extracting derivatives out of the
>approximation?

The pitfalls are the same as with any derivative extraction technique,
except they are somewhat mitigated by the fact that the polynomial
approximation is essentially a curve fit and smoothing of the data.
One nice advantage of this technique is that the 1st and 2nd
derivative weight matrices may be had with little computational
effort.  This idea is used in orthogonal collocation to compute
solutions differential equations all the time.  For some good
references see:

@article{Villadsen:Stewart:67,
  author = "Villadsen, John V. and Stewart, Warren E.",
  title = "Solution of Boundary-value Problems by Orthogonal Collocation",
  journal = "Chemical Engineering Science",
  volume = "22",
  pages = "1483-1501",
  year = "1967",
  file = "Numerical Analysis"	}

@book{Finlayson:72,
  author = "Finlayson, Bruce A.",
  title = "Method of Weighted Residuals and Variational Principles: with {A}pplication in {F}luid {M}echanics, {H}eat and {M}ass {T}ransfer",
  publisher = "Academic Press",
  address = "New York",
  year = "1972",
  isbn = "0-12-257050-2",
  file = "office",
  series = "Mathematics in Science and Engineering",
  volume = "87"	}

>
>5. If I must use the Laguerre polynomial, which is defined on 
>[0, infinity], then where do I find out the recurrence relation 
>for evaluating it?

The consummate reference for this type of thing is:

@book{Abramowitz:Stegun:72 ,
	editor = "Abramowitz, Milton and Stegun, Irene A." ,
	publisher = "Dover Publications, Inc." ,
	title = "Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables" ,
	year = "1972"	}

Another excellent reference that contains all the basic information
and classical results on orthogonal polynomial approximation is

@book{Davis:75,
  author = "Davis, Philip J.",
  title = "Interpolation \& Approximation",
  publisher = "Dover Publications, Inc.",
  address = "New York",
  year = "1975",
  isbn = "0-486-62495-1"	}

Both of these books are inexpensive and available in paperback.  Would
you expect anything else from Dover?

>
>Thanks,
>
>        -ans.
>
>
>-- 
>Ajay Shah, (213)749-8133, ajayshah@usc.edu


-- 
Tony Mullins (jamull@che.utexas.edu)
Dept. of Chemical Engineering, CPE 5.438
University of Texas - Austin
Austin, TX  78712-1062