{"id":336,"date":"2012-10-08T12:30:11","date_gmt":"2012-10-08T17:30:11","guid":{"rendered":"https:\/\/blogs.mathworks.com\/cleve\/?p=336"},"modified":"2017-05-01T07:05:16","modified_gmt":"2017-05-01T12:05:16","slug":"chebfun-roots","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/cleve\/2012\/10\/08\/chebfun-roots\/","title":{"rendered":"CHEBFUN, Roots"},"content":{"rendered":"&nbsp;\r\n\r\n<style type=\"text\/css\">\r\n<p>h1 { font-size:18pt; }<br \/>\r\nh2.titlebg { font-size:13pt; }<br \/>\r\nh3 { color:#4A4F55; padding:0px; margin:5px 0px 5px; font-family:Arial, Helvetica, sans-serif; font-size:11pt; font-weight:bold; line-height:140%; border-bottom:1px solid #d6d4d4; display:block; }<br \/>\r\nh4 { color:#4A4F55; padding:0px; margin:0px 0px 5px; font-family:Arial, Helvetica, sans-serif; font-size:10pt; font-weight:bold; line-height:140%; border-bottom:1px solid #d6d4d4; display:block; }<\/p>\r\n<p>p { padding:0px; margin:0px 0px 20px; }<br \/>\r\nimg { padding:0px; margin:0px 0px 20px; border:none; }<br \/>\r\np img, pre img, tt img, li img { margin-bottom:0px; } <\/p>\r\n<p>ul { padding:0px; margin:0px 0px 20px 23px; list-style:square; }<br \/>\r\nul li { padding:0px; margin:0px 0px 7px 0px; background:none; }<br \/>\r\nul li ul { padding:5px 0px 0px; margin:0px 0px 7px 23px; }<br \/>\r\nul li ol li { list-style:decimal; }<br \/>\r\nol { padding:0px; margin:0px 0px 20px 0px; list-style:decimal; }<br \/>\r\nol li { padding:0px; margin:0px 0px 7px 23px; list-style-type:decimal; }<br \/>\r\nol li ol { padding:5px 0px 0px; margin:0px 0px 7px 0px; }<br \/>\r\nol li ol li { list-style-type:lower-alpha; }<br \/>\r\nol li ul { padding-top:7px; }<br \/>\r\nol li ul li { list-style:square; }<\/p>\r\n<p>pre, tt, code { font-size:12px; }<br \/>\r\npre { margin:0px 0px 20px; }<br \/>\r\npre.error { color:red; }<br \/>\r\npre.codeinput { padding:10px; border:1px solid #d3d3d3; background:#f7f7f7; }<br \/>\r\npre.codeoutput { padding:10px 11px; margin:0px 0px 20px; color:#4c4c4c; }<\/p>\r\n<p>@media print { pre.codeinput, pre.codeoutput { word-wrap:break-word; width:100%; } }<\/p>\r\n<p>span.keyword { color:#0000FF }<br \/>\r\nspan.comment { color:#228B22 }<br \/>\r\nspan.string { color:#A020F0 }<br \/>\r\nspan.untermstring { color:#B20000 }<br \/>\r\nspan.syscmd { color:#B28C00 }<\/p>\r\n<p>.footer { width:auto; padding:10px 0px; margin:25px 0px 0px; border-top:1px dotted #878787; font-size:0.8em; line-height:140%; font-style:italic; color:#878787; text-align:left; float:none; }<br \/>\r\n.footer p { margin:0px; }<\/p>\r\n<\/style>\r\n<div class=\"content\">\r\n\r\n<!--introduction-->\r\n\r\nThe ROOTS function in Chebfun is one of its most powerful features.\r\n\r\nThis is the second part of my series on Chebfun. Part one is <a href=\"https:\/\/blogs.mathworks.com\/cleve\/2012\/10\/01\/chebfun-numerical-computing-with-functions\/\">here<\/a>.\r\n\r\n<!--\/introduction-->\r\n<h3>Contents<\/h3>\r\n<div>\r\n<ul>\r\n \t<li><a href=\"#ddc05790-77a0-4c29-83a6-534537a5f00f\">Roots versus zeros<\/a><\/li>\r\n \t<li><a href=\"#3c74ef75-1a86-4f0a-aab8-4c3773593f9d\">Companion and colleague matrices.<\/a><\/li>\r\n \t<li><a href=\"#7a1a38bb-9743-4ed7-9500-fe079ec6dfca\">Bessel function example<\/a><\/li>\r\n \t<li><a href=\"#e304e223-3d2c-4067-acc2-a41e97959309\">Hidden uses<\/a><\/li>\r\n<\/ul>\r\n<\/div>\r\n<h4>Roots versus zeros<a name=\"ddc05790-77a0-4c29-83a6-534537a5f00f\"><\/a><\/h4>\r\nBefore I wrote this blog I tried to make a distinction between the mathematical terms \"roots\" and \"zeros\". As far as I was concerned, equations had \"roots\" while functions had \"zeros\". The <b>roots<\/b> of the equation $x^3 = 2x + 5$ were the <b>zeros<\/b> of the polynomial $x^3 - 2x - 5$. But now I've decided to stop trying to make that distinction.\r\n\r\nThe MATLAB function <tt>roots<\/tt> finds all of the roots of a polynomial. No equation or interval or starting approximation is involved. But <tt>roots<\/tt> applies only to polynomials. The MATLAB function <tt>fzero<\/tt> finds only one zero of a function, not an equation, near a specified starting value or, better yet, in a specified interval. To find many zeros you have to call <tt>fzero<\/tt> repeatedly with carefully chosen starting values. So MATLAB does not make the rigorous distinction between roots and zeros that I used to desire.\r\n\r\nChebfun has a very powerful and versatile function named <tt>roots<\/tt>. A <tt>chebfun<\/tt> is a highly accurate polynomial approximation to a smooth function, so the <tt>roots<\/tt> of a chebfun, which are the roots of a polynomial, are usually excellent approximations to the zeros of the underlying function. And Chebfun's <tt>roots<\/tt> will find all of them in the interval of definition, not just one.\r\n\r\nSo, Chebfun has helped convince me to stop trying to distinguish between \"roots\" and \"zeros\".\r\n<h4>Companion and colleague matrices.<a name=\"3c74ef75-1a86-4f0a-aab8-4c3773593f9d\"><\/a><\/h4>\r\nWhen I was writing the first MATLAB years ago I was focused on matrix computation and was concerned about code size and memory space, so when I added <tt>roots<\/tt> for polynomials I simply formed the companion matrix and found its eigenvalues. That was a novel approach for polynomial root finding at the time, but it has proved effective and is still used by the MATLAB <tt>roots<\/tt> function today.\r\n\r\nChebfun continues that approach by employing <i>colleague<\/i> matrices for the Chebfun <tt>roots<\/tt> function. I had never heard of colleague matrices until the Oxford workshop a few weeks ago. The eigenvalues of the colleague matrix associated with a Chebyshev polynomial provide the roots of that polynomial in the same way that the eigenvalues of the companion matrix associated with a monic polynomial provide its roots.\r\n<h4>Bessel function example<a name=\"7a1a38bb-9743-4ed7-9500-fe079ec6dfca\"><\/a><\/h4>\r\nLet's pursue an example involving a fractional order Bessel function. Because of the fractional order, this function has a mild singularity at the origin, so we should turn on Chebfun's <tt>splitting<\/tt> option.\r\n<pre class=\"codeinput\">help <span class=\"string\">splitting<\/span>\r\nsplitting <span class=\"string\">on<\/span>\r\n<\/pre>\r\n<pre class=\"codeoutput\"> SPLITTING   CHEBFUN splitting option\r\n    SPLITTING ON allows the Chebfun constructor to split the interval by a\r\n    process of automatic subdivision and edge detection.  This option is\r\n    recommended when working with functions with singularities. \r\n\r\n<\/pre>\r\n<pre class=\"codeinput\">format <span class=\"string\">compact<\/span>\r\nnu = 4\/3\r\na = 25\r\nJ = chebfun(@(x) besselj(nu,x),[0 a]);\r\nlengthJ = length(J)\r\nplot(J)\r\nxlabel(<span class=\"string\">'x'<\/span>)\r\ntitle(<span class=\"string\">'J_{4\/3}(x)'<\/span>)\r\n<\/pre>\r\n<pre class=\"codeoutput\">nu =\r\n    1.3333\r\na =\r\n    25\r\nlengthJ =\r\n   385\r\n<\/pre>\r\n<img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/images\/cleve\/chebfun_2_01.png\" alt=\"\" hspace=\"5\" vspace=\"5\" \/>\r\n\r\nHere are all of our example function's zeros in the interval.\r\n<pre class=\"codeinput\">r = roots(J)\r\nhold <span class=\"string\">on<\/span>\r\nplot(r,0*r,<span class=\"string\">'r.'<\/span>)\r\nhold <span class=\"string\">off<\/span>\r\n<\/pre>\r\n<pre class=\"codeoutput\">r =\r\n    0.0000\r\n    4.2753\r\n    7.4909\r\n   10.6624\r\n   13.8202\r\n   16.9720\r\n   20.1206\r\n   23.2673\r\n<\/pre>\r\n<img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/images\/cleve\/chebfun_2_02.png\" alt=\"\" hspace=\"5\" vspace=\"5\" \/>\r\n\r\nWithout Chebfun, that would have required <i>apriori<\/i> knowledge about the number and approximate location of the zeros in the interval and then a <tt>for<\/tt> loop around calls to <tt>fzero<\/tt>.\r\n<h4>Hidden uses<a name=\"e304e223-3d2c-4067-acc2-a41e97959309\"><\/a><\/h4>\r\nChebfun frequently invokes <tt>roots<\/tt> where it might not be obvious. For example, finding the absolute value of a function involves finding its zeros.\r\n<pre class=\"codeinput\">plot(abs(J))\r\nxlabel(<span class=\"string\">'x'<\/span>)\r\ntitle(<span class=\"string\">'|J_{4\/3}(x)|'<\/span>)\r\n<\/pre>\r\n<img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/images\/cleve\/chebfun_2_03.png\" alt=\"\" hspace=\"5\" vspace=\"5\" \/>\r\n\r\nLet's find the zeros of the first derivative so we can plot circles at the local maxima. The derivative is computed by differentiating the Chebyshev polynomial, not by symbolic differentiation of the Bessel function.\r\n<pre class=\"codeinput\">z = roots(diff(J))\r\nhold <span class=\"string\">on<\/span>\r\nplot(z,abs(J(z)),<span class=\"string\">'ko'<\/span>)\r\nhold <span class=\"string\">off<\/span>\r\n<\/pre>\r\n<pre class=\"codeoutput\">z =\r\n    2.2578\r\n    5.7993\r\n    9.0218\r\n   12.2005\r\n   15.3637\r\n   18.5194\r\n   21.6709\r\n   24.8200\r\n<\/pre>\r\n<img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/images\/cleve\/chebfun_2_04.png\" alt=\"\" hspace=\"5\" vspace=\"5\" \/> <script language=\"JavaScript\"> <!-- \r\n    function grabCode_3f356c9f5ada458894d0e5e2402bf881() {\r\n        \/\/ Remember the title so we can use it in the new page\r\n        title = document.title;\r\n\r\n        \/\/ Break up these strings so that their presence\r\n        \/\/ in the Javascript doesn't mess up the search for\r\n        \/\/ the MATLAB code.\r\n        t1='3f356c9f5ada458894d0e5e2402bf881 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 3f356c9f5ada458894d0e5e2402bf881';\r\n    \r\n        b=document.getElementsByTagName('body')[0];\r\n        i1=b.innerHTML.indexOf(t1)+t1.length;\r\n        i2=b.innerHTML.indexOf(t2);\r\n \r\n        code_string = b.innerHTML.substring(i1, i2);\r\n        code_string = code_string.replace(\/REPLACE_WITH_DASH_DASH\/g,'--');\r\n\r\n        \/\/ Use \/x3C\/g instead of the less-than character to avoid errors \r\n        \/\/ in the XML parser.\r\n        \/\/ Use '\\x26#60;' instead of '<' so that the XML parser\r\n        \/\/ doesn't go ahead and substitute the less-than character. \r\n        code_string = code_string.replace(\/\\x3C\/g, '\\x26#60;');\r\n\r\n        copyright = 'Copyright 2012 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('<\/p>\r\n<pre>\\n');\r\n        d.write(code_string);\r\n\r\n        \/\/ Add copyright line at the bottom if specified.\r\n        if (copyright.length > 0) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (copyright.length > 0) {\r\n                d.writeln('% _' + copyright + '_');\r\n            }\r\n        }\r\n\r\n        d.write('<\/pre>\r\n<p>\\n');\r\n\r\n        d.title = title + ' (MATLAB code)';\r\n        d.close();\r\n    }   \r\n     --> <\/script>\r\n<p style=\"text-align: right; font-size: xx-small; font-weight: lighter; font-style: italic; color: gray;\">\r\n<a><span style=\"font-size: x-small; font-style: italic;\">Get\r\nthe MATLAB code<noscript>(requires JavaScript)<\/noscript><\/span><\/a>\r\n\r\nPublished with MATLAB\u00ae R2012b<\/p>\r\n<p class=\"footer\">\r\nPublished with MATLAB\u00ae R2012b<\/p>\r\n\r\n<\/div>\r\n<!--\r\n3f356c9f5ada458894d0e5e2402bf881 ##### SOURCE BEGIN #####\r\n%% CHEBFUN, Roots\r\n% The ROOTS function in Chebfun is one of its most powerful features.\r\n%\r\n% This is the second part of my series on Chebfun. Part one is\r\n% <http:www.mathworks.com\/cleve\/2012\/10\/01\/chebfun-numerical-computing-with-functions here>.\r\n\r\n%% Roots versus zeros\r\n% Before I wrote this blog I tried to make a distinction between the\r\n% mathematical terms \"roots\" and \"zeros\".  As far as I was concerned,\r\n% equations had \"roots\" while functions had \"zeros\".  The *roots* of\r\n% the equation $x^3 = 2x + 5$ were the *zeros* of the polynomial\r\n% $x^3 - 2x - 5$.  But now I've decided to stop trying to make that\r\n% distinction.\r\n\r\n%%\r\n% The MATLAB function |roots| finds all of the roots of a polynomial.\r\n% No equation or interval or starting approximation is involved.\r\n% But |roots| applies only to polynomials.\r\n% The MATLAB function |fzero| finds only one zero of a function,\r\n% not an equation, near a specified starting value or, better yet,\r\n% in a specified interval.\r\n% To find many zeros you have to call |fzero| repeatedly with\r\n% carefully chosen starting values.\r\n% So MATLAB does not make the rigorous distinction between roots and\r\n% zeros that I used to desire.\r\n\r\n%%\r\n% Chebfun has a very powerful and versatile function named |roots|.\r\n% A |chebfun| is a highly accurate polynomial approximation to a smooth\r\n% function, so the |roots| of a chebfun, which are the roots of a\r\n% polynomial, are usually excellent approximations to the zeros of the\r\n% underlying function.  And Chebfun's |roots| will find all of them\r\n% in the interval of definition, not just one.\r\n\r\n%%\r\n% So, Chebfun has helped convince me to stop trying to distinguish between\r\n% \"roots\" and \"zeros\".\r\n\r\n%% Companion and colleague matrices.\r\n% When I was writing the first MATLAB years ago I was focused on matrix\r\n% computation and was concerned about code size and memory space, so when\r\n% I added |roots| for polynomials I simply formed the companion matrix\r\n% and found its eigenvalues.  That was a novel approach for polynomial root\r\n% finding at the time, but it has proved effective and is still used by the\r\n% MATLAB |roots| function today.\r\n\r\n%%\r\n% Chebfun continues that approach by employing _colleague_ matrices for\r\n% the Chebfun |roots| function.  I had never heard of colleague matrices\r\n% until the Oxford workshop a few weeks ago.  The eigenvalues of the\r\n% colleague matrix associated with a Chebyshev polynomial provide the roots\r\n% of that polynomial in the same way that the eigenvalues of the companion\r\n% matrix associated with a monic polynomial provide its roots.\r\n\r\n%% Bessel function example\r\n% Let's pursue an example involving a fractional order Bessel function.\r\n% Because of the fractional order, this function has a mild singularity\r\n% at the origin, so we should turn on Chebfun's |splitting| option.\r\n\r\nhelp splitting\r\nsplitting on\r\n\r\n%%\r\n\r\nformat compact\r\nnu = 4\/3\r\na = 25\r\nJ = chebfun(@(x) besselj(nu,x),[0 a]);\r\nlengthJ = length(J)\r\nplot(J)\r\nxlabel('x')\r\ntitle('J_{4\/3}(x)')\r\n\r\n%%\r\n% Here are all of our example function's zeros in the interval.\r\n\r\nr = roots(J)\r\nhold on\r\nplot(r,0*r,'r.')\r\nhold off\r\n\r\n%%\r\n% Without Chebfun, that would have required _apriori_ knowledge about the\r\n% number and approximate location of the zeros in the interval and then\r\n% a |for| loop around calls to |fzero|.\r\n\r\n%% Hidden uses\r\n% Chebfun frequently invokes |roots| where it might not be obvious.\r\n% For example, finding the absolute value of a function involves\r\n% finding its zeros.\r\nplot(abs(J))\r\nxlabel('x')\r\ntitle('|J_{4\/3}(x)|')\r\n\r\n%%\r\n% Let's find the zeros of the first derivative so we can plot circles\r\n% at the local maxima.  The derivative is computed by differentiating\r\n% the Chebyshev polynomial, not by symbolic differentiation of the\r\n% Bessel function.\r\nz = roots(diff(J))\r\nhold on\r\nplot(z,abs(J(z)),'ko')\r\nhold off\r\n\r\n##### SOURCE END ##### 3f356c9f5ada458894d0e5e2402bf881\r\n-->","protected":false},"excerpt":{"rendered":"<!--introduction-->\r\n\r\nThe ROOTS function in Chebfun is one of its most powerful features.\r\n\r\nThis is the second part of my series on Chebfun. Part one is <a href=\"https:\/\/blogs.mathworks.com\/cleve\/2012\/10\/01\/chebfun-numerical-computing-with-functions\/\">here<\/a>.\r\n\r\n<!--\/introduction-->... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/cleve\/2012\/10\/08\/chebfun-roots\/\">read more >><\/a><\/p>","protected":false},"author":78,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[11],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/336"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/users\/78"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/comments?post=336"}],"version-history":[{"count":12,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/336\/revisions"}],"predecessor-version":[{"id":2451,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/336\/revisions\/2451"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media?parent=336"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/categories?post=336"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/tags?post=336"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}