Numerical Integration

From CDS 130

Jump to: navigation, search
Numerical Integration

Contents

  1. Objective
  2. Motivation
  3. Priming questions
  4. Notes
    1. Introduction
    2. Introduction cont.
    3. Introduction cont.
    4. Introduction cont.
    5. Introduction cont.
    6. Introduction cont.
    7. Basic concept
    8. Using a computer
    9. Approach A
    10. Approach B
    11. Question
    12. Answer
    13. Alternative to Square Tiles
    14. Rules
    15. Rules cont.
    16. Rules Summary
    17. Rectangle Width
    18. Estimates using a spreadsheet
    19. Estimates using program
      1. Using "Left" rule
      2. Using "Middle" rule
      3. Using "Right" rule
    20. Estimates using program II
  5. Questions
    1. Tile Size
    2. Rectangle motivation
    3. Algorithm for splitting rectangles
    4. Numerical Integration
    5. Numerical Integration
    6. Numerical Integration
    7. Numerical Integration
  6. Activity
    1. Numerical Integration
    2. Numerical Integration

1. Objective

  • To introduce the concept of numerical integration
  • To have an understanding of the trade-off between number of calculations and accuracy of an estimate of area.

2. Motivation

  • In scientific computing, we often want to figure out the area enclosed by a set of lines.
  • Most often, those set of lines do not correspond to a shape for which we have an analytic formula, such as L\cdot W or \pi\cdot r^2.

3. Priming questions

How would you determine the area of the shape?
How would you determine the area of the shape?


4. Notes

4.1. Introduction

  • Kepler was an astronomer born in 1571 who plotted data of the location of planets with respect to the sun.
  • Like all scientists, he wanted a simple rule to explain lots of numbers. In his case his numbers were values of the positions of the planets throughout the year.

From [1]

4.2. Introduction cont.

  • One day his child was playing with little square lego blocks.
  • He placed these blocks on his sheet of paper and found that 131 fit into the area "swept" out by the planet from point A to B (which took about 3 months).
  • He then placed these blocks in the area "swept" out by the planet from C to D (which took 3 months).
  • He noticed that he needed 131 legos for this area too.


4.3. Introduction cont.

  • He then placed these blocks in the area "swept" out by the planet from C to H (which took about 3 months).
  • He noticed that he needed 131 legos for this area too.


4.4. Introduction cont.

  • Would Kelper have come up with his rule if the tiles were huge in comparison to his drawing?
  • Probably not


4.5. Introduction cont.

  • You can estimate areas by placing tiles on the area and counting the number of tiles required to cover the area.
  • Smaller tiles give a better estimate of the area.

4.6. Introduction cont.

  • You have already encountered the concept of estimating areas using squares before
  • (a rectangle can be thought of as a bunch of stacked squares)
  • How many people were surveyed?
  • Bonus question: Something is fishy about these survey results.

Image:histogram.png

Spreadsheet for this histogram

  • Bonus answer: It is quite unlikely that the numbers in each bin would be a multiple of ten. It is also suspect that nobody chose 8 or 9.

4.7. Basic concept

Take-away message from introduction:

  • Estimate shapes with squares (or rectangles = stacks of squares)
  • Smaller squares give better estimate
  • More squares require more computation (counting)

4.8. Using a computer

  • In this class, we will consider only "simple" shapes.
    • always draw shapes on an x-y scale
    • the x and y axes will be the lower and upper boundaries, respectively

Image:triangle_simpleb.svg

4.9. Approach A

Approach A for laying down tiles. Stack tiles until the right-top corner of one of the tiles is at or above the upper line.

4.10. Approach B

Approach B for laying down tiles. Stack tiles until the left-top corner of one of the tiles is at or above the upper line.

4.11. Question

  • Why not use tiles that are shaped like triangles?!

4.12. Answer

  • Most of the time the shape of the curve is not so simple.

4.13. Alternative to Square Tiles

  • This is the approach that we will use.
  • Instead of counting tiles (squares), you add up the area of rectangles.
  • What is the advantage of this?
  • This will be the method used when we do the calculation with a computer.

4.14. Rules

  • Use rectangles to compute the area of the triangle.
    • Rule: you may use only four rectangles
    • Rule: your rectangles do not need to completely cover (obscure) the triangle
    • Rule: rectangles must have a width of 1 block
    • Rule: The height of the rectangle for a given problem is always chosen based on one of three rules.

4.15. Rules cont.

The possibilities for rectangle heights.

  • Left: Always make the rectangle the height of the curve at the left side of the rectangle. In the left-most image, the first rectangle has a height of zero.
  • Middle: Always make the rectangle the height of the line at the middle of the rectangle
  • Right: Always make the rectangle the height of the line at the right side of the rectangle

4.16. Rules Summary

  • Rectangles can be used to estimate area
  • There are choices for how to choose the height of the rectangles
  • Now repeat the rectangle exercise using rectangles of width 0.5.

4.17. Rectangle Width

  • The equivalent to choosing a tile size is choosing a rectangle width and an algorithm for picking the rectangle height.
  • Smaller-width rectangles lead to more computation ...
  • ... but more accuracy

4.18. Estimates using a spreadsheet

  • This spreadsheet shows the area of all rectangles for the left, middle, and right choices of rectangle heights [2]


The possible rules to use for determining rectangle heights:

  • Left: Always make the rectangle the height of the curve at the right side of the rectangle
  • Middle: Always make the rectangle the height of the line at the middle of the rectangle
  • Right: Always make the rectangle the height of the line at the right side of the rectangle

4.19. Estimates using program

In some cases, where we have a simple equation for the height of the actual curve (e.g., y=.33x^2), we can use iteration to compute the sum. To determine the required for loop, write out the calculations that must be performed without iteration first. Then write a for that does the same calculation.

4.19.1. Using "Left" rule

H(1) = 1*0;
H(2) = 1*1;
H(3) = 1*2;
H(4) = 1*3;
a = H(1) + H(2) + H(3) + H(4);
w = 1.0;
for i = [1:4] % 4 rectangles, so need 4 iterations.
  H(i) = w*(i-1.0); % or 1.0*(i-1.0)
end
a = H(1) + H(2) + H(3) + H(4);
% or
a = sum(H) 

4.19.2. Using "Middle" rule

Write out the long-hand version of the program to the right.

w = 1.0;
for i = [1:4]
  H(i) = w*(i-0.5);
end
H
sum(H)

4.19.3. Using "Right" rule

H(1) = 1.0*1;
H(2) = 1.0*2;
H(3) = 1.0*3;
H(4) = 1.0*4;

Write out the for-loop version of the set of commands to the left.

4.20. Estimates using program II

Repeat the above three cases except use rectangle with one-half the width.

5. Questions

5.1. Tile Size

Suppose that you want to estimate the area of room by laying down tiles.

  • What is an advantage of using small tiles to estimate the area?
  • What is an advantage of using big tiles to estimate the area?

5.2. Rectangle motivation

When we are estimating area using a computer, we add up the area of rectangles instead of the area of a bunch of tiles (squares) or triangles. Why?

5.3. Algorithm for splitting rectangles

The image below shows how a student doubled the number of rectangles used to estimate the area in the blue box. They just drew a line through the middle of each rectangle.

  1. Why is this approach not useful?
  2. Suggest a better algorithm for doubling the number of rectangles.

5.4. Numerical Integration

  1. Estimate the area of the blue shape using 5 vertical rectangles. Draw the rectangles and show your calculations.
  2. State the algorithm that you used to determine the height of each rectangle. (Left, Middle, or Right)
  3. Did your algorithm lead to an over- or under-estimate of the area?
  4. If 10 rectangles are used
    • How many more calculations are required to estimate the area?
    • Will the answer be closer to the analytic value of the area?

Image:area_triangles.svg

5.5. Numerical Integration

  • Estimate the area of the blue shape using 4 vertical rectangles. Draw the rectangles and show your calculations.
  • State the algorithm that you used to determine the height of each rectangle.
  • Did your algorithm lead to an over- or under-estimate of the area?
  • If twice as many rectangles are used
    • How many more calculations are required to estimate the area?
    • Will the answer be closer to the analytic value of the area?

Image:area_triangles2.svg

5.6. Numerical Integration

In this problem, we are given an equation that represents the height so we can compute the area by hand calculations and by iteration.

Compute the area between the lines y=0, x=3, and y=x2 using rectangles of width 1. Use this graph paper and let 1 unit be the width of a square.

Repeat the above using rectangles of width 1/2 of a square.

Write down your rule for selecting the heights of the rectangles in 1. and 2. What would an advantage be of having a simple rule or a rule that is the same for all rectangles as opposed to a rule that depends on x?

Write a program without a for to compute the area using w=1.

Re-write the program with a for loop.

Answer the last two questions using w = 0.5.

5.7. Numerical Integration

The following program is used to estimate the area under the curve y = x2/4 between x = 0 and x = 5:

A = 0;
for i = [1:5]
  A = A+ (i)^2/4;
end

Sketch the curve and the rectangles that correspond to the program above. Label the height of each rectangle.


6. Activity

6.1. Numerical Integration

Use vertical rectangles to estimate the areas of the objects shown on the following hand-outs.

6.2. Numerical Integration

In this problem, we are given an equation that represents the height so we can compute the area by hand calculations and by iteration.

  • Compute the area between the lines y=0, x=3, and the curve y=0.3333·x3 using rectangles of width 1. Use this graph paper and let 1 unit be the width of a square. Turn in your diagram at the start of class. Include your calculations on your paper. You do not need to put your answers to this question on your wiki page.
  • Write a program without a for to compute the area using w=1.
  • Write a program with a for to compute the area using w=1.
  • Repeat all of the above using using w = 0.5.
Personal tools