{"id":29503,"date":"2017-11-18T13:03:57","date_gmt":"2017-11-18T19:03:57","guid":{"rendered":"https:\/\/www.johndcook.com\/blog\/?p=29503"},"modified":"2024-05-20T15:00:19","modified_gmt":"2024-05-20T20:00:19","slug":"runge-phenomena","status":"publish","type":"post","link":"https:\/\/www.johndcook.com\/blog\/2017\/11\/18\/runge-phenomena\/","title":{"rendered":"Runge phenomena"},"content":{"rendered":"

I’ve mentioned the Runge phenomenon in a couple<\/a> posts<\/a> before. Here I’m going to go into a little more detail.<\/p>\n

First of all, the “Runge” here is Carl David Tolm\u00e9 Runge, better known for the Runge-Kutta algorithm<\/a> for numerically solving differential equations. His name rhymes with cowabunga<\/em>, not with sponge<\/em>.<\/p>\n

Runge showed that polynomial interpolation at evenly-spaced points can fail spectacularly to converge. His example is the function f<\/em>(x<\/em>) = 1\/(1 + x<\/em>\u00b2) on the interval [\u22125, 5], or equivalently, and more convenient here, the function f<\/em>(x<\/em>) = 1\/(1 + 25x<\/em>\u00b2) on the interval [\u22121, 1]. Here’s an example with 16 interpolation nodes.<\/p>\n

\"Runge's<\/p>\n

Runge found that in order for interpolation at evenly spaced nodes in [\u22121, 1] to converge, the function being interpolated needs to be analytic inside a football-shaped [1] region of the complex plane with major axis [\u22121, 1] on the real axis and minor axis approximately [\u22120.5255, 0.5255]\u00a0 on the imaginary axis. For more details, see [2].<\/p>\n

The function in Runge’s example has a singularity at 0.2i<\/em>, which is inside the football. Linear interpolation at evenly spaced points would converge for the function\u00a0f<\/em>(x<\/em>) = 1\/(1 + x<\/em>\u00b2) since the singularity at i<\/em> is outside the football.<\/p>\n

\"Runge's<\/p>\n

For another example, consider the function\u00a0f<\/em>(x<\/em>) = exp(\u22121\/x<\/em>\u00b2) , defined to be 0 at 0. This function is infinitely differentiable but it is not analytic at the origin. With only 16 interpolation points as above, there’s a small indication of trouble at the ends.<\/p>\n

\"Interpolating<\/p>\n

With 28 interpolation points in the plot below, the lack of convergence is clear.<\/p>\n

\"Interpolating<\/p>\n

The problem is not polynomial interpolation\u00a0per se<\/em> but polynomial interpolation at evenly-spaced nodes. Interpolation at Chebyshev points converges for the examples here. The location of singularities effects the rate<\/em> of convergence but not whether the interpolants converge.<\/p>\n

Related<\/strong>:\u00a0Help with interpolation<\/a><\/p>\n

***<\/p>\n

[1] American football, that is. The region is like an ellipse but pointy at \u22121 and 1.<\/p>\n

[2] Approximation Theory and Approximation Practice<\/a> by Lloyd N. Trefethen<\/p>\n","protected":false},"excerpt":{"rendered":"

I’ve mentioned the Runge phenomenon in a couple posts before. Here I’m going to go into a little more detail. First of all, the “Runge” here is Carl David Tolm\u00e9 Runge, better known for the Runge-Kutta algorithm for numerically solving differential equations. His name rhymes with cowabunga, not with sponge. Runge showed that polynomial interpolation […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[9],"tags":[195,166,229],"class_list":["post-29503","post","type-post","status-publish","format-standard","hentry","category-math","tag-interpolation","tag-math","tag-numerical-analysis"],"acf":[],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\n","aioseo_head_json":{"title":"Runge phenomenon for interpolation at evenly spaced nodes","description":"Polynomial interpolation at evenly-spaced nodes converges if the function being interpolated is analytic in a football-shaped region centered at the origin.","canonical_url":"https:\/\/www.johndcook.com\/blog\/2017\/11\/18\/runge-phenomena\/","robots":"max-image-preview:large","keywords":"interpolation,math,numerical analysis","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"en_US","og:site_name":"John D. Cook | Applied Mathematics Consulting","og:type":"article","og:title":"Runge phenomenon for interpolation at evenly spaced nodes","og:description":"Polynomial interpolation at evenly-spaced nodes converges if the function being interpolated is analytic in a football-shaped region centered at the origin.","og:url":"https:\/\/www.johndcook.com\/blog\/2017\/11\/18\/runge-phenomena\/","article:published_time":"2017-11-18T19:03:57+00:00","article:modified_time":"2024-05-20T20:00:19+00:00","twitter:card":"summary","twitter:title":"Runge phenomenon for interpolation at evenly spaced nodes","twitter:description":"Polynomial interpolation at evenly-spaced nodes converges if the function being interpolated is analytic in a football-shaped region centered at the origin.","twitter:image":"https:\/\/www.johndcook.com\/blog\/wp-content\/uploads\/2022\/05\/twittercard.png"},"aioseo_meta_data":{"post_id":"29503","title":"Runge phenomenon for interpolation at evenly spaced nodes","description":"Polynomial interpolation at evenly-spaced nodes converges if the function being interpolated is analytic in a football-shaped region centered at the origin.","keywords":null,"keyphrases":{"focus":{"keyphrase":"","score":0,"analysis":{"keyphraseInTitle":{"score":0,"maxScore":9,"error":1}}},"additional":[]},"primary_term":null,"canonical_url":null,"og_title":null,"og_description":null,"og_object_type":"default","og_image_type":"default","og_image_url":null,"og_image_width":null,"og_image_height":null,"og_image_custom_url":null,"og_image_custom_fields":null,"og_video":"","og_custom_url":null,"og_article_section":null,"og_article_tags":null,"twitter_use_og":false,"twitter_card":"default","twitter_image_type":"default","twitter_image_url":null,"twitter_image_custom_url":null,"twitter_image_custom_fields":null,"twitter_title":null,"twitter_description":null,"schema":{"blockGraphs":[],"customGraphs":[],"default":{"data":{"Article":[],"Course":[],"Dataset":[],"FAQPage":[],"Movie":[],"Person":[],"Product":[],"ProductReview":[],"Car":[],"Recipe":[],"Service":[],"SoftwareApplication":[],"WebPage":[]},"graphName":"Article","isEnabled":true},"graphs":[],"defaultGraph":"Article","defaultPostTypeGraph":""},"schema_type":"default","schema_type_options":"{\"article\":{\"articleType\":\"BlogPosting\"},\"course\":{\"name\":\"\",\"description\":\"\",\"provider\":\"\"},\"faq\":{\"pages\":[]},\"product\":{\"reviews\":[]},\"recipe\":{\"ingredients\":[],\"instructions\":[],\"keywords\":[]},\"software\":{\"reviews\":[],\"operatingSystems\":[]},\"webPage\":{\"webPageType\":\"WebPage\"}}","pillar_content":false,"robots_default":true,"robots_noindex":false,"robots_noarchive":false,"robots_nosnippet":false,"robots_nofollow":false,"robots_noimageindex":false,"robots_noodp":false,"robots_notranslate":false,"robots_max_snippet":"-1","robots_max_videopreview":"-1","robots_max_imagepreview":"large","priority":null,"frequency":"default","location":null,"local_seo":null,"breadcrumb_settings":null,"limit_modified_date":false,"created":"2020-12-21 02:36:26","updated":"2025-06-04 00:27:08","ai":null,"seo_analyzer_scan_date":null},"aioseo_breadcrumb":"

\n\t\t\tHome<\/a>\n\t\t<\/span>»<\/span>\n\t\t\tMath<\/a>\n\t\t<\/span>»<\/span>\n\t\t\tRunge phenomena\n\t\t<\/span><\/div>","aioseo_breadcrumb_json":[{"label":"Home","link":"https:\/\/www.johndcook.com\/blog"},{"label":"Math","link":"https:\/\/www.johndcook.com\/blog\/category\/math\/"},{"label":"Runge phenomena","link":"https:\/\/www.johndcook.com\/blog\/2017\/11\/18\/runge-phenomena\/"}],"_links":{"self":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts\/29503","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/comments?post=29503"}],"version-history":[{"count":0,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts\/29503\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/media?parent=29503"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/categories?post=29503"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/tags?post=29503"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}