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
   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.

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). Do you think approach to the fixed point is faster or slower than that hof Newton? 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.15, a = 0, and a = 0.15. 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 bank at 2 per cent per month interest, and that you pay your bank 40 dollars per month.
   If your original debt is 700 dollars, how long will it take you to pay the loan?
   If your original debt is 3000 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.02*x1 - 40.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.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?