Study guide
13.3 Numerical Analysis: Error, Root Finding, Interpolation, and Quadrature
GRE Subject Test: Mathematics Exam
Track your progress as you read
Finished sections get a check mark.
1 Chapter 1: Single-Variable Differential Calculus
1.1 Limits, Continuity, and Epsilon-Delta Definitions 1.2 Differentiation Rules, Implicit & Inverse Differentiation 1.3 Mean Value Theorem, Rolle's Theorem, and Function Extrema 1.4 L'Hôpital's Rule, Curve Sketching, and Optimization 1.5 Functions, Graphs, Transformations, and Inverses 1.6 Trigonometric Functions, Identities, and Equations 1.7 Coordinate Geometry, Lines, Circles, and Conics 1.8 Parametric and Polar Curves
2 Chapter 2: Single-Variable Integral Calculus
2.1 Riemann Sums and the Fundamental Theorem of Calculus 2.2 Advanced Integration Techniques 2.3 Geometric Applications: Areas, Volumes, and Arc Length 2.4 Improper Integrals and Convergence Criteria
3 Chapter 3: Sequences, Infinite Series & Power Series
3.1 Sequences, Monotonicity, and Limits 3.2 Infinite Series and Convergence Tests 3.3 Power Series, Radius and Interval of Convergence 3.4 Taylor and Maclaurin Series with Error Bounds
4 Chapter 4: Multivariable Differential Calculus
4.1 Multivariable Functions, Limits, and Partial Derivatives 4.2 Directional Derivatives, Gradients, and Tangent Planes 4.3 Multivariable Chain Rule and Implicit Differentiation 4.4 Multivariable Extrema, Hessian Matrix, and Lagrange Multipliers
5 Chapter 5: Multivariable Integration & Vector Calculus
5.1 Multiple Integrals in Cylindrical and Spherical Coordinates 5.2 Change of Variables and the Jacobian Determinant 5.3 Vector Fields, Line Integrals, and Green's Theorem 5.4 Surface Integrals, Stokes' Theorem, and the Divergence Theorem
6 Chapter 6: Ordinary Differential Equations
6.1 First-Order ODEs: Separable, Linear, and Exact Equations 6.2 Special First-Order ODEs: Homogeneous, Bernoulli, and Orthogonal Trajectories 6.3 Second-Order Linear Homogeneous ODEs with Constant Coefficients 6.4 Nonhomogeneous Linear ODEs: Undetermined Coefficients and Variation of Parameters
7 Chapter 7: Elementary Algebra & Number Theory
7.1 Elementary Algebra, Polynomials, Roots, and Factorization 7.2 Divisibility, Primes, and the Euclidean Algorithm 7.3 Modular Arithmetic, Chinese Remainder Theorem, and Euler's Totient
8 Chapter 8: Linear Algebra: Vector Spaces & Transformations
8.1 Vector Spaces, Subspaces, Span, and Linear Independence 8.2 Basis, Dimension, and Coordinate Representations 8.3 Linear Transformations, Kernel, Range, and the Rank-Nullity Theorem 8.4 Matrix Representations of Transformations and Change of Basis
9 Chapter 9: Linear Algebra: Matrices, Determinants & Spectral Theory
9.1 Systems of Linear Equations, Matrix Rank, and Row Reduction 9.2 Determinants, Matrix Inverses, and Cramer's Rule 9.3 Eigenvalues, Eigenvectors, and Diagonalization 9.4 Inner Product Spaces, Gram-Schmidt, and the Spectral Theorem
10 Chapter 10: Abstract Algebra: Groups, Rings & Fields
10.1 Groups, Subgroups, and Permutations 10.2 Cosets, Lagrange's Theorem, Normal Subgroups, and Homomorphisms 10.3 Rings, Ideals, Modules, Polynomial Rings, and Fields
11 Chapter 11: Introductory Real Analysis
11.1 The Real Field and Metric Space Topology 11.2 Compactness, Completeness, and Connectedness in R^n 11.3 Continuity, Uniform Continuity, and Value Theorems 11.4 Sequences and Series of Functions: Pointwise and Uniform Convergence
12 Chapter 12: Complex Analysis
12.1 Complex Numbers and Analytic Functions 12.2 Contour Integration and Cauchy's Theorems 12.3 Laurent Series, Singularities, and the Residue Theorem
13 Chapter 13: Topology, Geometry & Numerical Analysis
13.1 Topological Spaces, Open/Closed Sets, and Bases 13.2 Euclidean Geometry, Similarity, Circles, and Transformations 13.3 Numerical Analysis: Error, Root Finding, Interpolation, and Quadrature
14 Chapter 14: Probability, Statistics & Discrete Mathematics
14.1 Logic, Set Theory, Algorithms, and Combinatorics 14.2 Graph Theory: Trees, Cycles, Paths, and Planarity 14.3 Probability Spaces, Conditional Probability, and Bayes' Theorem 14.4 Random Variables, Expected Value, Variance, and Common Distributions
13.3 Numerical Analysis: Error, Root Finding, Interpolation, and Quadrature
Key Takeaways Explain This Topic AI
Absolute error measures |x - x-hat|, relative error divides by a nonzero reference magnitude, and conditioning describes how input error is amplified by the mathematical problem.
Bisection is slow but guaranteed for a continuous sign-changing bracket; Newton's method is usually fast near a simple root but requires derivative and convergence checks.
A unique polynomial of degree at most n interpolates n+1 distinct data points, but high-degree interpolation and clustered nodes can amplify error.
Composite trapezoidal and Simpson rules trade function evaluations for predictable error orders; Simpson's rule requires an even number of equal subintervals.
Last updated: September 2026
13.3 Numerical Analysis: Error, Root Finding, Interpolation, and Quadrature
Numerical analysis replaces an exact symbolic answer with a controlled approximation. A complete numerical result includes a method, a stopping rule, and an error statement.
Error, stability, and conditioning
If x x x is exact and x ^ \hat x x ^ is approximate, absolute error is ∣ x − x ^ ∣ |x-\hat x| ∣ x − x ^ ∣ and relative error is ∣ x − x ^ ∣ / ∣ x ∣ |x-\hat x|/|x| ∣ x − x ^ ∣/∣ x ∣ when x ≠ 0 x\ne0 x = 0 . Decimal rounding to p p p places produces absolute error at most half a unit in the last retained place.
Conditioning belongs to the problem: it measures how sensitively the exact output responds to small input changes. For differentiable f f f , a local relative condition number is approximately κ f ( x ) = ∣ x f ′ ( x ) f ( x ) ∣ . \kappa_f(x)=\left|\frac{x f'(x)}{f(x)}\right|. κ f ( x ) = f ( x ) x f ′ ( x ) .
Stability belongs to an algorithm: a stable method does not introduce much more error than the underlying data uncertainty. Subtracting nearly equal floating-point numbers can cause catastrophic cancellation because leading significant digits disappear.
Bracketing and root-finding methods
If f f f is continuous on [ a , b ] [a,b] [ a , b ] and f ( a ) f ( b ) < 0 f(a)f(b)<0 f ( a ) f ( b ) < 0 , the Intermediate Value Theorem guarantees a root in ( a , b ) (a,b) ( a , b ) . Bisection replaces the endpoint having the same sign as midpoint m = ( a + b ) / 2 m=(a+b)/2 m = ( a + b ) /2 . After n n n bisections, the bracket width is ( b − a ) / 2 n (b-a)/2^n ( b − a ) / 2 n , and the midpoint error is at most ( b − a ) / 2 n + 1 (b-a)/2^{n+1} ( b − a ) / 2 n + 1 . Bisection converges linearly but cannot lose a valid sign-changing bracket.
Newton's method uses the tangent-line approximation: x n + 1 = x n − f ( x n ) f ′ ( x n ) . x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}. x n + 1 = x n − f ′ ( x n ) f ( x n ) .
Near a simple root and under standard smoothness assumptions, convergence is quadratic: roughly speaking, the number of correct digits doubles. It can fail when f ′ ( x n ) = 0 f'(x_n)=0 f ′ ( x n ) = 0 , when an iterate leaves the useful region, or when the initial guess is poor. For a root of multiplicity m > 1 m>1 m > 1 , ordinary Newton convergence drops to linear; the modified step x n + 1 = x n − m f ( x n ) f ′ ( x n ) x_{n+1}=x_n-m\frac{f(x_n)}{f'(x_n)} x n + 1 = x n − m f ′ ( x n ) f ( x n )
restores quadratic local convergence when m m m is known.
The secant method replaces the derivative by a difference quotient: x n + 1 = x n − f ( x n ) x n − x n − 1 f ( x n ) − f ( x n − 1 ) . x_{n+1}=x_n-f(x_n)\frac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})}. x n + 1 = x n − f ( x n ) f ( x n ) − f ( x n − 1 ) x n − x n − 1 .
It uses no derivative and is typically faster than bisection, but it lacks bisection's bracket guarantee.
Worked root example
To approximate 2 \sqrt2 2 , apply Newton to f ( x ) = x 2 − 2 f(x)=x^2-2 f ( x ) = x 2 − 2 : x n + 1 = 1 2 ( x n + 2 x n ) . x_{n+1}=\frac12\left(x_n+\frac{2}{x_n}\right). x n + 1 = 2 1 ( x n + x n 2 ) .
Starting with x 0 = 1.5 x_0=1.5 x 0 = 1.5 gives x 1 = 17 / 12 ≈ 1.416667 x_1=17/12\approx1.416667 x 1 = 17/12 ≈ 1.416667 and x 2 ≈ 1.414216 x_2\approx1.414216 x 2 ≈ 1.414216 , already accurate to about five decimal places.
Polynomial interpolation and finite differences
Given distinct nodes x 0 , … , x n x_0,\ldots,x_n x 0 , … , x n and values y i y_i y i , there is a unique polynomial of degree at most n n n satisfying p ( x i ) = y i p(x_i)=y_i p ( x i ) = y i . Lagrange form is p ( x ) = ∑ i = 0 n y i L i ( x ) , L i ( x ) = ∏ j ≠ i x − x j x i − x j . p(x)=\sum_{i=0}^n y_i L_i(x),\qquad
L_i(x)=\prod_{j\ne i}\frac{x-x_j}{x_i-x_j}. p ( x ) = i = 0 ∑ n y i L i ( x ) , L i ( x ) = j = i ∏ x i − x j x − x j .
If f f f has n + 1 n+1 n + 1 derivatives, interpolation error is f ( x ) − p ( x ) = f ( n + 1 ) ( ξ ) ( n + 1 ) ! ∏ i = 0 n ( x − x i ) f(x)-p(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}\prod_{i=0}^n(x-x_i) f ( x ) − p ( x ) = ( n + 1 )! f ( n + 1 ) ( ξ ) i = 0 ∏ n ( x − x i )
for some ξ \xi ξ in the interval containing the nodes and x x x .
For equally spaced nodes with spacing h h h , forward difference f ′ ( x ) ≈ f ( x + h ) − f ( x ) h f'(x)\approx\frac{f(x+h)-f(x)}{h} f ′ ( x ) ≈ h f ( x + h ) − f ( x )
has first-order truncation error, while the centered difference f ′ ( x ) ≈ f ( x + h ) − f ( x − h ) 2 h f'(x)\approx\frac{f(x+h)-f(x-h)}{2h} f ′ ( x ) ≈ 2 h f ( x + h ) − f ( x − h )
has second-order truncation error. Making h h h extremely small is not always better: rounding and cancellation eventually dominate truncation error.
Numerical quadrature
For n n n equal subintervals of width h = ( b − a ) / n h=(b-a)/n h = ( b − a ) / n , the composite trapezoidal rule is T n = h [ f ( a ) + f ( b ) 2 + ∑ i = 1 n − 1 f ( a + i h ) ] . T_n=h\left[\frac{f(a)+f(b)}2+\sum_{i=1}^{n-1}f(a+ih)\right]. T n = h [ 2 f ( a ) + f ( b ) + i = 1 ∑ n − 1 f ( a + ih ) ] .
For twice continuously differentiable f f f , its global error is order h 2 h^2 h 2 .
Composite Simpson's rule requires even n n n : S n = h 3 [ f ( x 0 ) + f ( x n ) + 4 ∑ i odd f ( x i ) + 2 ∑ i even , 0 < i < n f ( x i ) ] . S_n=\frac h3\left[f(x_0)+f(x_n)+4\sum_{i\text{ odd}}f(x_i)+2\sum_{i\text{ even},\,0<i<n}f(x_i)\right]. S n = 3 h [ f ( x 0 ) + f ( x n ) + 4 i odd ∑ f ( x i ) + 2 i even , 0 < i < n ∑ f ( x i ) ] .
For four-times continuously differentiable f f f , its global error is order h 4 h^4 h 4 . Simpson's rule is exact for every polynomial of degree at most 3; the trapezoidal rule is exact for every polynomial of degree at most 1.
Worked quadrature example
Approximate ∫ 0 2 x 2 d x \int_0^2 x^2\,dx ∫ 0 2 x 2 d x using Simpson's rule with n = 2 n=2 n = 2 , so h = 1 h=1 h = 1 : S 2 = 1 3 [ f ( 0 ) + 4 f ( 1 ) + f ( 2 ) ] = 1 3 ( 0 + 4 + 4 ) = 8 3 . S_2=\frac13[f(0)+4f(1)+f(2)]
=\frac13(0+4+4)=\frac83. S 2 = 3 1 [ f ( 0 ) + 4 f ( 1 ) + f ( 2 )] = 3 1 ( 0 + 4 + 4 ) = 3 8 .
This equals the exact integral because x 2 x^2 x 2 has degree below 4.
Common traps
A small residual ∣ f ( x ^ ) ∣ |f(\hat x)| ∣ f ( x ^ ) ∣ does not always mean a small root error when the problem is ill-conditioned. Newton's formula is undefined at a zero derivative and is not globally guaranteed. Interpolation nodes must be distinct. Composite Simpson's rule needs equal spacing and even n n n . Finally, reducing a step size lowers truncation error only until floating-point rounding begins to dominate.