Topics:

• What is a difference equation? Iterations.
• Stair-step diagrams.
• Geometry of linear maps
• Stability tpyes of fixed points.
• Linearization theorem.
• Application: Why Newton's method converges fast for good starting values?

Assignment:

1. Describe the fixed points and their stability types of the linear map
   x1 -> a*x1 + b
   for all values of a, b and initial conditions x0.

2. Using PHASER, determine if the origin is an unstable or asymptotically stable fixed point of the following maps. Make sure to include one screen image of stair-step diagram for each map. Show that derivative of each equation at the origin is either 1 or -1 so that the Linearization theorem is not useful in determining the stability type of the origin.
   1. x1 -> x1 - 1.2*x1*x1*x1
   2. x1 -> x1 + 1.1*x1*x1*x1
   3. x1 -> -x1 - 1.2*x1*x1*x1
   4. x1 -> -x1 + 1.3*x1*x1*x1
   Hint: Enter the MAP x1 -> a*x1 + b*x1*x1*x1 into PHASER. Now set the parameter values appropriately to study any one of the maps above.

3. Using the Linearization Theorem, prove that x1 = sqrt(2) is an asymptotically stable fixed point of the map x1 -> x1 - 0.25*(x1*x1 -2.0). Do you think approach to the fixed point is faster or slower than that of Newton?
   Are there other fixed points of this difference equation? If there are, what are their stability types?

4. Consider the map x1 -> a + x1 + x1*x1 where a is a parameter. Draw at least three stair step diagrams, say, for a = -0.17, a = 0, and a = 0.17. Describe the changes in the number and stability types of fixed points as the parameter a is changed pass 0.

5. Suppose you want to make an investment that will pay for your child's college education. You figure you will need $45,000 when your child starts college, 16 years from now. You can buy a long term certificate of deposite or CD that pays a 6 per cent annual interest compounded monthly. What size CD should you buy?
   Hint: Use the linear equation x1 -> (1.0 + 0.06/12)*x1 . To get this equation use the Linear 1D in the Map library of PHASER and set the parameters appropriately.

6. Consider the map x1 -> 0.375*x1 + 1.5/x1 - 0.5/(x1*x1*x1). Iterate this map (derived by Alkalsadi around 1450AD) with the starting value 1.5 until 15 digits settle down. How many iterations are required? Now, count the number of all the additions, multiplications and divisions you have made to obtain your approximation to sqrt(2).
   Next do the same with Newton's method using x1 ->0.5*(x1 + 2.0/x1). Which method requires fewer number of iterations? Which method requires fewer number of operations to compute sqrt(2) to the same precision?