# Chapter 5 - Roots of Nonlinear Equations

### Assignment: Due Thursday, March 21, 2002

Do computer problem 5.2 on page 250. For part (a) be sure to give a thorough analysis of the convergence properties. Determine whether or not fixed point iteration converges; if it does converge what the rate is; if the rate is linear, the number of iterations it would take to gain a digit of accuracy. Show all work. For part (b) I recommend modifying Newton1.java (one of the programs you ran in the lab before break). Turn in the output from your programs for each different g together with a written description of how the actual convergence compared to that predicted from part (a). Run the program for each g with at least two different starting points and note any differences in behavior.

### Topics from the Chapter

• Sections 5.1 and 5.2 -- What is a non-linear equation? A system of non-linear equations? Existence and uniqueness of solutions: Anything can happen -- no nice theoretical results as there are for linear equations. Definition of multiple root
• Section 5.3 -- Sensitivity and Conditioning. How is root finding related to evaluation of a function? Why do multiple roots cause problems?
• Section 5.4 -- Convergence Rates and Stopping Criteria. What is the definition of convergence rate? What does the r in the definition tell you? What does the C tell you? How can you look at output from an iterative method and guess the convergence rate of the method? What are some typical stopping criteria for iterative algorithms?
• Bisection Method, Newton's Method, and Secant Method -- Section 5.5.1, 5.5.3, and 5.5.4 Know each algorithm, its convergence rate, its pros and cons, and its "geometry" (be able to illustrate what each method does with pictures)
• Fixed Point Iteration (Section 5.5.2): Know the algorithm, the relationship to root finding, the relationship to Newton (or vice versa), the convergence properties. Be able to find fixed point schemes to find roots of a function and determine whether or not the fixed point scheme will converge (and at what rate).
• Other methods (Section 5.5.5 and 5.5.7): Understand the idea of interpolation by functions more complex than the linear ones used in Newton and secant; understand why inverse interpolation is more reasonable than interpolation; Know what is meant by a safeguarded method.

### Other Practice/Review Exercises

• Review Questions: pages 246-248: #5.1-5.5, 5.9 - 5.20, 5.23, 5.24, 5.27 - 5.29, 5.31
• Exercises: Pages 248 - 250: #5.1 - 5.4, 5.6, 5.11