Description

In this assignment, you will implement a simple algorithm for finding a root (approximately) of a continuous one-dimensional function f : → . Treat this homework as a warm-up: become comfortable with the language which you will be using (either matlab or python); try to write clean, well-commented code, in which all possible errors are checked; always keep performance in mind, but don’t overdo it (readability is more important, in this course).

You should turn in an archive containing all of your source code, plots, and a document containing a brief description of your code (how to run it, what parameters it takes, etc), and answers to all questions. Email this archive to your TA, at cotter@tti-c.org.

Setting up your environment

In this course, you may choose between using matlab or python for your assignments. Octave, while it is mostly matlab-compatible, is not quite matlab-compatible enough (the code provided for some assignments will not run under octave).

If you’re using python, you should install the numpy ( http://numpy.scipy.org/) library. We also recommend that you use the matplotlib ( http://matplotlib.sourceforge.net/) library for creating plots. Finally, you might find it convenient to use IPython ( http://ipython.scipy.org/), rather than python’s default shell, though this is purely optional.

1 Bisection method

Implement the bisection method ( http://en.wikipedia.org/wiki/Bisection_method). Your function should take four parameters: f (the function), a (the left endpoint of the initial interval), b (the right endpoint) and ε (the desired accuracy); it should return a list of the triples a,b,f for each iteration. This algorithm is very simple, so style counts! In particular:

1. On entry, check that a < b, sgn≠sgn, and ε > 0, raising an error if any of these conditions is not satisfied
2. Check that you do not enter an infinite loop (which may happen if, for example, ε is smaller than the amount of precision in the arithmetic), by raising an error if some ridiculously large number of iterations are performed
3. Try to evaluate the function f as few times as possible per iteration
4. Comment any portion of your code of which the interpretation is not obvious (admittedly, there may be no such code for this problem)

1.1 Convergence rate

Use the bisection method to estimate by finding a zero of f = x² - 2, with a starting interval of . Create a plot of error () versus the number of iterations, with the error in log scale. Describe, in a few sentences, the shape of this plot, and why it has this shape.

Remember that you need to turn in your plots. In matlab, you can save from the plot window. In python (with matplotlib), use the savefig function.

2 Bisection method for optimization

We may minimize a convex f : → by finding a point at which f′ = 0. Implement the bisection method for optimization, by finding such a point (by modifying a copy of your implementation in problem 1). Your function should take four parameters: f (the function), f′ (its derivative), a (the left endpoint of the initial interval), b (the right endpoint) and ε (the desired accuracy); it should return a list of the triples a,b,f.

2.1 Optimization

Consider the function f = e^-x + x². Is this function convex? Minimize f using the bisection method, with a starting interval of , and ε = 10^-12. Create a plot of the function value f versus the number of function evaluations n.

2.2 Function fitting

The “data.csv” file ( /pa1/data.csv) contains a set of x,y pairs, one per line, with x . Your task is to fit a line to this data, with the objective function:

Is this function convex? Solve the problem using the bisection method, with a starting interval of . Create a plot containing both the data, and the fitted line.