|
from ..libmp.backend import xrange |
|
from .calculus import defun |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
def chebcoeff(ctx,f,a,b,j,N): |
|
s = ctx.mpf(0) |
|
h = ctx.mpf(0.5) |
|
for k in range(1, N+1): |
|
t = ctx.cospi((k-h)/N) |
|
s += f(t*(b-a)*h + (b+a)*h) * ctx.cospi(j*(k-h)/N) |
|
return 2*s/N |
|
|
|
|
|
def chebT(ctx, a=1, b=0): |
|
Tb = [1] |
|
yield Tb |
|
Ta = [b, a] |
|
while 1: |
|
yield Ta |
|
|
|
Tmp = [0] + [2*a*t for t in Ta] |
|
for i, c in enumerate(Ta): Tmp[i] += 2*b*c |
|
for i, c in enumerate(Tb): Tmp[i] -= c |
|
Ta, Tb = Tmp, Ta |
|
|
|
@defun |
|
def chebyfit(ctx, f, interval, N, error=False): |
|
r""" |
|
Computes a polynomial of degree `N-1` that approximates the |
|
given function `f` on the interval `[a, b]`. With ``error=True``, |
|
:func:`~mpmath.chebyfit` also returns an accurate estimate of the |
|
maximum absolute error; that is, the maximum value of |
|
`|f(x) - P(x)|` for `x \in [a, b]`. |
|
|
|
:func:`~mpmath.chebyfit` uses the Chebyshev approximation formula, |
|
which gives a nearly optimal solution: that is, the maximum |
|
error of the approximating polynomial is very close to |
|
the smallest possible for any polynomial of the same degree. |
|
|
|
Chebyshev approximation is very useful if one needs repeated |
|
evaluation of an expensive function, such as function defined |
|
implicitly by an integral or a differential equation. (For |
|
example, it could be used to turn a slow mpmath function |
|
into a fast machine-precision version of the same.) |
|
|
|
**Examples** |
|
|
|
Here we use :func:`~mpmath.chebyfit` to generate a low-degree approximation |
|
of `f(x) = \cos(x)`, valid on the interval `[1, 2]`:: |
|
|
|
>>> from mpmath import * |
|
>>> mp.dps = 15; mp.pretty = True |
|
>>> poly, err = chebyfit(cos, [1, 2], 5, error=True) |
|
>>> nprint(poly) |
|
[0.00291682, 0.146166, -0.732491, 0.174141, 0.949553] |
|
>>> nprint(err, 12) |
|
1.61351758081e-5 |
|
|
|
The polynomial can be evaluated using ``polyval``:: |
|
|
|
>>> nprint(polyval(poly, 1.6), 12) |
|
-0.0291858904138 |
|
>>> nprint(cos(1.6), 12) |
|
-0.0291995223013 |
|
|
|
Sampling the true error at 1000 points shows that the error |
|
estimate generated by ``chebyfit`` is remarkably good:: |
|
|
|
>>> error = lambda x: abs(cos(x) - polyval(poly, x)) |
|
>>> nprint(max([error(1+n/1000.) for n in range(1000)]), 12) |
|
1.61349954245e-5 |
|
|
|
**Choice of degree** |
|
|
|
The degree `N` can be set arbitrarily high, to obtain an |
|
arbitrarily good approximation. As a rule of thumb, an |
|
`N`-term Chebyshev approximation is good to `N/(b-a)` decimal |
|
places on a unit interval (although this depends on how |
|
well-behaved `f` is). The cost grows accordingly: ``chebyfit`` |
|
evaluates the function `(N^2)/2` times to compute the |
|
coefficients and an additional `N` times to estimate the error. |
|
|
|
**Possible issues** |
|
|
|
One should be careful to use a sufficiently high working |
|
precision both when calling ``chebyfit`` and when evaluating |
|
the resulting polynomial, as the polynomial is sometimes |
|
ill-conditioned. It is for example difficult to reach |
|
15-digit accuracy when evaluating the polynomial using |
|
machine precision floats, no matter the theoretical |
|
accuracy of the polynomial. (The option to return the |
|
coefficients in Chebyshev form should be made available |
|
in the future.) |
|
|
|
It is important to note the Chebyshev approximation works |
|
poorly if `f` is not smooth. A function containing singularities, |
|
rapid oscillation, etc can be approximated more effectively by |
|
multiplying it by a weight function that cancels out the |
|
nonsmooth features, or by dividing the interval into several |
|
segments. |
|
""" |
|
a, b = ctx._as_points(interval) |
|
orig = ctx.prec |
|
try: |
|
ctx.prec = orig + int(N**0.5) + 20 |
|
c = [chebcoeff(ctx,f,a,b,k,N) for k in range(N)] |
|
d = [ctx.zero] * N |
|
d[0] = -c[0]/2 |
|
h = ctx.mpf(0.5) |
|
T = chebT(ctx, ctx.mpf(2)/(b-a), ctx.mpf(-1)*(b+a)/(b-a)) |
|
for (k, Tk) in zip(range(N), T): |
|
for i in range(len(Tk)): |
|
d[i] += c[k]*Tk[i] |
|
d = d[::-1] |
|
|
|
err = ctx.zero |
|
for k in range(N): |
|
x = ctx.cos(ctx.pi*k/N) * (b-a)*h + (b+a)*h |
|
err = max(err, abs(f(x) - ctx.polyval(d, x))) |
|
finally: |
|
ctx.prec = orig |
|
if error: |
|
return d, +err |
|
else: |
|
return d |
|
|
|
@defun |
|
def fourier(ctx, f, interval, N): |
|
r""" |
|
Computes the Fourier series of degree `N` of the given function |
|
on the interval `[a, b]`. More precisely, :func:`~mpmath.fourier` returns |
|
two lists `(c, s)` of coefficients (the cosine series and sine |
|
series, respectively), such that |
|
|
|
.. math :: |
|
|
|
f(x) \sim \sum_{k=0}^N |
|
c_k \cos(k m x) + s_k \sin(k m x) |
|
|
|
where `m = 2 \pi / (b-a)`. |
|
|
|
Note that many texts define the first coefficient as `2 c_0` instead |
|
of `c_0`. The easiest way to evaluate the computed series correctly |
|
is to pass it to :func:`~mpmath.fourierval`. |
|
|
|
**Examples** |
|
|
|
The function `f(x) = x` has a simple Fourier series on the standard |
|
interval `[-\pi, \pi]`. The cosine coefficients are all zero (because |
|
the function has odd symmetry), and the sine coefficients are |
|
rational numbers:: |
|
|
|
>>> from mpmath import * |
|
>>> mp.dps = 15; mp.pretty = True |
|
>>> c, s = fourier(lambda x: x, [-pi, pi], 5) |
|
>>> nprint(c) |
|
[0.0, 0.0, 0.0, 0.0, 0.0, 0.0] |
|
>>> nprint(s) |
|
[0.0, 2.0, -1.0, 0.666667, -0.5, 0.4] |
|
|
|
This computes a Fourier series of a nonsymmetric function on |
|
a nonstandard interval:: |
|
|
|
>>> I = [-1, 1.5] |
|
>>> f = lambda x: x**2 - 4*x + 1 |
|
>>> cs = fourier(f, I, 4) |
|
>>> nprint(cs[0]) |
|
[0.583333, 1.12479, -1.27552, 0.904708, -0.441296] |
|
>>> nprint(cs[1]) |
|
[0.0, -2.6255, 0.580905, 0.219974, -0.540057] |
|
|
|
It is instructive to plot a function along with its truncated |
|
Fourier series:: |
|
|
|
>>> plot([f, lambda x: fourierval(cs, I, x)], I) #doctest: +SKIP |
|
|
|
Fourier series generally converge slowly (and may not converge |
|
pointwise). For example, if `f(x) = \cosh(x)`, a 10-term Fourier |
|
series gives an `L^2` error corresponding to 2-digit accuracy:: |
|
|
|
>>> I = [-1, 1] |
|
>>> cs = fourier(cosh, I, 9) |
|
>>> g = lambda x: (cosh(x) - fourierval(cs, I, x))**2 |
|
>>> nprint(sqrt(quad(g, I))) |
|
0.00467963 |
|
|
|
:func:`~mpmath.fourier` uses numerical quadrature. For nonsmooth functions, |
|
the accuracy (and speed) can be improved by including all singular |
|
points in the interval specification:: |
|
|
|
>>> nprint(fourier(abs, [-1, 1], 0), 10) |
|
([0.5000441648], [0.0]) |
|
>>> nprint(fourier(abs, [-1, 0, 1], 0), 10) |
|
([0.5], [0.0]) |
|
|
|
""" |
|
interval = ctx._as_points(interval) |
|
a = interval[0] |
|
b = interval[-1] |
|
L = b-a |
|
cos_series = [] |
|
sin_series = [] |
|
cutoff = ctx.eps*10 |
|
for n in xrange(N+1): |
|
m = 2*n*ctx.pi/L |
|
an = 2*ctx.quadgl(lambda t: f(t)*ctx.cos(m*t), interval)/L |
|
bn = 2*ctx.quadgl(lambda t: f(t)*ctx.sin(m*t), interval)/L |
|
if n == 0: |
|
an /= 2 |
|
if abs(an) < cutoff: an = ctx.zero |
|
if abs(bn) < cutoff: bn = ctx.zero |
|
cos_series.append(an) |
|
sin_series.append(bn) |
|
return cos_series, sin_series |
|
|
|
@defun |
|
def fourierval(ctx, series, interval, x): |
|
""" |
|
Evaluates a Fourier series (in the format computed by |
|
by :func:`~mpmath.fourier` for the given interval) at the point `x`. |
|
|
|
The series should be a pair `(c, s)` where `c` is the |
|
cosine series and `s` is the sine series. The two lists |
|
need not have the same length. |
|
""" |
|
cs, ss = series |
|
ab = ctx._as_points(interval) |
|
a = interval[0] |
|
b = interval[-1] |
|
m = 2*ctx.pi/(ab[-1]-ab[0]) |
|
s = ctx.zero |
|
s += ctx.fsum(cs[n]*ctx.cos(m*n*x) for n in xrange(len(cs)) if cs[n]) |
|
s += ctx.fsum(ss[n]*ctx.sin(m*n*x) for n in xrange(len(ss)) if ss[n]) |
|
return s |
|
|
