MAT237Y, University of Toronto, 2017-8 Homework Assignment # 2 Preliminary material The homework assignment is found on the other side of this page. Our goal in this homework is to develop an algorithm for solving equations of the form (1) f (x) = x where f is a function S S, for some S Rn . This kind of problem is sometimes called a fixed point problem, and a solution x of problem (1) is called a fixed point of f . The algorithm we will consider is the following: Step 0. Pick any point x0 S. Step 1. Define x1 = f (x0 ). Step 2. Define x2 = f (x1 ). and in general, iterate ths procedure, so that at the jth step, Step j. Define xj = f (xj1 ). Thus, this procedure generates a sequence {xj } j=0 in S. In the exercises, you will show that if we make an appropriate assumption about the function f , then the sequence {xj } converges to a limit x, and the limit solves problem (1). That is, you will prove the following. Theorem 1. Assume that S Rn , and that f : S S is a function with the following property: (2) there exists (0, 1) such that |f (x) f (y)| |x y| for all x, y S. Also assume that S is closed. Then the fixed point problem (1) has exactly one solution in S, and for any choice of the starting point x0 S, the sequence generated by the above algorithm converges to that solution. A function that satisfies (2) is sometimes called a contraction mapping, and Theorem 1 is therefore called the Contraction Mapping Principle. (In fact, Theorem 1 is a special case of a more general theorem of the same name.) One particular example of a function f that satisfies (2) is the function f : R1 R1 given by f (x) = x, where (0, 1). Before proceeding to the homework assignment, it may be helpful to consider problem (1), and to explicitly find the sequence {xj } as defined above (with x0 = 1 for example), for this particular function. This does not need to be turned in. 1 2 Homework assignment. Now assume that S Rn is closed and that f : S S satisfies property (2) on the previous page. Thus f and S satisfy the hypotheses of Theorem 1. Pick some x0 S, and let {xj } be the sequence obtained from the algorithm above starting at x0 . The function f and the sequence {xj } are considered to be fixed, for the problems below. 1. For the sequence {xj } defined above, define r0 := |x1 x0 |. a. Prove that for every j 1, |xj+1 xj | rj := j r0 . b. Prove that for every j 1, for every k > j, xk B(Rj , xj ) for Rj := rj . 1 2. Prove that the sequence {xj } has a convergent subsequence. 3. For the sequence {xj } defined above, let {xjk } denote a convergent subsequence (which exists by problem (2) above), and let x denote its limit. a. Prove that, for any fixed j N, it must be true that r0 as in problem 1 above. |xj x| Rj , where Rj = j 1 (Note, this is the same as saying that x B(Rj , xj ), i.e. the closure of the ball from Problem 1b.) b. Prove that the whole sequence {xj } converges to x (not just the subsequence {xjk }). Hint: In parts of this exercise, it is useful to think that j is a fixed number, but jk denotes a sequence that is tending to . 4. So far we know that the sequence found by our algorithm satisfies xj x for some limit x. a. Prove that x S and show that x solves the equation (3) f (x) = x. (If you wish to use continuity of f in your solution, you must prove it.) b. Explain why there can only be one solution of the equation. Hint for (b): It suffices to prove that if x and y both solve (3), then |x y| = 0. What do you know about f that can help you do this