Lesson 8—The Bisection Method

Purpose

This lesson introduces you to the bisection method, a second 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

Main Exercise

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. You should also write a “bisect” function that finds a zero of another function. The “bisect” function should take three arguments: a handle for the function, f, of which to find a zero, and two x values, x₁ and x₂ with the property that the signs of f(x₁) and f(x₂) differ. You may assume that f is continuous between x₁ and x₂. 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 already have a function from the Newton’s method lab that evaluates the derivative of an arbitrary function. See if you can figure out how to re-use this function in the present lab.

Extra Credit

The bisection method is closely related to an algorithm called “binary search” for finding a piece of data in a sorted vector. The main difference is that while the bisection method maintains a pair of x values that bracket a zero of f, and updates this pair by examining the sign of f at the point midway between these two values, binary search maintains a pair of positions in the vector that bracket the location of the desired value (or the location where it would be, if present—it might not be in the array at all), and updates these positions by comparing the vector element halfway between them to the desired value. Since the vector is assumed to be sorted, noticing whether the middle element is greater than the desired one or less tells you whether the desired value lies in the first or second half of the interval. Search for the phrase “binary search” on the Internet for more information.

For up to 2 points extra credit, write a function that takes a vector of numbers, v, and a specific number, x, and returns True if x appears somewhere in v and False otherwise. Your function should use binary search to compute its answer. You may assume that v is sorted into increasing order.

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.