The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [interpolation]

Questions on interpolation, the estimation of the value of a function from given input, based on the values of the function at known points. It is necessary because in science and engineering we often need to deal with discrete experimental data.

Filter by
Sorted by
Tagged with
3
votes
2answers
271 views

Any employment for the Varignon parallelogram?

The midpoints of the sides of an arbitrary quadrilateral form a parallelogram, which is called the Varignon parallelogram of the quad. While answering a question about Quadrilateral Interpolation it ...
3
votes
3answers
2k views

Quadrilateral Interpolation

The simplest finite element shape in two dimensions is a triangle. In a finite element context, any geometrical shape is endowed with an interpolation, which is linear for triangles (most of the time),...
9
votes
1answer
9k views

Implementation of Monotone Cubic Interpolation

I'm in need to implement Monotone Cubic Interpolation for interpolate a sequence of points. The information I have about the points are x,y and timestamp. I'm much more an IT guy rather than a ...
7
votes
3answers
624 views

Constructing a cubic given four points

Question: Is there an easier way to solve this problem? Suppose the polynomial $f(x)$ is of degree $3$ and satisfies $f(3)=2$, $f(4)=4$, $f(5)=-3$, and $f(6)=8$. Determine the value of $f(...
11
votes
2answers
27k views

How to calculate interpolating splines in 3D space?

I'm trying to model a smooth path between several control points in three dimensions, the problem is that there doesn't appear to be an explanation on how to use splines to achieve this. Are splines a ...
2
votes
1answer
11k views

How would I create a exponential ramp function from 0,0 to 1,1 with a single value to explain curvature?

I need an exponential function that will take linear input from 0,0 to 1,1 and give me back an exponential shaped curve such that changes in X near the 0 point result in small increases in Y, but each ...
12
votes
1answer
592 views

Interpolating the primorial $p_{n}\#$

The primorial $p_{n}\#$ is given by the product $p_n\# = \prod_{k=1}^n p_k$ (where $p_{k}$ is the $k$th prime) -- is there a natural (a la the gamma function $\Gamma(z)$) way of interpolating it for ...
4
votes
1answer
598 views

Analog of Vandermonde determinant for fitting a quadratic form?

1D interpolation: finding a polynomial satisfying $\forall_i\ p(x_i)=y_i$ can be written as a system of linear equations, having well known Vandermonde determinant: $\det=\prod_{i<j} (x_i-x_j)$. ...
3
votes
3answers
162 views

Show $P(z) $ is a polynomial of degree $n-1$ interpolating an Analytic function.

Let $C$ be a regular curve enclosing the distinct points $ω_1,ω_2,...ω_n$ and let $p(ω) = (ω −ω_1)(ω −ω_2) \cdots (ω −ω_n)$. Suppose that $f (ω)$ is analytic in a region that includes $C$. Show that ...
3
votes
1answer
392 views

There is a unique polynomial interpolating $f$ and its derivatives

I have questions on a similar topic here, here, and here, but this is a different question. It is well-known that a Hermite interpolation polynomial (where we sample the function and its derivatives ...
2
votes
1answer
244 views

A polynomial agreeing with a function and its derivatives

If we want $$p(x_i)=a_i, \qquad x_1 < \dotsb < x_{n+1},$$ then there is a unique polynomial of degree $\leq n$ that accomplishes this (Lagrange interpolation). If we want $$p(x_i)=a_i, \qquad ...
2
votes
2answers
356 views

Finding a simple spline-like interpolating function

I am looking for a continuous function $y=f(x,\alpha)$ for the interval $0\le x \le 1$ such that $0\le y \le 1$ and $y(0,\alpha)=0$ and $y(1,\alpha) = 1$ and $y(\alpha,\alpha) = 1-\alpha$ and $dy/dx|_{...
0
votes
2answers
210 views

Quadrilateral Finite Elements must be convex and not self-intersecting. But why?

Main reference @ Mathematics Stack Exchange: Quadrilateral Interpolation Quoted from this question: Why a quadrilateral with bilinear interpolation? Little else is possible with polynomial terms ...
0
votes
0answers
81 views

Specific Root of Interpolating Polynomial

We define polynomial $P=(x-\beta)\cdot g(x)$, where degree of $P$ is fixed $n-1$, $\beta$ is chosen uniformly at random from the field of $p$ elements. We evaluate $P$ at some $x_i$ values. So we get $...
15
votes
4answers
7k views

Polynomial fitting where polynomial must be monotonically increasing

Given a set of monotonically increasing data points (in 2D), I want to fit a polynomial to the data which is monotonically increasing over the domain of the data. If the highest x value is 100, I don'...
11
votes
2answers
4k views

Hardy–Littlewood-Sobolev inequality without Marcinkiewicz interpolation?

Here is the statement of the Hardy–Littlewood–Sobolev theorem. Let $0< \alpha< n$, $1 < p < q < \infty$ and $\frac{1}{q}=\frac{1}{p}-\frac{\alpha}{n}$. Then: $$ \left \| \int_{\mathbb{...
8
votes
2answers
2k views

$f(x)=1/(1+x^2)$. Lagrange polynomials do not always converge. why?

Let $f(x) = \frac{1}{1+x^2}$. Error of Interpolation with Lagrange polynomials for $n+1$ points is given by $$ e(x)=f(x)-P_n(x)=\frac{f^{(n+1)}(\eta_x)}{(n+1)!}\prod_{i=0}^n (x-x_i) $$ Carl Runge ...
9
votes
1answer
5k views

Natural cubic splines vs. Piecewise Hermite Splines

Recently, I was reading about a "Natural Piecewise Hermite Spline" in Game Programming Gems 5 (under the Spline-Based Time Control for Animation). This particular spline is used for generating a C2 ...
8
votes
2answers
13k views

Evaluate derivative of Lagrange polynomials at construction points

Assume, that we have points $x_i$ with $i=1,...,N+1$. We construct the Lagrange basis polynomials as \begin{align} L_j(x) = \prod_{k\not = j} \frac{x-x_k}{x_j-x_k} \end{align} Now according to my ...
5
votes
2answers
294 views

Find a smooth function with prescribed moments

In several contexts I’ve encountered variants of the following problem : let $m_0,m_1,m_2$ be real numbers such that $0 < m_1 < m_0$ and $\frac{m_1^2}{m_0} <m_2 < m_1$. Then, show that ...
5
votes
2answers
4k views

Determine the coefficients of an unknown black-box polynomial

Let $p$ be a polynomial of known degree $n$: $$p(x) = a_0 + a_1 x + \ldots + a_n x^n$$ Suppose we have a magic black box that can evaluate the polynomial for us. How could one then determine the ...
4
votes
2answers
757 views

Smoothest function which passes through given points?

I am trying to interpolate/extrapolate on the basis of a known collection of (finitely many) points. I'm wondering if there is a way to formalize this intuitive notion: find a 'smoothest' function ...
3
votes
2answers
24k views

Lagrange Interpolating Polynomials - Error Bound

Let $f(x) = e^{2x} - x$, $x_0 = 1$, $x_1 = 1.25$, and $x_2 = 1.6$. Construct interpolation polynomials of degree at most one and at most two to approximate $f(1.4)$, and find an error bound for the ...
4
votes
3answers
352 views

Does a sequence of moments determine the function?

Related questions and answers: Find a smooth function with prescribed moments When do equations represent the same curve? Consider a real valued integrable function $f(x)$ at the interval $a \le x \...
2
votes
1answer
524 views

Interpolation inequality

Lef $u$ be at least a $C^2$ function on $\mathbb{R}^n$. Let's denote the gradient by $D$. Also, (using the multiindex notation), define the seminorm $$||D^ku|| = \sup_{|\gamma|=k}{\sup_x{|D^{\gamma}...
2
votes
1answer
2k views

existence and uniqueness of Hermite interpolation polynomial

What are the proofs of existence and uniqueness of Hermite interpolation polynomial? suppose $x_{0},...,x_{n}$ are distinct nodes and $i=1 , ... ,n$ and $m_{i}$ are in Natural numbers. prove exist ...
2
votes
3answers
623 views

Uniqueness in Lagrange Interpolation Theorem?

The polynomials $p(x) = 5x^3 - 27x^2 + 45x - 21$ and $q(x) = x^4 - 5x^3 + 8x^2 - 5x + 3$ both interpolate the points $(1,2) , (2,1) , (3,6), (4,47)$. Even though these polynomials are of different ...
2
votes
1answer
208 views

Do nth degree polynomials derived using Least Squares Interpolation always have n+1 intersections with the function?

I have recently studied Interpolation Techniques in my College Numerical Methods class and I have this question: If we have a function $f(x)$ and we are asked to use Least Squares Interpolation(LSI) ...
1
vote
1answer
78 views

Trouble doing polynomial interpolation

I need to do a polynomial interpolation of a set $N$ of experimental points; the functional form I have to use to interpolate is this: $$ f(x) = a + bx^2 + cx^4,$$ as you can see the coefficient that ...
3
votes
3answers
98 views

Show that there is a unique polynomial of degree at most $2n+1$ such that $q^{[k]}(x_1)=a_k,$ $q^{[k]}(x_2)=b_k$ for $k=0, \dots, n$.

Let $x_1, x_2 \in \mathbb R$ and let $(a_0, a_1, \dots, a_n), (b_0, b_1, \dots, b_n)$ be $(n+1)$-tuples of real numbers. Show that there is a unique polynomial of degree at most $2n+1$ such that $$q^{[...
2
votes
1answer
2k views

Degrees of interpolating polynomials

Given a collection of $m+1$ points $\{(x_0,y_0), (x_1,y_1), ..., (x_m,y_m)\}$, we can form the interpolating Lagrange polynomial $L(x)$: $$ L(x) = \sum_{i = 0}^{m} y_i l_i(x) \\ l_i(x) = \prod_{\...
1
vote
1answer
370 views

Intuition for the coefficients in divided difference polynomials

I read the example on the Wikipedia page on divided differences, but I don't understand why we do this "slope" thing $\frac{y_1-y_0}{x_1-x_0}$ between every known point, and why does it really solve ...
1
vote
1answer
853 views

Jacobian determinant for bi-linear Quadrilaterals

Mapping from a square $\left[-\frac{1}{2},\frac{1}{2}\right]\times\left[-\frac{1}{2},\frac{1}{2}\right]$ with local coordinate system $\,(\xi,\eta)\,$ to an arbitrary quadrilateral with global ...
1
vote
1answer
65 views

Estimate the difference between $f$ and $p$ interpolating $f$

Suppose $p$ is the unique polynomial of degree $\leq 2$ that agrees with a function $f$ at points $a_1 < a_2 < a_3$. If the third derivative $f^{(3)}$ exists, and $x\in (a_1,a_3)$, then we can ...
0
votes
1answer
204 views

Overlapping Polynomials

This question is related to this:https://math.stackexchange.com/questions/1412564/interpolating-polynomial-its-root We have $P_3=P_2\cdot P_1$,for three non-zero polynomials. The degree of each ...
10
votes
1answer
1k views

Cauchy Integral Formula for Matrices

How do I evaluate the Cauchy Integral Formula $f(A)=\frac{1}{2\pi i}\int\limits_Cf(z)(zI-A)^{-1}dz$ for a matrix $A=\left(\begin{array}{ccc}2&2&-5\\3&7&-15\\1&2&-4\end{array}\...
4
votes
1answer
119 views

Interpolation between iterated logarithms

I am investigating the family of functions $$\log_{(n)}(x):=\log\circ \cdots \circ \log(x)$$ Is there a known smooth interpolation function $H(\alpha, x)$ such that $H(n,x)=\log_{(n)}(x)$ for $n\in\...
3
votes
1answer
6k views

Construct / find the simplest function based on data

Let's say I have these 7 natural numbers (all between 0 and 255): 255, 23, 45, 32, 87, 52, 146 How can I find a function F(x) that, once computed, gives me back ...
6
votes
2answers
7k views

Spline interpolation versus polynomial interpolation

What is the difference, if any, between spline interpolation and piecewise polynomial interpolation?
6
votes
1answer
3k views

Remainder term of Lagrange Interpolation Polynomial

Suppose $x_0,x_1,\ldots,x_n$ are $n+1$ distinct numbers in the interval $[a,b]$ and $f\in C^{n+1}[a,b]$. Then for each $x$ in $[a,b]$, there is a number $\xi$ in $(a,b)$ such that $$f(x) = P(x) + \...
6
votes
2answers
224 views

How interpret $\||x|^\gamma u\|_{L^r}\leq C\|\nabla u\|_{L^p}^{a}\||x|^\beta u\|_{L^q}^{1-a}$ for $u\in\mathcal C_0^1(\mathbb R^d)$?

Let $$\frac{1}{r}+\frac{\gamma }{d}=a\left(\frac{1}{p}+\frac{\alpha -1}{d}\right)+(1-a)\left(\frac{1}{q}+\frac{\beta }{d}\right),$$ where $d\geq 1$, $a\in [0,1]$, $\alpha ,\beta,\gamma \in \mathbb R$...
3
votes
2answers
461 views

Lagrange linear, quadratic, and cubic interpolations maximum interpolation error functions comparison

Using Theorem 1, calculate that the maximum interpolation error that is bounded for linear, quadratic, and cubic interpolations. Then compare the found error to the bounds given by Theorem 2. The ...
2
votes
4answers
7k views

Smooth transition between two lines (2d)

I have function that is defined as $$ Y = \frac{1}{15} x \longrightarrow {\rm if}\qquad 0 \leq x \leq 30 $$ $$ Y = \frac{1}{70} x + \frac{11}{7} \longrightarrow {\rm if}\qquad x > 30 $$ The ...
10
votes
3answers
594 views

A Curious Binomial Sum Identity without Calculus of Finite Differences

Let $f$ be a polynomial of degree $m$ in $t$. The following curious identity holds for $n \geq m$, \begin{align} \binom{t}{n+1} \sum_{j = 0}^{n} (-1)^{j} \binom{n}{j} \frac{f(j)}{t - j} = (-1)^{n} \...
9
votes
0answers
1k views

What is the maximum overshoot of interpolating splines in $d$ dimensions?

Consider cubic splines $s( x, y )$ which interpolate values $y = \{ y_0, y_1, \dots,y_n \}$, on the uniform grid $\{ 0, 1,\dots, n \}$. Fix $s''(0) = s''(n) = 0$ (natural splines). How big can $$\...
6
votes
0answers
196 views

estimating a particular analytic function on a bounded sector.

Let $f(z)$ be an analytic function on $C^+=\{\Re z>0\}$, and we have the following (weaker) estimates $$ |f(re^{i\theta},a)|\leq C (r\cos\theta)^{-n}, ~~~r>0,-\frac{\pi}{2}<\theta<\frac{\...
6
votes
4answers
2k views

Proof of Schur's test via Young's inequality

I am able to prove the following generalization of Schur's test using the Riesz-Thorin interpolation theorem, however I have been stuck for days now trying to prove it using Young's inequality: Let ...
5
votes
1answer
500 views

Determining Coefficients of a Finite Degree Polynomial $f$ from the Sequence $\{f(k)\}_{k \in \mathbb{N}}$

Suppose $f$ is an unknown polynomial of degree $n$ (in one indeterminate) but the sequence $\{ f(k) \}_{k \in \mathbb{N}}$ is given. It is a nice exercise to show that one needs only the first $n+1$ ...
5
votes
1answer
593 views

Integer valued polynomial through some known points

I have 2 questions, but I'll put both of them here since they are closely related: An integer valued polynomials $P(x)$ is a polynomial whose value $P(n)\in\mathbb{N}$ for every $n\in\mathbb{N}$. 1-...
1
vote
0answers
86 views

Polynomial Interpolation When part of $y_i$'s are Shuffled

Hypothesis: Let $\vec{x}=[x_1,...,x_n]$ be elements of field $\mathbb{Z}_p$, where $p$ is a large prime. $x_i \neq x_j$, $x_i \in \mathbb{Z}_p$. Note $x_i$ values are NOT picked uniformly random and ...