Learn about numerical integration

[damianjilk2]

Review research articles and books to get a better understanding of different applications of common numerical integration tools.

[damianjilk2]

Finished reading through Numerical Methods by Robert Hornbeck.

Synopsis of chapter 8:

• Numerical integration (a.k.a. numerical quadrature) is used to approximate the definite integral when an analytical solution is difficult or impossible to obtain.
• Common techniques include Trapezoidal Rule, Simpson's Rule, and Gaussian Quadrature.

  • Trapezoidal Rule: a simple method that provides a good approximation for many functions.

    • 
    • good for rough estimates or when the function is nearly linear over small intervals

  • Simpson's Rule: uses parabolic segments instead of linear ones to approximate the area

    • 
    • suitable for smooth, well-behaved functions over small to medium intervals

  • Gaussian Quadrature: uses specially chosen sample points and weights.

    • where w_i are weights and x_i are sample points.
    • ideal for high-precision integration, especially when dealing with polynomials

• Error analysis is particularly important when considering numerical integration. The rate of convergence differs drastically between methods so it is important to understand which quadrature would be most appropriate in each scenario.
• Adaptive quadrature methods adjust the number of subdivisions dynamically based on the function's behavior. They can refine the partitioning where the function changes rapidly and coarsen it when the function is smooth.
• The best method for dealing with singularities is to eliminate them if possible. However, if this proves to be impossible, the book claims that the Gauss quadrature approach if used with care can yield quite accurate results in most cases. Note: it will not work if the function is oscillatory in the region considered.

[damianjilk2]

Introduction to Numerical Analysis by F.B. Hildebrand (second edition):

Error analysis can be quite complicated. There are many considerations to make when rounding an infinite sig fig number and depending on your tolerance, your approximation might be significantly hindered by this rounding.

Chapter 4: Finite-difference Interpolation Finite-difference interpolation is used to estimate values of a function at points where it is not explicitly known. It leverages known values of a function at discrete points to construct an interpolating polynomial.

Forward difference -- Del f(x_i) = f(x_i+1) - f(x_i) Backward difference -- nabla f(x_i) = f(x_i) - f(x_i-1) Central difference -- del f(x_i) = 1/2 * (f(x_i+1) - f(x_i-1))

Special formulas like Stirling's, Bessel's, and Everett's are used for more efficient computation and/or higher accuracy.

The technique used should be based on the data distribution and desired accuracy. Precomputed tables enhance efficiency and reduce error.

Chapter 5: Operations with Finite Differences Euler-Maclaurin Sum Formula connects summation and integration. There are many variations of this and can lead to simplifications such as the trapezoidal rule and the repeated midpoint rule.

Chapter 6: Numerical Solution of Differential Equations Open-type -- domain extends beyond the range of the data Closed-type -- data points at the beginning and end of the limits of integration are known

Simplest procedure is Euler's method: y_n+1 = y_n + h*f(x_n,y_n) More complicated equations such as the Adams-Bashforth method where several levels of differences are calculated and considered when computing the value in question.

Runge-Kutta method. There are variations such as order 2 and order 4. Here is one variation of this formula and performs far better than Euler's method for complicated functions.

Chapter 8: Gaussian Quadrature and Related Topics Gaussian quadrature is a numerical method for approximating integrals using weighted sums at specific points (abscissas). Hermite interpolation -- polynomial interpolation that includes both function values and derivate values at selected points. Legendre-Gauss quadrature - a type of Gaussian quadrature using Legendre polynomials as basis functions. Laguerre-Gauss quadrature - uses Laguerre polynomials and their roots. Effective for integrals involving exponential weight functions. Hermite-Gauss quadrature - Hermite polynomials and their roots with Gaussian weight functions.

Formulas with preassigned abscissas:

• Radau quadrature -- uses one endpoint of the integration interval as an abscissa.
• Lobatto quadrature -- uses both endpoints of the integration interval as abscissas.

[damianjilk2]

An Introduction to Numerical Analysis by Endre Süli and David Mayers:

Chapter 2: Solution of Systems of Linear Equations

• Gaussian elimination is a systematic method for solving linear systems.
• LU factorization decomposes a matrix A into a product of a lower triangle matrix L and an upper triangle matrix U. A = LU.
• Pivoting: swapping rows and columns.
• A matrix is considered ill-conditioned if small changes in the input (such as errors in data) can cause large changes in the output. This is measured using the condition number (kappa) of the matrix. The Hilbert Matrix is a classic example of an ill-conditioned matrix.

Chapter 7 and 10: Numerical Integration

• Newton-Cotes formulas are a group of methods for numerical integration based on evaluating the integrand at equally spaced points. The most common forms are Trapezoidal rule (trapezoid) and Simpson's rule (parabolas).
• The estimated error of these methods can be computed (Theorem 7.1). Error values are calculated for E1 (trapezium rule) and E2 (Simpson's rule).
• Composite numerical integration methods apply formulas like trapezoidal or Simpson's rule to subintervals of the integration range and sum the results. The associated error estimates are also solved.
• Euler-Maclaurin expansion -- connection between integrals and sums. Used to derive error estimates and improve accuracy of numerical integration methods.
• Richardson extrapolation improves the accuracy of an approximation by using two approximations with different step sizes. The idea is to combine these approximations in a way that cancels out the leading error term.
• Romberg integration method - applies Richardson extrapolation to the trapezoidal rule. During the construction of this integral, a Romberg table is created and is generally iterated until a certain tolerance is reached.
• Gauss quadrature (use quadrature weights and points in a way that the highest possible degree of accuracy is achieved for specific degrees of polynomials -- degree 2n+1 presented in book but specific degree depends on definitions); composite Gauss; error approximation
• Radau quadrature - one endpoints of the interval is included as a node
• Lobatto quadrature - both endpoints of the interval are included as nodes

Chapter 12 and 13: Initial Value problems and Boundary Value Problems for ODEs

• Euler's Method: y_(n+1) = y_n + h*f(x_n, y_n)
• Implicit Euler method: y_(n+1) = y_n = f*f(x_n+1, y_n+1)
• Stiff systems are characterized by having widely varying timescales, requiring methods that remain stable for larger step sizes. Implicit methods are typically preferred for stiff systems.
• The shooting method: converts a BVP (boundary value problem) into an IVP (initial value problem) by guessing the initial conditions and solving the resulting IVP, then iterating.

Chapter 14: The Finite Element Method

• numerical technique for solving partial differential equations and integral equations.
• Steps: discretize the domain; select basis functions; variational formulation (transform original PDE into an integral form); assemble system of equations; apply boundary conditions; solve

[damianjilk2]

Numerical Linear Algebra by Lloyd N. Trefethen and David Bau III:

Part 2: QR Factorization and Least Squares

• a projector is an operator that maps a vector space onto a subspace
• QR factorization decomposes a matrix A into an orthogonal matrix Q and an upper triangular matrix R:

  • A = QR
  • Q is an orthogonal matrix: Q^T * Q = I

• Gram-Schmidt Orthogonalization steps:

  1. start with a set of linearly independent vectors {a1, a2, ... , an}
  2. generate orthogonal vectors {q1, q2, ... , qn} such that each qi is orthogonal to the previous vectors
  3. normalize qi to get an orthonormal set

• Modified Gram-Schmidt: more numerically stable
• Householder Triangularization: an efficient method for QR factorization using Householder reflections

Part 3: Conditioning and Stability

• Conditioning refers to the sensitivity of the solution of a problem to changes in the input data.
• Condition number (kappa) for a matrix A: kappa(A) = ||A|| ||A^-1||
• Error types:

  • round-off errors: due to finite precision
  • truncation errors: due to approximations in numerical methods

• Stability: a stable algorithm gives nearly the right answer to nearly the right question.
• A backward stable algorithm gives exactly the right answer to nearly the right question.

Part 4: Systems of Equations

• Gaussian Elimination: fundamental algorithm for solving linear systems of equations. Involves three main steps: forward elimination, back substitution, and row operations to reduce a matrix to upper triangular form.
• Pivoting: swapping rows and/or columns to improve numerical stability and accuracy in Gaussian elimination
• Cholesky Factorization: specialized factorization for symmetric, positive-definite matrices. More efficient and numerically stable compared to general LU factorization for this type of matrices.

Part 6: Iterative Methods

• Arnoldi Iteration is used to find a few eigenvalues and eigenvectors of large sparse matrices. The process involves orthogonalized A*vi against the previous basis vectors using the Gram-Schmidt process.
• Generalized Minimal Residuals (GMRES) is an iterative method for solving nonsymmetric linear systems.
• Lanczos Iteration is similar to Arnoldi or GMRES but is specialized for symmetric matrices.
• Lanczos process can be used to approximate integrals and eigenvalues.
• Conjugate Gradients: an efficient iterative method for solving symmetric positive-definite systems.
• Preconditioning transforms the original system into one that is easier to solve iteratively. A preconditioner M approximates A but is easier to invert.