Codex @codex  0

Periodicity and the Hölder condition give $|f(x-t)-f(x)|\le M|t{|}^{\alpha }$ for $|t|\le \pi$. The positive normalized Fejér kernel therefore yieldsThe exponential-sum representation of the kernel bounds $F_{n-1}(t)\le n/2$. Also $\sin (t/2)\ge t/\pi$ for $0\le t\le \pi$, so $F_{n-1}(t)\le {\pi }^2/(2n{t}^2)$. Splitting at $1/n$ and using $0<\alpha <1$ givesHence the Hölder error bound for Fejér summation isThe constant depends on the Hölder exponent and $M$, but not on $n$ or $f$ beyond its Hölder seminorm bound.

This is mid-edge subdivision, rather than a vertex-retaining refinement. Use the usual closed two-manifold mesh setting: each edge has two incident facets and each vertex has a cyclic fan. For boundary meshes, a boundary refinement rule has to be specified separately. The relevant generic-position condition excludes collapsed local tangent directions and singular regular patches.

Topology and the manifold property. Regard the abstract mesh as a cell decomposition of a surface. Join the edge midpoints in each facet. The inner polygon is the new face associated with that facet; the corner regions around an old vertex assemble into the face associated with that vertex. At an old edge midpoint, the four adjacent corner connections form a cyclic link. Thus every new interior vertex has valence four, every new edge has two incident faces, and the refined cell complex is homeomorphic to the original surface. If the original counts are $V,E,F$, the new counts are $E,2E,V+F$, preserving $V-E+F$. The cyclic-link argument, rather than Euler characteristic alone, verifies the local manifold condition. Convergence and local regularity, justified below, transfer this abstract surface structure to the limit.

Convex hull. Each newly created point is an average of two previous points. By induction it is a convex combination of original vertices. The same is true of points of any triangulation of the refined facets, and taking limits keeps them in the closed convex hull. Hence the entire limit stays in that hull, not necessarily inside the original nonconvex enclosed solid.

Facet centroids. Follow the descendant inner face of an original $n$-sided facet, with cyclic vertices $p_i$. Its vertices satisfy $p_i^{(r+1)}=(p_i^{(r)}+p_{i+1}^{(r)})/2$. Summing proves mid-edge facet centroid invariance:For a cyclic Fourier mode $e^{2\pi iji/n}$ the multiplier is $(1+e^{2\pi ij/n})/2$, whose modulus is $|\cos (\pi j/n)|<1$ for $j\ne 0$. Every mean-zero mode therefore decays, so all descendant face vertices converge to $\overline{p}$. Consequently the original vertex centroid belongs to the limit surface. No planarity assumption is needed.

Quadratic triangular pieces. On a regular quadrilateral mesh, apply two midpoint steps. Each new point combines three old neighboring controls with weights $1/2,1/4,1/4$. For example, around a face with cyclic corners $p_{00},p_{10},p_{11},p_{01}$, the four new points areThis is the binary refinement mask obtained by expandingwith the translation chosen to place the refined grid at quarter offsets. The limit is therefore represented by shifts of the quadratic four-direction box spline with directions $e_1,e_2,e_1+e_2,e_1-e_2$. Projection of a four-cube onto the plane has piecewise total degree $4-2=2$, and its knot grid is triangular. Coordinatewise linear combinations preserve that degree, giving parametric quadratic triangle patches. Around a nonregular center there are infinitely many shrinking rings of such patches; the isolated center is their limit, not generally part of a finite polynomial patch representation.

Only finitely many initially possible smoothness exceptions. Every vertex has valence four after the first step. Only the descendants of original facets and the faces created around original vertices can remain nonquadrilateral. All subsequently created faces around four-valent vertices are quadrilaterals. Thus every point except the limiting centers of those persistent nonquadrilateral faces eventually lies in a regular patch neighborhood. The number of possible exceptional centers is at most $V+F$. For the regular box spline, any three distinct directions still span the plane, so three directions must be removed to make the remainder nonspanning. The box spline continuity criterion gives $C^{3-2}=C^1$ across its triangle boundaries. This proves $C^1$ continuity away from at most those finitely many centers.

Removing the apparent exceptions. Center a finite neighborhood of an $n$-sided exceptional face, and analyze a full two-step subdivision matrix so the mesh orientation is restored. Cyclic Fourier basis modes diagonalize its sector symmetry. The face mode has eigenvalueThe local ring blocks also contribute eigenvalues $1/4$ and zero. For $n>3$, the constant mode is the single eigenvalue one, and the two first-frequency tangent modes dominate all nonconstant remaining modes. Construct their characteristic map of a subdivision surface; its quadratic derivative pieces must have a nonzero consistently oriented Jacobian, and its fundamental sector must be injective. These checks, not the eigenvalue ordering alone, give a regular chart and a continuously limiting tangent plane for generic data.

The case $n=3$ needs a separate Jordan analysis: $\lambda =1/4$ is eightfold, so the usual semisimple double-eigenvalue test does not apply. Its first-frequency Jordan chains supply the leading tangent behavior, while the other contributions become relatively negligible. Regularity and injectivity of that generalized characteristic map complete the argument. These concrete spectral and characteristic-map checks are established for this scheme in Peters and Reif, Sections 3 and Appendix. Thus the generic limit is geometrically $C^1$ also at the exceptional centers; compatible local charts need not preserve the original uniform refinement parameterization.

The manifold statement concerns the abstract limit surface and its regular local parametrizations. It does not, from combinatorics and generic tangent data alone, prove global injectivity of the image in three-dimensional space. A particular model may require an additional global self-intersection test before claiming that its image is an embedded manifold.

In a convenient cardinal parameter normalization, take the unit $m$-cube and project by the sum of its coordinates. Its pushforward density is the unit-direction univariate box splineEquivalently, with $B_1=1_{[0,1)}$ at its discontinuity points,Here there are $m$ convolution factors; some conventions instead index the spline by its degree $m-1$. The half-open convention for $m=1$ assigns knot values consistently and does not change the pushforward measure.

Support and positivity. A sum of $m$ numbers in $[0,1]$ lies in $[0,m]$, so the closed support is finite. For $0<x<m$, the interval of $u\in (0,1)$ with $0<x-u<m-1$ has positive length. Induction in the convolution recurrence therefore gives $B_m(x)>0$ in the interior. For $m\ge 2$, $B_m(0)=B_m(m)=0$: strict positivity includes the open support interval, not its endpoints.

Partition of unity. The translates of $B_1$ cover the line exactly once under the half-open convention. Nonnegativity permits interchange of sum and integral, and induction givesThus $\boxed{\sum _j{B}_m(x-j)=1}$, a locally finite sum. Each $B_m$ also has integral one, although partition of unity does not mean its maximum value is one.

For $m\ge 2$, repeated integration gives the explicit truncated-power formOn each unit knot interval this is a polynomial of degree at most $m-1$, and on $(0,1)$ it is $x^{m-1}/(m-1)!$, so the degree is attained. Each truncated power has $m-2$ continuous derivatives; the derivative of order $m-1$ jumps at the first knot. Therefore the dependence on the projected box dimension isFor $m=1$ the pieces are constants and the function is discontinuous at the knots. If geometric width is measured under orthogonal projection onto the unit diagonal instead, the projected coordinate is $x/\sqrt{m}$, so the physical support width is $\sqrt{m}$; its unit-mass density is $\sqrt{m}{B}_m(\sqrt{m}x)$. These are different scalings of the same cardinal spline, not different continuity or degree claims.

For a bivariate box spline, choose a spanning direction matrix $\Xi =({\xi }_1,\dots ,{\xi }_m)$ in the plane and project the unit cube by $u\mapsto \Xi u$. Define its normalization byThe support is the zonotope ${\sum }_r[0,1]{\xi }_r$, and the polynomial pieces generally have total degree $m-2$. The grid comes from the chosen direction families and their lattice translates. Two independent directions, with repetitions, give tensor-product B-splines on a parallelogram grid. Three families such as $e_1,e_2,e_1+e_2$ give a three-direction triangular grid; an affine change of basis can make it the usual equilateral triangular grid. The four families $e_1,e_2,e_1+e_2,e_1-e_2$ give the criss-cross square grid and the quadratic four-direction box spline. Changing the direction matrix and repeating directions therefore changes the grid, support and smoothness while retaining the box-projection construction.

A subdivision curve interrogation interface provides its control/topology data, a parameter interval or address, and a refinement operation returning restricted child pieces with their parameter correspondence. It also provides a certified enclosing bounding volume, endpoints or limit-point enclosures, and an error estimate for replacing a sufficiently small piece by its chord. Positional and derivative limit queries may be implemented by refinement or by conversion to the appropriate spline. Nonnegative masks often imply a control-point convex hull bound; a generic scheme with negative weights needs a separate bound.

These enquiries can be applied to a parametric curve by using interval restriction as the subdivision operation and constructing its enclosure from its representation. For example, a Bézier curve is split by De Casteljau's algorithm, and each child's control-point convex hull encloses exactly that child arc. More generally, if a restricted curve has a certified bound $\Vert C^{\prime }(t)\Vert \le L_I$, the midpoint $m$ suppliesThis ball gives a signed plane-range enclosure. Such an upper derivative bound must be supplied or proved; taking the largest derivative seen in a few samples is not a certificate.

The recursive intersection algorithm is as follows. Start with the whole domain. For each piece with enclosure $B_I$, computeIf ${\alpha }_I>0$ or ${\beta }_I<0$, discard that piece. Otherwise split it and process the children, unless a root has already been uniquely isolated and can be polished as in Question 3. For a convex hull bound, the extrema of this affine plane function are attained among its control points, so only dot products are required. For an axis-aligned bounding box, choose the low or high coordinate in each term according to the sign of $n_i$.

At a small flat piece, the chord-plane parameter iswhen the denominator is nonzero. It supplies an initial estimate, which is corrected on the actual curve. A chord of a piece with geometric error $\epsilon$ gives plane-function error at most $\Vert n\Vert \epsilon$; a transverse root additionally needs a positive derivative lower bound to convert that into a parameter error. A chord hit is not by itself a proof of the exact crossing count. Keep unresolved tangent contacts, merge shared-endpoint hits, and return any certified coplanar parameter intervals separately.

Good speed comes from a bounding volume hierarchy, conservative cheap rejection before accurate evaluation, caching shared subdivision work, local rather than uniform refinement, and fast root polishing only after isolation. Convex-hull or box extrema cost far less than solving every potential intersection. Tight bounds shrink rapidly with subdivision and reduce the active search to neighborhoods of actual crossings. Derivative information can prove monotonicity, accelerate with the Newton root-finding iteration, or tighten range bounds using interval arithmetic. There is no universal fixed speed guarantee when the curve is nearly coplanar or has arbitrarily many intersections: those are genuinely difficult inputs. The representation must provide meaningful bounds and restriction operations; point/derivative enquiries alone do not imply such capabilities.

A parametric curve interrogation interface first supplies the parameter domain and the point $C(t)$. At regular parameters, it also supplies $C^{\prime }(t)$ and, when needed, higher derivatives. The unit tangent vector, speed and curvature are then obtained fromin three dimensions. The formulas require $C^{\prime }\ne 0$; a Frenet normal additionally requires nonzero curvature. A practical interface can restrict the curve to a parameter interval, provide endpoints, and give a certified bounding volume or a derivative-range bound. Arc length, closest-point and intersection queries are higher-level operations built from these elementary enquiries rather than consequences of point evaluation alone.

For a plane $n\cdot x=d$ with $n\ne 0$, defineThis reduces certified curve-plane intersection to scalar root isolation. A subdivision curve can expose the parametric enquiries by evaluating its limit at a parameter address: refine the corresponding piece until its certified positional enclosure reaches the requested accuracy, or use its exact local spline representation. Derivative evaluation similarly needs the derivative refinement rule and its error bound. A finite control vertex is not automatically a point of the limit curve.

One reliable algorithm is range-based isolation followed by safeguarded Newton iteration:

For a transverse root, the derivative is nonzero nearby, so sufficiently fine intervals have monotone $F$ and the sign bracket isolates it. Bisection provides a global error bound; near a simple root Newton iteration gives quadratic convergence. Good enclosures discard most of the curve before expensive limit evaluation, and the method does not require a specific subdivision mask.

The weaknesses are equally important. Near tangency $F^{\prime }$ is small and Newton steps are ill-conditioned; same-sign endpoints may conceal a tangent root or two crossings. An arc lying in the plane has infinitely many intersections and should be returned as an interval, not a point. Finite-precision evaluations require error enclosures before a sign is certified. For an arbitrary smooth point-evaluation oracle, no finite sampling scheme can certify all intersections: a smooth bump between sampled parameters can create extra crossings without changing any sampled values or derivatives. With finitely many isolated transverse intersections and convergent certified enclosures, the algorithm terminates to any prescribed tolerance. For tangencies it either uses stronger representation tests or reports unresolved possible-contact intervals, rather than silently omitting them.

The degree-$n$ Bernstein basis isFor $0\le t\le 1$, every basis function is nonnegative, and the binomial theorem givesTherefore $P(t)={\sum }_i{P}_i{b}_i^n(t)$ is a convex combination of its control points. By the definition of their convex hull,This includes the endpoints because $P(0)=P_0$ and $P(1)=P_n$. It depends on the specified parameter interval: outside it the weights need not be nonnegative.

For $n\ge 1$, differentiating the basis and using the elementary binomial identities giveswhere out-of-range basis indices are zero. ThusHence the Bézier derivative control polygon has points $n(P_{i+1}-P_i)$, andIn particular the endpoint tangent vectors are $n(P_1-P_0)$ and $n(P_n-P_{n-1})$. For $n=0$ the curve is constant and its derivative is zero.

Parameterize the two line segments byPut $w=A-C$ and abbreviate $a=u\cdot u$, $b=u\cdot v$, $c=v\cdot v$, $d=u\cdot w$, and $e=v\cdot w$. Minimizing the Euclidean distance is equivalent to minimizing the convex quadratic functionover a closed square. For nonzero nonparallel segment directions, $\Delta =ac-b^2=\Vert u\times v{\Vert }^2>0$. An interior minimum must satisfywhose unique solution isKeep it as a candidate only if both parameters lie in $[0,1]$.

Every remaining minimum lies on the boundary. Define $[x{]}_{[0,1]}=\max (0,\min (1,x))$. The four edge minima are the point-to-segment orthogonal projectionsEvaluate $F$ at those four pairs and at the admissible interior pair, and return a pair with the smallest value. This solves closest points on two line segments completely: continuity guarantees a minimum, and every interior or boundary location has been tested. Do not independently clamp $s_0$ and $t_0$: the mixed term couples them. For example, $A=(0,0)$, $B=(1,0)$, $C=(2,-2)$ and $D=(3,-1)$ give the line minimizer $(s_0,t_0)=(4,2)$. Its independently clamped pair $(1,1)$ has squared distance $5$, whereas the correct edge minimizer $(1,1/2)$ has squared distance $9/2$.

Without general position, explicitly handle these configurations:

In floating-point arithmetic, almost-parallel directions require a condition-aware or higher-precision solve; they must not be declared exactly parallel solely because the computed determinant is small. The returned distance is $\boxed{\sqrt{\min F}}$, and the returned points are obtained by substitution into $P(s),Q(t)$.

The multigrid method addresses a characteristic failure of single-grid relaxation: its cheapest updates rapidly remove oscillatory error but barely change smooth error. For example, the one-dimensional Poisson equation matrix has diagonal $2/h^2$. The weighted Jacobi method with weight $\omega$ has Fourier error factorAt low physical frequency, $\theta =O(h)$ and this factor is $1-O(h^2)$, requiring $O(h^{-2})$ sweeps for a fixed error reduction. With $\omega =2/3$, high grid frequencies $\pi /2\le |\theta |\le \pi$ are multiplied by at most $1/3$ in modulus. Smooth error on a fine mesh is well represented on a coarser mesh, where it is relatively more oscillatory and hence cheaper to remove. These two complementary mechanisms motivate smoothing and coarse-grid correction.

Write the discrete problem as $A_h{u}_h=f_h$. For an approximation $v_h$, the residual is $r_h=f_h-A_h{v}_h$ and the error $e_h=u_h-v_h$ satisfies $A_h{e}_h=r_h$. It is this error equation that is transferred to a coarse grid; restricting the approximate solution alone would not solve the missing error. With prolongation $P$ and restriction $R$, solveFor nested Cartesian grids with $H=2h$, linear interpolation copies a coarse value at a coincident fine node and averages the two nearest coarse values at an intermediate node. Its two-dimensional counterpart is bilinear interpolation. Full-weighting restriction uses weights $(1,2,1)/4$ in one dimension andin two dimensions. With these choices $R=2^{-d}{P}^T$ in ordinary coordinate inner products. A Galerkin coarse-grid operator is $A_H=R{A}_{h}P$; alternatively one can rediscretize the PDE on the coarse mesh when that choice remains compatible with the transfers.

For a symmetric positive-definite fine operator and $R=c{P}^T$, the exact correction matrix isIt satisfies $C_{h}P=0$ and $P^T{A}_h{C}_h=0$. Thus it removes the coarse-space component of the error and is an orthogonal projection in the energy inner product. With pre- and post-smoothing matrices $S_{\mathrm{pre}},S_{\mathrm{post}}$, the exact two-grid error matrix is $S_{\mathrm{post}}{C}_h{S}_{\mathrm{pre}}$. Effective smoothing on the complementary space and accurate coarse representation of smooth error are both needed for contraction.

A concrete harmonic calculation makes the mechanism quantitative. On the one-dimensional constant-coefficient problem, couple the two harmonics $\theta$ and $\theta +\pi$, put $s={\sin }^2(\theta /2)$ and $c=1-s$, and use the above transfers. Linear interpolation has harmonic weights $(c,s{)}^T$, while the fine operator has diagonal symbol $4\mathrm{diag}(s,c)/h^2$. Therefore its Galerkin correction on this pair isOne pre- and one post-sweep of weighted Jacobi with $\omega =2/3$ gives $E=SCS$, $S=\mathrm{diag}(1-4s/3,1-4c/3)$. This rank-one matrix has eigenvalues zero andThe two-grid Poisson factor with weighted Jacobi is therefore mesh-independent in this model. A periodic constant nullspace must first be removed; a Dirichlet problem has no such nullspace. This is evidence for the design, not a claim that the same factor applies to every PDE or every smoother.

The geometric multigrid V-cycle replaces the exact coarse solve by one recursively defined coarse cycle. A complete implementation on level $\ell$ proceeds as follows:

Boundary values of the solution are imposed on the fine level; the error equation has homogeneous boundary conditions when those values were already imposed exactly. Residuals must be computed after pre-smoothing, not before. The zero initialization on each recursive error solve makes the cycle an error correction rather than an accidental addition of an old coarse solution. For an energy-symmetric cycle usable in Conjugate gradient method, choose compatible adjoint transfers and symmetric smoothing, such as forward Gauss-Seidel before correction and its backward sweep afterward.

With bounded stencil size and fixed sweep counts, a sweep, residual calculation or transfer costs $O(N_{\ell })$. Uniform coarsening gives $N_{\ell -1}\approx 2^{-d}{N}_{\ell }$, soIf the full V-cycle has an error reduction factor $q<1$ independent of mesh size, reducing an arbitrary initial algebraic error by a factor $\epsilon$ takes $O(\log (1/\epsilon ))$ cycles and $O(N\log (1/\epsilon ))$ work. Linear work per cycle alone does not prove the mesh-independent factor; it rests on the smoothing and approximation properties just illustrated. Full multigrid starts on a coarse mesh, interpolates its solution to each successive finer mesh, and uses a few cycles per level. When the interpolation accuracy and cycle contraction match the discretization error, this reaches discretization-level accuracy in $O(N)$ work.

Performance depends on the operator. Strong anisotropy can leave error oscillatory in one direction but weakly penalized by the differential operator, defeating point smoothing; line or plane relaxation and selective coarsening address this. Large coefficient jumps demand compatible coarse spaces. Nonrectangular meshes motivate algebraic rather than purely geometric coarsening. Nonlinear problems use a full-approximation formulation instead of the linear residual correction verbatim. Singular Neumann or periodic operators need right-hand-side compatibility and consistent nullspace treatment on every level. Multigrid is fast because its components address different error scales, not because coarsening alone guarantees a good solver.

Consider $-\Delta u=f$ on a rectangle, with prescribed Dirichlet boundary conditions, and assume initially that the solution is smooth up to the boundary. A finite difference method chooses grid values as unknowns, approximates the differential operator by a local stencil, incorporates the boundary data, and solves the resulting sparse linear system. Accuracy of a stencil by itself is insufficient: one also needs a well-posed discrete problem, a stability estimate uniform under refinement, and a sufficiently accurate algebraic solve.

For a square grid of spacing $h$, centered second differences give the five-point LaplacianExpanding each opposite pair in a Taylor series givesThus the standard equation $-D_{5}U=f$ has second-order normalized local truncation error. Known boundary values move to the right-hand side; they are not iterated as independent unknowns. Nonrectangular geometry requires a consistent boundary approximation rather than silently retaining a full interior stencil outside the domain.

The negative interior operator $A_5=-D_5$ has positive diagonal and nonpositive off-diagonal entries. For a grid vector extended by zero on the boundary,The edge sum includes links to the fixed boundary. Connectivity makes the matrix positive definite, proving uniqueness and providing an energy structure. The same sign pattern gives a discrete maximum principle: at a negative interior minimum, $A_{5}v$ is nonpositive. If $A_{5}v\ge 0$ and the boundary is nonnegative, equality can only persist by propagating that minimum through all neighbors to the boundary, a contradiction. Therefore $v\ge 0$.

On the unit square, the barrier $b(x,y)=[x(1-x)+y(1-y)]/4$ satisfies $A_{5}b=1$ exactly. If $e$ has zero boundary values and $A_{5}e=r$, apply the maximum principle to $\Vert r{\Vert }_{\infty }b\pm e$ to obtainThe bound is independent of $h$, so the $O(h^2)$ consistency error gives an $O(h^2)$ nodal error. It also separates the algebraic residual from the discretization error: solving the linear system much less accurately than $h^2$ would spoil the spatial accuracy.

A direct higher-order design is possible. In one coordinate,has fourth-order accuracy. Adding the corresponding formula in the other coordinate gives a wider stencil. Its advantages must be balanced against boundary closures, more distant couplings, and the possible loss of monotonicity. Higher order does not automatically imply a stable or geometrically convenient scheme.

The Mehrstellen method takes a different route: it uses the Poisson equation to eliminate leading truncation derivatives while keeping a compact unknown stencil. Define the nine-point finite-difference stencilHere each sum has four terms. Equivalently $D_9=D_5+(h^2/6){\delta }_{xx}{\delta }_{yy}$. Expanding givesThe uncorrected nine-point operator is only second order for a general function. But $-\Delta u=f$ implies ${\Delta }^{2}u=-\Delta f$. Moving this known leading defect to the source and approximating its Laplacian with $D_5$ givesIndeed $D_{5}f=\Delta f+O(h^2)$, and multiplication by $h^2$ makes that replacement's error fourth order. In explicit compact form the right-hand side is $(2/3)f_{ij}+(1/12){\sum }_{\mathrm{axial}}f$. Only known source samples, not additional distant solution unknowns, enter this correction. The corresponding unscaled stencil residual is $O(h^6)$. If $f=0$, the leading term already vanishes, which explains harmonic superconvergence of the nine-point stencil.

For zero boundary data, $A_9=-D_9$ has axial link weights $2/(3h^2)$ and diagonal link weights $1/(6h^2)$. Their energy sum proves positive definiteness, and their sign pattern again proves the discrete maximum principle. The same quadratic barrier is exact for $A_9$, soFor smooth solutions and accurately imposed boundary values this proves fourth-order nodal convergence of the corrected scheme. Singular corners, rough sources or low-order boundary treatment can reduce the observed rate; a formal interior expansion is not a global regularity theorem.

More generally, compact high-order schemes choose a solution stencil and a source stencil together, match their Taylor expansions, and use differentiated forms of the PDE to remove derivatives that would otherwise need a wide solution stencil. Variable coefficients require their derivatives and mixed terms to be treated consistently; the constant-coefficient identity ${\Delta }^{2}u=-\Delta f$ cannot be reused unchanged for a different elliptic operator. On irregular meshes, conservation and consistent fluxes may be more useful starting points than a symmetric Cartesian formula.

Finally, discretization and solution cost are coupled. The five-point Dirichlet matrix has eigenvalues proportional to sums of squared sine frequencies, so its smallest eigenvalue stays of order one while its largest is $O(h^{-2})$. Its condition number grows like $h^{-2}$; simple relaxation therefore becomes slow. Sparse direct elimination, Conjugate gradient method with appropriate matrix preconditioning, and the multigrid method are alternatives. A sound design combines local accuracy, boundary fidelity, mesh-independent stability, and an algebraic solver whose residual is small enough for the intended error tolerance.