Math 170B HW #1 Partial Solutions
=================================

1a. g(x) = x - x^2 + 2.  g(p) = p is equivalent to f(p) = 0.
    h(x) = x + x^2 - 2.  h(p) = p is equivalent to f(p) = 0.

1b. g(x) = x + sinx - xcosx.  g(p) = p is equivalent to f(p) = 0.
    h(x) = x - sinx + xcosx.  h(p) = p is equivalent to f(p) = 0.


2a. There are three fixed points at x = -1, 0, 1.

2b. There are two fixed points at x = -1, 1.

2c. There is one fixed point at x = 0.


3a. g(2) = 0 so g(x) is not in [1,2].

3b. g(x) is in [1,2] since the absolute max and min on that interval 
    are 2 and 1 respectively. (Check this!)

3c. g(1) = 1/2 and g(2) = 4 so g(x) is not in [1,2].


(For #4abc I used the MATLAB routine given in #8)
4a. p_5 = 0.97857206208770.
    p_10 = 0.99932332750265.
    p_15 = 0.99997884705049.

4b. p_5 = 1.02189714865412.
    p_10 = 1.00067713069307.
    p_15 = 1.00002115339696.

4c. p_5 = 0.76819583128202.
    p_10 = 0.73500630901484.
    p_15 = 0.73964996276966.


5a. g(1.4) and g(1.45) are in [1.4, 1.45] and g'(x) = 0 at x = sqrt(2) which is 
    in [1.4, 1.45]. 

5b. g''(x) = 2/x^3 > 0 for all x in [1.4, 1.45] which means that g' is increasing 
    in [1.4, 1.45]. g'(1.4) = -0.0102041 and g'(1.45) = 0.0243757 so we have that 
    k = g'(1.45) = 0.0243757. 

5c. Use the formula from Corollary 2.4 that says |p_n - p| <= k^n max{p_0 - a, b - p_0}.
    It turns out that we need n = 6 iterations.    

(I used the MATLAB routine given #8)
5d. p_3 = 1.41421356237309 and the absolute error is 5.107025913275720e-015.


6. If |g'(p)| < 1, then there exists some M, 0 < M < 1, such that |g'(p)| <= M < 1.
   Let n = (1-M)/2 (note n > 0). Since g'(x) is continuous at p, there exists an 
   e > 0 such that |g'(x) - g'(p)| < n if |x - p| < e. This means, |g'(x) - g'(p)| < n 
   for all x in [p-e, p+e]. Next, we can simplify |g'(x) - g'(p)| < n to be 

             -n < g'(x) - g'(p) < n           for all x in [p-e, p+e]

         g'(p) - n < g'(x) < g'(p) + n        for all x in [p-e, p+e].

   But since |g'(p)| <= M, this means -M <= g'(p) <= M so we have

         -M - n < g'(x) < M + n              for all x in [p-e, p+e]

         -(M + n) < g'(x) < M + n            for all x in [p-e, p+e]

   This means that |g'(x)| < M + n for all x in [p-e, p+e]. But note that by our 
   choice of n = (1-M)/2, we get that M + n < 1. So define k = M + n. Then we have 
   that |g'(x)| <= k < 1 for all x in [p-e, p+e]. 

   In order to apply any fixed point theorem, we need that g(q) is in [p-e, p+e] for 
   all q in [p-e, p+e]. Let's show that. We use the fact that p is a fixed point for 
   g and the Mean Value Theorem to get, for any q in [p-e, p+e], 

   |g(q) - p| = |g(q) - g(p)| = |g'(w)| |q-p| <= k|q-p| <= k e < e

   where w is in [p-e, p+e]. Hence we have just shown that g(x) is in [p-e, p+e] for 
   all x in [p-e, p+e] and we also know from before that  |g'(x)| <= k < 1 for all x
   in [p-e, p+e]. Now we may apply the theorem on fixed point convergence on g. QED 


(For #7, we use a variation of the triangle inequality. The normal triangle inequality 
says that |x + y| <= |x| + |y|.  The variation we use in the following proof is 
| |x| - |y| | <= |x-y|.  This requires a proof!)

7. If |g'(p)| > 1, then there is some M > 1 such that |g'(p)| >= M > 1. Let n = (M-1)/2 
   (note n > 0). Since g'(x) is continuous at p, there exists an e > 0 such that 
   |g'(x) - g'(p)| < n if |x - p| < e. This means, |g'(x) - g'(p)| < n for all x in 
   [p-e, p+e]. By the triangle inequality, we have

       | |g'(x)| - |g'(p)| | <= |g'(x) - g'(p)| < n       for all x in [p-e, p+e]
  
   which gives  -n < |g'(x)| - |g'(p)| < n    for all x in [p-e, p+e] 

   which gives  |g'(p)| - n < |g'(x)| < |g'(p)| + n    for all x in [p-e, p+e].   (**)

   What we really want here is a lower bound on |g'(x)| that is strictly bigger than 1; 
   i.e., we want a k > 1 such that |g'(x)| >= k > 1 for all x in [p-e, p+e]. Hence, we 
   will only consider manipulating the lower bound of (**). Recall |g'(p)| >= M, so 
   we have 
   
                M - n  <= |g'(p)| - n < |g'(x)|      for all x in [p-e, p+e].

   Define k = M - n. By our definition of n = (M-1)/2, we see that k > 1 and |g'(x)| >= k > 1 
   for all x in [p-e, p+e].   

   Now we are ready to consider the absolute error |p_n - p|. We use the Mean Value 
   Theorem to get 
 
   |p_n - p| = |g(p_{n-1}) - g(p)| = |g'(q_n)| |p_{n-1} - p| >= k |p_{n-1} - p|

   where q_n is in [p-e,p+e]. Applying this inequality inductively gives

   |p_n - p| >= k |p_{n-1} - p| >= k^2 |p_{n-2} - p| >= ... >= k^n |p_0 - p|.

   Since k > 1, k^n --> infinity as n --> infinity. QED


8. fixedptit(1.425,0,3) gives 1.41421356296230 with n = 3.
   fixedptit(1.425,10^(-10),-1) gives 1.41421356237309 with n = 4.