- (4 points) In class, we showed that if Newton’s iteration converges to r, a root of f(x) = 0, then usually it has quadratic convergence, i.e., limn→∞ |xn+1 − r|/|xn − r|2 = c, where c = 06 is a constant. From a numerical experiment on f(x) = x2 − 2, we found after |f(xn)| is small enough, |f(xn)| is squared every step. In fact it is usually true for a general nonlinear equation. Suppose f, f′ and f′′ are continuous. Prove that if xn converges to a root, f(xn) usually converges to 0 with quadratic convergence, i.e.,
lim |f(xn+1)|/|f(xn)|2 = c
n→∞
for a nonzero constant c.
Note: Use the Taylor series theory in your analysis. The proof is not difficult.
- (6 points) In class, we derived Newton’s method by using the first two terms in the Taylor series. Derive a new method by using the first three terms in the Taylor series in a similar way.
(Bonus 5 points) Show usually the new method has cubic convergence.
- (10 points) Write a Matlab program m for the secant method. Suppose we want to find the largest positive root of f(x) = x3 − 5x + 3. Plot the graph of y = f(x) on an appropriate interval by Matlab (check how to use Matlab build-in function plot). Use your secant.m to compute the root. Also use the bisection method, the Newton method, and the new method you derived in question 2 to find the root. For the bisection method, use [1,3] as the initial interval, for the Newton method, use x0 = 2 as the initial point, for the secant method, use x0 = 1 and x1 = 2 as the two initial points, and for the new method, use x0 = 2 as the initial point. You can choose any appropriate initial points and initial interval, Take tolerances xtol=1.e-12 and ftol=1.e-12 for Newton’s method, the new method, and the secant method, and take delta=1.e-12 for the bisection method. Set a big number for the maximum number of iterations of the secant method and Newton’s method such that the iteration stops only when xtol=1.e-12 or ftol=1.e-12 is satisfied. Comment on the speeds of convergence of these four methods. Print out the graph of y = f(x) and the commands you used to plot the graph, your program secant.m, and other M-files related to f(x). Also print out the results of each iteration step. You can use M-files newton.m and bisection.m on the course web site.
