Skip to content

Exercises: Series II

Dichotomy

Let's try to find the number x_0 so that f(x_0) = 0 with f(x) = exp(x)-3x using dichotomy.

Dichotomy is a fast and powerful method to find the zero of a continuous function.

If a and b are two real numbers such as f(a) < 0 and f(b) > 0, then there exists at least one number x_0 in the interval [a;b] such as f(x_0)= 0.

The dichotomy method consists in choosing 2 initial values a and b such as f(a) < 0 < f(b), then to reduce the [a;b] interval as follows:

  1. let's compute m = \frac{a+b}{2}
  2. if f(m) < 0 then the zero of the function is in the [m;b] interval else, the zero of the function is in the [a;m] interval
  3. let's repeat steps 1 and 2 until the interval is small enough (i.e., smaller than a pre-defined \epsilon)

Write a python script to compute the zero of f(x) = exp(x)-3x using dichotomy. The solution will be found within a precision \epsilon defined by the user.

Solution

Pascal's triangle

Binomial coefficients can be defined using two formula. Either:

\left(\begin{array}{c}n\\p\end{array}\right) = \frac{n!}{(n-p)! p!}

or

\left(\begin{array}{c}n\\0\end{array}\right) = \left(\begin{array}{c}n\\n\end{array}\right) = 1 \quad \text{and} \quad \left(\begin{array}{c}n\\p\end{array}\right) = \left(\begin{array}{c}n-1\\p\end{array}\right) + \left(\begin{array}{c}n-1\\p-1\end{array}\right) \quad \text{for any }n > 0 \text{ and } 0 < p < n
  1. define a function that computes the factorial n! for any given n
  2. define a function that computes any given binomial coefficient \left(\begin{array}n\\ p\end{array}\right) using the factorial formula
  3. define a recursive function that computes any binomial coefficient using the second formula (i.e., the recursive one)
  4. the problem of the previous function is that it is quite inefficient since it recomputes over and over the same intermediate values. Modify this function so that any computed values is stored in a Python dictionnary that can be re-used as necessary instead of recomputing the intermediate values.

Solution