Math Fun Facts!
hosted by the Harvey Mudd College Math Department created, authored and ©1999-2010 by Francis Su
Subscribe to our RSS feed   or follow us on Twitter.
Get a random Fun Fact!
or
No subject limitations
Search only in selected subjects
    Algebra
    Calculus or Analysis
    Combinatorics
    Geometry
    Number Theory
    Probability
    Topology
    Other subjects
  Select Difficulty  
Enter keywords 

  The Math Fun Facts App!
 
  List All : List Recent : List Popular
  About Math Fun Facts / How to Use
  Contributors / Fun Facts Home
© 1999-2010 by Francis Edward Su
All rights reserved.

From the Fun Fact files, here is a Fun Fact at the Advanced level:

Multidimensional Newton's Method

You've probably heard of Newton's Method from your calculus course. It can be used to locate zeros of real-valued functions. But did you know that it is possible to define a multi-dimensional version of Newton's Method for functions from Rn to Rn?

Here's how it goes. The derivative Df(x) of the function f is the linear transformation that best approximates f near the point x. It can be represented by a matrix A whose entries are the partial derivatives of the components of f with respect to all the coordinates.

The best linear approximation to f is given by the matrix equation:


y-y0 = A (x-x0)

So, if x0 is a good "guess" for the zero of f, then solving for the zero of this linear approximation will give a "better guess" for the zero of f. Thus let y=0, and since y0=f(x0) one can solve the above equation for x. This leads to the Newton's method formula:

xn+1 = xn - A-1 f(xn)

where xn+1 denotes the (n+1)-st guess, obtained from the n-th guess xn in the fashion described above.

Iterating this will give better and better approximations if you have a "good enough" initial guess.

Presentation Suggestions:
Point out how this generalizes the usual Newton's method formula that they have learned. (The inverse of A is analogous to dividing by f'.)

The Math Behind the Fact:
The set of all initial guesses (called seeds) that converge to a given root is called the basin of attraction for that root. This set can often be fractal, and this idea is often the basis for many of the pictures found in popular books on fractals.

You can learn about the multi-dimensional Newton's method in a numerical analysis course, or an advanced analysis course (since it may be used as a basis for a proof of the Inverse Function Theorem), or an operations research course called non-linear programming. The basics of linear transformations are covered in a course on linear algebra.

How to Cite this Page:
Su, Francis E., et al. "Multidimensional Newton's Method." Math Fun Facts. <http://www.math.hmc.edu/funfacts>.

Share

References:
Keywords:    linear algebra, calculus, roots of a polynomial
Subjects:    algebra, calculus, analysis
Level:    Advanced
Fun Fact suggested by:   Francis Su
Suggestions? Use this form.
4.25
 
current
rating 		Click to rate this Fun Fact...
    *   Awesome! I totally dig it!
    *   Fun enough to tell a friend!
    *   Mildly interesting
    *   Not really noteworthy
and see the most popular Facts!
Get the Math Fun Facts
iPhone App!

Want another Math Fun Fact?

For more fun, tour the Mathematics Department at Harvey Mudd College!