Lab 7—The Bisection Method

Purpose

This lesson introduces you to the bisection method, an algorithm for finding roots of functions. It also introduces the if statement, and generally reinforces your programming ability.

Background

Given a function, f(x), a root of f is simply a value of x at which f(x) = 0. Finding roots of functions is the heart of algorithms for solving many mathematical problems.

The bisection method is a popular algorithm for finding a root of function, if you know x values on either side of the root. For a description of it, see the video lecture entitled “Bisection Method: Algorithm” at https://www.youtube.com/watch?annotation_id=annotation_671603&feature=iv&src_vid=244sNlaspTg&v=Y2AUhxoQ-OQ. I also expect to discuss it in class on November 16.

if statements let you write programs that make choices. Matlab’s if statement is covered in sections 13.1 and 13.2 of our textbook. I expect to talk about it in class on November 18.

This exercise is based on one developed by Prof. Carol Haddad at SUNY Geneseo.

Activity

An explorer has arrived at the base of a mysterious parabolic peninsula. The coastline of the peninsula is described by the equation y = 16 - 4x², in a coordinate system where the x axis is the coastline of the mainland and the ocean extends indefinitely in the positive y direction. By an amazing and convenient coincidence, the explorer has camped exactly at the origin of this coordinate system. The explorer wants to find the shortest route from her campsite to the coast of the peninsula.

The explorer knows that she can find a point on the peninsula closest to her campsite by working out an equation for the distance between the camp and the point in terms of the point’s x coordinate. She can then differentiate this equation and find x values that make the derivative 0. One (or more) of these should correspond to the point closest to her camp. (How many closest points are there? You only need to find one.)

Write a Matlab script that carries out the calculation described above to find the (x,y) coordinates of a coastline point closest to the explorer’s camp. Your script should call a “bisect” function (which you will need to write) that finds a root of another function. Your “bisect” should take three arguments: a handle for the function, f, of which to find a root, and two x values, x_l and x_u with the property that the signs of f(x_l) and f(x_u) differ. You may assume that f is continuous between x_l and x_u. The “bisect” function should return a value of x at which f is nearly 0. Your main script should use “bisect” to find an x value at which the derivative of the distance function is 0.

You may work out the derivative of the distance function by hand if you want to, but you don’t need to—from our Newton’s method lab and the discussion of its extra credit part, you know how to write a Matlab function that generates the derivative of another function passed to it as a parameter.

Follow-Up

I will grade this exercise in a face-to-face meeting with you. During this meeting I will look at your solution, ask you any questions I have about it, answer questions you have, etc. Please bring a written solution to the exercise to your meeting, as that will speed the process along.

Sign up for a meeting via Google calendar. If you worked in a group on this exercise, the whole group should schedule a single meeting with me. Please make the meeting 15 minutes long, and schedule it to finish before the end of the “Grade By” date above.