Basic, Intermediate and CAS problems

The following is the list of non-advanced problems for Chapter 3 of the class notes. There is a forum open at the end, so you can ask questions. It is a great way to interact with the instructor and with other students in your class, should you need some assistance with any question. Please, do not post solutions.

1. The following sequences all converge to zero. $\begin{align*} v_n &= n^{-10} &w_n &= 10^{-n} &x_n &=10^{-n^2} &y_n &=n^{10}3^{-n} &z_n &=10^{-3\cdot 2^n} \end{align*}$

   Indicate the type of convergence of each sequence.

2. Find an example of a function \( f\colon \mathbb{R} \to \mathbb{R} \) with a unique root at \( x=0 \) for which the Newton-Raphson sequence is a loop no matter the initial guess \( x_0\neq 0 \): \( x_{2n}=x_0 \), \( x_{2n+1}=-x_0 \) for all \( n \in \mathbb{N}. \) Bonus points is your function is trigonometric.

3. Consider the equation \( x = \cos x. \)

   • Show graphically that there exists a unique positive root \( x^\star. \) Indicate approximately where it is located.
   • Show that Newton’s method applied to \( f(x) = x-\cos x \) converges for any initial guess \( x_0 \in \big[0,\frac{\pi}{2}\big]. \)

4. Consider the equation \( \tan x + \lambda x = 0, \quad (0 < \lambda < 1). \)

   • Show graphically, as simply as possible, that there is exactly one root \( x^\star \) in the interval \( \big[ \frac{1}{2}\pi, \pi\big]. \)
   • Does Newton’s method converge to the root \( x^\star \in \big[ \frac{1}{2}\pi, \pi\big] \) if the initial approximation is taken to be \( x_0 = \pi \)? Justify your answer.

5. Consider the equation \( \log^2 x - x -1 = 0, (x > 0). \)

   • Graphical considerations suggest that there is exactly one positive solution \( x^\star \), and that \( 0 <x^\star < 1. \) Prove this.
   • What is the largest positive \( 0<x_0\leq 1 \) such that Newton’s method with \( f(x) = \log^2 x - x -1 \) started at \( x_0 \) converges to \( x^\star \)?

6. Consider the two equivalent equations

   $$\begin{align} x\log x -1 &= 0, \\\\ \log x - \frac{1}{x} &= 0. \end{align}$$
   • Show that there is exactly one positive root and find a rough interval containing it.

   • For both equations above, determine the largest interval on which Newton’s method converges.

     Hint: Investigate the convexity of the functions involved.

7. Design a process in desmos.com to test the search for critical points given by the recursion formulas produced by Newton’s method.

   

8. In a computer language or CAS of your choice, design a routine that gathers the following as input:

   • The definition of a generic real-valued function \( f\colon \mathbb{R} \to \mathbb{R}, \)
   • The derivative \( f’ \) of that function,
   • An initial guess \( x_0 \in \mathbb{R}, \)
   • A number \( N \) of steps,

   and produces the first \( N+1 \) terms of the Newton-Raphson sequence to approximate a root of \( f. \)

   Modify the previous routine to receive as input, instead of a number of steps, a tolerance tol indicating the accuracy of the solution. For example, if we require a root of the equation \( f(x)=0 \) accurate to the first 16 correct decimal places, we use tol = 1e-16.

9. The purpose of this problem is the design of Horner’s method to evaluate polynomials effectively. Given a polynomial

   $$p(x) = \sum_{k=0}^n a_k x^k = a_0 + a_1 x + \dotsb + a_n x^n,$$

   where \( a_0, a_1, \dotsc, a_n \) are real numbers, and given \( x_0 \in \mathbb{R} \), we define the Horner’s scheme \( \{ b_0, b_1, \dotsc, b_n \} \) to evaluate \( p(x_0) \) as follows:

   $$\begin{align*} b_n &= a_n \\\\ b_{n-1} &= a_{n-1} + b_n x_0 \\\\ b_{n-2} &= a_{n-2} + b_{n-1} x_0 \\\\ &\vdots \\\\ b_0 &= a_0 + b_1 x_0 \end{align*}$$
   • Prove that \( b_0 = p(x_0) \)
   • Use Horner’s method to evaluate \( p(x) = 2x^3 - 6x^2 +2x -1 \) at \( x=3. \) Illustrate all steps, and count the number of basic operations (addition, subtraction, multiplication, division) used.
   • Employ the usual method of evaluation of polynomials to evaluate \( p(x) = 2x^3 - 6x^2 +2x -1 \) at \( x=3. \) Count the number of basic operations (note that a raising to the cube counts as two multiplications, e.g.)

10. In a computer language or CAS of your choice, write a routine to apply Horner’s scheme to evaluate polynomials. Your routine should gather the following inputs:

    • A list of coefficients [a0, a1, ..., an] representing the polynomial \( p(x) = a_0 + a_1 x + \dotsb + a_n x^n. \)
    • A value x0

    The output of your routine should be \( p(x_0). \)

11. Use any of the routines that you wrote in Problem 8 to produce a table and a visual representation for the numerical solution of the following equations, with the given initial guesses and steps.

    • \( f(x) = \sin x \), with \( x_0=0.5 \), 5 steps.
    • \( f(x) = \sin x \), with \( x=3 \), enough steps to obtain accurately the first 16 correct decimal places of \( \pi. \)
    • \( f(x) = -1+\log x \), with \( x=2 \), enough steps to obtain accurately the first 16 correct decimal places of \( e. \)

12. The objective of this problem is to use Newton’s method to find an approximation to the golden ratio \( \phi=\frac{1}{2}(1+\sqrt{5}) \) accurate to the first 16 decimal places. Find first an appropriate polynomial \( p(x) \) with integer coefficients for which \( \phi \) is a root. Employ any of the routines that you wrote in Problem 9 with a good initial guess to guarantee the required result.

13. Consider the function \( f(x) = 9x -4\log(x-7). \) We wish to study the behavior of Newton-Raphson to find approximations to the critical points of this function.

    • Find the domain \( D \) of \( f. \)
    • Find the global minimum of \( f \) analytically.
    • Compute an exact formula for the Newton-Raphson iterate \( x_{n+1} \) for an initial guess \( x_0 \in D. \)

    • Compute five iterations of the Newton-Raphson method starting at each of the following initial guesses:

      • \( x_0 = 7.4. \)
      • \( x_0 = 7.2. \)
      • \( x_0 = 7.01. \)
      • \( x_0 = 7.8. \)
      • \( x_0 = 7.88. \)
    • Prove that the Newton-Raphson method converges to the optimal solution for any initial guess \( x_0 \in (7,7.8888). \)
    • What is the behavior of the Newton-Raphson method if the initial guess is not in the interval \( (7,7.8888)? \)

14. Consider the function \( f(x) = 6x -4\log(x-2) -3\log(25-x). \) We wish to study the behavior of Newton-Raphson to find approximations to the critical points of this function.

    • Find the domain \( D \) of \( f. \)
    • Find the global minimum of \( f \) analytically.
    • Compute an exact formula for the Newton-Raphson iterate \( x_{n+1} \) for an initial guess \( x_0 \in D. \)

    • Compute five iterations of the Newton-Raphson method starting at each of the following initial guesses:

      • \( x_0 = 2.6. \)
      • \( x_0 = 2.7. \)
      • \( x_0 = 2.4. \)
      • \( x_0 = 2.8. \)
      • \( x_0 = 3. \)
    • Prove that the Newton-Raphson method converges to the optimal solution for any initial guess \( x_0 \in (2,3.05). \)
    • What is the behavior of the Newton-Raphson method if the initial guess is not in the interval \( (2,3.05)? \)

15. Approximate the solution of the following system by computing two steps of Newton-Raphson’s method for an appropriate function \( \boldsymbol{g} \colon \mathbb{R}^3 \to \mathbb{R}^3: \) and initial guess \( \boldsymbol{x}_0 = (1,0,1) \).

    $$\begin{cases} 3 &= x^2 + y^2 + z^2 \\ 1 &= x^2 + y^2 - z \\ 1 &= x + y + z \end{cases}$$

16. The purpose of this exercise is to show that Newton’s method is unaffected by linear scaling of the variables. Consider a linear invertible transformation of variables \( \boldsymbol{x}^\intercal = \boldsymbol{A} \cdot \boldsymbol{y}^\intercal \). Write Newton’s method in the space of the variables \( \boldsymbol{y} \) and show that it generates the sequence \( \boldsymbol{y}_n^\intercal = \boldsymbol{A}^{-1} \cdot \boldsymbol{x}_n^\intercal \), where \( \{ \boldsymbol{x}n \}{n \in \mathbb{N}} \) is the sequence generated by Newton’s method in the space of variables \( \boldsymbol{x} \).

17. Let \( \boldsymbol{A} \) be a square matrix. A LU-decomposition is a factorization of \( \boldsymbol{A}=\boldsymbol{L} \cdot \boldsymbol{U} \) into a lower triangular matrix \( \boldsymbol{L} \) and an upper triangular matrix \( \boldsymbol{U} \), both of which have non-zero entries in their diagonals. For example, the general case for \( 3 \times 3 \) square matrices:

    $$\begin{bmatrix} a_{11} & a_{12} & a_{13} \\\\ a_{21} & a_{22} & a_{23} \\\\ a_{31} & a_{32} & a_{33} \end{bmatrix} = \underbrace{\begin{bmatrix} \ell_{11} & 0 & 0 \\\\ \ell_{21} & \ell_{22} & 0 \\\\ \ell_{31} & \ell_{32} & \ell_{33} \end{bmatrix}}_{\boldsymbol{L}} \cdot \underbrace{\begin{bmatrix} u_{11} & u_{12} & u_{13} \\\\ 0 & u_{22} & u_{23} \\\\ 0 & 0 & u_{33} \end{bmatrix}}_{\boldsymbol{U}}$$
    • Find an LU-decomposition of the following matrix
    $$\begin{bmatrix} 4 & 3 \\\\ 6 & 3 \end{bmatrix}$$

    that satisfies that all diagonal entries of \( \boldsymbol{L} \) are ones.

    • Find an example of a \( 2\times 2 \) square matrix for which there is not any possible LU-decomposition.

18. In a computer language or CAS of your choice, design a routine that solves a linear system

    $$\overbrace{\begin{bmatrix} a_{11} & \dotsb & a_{1d} \\ \vdots & \ddots & \vdots \\ a_{d1} & \dotsb & a_{dd} \end{bmatrix}}^{\boldsymbol{A}} \cdot \overbrace{\begin{bmatrix} x_1 \\ \vdots \\ x_d \end{bmatrix}}^{\boldsymbol{x}^\intercal} = \overbrace{\begin{bmatrix} c_1 \\ \vdots \\ c_d \end{bmatrix}}^{\boldsymbol{c}^\intercal}$$

    by performing first a LU-decomposition \( \boldsymbol{A} = \boldsymbol{L} \cdot \boldsymbol{U} \) (provided this is possible!) and manipulating the resulting equation to solve instead the two (faster) systems:

    • Find \( \boldsymbol{y} \) that solves the system \( \boldsymbol{L}\cdot \boldsymbol{y}^\intercal = \boldsymbol{c}^\intercal \) by Gaussian elimination.
    • Find \( \boldsymbol{x} \) that solves the system \( \boldsymbol{U}\cdot \boldsymbol{x}^\intercal = \boldsymbol{y}^\intercal \) by Gaussian elimination.

    You may design a routine that computes LU-decompositions, or you may use a built-in routine for that purpose.

19. In a computer language or CAS of your choice, design a routine that gathers the following as input:

    • The definition of a generic real-valued function \( f\colon \mathbb{R}^d \to \mathbb{R}, \)
    • The gradient \( \nabla f \) of that function,
    • An initial guess \( \boldsymbol{x}_0 \in \mathbb{R}, \)
    • A number \( N \) of steps,

    and produces the first \( N+1 \) terms of the Newton-Raphson sequence to approximate a root of \( f. \)

20. Approximate the solution for the system in Problem 15 by computing the first two iterations of a Broyden method with \( \boldsymbol{A}_0 = \nabla \boldsymbol{g} (\boldsymbol{x}_0) \) for an appropriate function \( \boldsymbol{g} \colon \mathbb{R}^d \to \mathbb{R} \) and initial guess \( \boldsymbol{x}_0 = (1,0,1). \)

21. Compute the first two iterations of Broyden method with initial guess \( (1,4) \) to search for the critical points of the function \( f(x,y) = 2x^2+y^2-xy \)

    • Using \( \boldsymbol{A}_0 = \begin{bmatrix} 1 & 0 \ 0 & 1 \end{bmatrix}. \)
    • using \( \boldsymbol{A}_0 = \mathrm{Hess} f(1,4). \)

22. Approximate the solution for the system in Problem 15 by computing the first two iterations of a Broyden method for an appropriate function \( \boldsymbol{g} \colon \mathbb{R}^d \to \mathbb{R} \) and initial guess \( \boldsymbol{x}_0 = (1,0,1). \)

23. Compute the first two iterations of the method of Steepest descent with initial guess \( (1,4) \) to search for the critical points of the function \( f(x,y) = 2x^2+y^2-xy. \)

24. Consider the quadratic polynomial \( p(x,y) = \tfrac{1}{2} \mathcal{Q}_{\boldsymbol{Q}}(x,y) + \langle D, [x,y] \rangle + 13, \) with

    $$\begin{align*} D &= [4, -15], & Q &= \begin{bmatrix} 10 & -9 \\\\ -9 & 10 \end{bmatrix} \end{align*}$$
    • Find the global minimum value of \( p \), and its location.
    • Compute the eigenvalues of \( Q \). Is \( Q \) positive definite?
    • What is the worst-case scenario rate of convergence of sequences of steepest descent for this function?

    • Compute sequences of steepest descent for this function with the initial guesses below.

      • \( (0,0) \)
      • \( (-0.4, 0) \)
      • \( (10,0) \)
      • \( (11, 0) \)

25. Consider the quadratic polynomial \( p(x,y,z) = \tfrac{1}{2} \mathcal{Q}_{\boldsymbol{Q}}(x,y,z) + \langle D, [x,y,z] \rangle, \) with

    $$\begin{align*} D &= [12, -47, -8], & Q &= \begin{bmatrix} 10 & -18 & 2 \\\\ -18 & 40 & -1 \\\\ 2 & -1 & 3 \end{bmatrix} \end{align*}$$
    • Find the global minimum value of \( p \), and its location.
    • Compute the eigenvalues of \( Q \). Is \( Q \) positive definite?
    • What is the worst-case scenario rate of convergence of sequences of steepest descent for this function?

    • Compute sequences of steepest descent for this function with the initial guesses below.

      • \( (0,0,0) \)
      • \( (15.09, 7.66, -6.56) \)
      • \( (11.77, 6.42, -4.28) \)
      • \( (4.46, 2.25, 1.85) \)