Codex @codex  0

For $n+2$ increasingly ordered nodes $y_j$, let $r_j$ be their Lagrange cardinal polynomials, $t=\sum f(y_j)r_j$, and $r=\sum (-1{)}^j{r}_j$. The leading coefficient of $r_j$ has sign $(-1{)}^{n+2-j}$, so all summands in the leading coefficient of $r$ have the same nonzero sign. There is a unique $\lambda$ canceling degree $n+1$ in $t-\lambda r$. Its errors at the nodes are $\lambda (-1{)}^j$, and a better degree-at-most-$n$ approximation would have a difference polynomial with at least $n+1$ roots. Thus it minimizes the maximum node error. Increasing order matters: for the permutation $(0,1/3,1,2/3)$ the alternating interpolant is already the quadratic $-1+9x(1-x)$, so the leading-coefficient assertion for $n=2$ fails.

For a basis $e_1,\dots ,e_n$ of a finite-dimensional vector space $V$, its dual basis consists of linear functionals $e_1^{\ast },\dots ,e_n^{\ast }$ satisfyingThe Kronecker delta means that each rule gives one on its own basis vector and zero on the others. These rules extract coordinates:Applying $e_i^{\ast }$ to a linear combination removes every term except the $i$th. Consequently the dual basis is a basis of the dual space, and every linear functional has expansion $\phi ={\sum }_i\phi (e_i)e_i^{\ast }$. ^[ref].

Coordinate extraction works for a nonorthogonal basis too. With $b_1=(1,0)$ and $b_2=(1,1)$, the dual basis isThe checks $b_1^{\ast }(b_1)=1$, $b_1^{\ast }(b_2)=0$, $b_2^{\ast }(b_1)=0$, and $b_2^{\ast }(b_2)=1$ fix the two rules. For $v=(3,1)$ they give coordinates $(2,1)$, so $v=2b_1+b_2$. The usual dot products with $b_1,b_2$ instead give $3,4$ and do not extract these coordinates: simple projection formulas depend on an orthonormal basis.

The same idea explains polynomial interpolation. On polynomials of polynomial degree at most $n$, evaluation at distinct interpolation nodes $x_0,\dots ,x_n$ gives the dual basis to the Lagrange cardinal polynomials, because ${\ell }_i(x_j)={\delta }_{ij}$. Samples are coordinates in this basis, so the reconstruction $p={\sum }_{i}p(x_i){\ell }_i$ is a dual-basis expansion. Differentiation weights from nodal evaluations and factorial monomial basis for polynomial differentiation apply the same principle to different measurements.

At decreasing distinct interpolation nodes $1\ge t_0>\cdots >t_n\ge -1$, the Lagrange cardinal polynomial $L_i(x)={\prod }_{j\ne i}(x-t_j)/{\prod }_{j\ne i}(t_i-t_j)$ has denominator sign $(-1{)}^i$. For $1\le k\le n$, its numerator's $k$th derivative at one is $k!$ times a sum of products of $n-k$ nonnegative factors $1-t_j$. At most one factor vanishes, and at least one product avoids it, so that sum is strictly positive. The same alternating nodal signs therefore maximize every endpoint derivative simultaneously.

Gaussian quadrature is a quadrature rule that chooses both sample locations and coefficients to achieve unusually high polynomial exactness. For a finite interval $[a,b]$ with $a<b$, assume the integration weight $w$ is integrable and positive almost everywhere. DefineLet $p_n$ be the monic orthogonal polynomial of polynomial degree $n$ for the inner product $⟨u,v{⟩}_w={\int }_a^{b}u(x)v(x)w(x)dx$: it satisfies $⟨p_n,q{⟩}_w=0$ for every polynomial $q$ of polynomial degree below $n$. The polynomial roots of $p_n$ are distinct and inside $(a,b)$; take them as the nodes $x_i$. Integrate the Lagrange cardinal polynomials ${\ell }_i$ to obtain $A_i=I_w({\ell }_i)$. These coefficients are positive, andThe integration weight $w(x)$ and the discrete coefficients $A_i$ play different roles: $w$ specifies the integral being approximated, while $A_i$ tell us how much each sample contributes.^[ref]

A proof outline explains the gain over simply integrating an arbitrary polynomial interpolation. Use polynomial division to write $f=p_{n}q+r$, with $\mathrm{deg}q\le n-1$ and $\mathrm{deg}r\le n-1$. Orthogonality makes $I_w(p_{n}q)=0$, and sampling at the polynomial roots of $p_n$ makes $Q_n(p_{n}q)=0$. The Lagrange cardinal polynomials recover $r$ exactly, so both expressions agree. Also $A_i=Q_n({\ell }_i^2)=I_w({\ell }_i^2)>0$, since ${\ell }_i^2$ has polynomial degree $2n-2$. This is the mechanism behind positive weights of Gaussian quadrature.

For a concrete two-node example, set $w=1$ on $[-1,1]$. The Legendre polynomial $P_2(x)=(3x^2-1)/2$ has polynomial roots $x=\pm 1/\sqrt{3}$. Its monic polynomial version $p_2=x^2-1/3$ has zero integral against both $1$ and $x$, as required. Symmetry and exactness for the constant polynomial give $A_1=A_2=1$. Thus the Gauss–Legendre instance of Gaussian quadrature isDirect evaluation on $1,x,x^2,x^3$ gives $2,0,2/3,0$, exactly their integrals. For the polynomial $f(x)=1+x+x^2+x^3$, two samples therefore give $8/3$ exactly. But for $x^4$ the rule gives $2/9$, whereas the integral is $2/5$: the error $I_1-Q_2$ is $8/45$.

The ceiling $2n-1$ is sharp for $n$ distinct real nodes under the positive-weight assumptions. Their squared nodal polynomial ${\prod }_i(x-x_i{)}^2$ has polynomial degree $2n$, is zero at every sample, and has a strictly positive weighted integral. Thus no such quadrature rule integrates every polynomial of polynomial degree $2n$ exactly. Nor does Gaussian quadrature integrate every nonpolynomial function exactly: the same two-node example gives $Q_2(|x|)=2/\sqrt{3}$, while $I_1(|x|)=1$.

Gaussian quadrature is useful when evaluations are costly and a modest polynomial captures the integrand well. More precisely, for a continuous function $f$ and any polynomial $r$ of polynomial degree at most $2n-1$, positivity and constant exactness giveThe uniform norm on $[a,b]$ measures the approximation between samples. This bound connects quadrature rule accuracy to uniform approximation, rather than promising an error from sample count alone. Corners, sharp unresolved features and roundoff error require their own assessment; the absolute value function example already shows why polynomial exactness is a qualified guarantee.

An interpolation node is an argument value $x_i$ at which an interpolation polynomial must take a prescribed value $y_i$. The interpolation nodes specify where the constraints apply; the values specify how high the graph must pass there. In the three-point example, the interpolation nodes are $0,1,2$, while the prescribed values are $1,2,5$. Changing the interpolation nodes changes the Lagrange cardinal polynomials and the polynomial interpolation error, even if their number stays fixed.

An interpolatory quadrature approximates a definite integral by exactly integrating the interpolation polynomial through prescribed sampled values. For distinct quadrature nodes $x_0,\dots ,x_n$, its quadrature weights are $W_j={\int }_a^b{\ell }_j(x)dx$, where ${\ell }_j$ are the Lagrange cardinal polynomials. It is exact for all polynomials of polynomial degree at most $n$, because polynomial interpolation reproduces them. Newton-Cotes quadrature adds equal spacing of the quadrature nodes.

For distinct interpolation nodes $x_0,\dots ,x_n$, the Lagrange cardinal polynomial ${\ell }_i$ has value one at its own interpolation node and zero at every other interpolation node:Here ${\delta }_{ij}$ is the Kronecker delta. These Lagrange cardinal polynomials form a basis of the vector space of polynomials of polynomial degree at most $n$: every such polynomial has the unique expansion $p(x)={\sum }_{i}p(x_i){\ell }_i(x)$. The nodal evaluation linear functionals $E_j(p)=p(x_j)$ form the dual basis, since $E_j({\ell }_i)={\delta }_{ij}$.

For the interpolation nodes $0,1,2$, the three Lagrange cardinal polynomials areTheir values on the interpolation nodes are the rows of the identity matrix. In the figure, each colored curve passes through its own unit-height marker and through zero at the other two interpolation nodes. Multiplying the curves by the data $1,2,5$ and adding gives the Lagrange polynomial $x^2+1$.

Since the constant polynomial one interpolates data values all equal to one, uniqueness gives ${\sum }_i{\ell }_i(x)=1$. Nevertheless, ${\ell }_2(1/2)=-1/8$, so Lagrange cardinal polynomials need not stay between zero and one. If a single data value $y_i$ changes by $\epsilon$, the interpolation polynomial changes by exactly $\epsilon {\ell }_i(x)$. Thus a Lagrange cardinal polynomial describes how one observation influences the entire graph, and ${\sum }_i|{\ell }_i(x)|$ controls the worst amplification of simultaneous data errors at $x$; its maximum is the Lebesgue constant of interpolation.

For $n+1$ distinct interpolation nodes and an integer $0\le k\le n$,To prove this, the Lagrange interpolation polynomial for the data $x_i^k$ is exactly $x^k$, by uniqueness of polynomial interpolation. The coefficient of $x^n$ in its $i$th Lagrange cardinal polynomial is $1/{\prod }_{j\ne i}(x_i-x_j)$. Comparing the coefficients of $x^n$ gives the identity. At $k=0$, values of the constant polynomial $1$ are intended even at a zero node. Negative exponents are outside the assertion.

The Lagrange polynomial writes the interpolation polynomial as a linear combination of Lagrange cardinal polynomials. Each one selects a single interpolation node, so the data values themselves become the coefficients:Distinct interpolation nodes make every denominator nonzero. At $x_j$, all terms vanish except $y_j{\ell }_j(x_j)=y_j$. This gives an explicit construction without solving for monomial coefficients. The elegance of the Lagrange polynomial is that it builds all constraints into the basis, leaving no equations to solve for the data values.

For $(x_0,x_1,x_2)=(0,1,2)$ and $(y_0,y_1,y_2)=(1,2,5)$, substitution givesAt $x=1/2$, the Lagrange cardinal polynomial values are $3/8,3/4,-1/8$, so $p_2(1/2)=3/8+2(3/4)+5(-1/8)=5/4$. A negative Lagrange cardinal polynomial value is allowed: these weights sum to one but need not be probabilities.

The product form is especially useful for deriving differentiation weights from nodal evaluations and quadrature rules. For repeated numerical evaluation, the barycentric interpolation formula reorganizes the same Lagrange polynomial into precomputed weights and sums; it avoids evaluating every full product at every argument.

Define the Lagrange cardinal polynomialsDistinct nodes make every denominator nonzero. At $x_s$ these polynomials satisfy ${\ell }_r(x_s)={\delta }_{rs}$, so the Lagrange interpolation polynomial isIt has degree at most $n$ and takes the prescribed data values. If two such polynomials existed, their difference would have $n+1$ distinct roots but degree at most $n$, forcing that difference to be zero. This also proves uniqueness.

The relevant uniqueness is uniqueness of the node set, with $n\ge 1$. Reordering the same nodes cannot change a constraint imposed at every node, so an unsorted “different sequence” obtained only by permutation would not give the claimed counterexample. Order the genuinely different nodes as $1\ge t_0>t_1>\cdots >t_n\ge -1$ and let $L_i$ be their Lagrange cardinal polynomials:The denominator has sign $(-1{)}^i$. For $1\le k\le n$, repeated differentiation of its numerator givesAll products are nonnegative. At most one factor $1-t_j$ is zero, and because $n-k\le n-1$, some product omits that factor. The derivative is consequently strictly positive, including when $k=n$, for which the product is empty and equals one. This proves the endpoint derivative signs of Lagrange cardinal polynomials:Choose a single Lagrange interpolation polynomial by prescribing $q(t_i)=(-1{)}^i$:It satisfies $|q(t_i)|=1$ at every prescribed node. Its leading coefficient is ${\sum }_{i}1/|{\prod }_{j\ne i}(t_i-t_j)|>0$, so it has degree exactly $n$. The endpoint sign formula gives $q^{(k)}(1)={\sum }_i|L_i^{(k)}(1)|$ simultaneously for all $k$.

Interpolate the Chebyshev polynomial $T_n$ on the same nodes. Since $|T_n(t_i)|\le 1$,The only points at which $|T_n|=1$ are its $n+1$ extrema. A different set of $n+1$ distinct nodes includes at least one nonextremal point; at that point the bracket is strictly positive, and so is its derivative weight for every $k$. Moreover $T_n^{(k)}(1)>0$: differentiating its differential equation gives $T_n^{(k+1)}(1)=(n^2-k^2)T_n^{(k)}(1)/(2k+1)$, beginning with $T_n(1)=1$ and ending at $k=n-1$. ThusThe same $q$ violates every sharp derivative bound, proving uniqueness of Chebyshev derivative-norming nodes for the given Markov-Duffin-Schaeffer theorem. The result concerns node sets or consistently ordered sequences; a mere permutation is the literal ordering exception noted above.

Order the interpolation nodes as $t_0<\cdots <t_n$, as required by their alternating nodal data. Write $w(x)={\prod }_{j=0}^n(x-t_j)$ and ${\ell }_i(x)=w(x)/[(x-t_i)w^{\prime }(t_i)]$ for the Lagrange cardinal polynomials. Differentiating Lagrange interpolation givesThe upper bound is the triangle inequality; equality follows by choosing each independent nodal value to be the sign of its weight. Thus this is the nodal derivative norm from Lagrange cardinal polynomials.

To identify the maximizing signs, put $P_i=w/(x-t_i)$, a monic polynomial of degree $n$. Since $\mathrm{sign}{w}^{\prime }(t_i)=(-1{)}^{n-i}$,For $0\le k<n$, let ${\xi }_{i,j}$ be the ordered roots of $P_i^{(k)}$, $1\le j\le n-k$. The roots of $P_i$ decrease componentwise as $i$ increases: deleting a later node replaces one retained node by an earlier one. The monotonicity of polynomial critical points in their roots, iterated $k$ times, therefore gives ${\xi }_{n,j}\le \cdots \le {\xi }_{0,j}$. Moreover, $P_n$ and $P_0$ weakly interlace, so the Markov interlacing lemma gives ${\xi }_{0,j}\le {\xi }_{n,j+1}$. Together,These root bands have disjoint interiors. At a fixed $x$, all but at most one band lie wholly on one side of $x$. In the possible remaining band, ${\xi }_{i,j}$ moves monotonically as $i$ increases. Since the leading coefficients of all $P_i^{(k)}$ are positive, the sequence $P_i^{(k)}(x)$ has at most one sign change after zero entries are ignored. The same holds for $(-1{)}^i{\ell }_i^{(k)}(x)$. If $k=n$, every $P_i^{(n)}=n!>0$, so the conclusion also holds.

The maximizing nodal signs can consequently be chosen as $\pm (-1{)}^i$ throughout, or as $\pm (-1{)}^i$ before one index $s$ and $\mp (-1{)}^i$ from that index onward. Zero weights can be assigned either sign to complete such a pattern. These are precisely the nodal values of $\pm p^{\ast }$ or $\pm q_s$, provingThe argument works for all real $x$, hence in particular for $[-1,1]$. For $k>n$ every derivative vanishes and the result is immediate.

Enumerate the finite set increasingly, $y_1<\cdots <y_{n+2}$, so alternating signs refer to spatial order. This is the enumeration needed for the interpolation construction below. The Lagrange cardinal polynomials satisfy $r_j(y_k)={\delta }_{jk}$ and have degree $n+1$.

If the printed indexing were interpreted as an arbitrary fixed permutation, the assertion in (a) would need this qualification. For example with $n=2$, $(y_1,y_2,y_3,y_4)=(0,1/3,1,2/3)$ gives $r(x)=-1+9x(1-x)$ of degree two; for $f=0$ every $\lambda$ works. Ordering the nodes resolves the issue and yields the requested minimizer for every set $Y$.

The Lagrange cardinal polynomials areThus the Lagrange interpolation polynomial isIt has degree at most $n$ and takes the required values. Uniqueness follows because the difference of two such polynomials has $n+1$ distinct roots and degree at most $n$, so is zero. The source's phrase “degree $n$” must allow a smaller degree, for example when $f$ is constant.

Define the divided difference recursively by $f[x_i]=f_i$ andInduction on this recursion, or comparison of the leading coefficient in the Newton interpolation polynomial, givesFor completeness the induction works term by term: an interior term gets the coefficient $(1/(x_i-x_n)-1/(x_i-x_0))/(x_n-x_0)=1/((x_i-x_n)(x_i-x_0))$, multiplying the product over the other interior nodes; the two endpoint terms give the same formula. This is also the leading coefficient of $p$ directly from the cardinal formula, so $p^{(n)}=n!f[x_0,\dots ,x_n]$.

The function $f-p\in C^n[x_0,x_n]$ has $n+1$ distinct zeros. Repeated application of Rolle theorem gives $\xi \in (x_0,x_n)$ with $(f-p{)}^{(n)}(\xi )=0$ when $n\ge 1$. HenceFor $n=0$, this is simply $f[x_0]=f(x_0)$ and we take $\xi =x_0$.

The polynomial $p_n$ interpolates $f$ at the interpolation nodes whenFor distinct interpolation nodes, define the Lagrange cardinal polynomialsThe denominators are nonzero, each polynomial degree is at most $n$, and ${\ell }_i(x_j)={\delta }_{ij}$, with ${\delta }_{ij}$ the Kronecker delta. Thereforeis a Lagrange interpolation polynomial belonging to the vector space of univariate polynomials ${\Pi }_n$, and it has all the required sampled values.

If $r_n\in {\Pi }_n$ also works, $p_n-r_n$ has $n+1$ distinct roots of a polynomial while its polynomial degree is at most $n$. The root bound for a polynomial forces it to be the zero polynomial, proving uniqueness. The phrase “degree $n$” denotes the allowed maximum; the actual polynomial degree may be smaller. No continuity assumption is needed merely to construct the interpolation polynomial from these finitely many values.

For each interpolation node define the Lagrange cardinal polynomialAll denominators are nonzero because the interpolation nodes are distinct. Each polynomial has polynomial degree at most $n$, and ${\ell }_j(x_i)={\delta }_{ij}$, where ${\delta }_{ij}$ is the Kronecker delta. Consequently the linear combinationbelongs to the vector space of univariate polynomials ${\Pi }_n$ and has the required values. This proves existence of the Lagrange interpolation polynomial.

For uniqueness, suppose $p_n$ and $r_n$ both work. Their difference is a polynomial of polynomial degree at most $n$ with $n+1$ distinct roots of a polynomial. The root bound for a polynomial forces $p_n-r_n$ to be the zero polynomial.

The seven supplied values follow $f_i=i^2+1$. The quadratic polynomial $x^2+1$ belongs to ${\Pi }_6$ and takes all seven values, so uniqueness givesThe subscript bounds the polynomial degree; it does not require polynomial degree exactly six.

A Newton-Cotes quadrature integrates a Lagrange interpolation polynomial at equally spaced quadrature nodes. For the Newton-Cotes closed quadrature, the endpoints are included: write $x_j=a+jh$, $h=(b-a)/n$, and useThese quadrature weights depend on the quadrature nodes, not on the sampled function. Open Newton-Cotes quadrature uses equally spaced interior quadrature nodes instead.

For Simpson's rule, use $n=2$ and set $x=a+ht$, so $0\le t\le 2$. The Lagrange cardinal polynomials becomeIntegrating these quadratic polynomials gives $1/3$, $4/3$, $1/3$, respectively. The change of variable contributes $h$, soIts degree of precision of a quadrature rule is three: it integrates every quadratic polynomial by construction, and also the cubic nodal polynomial $(x-a)(x-a-h)(x-b)$, whose integral vanishes by odd symmetry about $a+h$. Any cubic polynomial differs from its quadratic polynomial interpolant by a constant multiple of this nodal polynomial.

Let $L_{n+1}$ denote the conventional Legendre polynomial, normalized by $L_{n+1}(1)=1$. The $n+1$ quadrature nodes are its distinct polynomial roots in $(-1,1)$. For these nodes form the Lagrange cardinal polynomialsChoose the quadrature weights by integrating these polynomials:An equivalent standard formula isThe reason for selecting these quadrature nodes is the resulting degree of precision of a quadrature rule. For any polynomial $p$ of polynomial degree at most $2n+1$, polynomial division givesThe orthogonality of the Legendre polynomial makes ${\int }_{-1}^1{L}_{n+1}s=0$, while $p(x_i)=r(x_i)$ at each quadrature node. The definition of the quadrature weights integrates $r$ exactly, soIn particular, ${\sum }_i{w}_i=2$. Applying this exactness to ${\ell }_i^2$ also proves $w_i={\int }_{-1}^1{\ell }_i(x{)}^{2}dx>0$.

For the distinct interpolation nodes, define the Lagrange cardinal polynomialsEvery denominator is nonzero, each $L_i$ has polynomial degree at most $n$, and $L_i(x_j)={\delta }_{ij}$. Hence the Lagrange interpolation polynomialbelongs to ${\Pi }_n$ and has $p_n(x_j)=f_j$. This proves existence.

If $p_n$ and ${\tilde{p}}_n$ both fit the data, their difference has polynomial degree at most $n$ but vanishes at the $n+1$ distinct interpolation nodes. Repeated application of the factor theorem implies that ${\prod }_{j=0}^n(x-x_j)$ divides that difference. A nonzero polynomial of degree at most $n$ cannot have such a divisor of degree $n+1$. Thus $p_n-{\tilde{p}}_n=0$, proving uniqueness. When $n=0$, the empty product defining $L_0$ is $1$, so the argument includes the constant case.

A piecewise-linear hat function is a continuous piecewise linear function that selects one node of a finite element mesh: it is one there and zero at every other node. For an interior node $x_i$, its exact formula on a possibly nonuniform mesh isIts support of a function is $[x_{i-1},x_{i+1}]$. It rises on the left interval and falls on the right, producing its hat-shaped graph. The interior hat functions form a basis of the continuous $P_1$ conforming finite element space with homogeneous Dirichlet boundary conditions. Chen's author notes define this nodal basis and illustrate it in one and two dimensions.^[ref] The nodal property ${\varphi }_i(x_j)={\delta }_{ij}$ makes the coefficients directly readable: if $v_h={\sum }_i{c}_i{\varphi }_i$, then $v_h(x_i)=c_i$. Unlike the global Lagrange cardinal polynomials, each of these functions is confined to two neighboring elements.

For example, with $x_j=j/4$, the middle hat function is ${\varphi }_2(x)=4x-1$ on $[1/4,1/2]$, $3-4x$ on $[1/2,3/4]$, and zero elsewhere. Hence ${\varphi }_2(3/8)=1/2$, while ${\varphi }_1(3/8)=1/2$ and ${\varphi }_3(3/8)=0$. The finite element solution of the one-dimensional Poisson equation therefore has $u_h(3/8)=(3/32)/2+(1/8)/2=7/64$.

Local assembly makes this locality computational. On an element $[a,b]$ of length $d=b-a$, the two local basis functions are $N_L=(b-x)/d$ and $N_R=(x-a)/d$. For the Poisson equation with unit forcing, their local stiffness matrix and load vector areAdd these four matrix entries and two loads to the rows and columns belonging to the element's endpoints, then impose the prescribed boundary values. An interior node receives contributions from its two neighboring elements. Writing $d_L=x_i-x_{i-1}$ and $d_R=x_{i+1}-x_i$ giveswith off-diagonal entries included only for interior neighbors. On a uniform mesh these reduce to $2/h$, $-1/h$ and $h$. Nonadjacent hat functions have no derivative overlap of positive length, so all distant entries vanish. This produces a sparse matrix with only three diagonals: the global coupling is built entirely from local two-node interactions.