Homework 2

Due: Thursday 2/22

---

1. Write a MATLAB program which uses Newton's method to compute the first four positive solutions to the equation $x = \csc{x}$ to machine precision. To obtain accurate initial guesses, plot the functions involved and choose a number nearby the solution you are interested in.

2. Recall in class we discussed an algorithm for computing $1/\alpha$ , $\alpha >0$ that only involved addition, subtraction and multiplication. This algorithm was obtained by applying Newton's method to the function $f(x) = \alpha - 1/x$. The method obtained was \[ x_{i+1} = x_i(2 - \alpha x_i). \]

   1. In MATLAB, implement this method with the goal of computing $1/3$ with an absolute error of $10^{-6}$ using initial guesses $x_0 = .25$ and $x_0 = 1$. What happens for each guess?

   2. Show mathematically that if the initial guess is taken to be $x_0 > 2/\alpha$, then $x_i \to -\infty$ as $i\to \infty$.

   3. If $0 < x_0 < 2/\alpha$ then one can show the algorithm converges. In order to meet this condition, we need to pick $x_0<2/\alpha$ without dividing by $\alpha$ (that would defeat the purpose). We can make a valid guess using the formula
      x_0 = pow2(-ceil(log2(alpha)))
      (why might this be computationally efficient for IEEE floating point numbers?) and then run Newton's method.

      Using this guess and the algorithm above, write code in MATLAB which computes $1/\alpha$, $\alpha >0$ to machine precision. Give the answer for $\alpha = 3$ and $\alpha = 5$ and state the number of iterations required to converge for each.

3. Give an example of a function $f(x)$ for which the Secant method performs better than Newton's method for any initial guesses. Explain why this is the case, and back up your claim with numerical evidence.

4. This problem explores circumstances where the order of convergence for Newton's method may be higher or lower than $2$. In all of what follows, we will suppose that $f(x)$ has a root $\bar{x}$ in the interval $[a,b]$ and that $f$ has infinitely many continuous derivatives on $[a,b]$ with $f^\prime(x) \neq 0$ for all $x\in [a,b]$.

   1. Suppose that the second derivative satisfies $f^{\prime\prime}(\bar{x}) = 0$ and $f^{\prime\prime}(x) \neq 0$ for all other $x\in[a,b]$ and that the third derivative satisfies $f^{\prime\prime\prime}(x) \neq 0$ for all $x\in [a,b]$. Use Taylor series to show that the ith error $e_i = x_i -\bar{x}$ satisfies \[ e_i - \frac{f(x_i)}{f^\prime(x_i)} = \frac{1}{3}\frac{f^{\prime\prime\prime}(\bar{x})}{f^\prime(\bar{x})}e_i^3 + \mathcal{O}(e_i^{4}). \]

      What does this imply is the order of convergence for Newton's method applied to $f$?

   2. Suppose that first derivative satisfies $f^{\prime}(\bar{x}) = 0$, $f^{\prime}(x) \neq 0$ for all other $x\in[a,b]$ and that the second derivative satisfies $f^{\prime\prime}(x) \neq 0$ for all $x\in [a,b]$. Use Taylor series to show that the ith error $e_i = x_i -\bar{x}$ satisfies \[ e_i - \frac{f(x_i)}{f^\prime(x_i)} = \frac{1}{2}e_i + \mathcal{O}(e_i^{2}). \]

      What does this imply is the order of convergence for Newton's method applied to $f$?

5. It is not uncommon in practice to solve a problem involving a composite function. Suppose one wants to find the values of $x$ where $f(x)= 0$. However, $f$ is given in terms of $y$ and there is a second equation that determines the value of $y$ for any given value of $x$. Specifically, suppose that \[ f(y) = y^3 + 3y +1,\quad\text{and}\quad y+ x = e^{-6y}. \] Given $x$, to evaluate $f$, one must first solve the second equation for $y$ and then substitute this into $f(y)$.

   1. Describe how to use the bisection method to find the value of $x$ where $f=0$. Make sure to explain how to find the initial bracketing interval.
   2. Writing $f$ as $f(y(x))$, explain how to use Newton's method to find the value of $x$ where $f=0$.
   3. Using MATLAB, find the value of $x$ where $f=0$ within machine precision.