Editing Numerical integration (section)

===Quadrature rules based on interpolating functions===
A large class of quadrature rules can be derived by constructing [[interpolation|interpolating]] functions that are easy to integrate. Typically these interpolating functions are [[polynomial]]s.  In practice, since polynomials of very high degree tend to [[Runge's phenomenon|oscillate wildly]], only polynomials of low degree are used, typically linear and quadratic.

[[Image:Integration trapezoid.svg|right|thumb|300px|Illustration of the trapezoidal rule.]]
The interpolating function may be a straight line (an [[affine function]], i.e. a polynomial of degree 1)
passing through the points <math> \left( a, f(a)\right) </math> and <math> \left( b, f(b)\right) </math>.
This is called the ''[[trapezoidal rule]]''
<math display="block">\int_a^b f(x)\, dx \approx (b-a) \left(\frac{f(a) + f(b)}{2}\right).</math>

[[Image:Integration simpson.svg|right|thumb|300px|Illustration of Simpson's rule.]]
For either one of these rules, we can make a more accurate approximation by breaking up the interval <math> [a,b] </math> into some number <math> n </math> of subintervals, computing an approximation for each subinterval, then adding up all the results. This is called a ''composite rule'', ''extended rule'', or ''iterated rule''. For example, the composite trapezoidal rule can be stated as
<math display="block">\int_a^b f(x)\, dx \approx 
\frac{b-a}{n} \left( {f(a) \over 2} + \sum_{k=1}^{n-1} \left( f \left( a + k \frac{b-a}{n} \right) \right) + {f(b) \over 2} \right),</math>

where the subintervals have the form <math> [a+k h,a+ (k+1)h] \subset [a,b], </math> with <math display="inline">h = \frac{b - a}{n}</math> and <math>k = 0,\ldots,n-1. </math> Here we used subintervals of the same length <math> h </math> but one could also use intervals of varying length <math> \left( h_k \right)_k </math>.

Interpolation with polynomials evaluated at equally spaced points in <math> [a,b] </math> yields the [[Newton–Cotes formulas]], of which the rectangle rule and the trapezoidal rule are examples. [[Simpson's rule]], which is based on a polynomial of order 2, is also a Newton–Cotes formula.

Quadrature rules with equally spaced points have the very convenient property of ''nesting''.  The corresponding rule with each interval subdivided includes all the current points, so those integrand values can be re-used.

If we allow the intervals between interpolation points to vary, we find another group of quadrature formulas, such as the [[Gaussian quadrature]] formulas. A Gaussian quadrature rule is typically more accurate than a Newton–Cotes rule that uses the same number of function evaluations, if the integrand is [[Smooth function|smooth]] (i.e., if it is sufficiently differentiable). Other quadrature methods with varying intervals include [[Clenshaw–Curtis quadrature]] (also called Fejér quadrature) methods, which do nest.

Gaussian quadrature rules do not nest, but the related [[Gauss–Kronrod quadrature formula]]s do.