ICSI401 Homework 3-More root finding and related topics Solved

3.1         More root finding and related topics
•    This question will test your understanding of the intermediate value theorem, which you will recall is the theorem that motivates bisection search.

Consider the following function f(x):

                                                                                                                                               (3.1)

(This notation is standard and means that f(x) = x whenever x < −1/2 and f(x) = x + 2 whenever x > −1/2.)

Note that f(x) is defined for every real x, but it has no roots. That is, there is no x∗ such that f(x∗) = 0. Nonetheless, we can find an interval [a,b] such that f(a) < 0 < f(b): just choose a = −1,b = 1. Why can’t we use the intermediate value theorem to conclude that f has a zero in the interval [−1,1]?

•    This question will test your understanding of the limitations of bisection search and Newton’s method. Consider the function .

–    Can we use bisection search to find one of its roots? Why or why not?

–    Can we use Newton’s method to find one of its roots? Why or why not?

3.2        Fixed point iteration
•    Complete problem 4.7.12 in the textbook. This will test your knowledge of what a fixed point of a function is, how to find them, and how to determine when iteration will converge to a fixed point.

3-1

3-2

•    Application question. Here’s how this works: You get full points for a reasonable attempt. So you MUST attempt this question. You get extra credit if you’re correct. This question presents a simple model of population dynamics, and analyzes its equilibrium states. Models like this, but more complicated, can be used to predict global population trends, for instance.

Let Nt denote the number of individuals in a population at time t. We will assume that Nt

evolves at each time step according to the following equation:
 
Nt+1 = Nt + rNt(1 − Nt/K),
(3.2)
where

–    r is the birth minus death rate (per existing individual) parameter. Let us assume that it is larger than 0.

–    K is a positive constant representing fundamental resource limitations for the population. For example, on Earth, there is only a finite amount of of consumable biomass, and so the number of humans on Earth probably cannot grow to infinity. Note that when Nt > K, we have Nt+1 − Nt < 0.

Supposing we start with some initial population N0, we can calculate Nt as follows:

–    Define F(x) = x + rx(1 − x/K).

–    Define x = N0.

–    Compute Nt = F ◦ F ◦ ... ◦ F(x), where F is applied t times.

Now, we want to determine cases where this process converges. Suppose r > 0 and K > 0 are fixed.

–    Determine all non-negative values of x for which F is a contraction.

Hints: Recall that we say that a function F is a contraction if its Lipschitz constant L is strictly less than 1. In other words:

                                                                                          |F(z) − F(z0)| 6 L · |z − z0|                                                        (3.3)

for all z,z0 > 0. Remember that you can get an upper bound on L by upper bounding |F0(z)| for every z.

You should get an answer of the form “x > g(K)” for some explicit function g that you have to determine.

–    Suppose that x 6 K. Show that F(x) > x.

–    Suppose that x > K. Show that F(x) < x.

–    What we’ve shown, then, is that F is a contraction on the interval (g(K),∞), and, furthermore, if we fix any L > g(K), U > K > L, then F maps any value y ∈ [L,U] to some value F(y) ∈ [L,U]. Thus, by Banach’s fixed point theorem, we can conclude that F has a unique fixed point x∗ in the interval [L,U], and iterated application of F converges to x∗. Here, x∗ is the limiting population size!

Furthermore, since K is guaranteed to be in [L,U], we see that x∗ = K. That is, if we start at any positive population size > g(K), the population will eventually converge to K (in fact, with more work, one can show that this happens for any positive initial 3-3

population size). This makes intuitive sense: remember that K represents the resource constraints on the population, so this says that the population will converge to the capacity of its environment.

You don’t have to do anything for this bullet point. Just make sure that you understand it!

3.3         Condition numbers and algorithmic stability
Recall that the relative condition number κ(x) of a function f(x) is approximately the factor by which a relative error in the input gets magnified in the relative error in the output. I.e., if x is perturbed to ˆx, then

                                                                          .                                                               (3.4)

We gave a formula for κ(x) in class, and it also appears in the textbook.

•    Qualitatively speaking, if the relative condition number of a function is large, does this make the function ill-conditioned, or well-conditioned (choose one)?

•    Suppose that a problem has a very small condition number for a given input, but the relative error of the output of an algorithm for the problem is large. Is this the fault of the problem or of the algorithm (choose one)?

•    Complete problem 6.3.5 on compound interest in the textbook, and make sure that you understand how they derived In(x). Also, note that limn→∞ In(x) = ex.

For part (d), demonstrate your method in Matlab.

3.4        Some numerical linear algebra
•    This problem will teach you how to work with the LU decomposition of a matrix programmatically to solve a linear system.

The Matlab function lu(A) returns [L, U, P], where L is a lower triangular matrix, U is an upper triangular matrix, and P is a permutation matrix, such that

                                                                                                     A = PTLU.                                                                              (3.5)

Complete the following code to produce a solution to the equation Ax = b, without multiplying the input matrices.

function x = solve_with_LU(L, U, P, b)

%

% Given a lower triangular matrix L, an upper triangular matrix U,

% a permutation matrix P, and a vector b,

% return a solution to the equation P’LUx = b.

%

3-4

z = P’\b y = %FILL THIS IN!

x = %FILL THIS IN! end

•    In Matlab, compute the matrices P, L, and U from the LU decomposition of the matrix

                                                                                                                                                                    (3.6)

and use the completed function above to obtain the solution to the system Ax = b, where

                                                                                                                                                                                      (3.7)

Please note that you have to turn in Matlab code for this question, including the completed version of the function above.