Homework 3: Function accuracy

Note: This assignment must be submitted in github classroom.

Numeric Accuracy in Functions

Counting function calls

How often does the recursive implementation of fibonacci call on itself? Yes, we could determine this mathematically, but … where is the fun in that? Determine the number of calls to fibonacci for n = 1, …, 10 without changing the function itself. Hint: ?trace

fibonacci <- function(n, a, b) {
  stopifnot(is.numeric(n), n >= 0)
  if (n == 0) return(a)
  if (n == 1) return(b)
  return(fibonacci(n-1, a, b) + fibonacci(n-2, a, b))
}

Equivalence does not mean equivalent errors

Consider the two functions \(f\) and \(g\):

\[ f(x) = x^2 \cdot (\sqrt{x+1} - \sqrt{x}) \ \ \text{ and } \ \ g(x) = \frac{x^2}{\sqrt{x+1} + \sqrt{x}} \] Mathematically, these two functions are equivalent.

1. Implement the functions \(f\) and \(g\) and show that the implementations give numerically non-identical results.

2. Show that for \(x = 5 \cdot 10^6\) we get \(f(5\ 000\ 000) = 5\ 590\ 169\ 667\) and \(g(5\ 000\ 000) = 5\ 590\ 169\ 664\).
   Which of these results is more correct? Explain (Proofs are fine, too).

Midnight means it’s dark outside?

Assume that you are using \(\beta = 10\) and \(p = 3\). Make sure that you use the limited precision by rounding to p significant digits in each step (with signif)

1. Write a function midnight that finds the solutions to \(a x^2 + bx + c = 0\) (i.e. implements the midnight formula):

\[ x_{1,2} = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a} \]

2. What is the relative error of midnight for a = 1.22, b = 3.34 and c = 2.28?

3. The midnight formula contains two terms that might result in a catastrophic cancellation. Which are the terms? Which of the two contributes to the error in the example? Construct an example, in which the other term dominates the relative error.

4. A different approach to find the roots of a quadratic equation is to ‘identify’ two numbers \(r_1\) and \(r_2\), such that the two conditions hold: \[ \begin{eqnarray*} r_1 \cdot r_2 &=& a \cdot c\\ r_1 + r_2 &=& b \end{eqnarray*} \] The quadratic equation can then be written as the product of \((x+\frac{c}{r_1})(ax + r_1)\).
   Implement this approach iteratively as midnight2, i.e. use a starting point for \(r_1\), then alternatingly update \(r_2\) and \(r_1\) until the values converge (change less than a pre-specified tolerance).

5. What relative error do results produced with midnight2 have? Compare with the two previous results.

6. How does the general purpose function uniroot compare to the special solution to the midnight formula? Calculate the relative error.
   Assume that the previous solution with p > 16 provides the ‘correct’ solution.