Numerical Analysis I Unit 12 ReviewComposite Trapezoidal & Simpson's Rules

Key Concepts

• Numerical integration approximates definite integrals when analytical solutions are difficult or impossible to obtain
• Trapezoidal Rule uses trapezoids to approximate the area under a curve by connecting points with straight lines
• Simpson's Rule uses quadratic polynomials to approximate the area under a curve, providing higher accuracy than the Trapezoidal Rule
• Composite methods divide the integration interval into smaller subintervals, applying the Trapezoidal or Simpson's Rule to each subinterval and summing the results
  • Composite Trapezoidal Rule: $\int_a^b f(x) dx \approx \frac{h}{2} [f(x_0) + 2f(x_1) + 2f(x_2) + ... + 2f(x_{n-1}) + f(x_n)]$, where $h = \frac{b-a}{n}$ and $x_i = a + ih$
  • Composite Simpson's Rule: $\int_a^b f(x) dx \approx \frac{h}{3} [f(x_0) + 4f(x_1) + 2f(x_2) + 4f(x_3) + ... + 2f(x_{n-2}) + 4f(x_{n-1}) + f(x_n)]$, where $h = \frac{b-a}{n}$ and $x_i = a + ih$
• Error analysis helps determine the accuracy of numerical integration methods and guides the selection of appropriate step sizes
• Practical applications of numerical integration include computing areas, volumes, and solving differential equations in various fields such as physics, engineering, and economics

Historical Context

• Numerical integration methods have been developed and refined over centuries to solve problems in mathematics, science, and engineering
• Ancient Babylonians and Egyptians used early forms of numerical integration to calculate areas and volumes for practical purposes (land surveying, construction)
• Archimedes (287-212 BC) developed the method of exhaustion, an early precursor to modern numerical integration techniques
  • He used inscribed and circumscribed polygons to approximate the area of a circle and the volume of a sphere
• Isaac Newton (1643-1727) and Gottfried Leibniz (1646-1716) independently developed the fundamental theorem of calculus, laying the groundwork for modern integration techniques
• In the 19th century, mathematicians such as Carl Friedrich Gauss (1777-1855) and Augustin-Louis Cauchy (1789-1857) made significant contributions to the development of numerical integration methods
• With the advent of computers in the 20th century, numerical integration became an essential tool for solving complex problems in various fields, leading to the development of more advanced and efficient algorithms

Trapezoidal Rule Explained

• The Trapezoidal Rule is a numerical integration method that approximates the area under a curve by dividing it into trapezoids
• To apply the Trapezoidal Rule, the integration interval $[a, b]$ is divided into $n$ equal subintervals of width $h = \frac{b-a}{n}$
• The function $f(x)$ is evaluated at the endpoints of each subinterval, denoted as $x_0, x_1, ..., x_n$, where $x_i = a + ih$
• The area of each trapezoid is calculated using the formula: $A_i = \frac{h}{2}[f(x_i) + f(x_{i+1})]$
• The Trapezoidal Rule approximates the definite integral by summing the areas of all trapezoids: $\int_a^b f(x) dx \approx \sum_{i=0}^{n-1} A_i = \frac{h}{2} [f(x_0) + 2f(x_1) + 2f(x_2) + ... + 2f(x_{n-1}) + f(x_n)]$
• The error in the Trapezoidal Rule is proportional to the square of the step size $h$, meaning that halving the step size reduces the error by a factor of 4
  • The error term for the Trapezoidal Rule is given by: $E_T = -\frac{(b-a)h^2}{12}f''(\xi)$, where $\xi$ is some value in the interval $[a, b]$

Simpson's Rule Breakdown

• Simpson's Rule is a numerical integration method that approximates the area under a curve using quadratic polynomials
• The integration interval $[a, b]$ is divided into an even number of subintervals $n$ (where $n$ is a multiple of 2) with a step size of $h = \frac{b-a}{n}$
• The function $f(x)$ is evaluated at the endpoints and midpoints of each subinterval, denoted as $x_0, x_1, ..., x_n$, where $x_i = a + ih$
• Simpson's Rule approximates the definite integral by summing the weighted function values: $\int_a^b f(x) dx \approx \frac{h}{3} [f(x_0) + 4f(x_1) + 2f(x_2) + 4f(x_3) + ... + 2f(x_{n-2}) + 4f(x_{n-1}) + f(x_n)]$
  • The weights alternate between 4 and 2 for the interior points, with the endpoints having a weight of 1
• Simpson's Rule is derived by fitting a quadratic polynomial through three consecutive points and integrating the polynomial over the subinterval
• The error in Simpson's Rule is proportional to the fourth power of the step size $h$, meaning that halving the step size reduces the error by a factor of 16
  • The error term for Simpson's Rule is given by: $E_S = -\frac{(b-a)h^4}{180}f^{(4)}(\xi)$, where $\xi$ is some value in the interval $[a, b]$
• Simpson's 3/8 Rule is a variant that uses cubic polynomials and requires the number of subintervals to be a multiple of 3

Composite Methods

• Composite methods involve dividing the integration interval into smaller subintervals and applying the Trapezoidal Rule or Simpson's Rule to each subinterval
• The Composite Trapezoidal Rule divides the interval $[a, b]$ into $n$ equal subintervals of width $h = \frac{b-a}{n}$ and applies the Trapezoidal Rule to each subinterval
  • The approximation is given by: $\int_a^b f(x) dx \approx \frac{h}{2} [f(x_0) + 2f(x_1) + 2f(x_2) + ... + 2f(x_{n-1}) + f(x_n)]$, where $x_i = a + ih$
• The Composite Simpson's Rule divides the interval $[a, b]$ into an even number of subintervals $n$ (where $n$ is a multiple of 2) with a step size of $h = \frac{b-a}{n}$ and applies Simpson's Rule to each pair of subintervals
  • The approximation is given by: $\int_a^b f(x) dx \approx \frac{h}{3} [f(x_0) + 4f(x_1) + 2f(x_2) + 4f(x_3) + ... + 2f(x_{n-2}) + 4f(x_{n-1}) + f(x_n)]$, where $x_i = a + ih$
• Composite methods provide more accurate results than applying the Trapezoidal Rule or Simpson's Rule to the entire interval at once
• The choice between the Composite Trapezoidal Rule and the Composite Simpson's Rule depends on the desired accuracy and the computational cost
  • The Composite Simpson's Rule generally provides higher accuracy but requires more function evaluations

Error Analysis

• Error analysis is crucial for understanding the accuracy of numerical integration methods and determining the appropriate step size
• The error in the Trapezoidal Rule is proportional to the square of the step size $h$, while the error in Simpson's Rule is proportional to the fourth power of $h$
  • Trapezoidal Rule error term: $E_T = -\frac{(b-a)h^2}{12}f''(\xi)$, where $\xi$ is some value in the interval $[a, b]$
  • Simpson's Rule error term: $E_S = -\frac{(b-a)h^4}{180}f^{(4)}(\xi)$, where $\xi$ is some value in the interval $[a, b]$
• The error terms involve higher-order derivatives of the function $f(x)$, which are often difficult to compute or estimate
• In practice, the error is estimated by comparing the results obtained using different step sizes or by using adaptive methods that automatically adjust the step size based on the local error estimate
• Richardson extrapolation is a technique that combines the results of two or more numerical integration methods with different step sizes to obtain a more accurate estimate
  • For example, combining the results of the Trapezoidal Rule with step sizes $h$ and $h/2$ can yield an estimate with an error proportional to $h^4$
• Other error estimation techniques include the Romberg method and the Gauss-Kronrod quadrature, which adaptively refine the subintervals based on error estimates

Practical Applications

• Numerical integration is widely used in various fields to solve problems involving definite integrals that cannot be evaluated analytically
• In physics and engineering, numerical integration is used to compute areas, volumes, moments of inertia, and other physical quantities
  • Example: Calculating the work done by a variable force over a given displacement
• In computational fluid dynamics, numerical integration is used to solve the governing equations for fluid flow, such as the Navier-Stokes equations
• In financial mathematics, numerical integration is used to price options, calculate risk measures, and evaluate portfolio performance
  • Example: Computing the value of a European call option using the Black-Scholes model
• In computer graphics and image processing, numerical integration is used for anti-aliasing, texture mapping, and volume rendering
• In numerical analysis, numerical integration is a fundamental tool for solving ordinary and partial differential equations, which model various physical phenomena
  • Example: Solving the heat equation to model temperature distribution in a material over time
• Numerical integration is also used in data analysis and machine learning for tasks such as probability density estimation and model fitting

Advanced Topics

• Adaptive quadrature methods automatically adjust the step size and the order of the integration method based on local error estimates
  • Examples include the Adaptive Simpson's Rule, Gauss-Kronrod quadrature, and the Clenshaw-Curtis method
• Gaussian quadrature is a family of numerical integration methods that achieve high accuracy by selecting optimal interpolation points and weights
  • Gauss-Legendre quadrature is commonly used and is based on Legendre polynomials
  • Other Gaussian quadrature methods include Gauss-Hermite, Gauss-Laguerre, and Gauss-Chebyshev quadrature
• Multidimensional integration involves evaluating integrals over multiple variables, which is computationally expensive and often requires specialized methods
  • Monte Carlo integration is a stochastic method that estimates multidimensional integrals by randomly sampling points from the integration domain
  • Quasi-Monte Carlo methods use deterministic sequences (low-discrepancy sequences) to improve the convergence rate compared to random sampling
• Singular integrals and improper integrals require special treatment when using numerical integration methods
  • Techniques such as variable transformations, singularity subtraction, and extrapolation can be used to handle these cases
• Parallel and distributed computing techniques can be employed to accelerate numerical integration for large-scale problems or real-time applications
  • Example: Using GPU acceleration to speed up Monte Carlo integration for high-dimensional problems