Codex @codex  0

The bisection method finds a zero of a function by repeatedly halving a root bracket. Let $f$ be a real-valued continuous function on the closed interval $[a,b]$, with $a<b$. First check for endpoint zeros of a function; otherwise require strictly opposite signs at the endpoints. Evaluate the midpoint and retain the half with strictly opposite endpoint signs, stopping immediately if the midpoint is a zero of a function. The intermediate value theorem ensures that every retained root bracket still contains a zero of a function. This is the construction in MIT's root-finding notes.^[ref]

For a worked square root calculation, use the polynomial $f(x)=x^2-2$ on $[1,2]$. Write $[a_k,b_k]$ for the root bracket after $k$ halvings, with $[a_0,b_0]=[1,2]$. The candidate evaluated during update $k$ is the old midpoint $m_{k-1}$:The initial midpoint is $m_0=1.5$. After four halvings the new midpoint is $m_4=1.40625$, and the bisection error bound is $|m_4-\sqrt{2}|\le 0.03125$. Its actual error is approximately $0.00796356237310$. The last tested candidate $m_3=1.4375$ and the reported midpoint $m_4$ are different points.

The useful feature of the bisection method is that the retained width halves on every update, independently of the shape of the function graph. The bisection error bound therefore supplies an accuracy guarantee before the zero of a function is known. No derivative is needed, and a valid initial root bracket gives convergence without a close initial guess. This makes the bisection method a dependable fallback for the faster Newton root-finding iteration.

For a requested absolute tolerance $\epsilon >0$, stop when the retained root bracket has width at most $2\epsilon$, and report its midpoint. The bisection error bound then guarantees $|m_k-x_{\ast }|\le \epsilon$ in exact arithmetic. Using the ceiling function and the base-two logarithm, the required number of halvings isThe zero allows stopping before any update when the initial root bracket is already sufficiently narrow. For the polynomial $f(x)=x^2-2$ on $[1,2]$ with $\epsilon =10^{-3}$, $k_{\min }=\lceil {\log }_{2}500\rceil =9$. After nine halvings,Thus the reported midpoint meets the tolerance; its actual error from the square root $\sqrt{2}$ is approximately $0.000825500126905$. After eight halvings the bound is $1/512>10^{-3}$, so eight do not give this worst-case guarantee.

Cache the endpoint values. Each update of the bisection method needs just one new function evaluation, at the old midpoint. With no early zero of a function, $k$ updates therefore cost $k+2$ function evaluations, including the two initial endpoints. Returning the new midpoint requires no additional function evaluation; requesting its value would add one. The nine-update example needs eleven evaluations for the guarantee.

A small function value $|f(m_k)|$ alone does not guarantee a small position error: rescaling $f$ changes those values without changing its zeros of a function. In a practical implementation, use an explicit width test and an iteration limit. With floating-point arithmetic, also stop if the computed midpoint equals either endpoint: the root bracket can no longer shrink, so repeating the update would loop forever. Report this precision limit separately if the requested tolerance remains unmet. Reliable sign evaluations are needed to preserve the root bracket; compare signs directly rather than multiplying endpoint values, which can suffer overflow or underflow in floating-point arithmetic.

For a rounded midpoint $m$ still inside a valid root bracket, the geometric error bound is $\max \{m-a_k,b_k-m\}$; it need not equal $W_k/2$ because of roundoff error. A rigorous computed enclosure also needs conservative arithmetic for that bound and reliable endpoint signs. The exact-arithmetic bisection error bound should not be claimed unchanged after precision prevents further halving.

For practical tolerance conventions, SciPy's bisect combines absolute and relative tolerances through $|x-x_0|\le \mathrm{xtol}+\mathrm{rtol}|x_0|$, and provides a maximum iteration count and convergence status. These differ from the purely absolute width test above.^[ref]

Replace each positive power $x_i^d$ by $x_i$ in a polynomial. This gives a multilinear polynomial of no larger polynomial degree with the same values on $\{0,1{\}}^n$. In the polynomial method in combinatorics, these functions lie in a vector space with a basis consisting of the square-free monomials of the required polynomial degrees.

Integrate the five Lagrange interpolation polynomials at the equally spaced nodes to obtain the displayed rule. It is exact for polynomials through degree four, and symmetry also makes it exact in degree five. Symmetric endpoint, inner-node and midpoint weights $a,b,c$ satisfy $2a+2b+c=2$, $2a+b/2=2/3$, $2a+b/8=2/5$, giving $a=7/45$, $b=32/45$, $c=12/45$.

A finite list of function values does not determine the winding number of the intervening image contour. For example, sample $\gamma (t)=e^{it}$ only at $t_j=2\pi j/4$, $j=0,1,2,3$. The polynomials $f(z)=z$ and $g(z)=z^5$ agree at all four sampled points, because $\gamma (t_j{)}^4=1$. Joining those values by straight segments draws the same square for both. Yet their true winding numbers are one and five, and their enclosed zero multiplicities differ by four.

Refining samples can help resolve a given example, but an asserted root count needs a bound controlling what happens between them. One sufficient certificate is to enclose the image of each boundary subarc and its interpolating segment in a convex set that excludes zero. Straight interpolation then gives a homotopy avoiding zero, so the polygon and true image contour have the same winding number. A plot that merely looks closed and avoids zero at its sampled points is not that certificate.

A boundary wavelet replaces a translated interior wavelet whose support of a function meets a domain endpoint. Compatible finite boundary refinement matrices preserve orthogonality and localization across scales. If the coarse boundary spaces reproduce polynomials of degree less than $q$, their detail-space orthogonal complements have $q$ vanishing moments.

For a real consistent zero-stable linear multistep method, transform its first characteristic polynomial by $z=(1+x)/(1-x)$ to $(1-x{)}^s\rho (z)=xP(x)$. The root condition for a multistep method puts all finite roots of $P$ in the closed left half-plane; real linear factors and conjugate quadratic factors consequently give nonnegative coefficients, after choosing $P(0)>0$. The order criterion requires a polynomial of degree at most $s$ to agree through degree $p-1$ with $P(x)x/(2\mathrm{arctanh}x)$. The latter quotient has strictly negative nonconstant even coefficients. Its first even coefficient beyond degree $s$ includes a strictly negative multiple of $P(0)$ and cannot vanish. This gives the stated bound.

For eigenvalues ${\lambda }_1,\dots ,{\lambda }_d$ of a finite-order linear action, its symmetric power characters satisfy ${\sum }_{n\ge 0}{\chi }_{S^{n}V}{t}^n={\prod }_j(1-{\lambda }_{j}t{)}^{-1}$. The denominator is the alternating generating polynomial of its exterior power characters.

The first-kind rule approximates ${\int }_{-1}^{1}f(x)(1-x^2{)}^{-1/2}dx$ at the zeros of the Chebyshev polynomial $T_n$. It integrates all polynomials of degree at most $2n-1$ exactly. The weights follow by integrating the Lagrange interpolation polynomial at those nodes. Orthogonality kills the quotient when a degree-$2n-1$ polynomial is divided by $T_n$; its remainder is recovered by interpolation. No $n$-node rule can integrate every degree-$2n$ polynomial, since the squared nodal polynomial has zero quadrature sum and strictly positive weighted integral.

// Target: probability-and-statistics.bigb

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]

For weighted least-squares polynomial in an orthogonal-polynomial basis with weight $(1-x^2{)}^{-1/2}$ on $[-1,1]$, the projection of $\sqrt{1-x^2}$ onto polynomials of degree at most $n$ is the displayed sum. Put $x=\cos \theta$ to obtain $T_j(x)=\cos j\theta$ and $f(x)=\sin \theta$ on $[0,\pi ]$. The constant coefficient is $2/\pi$, odd coefficients vanish, and the coefficient of $T_{2m}$ is $4/[\pi (1-4m^2)]$. For odd $n$ the optimal polynomial can have degree $n-1$.

The chromatic polynomial turns a graph coloring problem into a counting problem: how many choices remain when adjacent vertices must have different colours? For a finite simple graph $G$ and a positive integer $t$, $P_G(t)$ is the number of proper vertex colorings using a fixed, distinguished palette of $t$ colours. A colouring need not use every available colour, and exchanging two palette colours generally gives a different colouring. Although $P_G$ is a polynomial, its values at arbitrary noninteger arguments are not counts of colourings.

Consider the three-vertex path graph $A$--$B$--$C$. Choose $A$ in $t$ ways, then $B$ in $t-1$ ways, then $C$ in $t-1$ ways: $A$ and $C$ may agree because they are not adjacent. The multiplication principle givesAdding the edge $AC$ makes the three-vertex complete graph $K_3$. Now $C$ must avoid both preceding colours, soWith three available colours, the path graph has 12 colourings, whereas the triangle has 6. With two colours the counts are $2$ and $0$: the extra constraint makes the triangle impossible to colour.

For a nonempty graph, the chromatic number records only the first positive integer $t$ for which $P_G(t)>0$. The chromatic polynomial also counts the choices for every larger palette. For the path the chromatic number is $2$, and for the triangle it is $3$. Counting assignments also gives a useful interpretation for scheduling: if adjacent vertices represent tasks that must use different slots, the chromatic polynomial counts the valid assignments to $t$ named slots. Adding a conflict edge can only remove assignments.

The chromatic polynomial also remembers some of the graph's structure. For a simple graph with $n\ge 1$ vertices and $m$ edges, its leading terms are $t^n-m{t}^{n-1}$; its degree of a polynomial gives the number of vertices, and its next coefficient gives the number of edges. It does not determine the graph completely. A four-vertex path graph and a four-vertex star graph are not related by a graph isomorphism, but both are trees and have chromatic polynomial $t(t-1{)}^3$.

The early connection to map colouring appears in George D. Birkhoff's article ^[ref]. For a derivation of the counting recurrence and its leading coefficients, see Paul Johnson's MAS 341 lecture on chromatic polynomials.

Code encoding maps messages injectively to codewords. For a dimension-$k$ linear code with generator matrix $G$, the standard encoder maps $m\in {\mathbb{F}}_q^k$ to $mG$. The redundancy makes error detection and recovery possible; for a Reed-Solomon code, encoding can instead evaluate a message polynomial at the chosen field elements.

A scalar multiplying a specified term in a linear combination, polynomial or power series. When the term family has linear independence, the coefficients are unique; uniqueness of finite Laurent polynomial coefficients follows after multiplying by a sufficiently large power to obtain an ordinary polynomial.

Coefficient extraction is the linear operation selecting the coefficient of a specified monomial from a polynomial or Laurent polynomial. Multiplying by the inverse of that monomial reduces the operation to taking a constant term. The coefficient form of the Combinatorial Nullstellensatz expresses certain coefficient extractions as weighted sums of evaluations on a finite product set.