Lab 5—Finding Roots with Newton’s Method

Purpose

This lesson introduces you to Newton’s method, an important algorithm for finding zeros of functions, as well as to several other mathematical programming tricks. It also reinforces your understanding of while loops.

Background

Given a function, f(x), a zero or root of f is simply a value of x at which f(x) = 0. Finding zeros of functions is the heart of algorithms for solving many mathematical problems, as illustrated later in this exercise.

Newton’s method, sometimes called the Newton-Raphson method, is a simple and widely used algorithm for finding zeros. For a description of it and the underlying mathematics, see the “Newton’s Method” video at https://www.youtube.com/watch?v=WO0GMNUCMNw.

This lab requires you to use a Matlab feature called “function handles.” Sections 14.3 and 14.4 of our textbook describe function handles and the related concept of “anonymous functions,” and we will also talk about them in class.

Activity

The basic plan for this exercise is to write a Matlab function that uses Newton’s method to find a zero of a given function, write a supporting function that calculates derivatives, and finally use the Newton’s method function to solve several problems that reduce to zero-finding. Here are the details…

Step 1

Write a function, which I’ll call derivative in this handout, that takes a function handle, f, and a number, x, as its arguments, and that returns a close approximation to the derivative of f evaluated at x. For an alternative version of this task, see the extra credit section below.

We will develop an algorithm for approximating derivatives of arbitrary functions through class discussion.

Step 2

Write a function, newton, that takes a function handle, f, and a number, x, as its parameters, and that returns a close approximation to a zero of f. Your function should use Newton’s method, with x as its initial estimate of the zero, to find its answer. Your function should also use the derivative function from step 1 to calculate the derivatives that Newton’s method uses.

Step 3

Use the newton function from step 2 to solve the following problems. It may be helpful to write a script for each problem, possibly broken into sections that you can execute individually (via the “Run Section” button in Matlab’s editor), to organize the code you use in solving each problem. We will develop algorithms for these problems through class discussion if needed.

Problem 1. Find a solution to the equation

cosx = -2x

Problem 2. Given a positive number, x, calculate √x, without using any explicit root or exponentiation operations. (Needing to do this is a situation that the designers of the “square root” functions in calculators and programming languages face—they can’t use a built-in operation because they are the ones building the operation in to begin with! Wisdom has it that many calculators, computers, and programming languages do in fact use Newton’s method to implement their square root (and certain other) operations.)

Extra Credit

For up to 2 points extra credit, write the derivative function so that it only takes the function handle, f, as its parameter, and returns a new handle to a function that is (a close approximation to) the derivative of f. Note: this does not require you to write or use any symbolic differentiation code, and you will not receive the extra credit if you use symbolic differentiation.

Follow-Up

I will grade this exercise in a face-to-face meeting with you. During this meeting I will look at your solution, ask you any questions I have about it, answer questions you have, etc. Please bring a written solution to the exercise to your meeting, as that will speed the process along.

Sign up for a meeting via Google calendar. If you worked in a group on this exercise, the whole group should schedule a single meeting with me. Please make the meeting 15 minutes long, and schedule it to finish before the end of the “Grade By” date above.