General Instructions
MAT 128B, Winter 2019 Programming Project 1
(due by Wednesday, January 30, 11:59 pm)
• You are required to submit each of your programming projects via file upload to Canvas. Note that the due dates set in Canvas are hard deadlines. I will not accept any submissions outside of Canvas or after the deadline.
• Write a report that includes all required numerical results, a discussion of your results, and explanations of runs for which a method failed. Your report should be at least one page long, but not longer than three pages.
• When you are asked to print out numerical results, print numbers in 16-digit floating-point for- mat. You can use the Matlab command “format long e” to switch to that format from Mat- lab’s default. For example, the number 10π would be printed out as 3.141592653589793e+01 in 16-digit floating-point format.
• For each programming project, upload these files: a single pdf file of your report and a complete set of Matlab files that lets us run and check your programs. This set should consist of one file for each Matlab function you are asked to write and a single driver file for each of the problems that you are asked to test your programs on. Each of these driver files should generate the required numerical results for all runs of a problem. So for this current project, you should submit a total of 7 Matlab files: 4 files for the functions FPI, NEWTON, DAMPED NEWTON, and SECANT and three driver files for Problems 1–3.
We consider the problem of computing solutions of nonlinear equations
f(x) = 0, (1)
where f : R → R is a continuous function. A solution x of (1) is called a root of f. Newton’s method, Newton’s method with damping, and the secant method are root-finding procedures that are applied directly to the function f. Fixed-point iteration is applied to a continuous function g the fixed points of which are roots of f.
Write Matlab functions FPI, NEWTON, DAMPED NEWTON, and SECANT for carrying out the versions of fixed-point iteration, Newton’s method, Newton’s method with damping, and the secant method that were presented in class. For Newton’s method and Newton’s method with damping, the function f is assumed to be continuously differentiable.
For all 4 functions, use the stopping criterion
|xi+1 − xi| < TOL. max{ |xi+1|, 1 }
Here, xi+1 and xi denotes the approximate root of f generated in the current iteration and previous iteration, respectively. Make an effort to write your programs such that you use as few function evaluations (of g, f, and f′) as possible.
The input parameters for FPI should be:
• A Matlab function for evaluating the function g at any given x
• The initial guess x0
• The convergence tolerance TOL
• The integer N0 to safeguard against infinite loops due to bugs or non-converging iterates
The input parameters for NEWTON should be:
• A Matlab function for evaluating the function f at any given x
• A Matlab function for evaluating the derivative f′ at any given x
• The initial guess x0
• The convergence tolerance TOL
• The integer N0 to safeguard against infinite loops due to bugs or non-converging iterates
The input parameters for DAMPED NEWTON should be:
• A Matlab function for evaluating the function f at any given x
• A Matlab function for evaluating the derivative f′ at any given x
• The initial guess x0
• The convergence tolerance TOL
• The integer N0 to safeguard against infinite loops due to bugs or non-converging iterates • A small λmin > 0 to safeguard against tiny λi’s
The input parameters for SECANT should be:
• A Matlab function for evaluating the function f at any given x
• The initial guesses x0 and x1
• The convergence tolerance TOL
• The integer N0 to safeguard against infinite loops due to bugs or non-converging iterates
Use your functions to compute roots for the following three problems. For all your runs, use the convergence tolerance
TOL = 10−15
and choose N0 large enough so that you can observe convergence or divergence. Use
λmin = 10−15 for your runs with DAMPED NEWTON.
Problem 1: Run NEWTON and SECANT to find a root of the function f1(x) = 2×4 − 3×2 − 77.
Apply FPI to the function
56 3 2 771/4
g1(x)= 2x +112
the fixed point of which is the positive root of f1. Run both NEWTON and FPI with the three
initial guesses
x0=1, x0=1, x0=0. 2
Run SECANT with the three pairs of initial guesses
x0=0andx1=1, x0=1andx1=2, x0=1andx1=−1. 22
Problem 2: Run NEWTON, DAMPED NEWTON, and SECANT to find a root of the function f2(x)=arctanx− 2x .
Apply FPI to the function
1+x2 g2(x) = x2 + 1 arctan x
2
the fixed points of which are the roots of f2. Run each of FPI, NEWTON, and DAMPED NEWTON
with the three initial guesses
for a total of 9 runs. Run SECANT with the three pairs of initial guesses
x0 =1andx1 =2, x0 =2andx1 =3, x0 =10andx1 =11.
Problem 3: Run NEWTON, DAMPED NEWTON, and SECANT to find a root of the function f3(x) = arctan x.
Run both NEWTON and DAMPED NEWTON with the 4 initial guesses x0 =1, x0 =10, x0 =r−10−15, x0 =r+10−15,
x0 =1, x0 =2, x0 =10,
where r denotes the value of the positive approximate root of f2 that you obtained from your run of NEWTON with x0 = 1 in Problem 2. Run SECANT with the three pairs of initial guesses
x0 =1andx1 =2, x0 =10andx1 =11, x0 =r−1 andx1 =r+1. 22
For all your runs in Problems 1–3, print out the final value of xi+1 at termination, the corresponding iteration index i, the total number of evaluations of the function f (or g in the case of FPI) used in that run, and for NEWTON and DAMPED NEWTON, the total number of evaluations of the derivative f′. For all your runs, comment on the speed of convergence and possible divergence. If there is divergence, provide an explanation for it.