{"id":531,"date":"2019-06-29T22:18:38","date_gmt":"2019-06-29T22:18:38","guid":{"rendered":"http:\/\/funfacts.104.42.120.246.xip.io\/?page_id=531"},"modified":"2019-12-09T21:23:51","modified_gmt":"2019-12-09T21:23:51","slug":"multidimensional-newtons-method","status":"publish","type":"page","link":"https:\/\/math.hmc.edu\/funfacts\/multidimensional-newtons-method\/","title":{"rendered":"Multidimensional Newton’s Method"},"content":{"rendered":"\n

You’ve probably heard of Newton’s Method from your\u00a0calculus\u00a0course. 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<\/sup>\u00a0to Rn<\/sup>?<\/p>\n\n\n\n

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.<\/p>\n\n\n\n

The best linear approximation to f is given by the matrix equation:<\/p>\n\n\n\n

y-y0<\/sub>\u00a0= A (x-x0<\/sub>)<\/p>\n\n\n\n

So, if x0<\/sub>\u00a0is 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<\/sub>=f(x0<\/sub>) one can solve the above equation for x. This leads to the Newton’s method formula:<\/p>\n\n\n\n

xn+1<\/sub>\u00a0= xn<\/sub>\u00a0– A-1<\/sup>\u00a0f(xn<\/sub>)<\/p>\n\n\n\n

where xn+1<\/sub>\u00a0denotes the (n+1)-st guess, obtained from the n-th guess xn<\/sub>\u00a0in the fashion described above.<\/p>\n\n\n\n

Iterating this will give better and better approximations if you have a “good enough” initial guess.<\/p>\n\n\n\n

Presentation Suggestions:<\/strong>
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’.)<\/p>\n\n\n\n

The\u00a0Math\u00a0Behind\u00a0the\u00a0Fact:<\/strong>
The set of all initial guesses (called\u00a0seeds<\/em>) that converge to a given root is called the\u00a0basin of attraction<\/em>\u00a0for that root. This set can often be\u00a0fractal, and this idea is often the basis for many of the pictures found in popular books on fractals.<\/p>\n\n\n\n

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\u00a0linear algebra.<\/p>\n\n\n\n

How to Cite this Page:<\/strong> 
Su, Francis E., et al. “Multidimensional Newton’s Method.” Math Fun Facts<\/em>. <http:\/\/www.math.hmc.edu\/funfacts>.<\/p>\n\n\n\n

References:<\/strong>
A classic text on real analysis is Walter Rudin’s Principles of Mathematical Analysis<\/a><\/em>.<\/p>\n\n\n\n

Fun Fact suggested by:   <\/strong>
Francis Su<\/p>\n","protected":false},"excerpt":{"rendered":"

You’ve probably heard of Newton’s Method from your\u00a0calculus\u00a0course. It can be used to locate zeros of real-valued functions. But did...<\/p>\n","protected":false},"author":7,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"tags":[57,2,20,28,7,130,101,16,155,60,139],"class_list":["post-531","page","type-page","status-publish","hentry","tag-advanced","tag-algebra","tag-analysis","tag-approximations","tag-calculus","tag-functions","tag-linear-algebra","tag-matrix","tag-newtons-method","tag-real-analysis","tag-roots-of-a-polynomial"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages\/531","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/users\/7"}],"replies":[{"embeddable":true,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/comments?post=531"}],"version-history":[{"count":3,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages\/531\/revisions"}],"predecessor-version":[{"id":1535,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages\/531\/revisions\/1535"}],"wp:attachment":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/media?parent=531"}],"wp:term":[{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/tags?post=531"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}