Polynomial interpolation - Revision history

Rongzhou: /* Newton polynomial */

2026-10-14T13:22:57Z

Newton polynomial

← Older revision		Revision as of 13:22, 14 October 2026
Line 89:		Line 89:
	=== Newton polynomial ===		=== Newton polynomial ===

	Although more complex, Newton polynomial is a somewhat smarter version of the [[Vandermonde_polynomial\|Vandermonde polynomial]]:		Although more complex, Newton polynomial is a somewhat smarter version of the [[#Vandermonde_polynomial\|Vandermonde polynomial]]:

	$$		$$
Line 104:		Line 104:

	Notice $\forall i \in [0,n], i \in N: c_{n+1}\left(x-x_{0}\right) \cdots\left(x-x_{n}\right)=0$ which means $\forall i \in [0,n], i \in N: P_{n+1}(x_i)=P_n(x_i)$. So $P_{n+1}(x)$ indeed interpolates for all the original datapoints.		Notice $\forall i \in [0,n], i \in N: c_{n+1}\left(x-x_{0}\right) \cdots\left(x-x_{n}\right)=0$ which means $\forall i \in [0,n], i \in N: P_{n+1}(x_i)=P_n(x_i)$. So $P_{n+1}(x)$ indeed interpolates for all the original datapoints.

			<ref>{{#cite:Q2153}}</ref>

	==== Numerical solution ====		==== Numerical solution ====
Line 123:		Line 125:
	Obviously, in practice, with modern computers, the difference is a few microseconds.		Obviously, in practice, with modern computers, the difference is a few microseconds.
	</blockquote>		</blockquote>

			<ref>{{#cite:Q2153}}</ref>

	==== Python implementation ====		==== Python implementation ====

Rongzhou: /* Python implementation */

2026-10-14T13:21:08Z

Python implementation

← Older revision		Revision as of 13:21, 14 October 2026
Line 71:		Line 71:
	plot.plot(x,y,marker='o', color='r', ls='', markersize=10)		plot.plot(x,y,marker='o', color='r', ls='', markersize=10)

	def f(o):		def p(t): # calculate the value P(t) for arbitrary t \in R
	sum = 0		sum = 0
	for i in range(n+1):		for i in range(n+1):
Line 77:		Line 77:
	for j in range(n+1):		for j in range(n+1):
	if i!= j:		if i!= j:
	prod=prod*(o-x[j])/(x[i]-x[j])		prod=prod*(t-x[j])/(x[i]-x[j])
	sum = sum + prod		sum = sum + prod
	return sum		return sum

	plot.plot(prange,f(prange))		plot.plot(prange,p(prange))
	plot.show()		plot.show()
	</syntaxhighlight>		</syntaxhighlight>

Rongzhou: Newton polynomial

2026-10-14T13:13:14Z

Newton polynomial

Show changes

Rongzhou: Created page with "'''Polynomial interpolation''' is the process of finding a polynomial {{#content:Q2150}} that for a definite set of datapoints $\{(x_i,y_i)| i\in [0,n], i \in N\}$ satisfies $P(x_i)=y_i$.
A polynomial of degree $n$ has $n+1$ arbitrary constants $a_k$ and therefore $n+1$ degrees of freedom, corresponding to $n+1$ datapoints $\{(x_i,y_i)| i\in [0,n], i \in N\}$. It can be therefore stipulated $\exists P(x), \forall i, P(x_i)=y_i$.
== Met..."

2026-10-14T11:12:09Z

Created page with "'''Polynomial interpolation''' is the process of finding a polynomial {{#content:Q2150}} that for a definite set of datapoints $\{(x_i,y_i)| i\in [0,n], i \in N\}$ satisfies $P(x_i)=y_i$. <blockquote> A polynomial of degree $n$ has $n+1$ arbitrary constants $a_k$ and therefore $n+1$ degrees of freedom, corresponding to $n+1$ datapoints $\{(x_i,y_i)| i\in [0,n], i \in N\}$. It can be therefore stipulated $\exists P(x), \forall i, P(x_i)=y_i$. </blockquote> == Met..."

New page

'''Polynomial interpolation''' is the process of finding a [[polynomial]]

{{#content:Q2150}}

that for a definite set of datapoints $\{(x_i,y_i)| i\in [0,n], i \in N\}$ satisfies $P(x_i)=y_i$.

<blockquote>
A polynomial of degree $n$ has $n+1$ arbitrary constants $a_k$ and therefore $n+1$ degrees of freedom, corresponding to $n+1$ datapoints $\{(x_i,y_i)| i\in [0,n], i \in N\}$.

It can be therefore stipulated $\exists P(x), \forall i, P(x_i)=y_i$.
</blockquote>

== Methods ==

=== Vandermonde polynomial ===

$$
P(x)=c_{0} x^{n}+c_{1} x^{n-1}+\cdots+c_{n} . \nonumber
$$

Since $P(x_i)=y_1$, a [[linear system]] of $n$ equations and $n$N variables ($c_n$) can be constructed:

$$
\begin{gathered} y_{0}=c_{0} x_{0}^{n}+c_{1} x_{0}^{n-1}+\cdots+c_{n-1} x_{0}+c_{n} \\ y_{2}=c_{0} x_{1}^{n}+c_{1} x_{1}^{n-1}+\cdots+c_{n-1} x_{1}+c_{n} \\ \vdots \\ y_{n}=c_{0} x_{n}^{n}+c_{1} x_{n}^{n-1}+\cdots+c_{n-1} x_{n}+c_{n} \end{gathered} \nonumber
$$

Which can also be written in matrix form:

$$
\left(\begin{array}{ccccc} x_{0}^{n} & x_{0}^{n-1} & \cdots & x_{0} & 1 \\ x_{1}^{n} & x_{1}^{n-1} & \cdots & x_{1} & 1 \\ \vdots & \vdots & \ddots & \vdots & \\ x_{n}^{n} & x_{n}^{n-1} & \cdots & x_{n} & 1 \end{array}\right)\left(\begin{array}{c} c_{0} \\ c_{1} \\ \vdots \\ c_{n} \end{array}\right)=\left(\begin{array}{c} y_{0} \\ y_{1} \\ \vdots \\ y_{n} \end{array}\right) \nonumber
$$

Solving the system gives $P(x)$<ref>{{#cite:Q2153}}</ref>

=== Lagrange polynomial ===

$$
P(x)=\sum_{j=0}^n\left(y_j\prod_{\substack{k=0 \\ k\neq j}}^n\frac{x-x_k}{x_j-x_k}\right)
$$

Since $\prod_{\substack{k=0 \\ k\neq j}}^n\frac{x-x_k}{x_j-x_k}$ always produce a polynomial of leading term $x^n$ (degree $n$), P(x), which is a sum of those polynomials, is itself a polynomial of degree $n$.

It can be further verified $P(x_i)=y_i$ by substituting $x=x_i$ into the original expression.

<blockquote>
Intuition: Over $(x_i,y_i)$, Lagrange polynomial has the same effects as $P(x_i)=\sum_{j=0}^m \delta_{ij} y_i$

Where $\delta_{ij}$ is the [[kronecker delta function]]:

$$
\delta_{ij} =
\begin{cases}
1, & i=j,\\
0, & i\ne j.
\end{cases}
$$
</blockquote>

==== Python implementation ====

<syntaxhighlight lang="python" copy>
import numpy as np
import matplotlib.pyplot as plot

x=[1,3,5,7,8,9,10,12,13]
y=[50,-30,-20,20,5,1,30,80,-10]

n=len(x)-1
prange = np.linspace(min(x),max(x),500)

plot.plot(x,y,marker='o', color='r', ls='', markersize=10)

def f(o):
sum = 0
for i in range(n+1):
prod = y[i]
for j in range(n+1):
if i!= j:
prod=prod*(o-x[j])/(x[i]-x[j])
sum = sum + prod
return sum

plot.plot(prange,f(prange))
plot.show()
</syntaxhighlight>

<ref>{{#cite:Q2154}}</ref>