{"id":1284,"date":"2015-11-09T12:00:46","date_gmt":"2015-11-09T17:00:46","guid":{"rendered":"https:\/\/blogs.mathworks.com\/cleve\/?p=1284"},"modified":"2016-08-05T16:12:46","modified_gmt":"2016-08-05T21:12:46","slug":"zeroin-part-3-matlab-zero-finder-fzero","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/cleve\/2015\/11\/09\/zeroin-part-3-matlab-zero-finder-fzero\/","title":{"rendered":"Zeroin, Part 3: MATLAB Zero Finder, FZERO"},"content":{"rendered":"<div class=\"content\"><!--introduction--><p>MATLAB adds capability to search for an interval with a sign change.<\/p><!--\/introduction--><h3>Contents<\/h3><div><ul><li><a href=\"#e7e8d656-c258-43e3-b1f2-82c51a0eaecf\">Seeking a sign change.<\/a><\/li><li><a href=\"#72aaeb69-3fc4-43d1-99a2-74d4178ea30f\">MathWorks addition<\/a><\/li><li><a href=\"#18913c49-78db-4e23-8907-20a5cc97d455\">An example<\/a><\/li><\/ul><\/div><h4>Seeking a sign change.<a name=\"e7e8d656-c258-43e3-b1f2-82c51a0eaecf\"><\/a><\/h4><p>We are looking for a zero of a real-valued function, $f(x)$, of a real variable, $x$.  All of the versions of <i>zeroin<\/i> that I have described in the previous posts in this series, <a href=\"https:\/\/blogs.mathworks.com\/cleve\/2015\/10\/12\/zeroin-part-1-dekkers-algorithm\/\">part 1<\/a> and <a href=\"https:\/\/blogs.mathworks.com\/cleve\/2015\/10\/26\/zeroin-part-2-brents-version\/\">part 2<\/a>, have required a starting interval $[a,b]$ with a sign change. What if we don't know such an interval?<\/p><h4>MathWorks addition<a name=\"72aaeb69-3fc4-43d1-99a2-74d4178ea30f\"><\/a><\/h4><p>MathWorks added the possibility of a search for a sign change to precede the Dekker\/Brent <i>zeroin<\/i>.  The algorithm is straightforward. Start at a single given $x$.  Take an interval centered at $x$ with half-width $x\/50$.  Evaluate $f(x)$ at the interval endpoints. If the signs match, increase the interval width by a factor $\\sqrt{2}$ and repeat until a sign change is detected.<\/p><p>Here is a bit of code.<\/p><pre class=\"codeinput\">   type <span class=\"string\">signchange<\/span>\r\n<\/pre><pre class=\"codeoutput\">\r\nfunction [a,b] = signchange(f,x)\r\n% SIGNCHANGE [a,b] = signchance(f,x) seeks an\r\n% interval [a,b] where f(x) changes sign.\r\n\r\n   a = x;\r\n   b = x;\r\n   if x ~= 0\r\n      dx = x\/50;\r\n   else\r\n      dx = 1\/50;\r\n   end\r\n   while sign(f(a)) == sign(f(b))\r\n      dx = sqrt(2)*dx;\r\n      a = x - dx;\r\n      b = x + dx;\r\n   end\r\nend\r\n   \r\n\r\n<\/pre><h4>An example<a name=\"18913c49-78db-4e23-8907-20a5cc97d455\"><\/a><\/h4><p>Let's compute $\\sqrt{2}$ by using the full-blown <tt>fzero<\/tt> from the MATLAB library to find a zero of $2-x^2$.<\/p><pre class=\"codeinput\"><span class=\"comment\">%  f = @(x) 2 - x^2;<\/span>\r\n<\/pre><p>Set a display parameter asking for intermediate results.<\/p><pre class=\"codeinput\"><span class=\"comment\">%  opt = optimset('display','iter');<\/span>\r\n<\/pre><p>Start the search a $x = 1$.<\/p><pre class=\"codeinput\"><span class=\"comment\">%  fzero(f,1,opt)<\/span>\r\n<\/pre><p>We get one line of output each time <tt>a<\/tt> is decreased and <tt>b<\/tt> is increased. All the values of <tt>f(a)<\/tt> are positive and all the values of <tt>f(b)<\/tt> are also positive until <tt>b = 1.452548<\/tt> when the first sign change is reached.<\/p><pre class=\"codeinput\"><span class=\"comment\">%  Search for an interval around 1 containing a sign change:<\/span>\r\n<span class=\"comment\">%   Func-count    a          f(a)             b          f(b)        Procedure<\/span>\r\n<span class=\"comment\">%      1        1.000000      1.000000      1.000000      1.000000   initial interval<\/span>\r\n<span class=\"comment\">%      3        0.971716      1.055769      1.028284      0.942631   search<\/span>\r\n<span class=\"comment\">%      5        0.960000      1.078400      1.040000      0.918400   search<\/span>\r\n<span class=\"comment\">%      7        0.943431      1.109937      1.056569      0.883663   search<\/span>\r\n<span class=\"comment\">%      9        0.920000      1.153600      1.080000      0.833600   search<\/span>\r\n<span class=\"comment\">%     11        0.886863      1.213474      1.113137      0.760926   search<\/span>\r\n<span class=\"comment\">%     13        0.840000      1.294400      1.160000      0.654400   search<\/span>\r\n<span class=\"comment\">%     15        0.773726      1.401348      1.226274      0.496252   search<\/span>\r\n<span class=\"comment\">%     17        0.680000      1.537600      1.320000      0.257600   search<\/span>\r\n<span class=\"comment\">%     19        0.547452      1.700297      1.452548     -0.109897   search<\/span>\r\n<\/pre><p>Now the classic <i>zeroin<\/i> algorithm can reliably and rapidly find the zero.<\/p><pre class=\"codeinput\"><span class=\"comment\">%  Search for a zero in the interval [0.547452, 1.45255]:<\/span>\r\n<span class=\"comment\">%   Func-count    x          f(x)             Procedure<\/span>\r\n<span class=\"comment\">%     19        1.452548     -0.109897        initial<\/span>\r\n<span class=\"comment\">%     20        1.397600     0.0467142        interpolation<\/span>\r\n<span class=\"comment\">%     21        1.413990   0.000631974        interpolation<\/span>\r\n<span class=\"comment\">%     22        1.414214  -9.95025e-08        interpolation<\/span>\r\n<span class=\"comment\">%     23        1.414214   7.86149e-12        interpolation<\/span>\r\n<span class=\"comment\">%     24        1.414214  -4.44089e-16        interpolation<\/span>\r\n<span class=\"comment\">%     25        1.414214  -4.44089e-16        interpolation<\/span>\r\n<span class=\"comment\">%<\/span>\r\n<span class=\"comment\">%  Zero found in the interval [0.547452, 1.45255]<\/span>\r\n<span class=\"comment\">%<\/span>\r\n<span class=\"comment\">%  ans =<\/span>\r\n<span class=\"comment\">%     1.414213562373095<\/span>\r\n<\/pre><p>Here is a plot showing where the search for the sign change is carried out. The search begins in the center, expands symmetrically to the left and right, and succeeds when the negative value at the far right is discovered.<\/p><pre class=\"codeinput\">   zeroin_blog3plot\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/cleve\/zeroin_blog3_01.png\" alt=\"\"> <script language=\"JavaScript\"> <!-- \r\n    function grabCode_f053a23ba51c4684b6af9fd088c9f960() {\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='f053a23ba51c4684b6af9fd088c9f960 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' f053a23ba51c4684b6af9fd088c9f960';\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 2015 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('<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>\\n');\r\n\r\n        d.title = title + ' (MATLAB code)';\r\n        d.close();\r\n    }   \r\n     --> <\/script><p style=\"text-align: right; font-size: xx-small; font-weight:lighter;   font-style: italic; color: gray\"><br><a href=\"javascript:grabCode_f053a23ba51c4684b6af9fd088c9f960()\"><span style=\"font-size: x-small;        font-style: italic;\">Get \r\n      the MATLAB code <noscript>(requires JavaScript)<\/noscript><\/span><\/a><br><br>\r\n      Published with MATLAB&reg; R2015a<br><\/p><\/div><!--\r\nf053a23ba51c4684b6af9fd088c9f960 ##### SOURCE BEGIN #####\r\n%% ZEROIN, Part 3: MATLAB Zero Finder, Fzero\r\n% MATLAB adds capability to search for an interval with a sign change.\r\n\r\n%% Seeking a sign change.\r\n% We are looking for a zero of a real-valued function, $f(x)$, of a real\r\n% variable, $x$.  All of the versions of _zeroin_ that I have described\r\n% in the previous posts in this series,\r\n% <https:\/\/blogs.mathworks.com\/cleve\/2015\/10\/12\/zeroin-part-1-dekkers-algorithm\/\r\n% part 1> and\r\n% <https:\/\/blogs.mathworks.com\/cleve\/2015\/10\/26\/zeroin-part-2-brents-version\/\r\n% part 2>, have required a starting interval $[a,b]$ with a sign change.\r\n% What if we don't know such an interval?\r\n\r\n%% MathWorks addition\r\n% MathWorks added the possibility of a search for a sign change to precede\r\n% the Dekker\/Brent _zeroin_.  The algorithm is straightforward.\r\n% Start at a single given $x$.  Take an interval centered at $x$ with\r\n% half-width $x\/50$.  Evaluate $f(x)$ at the interval endpoints.\r\n% If the signs match, increase the interval width by a factor $\\sqrt{2}$\r\n% and repeat until a sign change is detected.\r\n\r\n%%\r\n% Here is a bit of code.\r\n\r\n   type signchange\r\n\r\n%% An example\r\n% Let's compute $\\sqrt{2}$ by using the full-blown |fzero| from the\r\n% MATLAB library to find a zero of $2-x^2$.\r\n\r\n%  f = @(x) 2 - x^2;\r\n\r\n%% \r\n% Set a display parameter asking for intermediate results.\r\n\r\n%  opt = optimset('display','iter');\r\n\r\n%%\r\n% Start the search a $x = 1$.\r\n\r\n%  fzero(f,1,opt)\r\n\r\n%%\r\n% We get one line of output each time |a| is decreased and |b| is increased.\r\n% All the values of |f(a)| are positive and all the values of |f(b)| are\r\n% also positive until |b = 1.452548| when the first sign change is reached.\r\n\r\n%  Search for an interval around 1 containing a sign change:\r\n%   Func-count    a          f(a)             b          f(b)        Procedure\r\n%      1        1.000000      1.000000      1.000000      1.000000   initial interval\r\n%      3        0.971716      1.055769      1.028284      0.942631   search\r\n%      5        0.960000      1.078400      1.040000      0.918400   search\r\n%      7        0.943431      1.109937      1.056569      0.883663   search\r\n%      9        0.920000      1.153600      1.080000      0.833600   search\r\n%     11        0.886863      1.213474      1.113137      0.760926   search\r\n%     13        0.840000      1.294400      1.160000      0.654400   search\r\n%     15        0.773726      1.401348      1.226274      0.496252   search\r\n%     17        0.680000      1.537600      1.320000      0.257600   search\r\n%     19        0.547452      1.700297      1.452548     -0.109897   search\r\n\r\n%%\r\n% Now the classic _zeroin_ algorithm can reliably and rapidly find the zero.\r\n\r\n%  Search for a zero in the interval [0.547452, 1.45255]:\r\n%   Func-count    x          f(x)             Procedure\r\n%     19        1.452548     -0.109897        initial\r\n%     20        1.397600     0.0467142        interpolation\r\n%     21        1.413990   0.000631974        interpolation\r\n%     22        1.414214  -9.95025e-08        interpolation\r\n%     23        1.414214   7.86149e-12        interpolation\r\n%     24        1.414214  -4.44089e-16        interpolation\r\n%     25        1.414214  -4.44089e-16        interpolation\r\n%   \r\n%  Zero found in the interval [0.547452, 1.45255]\r\n%  \r\n%  ans =\r\n%     1.414213562373095\r\n\r\n%%\r\n% Here is a plot showing where the search for the sign change is carried out.\r\n% The search begins in the center, expands symmetrically to the\r\n% left and right, and succeeds when the negative value at the\r\n% far right is discovered.\r\n%\r\n   zeroin_blog3plot\r\n\r\n##### SOURCE END ##### f053a23ba51c4684b6af9fd088c9f960\r\n-->","protected":false},"excerpt":{"rendered":"<div class=\"overview-image\"><img decoding=\"async\"  class=\"img-responsive\" src=\"https:\/\/blogs.mathworks.com\/images\/cleve\/zeroin_blog3_01.png\" onError=\"this.style.display ='none';\" \/><\/div><!--introduction--><p>MATLAB adds capability to search for an interval with a sign change.... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/cleve\/2015\/11\/09\/zeroin-part-3-matlab-zero-finder-fzero\/\">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,4,16],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/1284"}],"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=1284"}],"version-history":[{"count":3,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/1284\/revisions"}],"predecessor-version":[{"id":1315,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/1284\/revisions\/1315"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media?parent=1284"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/categories?post=1284"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/tags?post=1284"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}