Chapter 3

Apply the bisection routine bisect to find the root of the function $$ f(x)=\sqrt{x}-1.1 $$ starting from the interval \([0,2]\) (that is, \(a=0\) and \(b=2\) ), with atol \(=1 . \mathrm{e}-8\). (a) How many iterations are required? Does the iteration count match the expectations, based on our convergence analysis? (b) What is the resulting absolute error? Could this absolute error be predicted by our convergence analysis?

Consider the polynomial function \(^{8}\) $$ \begin{aligned} f(x)=&(x-2)^{9} \\ =& x^{9}-18 x^{8}+144 x^{7}-672 x^{6}+2016 x^{5}-4032 x^{4}+5376 x^{3}-4608 x^{2} \\ &+2304 x-512 . \end{aligned} $$ (a) Write a MATLAB script which evaluates this function at 161 equidistant points in the interval \([1.92,2.08]\) using two methods: i. Apply nested evaluation (cf. Example 1.4) for evaluating the polynomial in the expanded form \(x^{9}-18 x^{8}+\cdots\) ii. Calculate \((x-2)^{9}\) directly. Plot the results in two separate figures. (b) Explain the difference between the two graphs. (c) Suppose you were to apply the bisection routine from Section \(3.2\) to find a root of this function, starting from the interval \([1.92,2.08]\) and using the nested evaluation method, to an absolute tolerance \(10^{-6}\). Without computing anything, select the correct outcome: i. The routine will terminate with a root \(p\) satisfying \(|p-2| \leq 10^{-6}\). ii. The routine will terminate with a root \(p\) not satisfying \(|p-2| \leq 10^{-6}\). iii. The routine will not find a root. Justify your choice in one short sentence.

Consider the fixed point iteration \(x_{k+1}=g\left(x_{k}\right), k=0,1, \ldots\), and let all the assumptions of the Fixed Point Theorem hold. Use a Taylor's series expansion to show that the order of convergence depends on how many of the derivatives of \(g\) vanish at \(x=x^{*}\). Use your result to state how fast (at least) a fixed point iteration is expected to converge if \(g^{\prime}\left(x^{*}\right)=\cdots=\) \(g^{(r)}\left(x^{*}\right)=0\), where the integer \(r \geq 1\) is given.

Consider the function \(g(x)=x^{2}+\frac{3}{16}\). (a) This function has two fixed points. What are they? (b) Consider the fixed point iteration \(x_{k+1}=g\left(x_{k}\right)\) for this \(g .\) For which of the points you have found in (a) can you be sure that the iterations will converge to that fixed point? Briefly justify your answer. You may assume that the initial guess is sufficiently close to the fixed point. (c) For the point or points you found in (b), roughly how many iterations will be required to reduce the convergence error by a factor of \(10 ?\)

(a) Derive a third order method for solving \(f(x)=0\) in a way similar to the derivation of Newton's method, using evaluations of \(f\left(x_{n}\right), f^{\prime}\left(x_{n}\right)\), and \(f^{\prime \prime}\left(x_{n}\right) .\) The following remarks may be helpful in constructing the algorithm: \- Use the Taylor expansion with three terms plus a remainder term. \- Show that in the course of derivation a quadratic equation arises, and therefore \(t\) wo distinct schemes can be derived. (b) Show that the order of convergence (under the appropriate conditions) is cubic. (c) Estimate the number of iterations and the cost needed to reduce the initial error by a factor of \(10^{m}\). (d) Write a script for solving the problem of Exercise \(5 .\) To guarantee that your program does not generate complex roots, make sure to start sufficiently close to a real root. (e) Can you speculate what makes this method less popular than Newton's method, despite its cubic convergence? Give two reasons.

Consider Steffensen's method $$ x_{k+1}=x_{k}-\frac{f\left(x_{k}\right)}{g\left(x_{k}\right)}, \quad k=0,1, \ldots, $$ where $$ g(x)=\frac{f(x+f(x))-f(x)}{f(x)} $$ (a) Show that in general the method converges quadratically to a root of \(f(x)\). (b) Compare the method's efficiency to the efficiency of the secant method.

It is known that the order of convergence of the secant method is \(p=\frac{1+\sqrt{5}}{2}=1.618 \ldots\) and that of Newton's method is \(p=2\). Suppose that evaluating \(f^{\prime}\) costs approximately \(\alpha\) times the cost of approximating \(f\). Determine approximately for what values of \(\alpha\) Newton's method is more efficient (in terms of number of function evaluations) than the secant method. You may neglect the asymptotic error constants in your calculations. Assume that both methods are starting with initial guesses of a similar quality.

This exercise essentially utilizes various forms of Taylor's expansion and relies on expertise in calculus. (a) Prove that if \(f \in C^{2}[a, b]\) and there is a root \(x^{*}\) in \([a, b]\) such that \(f\left(x^{*}\right)=0, f^{\prime}\left(x^{*}\right) \neq 0\), then there is a number \(\delta\) such that, starting with \(x_{0}\) from anywhere in the neighborhood \(\left[x^{*}-\delta, x^{*}+\delta\right]\), Newton's method converges quadratically. (b) This is more challenging: prove the same conclusions under the same assumptions, except that now \(f\) is only assumed to have a first Lipschitz continuous derivative. Thus, while \(f^{\prime \prime}\) may not exist everywhere in \([a, b]\), there is a constant \(\gamma\) such that for any \(x, y \in[a, b]\) $$ \left|f^{\prime}(x)-f^{\prime}(y)\right| \leq \gamma|x-y| . $$

Given \(a>0\), we wish to compute \(x=\ln a\) using addition, subtraction, multiplication, division, and the exponential function, \(e^{x}\). (a) Suggest an iterative formula based on Newton's method, and write it in a way suitable for numerical computation. (b) Show that your formula converges quadratically. (c) Write down an iterative formula based on the secant method. (d) State which of the secant and Newton's methods is expected to perform better in this case in terms of overall number of exponential function evaluations. Assume a fair comparison, i.e., same floating point system, "same quality" initial guesses, and identical convergence criterion.

Write a MATLAB program to find all the roots of a given, twice continuously differentiable, function \(f \in C^{2}[a, b]\). Your program should first probe the function \(f(x)\) on the given interval to find out where it changes sign. (Thus, the program has, in addition to \(f\) itself, four other input arguments: \(a\), \(b\), the number \(n\) probe of equidistant values between \(a\) and \(b\) at which \(f\) is probed, and a tolerance tol.) For each subinterval \(\left[a_{i}, b_{i}\right]\) over which the function changes sign, your program should then find a root as follows. Use either Newton's method or the secant method to find the root, monitoring decrease in \(\left|f\left(x_{k}\right)\right| .\) If an iterate is reached for which there is no sufficient decrease (e.g., if \(\left|f\left(x_{k}\right)\right| \geq 0.5\left|f\left(x_{k-1}\right)\right|\) ), then revert back to \(\left[a_{i}, b_{i}\right]\), apply three bisection steps and restart the Newton or secant method. The \(i\) th root is deemed "found" as \(x_{k}\) if both $$ \left|x_{k}-x_{k-1}\right|<\operatorname{tol}\left(1+\left|x_{k}\right|\right) \quad \text { and } \quad\left|f\left(x_{k}\right)\right|<\text { tol } $$ hold.

Find all the roots of the function $$ f(x)=\left\\{\begin{array}{ll} \frac{\sin (x)}{x}, & x \neq 0 \\ 1, & x=0 \end{array}\right. $$ in the interval \([-10,10]\) for tol \(=10^{-7}\). [This function is special enough to have a name. It is called the sinc function.]

For \(x>0\) consider the equation \(x+\ln x=0\) It is a reformulation of the equation of Example \(3.4\). (a) Show analytically that there is exactly one root, \(0

We saw in Example \(3.5\) that the function $$ f(x)=\alpha \cosh (x / 4)-x $$ has two roots for \(\alpha=2\) and none for \(\alpha=10\). Is there an \(\alpha\) for which there is precisely one root? If yes, then find such an \(\alpha\) and the corresponding root; if not, then justify.

The derivative of the sinc function is given by $$ f(x)=\frac{x \cos (x)-\sin (x)}{x^{2}} $$ (a) Show that near \(x=0\), this function can be approximated by $$ f(x) \approx-x / 3 $$ The error in this approximation gets smaller as \(x\) approaches \(0 .\) (b) Find all the roots of \(f\) in the interval \([-10,10]\) for tol \(=10^{-8}\).

You are required by a computer manufacturer to write a library function for a given floating point system to find the cube root \(y^{1 / 3}\) of any given positive number \(y .\) Any such relevant floating point number can be represented as \(y=a \times 2^{e}\), where \(a\) is a normalized fraction \((0.5 \leq a<1)\) and \(e\) is an integer exponent. This library function must be very efficient and it should always work. For efficiency purposes it makes sense to store some useful constants ahead of computation time, e.g., the constants \(2^{1 / 3}, \frac{2}{3}\), and \(a / 3\), should these prove useful. (a) Show how \(y^{1 / 3}\) can be obtained, once \(a^{1 / 3}\) has been calculated for the corresponding fraction, in at most five additional flops. (b) Derive the corresponding Newton iteration. What is the flop count per iteration? (c) How would you choose an initial approximation? Roughly how many iterations are needed? (The machine rounding unit is \(2^{-52}\).) [You might find this exercise challenging.]

Suppose that the division button of your calculator has stopped working, and you have addition, subtraction, and multiplication only. Given a real number \(b \neq 0\), suggest a quadratically convergent iterative formula to compute \(\frac{1}{b}\), correct to a user-specified tolerance. Write a MATLAB routine that implements your algorithm, using \(\left|x_{k}-x_{k-1}\right|<10^{-10}\) as a convergence criterion, and apply your algorithm to \(b=\pi\) (that is, we compute \(\frac{1}{\pi}\) ), with two different initial guesses: (a) \(x_{0}=1\); and (b) \(x_{0}=0.1\). Explain your results.

Use your program from Exercise 21 to minimize (a) \(\phi(x)=\sin (x)\) and (b) \(\phi(x)=-\operatorname{sinc}(x)=-\frac{\sin (x)}{x}\) over the interval \([-10,10]\) with tol \(=10^{-8}\). You might find that determining the global minimum of the second function is significantly more challenging, even though the global minimum for the first one is not unique. Explain the source of difficulties and how you have addressed them. [Exercises 17 and 14 are relevant here.]