Lab 6—The Bisection Method

Purpose

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

Background

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

The bisection method is a popular algorithm for finding a zero of function, if you know x values on either side of the zero. 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.

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 zero of another function. Your “bisect” should take three arguments: a handle for the function, f, of which to find a zero, 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—you can write a Matlab function that evaluates the derivative of a function passed to it as a parameter. I leave the details of how to write such a function as a puzzle for you to think about.

Extra Credit

I mentioned above that you can write a Matlab function that evaluates the derivative of another function. If you call such a function “derivative”, the easiest way to think about it is that it takes two arguments, a function handle f, and a value, x, returning the value of f′(x). However, there is a more elegant way to think about “derivative”: as a function that takes just f as its parameter, and that returns another function handle to f′. For up to 2 points extra credit, see if you can write such a “derivative” function.

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.