MATH 524 Fall 17 Chapter 3
Basic, Intermediate and CAS problems

The following sequences all converge to zero.
Indicate the type of convergence of each sequence.

Find an example of a function \( f\colon \mathbb{R} \to \mathbb{R} \) with a unique root at \( x=0 \) for which the NewtonRaphson 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.

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]. \)

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.

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 \)?

Consider the two equivalent equations
 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.

Design a process in
desmos.com
to test the search for critical points given by the recursion formulas produced by Newton’s method. 
In a computer language or CAS of your choice, design a routine that gathers the following as input:
 The definition of a generic realvalued 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 NewtonRaphson 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 usetol = 1e16
. 
The purpose of this problem is the design of Horner’s method to evaluate polynomials effectively. Given a polynomial
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:
 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.)

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). \)
 A list of coefficients

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. \)

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.

Consider the function \( f(x) = 9x 4\log(x7). \) We wish to study the behavior of NewtonRaphson 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 NewtonRaphson iterate \( x_{n+1} \) for an initial guess \( x_0 \in D. \)

Compute five iterations of the NewtonRaphson 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 NewtonRaphson method converges to the optimal solution for any initial guess \( x_0 \in (7,7.8888). \)
 What is the behavior of the NewtonRaphson method if the initial guess is not in the interval \( (7,7.8888)? \)

Consider the function \( f(x) = 6x 4\log(x2) 3\log(25x). \) We wish to study the behavior of NewtonRaphson 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 NewtonRaphson iterate \( x_{n+1} \) for an initial guess \( x_0 \in D. \)

Compute five iterations of the NewtonRaphson 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 NewtonRaphson method converges to the optimal solution for any initial guess \( x_0 \in (2,3.05). \)
 What is the behavior of the NewtonRaphson method if the initial guess is not in the interval \( (2,3.05)? \)

Approximate the solution of the following system by computing two steps of NewtonRaphson’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) \).

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} \).

Let \( \boldsymbol{A} \) be a square matrix. A LUdecomposition 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 nonzero entries in their diagonals. For example, the general case for \( 3 \times 3 \) square matrices:
 Find an LUdecomposition of the following matrix
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 LUdecomposition.

In a computer language or CAS of your choice, design a routine that solves a linear system
by performing first a LUdecomposition \( \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 LUdecompositions, or you may use a builtin routine for that purpose.

In a computer language or CAS of your choice, design a routine that gathers the following as input:
 The definition of a generic realvalued 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 NewtonRaphson sequence to approximate a root of \( f. \)

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). \)

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^2xy \)
 Using \( \boldsymbol{A}_0 = \begin{bmatrix} 1 & 0 \ 0 & 1 \end{bmatrix}. \)
 using \( \boldsymbol{A}_0 = \mathrm{Hess} f(1,4). \)

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). \)

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^2xy. \)

Consider the quadratic polynomial \( p(x,y) = \tfrac{1}{2} \mathcal{Q}_{\boldsymbol{Q}}(x,y) + \langle D, [x,y] \rangle + 13, \) with
 Find the global minimum value of \( p \), and its location.
 Compute the eigenvalues of \( Q \). Is \( Q \) positive definite?
 What is the worstcase 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) \)

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
 Find the global minimum value of \( p \), and its location.
 Compute the eigenvalues of \( Q \). Is \( Q \) positive definite?
 What is the worstcase 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) \)