The Central Idea
A numerical answer should not be accepted merely because many digits are displayed.
Reliable numerical work asks four questions:
- Is the method converging?
- How large is the error?
- What tolerance is required?
- How can the result be verified?
Together, these questions connect computation to mathematical evidence.
What Is Convergence?
A sequence of approximations
\[ x_0,\quad x_1,\quad x_2,\quad\ldots \]converges to \(L\) when the terms approach \(L\).
We write
\[ \boxed{x_n\to L}. \]Informally, the approximations become arbitrarily close to \(L\) as the iteration continues.
Example of Convergence
Consider
\[ 1,\quad 1.5,\quad 1.416666\ldots,\quad 1.414215\ldots,\quad 1.41421356\ldots \]These values approach
\[ \sqrt2. \]Therefore,
\[ \boxed{x_n\to\sqrt2}. \]Divergence
A sequence diverges when it does not approach a finite limiting value.
For example,
\[ 1,\quad2,\quad4,\quad8,\quad16,\quad\ldots \]grows without bound.
It does not converge to a finite number.
Oscillation
Some sequences move repeatedly between values rather than approaching one limit.
For example,
\[ 1,\quad-1,\quad1,\quad-1,\quad\ldots \]oscillates and does not converge.
Convergence Is about the Sequence, Not Just One Step
A single small change between two iterates does not prove that the entire process converges.
Convergence concerns the long-term behavior of
\[ x_0,x_1,x_2,\ldots \]as a sequence.
True Error
Suppose the exact value is \(r\) and the numerical approximation is \(x\).
The signed error is
\[ e=x-r. \]The absolute error is
\[ \boxed{|x-r|}. \]Example: Absolute Error
Approximate
\[ \sqrt2 \]by
\[ 1.414. \]Since
\[ \sqrt2\approx1.414213562, \]the absolute error is approximately
\[ |1.414-1.414213562| \approx0.000213562. \]Thus,
\[ \boxed{\text{absolute error}\approx2.14\times10^{-4}}. \]Relative Error
Absolute error does not account for the scale of the true value.
When \(r\ne0\), the relative error is
\[ \boxed{ \frac{|x-r|}{|r|} }. \]It measures the error as a fraction of the true value.
Percent Error
Percent error is the relative error expressed as a percentage:
\[ \boxed{ \frac{|x-r|}{|r|}\times100\% }. \]Percent error is especially useful when comparing approximations across quantities of different sizes.
When the True Value Is Unknown
In most real numerical problems, the exact solution \(r\) is unknown.
Therefore,
\[ |x-r| \]cannot be computed directly.
Numerical methods instead use estimates or bounds based on available information.
Error Bound
An error bound is a number \(E\) known to satisfy
\[ \boxed{|x-r|\le E}. \]This is stronger than merely observing that an approximation appears close to the answer.
Bisection Gives a Direct Error Bound
Suppose a root \(r\) is known to lie in
\[ [a,b]. \]If the midpoint
\[ m=\frac{a+b}{2} \]is used as the approximation, then
\[ \boxed{ |m-r|\le\frac{b-a}{2} }. \]This is one reason bisection is so reliable.
Example: Bisection Error Bound
Suppose
\[ r\in[1.5213,1.5215]. \]The midpoint is
\[ m=1.5214. \]The interval width is
\[ 0.0002. \]Therefore,
\[ \boxed{|m-r|\le0.0001}. \]Successive Difference
In iterative methods, a commonly monitored quantity is
\[ \boxed{ |x_{n+1}-x_n| }. \]This measures the size of the latest update.
It is useful, but it is not generally identical to the true error.
Small Step versus Small Error
It is tempting to assume
\[ |x_{n+1}-x_n| \approx |x_n-r|. \]That approximation may be reasonable for some convergent methods near a root, but it is not a universal law.
A method can stagnate or converge slowly while the true error remains significant.
Residual
When solving
\[ f(x)=0, \]the residual at an approximation \(x\) is
\[ \boxed{f(x)}. \]Its magnitude
\[ |f(x)| \]measures how closely the approximation satisfies the equation in output space.
Residual Is Not the Same as Error
Error is measured in the input:
\[ |x-r|. \]Residual is measured through the equation:
\[ |f(x)|. \]These quantities can behave very differently.
Example: Residual and Error Can Differ
Consider
\[ f(x)=10^{-6}(x-1000). \]The exact root is
\[ r=1000. \]At
\[ x=999, \]the true error is
\[ |999-1000|=1, \]but the residual is only
\[ |f(999)|=10^{-6}. \]A tiny residual does not automatically imply a tiny error in \(x\).
Why the Derivative Connects Residual and Error
Near a simple root \(r\), a linear approximation gives
\[ f(x)\approx f'(r)(x-r). \]Since
\[ f(r)=0, \]the local relationship is
\[ \boxed{ x-r \approx \frac{f(x)}{f'(r)} }. \]Therefore, the local slope influences how residual size relates to root error.
Flat Functions Can Hide Error
If
\[ |f'(r)| \]is very small, then a small residual may correspond to a relatively large error in the root location.
This is one reason residual checks should be interpreted together with local sensitivity.
Tolerance
A tolerance is a chosen threshold that determines how much numerical discrepancy is acceptable.
For example,
\[ \varepsilon=10^{-6} \]might be used to stop an iteration once a relevant error indicator falls below that level.
Tolerance Is a Requirement, Not an Error
The tolerance
\[ \varepsilon \]is a target chosen by the user or problem.
The actual error is whatever discrepancy remains.
These are conceptually different quantities.
Absolute Tolerance
An absolute stopping condition might be
\[ \boxed{ |x_{n+1}-x_n|<\varepsilon }. \]This uses the same threshold regardless of the magnitude of \(x\).
Relative Tolerance
A relative stopping criterion may use
\[ \boxed{ \frac{|x_{n+1}-x_n|} {\max(1,|x_{n+1}|)} <\varepsilon }. \]The denominator prevents division by very small values while still scaling the test for large values.
Why Relative Tolerance Helps
An absolute error of
\[ 0.01 \]may be enormous for a quantity near
\[ 0.001 \]but negligible for a quantity near
\[ 10^8. \]Relative tolerance accounts for scale.
Mixed Tolerance
Numerical software often combines absolute and relative tolerances.
One common pattern is
\[ \boxed{ |x_{n+1}-x_n| \le \varepsilon_{\text{abs}} + \varepsilon_{\text{rel}}|x_{n+1}| }. \]This works across both small and large magnitudes.
Stopping Conditions
A numerical algorithm may stop when one or more of the following occurs:
\[ |x_{n+1}-x_n|<\varepsilon_x, \] \[ |f(x_n)|<\varepsilon_f, \] \[ b_n-a_n<\varepsilon_b, \]or
\[ n\ge N_{\max}. \]Success versus Safeguard Stops
Not every stop means success.
A tolerance condition may indicate successful convergence.
A maximum iteration count may indicate that the method failed to meet the requested tolerance.
Numerical software should distinguish these outcomes.
Convergence Rate
Two convergent methods may approach the same solution at very different speeds.
The rate of convergence describes how quickly the error decreases.
Faster convergence means fewer iterations are needed to achieve a given accuracy.
Linear Convergence
A method converges linearly when, approximately,
\[ |e_{n+1}| \approx C|e_n| \]with
\[ 0Example of Linear Convergence
If
\[ |e_{n+1}|\approx\frac12|e_n|, \]then each step roughly halves the error.
Bisection has this kind of predictable interval reduction.
Quadratic Convergence
A method has quadratic convergence when, approximately,
\[ \boxed{ |e_{n+1}| \approx C|e_n|^2 }. \]Once the error is small, squaring it can make it dramatically smaller.
Newton's method often has quadratic convergence near a suitable simple root.
Superlinear Convergence
Superlinear convergence is faster than linear convergence but need not be quadratic.
The standard secant method typically has convergence order
\[ \frac{1+\sqrt5}{2}\approx1.618 \]near a suitable simple root.
Convergence Rate Is Local
Statements such as
\[ \text{“Newton's method converges quadratically”} \]normally refer to behavior sufficiently near an appropriate simple root under suitable smoothness conditions.
Far from the root, the method may behave very differently.
Truncation Error
Truncation error arises when an infinite or exact mathematical process is replaced by a finite approximation.
Examples include:
- stopping an infinite series after finitely many terms;
- using a finite-difference approximation to a derivative;
- stopping an iterative solver after finitely many steps.
Roundoff Error
Roundoff error arises because numerical systems use finite precision.
Numbers such as
\[ \frac13,\qquad\pi,\qquad\sqrt2 \]cannot generally be stored exactly in ordinary finite floating-point arithmetic.
Truncation and Roundoff Are Different
Truncation error comes from replacing a mathematical process with a finite approximation.
Roundoff error comes from finite numerical representation.
Both may appear in the same computation.
Example: Truncation
Suppose an iterative root finder would converge only in the limit:
\[ x_n\to r. \]If the computation stops at
\[ x_{10}, \]the difference between \(x_{10}\) and \(r\) includes error caused by ending the infinite process after finitely many iterations.
Example: Roundoff
A computer may store a decimal approximation to
\[ \frac{1}{10} \]because \(0.1\) does not have a finite binary representation.
Repeated arithmetic with such approximations can accumulate small representation errors.
Accumulated Roundoff
A single roundoff error may be tiny.
Repeating millions of operations can magnify or accumulate such errors, especially when the algorithm is numerically sensitive.
Cancellation
Cancellation occurs when two nearly equal numbers are subtracted.
Significant digits may be lost because the leading digits cancel.
For example,
\[ 1.23456789-1.23456788=0.00000001. \]If the original numbers were already approximate, the relative accuracy of the difference can be poor.
Numerical Stability
A numerically stable algorithm controls the growth of computational errors.
An unstable algorithm can magnify small roundoff or input errors into large output errors.
Stability concerns the behavior of the algorithm.
Conditioning versus Stability
Conditioning concerns the mathematical problem.
Stability concerns the numerical algorithm.
A well-designed algorithm can reduce unnecessary computational error, but it cannot remove sensitivity that is inherent in an ill-conditioned problem.
Input Error
Numerical results can also inherit uncertainty from the inputs.
If a measured length is
\[ 10.0\pm0.1\text{ cm}, \]a computed area based on that measurement cannot meaningfully claim unlimited precision.
Error Propagation
Errors in input quantities can propagate through later calculations.
Some operations reduce their effect, while others magnify them.
Numerical verification should therefore consider not only computational error but also uncertainty already present in the data.
Backward Error
Another way to evaluate a numerical result is to ask:
For what nearby problem would this computed answer be exact?
This perspective is called backward error analysis.
It is especially important in advanced numerical analysis because a result may be trustworthy when it exactly solves a problem only slightly different from the original one.
Forward Error
Forward error measures how far the computed answer is from the exact answer:
\[ \boxed{|x-r|}. \]This is the direct error measure introduced earlier.
Residual as a Verification Tool
For
\[ f(x)=0, \]calculate
\[ \boxed{|f(x_{\text{approx}})|}. \]A small residual is an important first verification step.
Bracket Verification
If a continuous function satisfies
\[ f(a)f(b)<0, \]then the interval
\[ [a,b] \]provides independent evidence that at least one root lies inside.
A numerical approximation should be consistent with that bracket.
Substitution Verification
If a numerical method solves an equation written in transformed form, plug the candidate back into the original equation.
This is especially important after:
- squaring;
- clearing denominators;
- taking logarithms;
- introducing reciprocal expressions;
- changing variables.
Independent-Method Verification
A second numerical method can provide useful confirmation.
For example:
- locate a root by bisection;
- refine it by Newton's method;
- confirm with a residual check.
Agreement among independent methods strengthens confidence in the result.
Graphical Verification
A graph can confirm whether an approximate root lies near an \(x\)-axis crossing or whether two functions intersect near the reported point.
Graphical verification is especially good for detecting the wrong branch or an unintended solution.
It is usually not the strongest method for high-precision error control.
Dimensional Verification
In applied problems, units provide another check.
An answer for time should have units of time.
An answer for area should have squared length units.
A dimensionally impossible result indicates an error before numerical precision is even considered.
Magnitude Verification
Ask whether the answer has a plausible size.
If an equation is known to have a root between
\[ 2 \]and
\[ 3, \]a solver output of
\[ 27.4 \]should immediately trigger investigation.
Sign Verification
Context may determine the sign of a valid answer.
A physical length is typically nonnegative.
A probability must satisfy
\[ 0\le p\le1. \]Such constraints provide inexpensive verification.
Boundary Verification
Solutions should respect domain and boundary restrictions.
If the model requires
\[ x>0, \]then a negative numerical root is not an admissible solution to the modeled problem even if it satisfies a transformed algebraic equation.
Verification for Systems
For a system
\[ \mathbf{F}(\mathbf{x})=\mathbf{0}, \]evaluate every residual component.
A solution is reliable only if all equations are satisfied to the required tolerance.
Residual Norm for Systems
A residual vector
\[ \mathbf{r} = \mathbf{F}(\mathbf{x}) \]can be summarized by a norm such as
\[ \boxed{ \|\mathbf{r}\|_2 = \sqrt{r_1^2+r_2^2+\cdots+r_m^2} }. \]The norm should be consistent with the required tolerance and scaling of the equations.
Scaling Matters in Residual Tests
Suppose one equation naturally has values near
\[ 10^8 \]while another has values near
\[ 10^{-4}. \]Comparing raw residuals may be misleading.
Scaled or relative residuals may provide a more meaningful measure.
Correct Digits
If an approximation has absolute error less than
\[ 0.5\times10^{-k}, \]then rounding to \(k\) decimal places is guaranteed to match the correctly rounded exact value, provided no tie or representation ambiguity is present at the boundary.
Error bounds therefore connect directly to justified decimal reporting.
Example: Justifying Three Decimal Places
Suppose
\[ |x-r|<0.0005. \]Then the approximation is accurate enough to determine the correctly rounded value to three decimal places, except in an exact boundary case that would require explicit tie handling.
Interval Bounds and Rounding
Suppose
\[ 3.1622<\sqrt{10}<3.1623. \]Since the entire interval lies below
\[ 3.1625, \]every value in the interval rounds to
\[ \boxed{3.162} \]to three decimal places.
Why a Narrow Decimal Bracket May Need a Midpoint Check
Knowing only that
\[ 3.162The rounding boundary is
\[ 3.1625. \]Additional refinement is needed unless the bracket lies entirely on one side of that boundary.
Significant Figures
Significant figures concern precision relative to magnitude.
A relative error bound is often more natural for justifying significant figures than an absolute error bound.
False Precision
Reporting
\[ 1.521379706804568 \]is unjustified if the method only established
\[ |x-r|<10^{-4}. \]Extra displayed digits are not automatically meaningful digits.
Convergence Does Not Guarantee the Intended Solution
Newton's method may converge to a valid root that is not the root the problem intended.
Fixed-point iteration may converge to a different fixed point.
Therefore, convergence must be paired with domain and solution-region verification.
A Stable Decimal Is Not Necessarily a Correct Decimal
Suppose an algorithm repeatedly returns
\[ 2.000000. \]That value may be stable because of:
- true convergence;
- roundoff stagnation;
- a programming error;
- an incorrect update rule.
Stability must be verified against the original mathematical problem.
Stagnation
Stagnation occurs when further iterations stop changing the stored numerical value even though the desired mathematical accuracy has not necessarily been achieved.
Finite precision can cause
\[ x_{n+1}=x_n \]numerically before the true limiting process has finished.
Detecting Stagnation
If
\[ x_{n+1}=x_n \]but
\[ |f(x_n)| \]is still too large, the algorithm should not declare successful convergence.
It should report stagnation or insufficient precision.
Common Error: Confusing Residual with Error
A residual is
\[ f(x). \]Root error is
\[ x-r. \]They live in different spaces and need not have comparable magnitudes.
Common Error: Treating Tolerance as Guaranteed Error
A stopping rule such as
\[ |x_{n+1}-x_n|<10^{-6} \]does not automatically prove
\[ |x_n-r|<10^{-6}. \]Such a conclusion requires additional information about the method.
Common Error: Assuming More Iterations Always Improve the Answer
More iterations usually reduce truncation error for a convergent method.
But eventually:
- roundoff may dominate;
- stagnation may occur;
- an unstable process may amplify error.
More computation is not automatically better computation.
Common Error: Ignoring the Scale of the Problem
An absolute tolerance of
\[ 10^{-3} \]may be extremely strict for one problem and extremely loose for another.
Scale should influence tolerance selection.
Common Error: Verifying the Transformed Equation Only
If the original equation was altered, verify the candidate in the original form.
Otherwise, extraneous or inadmissible solutions may be accepted.
Common Error: Ignoring Solver Warnings
Numerical software may report:
- maximum iterations reached;
- singular matrix;
- derivative too small;
- failure to bracket a root;
- loss of precision.
These messages are part of the mathematical evidence and should not be discarded.
Common Error: Reporting an Approximation as Exact
Use
\[ = \]for exact equality and
\[ \boxed{\approx} \]for approximation.
For example,
\[ \sqrt2\approx1.414214. \]A Reliable Numerical Verification Workflow
- State the equation or system being solved.
- State the numerical method used.
- State the tolerance or stopping condition.
- Confirm that the method actually terminated successfully.
- Inspect successive iterates or interval widths for convergence behavior.
- Compute the residual.
- Use an error bound when the method provides one.
- Check domain, sign, magnitude, and units.
- Verify with an independent method when practical.
- Report only the precision justified by the evidence.
Example: Full Verification of a Bisection Result
Suppose bisection gives
\[ r\in[1.52137,1.52139] \]for
\[ f(x)=x^3-x-2. \]The midpoint is
\[ m=1.52138. \]The interval width is
\[ 0.00002. \]Therefore,
\[ |m-r|\le0.00001. \]Continue the Bisection Verification
Next, evaluate
\[ f(1.52138). \]The residual is very small.
We now have two different kinds of evidence:
- an interval-based error bound;
- a small equation residual.
Together they strongly support the reported approximation.
Example: Comparing Methods
Suppose bisection, Newton's method, and the secant method all produce
\[ x\approx1.52138 \]for
\[ x^3-x-2=0. \]Agreement among methods is useful, but it does not replace verification.
The final check remains:
\[ \boxed{|x^3-x-2|\text{ is sufficiently small}}. \]Practice 1: Absolute Error
The exact value is
\[ 5 \]and the approximation is
\[ 4.98. \]Find the absolute error.
Practice 2: Relative Error
Using the same values from Practice 1, find the relative error.
Practice 3: Percent Error
Convert the relative error from Practice 2 to percent error.
Practice 4: Bisection Bound
A root lies in
\[ [2.64,2.66]. \]If the midpoint is reported, what is the maximum possible error?
Practice 5: Residual
For
\[ f(x)=x^2-7 \]and
\[ x=2.646, \]compute the residual.
Practice 6: Tolerance versus Error
Does the stopping condition
\[ |x_{n+1}-x_n|<10^{-5} \]automatically prove
\[ |x_n-r|<10^{-5}? \]Practice 7: Convergence Type
If an error is approximately squared at every iteration,
\[ |e_{n+1}|\approx C|e_n|^2, \]what type of convergence is this?
Practice 8: Roundoff or Truncation?
Stopping an infinite iterative process after \(20\) steps introduces which type of error?
Practice 9: Verification
A solver returns
\[ x\approx0.739085 \]for
\[ x=\cos x. \]Write one residual expression that should be checked.
Practice 10: Reporting Precision
If an approximation is known only to have absolute error less than
\[ 0.01, \]should twelve decimal places be reported as meaningful?
Practice Answers
Practice 1
\[ |4.98-5| = \boxed{0.02}. \]Practice 2
\[ \frac{0.02}{5} = \boxed{0.004}. \]Practice 3
\[ 0.004\times100\% = \boxed{0.4\%}. \]Practice 4
The interval width is
\[ 2.66-2.64=0.02. \]The midpoint error is at most half the width:
\[ \boxed{0.01}. \]Practice 5
\[ f(2.646) = 2.646^2-7. \] \[ = 7.001316-7. \] \[ \boxed{f(2.646)=0.001316}. \]Practice 6
No.
The successive difference measures the latest step, not necessarily the true error.
Additional information about the method is required to convert that step size into a guaranteed root-error bound.
Practice 7
This is
\[ \boxed{\text{quadratic convergence}}. \]Practice 8
Ending an infinite mathematical process after finitely many steps produces
\[ \boxed{\text{truncation error}}. \]Practice 9
Rewrite the equation as
\[ f(x)=\cos x-x. \]Then check
\[ \boxed{\cos(0.739085)-0.739085}. \]Practice 10
No.
An error bound of \(0.01\) supports only limited precision. Reporting twelve decimal places would imply unsupported accuracy.
What to Remember
- Convergence means a sequence of approximations approaches a limiting value.
- Absolute error is \(|x-r|\), while relative error scales by the magnitude of the true value.
- A residual \(f(x)\) measures equation satisfaction, not necessarily root error.
- An error bound gives guaranteed information about the unknown true error.
- Tolerance is a chosen requirement, not the same thing as actual error.
- Successive differences, residuals, and interval widths are different stopping measures.
- Truncation error and roundoff error have different sources.
- Conditioning belongs to the problem; stability belongs to the algorithm.
- Verification should use residuals, bounds, domain checks, and independent evidence when possible.
- Report only the precision justified by the numerical evidence.
Where We Go Next
This lesson completes the Numerical and Algorithmic Methods section. Numerical tables, iterative rules, bracketing, bisection, fixed-point iteration, Newton's method, secant methods, system solvers, polynomial algorithms, computational tools, and pseudocode all depend on the same deeper discipline: approximate deliberately, measure uncertainty, and verify the result.
These ideas will reappear throughout later mathematics whenever exact symbolic answers give way to approximation, computation, modeling, optimization, simulation, or numerical analysis.