- 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.
- Consdier f(x) = x3 2.
- Show that f(x) = 0 has a solution in [1; 2] (use a theorem from class).
- Compute by hand (feel free to use a calculator) the rst three iterations of the following method (pick the appropriate initial value as needed).
- Bisection method.
- Newton’s method
- Secant method
- Linear interpolation
- 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.
- Use your code to nd the rst ten positive solutions of equation tan x = x.
- Investigate the behavior of the secant method on the function f(x) =jx aj. Explain your nding and discuss the cause.
- 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
- Why did the Bisection Method require approximately the same number of iterations to converge to the approximate root for all three test problems?
- 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.
|(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?|
- Let f(x) = sin(x) and g(x) = sin2(x) and note that both have x = as a root.
- Will Newton’s method converge to root for each of these functions? Why? What rate of convergence do you expect?
- 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.
- 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?
- 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
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.
- Prove the convergence result of the secant method using a similar argument as in Newton’s method.