Question

Q3

Preliminary material The homework assignment is found on the next page. Our goal in this homework is to develop an algorithm for solving equations of the form f (x) (1) = X where f is a function S S, for some S C R". This kind of problem is sometimes called 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: a Step 0. Pick any point Xo E S Step 1. Define x1 f(X0) f(x1) Step 2. Define x2 that at the jth step, and in general, iterate this procedure, So Step j. Define x = f(xj-1) This procedure generates a sequence {x} in S. In the exercises, you will show that if we make an appropriate assumption about f and S, then {xj} converges to a limit x and the limit solves problem (1). We will see later in the course how we can use the results of this and a future homework assignment to prove the Inverse Function Theorem, one of the major theorems in the theory of multivariable calculus The exercises on the next page will prove the following theorem. S is a function with the Theorem 1. Assume that S C R" is closed, and that f S following property: |f(x) f(y)plx - y for all x, y S (2) there exists pE (0, 1) such that Then the fixed point problem (1) has exactly one solution in S, and for any choice of starting point xo E S, the sequence generated by the above algorithm converges to this same solution A function that satisfies (2) is sometimes called a contraction mapping, and Theorem 1 is called the Contraction Mapping Principle. (In fact, Theorem 1 is a special re general theorem of the same name.) One particular example of a function f that satisfies (2) is the functionf : R R given by f(x) pa, where p e (0, 1). Before proceeding to the homework assignment, it may be helpful to consider problem (1), and to explicitly find the sequence x}j as defined above (with ro 1 for example), for this particular function. This does not need to be turned in case of a = 2 a. For every j 2 1 define Di Fix anyj 1 and prove that di 1- P for every k > j, X-xDi (Xk Xk-1)(xk-1Xk-2) +(xj41-x) Hint: If k > j, then x X = b. Prove that the sequence {x;}j has a convergent subsequence. For future use, let {x,}/ denote the convergent subsequence, and let x, denote its limit B(Dj,x)nS {x e S x - xjl D,}. Note that 3. For any j 2 1 define Bj Problem (2a) says that x E Bj whenever k > j. a. For arbitrary j E N, prove that x. E Bi (where x. is the limit of the convergent subsequence) b. Prove that the whole sequence {xj}j converges to x. (not just the subsequence