[Solved] COMP350 Numerical Computing Assignment #4. Solving a nonlinear equation

1. (4 points) In class, we showed that if Newtons iteration converges to r, a root of f(x) = 0, then usually it has quadratic convergence, i.e., limn |xn₊₁ r|/|xn r|² = c, where c = 06 is a constant. From a numerical experiment on f(x) = x² 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₊₁)|/|f(xn)|² = c

n

for a nonzero constant c.

Note: Use the Taylor series theory in your analysis. The proof is not difficult.

2. (6 points) In class, we derived Newtons 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.

3. (10 points) Write a Matlab program m for the secant method. Suppose we want to find the largest positive root of f(x) = x³ 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 x₀ = 2 as the initial point, for the secant method, use x₀ = 1 and x₁ = 2 as the two initial points, and for the new method, use x₀ = 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 Newtons 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 Newtons 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.