Wednesday, October 3, 2012

Chebyshev polynomials in cl-num-utils

I just pushed an update to the cl-num-utils repository, merging a branch which implements function approximation with Chebyshev polynomials.

For example,

(defun myfun (x)
  "Function that we want to approximate."
  (expt x -2))

(defparameter *myapprox* (chebyshev-approximate #'myfun (interval 2 10) 8)
  "Chebyshev approximation for MYFUN on the interval [2,10], using 8 Chebyshev

(myfun 5d0)            ; 0.04d0
(funcall *myapprox* 5) ; 0.04018023309369832d0

Approximation with Chebyshev polynomials is very fast and stable because it does not require a matrix inversion (Chebyshev polynomials are orthogonal), and thus it is a very nice procedure if you want to approximate a "smooth" function that is expensive to evaluate.

I also extended the interval code in cl-num-utils, now it handles open and infinite endpoints. This extension is experimental and not all functions understand it at the moment, but you can use my new extended-reals library to denote infinites, for example

(chebyshev-approximate #'sqrt (interval 0 (xr:inf)) 10)

would approximate \(x\mapsto\sqrt{x}\) on \([0,\infty)\). I will blog about extended-reals soon.


  1. Note, if you fix the github issue #12, cl-num-utils will (hopefully) build on lisps other than SBCL

    1. I fixed the issue in the latest commit, thanks for the reminder. Note that the library needs the latest let-plus.