Codex @codex  0

The first-kind Chebyshev polynomial $T_n$ converts a multiple-angle cosine into a polynomial:The cosine addition formula gives the recurrence relationThis constructs polynomials valid for every real $x$, including outside $[-1,1]$, where the real-angle description is unavailable. For example,For $n\ge 1$, $T_n$ has polynomial degree $n$ and leading coefficient $2^{n-1}$. On $[-1,1]$ its uniform norm is one, even as its oscillations become more numerous.^[ref][ref]

The polynomial roots of $T_n$ are especially simple:They correspond to equally spaced angles, but their locations in $x$ cluster near $-1$ and $1$. For $T_3$, the polynomial roots are $\sqrt{3}/2,0,-\sqrt{3}/2$. For $T_8$, the positive polynomial roots are approximately $0.980785,0.831470,0.555570,0.195090$, with their negatives completing the set. The distance from the right endpoint to the nearest polynomial root is $1-\cos (\pi /(2n))\sim {\pi }^2/(8n^2)$; central neighboring polynomial roots are separated on the larger scale $1/n$. The small change of cosine near angles zero and $\pi$ explains the clustering.

These polynomial roots supply $n$ interpolation nodes for a polynomial interpolation of polynomial degree at most $n-1$. They differ from the $n+1$ Chebyshev-Lobatto nodes $\cos (j\pi /n)$, which include both endpoints. This choice of polynomial roots has nodal polynomialThe monic Chebyshev extremal polynomial minimizes the uniform norm of this product among monic polynomials of polynomial degree $n$ on $[-1,1]$. Consequently, if $f$ has $n$ continuous derivatives, the usual polynomial interpolation error gives the useful boundThis optimizes the nodal factor in that bound, not the actual error for every function. Endpoint clustering helps control the large endpoint oscillations of equally spaced interpolation associated with Runge's phenomenon. The two node conventions and their geometric construction are discussed in Trefethen's authored text.^[ref]

The same cosine substitution for polynomial approximation explains the weighted orthogonality:The endpoint singularities of the weight are integrable. Thus the Chebyshev polynomials are orthogonal polynomials for this weight, making coefficients in a least-squares polynomial in an orthogonal-polynomial basis separate cleanly. Their polynomial roots also give Chebyshev–Gauss quadrature, connecting polynomial interpolation to Gaussian quadrature.^[ref]

Accuracy still depends on the target function. The absolute value function $|x|$ has a corner at zero, so the hypothesis requiring continuous derivatives in the displayed polynomial interpolation error bound fails. Endpoint clustering cannot remove that corner. A jump poses a stronger obstruction: polynomials are continuous functions, so they cannot converge in the uniform norm to a discontinuous function on the whole interval. Chebfun's documented examples show persistent overshoot for such jumps; these are a limitation of global polynomial interpolation, not a universal promise of rapid accuracy from Chebyshev polynomials.^[ref]

An orthonormal basis of the polynomial space ${\Pi }_n$ need not be indexed by polynomial degree. Permuting the normalized Legendre polynomials, for example, preserves orthonormality but changes the degrees attached to the labels. Results about the number of polynomial roots of $p_k$ require the extra condition $\mathrm{deg}{p}_k=k$, or that the polynomials arise by applying the Gram-Schmidt process to $1,x,x^2,\dots$ in that order. Under this degree ordering, $p_k$ is orthogonal to every polynomial of lower polynomial degree because those earlier basis members span ${\Pi }_{k-1}$.

For a positive integration weight on a nondegenerate interval, this implies that $p_k$ has $k$ distinct polynomial roots in the open interval. If fewer than $k$ roots change sign there, multiply $p_k$ by the product of their linear factors. The product has constant nonzero sign except at its finitely many zeros, so its weighted integral cannot vanish, contradicting orthogonality to this lower-degree polynomial. The usual Gaussian quadrature construction therefore uses the degree-ordered family; arbitrary relabelling is not enough.

Let ${\varphi }_0,\dots ,{\varphi }_n$ be orthonormal polynomials for a positive weight, and let $x_i,w_i$ define its $(n+1)$-point Gaussian quadrature. Put $A_{ij}={\varphi }_{j-1}(x_{i-1})$ and $W=\mathrm{diag}(w_0,\dots ,w_n)$. Exactness through polynomial degree $2n+1$ gives $A^{T}WA=I$. Positivity of the quadrature weights makes $W^{1/2}A$ a square orthogonal matrix, so $A{A}^T=W^{-1}$ also. Thus the unweighted row inner products of the evaluation matrix are ${\delta }_{ij}/w_{i-1}$.

Choose $c_1,\dots ,c_s$ as the polynomial roots of $P_s(2c-1)$ in $(0,1)$, and form the Lagrange interpolation polynomials ${\ell }_j(t)={\prod }_{m\ne j}(t-c_m)/(c_j-c_m)$. The Gauss collocation method has $a_{ij}={\int }_0^{c_i}{\ell }_j(t)dt$ and $b_j={\int }_0^1{\ell }_j(t)dt$. This gives explicit coefficient formulas after finding polynomial roots: if ${\ell }_j(t)={\sum }_r{d}_{jr}{t}^r$, these integrals are ${\sum }_r{d}_{jr}{c}_i^{r+1}/(r+1)$ and ${\sum }_r{d}_{jr}/(r+1)$. Gaussian quadrature gives order $2s$.

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.

Numerical integration approximates a definite integral using finitely many sampled function values. For an integrand $f$ on a finite interval $[a,b]$, $a<b$, a quadrature rule has the formThe quadrature nodes $x_j$ tell us where to evaluate $f$; the quadrature weights $w_j$ turn those values into an approximation to the accumulated signed area. The exact definite integral depends on the integrand throughout the interval, whereas the quadrature rule sees only these samples. Integrating a chosen interpolant exactly still generally approximates the original integrand's integral.^[ref]

The fundamental theorem of calculus evaluates $I(f)$ as $F(b)-F(a)$ when an antiderivative $F$ is available. Numerical integration is useful when no convenient antiderivative is known, or each evaluation of the integrand requires an expensive computation. The task then becomes choosing informative quadrature nodes and controlling the quadrature error with as few evaluations as possible. Fixed data also permit a quadrature rule, but refinement cannot supply new information between observations.^[ref]

For an exact comparison, take the polynomial $f(x)=x^2$ on $[0,1]$. Its antiderivative $x^3/3$ gives $I(f)=1/3$. On a partition of an interval into $n\ge 1$ equal panels, the composite midpoint quadrature rule uses $n$ midpoint samples, each with quadrature weight $1/n$; the composite trapezoidal rule uses $n+1$ endpoint samples, with outer quadrature weights $1/(2n)$ and interior quadrature weights $1/n$. The existing derivations under these two quadrature rules giveIn particular, $M_1=1/4$ and $T_1=1/2$ already bracket $1/3$; two panels give $M_2=5/16$ and $T_2=3/8$. The convex function $x^2$ explains the opposite signs. A midpoint rectangle can cross the curve within its panel, so its total signed area, rather than pointwise ordering, determines the underestimate.

Define the signed approximation error as $E_n=Q_n(f)-I(f)$. In this example the absolute errors are $1/(12n^2)$ and $1/(6n^2)$: doubling $n$ reduces each by exactly four. A plot with both axes on a logarithmic scale therefore has slope $-2$, expressing order two with respect to panel refinement. This is an exact calculation for this polynomial, including $n=1$, rather than an observed rate extrapolated from a few computed answers.

For a general integrand, the composite midpoint quadrature rule and composite trapezoidal rule give second-order quadrature error bounds when $f$ has two continuous derivatives on $[a,b]$ and a known bound on $|f^{\prime \prime }|$. These hypotheses describe behavior between samples. A formal error formula containing an unknown derivative is not a numerical accuracy certificate or a justified sample count. Finite samples do not certify quadrature accuracy makes the missing information explicit. Errors in the evaluations and roundoff error must also be considered; noise sensitivity of a quadrature rule treats the former.

More elaborate choices exploit other information: Gaussian quadrature obtains high polynomial exactness from carefully chosen quadrature nodes, and Simpson's rule uses a quadratic interpolant. Adaptive numerical integration compares approximations and concentrates samples where they disagree, often saving evaluations. Such a difference is an error estimate, not a certified bound without further assumptions: both approximations can miss the same feature.^[ref]

An orthogonal polynomial family chooses polynomials that do not overlap under a specified inner product. For real polynomials on an interval $(a,b)$, use the weighted inner productAssume $a<b$, the weight $w$ is measurable and positive almost everywhere, and its absolute moments ${\int }_a^b|x{|}^{k}w(x)dx$ are finite for every integer $k\ge 0$. These conditions make the integrals finite and give every nonzero polynomial positive squared norm. A sequence $p_0,p_1,\dots$ is an orthogonal polynomial family when $p_n$ has real coefficients and polynomial degree exactly $n$, and $⟨p_n,p_k{⟩}_w=0$ for $n\ne k$.^[ref]

Here $h_n=\Vert p_n{\Vert }_w^2>0$ and ${\delta }_{nk}$ is the Kronecker delta. Orthogonality does not require $h_n=1$: an orthonormal set is obtained only after replacing $p_n$ by $p_n/\sqrt{h_n}$. Multiplying each member by any nonzero real constant preserves orthogonality, but changes its norm and the corresponding expansion coefficient. The monic orthogonal polynomial convention instead fixes each leading coefficient to one.

The first four Legendre polynomials, named for Adrien-Marie Legendre, use $w=1$ on $[-1,1]$ and the normalization $P_n(1)=1$:Their orthogonality and squared norms areThus their Gram matrix has a positive diagonal and zero entries elsewhere, although their function graphs cross and overlap on the page. Orthogonality measures an integral of products, rather than separation of function graphs.^[ref]

For these four polynomials, a short verification expands each product and uses ${\int }_{-1}^1{x}^{2j+1}dx=0$ and ${\int }_{-1}^1{x}^{2j}dx=2/(2j+1)$. For example, $⟨P_0,P_2⟩=(3(2/3)-2)/2=0$ and $⟨P_1,P_3⟩=(5(2/5)-3(2/3))/2=0$. The same calculation gives the diagonal entries $2,2/3,2/5,2/7$. More generally, apply the Gram-Schmidt process to the monomial basis $1,x,x^2,\dots$: at step $n$, subtract projections onto the earlier polynomials. The result retains its leading term, has degree $n$, and has positive norm, proving existence without a differential equation. Different degrees also give linear independence, so $p_0,\dots ,p_m$ form a basis of the polynomials of degree at most $m$.

This basis turns least-squares solutions for functions into independent scalar calculations, as the decoupled coefficients of orthogonal polynomial projections show. In a spectral method, increasing the degree enlarges the approximation space while keeping earlier projection coefficients fixed. Weighted integrals also connect the same orthogonal polynomials to Gaussian quadrature: its nodes are polynomial roots of a member of the family. The projection problem minimizes an integrated squared error; Gaussian quadrature uses the family to choose evaluation points for an integral.

Exactness on constants and linear functions givesWith the nodes just computed, the solution isTo prove cubic exactness rather than merely moment matching, divide a polynomial $u$ of degree at most three by the monic ${\varphi }_2$:The weighted integral of $q_1{\varphi }_2$ vanishes by orthogonality, and its two nodal values vanish because the nodes are roots of ${\varphi }_2$. The remaining $r_1$ is integrated exactly by the two equations above. This proves Gaussian quadrature exactness through degree three.

Let $p(x)={\prod }_{i=0}^n(x-x_i)$ be the monic node polynomial. Suppose first that the quadrature is exact through degree $2n+1$. For any polynomial $r$ of degree at most $n$, $pr$ has degree at most $2n+1$, while every sampled value is zero. Exactness givesThus $p$ is an orthogonal polynomial of degree $n+1$, proving necessity in the orthogonal-node criterion for Gaussian quadrature.

Conversely, suppose the nodes are the zeros of such a polynomial. Rescale it to be monic without changing its zeros or orthogonality. For any $f$ of degree at most $2n+1$, polynomial division givesOrthogonality makes $\int pq=0$; the quadrature of $pq$ is zero because $p(x_i)=0$. The assumed degree-$n$ exactness applies to $r$, soHence degree-$2n+1$ exactness is equivalent to orthogonal nodes. The given distinct-zero property ensures the $n+1$ node values are independent interpolation data; the degree-$n$ exactness fixes the corresponding interpolatory weights. This is the construction of Gaussian quadrature.

Use the weighted inner product $⟨u,v⟩={\int }_0^{1}u(x)v(x)xdx$. A monic quadratic orthogonal polynomial ${\pi }_2(x)=x^2+ax+b$, orthogonal to 1 and $x$, satisfiesThus $a=-6/5$, $b=3/10$, and its two zeros are $x_{-}=(6-\sqrt{6})/10$ and $x_{+}=(6+\sqrt{6})/10$. Matching the first two weighted moments givesso $w_{-}=(9-\sqrt{6})/36$ and $w_{+}=(9+\sqrt{6})/36$. The two-node Gaussian quadrature with linear weight is thereforeFor completeness, a polynomial $P$ of degree at most three can be divided as $P=q{\pi }_2+r$, where both $q$ and $r$ have degree at most one. Orthogonality makes the weighted integral of $q{\pi }_2$ zero, and this term vanishes at both nodes. The two moment equations integrate $r$ exactly. Thus the Gaussian quadrature is exact for every cubic polynomial. No two-node rule can integrate every quartic: the square of its nodal polynomial has quadrature value zero and strictly positive weighted integral.

An $n$-node Gaussian quadrature formula chooses nodes and weights for an integral with a positive weight so that every polynomial of degree at most $2n-1$ is integrated exactly. Its nodes are the zeros of the degree-$n$ orthogonal polynomial for that weight.

For the even weight $w(x)=1-x^2$, the monic orthogonal quadratic has the form $p_2(x)=x^2-d$. Orthogonality to $x$ follows from oddness; orthogonality to one givesThe nodes are $\pm 1/\sqrt{5}$. The equal weights sum to $4/3$, hence each is $2/3$. The two-node Gaussian quadrature with quadratic weight is thereforeTo verify cubic exactness, divide any cubic as $P=p_{2}Q+R$ with $\mathrm{deg}Q,\mathrm{deg}R\le 1$. Orthogonality removes $p_{2}Q$ from the integral and its nodal values vanish; linear interpolation integrates $R$ exactly. This also proves the Gaussian property rather than merely matching two moments.

Put $P(t)={\prod }_i(t-x_i)$. For every polynomial $q$ of degree at most $n-1$, $Pq$ has degree at most $2n-1$ and vanishes at all nodes; thus ${\int }_{-1}^{1}Pq=0$. The monic degree-$n$ orthogonal polynomial for this integral is unique: the difference of two such monic polynomials has degree below $n$ and is orthogonal to itself, hence is zero. Consequently $P$ is the monic normalization of the degree-$n$ Legendre polynomial, proving the given nodes are exactly its roots. Together the three results characterize this Gaussian quadrature rule.

For node $x_i$, let ${\ell }_i$ be the Lagrange interpolation polynomial with ${\ell }_i(x_j)={\delta }_{ij}$. It has degree $n$, so ${\ell }_i^2$ has degree $2n$. The Gaussian quadrature with $n+1$ nodes is exact through degree $2n+1$, henceThe integrand is nonnegative. Since ${\ell }_i$ is a nonzero polynomial, it is nonzero on some open subinterval; the positive weight has positive integral there. Consequently $\boxed{a_i>0}$ for every node. This proves the positive weights of Gaussian quadrature property without assuming any coefficient sign beforehand.

Use the Gauss collocation coefficient construction. Find the $\nu$ polynomial roots $c_1,\dots ,c_{\nu }$ of the shifted Legendre polynomial $P_{\nu }(2c-1)$ in $(0,1)$, and formThen setThese are explicit polynomial integrals. For example, if ${\ell }_j(s)={\sum }_{r=0}^{\nu -1}{d}_{jr}{s}^r$, calculate $a_{ij}={\sum }_r{d}_{jr}{c}_i^{r+1}/(r+1)$ and $b_j={\sum }_r{d}_{jr}/(r+1)$. The resulting implicit Gauss collocation method has order $2\nu$; its Gaussian quadrature nodes integrate polynomials through degree $2\nu -1$ exactly. The one-stage example is the implicit midpoint rule, with $c_1=a_{11}=1/2$ and $b_1=1$. No search over nonlinear Runge-Kutta order conditions systems is needed.

With $x=\cos \theta$, the weighted inner product for the Chebyshev polynomials becomesThe identity $2\cos (n\theta )\cos (m\theta )=\cos ((n-m)\theta )+\cos ((n+m)\theta )$ and the vanishing of ${\int }_0^{\pi }\cos (k\theta )d\theta$ for positive integers $k$ give zero when $n\ne m$, $\pi /2$ when $n=m>0$, and $\pi$ when $n=m=0$. ThusFor Gaussian quadrature, choose the $n$ distinct nodes as the zeros of the degree-$n$ orthogonal polynomial for the weight, here $T_n$, and choose the weights as the weighted integrals of their Lagrange interpolation basis functions. If a polynomial $p$ has degree at most $2n-1$, divide it as $p=q{T}_n+r$, where both $q$ and $r$ have degree at most $n-1$. Orthogonality makes the integral of $q{T}_n$ zero, while its quadrature sum also vanishes; interpolation integrates $r$ exactly. This proves degree $2n-1$ exactness. It is optimal because the squared nodal polynomial, of degree $2n$, has zero quadrature sum and strictly positive integral.

For $n=3$, $T_3(x)=4x^3-3x$, so the nodes are $-\sqrt{3}/2,0,\sqrt{3}/2$. Their interpolation basis functions areThe weighted zeroth and second moments are $\pi$ and $\pi /2$, and the first moment is zero. Integrating these three basis functions gives equal weights $\pi /3$, hence the Chebyshev–Gauss quadrature rulewhich is exact for every polynomial of degree at most $5$.

For distinct Gaussian quadrature nodes, let ${\ell }_i$ be the Lagrange interpolation polynomial with ${\ell }_i(x_j)={\delta }_{ij}$. Since ${\ell }_i^2$ has degree $2n-2$, exactness givesThe last inequality follows from $w>0$ on the interval and the nonzero polynomial ${\ell }_i$ being nonzero on a subinterval. It does not require prior knowledge of the signs of the weights.

For $n=2$, the nodes are the roots of the supplied orthogonal polynomial $p_2$:Indeed exactness for $1$ gives $b_1+b_2={\int }_{-1}^1(1+x^2)dx=8/3$, and exactness for $x$ gives equality of the weights.

Use Gaussian quadrature: choose the $n$ nodes as the roots of the degree-$n$ Legendre polynomial, which are distinct and inside $(-1,1)$. Retain the integrated Lagrange interpolation weights. With the standard normalization $P_n(1)=1$, they can be writtenThe orthogonality of the Legendre polynomial against all lower-degree polynomials makes this quadrature exact up to degree $2n-1$, twice the arbitrary-node degree apart from the endpoint count. This is the Gauss–Legendre choice of Gaussian quadrature nodes and weights.

For two-node Gaussian quadrature with linear weight, the monic node polynomial $q(x)=x^2-sx+p$ must be orthogonal to $1$ and $x$ for weight $x$. Indeed, exactness through degree three makes the quadrature of $q$ and $xq$ vanish at its nodes. The moment equations areso $s=6/5$ and $p=3/10$. Thus the Gaussian quadrature nodes, labelled in increasing order, areIntegrating the linear Lagrange interpolation cardinal functions gives the weightsThey are positive, sum to $1/2$, and reproduce the first moment $1/3$. Any cubic polynomial has remainder of degree at most one after division by $q$; orthogonality annihilates the other part both in the integral and at the nodes. This proves degree-three exactness, not merely the two moment conditions for the weights.

For any distinct nodes, the polynomial $q(x)={\prod }_{j=1}^{\nu }(x-c_j{)}^2$ has degree $2\nu$, is nonnegative, and vanishes at every node. The quadrature rule sum for $q$ is zero, but ${\int }_0^{\pi }wqdx>0$ because the weight is positive and $q$ is positive except at finitely many points. Therefore no such rule is exact for all polynomials of degree at most $2\nu$, irrespective of the chosen weights.

For the sine weight, its first four moments are $2,\pi ,{\pi }^2-4,{\pi }^3-6\pi$. A monic degree-two orthogonal polynomial issince direct use of these moments gives $\int p_2\sin xdx=\int x{p}_2\sin xdx=0$. Its roots lie in $(0,\pi )$ and areThe weights follow by requiring exactness for $1$ and $x$: $b_1+b_2=2$ and $b_1{c}_1+b_2{c}_2=\pi$, and the symmetric nodes imply both weights are one. To prove cubic exactness, divide any cubic as $f=a{p}_2+r$, with $a,r$ of degree at most one. The integral of $a{p}_2$ is zero by orthogonality, and its nodal values vanish; the remaining linear polynomial is integrated exactly. This is the two-node Gaussian quadrature with sine weight; the argument proves its Gaussian quadrature property without assuming a general quadrature theorem.

Apply the Gaussian quadrature rule to the constant polynomial $1$. Exactness gives ${\sum }_{j=1}^n{A}_j=2$.