{"id":4240,"date":"2018-12-10T11:59:26","date_gmt":"2018-12-10T16:59:26","guid":{"rendered":"https:\/\/blogs.mathworks.com\/cleve\/?p=4240"},"modified":"2018-12-12T11:41:46","modified_gmt":"2018-12-12T16:41:46","slug":"explore-runges-polynomial-interpolation-phenomenon","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/cleve\/2018\/12\/10\/explore-runges-polynomial-interpolation-phenomenon\/","title":{"rendered":"Explore Runge&#8217;s Polynomial Interpolation Phenomenon"},"content":{"rendered":"\r\n<div class=\"content\"><!--introduction--><p>As the degree of an interpolating polynomial increases, does the polynomial converge to the underlying function?  The short answer is maybe. I want to describe a visual tool to help you investigate this question yourself.<\/p><!--\/introduction--><h3>Contents<\/h3><div><ul><li><a href=\"#02ee772d-a04d-49ec-956f-907b2db08831\">Carl Runge<\/a><\/li><li><a href=\"#10b4d230-4771-4368-992c-7c23b45e45c8\">interp_gadget<\/a><\/li><li><a href=\"#3cfd64b1-74da-4c3d-8471-9137bb4b3d40\">Vary coefficient<\/a><\/li><li><a href=\"#febeee74-7f80-4418-90f8-9d96703122e8\">Vary number of points<\/a><\/li><li><a href=\"#7490d0bc-a9e1-40ee-a821-bdba9d54fab4\">Vary weight<\/a><\/li><li><a href=\"#d899ab9e-a1f6-4aaf-a96f-06ca77577534\">Initial configuration<\/a><\/li><li><a href=\"#7bd0c375-f70c-4680-a77f-e5c9d1b674be\">High degree<\/a><\/li><li><a href=\"#24831c8e-2933-4dd1-b26a-8460179a9f5a\">Chebyshev distribution<\/a><\/li><li><a href=\"#10ca7317-78d3-4951-8990-96bdb7754250\">Gaussian target<\/a><\/li><li><a href=\"#869de7af-ff0d-4fad-b9df-09a50f091b04\">abs(x)<\/a><\/li><li><a href=\"#a372ac75-5be6-4540-8d5a-25fa9811607b\">Extra credit<\/a><\/li><li><a href=\"#bed085a8-2de1-44bf-b330-9a275746b9e6\">Software<\/a><\/li><\/ul><\/div><h4>Carl Runge<a name=\"02ee772d-a04d-49ec-956f-907b2db08831\"><\/a><\/h4><p>Carl Runge lived from 1856 until 1927.  We know his name because he was the first to write about what we now call the Runge-Kutta method for the numerical solution of ordinary differential equations.  His paper was published in 1895.  Martin Kutta came along six years later. But Runge made many other contributions, including the subject of today's post.<\/p><p>A classical result of Runge's advisor, Karl Weierstrass, is that for any continuous function, <i>there exists<\/i> a sequence of polynomials of increasing order that converge <i>uniformly<\/i> to the function. But this result does not tell us whether the polynomials can be <i>interpolating<\/i> or where the interpolating points might be located.<\/p><p>Runge's famous counterexample for interpolation is the function<\/p><p>$f(x) = \\frac{1}{1+25x^2}$<\/p><p>If this function is interpolated at equally spaced points in the interval [-1,1], the polynomials <i>do not<\/i> converge uniformly. In fact, the maximum error goes to infinity.<\/p><h4>interp_gadget<a name=\"10b4d230-4771-4368-992c-7c23b45e45c8\"><\/a><\/h4><p>I call my MATLAB&reg; program <tt>interp_gadget<\/tt>.  You can vary three parameters, $c$, $n$ and $w$.  You can choose one of the   three target functions involving the coefficient $c$.<\/p><p>$f_1(x) = \\frac{1}{1+c x^2}$<\/p><p>$f_2(x) = e^{-c x^2}$<\/p><p>$f_3(x) = |cx|$<\/p><p>The parameter $n$ is the number of interpolation points in the interval [-1 1].  The degree of the interpolating polynomial is $n-1$.<\/p><p>The distribution of the points involves the weight $w$. The points are a weighted average between equally spaced points and Chebyshev points concentrated towards the end of the interval.<\/p><p>$x_{ch} = \\cos({\\frac{n-\\frac{1}{2}:-1:\\frac{1}{2}}{n}\\pi})$<\/p><p>$x_{eq} = -1:\\frac{2}{n-1}:1$<\/p><p>$x = wx_{ch} + (1-w)x_{eq}$<\/p><p>The green curve in the following animations and plots is the target function $f(x)$ and the blue curve is the polynomial that interpolates the target at the blue circles. The interpolation error is the difference between the two curves.<\/p><h4>Vary coefficient<a name=\"3cfd64b1-74da-4c3d-8471-9137bb4b3d40\"><\/a><\/h4><p>Let's vary the coefficient $c$ in the bell-shaped target $f_1$, while keeping the number of equally spaced points fixed. The value $c = 25$ gives us Runge's function.  As $c$ increases, the peak in the target becomes sharper and the interpolation error increases.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/c_animation.gif\" alt=\"\"> <\/p><h4>Vary number of points<a name=\"febeee74-7f80-4418-90f8-9d96703122e8\"><\/a><\/h4><p>Let's vary the number of points, while keeping the target fixed and the points equally spaced.  As $n$ increases, we see the error near the ends of the interval increase dramatically.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/n_animation.gif\" alt=\"\"> <\/p><h4>Vary weight<a name=\"7490d0bc-a9e1-40ee-a821-bdba9d54fab4\"><\/a><\/h4><p>Let's vary the weight in the point distribution.  As we move from equal spacing towards Chebyshev spacing, the error near the end points decreases significantly.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/w_animation.gif\" alt=\"\"> <\/p><h4>Initial configuration<a name=\"d899ab9e-a1f6-4aaf-a96f-06ca77577534\"><\/a><\/h4><p>Now some static plots comparing a few different settings of the parameters.  Here is the initial setting with Runge's value of $c$ and nine equally spaced interpolation points.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/static_1.gif\" alt=\"\"> <\/p><h4>High degree<a name=\"7bd0c375-f70c-4680-a77f-e5c9d1b674be\"><\/a><\/h4><p>Increase the number of points while keeping them equally spaced.  There is trouble near the end points.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/static_2.gif\" alt=\"\"> <\/p><h4>Chebyshev distribution<a name=\"24831c8e-2933-4dd1-b26a-8460179a9f5a\"><\/a><\/h4><p>Distributing a modest number of points nearer the ends of the interval is a big improvement.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/static_3.gif\" alt=\"\"> <\/p><h4>Gaussian target<a name=\"10ca7317-78d3-4951-8990-96bdb7754250\"><\/a><\/h4><p>The Gaussian target $f_2(x)$ behaves pretty much like Runge's.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/static_4.gif\" alt=\"\"> <\/p><h4>abs(x)<a name=\"869de7af-ff0d-4fad-b9df-09a50f091b04\"><\/a><\/h4><p>Behavior with the target $f_3(x)$ warrants further investigation.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/static_5.gif\" alt=\"\"> <\/p><h4>Extra credit<a name=\"a372ac75-5be6-4540-8d5a-25fa9811607b\"><\/a><\/h4><p>Here is Runge's example again, with many equally spaced interpolation points.  I've added red lines at $x = \\pm .726$. In section 3.4 of a classic numerical analysis text that is now available as an inexpensive Dover reprint, <a href=\"http:\/\/store.doverpublications.com\/0486680290.html\">Dover link<\/a>, Eugene Isaacson and Herb Keller begin a proof of the fact that polynomial interpolation converges for $x$ between these red lines and diverges for $x$ outside them.  But a key portion of their proof is left as an exercise.<\/p><p>So, I have a few tasks for those inclined to undertake them. The first is to finish Isaacson and Keller's argument, which explains where the $.726$ comes from.  How does $.726$ depend on the coefficient $c$ in function $f_1(x)$?  Where are the red lines for our two other target functions?  How does their location depend upon $w$?<\/p><p>I don't know the answers to these questions.  If you discover something, please let us know in the comments.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/static_6.gif\" alt=\"\"> <\/p><h4>Software<a name=\"bed085a8-2de1-44bf-b330-9a275746b9e6\"><\/a><\/h4><p>I have submitted <tt>interp_gadget<\/tt> to the MATLAB Central file exchange, available at <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/69676\">this link<\/a>.  It is also included in version 4.01 of Cleve's Laboratory, available at <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/59085-cleve-laboratory\">this link<\/a>.<\/p><script language=\"JavaScript\"> <!-- \r\n    function grabCode_338bf3a5184d4c90a6dc1e70422ea70a() {\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='338bf3a5184d4c90a6dc1e70422ea70a ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 338bf3a5184d4c90a6dc1e70422ea70a';\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 2018 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_338bf3a5184d4c90a6dc1e70422ea70a()\"><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; R2018b<br><\/p><\/div><!--\r\n338bf3a5184d4c90a6dc1e70422ea70a ##### SOURCE BEGIN #####\r\n%% Explore Runge's Polynomial Interpolation Phenomenon\r\n% As the degree of\r\n% an interpolating polynomial increases, does the polynomial converge\r\n% to the underlying function?  The short answer is maybe.\r\n% I want to describe a visual tool to help you investigate this\r\n% question yourself.\r\n\r\n%% Carl Runge\r\n% Carl Runge lived from 1856 until 1927.  We know his name because\r\n% he was the first to write about what we now call the Runge-Kutta method\r\n% for the numerical solution of ordinary differential equations.  His\r\n% paper was published in 1895.  Martin Kutta came along six years later.\r\n% But Runge made many other contributions, including the subject of\r\n% today's post.\r\n\r\n%%\r\n% A classical result of Runge's advisor, Karl Weierstrass, is that\r\n% for any continuous function, _there exists_ a sequence of polynomials\r\n% of increasing order that converge _uniformly_ to the function.\r\n% But this result does not tell us whether the polynomials can be\r\n% _interpolating_ or where the interpolating points might be located.\r\n\r\n%%\r\n% Runge's famous counterexample for interpolation is the function\r\n%\r\n% $f(x) = \\frac{1}{1+25x^2}$\r\n%\r\n% If this function is interpolated at equally spaced points in the\r\n% interval [-1,1], the polynomials _do not_ converge uniformly.\r\n% In fact, the maximum error goes to infinity.\r\n\r\n%% interp_gadget\r\n% I call my MATLAB(R) program |interp_gadget|.  You can vary three\r\n% parameters, $c$, $n$ and $w$.  You can choose one of the   three\r\n% target functions involving the coefficient $c$.\r\n%\r\n% $f_1(x) = \\frac{1}{1+c x^2}$\r\n%\r\n%\r\n% $f_2(x) = e^{-c x^2}$\r\n%\r\n%\r\n% $f_3(x) = |cx|$\r\n\r\n%%\r\n% The parameter $n$ is the number of interpolation points in the interval\r\n% [-1 1].  The degree of the interpolating polynomial is $n-1$.\r\n\r\n%%\r\n% The distribution of the points involves the weight $w$.\r\n% The points are a weighted average between equally spaced points\r\n% and Chebyshev points concentrated towards the end of the interval.\r\n%\r\n% $x_{ch} = \\cos({\\frac{n-\\frac{1}{2}:-1:\\frac{1}{2}}{n}\\pi})$\r\n%\r\n% $x_{eq} = -1:\\frac{2}{n-1}:1$\r\n%\r\n% $x = wx_{ch} + (1-w)x_{eq}$\r\n%\r\n% The green curve in the following animations and plots\r\n% is the target function $f(x)$ and the blue curve is the polynomial\r\n% that interpolates the target at the blue circles.\r\n% The interpolation error is the difference between the two curves.\r\n\r\n%% Vary coefficient\r\n% Let's vary the coefficient $c$ in the bell-shaped target $f_1$,\r\n% while keeping the number of equally spaced points fixed.\r\n% The value $c = 25$ gives us Runge's function.  As $c$ increases, \r\n% the peak in the target becomes sharper and the interpolation error\r\n% increases.\r\n%\r\n% <<c_animation.gif>>\r\n\r\n%% Vary number of points\r\n% Let's vary the number of points, while keeping the target fixed\r\n% and the points equally spaced.  As $n$ increases, we see the error\r\n% near the ends of the interval increase dramatically.\r\n%\r\n% <<n_animation.gif>>\r\n\r\n\r\n%% Vary weight\r\n% Let's vary the weight in the point distribution.  As we move from equal\r\n% spacing towards Chebyshev spacing, the error near the end points\r\n% decreases significantly.\r\n%\r\n% <<w_animation.gif>>\r\n\r\n%% Initial configuration\r\n% Now some static plots comparing a few different settings of the\r\n% parameters.  Here is the initial setting with Runge's value of $c$\r\n% and nine equally spaced interpolation points.\r\n%\r\n% <<static_1.gif>>\r\n\r\n%% High degree\r\n% Increase the number of points while keeping them equally\r\n% spaced.  There is trouble near the end points.\r\n%\r\n% <<static_2.gif>>\r\n\r\n%% Chebyshev distribution\r\n% Distributing a modest number of points nearer the ends of the interval\r\n% is a big improvement.\r\n%\r\n% <<static_3.gif>>\r\n\r\n%% Gaussian target\r\n% The Gaussian target $f_2(x)$ behaves pretty much like Runge's.\r\n%\r\n% <<static_4.gif>>\r\n\r\n%% abs(x)\r\n% Behavior with the target $f_3(x)$ warrants further investigation.\r\n%\r\n% <<static_5.gif>>\r\n\r\n%% Extra credit\r\n% Here is Runge's example again, with many equally spaced interpolation\r\n% points.  I've added red lines at $x = \\pm .726$.\r\n% In section 3.4 of a classic numerical analysis text that is now\r\n% available as an inexpensive Dover reprint,\r\n% <http:\/\/store.doverpublications.com\/0486680290.html Dover link>,\r\n% Eugene Isaacson and Herb Keller begin a proof of the fact that\r\n% polynomial interpolation converges for $x$ between these red lines\r\n% and diverges for $x$ outside them.  But a key portion of\r\n% their proof is left as an exercise.\r\n%\r\n% So, I have a few tasks for those inclined to undertake them.\r\n% The first is to finish Isaacson and Keller's argument, which explains\r\n% where the $.726$ comes from.  How does $.726$ depend on the coefficient\r\n% $c$ in function $f_1(x)$?  Where are the red lines for our\r\n% two other target functions?  How does their location depend upon $w$?\r\n%\r\n% I don't know the answers to these questions.  If you discover\r\n% something, please let us know in the comments.\r\n% \r\n% <<static_6.gif>>\r\n\r\n\r\n%% Software\r\n% I have submitted |interp_gadget| to the MATLAB Central file exchange,\r\n% available at\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/69676\r\n% this link>.  It is also included in version 4.01 of\r\n% Cleve's Laboratory, available at\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/59085-cleve-laboratory\r\n% this link>.\r\n##### SOURCE END ##### 338bf3a5184d4c90a6dc1e70422ea70a\r\n-->","protected":false},"excerpt":{"rendered":"<div class=\"overview-image\"><img src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/static_1.gif\" class=\"img-responsive attachment-post-thumbnail size-post-thumbnail wp-post-image\" alt=\"\" decoding=\"async\" loading=\"lazy\" \/><\/div><!--introduction--><p>As the degree of an interpolating polynomial increases, does the polynomial converge to the underlying function?  The short answer is maybe. I want to describe a visual tool to help you investigate this question yourself.... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/cleve\/2018\/12\/10\/explore-runges-polynomial-interpolation-phenomenon\/\">read more >><\/a><\/p>","protected":false},"author":78,"featured_media":4320,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[12,16,8],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/4240"}],"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=4240"}],"version-history":[{"count":5,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/4240\/revisions"}],"predecessor-version":[{"id":4360,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/4240\/revisions\/4360"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media\/4320"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media?parent=4240"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/categories?post=4240"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/tags?post=4240"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}