3.1 roots

Chebfun comes with a global rootfinding capability -- the ability to find all the zeros of a function in its region of definition. For example, here is a polynomial with two roots in $[-1,1]$:

  x = chebfun('x');
  p = x^3 + x^2 - x;
  r = roots(p)
r =
   0.000000000000000
   0.618033988749895

We can plot $p$ and its roots like this:

  plot(p), grid on
  hold on, plot(r,p(r),'.r')

Of course, one does not need Chebfun to find roots of a polynomial. The MATLAB roots command works from a polynomial's coefficients and computes estimates of all the roots, not just those in a particular interval.

  roots([1 1 -1 0])
ans =
                   0
  -1.618033988749895
   0.618033988749895

A more substantial example of rootfinding involving a Bessel function was considered in Sections 1.2 and 2.4. Here is a similar calculation for the Airy functions Ai and Bi, modeled after the page on Airy functions at WolframMathWorld.

  Ai = chebfun(@(x) airy(0,x),[-10,3]);
  Bi = chebfun(@(x) airy(2,x),[-10,3]);
  hold off, plot(Ai,'r')
  hold on, plot(Bi,'b')
  rA = roots(Ai); plot(rA,Ai(rA),'.r')
  rB = roots(Bi); plot(rB,Bi(rB),'.b')
  axis([-10 3 -.6 1.5]), grid on

Here for example are the three roots of Ai and Bi closest to 0:

  [rA(end-2:end) rB(end-2:end)]
ans =
  -5.520559828095557  -4.830737841662014
  -4.087949444130971  -3.271093302836357
  -2.338107410459767  -1.173713222709129

Chebfun finds roots by a method due to Boyd and Battles [Boyd 2002, Boyd 2014, Battles 2006]. If the chebfun is of degree greater than about $50$, it is broken into smaller pieces recursively. On each small piece zeros are then found as eigenvalues of a "colleague matrix", the analogue for Chebyshev polynomials of a companion matrix for monomials [Specht 1960, Good 1961]. This method can be startlingly fast and accurate. For example, here is a sine function with $11$ zeros:

  f = chebfun('sin(pi*x)',[0 10]);
  lengthf = length(f)
  tic, r = roots(f); toc
  r
lengthf =
    44
Elapsed time is 0.004055 seconds.
r =
                   0
   1.000000000000000
   1.999999999999998
   3.000000000000000
   4.000000000000000
   4.999999999999999
   6.000000000000001
   7.000000000000000
   8.000000000000000
   9.000000000000007
   9.999999999999993

A similar computation with 101 zeros comes out equally well:

  f = chebfun('sin(pi*x)',[0 100]);
  lengthf = length(f)
  tic, r = roots(f); toc
  fprintf('%22.14f\n',r(end-4:end))
lengthf =
   214
Elapsed time is 0.038469 seconds.
     96.00000000000001
     97.00000000000000
     98.00000000000001
     99.00000000000000
    100.00000000000000

And here is the same on an interval with 1001 zeros.

  f = chebfun('sin(pi*x)',[0 1000]);
  lengthf = length(f)
  tic, r = roots(f); toc
  fprintf('%22.13f\n',r(end-4:end))
lengthf =
        1684
Elapsed time is 0.096928 seconds.
     996.0000000000000
     997.0000000000000
     998.0000000000000
     999.0000000000000
    1000.0000000000000

Here are the 130 roots from the "fish fillet" example in the Chebfun gallery:

f = cheb.gallery('fishfillet');
hold off, plot(f)
tic, r = roots(f); toc
hold on, plot(r,f(r),'.r'), hold off
Elapsed time is 0.015386 seconds.

With the ability to find zeros, we can solve a variety of nonlinear problems. For example, where do the curves $x$ and $\cos(x)$ intersect? Here is the answer.

  x = chebfun('x',[-2 2]);
  hold off, plot(x)
  f = cos(x);
  hold on, plot(f,'k')
  r = roots(f-x)
  plot(r,f(r),'or')
r =
   0.739085133215161

All of the examples above concern chebfuns consisting of a single fun. If there are several funs, then roots are included at jumps as necessary. The following example shows a chebfun with $26$ pieces. It has nine zeros: one within a fun, eight at jumps between funs.

  x = chebfun('x',[-2 2]);
  f = x^3 - 3*x - 2 + sign(sin(20*x));
  hold off, plot(f), grid on
  r = roots(f);
  hold on, plot(r,0*r,'.r')

If one prefers only the "genuine" roots, omitting those at jumps, they can be computed by using the nojump flag:

  hold off, plot(f), grid on
  r = roots(f,'nojump');
  hold on, plot(r,0*r,'.r')

3.2 min, max, abs, sign, round, floor, ceil

Rootfinding is more central to Chebfun than one might at first imagine, because a number of commands, when applied to smooth chebfuns, must produce non-smooth results, and it is rootfinding that tells us where to put the discontinuities. For example, the abs command introduces breakpoints wherever the argument goes through zero. Here we see that x consists of a single piece, whereas abs(x) consists of two pieces.

  x = chebfun('x')
  absx = abs(x)
  subplot(1,2,1), plot(x)
  subplot(1,2,2), plot(absx)
x =
   chebfun column (1 smooth piece)
       interval       length     endpoint values  
[      -1,       1]        2        -1        1 
vertical scale =   1 
absx =
   chebfun column (2 smooth pieces)
       interval       length     endpoint values  
[      -1,       0]        2         1        0 
[       0,       1]        2         0        1 
vertical scale =   1    Total length = 4

We saw this effect already in Section 1.4. Another similar effect shown in that section occurs with min(f,g) or max(f,g). Here, breakpoints are introduced at points where f-g is zero:

  f = min(x,-x/2), subplot(1,2,1), plot(f)
  g = max(.6,1-x^2), subplot(1,2,2), plot(g), ylim([.5,1])
f =
   chebfun column (2 smooth pieces)
       interval       length     endpoint values  
[      -1,       0]        2        -1        0 
[       0,       1]        2         0     -0.5 
vertical scale =   1    Total length = 4
g =
   chebfun column (3 smooth pieces)
       interval       length     endpoint values  
[      -1,   -0.63]        1       0.6      0.6 
[   -0.63,    0.63]        3       0.6      0.6 
[    0.63,       1]        1       0.6      0.6 
vertical scale =   1    Total length = 5

The function sign also introduces breaks, as illustrated in the last section. The commands round, floor, and ceil behave like this too. For example, here is $\exp(x)$ rounded to nearest multiples of $0.1$:

  g = exp(x);
  clf, plot(g)
  gh = round(10*g)/10;
  hold on, plot(gh,'jumpline','-');
  grid on

3.3 Local extrema

Local extrema of smooth functions can be located by finding zeros of the derivative. For example, here is a variant of the Airy function again, with all its extrema in its range of definition located and plotted.

  f = chebfun('exp(real(airy(x)))',[-15,0]);
  clf, plot(f)
  r = roots(diff(f));
  hold on, plot(r,f(r),'.r'), grid on

Chebfun users don't have to compute the derivative explicitly to find extrema, however. An alternative is to type

  [ignored,r2] = minandmax(f,'local');

which returns both interior local extrema and also the endpoints of f. Similarly one can type min(f,'local') and max(f,'local').

These methods will find non-smooth extrema as well as smooth ones, since these correspond to "zeros" of the derivative where the derivative jumps from one sign to the other. Here is an example.

  x = chebfun('x');
  f = exp(x)*sin(30*x);
  g = 2-6*x^2;
  h = max(f,g);
  clf, plot(h)

Here are all the local extrema, smooth and nonsmooth:

  [ignored,extrema] = minandmax(h,'local');
  hold on, plot(extrema,h(extrema),'.r')

Suppose we want to pick out the local extrema that are actually local minima. We can do that by hand by checking for the second derivative to be positive:

  h2 = diff(h,2);
  maxima = extrema(h2(extrema)>0);
  plot(maxima,h(maxima),'ok')

Or we could do it implicitly with local,

  [maxval,maxpos] = min(h,'local')
  plot(maxpos,maxval,'.k')
maxval =
   0.363476521730995
  -0.410835468002950
  -0.506554704820388
   0.257807200650399
   0.848004324296446
  -0.324870829559026
  -1.882251804443055
  -2.705787848740120
maxpos =
  -1.000000000000000
  -0.889007218654500
  -0.679567708415180
  -0.538855701053878
   0.438177223602421
   0.622477687626771
   0.804389189016844
   0.995948373499376

3.4 Global extrema: max and min

If min or max is applied to a single chebfun, it returns its global minimum or maximum. For example:

  f = chebfun('1-x^2/2');
  [min(f) max(f)]
ans =
   0.500000000000000   1.000000000000000

Chebfun computes such a result by checking the values of f at endpoints and at zeros of the derivative.

As with standard MATLAB, one can find the location of the extreme point by supplying two output arguments:

  [minval,minpos] = min(f)
minval =
   0.500000000000000
minpos =
    -1

Note that just one position is returned even though the minimum is attained at two points. This is consistent with the behavior of standard MATLAB.

This ability to do global 1D optimization in Chebfun is rather remarkable. Here is a nontrivial example.

  f = chebfun('sin(x)+sin(x^2)',[0,15]);
  hold off, plot(f,'k')

The length of this chebfun is not as great as one might imagine:

  length(f)
ans =
   216

Here are its global minimum and maximum:

  [minval,minpos] = min(f)
  [maxval,maxpos] = max(f)
  hold on
  plot(minpos,minval,'.b')
  plot(maxpos,maxval,'.r')
minval =
  -1.990085468159408
minpos =
   4.852581429906174
maxval =
   1.995232599437860
maxpos =
  14.234791972306912

For larger chebfuns, it is inefficient to compute the global minimum and maximum separately like this -- each one must compute the derivative and find all its zeros. The alternative minandmax code mentioned above provides a faster alternative:

  [extremevalues,extremepositions] = minandmax(f)
extremevalues =
  -1.990085468159408
   1.995232599437860
extremepositions =
   4.852581429906174
  14.234791972306912

3.5 norm(f,1) and norm(f,inf)

The default, $2$-norm form of the norm command was considered in Section 2.2. In standard MATLAB one can also compute $1$-, $\infty$-, and Frobenius norms with norm(f,1), norm(f,inf), and norm(f,'fro'). These have been overloaded in Chebfun, and in the first two cases, rootfinding is part of the implementation. (The $2$- and Frobenius norms are equal for a single chebfun but differ for quasimatrices; see Chapter 6.) The $1$-norm norm(f,1) is the integral of the absolute value, and Chebfun computes this by adding up segments between zeros, at which $|f(x)|$ will typically have a discontinuous slope. The $\infty$-norm is computed from the formula $|f|_\infty = \max(\max(f),-\min(f))$.

For example:

  f = chebfun('sin(x)',[103 103+4*pi]);
  norm(f,inf)
  norm(f,1)
ans =
   1.000000000000002
ans =
   7.999999999999992

3.6 Roots in the complex plane

Chebfuns live on real intervals, and the funs from which they are made live on real subintervals. But a polynomial representing a fun may have roots outside the interval of definition, which may be complex. Sometimes we may want to get our hands on these roots, and the roots command makes this possible in various ways through the flags 'all', 'complex', and 'norecursion'.

The simplest example is a chebfun that is truly intended to correspond to a polynomial. For example, the chebfun

f = 1+16*x^2;

has no roots in $[-1,1]$:

roots(f)
ans =
  0x1 empty double column vector

We can extract its complex roots with the command

roots(f,'all')
ans =
  0.000000000000000 - 0.250000000000000i
  0.000000000000000 + 0.250000000000000i

The situation for more general chebfuns is more complicated. For example, the chebfun

g = exp(x)*f(x);

also has no roots in $[-1,1]$,

roots(g)
ans =
  0x1 empty double column vector

but it has plenty of roots in the complex plane:

roots(g,'all')
ans =
 -0.000000000000002 - 0.249999999999979i
 -0.000000000000002 + 0.249999999999979i
 -4.510099694278965 + 0.000000000000000i
 -4.301164225397378 - 1.512642324323805i
 -4.301164225397378 + 1.512642324323805i
 -3.661328308890921 - 2.987062768432330i
 -3.661328308890921 + 2.987062768432330i
 -2.546068716313584 - 4.375176403335687i
 -2.546068716313584 + 4.375176403335687i
 -0.857245230145749 - 5.602871243782512i
 -0.857245230145749 + 5.602871243782512i
  1.626751513815270 - 6.531242873660521i
  1.626751513815270 + 6.531242873660521i
  5.552947899178226 - 6.812833096055662i
  5.552947899178226 + 6.812833096055662i

Most of these are spurious. What has happened is that g is represented by a polynomial chosen for its approximation properties on $[-1,1]$. Inevitably that polynomial will have roots in the complex plane, even if they have little to do with g. (See the discussion of the Walsh and Blatt-Saff theorems in Chapter 18 of [Trefethen 2013].)

One cannot expect Chebfun to solve this problem perfectly -- after all, it is working on a real interval, not in the complex plane, and analytic continuation from the one to the other is well known to be an ill-posed problem. Nevertheless, Chebfun may do a pretty good job of selecting genuine complex (and real) roots near the interval of definition if you use the 'complex' flag:

roots(g,'complex')
ans =
 -0.000000000000002 - 0.249999999999979i
 -0.000000000000002 + 0.249999999999979i

We will not go into detail here of how this is done, but the idea is that associated with any fun is a family of "Chebfun ellipses" in the complex plane, with foci at the endpoints, inside which one may expect reasonably good accuracy of the fun. Assuming the interval is $[-1,1]$ and the fun has length $L$, the Chebfun ellipse associated with a parameter $\delta\ll 1$ is the region in the complex plane bounded by the image under the map $(z+1/z)/2$ of the circle $|z|=r$, where $r$ is defined by the condition $r^{-L}=\delta$. (See Chapter 8 of [Trefethen 2013].) The command roots(g,'complex') first effectively does roots(g,'all'), then returns only those roots lying inside a particular Chebfun ellipse -- we take the one corresponding to delta equal to the square root of the Chebfun tolerance parameter eps.

One must expect complex roots of chebfuns to lose accuracy as one moves away from the interval of definition. Here's an example:

  f = exp(exp(x)).*(x-0.1i).*(x-.3i).*(x-.6i).*(x-1i);
  roots(f,'complex')
ans =
  0.000000000000073 + 0.100000000000033i
 -0.000000000075339 + 0.299999999948328i
  0.000000228970893 + 0.600000111611714i

Notice that the first three imaginary roots are located with about $13$, $10$, and $6$ digits of accuracy, while the fourth does not appear in the list at all.

Here is a more complicated example:

F = @(x) 4+sin(x)+sin(sqrt(2)*x)+sin(pi*x);
f = chebfun(F,[-100,100]);

This function has a lot of complex roots lying in strips on either side of the real axis.

  r = roots(f,'complex');
  hold off, plot(r,'.')

If you are dealing with complex roots of complicated chebfuns like this, it may be safer to add a flag 'norecursion' to the roots call, at the cost of slowing down the computation. This turns off the Boyd-Battles recursion mentioned above, lowering the chance of missing a few roots near interfaces of the recursion. If we try that here we find that the results look almost the same as before in a plot:

r2 = roots(f,'complex','norecursion');
hold on, plot(r,'om')

However, the accuracy has improved:

norm(F(r))
norm(F(r2))
ans =
     3.576456628650049e-08
ans =
     6.766581573580990e-09

To find poles in the complex plane as opposed to zeros, see Section 4.8 and also [Austin, Kravanja & Trefethen 2015]. More advanced methods of rootfinding and polefinding are based on rational approximations rather than polynomials, an area where Chebfun has significant capabilities; see the next chapter of this guide, Chapter 28 of [Trefethen 2013], and [Webb 2013].

3.7 References

[Austin, Kravanja & Trefethen 2015] A. P. Austin, P. Kravanja, and L. N. Trefethen, "Numerical algorithms based on analytic function values at roots of unity", SIAM Journal on Numerical Analysis, to appear.

[Battles 2006] Z. Battles, Numerical Linear Algebra for Continuous Functions, DPhil thesis, Oxford University Computing Laboratory, 2006.

[Boyd 2002] J. A. Boyd, "Computing zeros on a real interval through Chebyshev expansion and polynomial rootfinding", SIAM Journal on Numerical Analysis, 40 (2002), 1666-1682.

[Boyd 2014] J. A. Boyd, Solving Transcendental Equations: The Chebyshev Polynomial Proxy and Other Numerical Rootfinders, Perturbation Series, and Oracles, SIAM, 2014.

[Good 1961] I. J. Good, "The colleague matrix, a Chebyshev analogue of the companion matrix", Quarterly Journal of Mathematics, 12 (1961), 61-68.

[Specht 1960] W. Specht, "Die Lage der Nullstellen eines Polynoms. IV", Mathematische Nachrichten, 21 (1960), 201-222.

[Trefethen 2013] L. N. Trefethen, Approximation Theory and Approximation Practice, SIAM, 2013.

[Webb 2013] M. Webb, "Computing complex singularities of differential equations with Chebfun", SIAM Undergraduate Research Online, 6 (2013), http://dx.doi.org/10.1137/12S011520.