Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How do I use second order Taylor method to solve a system of non-linear equations? Is there a good reference that gives details? I found mentions of it in a dozen of numerical analysis books, but no examples

Specifically, $f:\mathbb{R}^n \to \mathbb{R}^m$, solve $f(\mathbf{x})=\mathbf{0}$ using second order Taylor expansion of $f$ around initial guess $\mathbf{x_0}$

share|improve this question
    
Which NA books have you been looking at? Note that the multidimensional version of Newton-Raphson involves expanding $f(\mathbf{x})$ up to the Jacobian-containing term (first-order). –  J. M. Sep 30 '10 at 4:07
    
the ones that come up in google books when I search for "higher order Taylor" –  Yaroslav Bulatov Sep 30 '10 at 4:14
    
I don't see any practical generalizations of Halley's method to multidimensional equations, if that's what you're getting at; the quadratic term involves a rank-3 tensor, and it looks unwieldy to manipulate in manner of how one would derive Halley's method from the Taylor expansion. –  J. M. Sep 30 '10 at 4:24
    
It looks unwieldy, which is why I'm looking for some reference that goes through the details –  Yaroslav Bulatov Sep 30 '10 at 4:33
    
Actually, what I was getting at is that there's one question you have to ask first: "how does one 'invert' a rank-3 tensor?" –  J. M. Sep 30 '10 at 23:47

1 Answer 1

One way to solve f(x) = y is to minimize g(x) = (f(x) - y)^2. You could do this by taking the quadratic approximation to g(x) that comes from the second order Taylor series centered at your initial guess, finding its minimum, and letting that minimum be the starting guess for the next iteration. This isn't necessarily the best algorithm, but it's easy to understand and implement.

For high-dimensional problems, the work is in solving the system of equations to minimize the quadratic approximation. A great deal of research has gone into doing that step cleverly, taking advantage of sparse matrix structure etc.

share|improve this answer
    
Well, I don't need a high-dimensional problem, just an example for n=2, m=2. As J.M. notes, it involves rank-3 tensor –  Yaroslav Bulatov Sep 30 '10 at 17:13
    
I think you and I may have different meanings of "second order" in mind. By second order, I mean up to and including 2nd derivatives. The quadratic approximation involves a linear system of equations, a rank-2 tensor. Sounds like you have in mind including third derivatives and hence encountering a rank-3 tensor. –  John D. Cook Sep 30 '10 at 19:25
    
Second derivative of f in my example is an m-by-n-by-n tensor –  Yaroslav Bulatov Sep 30 '10 at 20:25
    
I still consider converting simultaneous nonlinear equations into a nonlinear least squares problem as a bit of a cheat, but... :D Anyway, what Yaroslav has originally is a $m$-dimensional vector function with $n$ independent variables, so the first term of the Taylor expansion has a vector, the second (linear) term has a matrix... you get the idea. Rather unfortunate "order" is a very overloaded mathematical term, I must say. –  J. M. Sep 30 '10 at 23:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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