Thoughts on Numerical Integration (Part 15): Right endpoint rule and global rate of convergence

Numerical integration is a standard topic in first-semester calculus. From time to time, I have received questions from students on various aspects of this topic, including:
  • Why is numerical integration necessary in the first place?
  • Where do these formulas come from (especially Simpson’s Rule)?
  • How can I do all of these formulas quickly?
  • Is there a reason why the Midpoint Rule is better than the Trapezoid Rule?
  • Is there a reason why both the Midpoint Rule and the Trapezoid Rule converge quadratically?
  • Is there a reason why Simpson’s Rule converges like the fourth power of the number of subintervals?
In this series, I hope to answer these questions. While these are standard questions in a introductory college course in numerical analysis, and full and rigorous proofs can be found on Wikipedia and Mathworld, I will approach these questions from the point of view of a bright student who is currently enrolled in calculus and hasn’t yet taken real analysis or numerical analysis.
In the previous post in this series, we found that the local error of the right endpoint approximation to \displaystyle \int_{x_i}^{x_i+h} x^k \, dx was equal to 

\displaystyle \frac{k}{2} x_i^{k-1} h^2 + O(h^3).

We now consider the global error when integrating over the interval [a,b] and not just a particular subinterval.
The total error when approximating \displaystyle \int_a^b x^k \, dx = \int_{x_0}^{x_n} x^k , dx will be the sum of the errors for the integrals over [x_0,x_1], [x_1,x_2], through [x_{n-1},x_n]. Therefore, the total error will be

E \approx \displaystyle \frac{k}{2} \left(x_1^{k-1} + x_2^{k-1} + \dots + x_{n}^{k-1} \right) h^2.

So that this formula doesn’t appear completely mystical, this actually matches the numerical observations that we made earlier. The figure below shows the left-endpoint approximations to \displaystyle \int_1^2 x^9 \, dx for different numbers of subintervals. If we take n = 100 and h = 0.01, then the error should be approximately equal to

\displaystyle \frac{9}{2} \left(1.01^8 + 1.02^8 + \dots + 2^8 \right) (0.01)^2 \approx 2.61276,

which, as expected, is close to the actual error of 104.8741246 - 102.3 \approx 2.57412.
We now perform a more detailed analysis of the global error, which is almost a perfect copy-and-paste from the previous analysis. Let y_i = x_i^{k-1}, so that the error becomes

E \approx \displaystyle \frac{k}{2} \left(y_1 + y_2 + \dots + y_n \right) h^2 + O(h^3) = \displaystyle \frac{k}{2} \overline{y} n h^2,

where \overline{y} = (y_1 + y_2 + \dots + y_{n})/n is the average of the y_i. Clearly, this average is somewhere between the smallest and the largest of the y_i. Since y = x^{k-1} is a continuous function, that means that there must be some value of x_* between x_1 and x_{n} — and therefore between a and b — so that x_*^{k-1} = \overline{y} by the Intermediate Value Theorem. We conclude that the error can be written as

E \approx \displaystyle \frac{k}{2} x_*^{k-1} nh^2,

Finally, since h is the length of one subinterval, we see that nh = b-a is the total length of the interval [a,b]. Therefore,

E \approx \displaystyle \frac{k}{2} x_*^{k-1} (b-a)h \equiv ch,

where the constant c is determined by a, b, and k. In other words, for the special case f(x) = x^k, we have established that the error from the left-endpoint rule is approximately linear in h — without resorting to the generalized mean-value theorem.

Thoughts on Numerical Integration (Part 14): Right endpoint rule and local rate of convergence

Numerical integration is a standard topic in first-semester calculus. From time to time, I have received questions from students on various aspects of this topic, including:

  • Why is numerical integration necessary in the first place?
  • Where do these formulas come from (especially Simpson’s Rule)?
  • How can I do all of these formulas quickly?
  • Is there a reason why the Midpoint Rule is better than the Trapezoid Rule?
  • Is there a reason why both the Midpoint Rule and the Trapezoid Rule converge quadratically?
  • Is there a reason why Simpson’s Rule converges like the fourth power of the number of subintervals?

In this series, I hope to answer these questions. While these are standard questions in a introductory college course in numerical analysis, and full and rigorous proofs can be found on Wikipedia and Mathworld, I will approach these questions from the point of view of a bright student who is currently enrolled in calculus and hasn’t yet taken real analysis or numerical analysis.

In this post, we will perform an error analysis for the right-endpoint rule

\int_a^b f(x) \, dx \approx h \left[f(x_1) + f(x_2) + \dots + f(x_n) \right] \equiv R_n

where n is the number of subintervals and h = (b-a)/n is the width of each subinterval, so that x_k = x_0 + kh.

As noted above, a true exploration of error analysis requires the generalized mean-value theorem, which perhaps a bit much for a talented high school student learning about this technique for the first time. That said, the ideas behind the proof are accessible to high school students, using only ideas from the secondary curriculum, if we restrict our attention to the special case f(x) = x^k, where k \ge 5 is a positive integer.

For this special case, the true area under the curve $f(x) = x^k$ on the subinterval [x_i, x_i +h] will be

\displaystyle \int_{x_i}^{x_i+h} x^k \, dx = \frac{1}{k+1} \left[ (x_i+h)^{k+1} - x_i^{k+1} \right]

= \displaystyle \frac{1}{k+1} \left[x_i^{k+1} + {k+1 \choose 1} x_i^k h + {k+1 \choose 2} x_i^{k-1} h^2 + O(h^3) - x_i^{k+1} \right]

= \displaystyle \frac{1}{k+1} \left[ (k+1) x_i^k h + \frac{(k+1)k}{2} x_i^{k-1} h^2 + O(h^3) \right]

= x_i^k h + \displaystyle \frac{k}{2} x_i^{k-1} h^2 + O(h^3)

In the above, the shorthand O(h^3) can be formally defined, but here we’ll just take it to mean “terms that have a factor of h^3 or higher that we’re too lazy to write out.” Since h is supposed to be a small number, these terms will be much smaller in magnitude that the terms that have h or h^2 and thus can be safely ignored.

Using only the right-endpoint of the subinterval, the left-endpoint approximation of \displaystyle \int_{x_i}^{x_i+h} x^k \, dx is

(x_i+h)^k h = x_i^k h + k x_i^{k-1} h^2 + O(h^3).

Subtracting, the error in this approximation will be equal to

\displaystyle x_i^k h + k x_i^{k-1} h^2 - x_i^k h - \frac{k}{2} x_i^{k-1} h^2 + O(h^3) = \displaystyle \frac{k}{2} x_i^{k-1} h^2 + O(h^3)

Repeating the logic from the previous post in this series, this local error on [x_i, x_i+h], which is proportional to O(h^2), generates a total error on [a,b] that is proportional to h. That is, the right-endpoint rule has an error that is approximately linear in h, confirming the numerical observation that we made earlier in this series.

Engaging students: Finding the area of regular polygons

In my capstone class for future secondary math teachers, I ask my students to come up with ideas for engaging their students with different topics in the secondary mathematics curriculum. In other words, the point of the assignment was not to devise a full-blown lesson plan on this topic. Instead, I asked my students to think about three different ways of getting their students interested in the topic in the first place.

I plan to share some of the best of these ideas on this blog (after asking my students’ permission, of course).

This student submission comes from my former student Conner Dunn. His topic, from Geometry: finding the area of regular polygons.

green line

How can technology be used to effectively engage students with this topic? Note:  It’s not enough to say “such-and-such is a great website”; you need to explain in some detail why it’s a great website.

A good way to get students into the concept and see it’s real life use is to be given a realistic problem. The natural world doesn’t typically give you perfectly regular polygons, but we certainly like making them ourselves. Better yet, we can make regular polygons of a certain area knowing the methodology behind computing their areas. Using GeoGebra, I can challenge students to construct a regular polygon of an exact area using what they know about the use of equilateral triangles to compute area.

For example, let’s say I ask for a hexagon with an area of 12√3 square units. While there’s a few strategies of constructing a regular hexagon that Geometry students may know of, the strategy to shoot for here is to recognize this means we want a hexagon with a side length of 2 then construct the triangles. GeoGebra allows for students to use line segments and give them certain lengths, as well as construct angles using a virtual compass tool. Below is the solution to this example by constructing 6 equilateral triangles (each with an area of 2√3 square units) to form the regular hexagon.

This image has an empty alt attribute; its file name is geogebra-hexagon.png

green line

How does this topic extend what your students should have learned in previous courses?

By the end of the unit, students will have learned the formula for finding the area of a polygon (A = (1/2) * a * p, with a being the apothem, and p being the perimeter). But a big part of this unit is how we derive the formula from the process in which we solve the area using this equilateral triangle method. From many previous courses, students will have learned both the order of operations and properties of equality in equations, and we use this previous knowledge to connect a geometric understanding of area to an algebraic one. For example, when we have the idea of multiplying the area of an equilateral triangle by the number of sides, n, in the polygon, we have A = (1/2) b * h * n. It is by the use of communitive property that students can rearrange the variables like this: A = (1/2)h*b * n. And then we conclude that the b*n reveals that the perimeter of the polygon plays a role in our equation. This may seem subtle, but students being fluent in this knowledge helps them work in their geometric understandings much easier.

green line

How has this topic appeared in high culture (art, classical music, theatre, etc.)?

A big part of the method for understanding area of polygons is seeing how we can perfectly fit equilateral triangles inside of our polygons of choice. Perfectly fitting shapes into and around other shapes is something you see in mosaic art everywhere, particularly in Islamic architecture.

While mosaic artists are not necessarily calculating the areas of their art pieces (they might but I doubt it), a big part what makes these buildings so nice to look at is how the shapes fit with one another so nicely. This is an art that’s very intentional in its aesthetically pleasing aroma. This is something I think Geometry students can take to heart when confronting Geometry problems (a just as well with future courses). It’s the overlooked skill of literally connecting pieces together in order to get something we want. In the case of the Islamic architect, what we want is a pleasing building to look at, but math, of course, brings in more possible things to shoot for and equips us with plenty of pieces to (literally) connect together.

Thoughts on Numerical Integration (Part 13): Left endpoint rule and global rate of convergence

Numerical integration is a standard topic in first-semester calculus. From time to time, I have received questions from students on various aspects of this topic, including:
  • Why is numerical integration necessary in the first place?
  • Where do these formulas come from (especially Simpson’s Rule)?
  • How can I do all of these formulas quickly?
  • Is there a reason why the Midpoint Rule is better than the Trapezoid Rule?
  • Is there a reason why both the Midpoint Rule and the Trapezoid Rule converge quadratically?
  • Is there a reason why Simpson’s Rule converges like the fourth power of the number of subintervals?
In this series, I hope to answer these questions. While these are standard questions in a introductory college course in numerical analysis, and full and rigorous proofs can be found on Wikipedia and Mathworld, I will approach these questions from the point of view of a bright student who is currently enrolled in calculus and hasn’t yet taken real analysis or numerical analysis.
In the previous post in this series, we found that the local error of the left endpoint approximation to \displaystyle \int_{x_i}^{x_i+h} x^k \, dx was equal to 

\displaystyle \frac{k}{2} x_i^{k-1} h^2 + O(h^3).

We now consider the global error when integrating over the interval [a,b] and not just a particular subinterval.
The total error when approximating \displaystyle \int_a^b x^k \, dx = \int_{x_0}^{x_n} x^k , dx will be the sum of the errors for the integrals over [x_0,x_1], [x_1,x_2], through [x_{n-1},x_n]. Therefore, the total error will be

E \approx \displaystyle \frac{k}{2} \left(x_0^{k-1} + x_1^{k-1} + \dots + x_{n-1}^{k-1} \right) h^2.

So that this formula doesn’t appear completely mystical, this actually matches the numerical observations that we made earlier. The figure below shows the left-endpoint approximations to \displaystyle \int_1^2 x^9 \, dx for different numbers of subintervals. If we take n = 100 and h = 0.01, then the error should be approximately equal to

\displaystyle \frac{9}{2} \left(1^8 + 1.01^8 + \dots + 1.99^8 \right) (0.01)^2 \approx 2.49801,

which, as expected, is close to the actual error of 102.3 - 99.76412456 \approx 2.53588.
We now perform a more detailed analysis of the global error. Let y_i = x_i^{k-1}, so that the error becomes

E \approx \displaystyle \frac{k}{2} \left(y_0 + y_1 + \dots + y_{n-1} \right) h^2 + O(h^3) = \displaystyle \frac{k}{2} \overline{y} n h^2,

where \overline{y} = (y_0 + y_1 + \dots + y_{n-1})/n is the average of the y_i. Clearly, this average is somewhere between the smallest and the largest of the y_i. Since y = x^{k-1} is a continuous function, that means that there must be some value of x_* between x_0 and x_{n-1} — and therefore between a and b — so that x_*^{k-1} = \overline{y} by the Intermediate Value Theorem. We conclude that the error can be written as

E \approx \displaystyle \frac{k}{2} x_*^{k-1} nh^2,

Finally, since h is the length of one subinterval, we see that nh = b-a is the total length of the interval [a,b]. Therefore,

E \approx \displaystyle \frac{k}{2} x_*^{k-1} (b-a)h \equiv ch,

where the constant c is determined by a, b, and k. In other words, for the special case f(x) = x^k, we have established that the error from the left-endpoint rule is approximately linear in h — without resorting to the generalized mean-value theorem.

Engaging students: Finding the area of a circle

In my capstone class for future secondary math teachers, I ask my students to come up with ideas for engaging their students with different topics in the secondary mathematics curriculum. In other words, the point of the assignment was not to devise a full-blown lesson plan on this topic. Instead, I asked my students to think about three different ways of getting their students interested in the topic in the first place.

I plan to share some of the best of these ideas on this blog (after asking my students’ permission, of course).

This student submission comes from my former student Brendan Gunnoe. His topic, from Geometry: finding the area of a circle.

green line

History: Squaring the circle

The ancient Greeks and other groups at the time had a fascination with geometry. These cultures tended to like thinking in terms of simpler geometric shapes, such as circles, equilateral triangles and squares. One of the classic problems proposed by these ancient peoples was “Can you create a square with the same area as a circle with finitely many steps only using a compass and straightedge?”. This problem stood for thousands of years, stumping even the most brilliant of mathematicians that attempted to show it true. Eventually, in the year 1882, it was finally proven impossible because of a property of the number π. It’s not too hard to show that π isn’t an integer, nor is it rational. What was left to show is whether π was algebraic or transcendental. The proof from 1882 showed that π is in fact transcendental, proving that it cannot be made using the rules set out by the original question. If a number is algebraic, then it is a solution to a polynomial with rational coefficients.

green line

Curriculum: Using limit of triangular approximations to get the integral

The teacher starts off class by drawing a circle with an inscribed triangle, another with a square, and so on until a hexagon is inscribed. The teacher then draws isosceles triangles that originate at the circles center and extend to the corners of the polygons. The teacher could ask questions like “What do you notice about the total area of the triangles and the area of the circle as we keep adding sides to the polygon?” and “What do you notice about the triangles we made and the little wedges of the circle, what’s the same and what’s different about them?”. Then the teacher could arrange both the triangles and wedges in an alternating up and down fashion, almost like two zippers, to line up the triangles and wedges. The teacher could ask “What’s the length of the top of the triangles? What about the tops of the wedges, what’s their length?”.

Finally, the teacher asks “What happens when we let the number of pieces gets REALLY big? What happens to difference between the area of the triangles and wedges? What about the tops of the triangles and the tops of the wedges?”. In the limit, the upper edge converges to half of the circumference of the circle and the height of the triangles converges to the radius of the circle. Using this line of thinking, the teacher guides the students into seeing how you can derive the equation for the area of a circle by using approximating it with triangles, and then looking at what happens in the limit.

green line

Application

A telescope’s lens is what’s used to control how much light gets into the eye piece. Suppose you’re an astronomer and want to take a photo of the full Moon on a clear night, which gives off 0.25 lumens/s-m2. Suppose your camera needs to get a total of at least 3 lumens to produce a good photo and 5 lumens to get an amazing photo. What’s the radius of a lens (in centimeters) that can take a good photo in 10 minutes? What’s the radius of a lens that can take an amazing photo in 10 minutes?

Now suppose you’re working with the Hubble space telescope in low Earth orbit trying to get photos of a nearby star system. The radius of the main telescope is 120cm and the star system you want to observe is giving off light at a rate of 10-5 lumens/s-m2. How long will it take to get a good photo with Hubble? What about a great photo?

https://en.wikipedia.org/wiki/Hubble_Space_Telescope

https://en.wikipedia.org/wiki/Squaring_the_circle

Thoughts on Numerical Integration (Part 12): Left endpoint rule and local rate of convergence

Numerical integration is a standard topic in first-semester calculus. From time to time, I have received questions from students on various aspects of this topic, including:

  • Why is numerical integration necessary in the first place?
  • Where do these formulas come from (especially Simpson’s Rule)?
  • How can I do all of these formulas quickly?
  • Is there a reason why the Midpoint Rule is better than the Trapezoid Rule?
  • Is there a reason why both the Midpoint Rule and the Trapezoid Rule converge quadratically?
  • Is there a reason why Simpson’s Rule converges like the fourth power of the number of subintervals?

In this series, I hope to answer these questions. While these are standard questions in a introductory college course in numerical analysis, and full and rigorous proofs can be found on Wikipedia and Mathworld, I will approach these questions from the point of view of a bright student who is currently enrolled in calculus and hasn’t yet taken real analysis or numerical analysis.

In this post, we will perform an error analysis for the left-endpoint rule

\int_a^b f(x) \, dx \approx h \left[f(x_0) + f(x_1) + \dots + f(x_{n-1}) \right] \equiv L_n

where n is the number of subintervals and h = (b-a)/n is the width of each subinterval, so that x_k = x_0 + kh.

As noted above, a true exploration of error analysis requires the generalized mean-value theorem, which perhaps a bit much for a talented high school student learning about this technique for the first time. That said, the ideas behind the proof are accessible to high school students, using only ideas from the secondary curriculum, if we restrict our attention to the special case f(x) = x^k, where k \ge 5 is a positive integer.

For this special case, the true area under the curve $f(x) = x^k$ on the subinterval [x_i, x_i +h] will be

\displaystyle \int_{x_i}^{x_i+h} x^k \, dx = \frac{1}{k+1} \left[ (x_i+h)^{k+1} - x_i^{k+1} \right]

= \displaystyle \frac{1}{k+1} \left[x_i^{k+1} + {k+1 \choose 1} x_i^k h + {k+1 \choose 2} x_i^{k-1} h^2 + O(h^3) - x_i^{k+1} \right]

= \displaystyle \frac{1}{k+1} \left[ (k+1) x_i^k h + \frac{(k+1)k}{2} x_i^{k-1} h^2 + O(h^3) \right]

= x_i^k h + \displaystyle \frac{k}{2} x_i^{k-1} h^2 + O(h^3)

In the above, the shorthand O(h^3) can be formally defined, but here we’ll just take it to mean “terms that have a factor of h^3 or higher that we’re too lazy to write out.” Since h is supposed to be a small number, these terms will be much smaller in magnitude that the terms that have h or h^2 and thus can be safely ignored.

Using only the left-endpoint of the subinterval, the left-endpoint approximation of \displaystyle \int_{x_i}^{x_i+h} x^k \, dx is x_i^k h. Therefore, the error in this approximation will be equal to

\displaystyle \frac{k}{2} x_i^{k-1} h^2 + O(h^3).

In the next post of this series, we’ll show that the global error when integrating between a and b — as opposed to between x_i and x_i + h — is approximately linear in h.

Engaging students: Computing the determinant of a matrix

In my capstone class for future secondary math teachers, I ask my students to come up with ideas for engaging their students with different topics in the secondary mathematics curriculum. In other words, the point of the assignment was not to devise a full-blown lesson plan on this topic. Instead, I asked my students to think about three different ways of getting their students interested in the topic in the first place.

I plan to share some of the best of these ideas on this blog (after asking my students’ permission, of course).

This student submission again comes from my former student Brendan Gunnoe. His topic: computing the determinant of a matrix.

green line

How can this topic be used in your students’ future courses in mathematics or science?

When students learn about the determinant of a matrix, they only learn about computing it and don’t learn about the applications of the determinant or what they signify. One interesting use of the determinant is finding the eigenvectors of a matrix. A visual understanding of what an eigenvector is can be done by showing what a matrix does to the any generic vector, and what it does to the eigenvectors. For a generic vector that is different from an eigenvector, the matrix knocks the vector off the span of the original vector. What makes an eigenvector special is the fact that the matrix transformation keeps the eigenvector on its span but rescales said eigenvector by its eigenvalue. For example, take the matrix

\left[ \begin{array}{cc} 5 & 3 \\ 3 & 5 \end{array} \right].

This matrix’s eigenvectors are \left[ \begin{array}{c} 1 \\ 1 \end{array} \right] and \left[ \begin{array}{c} 1 \\ -1 \end{array} \right] with eigenvalues 8 and 2 respectively. That is,

\left[ \begin{array}{cc} 5 & 3 \\ 3 & 5 \end{array} \right] \left[ \begin{array}{c} 1 \\ 1 \end{array} \right] = \left[ \begin{array}{c} 8 \\ 8 \end{array} \right] = 8 \left[ \begin{array}{c} 1 \\ 1 \end{array} \right]

and

\left[ \begin{array}{cc} 5 & 3 \\ 3 & 5 \end{array} \right] \left[ \begin{array}{c} 1 \\ -1 \end{array} \right] = \left[ \begin{array}{c} 2 \\ -2 \end{array} \right] = 2 \left[ \begin{array}{c} 1 \\ -1 \end{array} \right].

Eigenvectors have many useful applications in future math and science classes including electronics, linear algebra, differential equations and mechanical engineering.

green line

How can technology (YouTube, Khan Academy [khanacademy.org], Vi Hart, Geometers Sketchpad, graphing calculators, etc.) be used to effectively engage students with this topic? Note: It’s not enough to say “such-and-such is a great website”; you need to explain in some detail why it’s a great website.

The YouTube channel 3Blue1Brown has a fantastic video on determinates and linear transformations. Grant, the channel owner, uses animations to visualize what a matrix transformation does to the plane . He starts by showing what a transformation does to a single square then shows why the change of change of that one area shows what happens to the area of any region. He also gives multiple explanations for what a negative determinate means in terms of orientation of the axes. Then he explains what happens when the determinate is 0. All of this is already extremely useful for understanding what a 2×2 matrix does, but Grant continues and extends all the same things for 3×3 transformations. Lastly, Grant gives a few explanations on why the formula for the determinate is what it is and poses a small puzzle for the viewer to contemplate. This video explains what and why we use determinates and how they can be useful all while showing pleasing visual examples and other explanations.

green line

What interesting word problems using this topic can your students do now?

Using determinates to see if a set of vectors is a basis.

The determinant can tell you when a matrix squishes space into a lower dimensional space like a line or a plane. Thus, taking the determinate of a matrix composed of a set of vectors tells you if those vectors are a basis for the matrix’s dimension.

Part 1. A 3D printer’s axes are set up in such a way that the print head can only travel in the direction \left[ \begin{array}{c} 1 \\ 1 \end{array} \right] and \left[ \begin{array}{c} -1 \\ 1 \end{array} \right]. Assume that the place where the print head is right now is the origin \left[ \begin{array}{c} 0 \\ 0 \end{array} \right]. Can you move the print head to the location \left[ \begin{array}{c} x \\ y \end{array} \right] and \left[ \begin{array}{c} 1 \\ -1 \end{array} \right] by only moving in the directions of \left[ \begin{array}{c} 1 \\ 1 \end{array} \right] and \left[ \begin{array}{c} -1 \\ 1 \end{array} \right]?

Hint: Try to solve \left[ \begin{array}{cc} 1 & -1 \\ 1 & 1 \end{array} \right] \left[ \begin{array}{c} a \\ b \end{array} \right] = \left[ \begin{array}{c} x \\ y \end{array} \right] . Does this always have a solution \left[ \begin{array}{c} a \\ b \end{array} \right]?

Part 2. Next time you turn on your 3D printer, one of the motor’s broke and now the print head can only move in the direction of \left[ \begin{array}{c} 1 \\ 0 \end{array} \right]. Assume that the place where the print head is right now is the origin \left[ \begin{array}{c} 0 \\ 0 \end{array} \right]. Can you move the print head to the location  by only moving in the direction of \left[ \begin{array}{c} 1 \\ 0 \end{array} \right]?

Hint: Try to solve \left[ \begin{array}{cc} 1 & 0 \\ 0 & 0 \end{array} \right] \left[ \begin{array}{c} a \\ b \end{array} \right] = \left[ \begin{array}{c} x \\ y \end{array} \right] . Does this always have a solution \left[ \begin{array}{c} a \\ b \end{array} \right]?

Part 3. You buy a new 3D printer that it can move in all three directions: up/down, left/right, forward/backwards. When you test out the movement of the print head, you see that each axis moves in the directions of \left[ \begin{array}{c} 1 \\ 0 \\ 0 \end{array} \right], \left[ \begin{array}{c} 0 \\ 1 \\ 0 \end{array} \right], and \left[ \begin{array}{c} 0 \\ 0 \\ 1 \end{array} \right]. Can you use your new 3D printer to go to any location \left[ \begin{array}{c} x \\ y \\ z \end{array} \right], inside the printing space?

Hint: Think about solving \left[ \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right] \left[ \begin{array}{c} a \\ b \\ c \end{array} \right] = \left[ \begin{array}{c} x \\ y \\ z \end{array} \right] . Does this always have a solution \left[ \begin{array}{c} a \\ b \\ c \end{array} \right]? How do you know?

Part 4. Your little sibling messed around with your new 3D printer and now it moves in the directions \left[ \begin{array}{c} 1 \\ 0 \\ 1 \end{array} \right], \left[ \begin{array}{c} 1 \\ 1 \\ 0 \end{array} \right], and \left[ \begin{array}{c} 2 \\ 1 \\ 1 \end{array} \right]. Is your 3D printer able to get to some point \left[ \begin{array}{c} x \\ y \\ z \end{array} \right] inside the printing space as is, or do you need to fix your printer?

Hint: Think about solving \left[ \begin{array}{ccc} 1 & 1 & 2 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{array} \right] \left[ \begin{array}{c} a \\ b \\ c \end{array} \right] = \left[ \begin{array}{c} x \\ y \\ z \end{array} \right]. Does this always have a solution \left[ \begin{array}{c} a \\ b \\ c \end{array} \right]? How do you know?

Thoughts on Numerical Integration (Part 11): Simpson’s Rule and exploration of error analysis

Numerical integration is a standard topic in first-semester calculus. From time to time, I have received questions from students on various aspects of this topic, including:

  • Why is numerical integration necessary in the first place?
  • Where do these formulas come from (especially Simpson’s Rule)?
  • How can I do all of these formulas quickly?
  • Is there a reason why the Midpoint Rule is better than the Trapezoid Rule?
  • Is there a reason why both the Midpoint Rule and the Trapezoid Rule converge quadratically?
  • Is there a reason why Simpson’s Rule converges like the fourth power of the number of subintervals?

In this series, I hope to answer these questions. While these are standard questions in a introductory college course in numerical analysis, and full and rigorous proofs can be found on Wikipedia and Mathworld, I will approach these questions from the point of view of a bright student who is currently enrolled in calculus and hasn’t yet taken real analysis or numerical analysis.

In the previous post in this series, I discussed three different ways of numerically approximating the definite integral \displaystyle \int_a^b f(x) \, dx, the area under a curve f(x) between x=a and x=b.

In this series, we’ll choose equal-sized subintervals of the interval [a,b]. If h = (b-a)/n is the width of each subinterval so that x_k = x_0 + kh, then the integral may be approximated as

\int_a^b f(x) \, dx \approx h \left[f(x_0) + f(x_1) + \dots + f(x_{n-1}) \right] \equiv L_n

using left endpoints,

\int_a^b f(x) \, dx \approx h \left[f(x_1) + f(x_2) + \dots + f(x_n) \right] \equiv R_n

using right endpoints, and

\int_a^b f(x) \, dx \approx h \left[f(c_1) + f(c_2) + \dots + f(c_n) \right] \equiv M_n

using the midpoints of the subintervals. We have also derived the Trapezoid Rule

\int_a^b f(x) \, dx \approx \displaystyle \frac{h}{2} [f(x_0) + 2f(x_1) + \dots + 2f(x_{n-1}) + f(x_n)] \equiv T_n

and Simpson’s Rule (if n is even)

\int_a^b f(x) \, dx \approx \displaystyle \frac{h}{3} \left[y_0 + 4 y_1 + 2 y_2 + 4 y_3 + \dots + 2y_{n-2} + 4 y_{n-1} +  y_{n} \right] \equiv S_n.

In the previous post in this series, we saw that both the left-endpoint and right-endpoint rules have a linear rate of convergence: if twice as many subintervals are taken, then the error appears to go down by a factor of 2. If ten times as many subintervals are used, then the error should go down by a factor of 10. However, both the Midpoint Rule and the Trapezoid Rule have a quadratic rate of convergence: if twice as many subintervals are taken, then the error appears to go down by a factor of 4. If ten times as many subintervals are used, then the error should go down by a factor of 100. Moreover, it appears that the error from the Midpoint Rule is about half that of the Trapezoid Rule if the same number of subintervals are used.

Let’s now explore the results of Simpson’s Rule applied to \displaystyle \int_1^2 x^9 \, dx = 102.3 using different numbers of subintervals. The results are summarized in the table below.

 

The first immediate observation is that these approximations are far better than even the Midpoint and Trapezoid Rules! Indeed, we see that S_{20} \approx 102.301, using only 20 subintervals, is a better approximation than (from previous posts) either M_{100} = 102.290 or T_{100} \approx 102.319 using 100 subintervals! The lesson to learn again: Simpson’s Rule is a bit more difficult to compute than the Trapezoid Rule or the Midpoint Rule because of the different weights. Nevertheless, choosing a good algorithm is often far better than simply doing lots of computations.

There’s a second observation: the rate of convergence appears to be much, much faster. Indeed, the data points appear to fit a quartic polynomial very well. Said another way, if twice as many subintervals are taken, then the error appears to go down by a factor of 16. We can actually see this in the figure, looking at the lines with 10, 20, 40, and 80 subintervals.

Error with 10 subintervals = |102.3174904 - 102.3| = 0.0174904.

Error with 20 subintervals = |102.3011002 - 102.3| = 0.0011002.

Error with 40 subintervals = |102.3000689 - 102.3| = 0.0000689.

Error with 80 subintervals = |102.3000043 - 102.3| = 0.0000043.

In all cases, the error on the next line is about the error on the previous line divided by 16.

This illustrates quartic convergence, as opposed to the mere linear convergence of the left- and right-endpoint rules or the quadratic convergence of the Midpoint and Trapezoid Rules.