Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

MATH-UA 252 - Spring ‘23 - Numerical Analysis - HW #1

Problem 1.    A fixed point iteration is an iteration of the form:

xn+1  = f (xn ),                                                                                (1)

where f  : R  → R.   A function  f  is said to be Lipschitz continuous with constant L  ≥ 0 on the interval [a, b] ⊆ R if, for every x, y ∈ [a, b], we have:

|f (x) − f (y)| ≤ L|x − y|.                                                                      (2)

Assume that f has the fixed point x*  ∈ [a, b].

1.  Prove that if x0  ∈ [a, b], if f ([a, b]) ⊆ [a, b], and f is Lipschitz with L < 1 on [a, b] then the fixed point iteration (1) converges to x.

2.  Prove that the relative error at the nth iteration satisfies:

|xn  − x* | ≤ Ln |x0  − x* |.                                                                  (3)

What is the order and rate of convergence of the sequence {xn  − x* }?

3.  Show that the number of iterations needed for a relative error smaller than ϵ > 0 is at least logL (ϵ).

4.  The number of digits of relative precision p for a relative error tolerance ϵ > 0 is:

p(ϵ) = log10 (1/ϵ).                                                                        (4)

Show that logL (ϵ) ∝ p(ϵ) (this means that there is some constant C such that logL (ϵ) = Cp(ϵ)). What is the constant of proportionality C?

5.  Write down a 10 × 10 table with rows corresponding to values of L and columns corresponding to values of p(ϵ), and with table values given by the number of iterations required to achieve the given relative precision for that particular Lipschitz constant L. Try to choose values of p and L which are the most interesting and informative.

6.  Summarize your results and write any observations about the fixed point iteration that you have made based on the previous parts of this exercise.

7.  The Babylonian algorithm is a fixed point iteration. How does its order of convergence relate to what you have found in this problem? Are there any discrepancies?  How do you account for them?

Problem 2.    Another algorithm for solving rootfinding problems is called bisection.  Assume that f has a single root x*  ∈ [a, b], and that f ∈ C0 ([a, b]) (that is, f is continuous on [a, b]). Bisection works by initially setting x0  = a and x1  = b.  Let an  = min(xn , xn+1) and bn  = max(xn , xn+1).  For each n ≥ 0, we want to maintain the invariant:

an  ≤ x*  ≤ bn                                                                                                                       (5)

Note that this implies that if x*   xn  and x*   xn+1, that either f (xn ) < 0 and f (xn+1) > 0, or f (xn ) > 0 and f (xn+1) < 0.

1.  Complete this idea by writing down an algorithm which repeatedly computes the midpoint of xn  and xn+1, giving the bisection iteration.  (It may help to draw a picture.)

2.  What is the rate and order of convergence of the sequence {xn  − x* }?

Problem  3.    Yet another algorithm for solving rootfinding problems is the  Secant method, where after choosing 北0  and 北1 , we iterate:

北n+2  = 北n+1  − f(北n(北)1(+)1)  f(北)北n ) f(北n+1),    n ≥ 0.                      (6)

1.  This algorithm can be derived by repeatedly finding where the line passing through  (北n , f(北n )) and (北n+1, f(北n+1) passes through the 北-axis.  Prove this.

2.  Draw a picture illustrating this iteration applied to the problem of computing 北 = ^y for y = 2.

Problem 4.    So far we’ve seen four different methods which can be used to solve 1D nonlinear equations: the fixed point iteration, the secant method, Newton’s method, and bisection.  The problem of computing 北 = ^y is equivalent to solving a 1D nonlinear equation.  We saw in class that applying Newton’s method to its solution results in the Babylonian algorithm, which is a fixed point iteration.

1.  Derive the secant method iteration for computing 北 = ^y.

2.  Write  Python  code  to  compute  北 =  ^y using  the  Babylonian  algorithm,  the  secant  method,  and bisection.

3.  Compare each of your three iterations by computing the square root of five different numbers of your choice.  Collect the following data:

(a)  The number of floating-point operations used to compute the square root by the entire iteration until convergence.

(b)  The relative error |北n  − 北* |/|北0  − 北* |.

You will have to decide the best way to judge when the iteration has “converged”.

4.  Compare and contrast the different methods. Do they always work? Do they work better or worse for different regions?