MATH2070: LAB 3: Roots of Equations

Introduction	Exercise 1
A Sample Problem	Exercise 2
The Bisection Idea	Exercise 3
Programming Bisection	Exercise 4
Variable Function Names	Exercise 5
	Exercise 6

Introduction

The root finding problem is the task of finding one or more values for a variable $x$ so that an equation

$$f(x) = 0$$

is satisfied. Denote the desired solution as $x_0$. As a computational problem, we are interested in effective and efficient ways of finding a value $x$ so that $\vert f(x)\vert$, called the ``residual error,'' is small. We hope this means that $\vert x-x_0\vert$, called the ``approximation error'' is small. Today we will look at some nonlinear equations and a very simple method of finding an approximate solution.

This lab will take two sessions. If you print this lab, you may find the pdf version more appropriate.

A Sample Problem

Suppose we want to know if there is a solution to:

$$\cos x = x$$

if the solution is unique, and what that solution is. This is not an algebraic equation, and there is little hope of forming an explicit expression for the solution.

Since we can't solve this equation exactly, it's worth knowing whether there is anything we can say about it. In fact, if there is a solution $x_0$ to the equation, we can probably find a computer representable number x which approximately satisfies the equation (has low residual error) and which is close to $x_0$ (has a low approximation error). The exercise below uses a plot to illustrate the existance of a solution.

Note: Matlab has the capability of plotting some functions by name. We won't be using this capability in this course because it is too specialized. Instead, we will construct plots the way you probably learned when you first learned about plotting: by constructing a list of $x$-values (abscissæ) and corresponding $y$-values (ordinates) and then plotting the points with lines connecting them.

Exercise 1: The following steps show how to use Matlab to plot the functions $y=\cos x$ and $y=x$ together in the same graph from $-\pi$ to $\pi$.

1. Define a Matlab (vector) variable xplot to take on 100 evenly-spaced values between -pi and pi. You can use linspace to do this.
2. Define the (vector) variable y1plot by y1plot=cos(xplot).
3. Define the (vector) variable y2plot by y2plot=xplot.
4. Plot both y1plot and y2plot by plotting the first,

   plot(xplot,y1plot)
   

   then hold on, plot the second, and hold off. You saw this done before in Lab 2.
5. The two lines intersect, clearly showing that a solution to the equation $\cos x=x$ exists. Include the Matlab commands you used in your summary file. Send me the plot in the form of a jpg file. To create such a file, use the command

     print -djpeg exer1.jpg
   

   or use the ``File'' menu, ``export'' and choose JPEG image.

Exercise 2:

1. Write an m-file named cosmx.m (``COS Minus X'') that defines the function
   
   $$f(x)=\cos x-x$$
   
   
   Recall that a function m-file is one that starts with the word function. In this case it should start off as

   function y = cosmx ( x )
   % y = cosmx(x) computes the difference y=cos(x)-x
   
   % your name and the date
   
   y = ???
   

   (This is very simple-the object of this exercise is to get going.) Include a copy of this file with your summary.
2. Now use your cosmx function in the same plot sequence

   plot(???
   hold on
   plot(???
   hold off
   

   as above to plot cosmx and the horizontal axis on the interval $-\pi\le x \le\pi$. Send me the plot file as exer2.jpg.

   Hint: The horizontal axis is the line $y=0$. To plot this as a function, you need a vector $x$-values between $-\pi$ and $\pi$ and a vector of $y$-values all of which are zero (use the Matlab function zeros).

The Bisection Idea

The idea of the bisection method is very simple. We assume that we are given two values $x=x_a$ and $x=x_b$ ($x_a<x_b$), and that the function $f(x)$ is positive at one of these values (say at $x_a$) and negative at the other. (When this occurs, we say that $[x_a,x_b]$ is a ``change-of-sign interval'' for the function.) Assuming $f$ is continuous, we know that there must be at least one root in the interval.

Intuitively speaking, if you divide a change-of-sign interval in half, one or the other half must end up being a change-of-sign interval, and it is only half as big. Keep dividing in half until the change-of-sign interval is so small that any point in it is within the specified tolerance.

More precisely, consider the point $x_c=(x_a+x_b)/2$. If $f(x_c)=0$ we are done. (This is pretty unlikely). Otherwise, depending on the sign of $f(x_c)$, we know that the root lies in $[x_a,x_c]$ or $[x_c,x_b]$. In any case, our change-of-sign interval is now half as large as before. Repeat this process with the new change of sign interval until the interval is sufficiently small and declare victory.

We are guaranteed to converge. We can even compute the maximum number of steps this will take, because if the original change-of-sign interval has length $\ell$ then after one bisection the current change-of-sign interval is of length $\ell/2$, etc. We know in advance how well we will approximate the root $x_0$. These are very powerful facts, which make bisection a robust algorithm--that is, it is very hard to defeat it.

Exercise 3:

1. If we know the start points $x_a$ and $x_b$ and the interval size tolerance $\epsilon$, we can predict beforehand the maximum number of steps the bisection code can take. What is the formula for this value?
2. Give an example of a continuous function that has a root in the interval [-1, 1], but for which bisection could not be used.

Programming Bisection

Before we look at a sample bisection program, let's discuss some things. If you haven't done much programming before, this is a good time to try to understand the logic behind how we choose variables to set up, what names to give them, and how to control the logic.

First of all, we should write the bisection algorithm as a Matlab function. There are two reasons for writing it as a function instead of a script m-file (without the function header) or by typing everything at the command line. The first reason is a practical one: we will be executing the algorithm several times, with differing end points, and functions allow us to use temporary variables without worrying about whether or not they have already been used before. The second reason is pedantic: you should learn how to do this now because it is an important tool in your toolbox.

Atkinson describes the bisection algorithm (Section 2.1) in the following manner. (The variable names have changed slightly.)

Algorithm Bisect($f$,$x_a$,$x_b$,root,$\epsilon$)

1. Define $x_c$:=$(x_a+x_b)/2$.
2. If $x_b-x_c < \epsilon$, then accept root:=$x_c$, and exit.
3. If sign($f(x_b)$) * sign($f(x_c)$) < 0, then $x_a$:=$x_c$; otherwise, $x_b$:=$x_c$.
4. Return to step 1.

The language of this description is based on a computer language called Algol that is now mainly used in papers in order to specify algorithms. One objective of this lab is to show how to rewrite it in the Matlab language. As a starting point, let's fix cosmx as the function and leave it out of the calling sequence. Let's also fix epsilon=1.0e-6. Note also that, in Matlab, returned values are separated from arguments, so the variable root, which I will call approxRoot to make a point, is written on the left of an equal sign. The first few lines of the file bisect_cosmx.m should be:

function approxRoot = bisect_cosmx( xa, xb)
% approxRoot = bisect( xa, xb) uses bisection to find a
% root of cosmx between a and b to tolerance 0.000001
% xa=left end point of interval
% xb=right end point of interval
% cosmx(xa) and cosmx(xb) should be of opposite signs

Now think about the iteration. Atkinson's algorithm employs the return to Step 1 device to indicate uncounted repetition of Steps 1-4. Matlab provides a more elegant construct for uncounted repetition: the while loop. In Atkinson's Step 2, the algorithm is terminated. Matlab while loops usually terminate at their end, so we continue iterating for as long as $x_b-x_c$ is larger than epsilon, rather than stopping when $x_b-x_c$ is smaller. This reversal of the test is sometimes confusing, but it is how it is done.

Here is a Matlab function that carries out the bisection algorithm for our cosmx function. The endpoints of the initial interval are variables that you specify when you invoke the function. The Matlab variables xa, xb and xc represent the mathematical quantities $x_a$, $x_b$ and $x_c$.

function approxRoot = bisect_cosmx( xa, xb)
% approxRoot = bisect_cosmx( xa, xb) uses bisection to find a
% root of cosmx between xa and xb to tolerance 0.000001
% xa=left end point of interval
% xb=right end point of interval
% cosmx(xa) and cosmx(xb) should be of opposite signs

% your name and the date

EPSILON = 1.0e-6;
fa = cosmx(xa); 
fb = cosmx(xb);

approxRoot = (xb+xa)/2;
itCount = 0;
while ( abs ( xb - xa ) > EPSILON )
  itCount = itCount + 1;

  xc = ( xa + xb ) / 2;
  approxRoot = xc;
  fc = cosmx(xc);

  % The following statement prints the progress of the algorithm
  disp(strcat('xa=',num2str(xa),', fa=',num2str(fa),', xc=',num2str(xc),...
        ', fc=',num2str(fc),', xb=',num2str(xb),', fb=',num2str(fb)))

  if ( fc == 0 )
    break;
  elseif ( sign(fb) * sign(fc) <= 0 )
    xa = xc; fa = fc;
  else
    xb = xc;
    fb = fc;
  end

end
disp(strcat('bisect_cosmx took itcount=',num2str(itCount),' steps.'))

Note: I have violated my own rule twice about having functions print things. The first disp statement merely prints progress of the function and can be discarded once you are confident it is correct. The print of the ``number of steps'' at the end is different, and really should be returned along with the approximate root. Matlab has the capability of returning more than one quantity, but we will not use that capability until later in this course.

Exercise 4: Create the file bisect_cosmx.m by typing it in yourself, by using copy-and-paste to copy it from this window or by downloading my version of bisect_cosmx.m.

1. Why is the name EPSILON all capitalized?
2. What does the sign(x) function do? What if x is 0?
3. What does the expression sign(fb) * sign(fc) <= 0 say about fb and fc?
4. What is the purpose of the statement approxRoot = (xb+xa)/2; preceeding the while statement?
5. The disp command is used only to monitor progress. Note the use of ... as the continuation character.
6. Try the command:

     x = bisect_cosmx ( 0, 3 )
   

   Is the value x close to a root of the equation cos(x)=x?
7. Type the command help bisect_cosmx at the Matlab command line. You should see your comments reproduced as a help message. This is one reason for putting comments at the top.
8. For what input numbers will this program produce an incorrect answer (i.e., return a value that is not close to a root)? Add a check before the loop so that the function will call the Matlab error function (use the help facility for details on using error) instead of returning an incorrect answer.
9. In your opinion, why did I use abs in the test inside the while statement?

Variable Function Names

Now we have written an m-file called bisect_cosmx.m that can find roots of the function cosmx on any interval, but we really want to use it on an arbitrary function. To do this, we could create an m-file for the other function, but we would have to call it cosmx.m, because that is what the bisect_cosmx function expects. Suppose that we have three files, called f1.m through f3.m, each of which evaluates a function that we want to use bisection on. We could rename f1.m to cosmx.m, and change its name inside the file as well, and repeat this for the other files. But who wants to do that?

It is more convenient to introduce a dummy variable for the function name, just as we used the dummy variables a and b for numerical values. In Matlab, function names are passed as quoted strings and their use is only a little more difficult than for numbers.

Warning: If you forget the quotes around the function name, you will get strange errors.

Note: Matlab also uses the @ character to denote ``function handles'' that are used in much the same way as quoted strings for function names. Release 14 and newer versions of Matlab also use the @ character to define ``anonymous'' functions, and it can be used instead of the feval function below. Since Release 13 is installed on the computers in GSCC, and since the syntax below remains valid in newer versions, we will continue using feval.

Exercise 5: Copy the file bisect_cosmx.m to a new file named bisect.m, or use the ``Save as'' menu choice to make a copy with the new name bisect.m.

1. In the declaration line for bisect, include a dummy function name. We might as well call it f, so the line becomes

   function approxRoot = bisect ( f, xa, xb )
   

2. Change the comments describing the purpose of the function, and explain the variable f.
3. Where we evaluated the function by writing f(x), we now have to use a Matlab helper function called feval (Function EVALuation). For instance, the line

   fa = cosmx(xa);
   

   must be rewritten as:

   fa = feval ( f, xa );
   

   Make this change for fa, and a similar change for fb and fc.
4. When we use bisect, we must include the function name, in quotes:

   x = bisect ( 'cosmx', 0, 3 )
   

   Execute this command and make sure that you get the same result as before. (This is called ``regression testing.'')

   Warning: If you forget the quotes around cosmx and use the command

   x = bisect ( cosmx, 0, 3 )   % error!
   

   you will get the following mysterious error message:

   >> bisect(cosmx,0,3)       
   ??? Input argument 'x' is undefined.
   
   Error in ==> cosmx.m
   On line 2  ==> y=cos(x)-x;
   

Exercise 6: The following table contains formulas and search intervals for three functions. Write three simple function files, f1.m, f2.m, and f3.m, each one similar to cosmx.m but with formulas from the table. Then use bisect to find a root in the given interval, and fill in the table. I have formatted the table as ASCII text so that you can easily include it in your summary file.

Name Formula           Interval     approxRoot No. Steps

 f1  x^2-9             [0,5]        _________  _________
 f2  x^6-x-1           [1,2]        _________  _________
 f3  2*x-exp(-x)       [-10,100]    _________  _________

Back to MATH2070 page.