6
$\begingroup$

There's a related question, but it doesn't seem to apply to spacecraft trajectories.

Suppose you want to send a non-thrusting spacecraft far from earth, and you have ground tracking of the spacecraft, but the spacecraft doesn't have any way of directly incorporating position/velocity updates into its nav system (no GPS, for example). So, you're getting range and range-rate updates on the ground and incorporating them into a trajectory approximation using a batch least squares estimator; and then you're propagating it forward in time using your knowledge of the system dynamics. You want to transmit this estimated trajectory to the spacecraft so that it can interpolate its position and velocity instead of relying on a noisy IMU.

I've heard of people using Chebyshev polynomials for this purpose, but it seems like SPICE has much better support for Hermite polynomials, and makes it much easier to produce Hermite-based spacecraft ephemeris than Chebyshev. While JPL has published a method for producing Chebyshev position/velocity fits for planetary bodies, the paper does not discuss their applicability to spacecraft or satellites.

In general, are there reasons to choose Hermite over Chebyshev, or vice-versa? I can't really find any discussions of their pros and cons, even in the SPK required reading from NAIF/SPICE.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ The nice thing about Hermite polynomials (and also Lagrange polynomials) is that they exactly hit the data points fed to the estimation techique. The nice thing about Chebyshev polynomials is the exact opposite: Chebyshev polynomial by design $\large{\text{do not}}$ exactly hit the input data points. One of the key appeals of Chebyshev approximation is that they instead come very close to the ideal of a minimax polynomial. There are ways improve upon Chebyshev approximation if the goal is to hit that ideal. $\endgroup$
    – David Hammen
    Aug 2, 2019 at 7:53
  • $\begingroup$ @DavidHammen Why would one prefer polynomials that don't hit the input data points? I think I'm not clear on why the minimax polynomial should fail to hit the input points. $\endgroup$
    – Translunar
    Aug 2, 2019 at 14:45
  • $\begingroup$ @DoctorMohawk that might require a new question, but maybe not. In the mean time there's this answer which may be helpful, and possibly something here and here as well. $\endgroup$
    – uhoh
    Aug 2, 2019 at 14:54
  • 1
    $\begingroup$ Because that's not the goal. The minimax polynomial of some degree N minimizes the maximum absolute error over the observed values. For example, suppose you have 1001 measurements of a function that maps reals to reals. You could use a 1000th order polynomial and hit all observations exactly. Good luck using that polynomial anywhere except exactly at those observation points. Alternatively one could use a least squares approach with a much lower order polynomial. A problem with least squares is that there's no guarantee about worst case behavior. A minimax polynomial provides that guarantee. $\endgroup$
    – David Hammen
    Aug 2, 2019 at 15:03

1 Answer 1

Reset to default
6
$\begingroup$

SPICE has multiple tools for constructing and using piecewise Lagrange and Hermite polynomials because those techniques are textbook. In contrast, techniques for constructing piecewise Chebyshev approximations are anything but textbook. SPICE supports one very specific format of using (but not constructing) piecewise Chebyshev polynomial approximations. That that format is exactly the format created by a different group at JPL to model planetary ephemerides is quite intentional.

That SPICE does not provide mechanisms for creating those piecewise Chebyshev polynomial approximations is also quite intentional. A lot of care and feeding is needed in creating those approximations, and the resulting approximations need to be validated by an expert.

With regard to which is preferable (Lagrange vs Hermite vs Chebyshev), those techniques were developed to answer different questions. A Lagrange polynomial exactly hits the provided data points. A piecewise Lagrange polynomial exactly hits a lot more data points, but with discontinuities at the derivatives at the points where one pieces shifts to the next. Piecewise Hermite polynomials add fitting to derivatives.

There's a problem here: Fitting exactly over long intervals means the match at intervening point will be anything but exact. Chebyshev polynomials (and similarly, least squares fits) relax the requirement to provide exact in exchange for a close fit. This allows one to use values at intervening points to keep the solution "close". What "close" means is in the eye of the beholder -- and in the eye of the norm. A least squares polynomial fit over some interval minimizes the L2 norm of the difference between function to be approximated and the approximation over the interval of interest.

The L2 norm is not the be-all and end-all of norms. There are other norms. A downside of the minimizing the L2 norm is that there can be some cases within the interval of interest where the least squares polynomial yields a bad fit. A polynomial of a given degree that minimizes the L-infinity norm addresses this issue, but at the cost of not having a minimal L2 norm. The polynomial that minimizes the L-infinity norm is called the minimax polynomial ("the" because it's unique for well-behaved functions).

Finding that minimax polynomial is difficult. Fortunately, a Chebyshev polynomial based on function values at the Chebyshev nodes is easy to construction and comes very close (typically within a factor of two) of the minimax polynomial. These (ease of construction and closeness to the minimax polynomial) are the primary reasons many prefer Chebyshev approximations.

Improve this answer
$\endgroup$
4
  • $\begingroup$ This is one of those @DavidHammen gems that's going to take a while to go through, but when done provides a lot of new insight. To get the ball rolling, what's an L2 norm and an L-infinity norm? $\endgroup$
    – uhoh
    Aug 2, 2019 at 15:59
  • 1
    $\begingroup$ @uhoh - The $L^n$ norm of a set of values ${f_i}$ is the $n^\text{ th}$root of the sum of the absolute values of each element raised to $n^\text{ th}$ power: $$|f|^n = \sqrt[n]{\sum_i ||f_i||^n}$$Note that the L2 norm of a vector is the square root of the sum of the squares of the elements, aka the Euclidean norm. This concept of Lebesgue norms be generalized to a functions $f(x)$ over some interval $(a,b)$ by integrating rather than summing: $$|f(x)|^n = \sqrt[n]{\int_a^b ||f(x)||^n\,dx}$$. (continued) $\endgroup$
    – David Hammen
    Aug 2, 2019 at 16:57
  • 1
    $\begingroup$ The L-infinity norm is the limit of the $L^n$ norm as $n\to\infty$. The largest element of $f_i$ (or the maximum absolute value of $f(x)$ over $(a,b)$ in the case of a function) dominates over all others as $n$ becomes bigger and bigger. This means the L-infinity norm is simply the maximum absolute value of all possible values. $\endgroup$
    – David Hammen
    Aug 2, 2019 at 16:58
  • 1
    $\begingroup$ In layman's terms, a minimax polynomial answers the question "What's the worst thing this approximation will to do to me if I use that approximation?" Computer implementations of sine, cosine, tangent, etc. typically use piecewise minimax polynomial approximations rather than Taylor series so that the approximation is (ideally) good to half an ULP (unit of last place). Performance-wise, Taylor series are lousy compared to piecewise minimax polynomials. $\endgroup$
    – David Hammen
    Aug 2, 2019 at 17:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.