Homework 3 Solution

    1. In 1685 John Wallis published a book called Algebra in which he described a method devised by Newton for solving equations. In a slightly modi ed form, this method was also published by Joseph Raphson in 1690. This form is the one commonly called Newton’s method or the Newton-Raphson method.

Newton himself discussed the method in 1669 and illustrated it with the equation x3 2x 5 = 0. Wallis used the same example. Find a root of this equation using Newton’s method (either by hand or by coding), thus continuing the tradition that every numerical analysis student should solve this venerable equation.

2. Consdier f(x) = x3    2.

        (a) Show that f(x) = 0 has a solution in [1; 2] (use a theorem from class).

        (b) Compute by hand (feel free to use a calculator) the rst three iterations of the following method (pick the appropriate initial value as needed).

            i. Bisection method.

            ii. Newton’s method

            iii. Secant method

            iv. Linear interpolation

        (c) Write a Matlab code for each of the method mentioned in 1(b). Use your code to nd the approximation of the solution of f(x) = 0. Create an error table for each method.

    3. Use your code to  nd the  rst ten positive solutions of equation tan x = x.
p

4. Investigate the behavior of the secant method on the function f(x) = jx aj. Explain your nding and discuss the cause.


5. Each of the functions

f1
(x) = sin(x)  x  1
f2
(x) = x(1
cos(x))
f3(x) = ex
x2 + 3x  2

have a root in the interval [ 2; 1]. Use all four of the above root nding methods to approximate the roots within absolute error tolerance 10 6 for each function. Limit the number of iterations to 500. For Newton’s Method, use starting value x0 = 1; for the Secant Method use x0 = 1 and x1 = 0:9. Summarize the results of the analysis for each method in table form.


Function    Number of Iterations    Approximate Root
f1(x)
f2(x)
f3(x)


    (a) Why did the Bisection Method require approximately the same number of iterations to converge to the approximate root for all three test problems?

    (b) Newton’s method should have experienced di culty approximating the root of one of the test functions. Identify which function presented a problem and explain why the di culty occurred.

1

(c) Above, the Bisection Method was used to  nd the root of the function f1(x) = sin(x)
x  1.
Consider the function g1(x) = (sin(x)  x  1)2. Clearly f1 and g1 have the same root in [
2; 1].
Could the Bisection Method be used to approximate the root in g1? Why or why not?


    6. Let f(x) = sin(x) and g(x) = sin2(x) and note that both have x =  as a root.

        (a) Will Newton’s method converge to root for each of these functions? Why? What rate of convergence do you expect?

        (b) Use Newton’s method to approximate as roots of f and g accurate to machine error. Use Matlab to check the rate of convergence at each step. List your results.

        (c) Plot the number of iterations for Newton’s method in part (b) against the absolute error at each step. Plot the results for f and g in the same graph. What does each curve resemble?

    7. If the root of f(x) = 0 is a double root (a root with multiplicity 2), then Newton’s method can be accelerated by using
f(xn)
xn+1 = xn    2f0(xn)


Create two examples by your own and compare the convergence of this scheme with regular Newton’s method. Explain why this algorithm will work.

8. Prove the convergence result of the secant method using a similar argument as in Newton’s method.













































2