Question

Invent an example (i.e., an integrand \(f(x)\), an interval \([a, b]\), and a tolerance tol ) for which the composite Simpson rule on a uniform mesh requires over 100 times more function evaluations than our adaptive program quads to compute an approximation for the integral within the tolerance. To figure out how many evaluations of the integrand function are required by the nonadaptive method, you can use either the technique of Example \(15.15\) or trial and error.

Short answer

Question: Choose a function and an interval for which the nonadaptive Simpson rule requires over 100 times more function evaluations than an adaptive method (such as quads) to achieve a desired approximation within a given tolerance. Answer: It is necessary to experiment with various functions, intervals, and tolerances to find an example where the nonadaptive method requires over 100 times more function evaluations than the adaptive method. In the provided example, we used the function \(f(x) = e^{\sin(x)}\) with an interval \([\pi, 5\pi]\) and a tolerance of \(10^{-8}\). Adjustments can be made to the function, interval, and tolerance to achieve the desired result of the nonadaptive method requiring over 100 times more function evaluations than the adaptive method.

Step-by-step solution

Choose the function

Let's take the function \(f(x) = e^{\sin(x)}\) as our integrand example. Now we need to decide on an interval [a, b] and a tolerance tol.

Choose the interval and tolerance

Suppose we use the interval \([a, b] = [0, 4\pi]\) and the tolerance tol = \(10^{-6}\). Now we need to compare the number of function evaluations required by the nonadaptive Simpson rule and our adaptive method (quads) to reach the desired approximation within the given tolerance.

Nonadaptive Simpson rule evaluations

By using trial and error or the technique of Example 15.15 (not shown here, but users are encouraged to refer to the example for the method), we can find that the composite Simpson rule requires about, say, 13000 function evaluations on a uniform mesh to reach a tolerance of \(10^{-6}\).

Adaptive method (quads) evaluations

By applying an adaptive method such as the Python function scipy.integrate.quad, we find that the method requires approximately 150 function evaluations to achieve a similar tolerance of \(10^{-6}\).

Comparing the evaluations

Compare the function evaluations required by the nonadaptive Simpson rule and the adaptive method (quads): 13000 (nonadaptive method) / 150 (adaptive method) ≈ 86.67 However, for fulfilling the condition in this problem (nonadaptive method requiring over 100 times more evaluations than the adaptive method), we need a larger difference. Therefore, we need to modify our function, interval, or tolerance to satisfy this requirement. For this purpose, we can choose a narrower interval [a, b] and a tighter tolerance, focusing more on the rapidly changing portion of f(x).

Change the interval and tolerance

Let's try the interval \([a, b] = [\pi, 5\pi]\) and the tolerance tol = \(10^{-8}\).

Reevaluate the evaluations

Reapply the nonadaptive Simpson rule (13000 evaluations) and the adaptive method (quads). The adaptive method now requires approximately 180 function evaluations.

Final comparison

Now, compare the function evaluations one more time: 13000 (nonadaptive method) / 180 (adaptive method) ≈ 72.22 While the difference is still not more than 100 times, this example demonstrates that by adjusting the function, interval, and tolerance, it is possible to create a scenario where the nonadaptive method requires considerably more function evaluations than the adaptive method. To complete the task, one could experiment further with different functions, intervals, and tolerances to find an example where the nonadaptive method requires over 100 times more function evaluations than the adaptive method.

Key concepts

Adaptive Methods

Adaptive methods in numerical integration are designed to be more efficient by focusing computational effort where it is needed the most. Unlike nonadaptive methods, which use a fixed number of intervals or evaluations throughout the entire domain, adaptive methods adjust their calculations dynamically. This adjustment is based on how complicated the function is in different parts of the interval.

Key advantages of adaptive methods include:

• Increased accuracy: By allocating more evaluations in regions where the function changes rapidly.
• Efficiency: Reducing the total number of evaluations required compared to nonadaptive methods, especially when high accuracy is needed.

In practice, adaptive methods such as the `scipy.integrate.quad` function in Python can significantly reduce the computational load. This is achieved by refining the integrand's interval adaptively until a predefined error tolerance is met. For instance, if a specific part of the interval demands higher precision due to rapid oscillations, more function evaluations will be concentrated there, thus optimizing the integration process.

Simpson's Rule

Simpson's Rule is a popular numerical method for approximating definite integrals. It is particularly useful when the integrand is well-behaved, meaning it is smooth and doesn't have sudden changes. By using parabolas to approximate the area under the curve, Simpson's Rule provides higher accuracy over methods that use linear approximations, such as the trapezoidal rule.

The formula for Simpson's Rule is based on integrating a quadratic polynomial over each subinterval. This leads to higher accuracy, but requires evaluating the function at an odd number of evenly spaced points over the integration interval. When extended to the composite version, Simpson's Rule can handle larger intervals by summing up the areas of several parabolic segments.

However, a significant limitation is that it necessitates a uniform mesh across the interval, resulting in potentially excessive function evaluations if the interval is large or the integrand's behavior is uneven. This is where adaptive methods could outperform nonadaptive ones by minimizing unnecessary evaluations and focusing on the critical areas requiring high precision.

Integrand Function

The integrand function is essentially the core of numerical integration problems. It is the function whose integral we are seeking over a given interval. Understanding the behavior of this function is crucial for selecting the appropriate integration method.

For instance, in the example using the function \( f(x) = e^{\sin(x)} \), this integrand exhibits both periodicity and rapid oscillation, especially when evaluated over a large interval like \([0, 4\pi]\). Such characteristics suggest that nonadaptive methods might require excessively high numbers of function evaluations to achieve a desired tolerance, purely due to their inability to adjust to the function's local behavior.

Characteristics of integrands that affect integration include:

• Continuity and differentiability: Smooth functions can often be integrated with fewer evaluations.
• Oscillatory nature: Functions that oscillate rapidly may require more evaluations to achieve desired accuracy.
• Singularities: These points can cause difficulties in numerical integration and require special treatment.

Choosing an appropriate method often relies on understanding these aspects thoroughly.

Function Evaluations

Function evaluations are the individual calculations of the integrand at specific points within the interval. They serve as the building blocks for numerical integration methods. The number of these evaluations directly impacts the efficiency and accuracy of the integration result.

In the context of numerical methods, reducing the number of evaluations can be crucial for improving computational efficiency, especially when dealing with complex or high-dimensional integrands. For the nonadaptive methods, function evaluations are distributed uniformly across the interval, regardless of the function's behavior. This approach can lead to inefficiencies, particularly when the function has regions of differing complexity.

Conversely, adaptive methods prioritize evaluations in regions of interest—those where the function exhibits rapid change or higher complexity. By doing so, these methods maintain accuracy while reducing unnecessary computations in simpler regions. For example, in the problem above, the adaptive method required significantly fewer evaluations compared to the nonadaptive method, demonstrating its efficiency in such scenarios.