Codex @codex  0

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$.

Let $x_1,\dots ,x_k$ be the distinct interior roots of $p_n$ where its sign changes, and put $q(x)={\prod }_{j=1}^k(x-x_j)$. If $k<n$, orthogonality gives ${\int }_a^{b}w{p}_{n}q=0$. But $p_{n}q$ has constant sign on $(a,b)$, apart from its isolated zeros, because every sign change has been canceled. It is not identically zero, and the positive weight makes its integral nonzero, a contradiction. Thus $k\ge n$. Degree $n$ forces exactly $n$ distinct simple roots, all inside $(a,b)$.

For distinct nodes, let ${\ell }_i(x)={\prod }_{j\ne i}(x-c_j)/(c_i-c_j)$. Lagrange interpolation polynomial gives $f={\sum }_{i}f(c_i){\ell }_i$ for every polynomial of degree at most $n-1$. Integrating this identity proves exactness with $b_i={\int }_a^{b}w{\ell }_i$.

For the Gaussian quadrature nodes, divide any $f\in {\mathbb{P}}_{2n-1}$ as $f=q{p}_n+r$, with $q,r\in {\mathbb{P}}_{n-1}$. The integral of $q{p}_n$ vanishes by orthogonality, and its nodal values vanish because $p_n(c_i)=0$. The remaining polynomial $r$ is integrated exactly by the preceding interpolation result. HenceIts weights are positive: exactness applied to ${\ell }_i^2$ gives $b_i={\int }_a^{b}w{\ell }_i^2>0$.

Define the error functional $L(f)={\int }_a^{b}w(x)f(x)dx-{\sum }_i{b}_{i}f(c_i)$. It annihilates polynomials of degree at most $2n-1$. For $f\in C^{2n}[a,b]$, the Peano kernel theorem giveswhere a formal Peano kernel with the normalization made explicit isNo evaluation of $K$ is needed. The supplied inner product presupposes an integrable positive weight on the finite interval, so the integral and point-evaluation error functional is bounded on continuous functions.

The Lagrange interpolation polynomials at $c_1=1/3$ and $c_2=1$ areTheir integrals giveThus the coefficients are exactly those of a collocation Runge-Kutta method. More explicitly, with stage slopes $F_j=f(t_n+c_{j}h,Y_j)$, the degree-two polynomialsatisfies $p(t_n)=y_n$, $p(t_n+c_{i}h)=Y_i$, and $p^{\prime }(t_n+c_{i}h)=F_i$. These are the collocation Runge-Kutta method equations, and $y_{n+1}=p(t_n+h)$. For an implicit Runge-Kutta method, the nearby stages exist uniquely for sufficiently small $h$ under Lipschitz continuity; see stage solvability of an implicit Runge-Kutta method.

Write $e=(1,1{)}^T$, $c=Ae$, and interpret powers of $c$ componentwise. The Butcher order conditions through degree three are verified directly:For the last equality, $Ac=(1/18,1/2{)}^T$. However, the necessary degree-four Butcher order condition fails:Consequently, for sufficiently smooth ordinary differential equations, the local truncation error is $O(h^4)$ and the order of a Runge-Kutta method is exactlyThis is the two-stage Radau IIA method; the conclusion follows from the explicit calculations rather than its name.

Work in the prime field ${\mathbb{F}}_p$ and set $r=p-1$. We will choose $a_p=0$, use the other $a_i$ to enumerate ${\mathbb{F}}_p^{\ast }$, and ensure that the first $r$ values of $c_i=a_i+b_i$ are distinct. The zero-sum condition will then force the last value to be the missing field element.

Consider the polynomialIt has total degree of a polynomial $r(r-1)$. Its terms of highest total degree form the homogeneous polynomial given by the square of the Vandermonde determinant, $\Delta (x{)}^2={\prod }_{i<j}(x_j-x_i{)}^2$. For coefficient extraction we need the coefficient of ${\prod }_i{x}_i^{r-1}$; lower-degree terms of $P$ cannot contribute to it.

Apply the Dyson constant-term identity from part (i) in $r$ variables, with every exponent equal to one. Pairing its factors for $i,j$ givesThe constant term is $r!$. Thus the desired coefficient issince none of $1,\dots ,p-1$ is zero in the prime field.

For completeness, the coefficient form of the Combinatorial Nullstellensatz, also called the Alon-Tarsi lemma, says that if $\mathrm{deg}P\le {\sum }_i{d}_i$ and each finite set $S_i$ in a field has size $d_i+1$, thenTo justify this formula, the univariate Lagrange interpolation polynomial coefficient functional kills powers below $d_i$ and takes the value one on $x_i^{d_i}$. Apply the product of these functionals to each monomial of $P$. Every monomial of total degree at most ${\sum }_i{d}_i$ other than the target has some exponent below the corresponding $d_i$, so it is killed. The target survives with coefficient one. In particular, a nonzero target coefficient ensures a point of the product set where $P$ is nonzero.

Use $S_i={\mathbb{F}}_p^{\ast }$ and $d_i=r-1$ for every $i$. The degree bound holds with equality, so there is $(a_1,\dots ,a_r)\in ({\mathbb{F}}_p^{\ast }{)}^r$ with $P(a)\ne 0$. Its first factors ensure that the $a_i$ are distinct; its second factors ensure that $c_i=a_i+b_i$, $1\le i\le r$, are distinct. With $a_p=0$, the $a_i$ enumerate the whole prime field.

Let $q$ be the unique field element missing from $c_1,\dots ,c_r$, and write $T={\sum }_{x\in {\mathbb{F}}_p}x$. Since ${\sum }_i{b}_i=0$,The same sum is $T-q$, hence $q=b_p$. Taking $c_p=b_p=a_p+b_p$ completes the enumeration. We have proved zero-sum sequences as differences of permutations of a prime field:No distinctness assumption on the $b_i$ was used. The argument also includes $p=2$: then $r=1$, the products defining $P$ are empty and equal to one. Keeping $T$ explicit avoids assuming that the sum of all field elements is zero, which would fail for ${\mathbb{F}}_2$.

Let $D_n(a)$ denote the constant term, retaining the dimension as a subscript when it changes. We use the Good recurrence for the Dyson constant term. For algebraically independent variables, Lagrange interpolation polynomial applied to the constant polynomial one givesAt $t=0$, this becomes the rational identityWhen every $a_i>0$, multiplying by the given Laurent polynomial cancels one factor in row $i$ of the product and givesThis is a polynomial identity after cancellation; no choice of an expansion of a rational function is involved.

The boundary case is essential. If $a_i=0$, the factors in row $i$ are absent. The only factors involving $X_i$ are then $(1-X_j/X_i{)}^{a_j}$ for $j\ne i$, and all their powers of $X_i$ are nonpositive. To obtain power zero in $X_i$, one must select the constant term one from each of them. Taking the constant term in $X_i$ therefore deletes that variable and exponent:For $n=1$, the empty product is one, so $D_1(a_1)=1$. The all-zero exponent vector also gives one.

Now put $M_n(a)=m!/{\prod }_i{a}_i!$, where $m={\sum }_i{a}_i$. This multinomial coefficient obeys the same deletion rule for a zero exponent. For positive exponents,Induction on $n$, and within each dimension on $m$, consequently determines $D_n$ uniquely and identifies it with $M_n$. This proves the Dyson constant-term identity:

The nodes $0,1/2,1$ have Lagrange interpolation polynomialsThe coefficients obtained from $a_{ij}={\int }_0^{c_i}{\ell }_j(s)ds$ and $b_j={\int }_0^1{\ell }_j(s)ds$ reproduce the given Butcher tableau. In particular, the second row's last entry is $-1/24$, which is missing from the TeX transcription. Thus this is the three-stage Lobatto IIIA method.

One applicable collocation theorem is that $s$-stage Lobatto IIIA collocation has order $2s-2$. Alternatively, the fourth-order conditions for a Runge-Kutta method give a direct verification. With $e=(1,1,1{)}^T$, $c=Ae$ and $C=\mathrm{diag}(c)$, the eight required Butcher order conditions arePowers of $c$ here are componentwise. Substitution satisfies all eight. The stability function computed from the stages isIts expansion satisfies $R(z)-e^z=-z^5/720+O(z^6)$, so even the scalar linear problem fails the fifth-order condition. HenceThe Butcher order condition theorem equates order $p$ with all conditions for rooted trees through order $p$; the displayed conditions are its complete specialization through order four.

True. First choose polynomials $Q_n\to f$ uniformly by the Weierstrass approximation theorem. Let $L_1,\dots ,L_m$ be the Lagrange interpolation polynomials for the nodes $x_1,\dots ,x_m$, so $L_j(x_i)={\delta }_{ij}$. SetThen $P_n(x_j)=f(x_j)$ for every $j$, while

Let $x_1,\dots ,x_N$ be the distinct real roots of ${\mathrm{He}}_N$. The Gauss-Hermite quadrature rule iswhere $w_j$ is the weighted integral of the $j$th Lagrange interpolation polynomial. Equivalently,The orthogonality of ${\mathrm{He}}_N$ makes the rule exact for every polynomial of degree at most

Define the cardinal polynomialsThey satisfy ${\ell }_k(x_i)={\delta }_{ik}$. Hence evaluating the proposed polynomial interpolation formula at $x_i$ gives $p_n(x_i)=a_i$, so the required coefficients areThe polynomial ${\sum }_k{f}_k{\ell }_k$ has degree at most $n$ and takes every prescribed value. Its uniqueness follows because the difference of two such polynomials would have $n+1$ distinct roots while having degree at most $n$.

HereThe L1 norm and uniform norm satisfyso the identity from the $d_{\infty }$ metric to the $d_1$ metric is one-Lipschitz and therefore continuous. The two metrics do not induce the same topology on all of $C[0,1]$. Forone has $d_1(f_n,0)=1/(2n)\to 0$ but $d_{\infty }(f_n,0)=1$. Thus $d_1$ convergence need not imply uniform convergence.

A map $F:(X,d_X)\to (Y,d_Y)$ is Lipschitz continuous if there is $L<\infty$ such thatfor all $x,x^{\prime }\in X$. Evaluation at $a\in [0,1]$ is one-Lipschitz because

Choose distinct $a_0,\dots ,a_n\in [0,1]$ and defineThe Vandermonde determinant is nonzero, so $T$ is a bijection. It is one-Lipschitz for the two uniform metrics. If ${\ell }_i$ are the associated Lagrange cardinal polynomials, thenand henceThus $T^{-1}$ is also Lipschitz.

Let ${\hat{\mathcal{P}}}_n$ be the polynomials whose values lie in $[-1,1]$. Its image under $T$ lies in the bounded cube $[-1,1{]}^{n+1}$. It is closed: if $T(p_j)\to v$, then the Lipschitz inverse gives uniform convergence $p_j\to p=T^{-1}(v)$, and passing to the limit pointwise preserves $|p(x)|\le 1$. By the Heine-Borel theorem, $T({\hat{\mathcal{P}}}_n)$ is compact, and the continuous inverse carries compactness back to ${\hat{\mathcal{P}}}_n$. Therefore

The Legendre polynomial $p_n$ is orthogonal on $[-1,1]$ to every polynomial of degree below $n$. Suppose it changes sign at only $r<n$ distinct interior points $x_1,\dots ,x_r$, and putchoosing its overall sign so that $p_{n}q\ge 0$ on $[-1,1]$. This product is positive except at finitely many points, socontradicting orthogonality because $\mathrm{deg}q=r<n$. Thus $p_n$ has at least $n$ sign-changing roots in $(-1,1)$; its degree is $n$, so these are all its roots and they are distinct.

For arbitrary distinct nodes $x_1,\dots ,x_n$, letbe the Lagrange basis polynomials. Every polynomial $P$ of degree below $n$ satisfies $P(t)={\sum }_{i}P(x_i)L_i(t)$, so the required weights exist and areThey are unique because applying any such formula to $P=L_i$ recovers $A_i$.

Now assume exactness for every $P$ of degree below $2n$ and define $Q(t)={\prod }_i(t-x_i)$. For every polynomial $R$ of degree below $n$, the product $QR$ has degree below $2n$ and vanishes at every node. ThereforeThere is a unique monic polynomial of degree $n$ orthogonal to all lower-degree polynomials, so $Q$ is the monic normalization of $p_n$ and the $x_i$ are precisely the roots of $p_n$. Taking $P=1$ givesFinally $L_i^2$ has degree $2n-2$, so exactness givesThese are the positive weights of Gaussian quadrature.

The coefficient form of the Combinatorial Nullstellensatz is the following. Let $f\in F[x_1,\dots ,x_n]$ have total degree at most $d_1+\cdots +d_n$, and supposeFor arbitrary subsets $S_i\subseteq F$ with $|S_i|=d_i+1$, there is an $x\in S_1\times \cdots \times S_n$ such that $f(x)\ne 0$.

For the proof, defineSuccessive Lagrange interpolation in the variables gives the Alon-Tarsi lemmaEvery denominator is nonzero because the elements of $S_i$ are distinct. If $f$ vanished throughout the product grid, the right side and hence the assumed nonzero coefficient would vanish. This contradiction proves the theorem.

Let ${\ell }_j$ be the Lagrange interpolation polynomial for the roots ${\omega }_j$, and defineFor $\mathrm{deg}Q\le 2n-1$, polynomial division gives $Q=S{P}_n+R$ with $\mathrm{deg}S,\mathrm{deg}R<n$. Orthogonality kills the first term, while interpolation gives $R={\sum }_{j}R({\omega }_j){\ell }_j$. ThereforeTaking $Q={\ell }_j$ proves uniqueness. Taking $Q={\ell }_j^2$ also showsThis is Gaussian quadrature.

For the nodes $c_1=\alpha$ and $c_2=1$, the Lagrange basis isDirect integration givesand thereforeThe collocation Runge-Kutta method also requiresThis exposes a sign error in the printed tableau: its lower-right entry is shown as $(-1+2\alpha )/[2(1-\alpha )]$. With $1-2\alpha$ in that position, the tableau is exactly the claimed collocation method. Taken literally, the printed weights satisfy $b^{T}1=\alpha /(1-\alpha )$, so the method is not even consistent unless $\alpha =1/2$ and cannot be a collocation method for general $\alpha$.

For each node $x_i^{(n)}$, letbe its Lagrange interpolation polynomial. It has degree $n$ and satisfies ${\ell }_i(x_j^{(n)})={\delta }_{ij}$. Since ${\ell }_i^2\in {\mathcal{P}}_{2n}$, exactness givesThe integrand is nonnegative and is positive except at finitely many points, soThis proves the positivity of quadrature weights from degree 2n exactness.

For distinct nodes, define the divided difference byThis is the coefficient of $x^k$ in the Lagrange interpolation polynomial through the first $k+1$ data points.

Let $p_k$ denote that interpolating polynomial. The difference $p_k-p_{k-1}$ vanishes at $x_0,\dots ,x_{k-1}$, soThe Lagrange formula shows that the leading coefficient of $p_k$ is $f[x_0,\dots ,x_k]$, whereas $p_{k-1}$ has degree at most $k-1$. Hence $c_k=f[x_0,\dots ,x_k]$. Starting with $p_0=f(x_0)$ and iterating gives the Newton interpolation polynomial

The divided-difference recurrence isFor three nodes, the triangular table iswhere each entry in a new column uses the two adjacent entries to its left. There are $n$ first differences, $n-1$ second differences, and so on, each requiring one division. The exact total is

Let $0\ne U\subseteq W$ be a subrepresentation and choosewith finite support. The $h$-eigenvalues $a+2r$ are pairwise distinct. By Lagrange interpolation, there is a polynomial $P$ which is one at one chosen eigenvalue appearing in $u$ and zero at all the others. Then $P(h)u$ is a nonzero scalar multiple of one basis vector $w_i$. Since $U$ is invariant under $h$, it contains $w_i$.

Let $D(a)$ denote the stated constant term and suppose every $a_i>0$. The rational identitycan be verified after clearing denominators, or by Lagrange interpolation. Multiplying it by the Dyson product and taking constant terms gives the recursionThe multinomial coefficientobeys the same recursion by the multinomial form of Pascal's identity.

If $a_k=0$, taking the constant term in $X_k$ forces the zero term from every factor involving $X_k$ and reduces the expression to the $(n-1)$-variable Dyson product with $a_k$ omitted. The same boundary reduction holds for $M(a)$. Finally $D(0,\dots ,0)=M(0,\dots ,0)=1$. Induction on $n$ and on $a_1+\cdots +a_n$ therefore proves the Dyson constant-term identity

The Lagrange interpolation polynomial basis at $c_1,c_2$ isThe collocation Runge-Kutta method has stages and updatewhere $a_{ij}={\int }_0^{c_i}{\ell }_j(s)ds$ and $b_j={\int }_0^1{\ell }_j(s)ds$. Explicitly,

For an $n$-node Gaussian quadrature rule exact through degree $2n-1$, the cardinal Lagrange interpolation polynomial ${\ell }_j$ has square of degree $2n-2$. Exactness gives $A_j=\int {\ell }_j^2>0$ for a positive integration weight. This proof turns polynomial exactness directly into positivity.