• To get full credit, you must write down sufficient intermediate steps, only giving the final answer earns you no credit!
• Please make sure that your handwriting is recognizable, otherwise you only get partial credit for the recognizable part.

1. Consider the bisection method starting with the ini-tial interval [1.5,3.5]. In the following questions the interval refers to the bisection interval whose width changes across different loops.
   • What is the width of the interval at the nth step?
   • What is the maximum possible distance between the root r and the midpoint of the interval?
2. In using the bisection algorithm with its initial in-terval as [a₀,b₀], we want to determine the root with its relative error no greater than . Assume a₀ >

Prove that the number of steps n must satisfy

.

• Perform four iterations of Newtons method for thepolynomial equation p(x) = 4x³ 2x² + 3 = 0 with the starting point x₀ = 1. Use a hand calculator and organize results of the iterations in a table.

1. Consider a variation of Netwons method in whichonly the derivative at x₀ is used,

.

Find C and s such that

.

1. Within (), will the iteration x_n+1 = tan¹ x_n converge?
2. Let p > What is the value of the following continued fraction?

Prove that the sequence of values converges. (Hint: this can be interpreted as x = lim_n x_n, where , and so forth.

Formulate x as a fixed point of some function.)

• What happens in problem II if a₀ < 0 < b₀? Derive an inequality of the number of steps similar to that in II. In this case, is the relative error still an appropriate measure?
• () Consider solving f(x) = 0 by Newtons method with the starting point x₀ close to a root of multiplicity k. We assume that f C^k+1. Note that is a zero of multiplicity k of the function f iff f^(k)() 6= 0; i < k, f⁽ⁱ⁾() = 0.
  • How can a multiple zero be detected by examining the behavior of the points (x_n,f(x_n))?
  • Prove that if r is a zero of multiplicity k of the function f, then quadratic convergence in Newtons iteration will be restored by making this modification:

.

1. () Analysis of the secant method for a root of multiplicity k by assuming that it converges.
   • Prove that if r is a zero of multiplicity k > 1 of the function f, the secant method only has linear convergence.
   • Use the same argument to show that the convergence rate of the secant method is .

Each of the first six problems weighs 5 points. Each of the other problems weighs 10 points. In particular, the last two problems are for extra credit and you do not have to solve them. However, special students such as my graduate students who audit this class have to solve all problems.

2 C++ programming

1. Implement the bisection method in C++. Test your program on these functions and intervals.
   • x¹ tanx on [0,],
   • x¹ 2^x on [0,1],
   • 2^x + e^x + 2cosx 6 on [1,3],
   • (x³+4x²+3x+5)/(2x³9x²+18x2) on [0,4].
2. Implement Newtons method in C++ to solve the equation x = tanx. Find the roots near 4.5 and 7.
3. Implement the secant method in C++. Test your program on the following functions and initial values.

1

• sin(x/2) 1 with,
• e^x tanx with x₀ = 1,x₁ = 1.4,
• x³ 12x² + 3x + 1 with x₀ = 0,x₁ = 0.

You should play with other initial values and (if you get different results) think about the reasons.

Each of the above three coding assignments weighs 10 points. The total number of points of this homework without extra credit is thus 5 6 + 10 + 10 3 = 70. IMPORTANT:

• Under the signature of your function in .m file, you must clearly state
  • the purpose of this C++ function,
  • the meaning of each input parameter,
  • preconditions on each input parameter,
  • the meaning of each output parameter,
  • postconditions on each output parameter.
• You must present in your solution your C++ code and corresponding test results.
• You need to send your source code to the course email [email protected]

3 Extra credits

Additional 10% credits will be given to you if you typeset your solutions in L^ATEX. You are welcome to use the L^ATEX template available on my webpage. You can also get partial extra credit for typesetting solutions of some problems.

Note: If you choose to typeset your solutions in L^ATEX, you still need to turn in a hard copy in class. In addition, please upload your latex source (.tex), supporting files, and C++ program in a single zip file (format: YourName_Homework1.zip) to the course email [email protected]

4 Reading

Download the electronic version of the following book from the library website:

• Numerical Analysis by W. Gautschi, 2nd Edition. ISBN: 978-0-8176-8259-0.

The above book will be referred to as NAG2012 in the rest of this class. Students who are eager to learn are encouraged to read pages 55-112 and 159-195.

Note: If you are a special student, you have to print out these pages and read the text before this semester ends. Otherwise you dont have to do it.