Questions tagged [lagrange-interpolation]
A method of generating a polynomial that crosses through a set of data. The degree of this polynomial is equal to the size of the data.
368
questions
0
votes
1
answer
20
views
Maximum degree of polynomial interpolating a two-degree polynomial with an additional condition
Let $f$ be a twice differentiable function over real line. Let $a\in \mathbb{R}$ and $h\in \mathbb{R}^{+}$. Let $P_f$ denote the interpolating polynomial of degree $2$ of $f$, i.e.,
$$f(a)=P_f(a), \...
1
vote
1
answer
25
views
how to prove the following equation $\sum_{i=1}^{i=n}\prod_{j=1,j\neq{i}}^{j=n}{\frac{1}{x_{i}-x_{j}}}=0$
$\sum_{i=1}^{i=n}\prod_{j=1,j\neq{i}}^{j=n}{\frac{1}{x_{i}-x_{j}}}=0$
The product on the denominator is what I derive from the derivative of an n degree polynomial with different solutions $x_{1}$ to $...
1
vote
2
answers
112
views
Where to find proof for the remainder formula of the interpolation in two variables
Professor showed this result in the lecture without giving any proof (after proving the existence of the interpolating polynomial in two variables). I've been trying to prove it myself or find a book ...
0
votes
1
answer
218
views
Showing recursive Formula for Polynomial Interpolation
Let $f : [a, b] \rightarrow \mathbb{R}$. Define
$$
f[a_0, ..., a_n] := \frac{f[a_1, ..., a_n]-f[a_0, ..., a_{n-1}]}{a_n - a_0}
$$
with $f[a]=f(a)$. Consider now $(m + 1)$ distinct nodes $x_j \in \...
0
votes
1
answer
35
views
Lagrange Interpolation as generalized polynom
I need to write an algorithm that constructs a function of the form
$f(x) = \sum_i^n q_i x^i$
that exactly goes through the points $p_i = (a_i, b_i)$.
In general building such a function is not the ...
4
votes
1
answer
67
views
Does there exist $f \in \mathcal{C}^\infty\left([a, b]\right)$ such that $M_n \rightarrow \infty$ but $\left\|f - p_n\right\| \rightarrow 0$?
Let $f \in \mathcal{C}^\infty\left([a, b]\right)$ and $n \in \mathbb{N}$.
Let $p_n$ be the Lagrange interpolating polynomial for a partition of equispaced points $a = x_0 < x_1 < \cdots < x_n ...
0
votes
1
answer
101
views
Does Lagrange interpolation at Chebyshev points solve the Runge phenomenon?
I recently came across the concept of the Runge phenomenon while studying numerical methods for special functions in the book "Numerical Methods for Special Functions" by Amparo Gil, ...
0
votes
1
answer
43
views
Prove $\max_{|x|\leq \frac13}|f(x)-p_2(x)|\leq \frac{1}{2\cdot 3^{\frac{11}{2}}}\,\max_{|x|\leq \frac13}|f^{(4)}(x)|$ for Runge's function.
Let $f(x)=\frac{1}{1+x^2}$ be Runge's function. If $p_2(x)$ is the interpolating polynomial of $f$ regarding the nodes $-\frac13,\,0,\frac13$, prove that:
$$\max_{|x|\leqslant \frac13}|f(x)-p_2(x)|\...
0
votes
1
answer
34
views
How to prove the given statement based on the conditions related to interpolating polynomials used in Adaptive Backward Differentiation Formula.
Full disclosure: This was part of my homework that I couldn't solve completely. Also, I wasn't sure how to give a proper title to this question.
Before going to the statement to prove, I think some ...
0
votes
0
answers
31
views
error calculation in Lagrange interpolation
Construct Lagrange interpolating polynomials of degree two and three to approximate:
a)$ f (0.25)$ yes
$f(0.1) = -0.62049958, f(0.2) = -0.28398668,
f(0.3) = 0.00660095,
f(0.4) = 0.24842440
$
...
0
votes
1
answer
45
views
Error term refinement of Lagrange interpolation
The error in Lagrange interpolation is
$$
E(x)\equiv f(x)-L_n(x)=\frac{f^{(n+1)}(\xi_x)}{(n+1)!}\prod_{j=0}^n(x-x_j)
$$
where $f\in C^{(n+1)}([a,b])$ is the function to be inter-/extrapolated, $\{x_0,\...
1
vote
2
answers
157
views
Nonlinear ODE with (pseudo-)spectral method
Consider an ODE of the form
$$c_0 u + c_1 u' + c_2 u'' \enspace = \enspace f(x,u) \quad .$$
I want to solve this ODE with spectral methods. To this end, let $\{ x_k \}_{k=0}^N$ be suitable nodes, e.g. ...
2
votes
0
answers
67
views
Finding rational coefficients of a cubic polynomial that fits 4 data points that have been floored to an integer
I have 4 data points:
(204, 5422892)
(205, 5722486)
(207, 6343357)
(213, 8386502)
I have information that these data points were generated with a cubic polynomial
$y = ax ^ 3 + bx ^ 2 + cx + d$
with ...
6
votes
1
answer
100
views
$\ \forall x_1,x_2,...,x_n \in \mathbb{R} (x_i\not=x_j)$ in the range of $[-1,1]$ prove:$\sum_{i=1}^{n}\frac{1}{\Pi_{k\not=i}|x_k-x_i|}\ge2^{n-2}$
$\ \forall$ $x_1,x_2,...,x_n$ $\in \mathbb{R}$ $(x_i\not=x_j)$ in the range of $[-1,1]$ prove :
$$\sum_{i=1}^{n}\frac{1}{\Pi_{k\not=i}|x_k-x_i|}\ge2^{n-2}$$
my attempt :
$$p(x) = \sum_{i=1}^{n}\left(...
0
votes
1
answer
62
views
$f(x)=x^n+a_{n-2}x^{n-2}+...+a_1x+a_0\in \mathbb{R}[X]$. prove$\ \exists$ $i\in[1,...,n]$ so that : $|f(i)| \ge \frac{n!}{\binom n i}$
$f(x)=x^n+a_{n-2}x^{n-2}+...+a_1x+a_0\in \mathbb{R}[X]$. prove$\ \exists$ $i\in[1,...,n]$ so that :
$$|f(x)| \ge \frac{n!}{\binom n i}$$
my attempt :
i used lagrange interpolation and compared $x^n$ ...
1
vote
0
answers
43
views
How many evaluations do you need to prove that a multivariate polynomial is the zero polynomial?
For a univariate polynomial $f$, you just need to prove that $f(x) = 0$ for $d+1$ distinct $x$ to prove that $f$ is the zero polynomial.
But for multivariate polynomials, how does that work? How many ...
0
votes
0
answers
34
views
How can I find a $n$-th degree polynomial for a line with $n-1$ predetermined points?
Essentially, I have a set of points which I want to create a polynomial that passes through a set of points. This is within the context of having set locations on a line to set times. It is preferred ...
0
votes
1
answer
49
views
Polynomial or wave through aligned points [closed]
If I have the distinct points $(x_{1}, 0) ... (x_{n}, 0)$,
A) What would be a simple polynomial (non-constant) passing through these points? And could I instead also write a simple continuous curve (a ...
0
votes
0
answers
130
views
Different bounds for truncation error in linear interpolation
I am reading about the Lagrange linear interpolation for approximating a function.
In the book, truncation error in linear interpolation is derived as follows :
Suppose $f(x)$ is a function which is ...
0
votes
0
answers
36
views
Possible dimension of vector space
Let $A=\{0,1,2,3\} \subset \mathbb{R}$ and $\mathbb{R}[X]$ be the set of all polynomials in one variable over $\mathbb{R}$. Let $V$ be the $\mathbb{R}$-vector space of functions $f: A \rightarrow \...
2
votes
0
answers
49
views
How to use bilinear interpolation to interpolate a new optimized trajectory?
Sorry if this does not quite make sense as I am still wrapping my head around it as well. Currently, I have a vehicle with some initial position $x_0$. From this position, four optimal trajectories ...
0
votes
0
answers
22
views
Linearly independent equivalent of lagrange interpolation
Im looking at lagrange interpolation and has been given that:
$P(t) = \sum_{i=1}^n \; y_iL_i(t)$
Is equivalent to the following matrice equation:
$$\begin{bmatrix}
q_1 \\
q_2 \\
\vdots \\
...
0
votes
0
answers
214
views
Lagrange Interpolating Polynomials with custom way to add Local Maximum/Minimum.
Given this data table consists of 10 points:
x | -3 1 2 4 5 6 9 11 12 14
y | 2 3 -2 0 -3 1 -1 0 -2 1
Construct a polynomial P(x) such that its graph passes through the points in the data table
and P(x)...
20
votes
2
answers
702
views
For what $n$ can we find a degree $\leq n-2$ polynomial such that $P(i) \in \{0 , 1 \}$ for $i \in [n]$, but not all identical.
For what $n$ is the following statement true:
There exists a choice of $ a_1, a_2, \ldots a_n \in \{ 0, 1 \}$, not all identical, such that there is a polynomial $F(x) \in \mathbb{R}[x]$ of degree at ...
0
votes
1
answer
246
views
Showing that Lagrange Basis Polynomials sum to 1 [closed]
I am currently trying to explain why it is the case that when given a Lagrange polynomial with coefficients of all $1$
$P_3(x)$ $=$ $L_0(x)$ + $L_1(x)$ + $L_2(x)$ + $L_3(x)$ $=$ $1$, for all $x$.
What ...
1
vote
1
answer
40
views
Fundamental polynomials: do they form a base
First, is $P_n$ $n$ or rather $n+1$ dimensional real vector space of polynomials of degree at most $n$ ? Here, $n$ indicates that it should be $n$ but the basis $1,x,x^2,x^3,...,x^n$ has $n+1$ ...
2
votes
1
answer
69
views
Prove that $P_{h}(f)$ satisfies $||f-P_{h}|| \leq Ch^{2}$
Consider a partition of the domain $\Omega=[a,b]$
$$ a=x_{1}<x_{2}<\cdots < x_{N}=b $$
with mesh size $h=\max\{x_{i+1}-x_{i}:i=1,...,N-1\}$.
Let V be an inner product space, with inner ...
4
votes
1
answer
229
views
How would a better mathematician than I complete this half-finished definition of what it means for a curve to be smooth?
Once upon a time, I was taught how to play connect the dots.
Some years later, I was given pseudo-code for an algorithm which would compute a polynomial of minimum degree passing through some points.
...
0
votes
1
answer
131
views
Understanding a proof for divided differences
suppose you are given the following proof of the statement:
$[x_0, ..., x_n; f \cdot g]=\sum_{k=0}^n[x_0,...,x_k; f]\cdot [x_k,...,x_n; g]$.
Some preliminary steps:
Let $[x_0,...,x_n; f]=\sum_{i=0}^n\...
1
vote
0
answers
111
views
Lagrange interpolation polynomial - error function
a) Calculate the Lagrange Interpolationpolynomial $p$ for the function $f(x) = \sin (\pi x)$ for the points $x_0 = 0, \ x_1 = 0.5 , \ x_2 = 1$.
b) Then estimate the maximum interpolation error on the ...
2
votes
1
answer
120
views
Prove a Vandermonde Determinant Formula
I seem to have stumbled upon a strange formula, and I'm not quite sure that I understand it. Consider the determinant standard Vandermonde matrix
$${}^nD = \left|\begin{matrix}
1 & x_{0} & ...
0
votes
1
answer
120
views
algebraic equivalent interpolation formulae
I'm approaching to finish reading this book by Ralston: A first course in numerical analysis book:
but I'm still missing the reason for the solution of the exercise ${}^*22, $
part $d$.
I understand ...
1
vote
1
answer
130
views
Why must a polynomial of degree n-1 or lower have the following result?
I am given a homework problem that states: prove that for any polynomial $q$ of degree $n-1$ or lower that:
$$\sum^n_{i=0}q(x_i)\prod_{j=0, j \ne i} (x_i - x_j)^{-1} = 0$$
Intuitively, I don't know ...
0
votes
1
answer
48
views
(Determine coefficients) Backward Differtiation Formula for m $ = 2 $ using Lagrange polynomial
So I want to determine the coefficients regarding the BDF($2$).
Note that I'm absolute beginner, so my attempt is not that great.
The solution has to be: $ \frac{3}{2}y_{k+2} - 2y_{k+1} + \frac{1}{2}...
0
votes
1
answer
53
views
find minimum value of $u$ for $\,u = \frac{ax^2+by^2}{\sqrt{a^2x^2+b^2y^2}}$
Find the minimum value of $u$ where
$x^2+y^2=1\;$ and $\;u =\displaystyle{\dfrac{ax^2+by^2}{\sqrt {a^2x^2+b^2y^2}}}$
1
vote
1
answer
55
views
Lagrange interpolation as two points get closer and closer
Suppose, you want to perform a Lagrange interpolation for $x_0$, $x_0+\varepsilon$ and $x_1$. What happens as $\varepsilon \to 0$?
Here are the Lagrange-polynomials
\begin{gather*}
L_0(x)=\frac{(x-(...
1
vote
0
answers
55
views
Issues with the Peano kernel in the Peano kernel theorem
I have a very simple question, because I somehow don’t get this definition.
The version of the Peano kernel theorem that we had in class is:
For all linear functionals $\mathcal{L}:C^{n+1}([a,b]) \...
0
votes
0
answers
31
views
why is my lagrangian interpolation not approximating as nearly accurate as Newton's DD approximation?
Here is the set of data:
$(X,Y)= (1,4.75), (2,4), (3,5.25), (5,19.75), (6,36)$
After I approximated to $3$rd order polynomial with Newton's interpolation, it modeled the true behavior of how $X$ and $...
0
votes
1
answer
149
views
Newton's Divided Difference Formula without given data point
This is the original question:
Let f(x)= sin((pi*x)/6) and P(x) a quadratic polynomial such that f(x)
= P(x) at x=0,1, and 2. Find P(x) using Newton's Divided Difference Formula
Since Newton's ...
3
votes
2
answers
117
views
Simplifying $\frac{a^4}{(a-b)(a-c)} + \frac{b^4}{(b-a)(b-c)} + \frac{c^4}{(c-a)(c-b)}$ using Lagrange’s polynomial
I have a question of symplifying this expression
$$
A=\frac{a^4}{(a-b)(a-c)} + \frac{b^4}{(b-a)(b-c)} + \frac{c^4}{(c-a)(c-b)} \tag{1}
$$
where $a$, $b$ and $c$ are distinct nonzero real numbers. ...
0
votes
0
answers
159
views
Convex optimization with Ridge regression
If this is the constrained version of ridge regression:
min
w∈Rd
∥Φw − y∥^2
s.t. ∥w∥2 ≤ s,
(1)
where Φ ∈ R
n×d and y ∈ R
n
. Answer the following questions.
•How can we prove that this is a convex ...
0
votes
1
answer
30
views
Trouble trying to bound an approximation using Lagrange interpolation.
I know this has been asked various times but I do not understand any of the answers given yet.
I'm working with the function $f(x)=e^{x}$ in the interval [-4,0] and I need to bound $|f(x)-Q_{n}(x)|$ ...
0
votes
1
answer
40
views
Lagrange Polynomial to estimate the derivatives of a function
We have the following question for our homework. I'm completely lost on what to do. I have no idea how to compute the error of the derivative or how to proceed from there. I've tried googling Lagrange ...
0
votes
1
answer
37
views
Find Hermitian interpolation with Lagrangian polynomials
Hi I have an exercise that I cannot solve.
Can someone help me?
I have to find the solution to the following Hermitian interpolation problem p(x) under the conditions:
$p(x_0)=-1, \ p'(x_0)=1 \ p(x_1)=...
0
votes
2
answers
127
views
how to prove span of Lagrange basis functions is equivalent to${\rm span}\{1,x,\dots,x^n\} $
Suppose we have n+1 points $x_0, x_1 , \dots , x_n$ and the following is Lagrange basis function.
$$
L_i(x):=\prod_{j=0, j \neq i}^n \frac{x-x_j}{x_i-x_j}
$$
How to prove that
$$
\operatorname{span}\{...
6
votes
3
answers
219
views
Prove that $\sum_{1\leq i\leq n}\prod_{j\neq i} \frac{1-x_ix_j}{x_i-x_j} = 0$ if $n$ is even and $1$ otherwise
Let $x_1,\cdots, x_n$ be different real numbers. Prove that $$\sum_{1\leq i\leq n} \prod_{j\neq i} \frac{1-x_ix_j}{x_i-x_j} = \begin{cases} 0,&\text{if }n\text{ is even}\\
1,&\text{if }n\text{ ...
0
votes
0
answers
87
views
Bounding error term in Lagrange Interpolation
I've spent more time that I'd like to admit working out this bound.
Online, I've seen that the remainder $R(x) = f(x) - L(x)$ in Lagrange interpolation is bounded by
$$| R(x) | \leq \frac{(x_n - x_0)^{...
3
votes
1
answer
780
views
What is the most efficient algorithm to evaluate a polynomial of n degree at K points?
A brute force approach would be to evaluate each point for each of the terms of a polynomial, which will be $O(Kn^2)$.
If we use logarithmic exponentiation to find each $x^i$ then it becomes $O(Kn \...
1
vote
0
answers
162
views
Is the following statement about polynomial approximation of non-differentiable functions true?
Statement
$\forall L \in \mathbb{R}^+$, and $\forall f:\mathbb{R}\to\mathbb{R}$ for which
$f$ isn't differentiable at point $a\in\mathbb{R}$
$f$ is infinitely differentiable everywhere else (on $\...
2
votes
1
answer
47
views
I don`t understand this little incongruence about the error function of Lagrange interpolation polynomial.
Given $f \in C^{n+1}([a,b])$ and a set of $n+1$ points in $[a,b]$. And given $P$ the Lagrange interpolation polynomial, the error function is $f - P = \frac{f^{(n+1)}(\eta_x)}{(n+1)!}w_S(x)$ where $...