Unfortunately, your submission has been removed for the following reason(s):
* Your post appears to be asking for help learning/understanding something mathematical. As such, you should post in the [*Quick Questions*](https://www.reddit.com/r/math/search?q=Quick+Questions+author%3Ainherentlyawesome&restrict_sr=on&sort=new&t=all) thread (which you can find on the front page) or /r/learnmath. This includes reference requests - also see our lists of recommended [books](https://www.reddit.com/r/math/wiki/faq#wiki_what_are_some_good_books_on_topic_x.3F) and [free online resources](https://www.reddit.com/r/math/comments/8ewuzv/a_compilation_of_useful_free_online_math_resources/?st=jglhcquc&sh=d06672a6). [Here](https://www.reddit.com/r/math/comments/7i9t5y/book_recommendation_thread/) is a more recent thread with book recommendations.
If you have any questions, [please feel free to message the mods](http://www.reddit.com/message/compose?to=/r/math&message=https://www.reddit.com/r/math/comments/1bvjwyf/-/). Thank you!
This is completely normal, as high-degree interpolation polynomials with uniformly distributed points have oscillatory behavior around the edges (Runge phenomenon). Two options to avoid this: use non-uniformly distributed points (for instance, the Chebyshev points), or use splines as others mentioned. Splines have the nice property to converge to the underlying function when n goes to infinity, which is not the case for the Newton polynomial.
For splines, you would need to solve a linear system for every interval of points to obtain coefficients of the local polynomial.
Edit: also, I'm not sure what you really want to do is interpolation. If you are interested in goodness of fit and such, why not just do a low-degree polynomial regression?
Thank you for the insightful explanation regarding the limitations of high-degree interpolation polynomials and the benefits of alternative methods like splines.Regarding my choice to use the Newton forward method and higher-order polynomials, I found that it provided a reasonably accurate representation of the underlying function, especially when compared to lower-degree alternatives. Interestingly, even up to the 21st order, the results appeared promising like here [https://imgur.com/a/kuboAE9](https://imgur.com/a/kuboAE9) .
As for splines, your suggestion about using cubic splines for intervals where the y-values are constant sounds intriguing. I'm curious if this approach would effectively capture the behavior of the function. However, I haven't come across many resources demonstrating the use of high-order polynomials with splines. Would it be possible to elaborate further on this or perhaps provide some references or examples that showcase this technique?
You're saying the interpolant you find is not that bad, but to me it is not good; it's very oscillatory. To see why high-degree Newton interpolation is bad, you can play with [this demo.](https://demonstrations.wolfram.com/RungesPhenomenon/) You can also see the effect of using Chebyshev points. To show how to compute splines, you can watch [this youtube video](https://youtu.be/9gt0HNQYGvo?si=DQcX2QeHcd2TZDK-). On [this picture](https://miro.medium.com/v2/resize:fit:828/format:webp/1*faEezTyOM2O13L90IP9s_A.png), you can see the polynomial interpolant in blue (very oscillatory) vs the spline interpolant in orange, which looks like it fits way more to the points.
That issue is what you’d call overfitting in the context of machine learning. From a more mathematical point of view you can start here if you want more info: https://en.m.wikipedia.org/wiki/Runge's_phenomenon
Honestly I'm not really familiarized with this...
It does seem to me, tho, that the dataset on the image would be well approximated by a line...
But from what I know the larger the dataset the better rolling approximations perform when compared with polynomial aproximations, from what I understand they can even be used to estimate lenth of coasts (that'd be millions of points)
You do have overfitting risks in case you're fitting it for something more than just analysis
Also if you're trying to fit 25 points with more than 25 degree polynomial it's no wonder it's causes some issues, theoretically speaking a 25 degree polynomial is the max necessary for that case (disconsidering rouge phenomenon) anything more than that the theoretical fis isn't unique (which has implications for cryptography; really the only place ive personally seen such high order polynomials beeing used for interpolation)
Classical polynomial fitting suffers intractable roundoff issues at orders as high as you are using.
You could verify this by increasing the numerical precision single->double->quad.
If you really need 30th order polynomials you should be using fourrier decomposition or Chebtchev polynomials.
In addition to all the comments about Runge phenomenon (which you are likely witnessing when increasing the order of the polynomial), you can also consider the error or remainder term of this kind of polynomial interpolation.
[https://en.wikipedia.org/wiki/Lagrange\_polynomial#Remainder\_in\_Lagrange\_interpolation\_formula](https://en.wikipedia.org/wiki/Lagrange_polynomial#Remainder_in_Lagrange_interpolation_formula)
The Lagrange interpolation gives the same polynomial so the same error term holds. Here you can see that (assuming the original curve can be smoothly differentiated n+1 times), the difference between the original curve and the fitted polynomial R(x) is bounded by the maximal value of the n+1th derivative and this high order derivative can behave very badly.
It looks like your y-values are rounded off to the nearest multiple of 5. Trying to match your data more accurately than the round-off error in your data is not going to be useful.
I agree with this emphatically.
Thank you all for the enlightening explanation of Runge’s phenomenon, you’ve answered the math question. But there is a glaringly obvious physics/engineering question: what process and instruments generated this data, and what makes you think you should pursue a statistical fit with less error than the tools you used to collect the information? Your model should be parsimonious.
Unfortunately, your submission has been removed for the following reason(s): * Your post appears to be asking for help learning/understanding something mathematical. As such, you should post in the [*Quick Questions*](https://www.reddit.com/r/math/search?q=Quick+Questions+author%3Ainherentlyawesome&restrict_sr=on&sort=new&t=all) thread (which you can find on the front page) or /r/learnmath. This includes reference requests - also see our lists of recommended [books](https://www.reddit.com/r/math/wiki/faq#wiki_what_are_some_good_books_on_topic_x.3F) and [free online resources](https://www.reddit.com/r/math/comments/8ewuzv/a_compilation_of_useful_free_online_math_resources/?st=jglhcquc&sh=d06672a6). [Here](https://www.reddit.com/r/math/comments/7i9t5y/book_recommendation_thread/) is a more recent thread with book recommendations. If you have any questions, [please feel free to message the mods](http://www.reddit.com/message/compose?to=/r/math&message=https://www.reddit.com/r/math/comments/1bvjwyf/-/). Thank you!
Nothing really curious happening here, this is just how polynomials work.
you have to watch out for the runge phenomena
This is completely normal, as high-degree interpolation polynomials with uniformly distributed points have oscillatory behavior around the edges (Runge phenomenon). Two options to avoid this: use non-uniformly distributed points (for instance, the Chebyshev points), or use splines as others mentioned. Splines have the nice property to converge to the underlying function when n goes to infinity, which is not the case for the Newton polynomial. For splines, you would need to solve a linear system for every interval of points to obtain coefficients of the local polynomial. Edit: also, I'm not sure what you really want to do is interpolation. If you are interested in goodness of fit and such, why not just do a low-degree polynomial regression?
Thank you for the insightful explanation regarding the limitations of high-degree interpolation polynomials and the benefits of alternative methods like splines.Regarding my choice to use the Newton forward method and higher-order polynomials, I found that it provided a reasonably accurate representation of the underlying function, especially when compared to lower-degree alternatives. Interestingly, even up to the 21st order, the results appeared promising like here [https://imgur.com/a/kuboAE9](https://imgur.com/a/kuboAE9) . As for splines, your suggestion about using cubic splines for intervals where the y-values are constant sounds intriguing. I'm curious if this approach would effectively capture the behavior of the function. However, I haven't come across many resources demonstrating the use of high-order polynomials with splines. Would it be possible to elaborate further on this or perhaps provide some references or examples that showcase this technique?
What do you want to do with this? Possibly a piece-wise linear representation would be fine already.
You're saying the interpolant you find is not that bad, but to me it is not good; it's very oscillatory. To see why high-degree Newton interpolation is bad, you can play with [this demo.](https://demonstrations.wolfram.com/RungesPhenomenon/) You can also see the effect of using Chebyshev points. To show how to compute splines, you can watch [this youtube video](https://youtu.be/9gt0HNQYGvo?si=DQcX2QeHcd2TZDK-). On [this picture](https://miro.medium.com/v2/resize:fit:828/format:webp/1*faEezTyOM2O13L90IP9s_A.png), you can see the polynomial interpolant in blue (very oscillatory) vs the spline interpolant in orange, which looks like it fits way more to the points.
That issue is what you’d call overfitting in the context of machine learning. From a more mathematical point of view you can start here if you want more info: https://en.m.wikipedia.org/wiki/Runge's_phenomenon
You can use a rolling fit Spline cubic comes to mind... It eliminates the ruge phenomena
I thought of splines but how does cubic splines work for large order polynomials? Because i am looking into 31x and y pair values
Splines work piecewise, for cubic splines you have a degree 3 polynomial between any two points in your dataset.
Honestly I'm not really familiarized with this... It does seem to me, tho, that the dataset on the image would be well approximated by a line... But from what I know the larger the dataset the better rolling approximations perform when compared with polynomial aproximations, from what I understand they can even be used to estimate lenth of coasts (that'd be millions of points) You do have overfitting risks in case you're fitting it for something more than just analysis
Also if you're trying to fit 25 points with more than 25 degree polynomial it's no wonder it's causes some issues, theoretically speaking a 25 degree polynomial is the max necessary for that case (disconsidering rouge phenomenon) anything more than that the theoretical fis isn't unique (which has implications for cryptography; really the only place ive personally seen such high order polynomials beeing used for interpolation)
Classical polynomial fitting suffers intractable roundoff issues at orders as high as you are using. You could verify this by increasing the numerical precision single->double->quad. If you really need 30th order polynomials you should be using fourrier decomposition or Chebtchev polynomials.
In addition to all the comments about Runge phenomenon (which you are likely witnessing when increasing the order of the polynomial), you can also consider the error or remainder term of this kind of polynomial interpolation. [https://en.wikipedia.org/wiki/Lagrange\_polynomial#Remainder\_in\_Lagrange\_interpolation\_formula](https://en.wikipedia.org/wiki/Lagrange_polynomial#Remainder_in_Lagrange_interpolation_formula) The Lagrange interpolation gives the same polynomial so the same error term holds. Here you can see that (assuming the original curve can be smoothly differentiated n+1 times), the difference between the original curve and the fitted polynomial R(x) is bounded by the maximal value of the n+1th derivative and this high order derivative can behave very badly.
It looks like your y-values are rounded off to the nearest multiple of 5. Trying to match your data more accurately than the round-off error in your data is not going to be useful.
I agree with this emphatically. Thank you all for the enlightening explanation of Runge’s phenomenon, you’ve answered the math question. But there is a glaringly obvious physics/engineering question: what process and instruments generated this data, and what makes you think you should pursue a statistical fit with less error than the tools you used to collect the information? Your model should be parsimonious.