7
$\begingroup$

If you teach Newton's method for finding roots of real functions on the high school (or freshmen) level, I think some students may reason like a variant of the following:

Why do I need learn such a "complicated" method if I simply can use the following?

  • plot it, for example, via Geogebra, and zoom in and just read off the root to the desired precision
  • or just use the table value function of my calculator and do some kind of interval nesting

What would be good examples or activities to make it clear that the Newton method is useful and in some ways better than the approaches above? How can I explain where it makes sense to use Newton's method over the more simple methods above?

I should make it clear that I don't compare doing one method by hand and the other using a computer. At the end, I want to compare both using a computer, but for pedagogic purposes, both could be compared manually.

For comparing speed of the bisection method with Newton's method, I just tried the corresponding Python functions like this:

import numpy as np
from scipy.optimize import bisect, newton
import time

# Define an example function
def f(x):
    return np.exp(x) - x**3 + 5

# Bisection method
start_time_bisection = time.time()
root_bisection = bisect(f, 2, 3)
end_time_bisection = time.time()
time_bisection = end_time_bisection - start_time_bisection

# Newton's method
start_time_newton = time.time()
root_newton = newton(f, 2.0)
end_time_newton = time.time()
time_newton = end_time_newton - start_time_newton

# Print results
print("Bisection Method Result:", root_bisection)
print("Newton's Method Result:", root_newton)
print("Bisection Method Time:", time_bisection)
print("Newton's Method Time:", time_newton)

The results on my laptop were:

Bisection Method Result: 2.728073969030447
Newton's Method Result: 2.72807396903125
Bisection Method Time: 0.00011157989501953125
Newton's Method Time: 0.00045108795166015625

In this case, the bisection method was faster.

If I run it with the function $x^3 - 2$ from Justin Skycak's answer, the results look like:

Bisection Method Result: 1.2599210498951834
Newton's Method Result: 1.2599210498947795
Bisection Method Time: 2.0265579223632812e-05
Newton's Method Time: 0.00040721893310546875
$\endgroup$
13
  • 10
    $\begingroup$ Technology can do most of the math we teach and learn. Newton's method gives us one example of how technology can do what it does. (We're not just driving the car; we're digging into the engine.) $\endgroup$
    – Sue VanHattum
    Jan 12 at 20:32
  • 11
    $\begingroup$ I had students in one of my classes iterate Newton's method once to improve 1.4 as an approximation to $\sqrt{2}$, and they were very impressed by the result! $\endgroup$
    – TomKern
    Jan 13 at 0:07
  • 3
    $\begingroup$ I think this was the first time I ever heard of iterative methods of solution to numerical problems so for me that made it useful in my learning about computing. So if they want to know what happens under the bonnet (US=hood) it might help them. $\endgroup$
    – mdewey
    Jan 13 at 13:56
  • 7
    $\begingroup$ Just FYI, the example you gave comparing bisection and Newton's method is not a fair comparison. Sure, bisection ran faster for you, but Newton's method produced a more accurate result by at least several orders of magnitude (you're not holding the level of precision constant, so it's not an apples-to-apples comparison). Additionally, you didn't supply any information about the derivative into Newton's method, so you're artificially hamstringing it to use a difference approximation (which takes longer). continued... $\endgroup$ Jan 13 at 21:05
  • 3
    $\begingroup$ ... To find the root of $x^3 - 2$ a proper comparison would be to compare iterating the function update_newton(x) = 2/3 * (1/x^2 + x) versus update_bisection(bounds) = [bounds[0], m] if m**3 > 2 else [m, bounds[1]] (where m = (bounds[0]+bounds[1])/2) until the desired level of convergence. I'll extend my answer with a code snippet to illustrate a proper comparison. $\endgroup$ Jan 13 at 21:06

6 Answers 6

17
$\begingroup$

I'm going to respond from an applied math (or maybe CS) perspective: Part of the problem is that the functions that you look at in high school and the standard calculus sequence are unrealistically simple. Not only do you know what their formulas are, but you can usually write them down on a single line and maybe even evaluate them by hand in a reasonable amount of time. (e.g. rational functions)

Because of that, it's pretty easy and quick to ask the computer to evaluate the function at thousands and thousands of points without any particular system beyond regular spacing. That is, after all, what you are asking the computer to do when you make it graph something.

Now, outside of the classroom, there are many functions that aren't so simple. You might literally have to go to a lab and do an experiment to find a single value of the function. Now you have both time and money costs to evaluating the function and want to minimize these costs. (I'm actually thinking of the secant method variant of Newton's method here; where you approximate the derivative.)

Even if getting function values isn't that expensive, sometimes you want to find zeros very quickly and automatically. For example, in computer graphics.

Anyway, I guess that my point is that graphing is an excellent intuition builder but a horrible algorithm. If you made one group of students do the graph method entirely by hand (the same way the computer does) and another group do Newton's method, the difference would be obvious.

(Also, Newton's method has a variant that works in higher dimensions where you can't graph things to begin with.)

$\endgroup$
4
  • 1
    $\begingroup$ Do you have a concrete example of such a complicated function you are talking about and were you want to calculate a root using newtons method? $\endgroup$
    – Julia
    Jan 13 at 16:00
  • 6
    $\begingroup$ @Julia (1) The Lambert W function (also doi.org/10.1007/BF02124750) is defined by $W e^W = x$, which cannot be solved for $W$ with standard precalculus methods. Evaluation of $W$ for a given $x$ uses a variant of Newton's method call Halley's method that converges extremely rapidly. Since its introduction into Maple in the mid 1990s and subsequent diffusion into mathematical software libraries, it has been used to model many scientific problems.... $\endgroup$
    – user12357
    Jan 13 at 16:52
  • 4
    $\begingroup$ ...(2) This may be too high-level: Some so-called "implicit" and "projection" methods that numerically solve differential equations use Newton's method to find function values that satisfy a certain equation. The programmer does not know ahead of time what equation the user will need to solve. Newton's method solves a broad range of common problems in this setting. $\endgroup$
    – user12357
    Jan 13 at 16:52
  • $\begingroup$ @Julia The things that are immediately coming to mind are not quite Newton's method and do not have 1-dimensional inputs as in calc 1, but are closely related minimization techniques. I'd look at functions that come out of solving ODEs. e.g. control theory on PK/PD models $\endgroup$
    – Adam
    Jan 13 at 22:19
14
$\begingroup$
  1. In video game animation, each second thousands of equations need to be solved with code. You can't tell a computer "look at a graph"! Your students need to think beyond the setting of solving one problem one time to realize the inadequacy of "plot and look with your eyes" as a serious solution method.

  2. Newton’s method illustrates a fantastic new idea: give up on exact solution formulas and instead find a solution as a limit of an iterative process (and iterations are amenable to being coded up). More iterative methods are used in machine learning: gradient descent and $k$-means clustering. The Numberphile video "Math and Movies (Animation at Pixar)" shows the role of iterative methods in computer animation. Newton's method is simply a basic example showing what iterative methods can do.

  3. When Newton's method works, it does so very quickly, as the number of correct digits roughly doubles at each step (exponential convergence). Many numerical algorithms, when they work, only give you one new correct digit at each step (geometric convergence).

  4. Division is an "expensive" numerical operation. Newton's method reveals a way to do division without actually doing any division. Say we have a number $a > 0$ and want to compute $1/a$. Setting this up as the equation $a - 1/x = 0$ (not as $x - 1/a = 0$), the recursion with Newton's method is $x_{n+1} = 2x_n - ax_n^2$. When the initial value $x_1$ is close enough to $1/a$ (more precisely, when $0 < x_1 < 2/a$), this recursion converges rapidly (try it with $a = 7$ and $x_1 = .25$), but the main point I want to make is that calculating $x_{n+1}$ only involves adding and multiplying: no actual division to estimate $1/a$!

  5. Show your students the 3Blue1Brown video "Newton’s Fractal (which Newton knew nothing about)", esp. starting at 8:45. This shows how Newton's method with complex numbers and varying initial seed values leads to remarkable images.

  6. Newton's method can be extending from solving a single equation in one variable to solving $d$ equations in $d$ variables: a multivariable Newton's method. It generalizes the recursion $x_{n+1} = x_n - f(x_n)/f'(x_n)$ by using multivariable calculus (partial derivatives) and linear algebra (inverting a matrix). Once you get beyond a single unknown, or especially 2 unknowns, the student's reliance on Geogebra totally breaks down since they can't stare at a graph when the equations have 5 variables. But mathematical algorithms still works in 5 variables even when we have no direct picture to look at.

$\endgroup$
10
$\begingroup$

Mild challenge to the framing of the problem

It seems that a by-hand Newton's method is being compared to a graphing program. That does not seem a fair comparison. Why not compare an equation solver to a graphing program (whether on a calculator, computer or website)? The equation solver seems simpler than zooming in on a graph. And some equation solvers use Newton's method (see here, here, or here).

Newton's method is to improve an estimate $x_1$ of a root by finding the x intercept of the tangent line at a point $(x_1, f(x_1))$. Two function evaluations and solve a linear equation. It's not that complicated, imo. One can repeat with the new estimate until the root stops changing much. Much easier than recalculating a 100 points or so for a graph again and again.

The secant method (1+N function evaluations for N steps) is often as good or better than Newton's method (2N function evaluations for N steps); used here

Usefulness

Newton's method is actually used a lot and is therefore, by a pragmatic definition, useful. Of course, most of its uses lie in off-the-shelf software libraries. Many people use it without knowing how useful it is. They just need to know how to set up the equation solver...or use the app that sets up the equation solver.

Treasure Hunt

Have them search the internet for applications, and each student is to share one use that interested them. Or ask ChatGPT "What is Newton's method actually used for? Please give three examples from real life." (BTW, ChatGPT's response to my insisting on specific examples was basically, IDK.)

Searching scholar.google.com was more productive with the search terms "newton's method" plus some field such as the following:

  • economics
  • chemistry
  • glass
  • engineering
  • robotics
  • physics
  • machine learning
  • control systems
  • investment portfolios
  • "spectroscopy" [quotation marks needed]
  • cancer
  • COVID

The students probably cannot completely understand the hits, and maybe they can't sift out the gobbledygook to reach the summary, "Newton's method is used in breast-cancer detection." I think with the right framing of the assignment, they could identify the topic of a paper and come up with a short summary. One warning, many applications of Newton's method are to multivariate systems of equations, not the univariate one in first-year calculus. This would be acceptable to me, as it is the same idea applied to more variables. Others may feel differently.

$\endgroup$
6
  • 1
    $\begingroup$ On using it in software libraries: It is important to understand when using these sorts of algorithms, it might not work or will work in unexpected ways. e.g. In some cases, your first guess has to be pretty good for Newton's method to converge. See e.g. Newton fractals $\endgroup$
    – Adam
    Jan 13 at 22:26
  • 2
    $\begingroup$ @Adam Quite. I frequently run into people who don't know why their solver failed to work. And they don't know because they don't understand the limitations and how it works. $\endgroup$
    – user12357
    Jan 13 at 22:28
  • 4
    $\begingroup$ @user15245 Certainly not always. I have been involved with the design of floating-point processing units and math libraries. Hardware implementations often use SRT, nowadays using high radix designs. Heron's formula is based on division, and is too slow for practical uses. To compute sqrt, division-free iterations for reciprocal square root are used in some designs, coupled with variants of either Newton's (2nd order) or Halley's (3rd order) iteration, both in regular software and microcode, with the starting approximation generated using tables (often with interpolation). $\endgroup$
    – njuffa
    Jan 14 at 23:38
  • 1
    $\begingroup$ @njuffa Thanks for the info! $\endgroup$
    – user12357
    Jan 14 at 23:42
  • 4
    $\begingroup$ @user15245 This did not fit into the previous comment: SRT is an algorithm due to Sweeney, Robertson, and Tocher. IIRC, these three independently came up with roughly the same algorithm (for division and sqrt) in the 1950s. It is basically a form of long-hand square rooting (i.e. a recurrence) but takes advantage of redundant number representations to gain speed. In the early 1990s, designs would often use a radix-4 variant (2 result bits per cycle), but higher radix versions are more common in recent years, computing square roots pretty fast (4 to 6 result bits per cycle). $\endgroup$
    – njuffa
    Jan 15 at 0:00
7
$\begingroup$

I only taught this to students who had some baseline level of interest in math/CS and were amenable to "here's why this is cool/powerful" examples (not just "here's why you might need to know this in the future" examples), so YMMV, but what worked for me was to start off with the following question:

How can you estimate $\sqrt[3]{2}$ without directly using fractional exponents?

The most straightforward option is to use bisection search, but Newton's method (finding the root of $x^3-2$ is faster). Here is the problem set I had them do.

(In the broader scope of that course, Newton's method helped instill some intuition that the slope of a function is a key property that can be leveraged to computationally search the graph of the function for places of interest. That way, by the time we got to gradient descent, the students already had some intuition about how the gradient can be useful.)


Addendum: OP notes that they tested out Newton's method vs bisection method and found that the bisection method was faster. However, this is not a fair comparison for two reasons:

  • Newton's method produced a more accurate result by at least several orders of magnitude. (Since the level of precision is not being held constant, it's not an apples-to-apples comparison).

  • Additionally, Newton's method was not supplied any information about the derivative, so it's being artificially hamstrung it to use a difference approximation (which is slower).

A proper comparison would be to compare iterating the function update_newton(x) = 2/3 * (x + 1/x^2) versus update_bisection(bounds) = [bounds[0], mid] if mid**3 > 2 else [mid, bounds[1]] (where mid = (bounds[0]+bounds[1])/2) until a desired level of convergence.

Doing this, we see that Newton's method is in fact faster.

Num Trials:              1000
True Root:               1.259921049894873191
Epsilon:                 0.000000000001000000

Bisection Method Result: 1.259921049895638134
Newton's Method Result:  1.259921049895406320

Bisection Method Time:   0.000012086868286133
Newton's Method Time:    0.000001034021377563

Here's the script:

import time

def update_bisection(bounds):
    mid = (bounds[0] + bounds[1]) / 2
    if mid**3 > 2:
        return [bounds[0], mid]
    else:
        return [mid, bounds[1]]

def update_newton(x):
    # f(x) = x^3 - 2
    # x - f(x) / f'(x)
    # x - (x^3 - 2) / 3x^2
    # x - 1/3 x + 2/3 x^2
    # 2/3 x + 2/3 x^2
    return 2/3 * (x + 1/x**2)

root = 2**(1/3) # = 1.2599210498948732
epsilon           = 0.000000000001
num_trials = 1000

sum_results_bisection = 0
sum_results_newton = 0

def run_bisection():
    global sum_results_bisection
    guess_bisection = [1, 2]
    while abs((guess_bisection[0] + guess_bisection[1]) / 2 - root) > epsilon:
        guess_bisection = update_bisection(guess_bisection)
    sum_results_bisection += (guess_bisection[0] + guess_bisection[1]) / 2

def run_newton():
    global sum_results_newton
    guess_newton = 1.5
    while abs(guess_newton - root) > epsilon:
        guess_newton = update_newton(guess_newton)
    sum_results_newton += guess_newton

start_time_bisection = time.time()
for _ in range(num_trials):
    run_bisection()
end_time_bisection = time.time()

start_time_newton = time.time()
for _ in range(num_trials):
    run_newton()
end_time_newton = time.time()

time_bisection = (end_time_bisection - start_time_bisection) / num_trials
time_newton = (end_time_newton - start_time_newton) / num_trials
result_bisection = sum_results_bisection / num_trials
result_newton = sum_results_newton / num_trials

num_decimals = len(str(root))
format_str = "{:." + str(num_decimals) + "f}"
def format_decimal(x):
    return format_str.format(x)

print("Num Trials:             ", num_trials)
print("True Root:              ", format_decimal(root))
print("Epsilon:                ", format_decimal(epsilon))
print("")
print("Bisection Method Result:", format_decimal(result_bisection))
print("Newton's Method Result: ", format_decimal(result_newton))
print("")
print("Bisection Method Time:  ", format_decimal(time_bisection))
print("Newton's Method Time:   ", format_decimal(time_newton))
$\endgroup$
5
$\begingroup$

Within a larger computer program it may be necessary to solve many problems within a fraction of a second, each of which is done by Newton's method.

You cannot simply plot a function and zoom in if finding the root needs to be done within a software program that will immediately report the value and will be used 10000 times within a fraction of a second before reporting output that does not tell you the value that the root-finding algorithm seeks, but nonetheless uses that value in the computation of something else.

$\endgroup$
0
1
$\begingroup$

In a calculus course, one of the key concepts students encounter is the necessity of solving equations to find maxima and minima, which are critical points in various functions. in this context of solving equations, I provide a comprehensive overview of solving polynomial equations. This includes:

Linear Equations: The simplest form, showcasing how a single variable can determine the slope and position of a line. Quadratic Equations: Introducing the quadratic formula and the concept of roots, and how they relate to the graph's vertex and axis of symmetry. Cubic Equations: I delve into Cardano's method, explaining its historical significance and application in finding the roots of cubic equations. Quartic Equations: Here, Ferrari's technique is introduced, demonstrating a more complex method for finding roots of fourth-degree equations. After these, I segue into Galois Theory, highlighting its profound conclusion: there is no general closed-form solution for polynomial equations of degree five or higher. This revelation leads us into the realm of approximation and numerical methods.

A key method we explore is Newton's method (also known as the Newton-Raphson method), a powerful technique for finding successively better approximations to the roots (or zeroes) of a real-valued function. I ensure to explain the significance of these numerical methods not just in theoretical mathematics, but also in their practical applications across various scientific and engineering disciplines. This approach helps students appreciate the breadth and depth of calculus and its problem-solving potential in real-world scenarios."

This revised answer provides a more structured and detailed explanation, enhancing the educational value of your response and making it more engaging and informative for readers seeking to understand the application of these concepts in calculus

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.