Main page
Community Hub0 subscribers
Community Hub
Truncation error
View on Wikipediafrom Wikipedia
In numerical analysis and scientific computing, truncation error is an error caused by approximating a mathematical process.[1][2] The term truncation comes from the fact that these simplifications often involve the truncation of an infinite series expansion so as to make the computation possible and practical.
Examples
[edit]Infinite series
[edit]A summation series for is given by an infinite series such as
In reality, we can only use a finite number of these terms as it would take an infinite amount of computational time to make use of all of them. So let's suppose we use only three terms of the series, then
In this case, the truncation error is
Example A:
Given the following infinite series, find the truncation error for x = 0.75 if only the first three terms of the series are used.
Solution
Using only first three terms of the series gives
The sum of an infinite geometrical series is given by
For our series, a = 1 and r = 0.75, to give
The truncation error hence is
Differentiation
[edit]The definition of the exact first derivative of the function is given by
However, if we are calculating the derivative numerically, has to be finite. The error caused by choosing to be finite is a truncation error in the mathematical process of differentiation.
Example A:
Find the truncation in calculating the first derivative of at using a step size of
Solution:
The first derivative of is and at ,
The approximate value is given by
The truncation error hence is
Integration
[edit]The definition of the exact integral of a function from to is given as follows.
Let be a function defined on a closed interval of the real numbers, , and be a partition of I, where where and .
![{\displaystyle f:[a,b]\to \mathbb {R} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/b592d102ccd1ba134d401c5b3ea177baaba3ffac)
![{\displaystyle [a,b]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9c4b788fc5c637e26ee98b45f89a5c08c85f7935)
![{\displaystyle P=\left\{[x_{0},x_{1}],[x_{1},x_{2}],\dots ,[x_{n-1},x_{n}]\right\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e154f451e776e58ef356670f49b866ea897bda1b)
![{\displaystyle x_{i}^{*}\in [x_{i-1},x_{i}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dafeab86f1179399f11208ee27a15c76434aed3d)
This implies that we are finding the area under the curve using infinite rectangles. However, if we are calculating the integral numerically, we can only use a finite number of rectangles. The error caused by choosing a finite number of rectangles as opposed to an infinite number of them is a truncation error in the mathematical process of integration.
Example A.
For the integral find the truncation error if a two-segment left-hand Riemann sum is used with equal width of segments.
Solution
We have the exact value as
![{\displaystyle {\begin{aligned}\int _{3}^{9}{x^{2}{dx}}&=\left[{\frac {x^{3}}{3}}\right]_{3}^{9}\\&=\left[{\frac {9^{3}-3^{3}}{3}}\right]\\&=234\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a5709298d239080a0090b20171fa298364ac5e16)
Using two rectangles of equal width to approximate the area (see Figure 2) under the curve, the approximate value of the integral
Occasionally, by mistake, round-off error (the consequence of using finite precision floating point numbers on computers), is also called truncation error, especially if the number is rounded by chopping. That is not the correct use of "truncation error"; however calling it truncating a number may be acceptable.
Addition
[edit]Truncation error can cause within a computer when because (like it should), while . Here, has a truncation error equal to 1. This truncation error occurs because computers do not store the least significant digits of an extremely large integer.
See also
[edit]References
[edit]- Atkinson, Kendall E. (1989), An Introduction to Numerical Analysis (2nd ed.), New York: John Wiley & Sons, p. 20, ISBN 978-0-471-50023-0
- Stoer, Josef; Bulirsch, Roland (2002), Introduction to Numerical Analysis (3rd ed.), Berlin, New York: Springer-Verlag, p. 1, ISBN 978-0-387-95452-3.
Truncation error
View on Grokipediafrom Grokipedia
Definition and Fundamentals
Core Definition
Truncation error refers to the discrepancy between an exact mathematical value and its finite approximation resulting from terminating an infinite process, such as truncating an infinite series or discretizing a continuous function in numerical methods.[4] This error arises inherently from the approximation of infinite or continuous phenomena by finite representations, which is a fundamental aspect of numerical analysis. The concept gained prominence in numerical analysis during the mid-20th century, coinciding with the rise of digital computing, though early discussions on related approximation errors appeared in Lewis Fry Richardson's 1910 work on finite difference solutions to differential equations and extrapolation techniques to mitigate such inaccuracies.[5] A classic illustration is the approximation of using the Leibniz formula, where , and the partial sum after terms yields a truncation error equal to the remainder of the infinite tail.[6] Mathematically, for an infinite series approximated by the partial sum , the truncation error is given by
This formulation captures the error's dependence on the neglected terms beyond the truncation point.[4] Unlike round-off error, which stems from finite-precision arithmetic in computations, truncation error originates from the model's inherent limitations in representing the exact process.[7]
Distinction from Round-Off Error
Round-off error arises from the finite precision with which numbers are represented and manipulated in computer systems, particularly through floating-point arithmetic that cannot exactly capture most real numbers./01:_Introduction/1.03:_Sources_of_Error) For instance, the decimal 0.1 is approximated in binary floating-point as 0.1000000000000000055511151231257827021181583404541015625 in double precision, introducing a small but inherent discrepancy.[8] In contrast to truncation error, which stems from approximations inherent to the numerical algorithm or model—such as terminating an infinite series or using finite differences—round-off error originates solely from the hardware and software limitations in representing and computing with numbers.[9] This fundamental difference means truncation error depends on the choice and refinement of the method, while round-off error is tied to the precision level of the computing environment; consequently, truncation often dominates in high-precision methods where arithmetic accuracy is sufficient to make algorithmic approximations the primary limitation, whereas round-off prevails in low-precision settings where representation errors amplify quickly.[10] The total numerical error in computations is the sum of truncation error and round-off error, necessitating separate analysis to develop effective mitigation strategies, such as balancing step sizes to minimize their combined impact./01:_Introduction/1.03:_Sources_of_Error) This separation allows for targeted improvements, like increasing arithmetic precision to curb round-off or refining algorithms to reduce truncation.[9] The distinction between these errors was particularly emphasized in early computational mathematics to guide error analysis amid the limitations of nascent computing hardware, as detailed in J. H. Wilkinson's seminal 1963 book Rounding Errors in Algebraic Processes, which focused on bounding round-off propagation while implicitly highlighting its separation from approximation-induced errors. In double-precision floating-point arithmetic, round-off error is typically on the order of the machine epsilon, $ \mathcal{O}(\epsilon_{\text{machine}}) \approx 10^{-16} $, and remains largely independent of the number of algorithmic steps.[8]Mathematical Formulation
General Expression
In numerical analysis, the truncation error arises when an exact mathematical quantity is approximated by a finite process, such as a partial sum or iterative scheme, denoted as , where represents the truncation parameter, such as the number of terms in a series or the number of computational steps. The general expression for the truncation error is given by , capturing the discrepancy between the true value and the approximation. This form is foundational across various approximation methods, including polynomial expansions and discrete schemes for solving equations.[11] As the truncation parameter increases or the step size decreases (where often parameterizes the discretization, such as grid spacing), the truncation error exhibits asymptotic behavior: as , provided the approximation converges to the exact solution. The rate of convergence is typically characterized by the order of the method, expressed as , where is the order of accuracy, indicating that the error decreases proportionally to for small . For instance, in first-order methods like the forward Euler scheme, , while higher-order methods achieve larger . This big-O notation quantifies the leading-order term in the error expansion, derived from Taylor series analysis of the approximation process.[11] A prominent example of this framework occurs in the truncation of Taylor series expansions. For a function expanded around a point , the partial polynomial yields a truncation error via the Lagrange form of the remainder:
for some between and . This exact expression, part of Taylor's theorem, bounds the error and highlights its dependence on higher derivatives and the expansion order.[11]
Truncation errors are further distinguished by scope in iterative methods, particularly for solving differential equations. The local truncation error represents the discrepancy introduced in a single step of the approximation, measuring how well the exact solution satisfies the discrete equation at that step alone, often for a method of global order . In contrast, the global truncation error accumulates these local contributions over multiple steps, resulting in an overall error of for the entire computation, assuming stability. This distinction is crucial for assessing method reliability in long simulations.[11][12]
Error Estimation Techniques
Error estimation techniques for truncation error focus on analytical methods to bound or quantify the discrepancy between exact and approximate solutions without requiring knowledge of the true solution. These approaches are essential in numerical analysis to assess method reliability and guide parameter selection, such as step sizes.[13] Asymptotic analysis provides a primary tool for estimating truncation error by examining the behavior as discretization parameters, like step size , approach zero. In this framework, the error is typically expressed as , where is a constant depending on the problem and is the order of convergence. To determine and approximate , approximations are computed at successively refined grids (e.g., , ) and the differences are analyzed, revealing the dominant error term through logarithmic plots or direct ratios. This method underpins convergence studies in iterative numerical schemes.[14] Remainder theorems offer explicit bounds for truncation errors in series expansions. For Taylor series approximations, the integral form of the remainder provides a precise estimate: after truncating at order , the error is , which can be bounded using bounds on the -th derivative. In the context of alternating series, Leibniz's test (also known as the alternating series estimation theorem) bounds the truncation error after terms by , where are the absolute values of the terms, provided the series terms decrease monotonically to zero. These theorems enable conservative error guarantees directly from problem properties.[15][16] Richardson extrapolation enhances error estimation by combining solutions from multiple step sizes to eliminate leading error terms. Assuming the approximation satisfies , the extrapolated error estimate is , which isolates higher-order terms and can achieve superconvergence. This technique, originally developed for geophysical computations, is widely applied to refine estimates in finite difference and integral methods. In finite difference methods, the order of truncation error directly governs overall accuracy; for instance, the forward difference approximation for the first derivative, , incurs a truncation error of , derived from Taylor expansion, making it first-order accurate. Higher-order schemes, like central differences, reduce this to , but the forward method's simplicity suits certain applications despite its coarser bound.[17] A concrete example arises in solving ordinary differential equations (ODEs) with the explicit Euler method, where the local truncation error— the error introduced per step—is . This follows from Taylor expanding the exact solution around the current point: for some , with the Euler step matching only up to the linear term, leaving the quadratic remainder. Global error then accumulates as over fixed intervals.[18]Applications in Numerical Analysis
Function Approximation via Series
In function approximation via series expansions, truncation error arises when a finite number of terms is used to represent an infinite series, such as in Taylor or Fourier expansions, leading to a remainder that quantifies the deviation from the true function value.[19] For Taylor series, a smooth function is approximated around a point by the partial sum
where the truncation error is captured by the remainder term .[19] The Lagrange form of this remainder is
for some between and , providing a bound on the error based on the magnitude of the -th derivative.[20] This error decreases as increases for analytic functions within their radius of convergence, but the rate depends on the function's smoothness and the interval of approximation./10%3A_Power_Series/10.03%3A_Taylor_and_Maclaurin_Series)
A classic example is the Taylor approximation of the sine function around , where . Truncating after the cubic term gives , with the third-order remainder for some between 0 and . Since , the error is bounded by , which is particularly small for but grows outside this range, illustrating how truncation error scales with distance from the expansion point./10%3A_Power_Series/10.03%3A_Taylor_and_Maclaurin_Series)
In Fourier series approximations, truncation error manifests differently for periodic functions with discontinuities, leading to the Gibbs phenomenon. When approximating a function like a square wave using the partial sum of its Fourier series up to terms, oscillations or "ringing" occur near jump discontinuities, with an overshoot of approximately 9% of the jump height that persists even as .[21] This artifact arises because the truncated series does not converge uniformly at discontinuities, resulting in a truncation error that fails to diminish locally despite pointwise convergence elsewhere.[22]
Polynomial interpolation represents another series-based approximation where truncation error can lead to unexpected divergence, as seen in Runge's phenomenon. For equispaced nodes on a wide interval like , interpolating the Runge function with polynomials of increasing degree causes large oscillations near the endpoints, diverging as grows due to the rapid increase in the Lebesgue constant for equidistant points./05%3A_Interpolation/5.05%3A_Spline_Method_of_Interpolation) The error formula for interpolation at nodes is
for some in the interval spanning the nodes and , where the nodal polynomial amplifies the error for equispaced nodes on large intervals.[23] This highlights the importance of node selection, such as Chebyshev points, to mitigate truncation-like divergence in practice.
Numerical Differentiation
In numerical differentiation, truncation error arises when approximating derivatives using finite difference methods, which replace continuous derivatives with discrete differences based on function evaluations at nearby points. These approximations are derived from Taylor series expansions, truncating higher-order terms to yield an error proportional to the step size . The leading-order truncation error term typically involves higher derivatives of the function, and reducing diminishes the error, though it must be balanced against round-off errors in practice. The forward difference formula for the first derivative is given by
with a truncation error of order . Using Taylor expansion, for some , the error term simplifies to , confirming the first-order accuracy. This method is simple but less accurate for smaller compared to symmetric alternatives.[24][25]
A higher-order approximation is the central difference formula,
which achieves a truncation error of order . The Taylor expansions around yield and , resulting in a leading error term of for some . This second-order accuracy reduces truncation error more effectively, making it preferred in many applications.[24]
For the second derivative, a common central difference approximation is
with truncation error of order . Taylor series expansion leads to a leading error term of , demonstrating second-order accuracy where the error depends on the fourth derivative. This stencil is widely used due to its balance of simplicity and precision.[24][25]
In general, for approximating the -th derivative using an -point stencil, the finite difference scheme solves for coefficients that match the Taylor expansion up to the desired order, yielding a truncation error of where for centered stencils, with the leading term involving the -th derivative of the function. This error structure, derived via Taylor series, allows for higher-order methods by expanding the stencil width.
In computational fluid dynamics, truncation errors from finite difference approximations significantly impact numerical stability, as analyzed through the modified equation approach. This method derives an effective partial differential equation that the discrete scheme solves exactly, incorporating truncation terms as additional dispersion (odd-order derivatives) or dissipation (even-order derivatives); for instance, central differences introduce dispersive errors that can lead to phase errors and instability for poorly resolved waves, while upwind schemes add numerical dissipation affecting short wavelengths. The approach, originally developed by Warming and Hyett, reveals how these error-induced terms modify the underlying PDE, guiding scheme design for stable simulations.90011-4)[26]
Numerical Integration
In numerical integration, truncation error arises from approximating the definite integral using discrete quadrature rules that rely on polynomial interpolation of the integrand, leading to discrepancies proportional to higher-order derivatives of . These errors are inherent to the method's finite representation of the continuous integral and diminish as the step size decreases, typically following an order of convergence determined by the rule's polynomial degree. Common quadrature methods, such as those based on Newton-Cotes formulas, derive their truncation errors from the remainder term in the interpolation polynomial via the error formula for interpolatory quadrature.[27] The trapezoidal rule approximates the integral over by assuming linear interpolation between endpoints, yielding for a single interval of width , with a local truncation error of for some . For the composite trapezoidal rule over subintervals each of width , the approximation becomes , and the total truncation error is , which is globally. This quadratic convergence stems from the rule's exactness for linear polynomials, with the second derivative capturing the curvature neglected in the approximation.[27][28] Simpson's rule improves accuracy by employing quadratic interpolation over two subintervals, using three points to approximate for , with a local truncation error of for . In its composite form over subintervals of width , the rule extends to , yielding a total error of , or overall. This higher-order error, derived from the interpolatory remainder and symmetry properties, makes Simpson's rule exact not only for quadratics but also for cubics.[27][28] More generally, for a closed Newton-Cotes k-point rule (using polynomial interpolation of degree k-1 over [a,b]), the truncation error depends on the parity of n = k-1: if n is odd, it is proportional to (b-a)^{n+2} f^{(n+1)}(\xi); if n is even, proportional to (b-a)^{n+3} f^{(n+2)}(\xi), for some \xi \in (a, b). This expression arises from the Peano kernel theorem applied to the interpolation error, bounding the discrepancy based on higher derivatives. For instance, the trapezoidal rule (k=2, n=1 odd) has error -\frac{(b-a)^3}{12} f''(\xi), while Simpson's rule (k=3, n=2 even) has -\frac{(b-a)^5}{2880} f^{(4)}(\xi).[29][27] Gaussian quadrature exemplifies advanced rules that optimize node placement and weights to minimize truncation error, achieving exactness for polynomials up to degree with only points, far surpassing Newton-Cotes for the same number of evaluations. The error term involves the -th derivative: for the -point Gauss-Legendre rule on (scalable to ), for some , reflecting the rule's roots at the zeros of the -th Legendre polynomial. This leads to exponential convergence for smooth analytic functions, making it ideal for high-precision applications.[30] In adaptive integration schemes, truncation error estimates from these rules guide dynamic mesh refinement to balance accuracy and efficiency. For instance, MATLAB'squad function (now superseded by integral but historically influential) employs adaptive Simpson's quadrature, estimating local error as the difference between coarse- and fine-grid approximations () and recursively subdividing subintervals until the estimated error falls below a user-specified tolerance, typically achieving the desired precision with fewer evaluations for smooth integrands.[31]
Additional Contexts
Summation and Addition Algorithms
In the context of summation and addition algorithms, truncation error arises when approximating an infinite series by a finite partial sum, leading to the omission of the tail terms. For convergent series with positive terms, such as the Taylor series for , the partial sum up to terms introduces a truncation error equal to the remainder for some between 0 and , which can be bounded as .[32] This bound ensures the error decreases rapidly for fixed as increases, due to the factorial growth in the denominator. For a general decreasing positive term series with where is positive, continuous, and decreasing, the truncation error after terms, , satisfies the integral test remainder estimate:
This provides both lower and upper bounds for the error, allowing precise control in numerical approximations without computing the full sum.[33][34]
A representative example is the harmonic series partial sum , which approximates the divergent full sum but is often used in asymptotic analysis. Using the Euler-Maclaurin formula, the truncation error relative to its known approximation (where is the Euler-Mascheroni constant) is given by , enabling accurate estimation for large .[35]
In addition algorithms, particularly for floating-point summation of finite but large sets of terms, truncation error can occur from deliberately ignoring small contributions to enhance computational efficiency, distinct from round-off errors due to precision limits. Adaptive truncation methods, such as error-bounding pairs, terminate summation when remaining terms fall below a threshold , guaranteeing the total error within while reducing the number of operations by up to 6.5% compared to naive thresholds for certain series.[36] These approaches incorporate stable summation techniques like Kahan compensation to minimize additional numerical instability.[36]
In big data processing, stochastic truncation in Monte Carlo summation introduces controlled truncation error by randomly selecting a finite number of terms from an infinite series representation, such as in Bayesian inference with intractable normalizing constants. This Russian Roulette technique provides unbiased estimators with variance bounds scaling favorably for scalability, allowing efficient approximation of expectations over massive datasets without full enumeration.[37]
Time-Stepping in Differential Equations
In numerical solutions of ordinary differential equations (ODEs) of the form $ y' = f(t, y) $, time-stepping methods discretize the continuous time evolution into finite steps of size $ h $, approximating the solution at discrete points $ t_n = t_0 + n h $. These methods inherently introduce truncation errors arising from the replacement of the exact integral or derivative with a finite difference approximation. The local truncation error measures the discrepancy per step when the exact solution is plugged into the numerical scheme, while the global truncation error accumulates over multiple steps to affect the overall accuracy. Convergence order concepts indicate that methods with higher order $ p $ achieve global errors of $ O(h^p) $, contingent on the local errors being $ O(h^{p+1}) $.[38] The explicit Euler method, $ y_{n+1} = y_n + h f(t_n, y_n) $, serves as the foundational explicit one-step approach, with a local truncation error of $ O(h^2) $ and global error of $ O(h) $. This error stems from the first-order Taylor approximation of the solution increment. More precisely, the local truncation error is defined as
derived via Taylor expansion of the exact solution $ y(t) $ around $ t_n $, where the leading term involves the second derivative $ y''(\xi) $ for some $ \xi \in (t_n, t_{n+1}) $. Under suitable smoothness assumptions on $ f $ and $ y $, the global error satisfies $ |y(t_n) - y_n| \leq C h $ for a constant $ C $ independent of $ h $ over a fixed interval.[38]
Higher-order methods mitigate these errors through more sophisticated approximations. The classical fourth-order Runge-Kutta (RK4) method, for example, uses four internal stages to estimate the increment, yielding a local truncation error of $ O(h^5) $ and global error of $ O(h^4) $. This reduction is achieved by weighted combinations of slopes evaluated at intermediate points, effectively canceling lower-order terms in the Taylor expansion up to the fourth derivative. Such multi-stage evaluations balance computational cost with improved accuracy for non-stiff problems.[39][38]
A illustrative example is the linear ODE $ y' = -y $ with initial condition $ y(0) = 1 $, whose exact solution is $ y(t) = e^{-t} $. Applying the Euler method produces $ y_{n+1} = (1 - h) y_n $, resulting in $ y_n = (1 - h)^n $, an exponential decay with rate $ \ln|1 - h| \approx -h - h^2/2 $ for small $ h > 0 $. The truncation error causes the numerical solution to decay more slowly than the exact $ e^{-t} \approx 1 - t + t^2/2 $, introducing a damping discrepancy that grows with the number of steps.[38]
For stiff ODEs, characterized by eigenvalues with widely separated magnitudes, explicit methods like forward Euler require prohibitively small $ h $ to control truncation errors without numerical instability, as the error amplification can dominate. Implicit methods, such as backward Euler $ y_{n+1} = y_n + h f(t_{n+1}, y_{n+1}) $, offer local truncation error $ O(h^2) $ while maintaining stability for larger steps via solution of nonlinear equations at each stage. This approach was pioneered in analyses of stiff systems in chemical kinetics, notably by Curtiss and Hirschfelder in 1952, who emphasized the need for methods that handle disparate timescales without excessive truncation penalties.[38]