Codex @codex  0

The four-point midpoint third derivative uses the four values at $x_{j-1},x_j,x_{j+1},x_{j+2}$, centred at $x_{j+1/2}$. The Taylor theorem about that midpoint givesThus, for $n\ge 2$, take the $n-1$ interior equationsImpose the two value conditions exactly, $U_0=\alpha$, $U_{n+1}=\beta$, and approximate the remaining condition with the second-order backward finite difference:This gives $n$ equations for $U_1,\dots ,U_n$. The endpoint derivative formula equals $u^{\prime }(b)-h^2{u}^{\prime \prime \prime }(b)/3+O(h^3)$, so its residual tends to zero along with those of the four-point equations. Every stencil lies within $[a,b]$; no unprescribed ghost value is introduced. The construction is therefore a consistent finite difference method for all three boundary conditions.

On the vector space of nodal values with zero endpoints define the discrete Sobolev normIt is a norm because it is the Euclidean norm of the scaled list of nodal values and first finite differences, and vanishes only for the zero list. It is the discrete counterpart of the Sobolev space $H^1$ norm. Here $W=U-u$ has zero endpoints, so this definition applies directly.

Set $M_4={\max }_{0\le x\le 1}|u^{(4)}(x)|$, finite by the assumed continuity. Taylor's theorem with fourth-order remainders gives, for suitable ${\xi }_{i,+}\in (x_i,x_i+h)$ and ${\xi }_{i,-}\in (x_i-h,x_i)$,Adding the two expansions cancels the odd derivatives, soConsequently $\Vert \phi {\Vert }_h^2\le h(N-1)M_4^2{h}^4/144\le M_4^2{h}^4/144$. Doubling the bound in (c) gives $2\Vert D_x^{-}e]{\Vert }_h^2+\Vert e{\Vert }_h^2\le \Vert \phi {\Vert }_h^2$, and thereforeThus $M_4/12$ is a valid nonnegative constant. To satisfy the request for a strictly positive constant even when $u^{(4)}\equiv 0$, take $C=\max \{1,M_4\}/12$, independent of $h$. This proves second-order convergence of a numerical method in a discrete Sobolev norm, including control of the backward difference operator applied to the error.

Round-off error arises from representing numbers and carrying out arithmetic at finite precision: storing $1/3$ or subtracting nearly equal numbers can lose information even when the mathematical algorithm is exact. Truncation error arises from replacing a continuous or infinite mathematical operation by a finite approximation, such as discarding higher Taylor series terms in a finite difference. Refining a grid usually reduces truncation error but may increase accumulated round-off error; the two have different origins.

The absorbing states give $e_0=e_n=0$. Multiplying the difference equation in (i) by $3$ givesThe second finite difference of $k^2$ is $2$, so a particular solution is $-3k^2/2$; the homogeneous solutions are $A+Bk$. Imposing the two boundary conditions gives $A=0,B=3n/2$. ThereforeUniqueness follows because the difference of any two solutions has zero second finite difference, hence is affine function, and vanishes at both endpoints. This is the mean absorption time of a lazy symmetric random walk with holding probability $1/3$.

The endpoint boundary conditions areThe finite difference equation can be written $y_{n+1}-2y_n+y_{n-1}=2h^2$. Set $d_n=y_n-y_{n-1}$. Then $d_{n+1}-d_n=2h^2$, so $d_n=d_1+2h^2(n-1)$. Summing from $1$ to $n$ givesUsing $y_N=5$ and $h=2/N$ yields $N{d}_1=4-h^{2}N(N-1)=4/N$, hence $d_1=4/N^2=h^2$. ThereforeThis also covers $N=1$, where there are no interior equations. Uniqueness follows because the difference of two solutions has zero second finite difference, hence is linear in $n$, and vanishes at both endpoints. This is an exact finite difference solution for constant second derivative: the method is exact at the nodes here because the centered second finite difference differentiates this quadratic polynomial exactly.

Put $h=\Delta x$ and suppose $L=(n+1)h$, so there are $n$ interior grid points $x_j=jh$, $j=1,\dots ,n$. Write $u_j(t)\simeq u(x_j,t)$. The fixed ends impose homogeneous Dirichlet boundary conditions,For a sufficiently smooth displacement field, the two Taylor series at fixed time givewhere all displayed derivatives on the right are evaluated at $(x_j,t)$. Adding cancels the odd terms, leaving the second-order central differenceSubstitute this finite difference into the wave equation and retain continuous time. The resulting method of lines gives coupled second-order ordinary differential equations,In particular, the first and last equations are ${\ddot{u}}_1=(c^2/h^2)(-2u_1+u_2)$ and ${\ddot{u}}_n=(c^2/h^2)(u_{n-1}-2u_n)$ for $n\ge 2$. With the interior displacement vector only,Equivalently, $A_{jj}=-2c^2/h^2$, $A_{j,j+1}=A_{j+1,j}=c^2/h^2$, and all other entries vanish. This entrywise definition also covers small $n$, including $A=(-2c^2/h^2)$ when $n=1$. The matrix is a symmetric matrix and a tridiagonal matrix. The spatial approximation has error $O(h^2)$ in Big O notation; time has not yet been discretized.

Each supplied eigenvector gives relative displacements at $x=1,2,3$ in a standing wave. Insert zero at $x=0,4$ to describe the whole sampled string. A real normal mode is $u_j(t)=C{v}_j\cos (\omega t+\varphi )$: its shape stays fixed while its amplitude oscillates.

These semidiscrete fixed-string normal modes are samples of $\sin (k\pi x/4)$, with $k=3,2,1$ in the order listed. More precisely, their interior vectors are $v_j^{(k)}=2^{-1/2}\sin (k\pi j/4)$, which have unit Euclidean norm and form an orthonormal basis of ${\mathbb{R}}^3$. Their eigenvalues and angular frequencies obeyThus larger absolute value of a negative eigenvalue means faster oscillation, rather than faster decay. The numerical angular frequencies approximate the continuous fixed-string values $k\pi c/L$; the finite difference spatial approximation changes them. Only three independent interior normal modes exist on this grid, and any interior displacement or initial velocity vector can be expanded in this orthonormal basis.

Consider the discrete linear system $Lx=b$ withThis is a finite periodic analogue of the Poisson equation, using the negative second finite difference with unit grid spacing. It is also a Graph Laplacian equation on a cycle graph; no continuum approximation is being claimed here.

Summing the four equations gives zero on the left, since each value occurs twice positively and twice negatively. A necessary condition is therefore ${\sum }_n{b}_n=0$. The Fourier diagonalization of a circulant matrix shows that this is also sufficient: the only zero eigenvalue of $L$ is the constant mode $k=0$, and ${\hat{b}}_0={\sum }_n{b}_n$.

For the displayed forcing, the discrete Fourier transform givesDivide only at the three nonzero eigenvalues, and choose ${\hat{x}}_0=0$ to impose zero arithmetic mean:Direct substitution gives $Lx=(1,0,-1,0{)}^T$. All other vectors satisfying the linear system are $x+a(1,1,1,1{)}^T$, because the kernel is the space of constant vectors. Thus balanced forcing determines the differences between values, while a reference level is an extra choice. This small model explains why a periodic Poisson equation needs both a compatibility condition and a normalization.

On the unit interval with zero Dirichlet boundary conditions, $u_t=u_{xx}+\kappa u$ has sine-mode growth rates $\kappa -j^2{\pi }^2$. Every finite-energy initial condition decays exactly when the largest rate is negative, namely $\kappa <{\pi }^2$. A centered finite difference grid with $h=1/(M+1)$ has eigenvectors $\sin (j\pi m/(M+1))$ and growth rates $\kappa -4h^{-2}{\sin }^2(j\pi /(2(M+1)))$. Its all-data decay threshold is the displayed ${\kappa }_h$, strictly less than ${\pi }^2$ and approaching it from below. Equality leaves a stationary lowest mode; exceeding the threshold allows growth.

Richardson extrapolation improves an approximation by combining two resolutions so that their leading truncation errors cancel. The useful surprise is that the size of that leading error need not be known: its scaling under refinement is enough. This lets an existing finite difference method or quadrature rule produce a more accurate answer from two runs, without first deriving a new method from scratch.

Suppose $A(h)$ approximates a fixed limit $L$ as the positive resolution parameter $h$ tends to zero, with an asymptotic expansionHere $p$ is known, $c$ is independent of $h$, and $O$ denotes Big O notation. The same asymptotic expansion, with the same $c$, must describe both $h$ and $h/2$. Nested grids make it natural to reuse samples, although nesting itself does not establish this error model. Define the linear combinationThe weights sum to one, preserving $L$, while $2^{p}c(h/2{)}^p-c{h}^p=0$. Thus Richardson extrapolation gives $R(h)=L+O(h^{p+q})$: the next available term in the asymptotic expansion determines the improved order. Justin Solomon's numerical analysis text develops this cancellation for finite differences and applies it to numerical integration.^[ref]

Geometrically, regard the approximation as a function of $t=h^p$. Its first two terms are a straight line $L+ct$. The two computed points lie at positive $t$; extending the line through them to $t=0$ gives $R(h)$. This is why the operation is extrapolation: it estimates a value outside the sampled parameter interval. The remaining curvature corresponds to the uncancelled terms of the asymptotic expansion.

Worked example: a centered derivative of sine. For the smooth function $f(x)=\sin x$, the exact derivative at $x=0$ is $L=\cos 0=1$. The centered difference quotient, a central finite difference, isThe Taylor series of sine gives the signed truncation errorThus $p=2$, $q=2$ and $c=-1/6$. Halving $h$ divides the leading truncation error by four. Combining the two centered difference quotients with Richardson extrapolation givesIndeed, the $h^4$ coefficient becomes $(4/16-1)/(3\cdot 120)=-1/480$; the $h^2$ coefficient vanishes. This is the even-power case of Richardson extrapolation discussed in Persson's authored lecture notes.^[ref]

For $h=0.4$ and $h/2=0.2$, the actual computations areThe absolute error drops from about $2.6454\times 10^{-2}$ for $A(0.4)$ to $5.3080\times 10^{-5}$ for $R(0.4)$, an improvement by roughly a factor of 498. Refining again gives $R(0.2)\approx 0.999996670632607$, whose absolute error is about $3.3294\times 10^{-6}$. The refined truncation errors decrease by nearly four for $A$ and nearly sixteen for $R$, reflecting their second and fourth orders.

The logarithmic scale on each axis turns power laws into straight lines. The dashed reference curves are $h^2/6$ and $h^4/480$, the magnitudes of the leading truncation errors. The plotted errors are computed with 70-digit decimal arithmetic, rather than clipped to a display floor; this isolates the asymptotic expansion from roundoff error.

Worked example: integrating an exponential. Approximate the definite integral of the exponential function on $[0,1]$:For numerical integration, the composite trapezoidal rule adds the areas of trapezoids between successive samples; this is the quadrature use of the endpoint average that also occurs in the ODE trapezoidal rule. On $n$ equal intervals, with $h=1/n$, defineSumming the geometric series gives $T_n=(e-1)\frac{h}{2}\frac{e^h+1}{e^h-1}$. Expanding the exponential function near zero yieldsThe leading truncation error again has $p=2$, $q=2$. On the uniform nested grids with $n$ and $2n$ intervals, Richardson extrapolation therefore givesThis linear combination is exactly composite Simpson's rule on the finer grid, whose spacing is $h/2$. On each coarse panel, an old endpoint receives weight $h/6$ and the new midpoint weight $2h/3$; shared old endpoints receive weight $h/3$. These are the usual Simpson's rule weights $1,4,2,\dots ,4,1$ multiplied by $h/6$. The equivalence is explained directly in LeMesurier's university notes.^[ref]

For two coarse panels and four fine panels,The absolute errors are about $0.0356493$, $0.00894008$ and $0.0000370135$, respectively. Reusing the fine-grid samples makes Richardson extrapolation especially attractive here: the resulting Simpson's rule needs no samples beyond those already used by $T_{2n}$.

When the improvement is justified. Richardson extrapolation requires the stated asymptotic expansion and the correct positive $p$. If the actual leading exponent is $r\ne p$, its coefficient after combination is $c(2^{p-r}-1)/(2^p-1)$, so the leading truncation error generally remains. Merely knowing $A(h)-L=O(h^p)$ does not supply a common coefficient $c$ or a higher-order remainder. A discontinuity of a function, a singular endpoint, or unrelated changes between grids can invalidate the assumed asymptotic expansion; refinement alone does not guarantee improvement for every numerical problem.

Roundoff error and errors in the sampled values survive the cancellation of truncation error. If the coarse and fine values have absolute perturbations bounded by $\epsilon$, the perturbation in $R(h)$ is bounded by $(2^p+1)\epsilon /(2^p-1)$; for $p=2$ this is $5\epsilon /3$. In floating-point arithmetic, a centered difference quotient can also amplify sample errors through division by $h$, so an indefinitely smaller $h$ need not be more accurate. Persson's notes describe this balance between truncation error and roundoff error.^[ref]

The same cancellation idea appears in step-doubling error estimation. For an order-$p$ one-step method for an ordinary differential equation, two half steps each contribute local truncation error of order $h^{p+1}$, so their accumulated leading local error has ratio $2^{-p}$ to one full step. This explains the denominator $2^p-1$ there; the appropriate exponent follows from that local error model, rather than automatically from a generic use of Richardson extrapolation.

The Haar wavelet provides an explicit one-vanishing moment comparison:It cancels a constant polynomial, but not a nonconstant affine function. To obtain two vanishing moments by an equally transparent construction, take three adjacent unit intervals with heights proportional to $1,-2,1$:The L2 norm normalization follows from $1^2+(-2{)}^2+1^2=6$. Direct integration givesThus $\eta$ has exactly two vanishing moments. In fact its coefficient is a finite difference of adjacent local integrals:The weights are those of the second-order central difference. The first moment balances the centres of the three intervals; it is not enough merely to balance their signed areas.

This $\eta$ is a normalized analyzing function, with no orthonormal basis assertion. Indeed, its unit translate has nonzero L2 inner product:Hence these translates already fail orthogonality. The Daubechies wavelet construction imposes additional refinement and orthogonality requirements; two vanishing moments and unit L2 norm by themselves do not supply those requirements.

The tangent stiffness at a point on a differentiable force-displacement curve is its local slope,It governs the first-order response to a small displacement change:The graphical interpretation is the slope of the tangent line. Structural stiffness measured from force-deflection behaviour includes geometry as well as material response.^[ref]

For the illustrative model $F(x)=ax+b{x}^3$, choose $a=100\mathrm{N}{\mathrm{m}}^{-1}$ and $b=1000\mathrm{N}{\mathrm{m}}^{-3}$. At $x_0=0.10\mathrm{m}$, the tangent stiffness is $130\mathrm{N}{\mathrm{m}}^{-1}$. An additional $\Delta x=0.001\mathrm{m}$ therefore predicts a force increase of $0.130\mathrm{N}$ to first order. Direct substitution gives $0.130301\mathrm{N}$; the difference is the higher-order contribution omitted by the tangent approximation. The secant stiffness from the origin is only $110\mathrm{N}{\mathrm{m}}^{-1}$ at this point.

In a displacement-controlled experiment, one can estimate the local slope with a central finite difference,Making $h$ smaller reduces the approximation error for a smooth exact curve, but measured differences can become dominated by measurement uncertainty. The force channel, displacement channel and loading branch must therefore be specified. Crosshead movement can include machine mechanical compliance, while an extensometer records a selected specimen extension.^[ref]

For a curve with hysteresis, loading and unloading can have different local slopes at the same displacement. At a sharp corner a unique derivative may not exist, and a finite-interval slope should be reported as such.

A telescoping sum cancels intermediate sequence terms, leaving boundary terms. For a finite sequence of real numbers $a_0,\dots ,a_n$, the displayed identity follows because every $a_1,\dots ,a_{n-1}$ occurs once with each sign. Applying it to an infinite series also requires checking the limit of the boundary terms; finite cancellation alone does not prove that the series is a convergent series.^[ref]

For $n\ge 1$, expanding the finite sum givesNo monotone sequence assumption is required. Consider the original sequence $4,9,2,7,5$. Its successive finite differences are $5,-7,5,-2$, soThe large intermediate rise and fall disappear from the net change. This is useful whenever one knows successive changes rather than every absolute value: adding the changes reconstructs the final value from the initial one. It also checks a cumulative-update calculation without requiring all increments to be positive.

A finite difference $\Delta a_{k-1}=a_k-a_{k-1}$ measures one discrete change. The identity ${\sum }_{k=1}^n\Delta a_{k-1}=a_n-a_0$ is the discrete counterpart of the fundamental theorem of calculus: accumulation of changes returns the endpoint difference. The related summation by parts transfers a finite difference from one factor of a product to another, with explicit boundary terms.

The Thomas algorithm is Gaussian elimination specialized to a tridiagonal matrix: each row couples an unknown only to its immediate neighbours. Eliminating one unknown changes just the next diagonal entry and right-hand side. Provided all pivot elements are nonzero, a forward sweep followed by back substitution solves an $n$-unknown linear system in $O(n)$ time and storage, using Big O notation. Treating the same entries as a full matrix wastes the zeros: classical dense LU factorization and solve costs grow cubically for factorization and quadratically for storage.

A concrete reason to care is the Dirichlet Poisson solution by tridiagonal elimination: a three-point finite difference for the second derivative couples adjacent points on a mesh, producing precisely this tridiagonal matrix. The same structure occurs in one-dimensional Crank-Nicolson method calculations. NPTEL's archived Lecture 13 introduces the Thomas algorithm from that time-stepping problem and labels the procedure “Thomas algorithm (1949)”.^[ref]

Truncation error is introduced by replacing an exact operation with a finite approximation. It remains even when all arithmetic is exact. For $f(x)=x^2$, the forward finite difference for its derivative at $x=1$ givesThus the truncation error is exactly $h$: $h=0.1$ gives $2.1$ and $h=0.01$ gives $2.01$. In finite precision, however, the numerator subtracts nearly equal values, and their roundoff error can be amplified by division by $h$. For smooth data with bounded evaluation errors of scale $u$, a typical bound has competing terms $C_{1}h+C_{2}u/h$. Smaller $h$ reduces the first term and increases the second; with fixed positive constants the balancing scale is $h\sim \sqrt{u}$. This is why blindly refining a finite difference eventually stops improving it.

For fixed $r$ and $f\in C^r[0,1]$, uniform convergence of normalized finite differences to $f^{(r)}$, uniform continuity of $f^{(r)}$, and $(n{)}_r/n^r\to 1$ imply $g_{n,r}\to f^{(r)}$ uniformly. Positivity and partition of unity make Bernstein polynomials contractions in the supremum norm. Consequently $\Vert B_{n-r}{g}_{n,r}-f^{(r)}{\Vert }_{\infty }\le \Vert g_{n,r}-f^{(r)}{\Vert }_{\infty }+\Vert B_{n-r}{f}^{(r)}-f^{(r)}{\Vert }_{\infty }\to 0$. The differentiability assumption is essential; continuity alone does not define the target derivative.

Consider the explicitly specified objectiveand estimate its derivative by a symmetric finite difference with step $h>0$. The choice of shared or independent noise changes the estimator's variance even though both use correct normal distributions at the two parameter values.

With common random numbers, the same $\epsilon$ appears on both sides:Thus $\mathbb{E}[G_{\mathrm{shared}}]=2\mu$ and $\mathrm{Var}(G_{\mathrm{shared}})=4{\sigma }^2$, independent of $h$. Cancellation removes the noisy square term. For this quadratic, the symmetric difference has no truncation bias in exact arithmetic.

For independent standard normals ${\epsilon }_{+},{\epsilon }_{-}$, instead useIf $Y=m+\sigma \epsilon$, expand $Y^2=m^2+2m\sigma \epsilon +{\sigma }^2{\epsilon }^2$. The standard-normal moments $\mathbb{E}{\epsilon }^2=1$, $\mathbb{E}{\epsilon }^3=0$ and $\mathbb{E}{\epsilon }^4=3$ giveAdding the two independent square variances and dividing by $4h^2$ yieldsBoth estimators have the correct expected value $2\mu$, but the independent-noise variance diverges as $h$ tends to zero. At $\mu =\sigma =1$ and $h=0.1$, the variances are $4$ and $302$. An average of $n$ independent replicate estimators divides each variance by $n$.

This is a complete calculation for the stated quadratic, not a universal dominance theorem. At $\mu =0$, $\sigma =1$ and $h=1$, the independent variance is $3$, below the shared value $4$. The covariance principle in common random numbers explains why coupling needs a specified objective and comparison. Very small steps in floating-point evaluation also introduce cancellation concerns that this exact-arithmetic model does not include.

For the centered second-difference matrix with diagonal $-2$ and off-diagonals $1$, the weighted-Jacobi eigenvalues areThe method converges for every grid size exactly when $0<\omega \le 1$.

Multiplying both $A$ and $b$ by $-1$ leaves $D^{-1}A$ and the weighted Jacobi method unchanged. Thus the same formula applies to the positive second-difference matrix $T_n$ with diagonal $2$ and neighboring entries $-1$, the finite difference form of the one-dimensional Poisson equation with Dirichlet boundary conditions. Its eigenvectors have components $\sin (jk\pi /(n+1))$, and $D^{-1}{T}_n$ has eigenvalues $1-\cos (k\pi /(n+1))$. At $\omega =2/3$, upper-half modes have factors between $-1/3$ and $1/3$, while low-frequency factors remain close to one on fine grids. This explains why the weighted Jacobi method helps a multigrid method by reducing oscillatory errors, even when it is a slow solver on its own.^[ref]

Taking a finite difference lowers the degree of a polynomial phase. For $S(\theta )={\sum }_{x=1}^{n}e(\theta P(x))$, expand $|S{|}^2$ by shifts $h$ and apply the Cauchy-Schwarz inequality to those shift sums. This gives $|S{|}^4\le 2n{\sum }_{h,l}{\sum }_{x\in I_{h,l}}e(\theta {\Delta }_h{\Delta }_{l}P(x))$, where $I_{h,l}$ enforces that $x,x+h,x+l,x+h+l$ lie in $[1,n]$. Although individual terms can be complex, the entire sum is real and nonnegative because it equals a sum of squares. For $P(x)=x^3$, the phase is $3hl(2x+h+l)$.