# Bisection Method Fortran

# Bisectional method Bisection.f90 # Closed Domain (Bisectional or False position selected by a key) CDomain.f90 # Open Domain: Newton's method Newton1.f90 # Open Domain: The method of secants Secant.f90 # Brute force method for multiple roots BForce.f90 # Solutions of a system of two nonlinear equations f(x,y) = 0, g(x,y) = 0 Newton2.f90.

Introduction | Exercise 1 |

A Sample Problem | Exercise 2 |

The Bisection Idea | Exercise 3 |

Programming Bisection | Exercise 4 |

Variable Function Names | Exercise 5 |

Exercise 6 | |

Convergence criteria | Exercise 7 |

The secant method | Exercise 8 |

Regula Falsi | Exercise 9 |

Muller's method (Extra) | Extra Credit |

- Define six real functions for Pegasus method Module to find a real root of a real function f(x) by Pegasus method Test program for Pegasus Method Module to find the real root of a continuous function by the Zeroin method Program to demonstrate the Zeroin method of module fzeroin.f90.
- PROGRAMS WRITTEN IN FORTRAN PROGRAMMING LANGUAGE 1. Finding the roots of an equation using BISECTION method. Finding the roots of an equation using NEWTON'S method. Finding the roots of an equation using SECANT method.
- Fortran example for Newton’s method¶ This example shows one way to implement Newton’s method for solving an equation (f(x)=0 ), i.e. For a zero or root of the function f(x). See Newton’s method for the square root for a description of how Newton’s method works.
- Feb 12, 2002 - (Programming) Implement the bisection algorithm in the programming language of your choice. Pci Serial Port Driver Windows 7 32 Bit Hp Dc7800. Sign function (different from Fortran intrinsic). Sample page from NUMERICAL RECIPES IN FORTRAN 77: THE ART OF.

The *root finding* problem is the task of finding one or morevalues for a variable so that an equation

is satisfied. Denote the desired solution as .As a computational problem, we are interested ineffective and efficient ways of finding a value that is ``closeenough' to . There are two common ways to measuring ``closeenough.'

- The ``residual error,' , is small, or
- The ``approximation error' or ``true error,' is small.

You will see in this lab that error estimates can be misleading and thereare many ways to adjust and improve them. We will not examine moresophisticated error estimation in this lab.

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

You can find Matlab code on the internet and in books (Quarteroni,Sacco and Saleri's book is an example).This code appears in a variety of styles. The coding style used in examples in these labs has an underlying consistency and is, in myopinion, one of the easiest to read, understand and debug.Some of the style rules followed in these labs includes:

- One statement per line, with minor exceptions.
- Significant variables are named with long names starting withnouns and followed by modifiers, and with beginnings of modifierscapitalized.
- Loop counters and other insignificant variables are short, oftena single letter such as
`k`,`m`or`n`.`i`and`j`are avoided as variable names. - The interior blocks of loops and if-tests are indented.
- Function files always have comments following the
`function`statement so that they are available using the`help`command.Function usage is indicated by repeating the signature line amongthe comments.

Clarity is important for debugging because if code is harder to read thenit is harder to debug. Debugging is one of the most difficult and least rewardingactivities you will engage in, so anything that simplifies debugging pays off.Clarity is also important when others read your code. Since I need to readyour code in order to give you a grade, please format your code similarlyto that in the labs.

Suppose we want to know if there is a solution to

whether the solution is unique, and what its value is. This is notan algebraic equation, and there is little hope of forming anexplicit expression for the solution.

Since we can't solve this equation exactly, it's worth knowing whetherthere is anything we can say about it. In fact, if there is a solution to the equation, we can *probably* find a computerrepresentable number `x` which approximately satisfies theequation (has low residual error) and which is close to (has alow approximation error). Each of the following two exercises uses aplot to illustrate the existance of a solution.

Note: Matlab has the capability of plotting somefunctions by name. We won't be using this capability in thiscourse because it is too specialized. Instead, we will constructplots the way you probably learned when you first learned aboutplotting: by constructing a pair of vectors of -values (abscissæ) andcorresponding -values (ordinates) and then plotting the pointswith lines connecting them.

**Exercise 1**: The following steps show how to use Matlab to plot the functions and together in the same graph from to .

- Define a Matlab (vector) variable
`xplot`to take on 100evenly-spaced values between`-pi`and`pi`. You can use`linspace`to do this. - Define the (vector) variable
`y1plot`by`y1plot=cos(xplot)`.This is for the curve . - Define the (vector) variable
`y2plot`by`y2plot=xplot`.This is for the line . - Plot both
`y1plot`and`y2plot`by plotting the first,then`hold on`, plot the second, and`hold off`. You saw this donebefore in Lab 2.Note: If you read the help files for the ``plot' function,you will find that an alternative single command is`plot(xplot,y1plot,xplot,y2plot)`. - The two lines intersect, clearly showing that a solution to the equation exists. Read an approximate value of at the intersection pointfrom the plot.
- Include the Matlab commands you used in your summary file. Send me the plotin the form of a
`jpg`file. To create such a file, use the commandor use the ``File' menu on the plot window, ``save' and choose JPEG image.

**Exercise 2**:

- Write an m-file named
`cosmx.m`(``COS Minus X') that defines the function

Recall that a function m-file is one that starts with the word`function`. In this case it should start off as(This is very simple-the object of this exercise is toget going.) Include a copy of this file with your summary. - Now use your
`cosmx`function to compute`cosmx(0.5)`.Your result should be about 0.37758 and should not result in extraneousprinted or plotted information. - Now use your
`cosmx`function in the same plot sequenceas above to plot`cosmx`and a line representing the horizontal axis on the interval. Send me the plot file as`exer2.jpg`.Hint: The horizontal axis is the line . To plot this asa function, you need a vector of at least two -values between and and a corresponding vector of -values all of whichare zero. Think of a way to generate an appropriate set of -valuesand -values when all the -values are zero. You could use theMatlab function

`zeros`. - Does the value of at the point where the curve crosses the-axis agree with the previous exercise?

The idea of the bisection method is very simple. We assume that weare given two values and (), and that the function is positive at one of these values (say at ) andnegative at the other. (When this occurs, we say that isa ``change-of-sign interval' for the function.) Assuming is continuous, we know that there must be at leastone root in the interval.

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

More precisely, consider the point .If we are done. (This is pretty unlikely.)Otherwise, depending on the sign of , we know that theroot lies in or . In any case, ourchange-of-sign interval is now half as large as before. Repeat thisprocess with the new change of sign interval until the interval issufficiently small and declare victory.

We are *guaranteed* to converge. We can even compute themaximum number of steps this could take, because if the originalchange-of-sign interval has length then after one bisection the current change-of-sign interval is of length , *etc*. We know in advance how wellwe will approximate the root . These are very powerfulfacts, which make bisection a *robust* algorithm--that is, itis very hard to defeat it.

**Exercise 3**:

- If we know the start points and and the interval size tolerance , we can predict beforehandthe number of steps required to reach the specified accuracy. Thebisection method will always find the root in that number or fewer steps.What is the formula for that number?
- Give an example of a continuous function that has only one root in theinterior of the interval [-2, 1], but for which bisection could not be used.

Before we look at a sample bisection program, let's discuss someprogramming issues. If you haven't done much programming before, thisis a good time to try to understand the logic behind how we choosevariables to set up, what names to give them, and how to control thelogic.

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

A precise description of the bisection algorithm is presentedby Quarteroni, Sacco, and Saleri in Section 6.2.1, on pages 250-251. The algorithmcan be expressed in the following way. (Note: the product is negative if and only if and are ofopposite sign and neither is zero.)

Given a function and so that , thensequences and for with for each can be constructed bystarting out with , then, for each ,

- Set .
- If is small enough, or if exit the algorithm.
- If , then set and .
- If , then set and .
- Return to step 1.

The bisection algorithm can be described in a manner more appropriate forcomputer implementation in the following way. Any algorithm intended fora computer program must address the issue of when to stop theiteration. In the following algorithm,

**Algorithm** Bisect(,)

- Set :=.
- If , or if happens to be exactly zero, then accept as the approximate root, and exit.
- If
`sign() * sign() < 0`, then :=; otherwise, :=. - Return to step 1.

Remarks:

- The latter form of the algorithm is expressed in a form that iseasily translated into a loop, with an explicit exit condition.
- The latter form of the algorithm employs a signum function ratherthan the value of in order to determine sign. This is a better strategybecause of roundoff errors. If and are each less than in Matlab, then their product is zero, not positive.

The language of this description, an example of ``pseudocode,' isbased on a computer language called Algol but is intended merely to bea clear means of specifying algorithms in books and papers. (The term``pseudocode' is used for any combination of a computer codinglanguage with natural language.) One objective of this lab is to showhow to rewrite algorithms like it in the Matlab language. As astarting point, let's fix to be the function `cosmx`that you just wrote. Later you will learn how to add it to thecalling sequence. Let's also fix .

Here is a Matlab function that carries out the bisection algorithmfor our `cosmx` function. In Matlab, returned values are separated from arguments, sothe variables `x` and `itCount` are written on the left of an equal sign.

Note: I have violated my own rule abouthaving functions print things, but the `disp` statementmerely prints progress of the function and will be discarded once youare confident the code is correct.

Remarks about the code: Compare the code and thealgorithm. The code is similar to the algorithm, but there are somesignificant differences. For example, the algorithm generatessequences of endpoints and andmidpoints . The code keeps track of only the most recent endpoint and midpoint values.This is a typical strategy in writing code--use variables to representonly the most recent values of a sequence when the full sequence doesnot need to be retained.

A second difference is in the looping. There is an error exit in thecase that the convergence criterion is never satisfied. If thefunction ever exits with this error, it is because either yourestimate of the maximum number of iterations is too small or becausethere is a bug in your code.

Note the symbol to represent equality in a test. Use ofa single `=` sign causes a syntax error in Matlab. In languages such as C no syntax error is produced but the statement iswrong nonetheless and can cause serious errors that are very hard to find.

**Exercise 4**: Create the file

`bisect_cosmx.m`by typing it in yourself, or by using copy-and-paste to copy it from theweb browser window.

- Replace the ``
`???`' with your result from Exercise 3.This value should be an integer, so be sure to increase the value fromExercise 3 to the next larger integer.(If you are not confident of your result, use 10000. If the codeis correctly written, it will work correctly for any value larger thanyour result from Exercise 3.)

Hint: Recall that . - Why is the name
`EPSILON`all capitalized? - The variable
`EPSILON`and the reserved Matlabvariable`eps`have similar-sounding names. As`EPSILON`is used in this function, is it related to`eps`?If so, how? - In your own words, what does the
`sign(x)`function do? What if`x`is 0? The`sign`function can avoid representation difficulties when`fa`and`fm`are near the largest or smallest numbers that can be represented on the computer. - The
`disp`command is used only to monitor progress. Notethe use of`...`as the continuation character. - What is the result if the Matlab
`error`function is called? - Based on your understanding of the code, what would the final value of
`itCount`be if`a`and`b`are already closer together than the tolerance when the functionstarts? - Try the command: Is the value
`z`close to a root of the equation`cos(z)=z`?

Warning: You should not see the error message! If you do,your value for the maximum number of iterations is too small. - How many iterations were required? Is this value smaller than thevalue from your formula in Exercise 3?
- Type the command
`help bisect_cosmx`at the Matlabcommand line. You should see your comments reproduced as a helpmessage. This is one reason for putting comments at the top. - For what input numbers will this program producean incorrect answer (
*i.e.*, return a value that is not closeto a root)? Add a check before the loop so that the function willcall the Matlab`error`function instead of returning an incorrect answer. - In your opinion, why did I use
`abs`in the convergence test?

Now we have written an m-file called `bisect_cosmx.m` that canfind roots of the function `cosmx` on any interval, but we reallywant 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 callthat m-file `cosmx.m` even if there were no cosines in it, becausethat is what the `bisect_cosmx` function expects. Suppose that wehave three files, called `f1.m` through `f3.m`, each of whichevaluates a function that we want to use bisection on. We *could*rename `f1.m` to `cosmx.m`, and change its name inside thefile as well, and repeat this for the other files. But who wants to dothat?

It is more convenient to introduce a dummy variable for the functionname, just as we used the dummy variables `a` and `b` fornumerical values. In Matlab, function names can be passed as ``function handles.'

In the bisection function given below, the name of the function is specifiedin the function call using the `@`

character as:

Warning: If you forget the `@`

in front of thefunction name, Matlab will produceerrors that seem to make no sense at all (even less than usual). Keepin mind that function names in calling sequences must havethe `@`

character in front of them.Check for this first when you get errors in a function.

Remark: Quarteroni, Sacco, and Saleri have an m-filenamed `bisect.m` on p. 252. Their function includes a variablenamed `fun` that contains a string representing the function whoseroot is to be found. They find function values using `eval`. Incontrast, `bisect.m` presented above uses a variable named `func`to contain a function handle to evaluate the function.Using function handles is moreflexible, allowing much more complicated functions, and is similar to theway that other programming languages (Fortran, C, C++, Java, etc.)work.

**Exercise 5**: Copy the file

`bisect_cosmx.m`to a new file named

`bisect.m`, or use the ``Save as' menu choiceto make a copy with the new name

`bisect.m`.

- In the declaration line for
`bisect`,include a dummy function name. We might as well call it`func`, sothe line becomes - Change the comments describing the purpose of the function,and explain the variable
`func`. - Where we evaluated the function by writing
`cosmx(x)`,you now write`func(x)`. For instance, the line must be rewritten as: Make this change for`fa`, and a similar change for`fb`and`fx`. - When we use
`bisect`, we must include the function namepreceeded by`@`

Execute this command and make sure that you get the same resultas before. (This is called ``regression testing.')Warning: If you forget the

`@`

before`cosmx`anduse the commandyou will get the following mysterious error message: - It is always a good idea to check that your answers are correct. Consider the simple problem . Write a simple function m-file named
`f0.m`(based on`cosmx.m`but defining the function ) and show that you get the correct solution (`x=1`to within`EPSILON`) starting from the change-of-sign interval`[0,3]`.

Remark for advanced users: Matlab allows a simple function to be defined withouta name or an m-file. You can then use it anywhere a function handle could be used. For example, for the function , you could writeor even asBe very careful when using this last form because there is no`@`

appearing in the `bisect` call but it is a functionhandle nonetheless.

- Copy your
`bisect.m`file to one named`bisect0.m`,or use ``Save as' from the ``File' menu. Be sure to change the nameof the function inside the file. Change the lineto readSince there is no longer a theoretical expression for the maximumnumber of interations, you should also increase the maximum number of iterations to 10000. - Consider the function
`f0=x-1`on the interval`[0,3]`.Does your new function`bisect0`find the correct answer? (It should.) - The amount the residual differs from zero is called the residualerror and the difference between the solution you found and the truesolution (found by hand or some other way) is called the trueerror. What are the residual and true errors when you used
`bisect0`to find the root of the function`f0`above?How many iterations did it take? - What are the residual and true errors when using
`bisect0`to find the root of the function`f5=(x-1)^5`?How many iterations did it take? - To summarize your comparison, fill in the following table
- The
`bisect0`function has the value`EPSILON = 1.0e-10;`in it. Does the table show that the residual error is always smallerthan`EPSILON`? What about the true error? - Set
- If , then accept as the approximate root, and exit.
- Replace with and with .
- Return to step 1.
- Write an m-file named
`secant.m`, based partly on`bisect.m`, and beginning with the lines - Because residual error is used for convergence, and becausethe number of iterations is unknown, choose the values
- Comment any ``
`disp`' statements so they do not provide a distraction. - Complete
`secant.m`according to the secant algorithm given above. - Test
`secant.m`with the linear function`f0(x)=x-1`. Youshould observe convergence to the exact root in a single iteration. If youdo not, go back and correct your code. Explain why it should only takea single iteration. - Repeat the experiments done with bisection above, usingthe secant method, and fill in the following table.
- In the above table, you can see that the secant method can be eitherfaster or slower than bisection. You may also observe convergence failures:either convergence to a value that is not near a root or convergence toa value substantially less accurate than expected. Regarding thebisection roots as accurate, are there any examplesof convergence to a value that is not near a root in the table? If so, which?Are there any examples of inaccurate roots? If so, which?
- Set
- If , then accept as the approximate root, and exit.
- If
`sign() * sign()`, then set , to keep the change-of-sign interval. - Set .
- Return to step 1.
- Starting from your
`bisect0.m`file, write an m-file named`regula.m`to carry out the regula falsi algorithm. - Test your work by finding the root of
`f0(x)=x-1`onthe interval`[-1,2]`. You should get the exact answer ina single iteration. - Repeat the experiments from the previous exercise but using
`regula.m`and fill in the following table.You should observe both faster and slower convergence, comparedwith bisection and secant. You should not observe lack of convergenceor convergence to an incorrect solution. - Function
`f5`,`(x-1)^5`turns out to be verydifficult for regula falsi! Loosen your convergence criterion to a tolerance of and increase the maximum allowable number ofiterations to 500,000 and fill in the following line of the table.(Be sure that any ```disp`' statements are commented out.)You should observe convergence, but it takes a very large number of iterations. `regula.m`and`bisect.m`both keep the current iterate,`x`in a change-of-sign interval. Why would it be wrong to usethe same convergence criterion in`regula.m`as was used in`bisect.m`?- Choose a convergence criterion and a maximumnumber of iterations
`ITMAX = 100` - Choose a third point, not quite at the center of the change-of-signinterval
`[a,b]` - Evaluate
`y0`,`y1`, and`y2`as values of`func`at`x0`,`x1`, and`x2`. - Determine coefficients
`A`,`B`, and`C`of the polynomial passing through the three points`(x0,y0)`,`(x1,y1)`and`(x2,y2)`, : - If the polynomial has real roots, find them and choose theone closer to
`x2`, otherwise choose something reasonable: - Discard the point
`(x0, y0)`and add the new point - Exit the loop and return
`result = x2`if the residual (`y2`) is smaller than . - Go back to 4 unless
`ITMAX`is exceeded, in which case print an error message. - Following the outline above, create a file
`muller.m`thatcarries out Muller's method. - Test
`muller.m`on the simple linear function starting with thechange-of-sign interval`[0,2]`. You should observe convergencein a single iteration. If you do not observe convergence in a singleinteration, you probably have a bug. Fix it before continuing. Explain why (one sentence, please) it requires only a single iteration. - Test
`muller.m`on the function`f1`on the change-of-sign interval`[0, 5]`. Again, you should observe convergence in a single iteration. If you do not, you probably have abug. Fix it before continuing.Explain why (one sentence, please) it requires only a single iteration. - Repeat the experiments from the previous exercise but using
`muller.m`and fill in the following table.You should observe that, since the interval at each iteration need notbe a change-of-sign interval, it is possible for the method to fail, as with

`secant`. It is possible to combine several methods insuch a way that the speed of`secant`or`muller`ispartially retained but failure is avoided by maintaining achange-of-sign interval at each iteration. One such method is calledBrent's method. See, for example,`http://en.wikipedia.org/wiki/Brent%27s_method`

The secant method is described by Quarteroni, Sacco, and Saleri in Section 6.2.2. Instead of dividing the interval in half, as is donein the bisection method, it regards the function as approximately linear,passing through the two points and and then finds theroot of this linear function. The interval need no longer bea change-of-sign interval, and the next value of need no longerlie inside the interval . In consequence, residual convergencemust be used in the algorithm instead of true convergence.

It is easy to see that if a straight line passes through the two points and , then it crosses the -axis () when.

The secant method can be described in the following manner.

**Algorithm** Secant(,)

The secant method is sometimes much faster than bisection, but sinceit does not maintain an interval inside which the solution must lie, thesecant method can fail to converge at all. Unlike bisection, thesecant method can be generalized to two or more dimensions, andthe generalization is usually called Broyden's method.

**Exercise 8**:

The regula falsi algorithm can be described in the following manner, reminiscentof the bisection and secant algorithms given above. Since the interval is supposed to begin as a change-of-sign interval, convergence isguaranteed.

**Algorithm** Regula(,)

Remark:It is critical to observe that Step 3 maintains theinterval as a change-of-sign interval that is a subinterval ofthe initial change-of-sign interval. Thus, regula falsi, unlike the secant method,must converge, although convergence might take a long time.

**Exercise 9**:

In the secant method, the function is approximated by its secant (thelinear function passing through the two endpoints) and then thenext iterate is taken to be the root of this linear function. Muller'smethod goes one better and approximates the function by the quadraticfunction passing through the two endpoints and the current iterate. Thenext iterate is then taken to be the root of this quadratic that isclosest to the current iterate.

### Bisection Method Using Fortran

In more detail, suppose I want a function with signature similar toour functions above:

**Exercise 10**:

### Bisection Method Fortran Function

Back to MATH2070 page.