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. 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 - x1*x1*x1
   2. x1 -> x1 + x1*x1*x1
   3. x1 -> -x1 - x1*x1*x1
   4. x1 -> -x1 + x1*x1*x1

2. 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). Are there other fixed points of this difference equation? If there are, what are their stability types?

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

4. Suppose you borrow x0 dollars from a friend at 1 per cent per month interest, and that you pay your friend 20 dollars per month.
   If your original debt is 800 dollars, how long will it take you to pay the loan?
   If your original debt is 3300 dollars, how long will it take you to pay the loan? Forever?
   What is the maximum amount you can barrow?
   Hint: use the linear equation x1 -> 1.01*x1 - 20.0. To get this equation use the Linear 1D in the Map library of PHASER and set the parameters appropriately.

5. 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.4 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?

6. Extra Credit: Prove, using the Linearization theorem, that the fixed point of of the map used to compute the real root of Newton's cubic y^3 -2y -5 = 0 is asymptotically stable. Hint: find a point slightly less than the fixed point and another point greater than the fixed point. Show that derivative of the map in this interval is less than one.