Welcome to MathOverflow

Question

2

1

Suppose you need to solve $f(\mathbf{x})=\mathbf{0}$ where $f:\mathbb{R}^n \to \mathbb{R}^m$, $m,n>1$. Newton's method relies on first order Taylor expansion of f. Where can I find details of analogous method using second order Taylor expansion? I found at least a dozen numerical analysis books which mention this method, but give no details or applications

edited Dec 22 2010 at 15:57

J. M.
2,065●7●20

asked Oct 2 2010 at 21:37

Yaroslav Bulatov
1,110●4●17

2

I'd be interested in learning about when using a second order technique might be useful and better than a first order method (Newton or Picard). It seems to me that higher methods are more prone to instabilities. – Deane Yang Oct 2 2010 at 23:17

@Deane: yes, methods with higher-order convergence tend to be finicky in that if you're a teeny bit far away from the solution you want to converge to, there is a great chance of converging to a different solution, or worse, diverge. – J. M. Oct 3 2010 at 0:30

@Yaroslav: Again, as I mentioned in your m.SE question, you need to figure out first what it means to invert a rank-3 tensor before you can figure out how to generalize Halley to multivariate nonlinear systems. Otherwise, there's Householder's method, but since multiplication of vectors, matrices and rank-3 tensors is noncommutative, you need to look at how to multiply the terms to get to your multivariate generalization. – J. M. Oct 3 2010 at 0:39

Halley's method is just one particular form of second order method. Alternative would be to use quadratic formula. Are you sure I just need to take Halley's formula and "plug it in"? – Yaroslav Bulatov Oct 3 2010 at 1:07

1

Since "order" is so overloaded a word :P , that's the reason I prefer "quadratically/cubically convergent" and "first/second order Taylor expansion" when discussing such iterative methods. :) – J. M. Oct 3 2010 at 14:22

show 2 more comments

Mike Spivey · Answer 1 · 2010-10-02 22:44:04Z UTC

3

The single-variable version of what you are looking for is called Halley's method. (See, for example, MathWorld's article on Halley's method.) Maybe there's a fairly straightforward way to generalize it to multivariable functions. Or, if nothing else, this gives you another search term.

answered Oct 2 2010 at 22:44

Mike Spivey
1,921●6●16

It seems like Halley's method is a hybrid between 1st order Taylor expansion and second order Taylor expansion books.google.com/…'s+method&hl=en&ei=jrenTNDRFJG-sAP1hr2HDQ&sa=X&oi=book_result&ct=result&resnum=4&ved=0CDUQ6AEwAw#v=onepage&q=Halley's%20method&f=false – Yaroslav Bulatov Oct 2 2010 at 22:57

J. M. · Answer 2 · 2010-12-22 15:56:43Z UTC

I haven't gotten around to downloading and reading it (and I'm wondering how I missed this when I was searching for results related to Halley's method), but apparently a multivariate version of the Halley iteration has already been developed decades ago. Maybe this might be of use.

Second order Taylor expansion to solve system of equations

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.