Talk:Polynomial interpolation

This is the talk page for discussing improvements to the Polynomial interpolation article.
This is not a forum for general discussion of the article's subject.

Put new text under old text. Click here to start a new topic.
New to Wikipedia? Welcome! Learn to edit; get help.

Article policies

Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL

Tip: Anchors are case-sensitive in most browsers.

This article links to one or more target anchors that no longer exist.

[[Pascal's triangle#The Triangle of Binomial Transform Coefficients is like Pascal's Triangle.|triangle of binomial transform coefficients]] The anchor (#The Triangle of Binomial Transform Coefficients is like Pascal's Triangle.) is no longer available because it was deleted by a user before.

Please help fix the broken anchors. You can remove this template after fixing the problems. | Reporting errors

Does anyone mind if I change the nodes from t to x ? I know t is used to indicate time but at the moment there is no reference to time on the page so I think it is clearer to use the standard variable x.MathMartin 13:34, 17 Sep 2004 (UTC)

Notes for convergence theorems:

1) The example when interpolation diverges on Chebyshev nodes for a continuous function seems highly desirable, but it needs a continuous but not absolutely continuous function. Can Cantor's function make it?

2) There are also nicest convergence theorems for analytical functions. They are mostly of a theoretical value; but they can explain (at least partially) the choice of a function in Runge's phenomenon (especially the strangest '25' coefficient in the denominator). Should they be mentioned? It's all from the Russian textbook; I know not of ones in English which have it. --Igor 16:45, Oct 10, 2004 (UTC)

1) I don't know, just try it out. 2) Yes, please add them, and also mention your textbook; a Russian reference is better than no reference. -- Jitse Niesen 13:19, 18 Oct 2004 (UTC)

I think we should move the Lebesgue constants part to a proper article. There are still interesting things to write and it already takes a great place in this article. Should we? Julien Tuerlinckx 20:23, 18 Jun 2005 (UTC)

Go for it. Jitse Niesen 22:13, 18 Jun 2005 (UTC)

Recent changes to this article[edit]

The recently added section to this article is called ==Applications and examples==. However, there are no applications and no examples in there. What I see is lots and lots of wording.

The first part of it leads to the fact that you need a polynomial of degree n to interpolate through n+1 points. But that is already very clearly stated in the section above. This new section does not attempt to prove this statement, so it adds nothing new to what is already stated.

The second part of this section goes at great length to explain the least squares. But again, we have an entire article devoted to that, called least squares. So why bother?

In conclussion, I believe the new section provides little if any value to the article. Comments? Oleg Alexandrov 02:33, 7 August 2005 (UTC)[reply]

I added this section to provide an introduction to this material, which seemed too complex for most people, as it was. It seemed written for mathematicians, when it should be written for the general public. While I don't object to complex theory, I feel there should also be material for non-mathematicians included. As for not having any examples or applications, I believe I refer to hiway cloverleaf design, running curves through sample data, and 3D surface construction, albeit briefly, as applications. I believe listing 1st-3rd degree equations, and some possible constraints for each, constitute examples. I am willing to entertain suggestions for a new section title, however. I don't believe the existing material made any mention of what happens if a degree higher or lower than that necessary for an exact fit is used. I felt this was needed. I also thought info on constraints other than points, such as angle and curvature, were important. As for going into great detail to explain least squares, I don't believe I explained it at all, but only mentioned it as one possible approximation method. I will add a link to that article. I also saw your style notes and will try to add those style changes. StuRat 04:17, 7 August 2005 (UTC)[reply]

Ok, I added the style changes you suggested and the "least squares" link, and also decided to change the section title to "Introduction" as it is rather light on detailed applications and examples, but does include good material to introduce those unfamiliar with the concepts. StuRat 04:43, 7 August 2005 (UTC)[reply]

I somehow missed the applications you mention, but now looking more carefully I found that sentence. Yes, calling that section ==Introduction== rather than ==Applications and examples== reflects better its contents.

I am always for making things simpler, but it might be that your introduction is a bit too wordy. Let us see how this develops. Oleg Alexandrov 05:27, 7 August 2005 (UTC)[reply]

Ok, let's see what other comments it gets. These concepts are quite difficult for the general public to understand, so I feel a lot of words are needed to explain them. I should also explain that I taught these concepts to students at one point, so am approaching this from the point of view of an educator, looking for where my students would have gotten lost. I freely admit, however, that some of my students weren't very bright, LOL. StuRat 07:15, 7 August 2005 (UTC)[reply]

I taught this stuff too, in the spring. :) Oleg Alexandrov 08:34, 7 August 2005 (UTC)[reply]

On a first reading, it is quite okay, but I would move it to the interpolation article, which is about linear interpolation, polynomial interpolation, spline interpolation and higher-dimensional interpolation. StuRat, any reason why you put it here? -- Jitse Niesen (talk) 11:18, 7 August 2005 (UTC)[reply]

I thought it dealt with polynomial interpolation. Linear interpolation is a subset of polynomial interpolation, in that a first degree polynomial is a line. Other than that, I didn't really get into other interpolations, like conic sections or bezier/NURBS curves, although I mentioned splines briefly (they were also mentioned briefly in another section of this article). I would consider putting my content under curve fitting, but since I refer to both the approximate fits of curve fitting and the exact fits of interpolation, I'm not sure that would be any better. I don't quite buy the idea that one knows before starting whether they want an exact fit or an approximate fit. I would say in many cases it will depend on the data and no such decision can be made until the various alternative exact and approximate solutions are compared. Also, the curve fitting section doesn't yet exist, but only redirects to regression analysis. This would require me to add much more material to flesh out the curve fitting section.

I see what you mean (I assume that you take Hermite interpolation to be a part of polynomial interpolation?). The reason that I prefer this to go to interpolation is that that article does not have a nice introduction and people are likely to first read the interpolation article and then perhaps click through to different kinds of interpolation. I agree that the style is a bit wordy and informal, but that's just a detail; the problem is that Wikipedia is an encyclopaedia and not a collection of lecture notes. Point 3 (fluctuating wildly) and 4 (lumpiness) seem the same to me. But hey, it's great, thanks; it may need some fine-tuning but it's a nice improvement. -- Jitse Niesen (talk) 17:27, 7 August 2005 (UTC)[reply]

I will consider moving it there, let me think about that a bit. As for being wordy and informal, if you have specific suggestions for changes that don't remove any of the content, they would be greatly appreciated. As for 3 and 4 being the same, perhaps I need to clarify that. For "fluctuating wildly" I meant going to nearly +inf or -inf values of y between points. It is possible for a curve to be "lumpy" (have numerous inflection points) without this happening. However, they are related, so perhaps should be combined into a single item. I will be busy for a while, but will get back to making some of these improvements within the next couple of days. StuRat 18:19, 7 August 2005 (UTC)[reply]

I decided the leave items 3 and 4 separate, but did clarify the difference. I also concluded that, painful as it is, creating a new curve fitting page and moving my intro there is the way to go. I am having a technical problem at the moment that prevents me from editing any page without sections. If one of you would be kind enough to move my intro, section title included, to curve fitting, I will then endeavor to do the rest.

That's a strange problem, but I moved the intro for you. Note that you can number the lists automatically by using # (edit the new curve fitting page and you'll see what I mean); apologies if you did not use # on purpose. -- Jitse Niesen (talk) 22:44, 7 August 2005 (UTC)[reply]

I agree with the move to curve fitting. In this way we will have a very elementary article on interpolation and related issues. Oleg Alexandrov 23:00, 7 August 2005 (UTC)[reply]

Jitse, thanks for moving it, and the auto-numbering system is fine, too. I don't think the "moved for StuRat" comment belongs on the main page, but should have been on the discussion page. Unfortunately, as I can't get at anything in section 0, I can't remove that comment either. Would you mind moving it to the discussion page and creating a new section there for me (since I can't edit section 0 of the discussion page either) ? Thanks. StuRat 00:08, 8 August 2005 (UTC)[reply]

To get to the very top of the article, use the edit button at the top of the page. :) Oleg Alexandrov 00:19, 8 August 2005 (UTC)[reply]

Ok, the bug has been fixed, I can now edit everything. StuRat 03:47, 8 August 2005 (UTC)[reply]

mathsoft link is broken

Where the article says

[...]interpolation is also essential to perform [...] Karatsuba Multiplication

should be FFT Multiplication, instead. Karatsuba just uses a trick to split the problem in two and recompose using three multiplications instead than four. FFT Multiplication does the interpolation-trick.

131.114.11.94 14:22, 19 July 2007 (UTC) Luca[reply]

haii[edit]

for me, add more example and with applications for student do their project..

Jet[edit]

What does "that is, it is prescribed there a whole k-jet" mean? That sounds ungramattical to me. Andrew (talk) 09:41, 1 July 2009 (UTC)[reply]

It probably should read "that is, the whole k-jet is prescribed there". I doubt that introducing the concept of jets is useful though, so I removed that phrase. -- Jitse Niesen (talk) 14:54, 1 July 2009 (UTC)[reply]

Stone-Weierstrass theorem[edit]

I think the Stone-Weierstrass theorem should at least be mentioned, as it addresses the polynomial interpolation of a curve. This article is about

... the interpolation of a given data set by a polynomial

but later on in the article we state

Polynomials can be used to approximate more complicated curves

so we are considering not only data set interpolation but also curves fitting. If no one object to this, I will add it later --Marco4math (talk) 12:23, 26 February 2010 (UTC)[reply]

Proof 2[edit]

I've found a cleared proof of the uniqueness using Vandermorde matrix, I'll replace the actual unclear proof 2 with a new one. --Marco4math (talk) 23:25, 4 March 2010 (UTC)[reply]

Do you have a citation to go with it? Anyway why do we need two proofs in the first place? The first proof looks like it adds to the article in an appreciable way but I think just removing proof 2 would be best. Dmcq (talk) 23:52, 4 March 2010 (UTC)[reply]

I think two proofs contributes a more diverse range of thinking, even though the outcome is equivalent. Given that this is an encyclopedia it should contain all knowledge? Additionally in the sentence "...no matter what method we use to do our interpolation: direct, spline, lagrange etc., (assuming we can do all our calculations perfectly) we will always get the same polynomial." I don't think "spline" should be in this list as a spline will not be equivalent to an interpolated polynomial and the two proofs do not explicitly prove the uniqueness theorem for derivatives at points as well. Should this be changed?--Mrpalermo (talk) 04:29, 5 November 2013 (UTC)[reply]

Alternate solution?[edit]

I was considering this problem on my own before looking it up, and came up with a solution that I believe is different from the one presented in the article. I asked a friend of mine what he thought, and his solution seems to be the one in the article. It was certainly different from mine.

The problem was, given a bunch of points, find the lowest-degree polynomial that passes through all of the given points. My friend's solution was this:

Suppose that there are (n + 1) points given. Then the polynomial that we are looking for is of the form

a_nxⁿ + a_n-1x^n-1 + ... + a₁x + a₀ = y

We can plug in each (x,y) pair into the equation above to get a system of equations and solve the system for all a_n's.

My solution was this:

Suppose the points given have the x-values, say, of 5, 8, and 17. Then construct the polynomial as:

y = a(x-5)(x-8) + b(x-5)(x-17) + c(x-8)(x-17)

Since the first term is the only non-zero term when x = 17, and we know the y-value when x = 17, it is trivial to solve for a. Same for b and c. Then, if you want, you can expand the equation to get a more normal-looking form.

Since even I managed to come up with this, I assume that someone else has. However, I don't want to put it on the page because it is original research. Does anyone else know if this method is already known? I think that it may be worth having on the page. It also requires no knowledge of matrices, and only simple algebra, so I think that it is more accessible to more people.

Thanks! hwalter42 (talk) 21:44, 7 January 2015 (UTC)[reply]

you've just rediscovered the approach using Lagrange polynomials, which is given in the article. If you compare that with your method you'll see they are the same.--JohnBlackburne^words_deeds 22:07, 7 January 2015 (UTC)[reply]

Ah, it was in a different form, so I didn't recognize it. Thank you for the fast response! hwalter42 (talk) 22:40, 7 January 2015 (UTC)[reply]

What's the difference between "polynomial interpolation theorem" and "unisolvence theorem"?[edit]

Aviad.rubinstein (talk) 22:17, 26 January 2020 (UTC)[reply]

graphic unclear[edit]

I could not make sense of the illustration captioned "Geometric interpretation of Catmull–Rom cubic interpolation of the black point with uniformly spaced abscissae.[9]"

Is the image missing labels after the minus signs? Is it really obvious what all those double-ended arrows are indicating? Jmichael ll (talk) 19:00, 13 March 2022 (UTC)[reply]

I agree thet the image is very confusing. As "Catmull–Rom interpolaton" is not mentioned elsewhere in the article, this image is definitely not relevant for this article, and I'll remove it. D.Lazard (talk) 20:10, 13 March 2022 (UTC)[reply]