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
$\begingroup$
$\endgroup$
7
-
2$\begingroup$ 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. $\endgroup$– Deane YangOct 2, 2010 at 23:17
-
$\begingroup$ @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. $\endgroup$– J. M. isn't a mathematicianOct 3, 2010 at 0:30
-
$\begingroup$ @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. $\endgroup$– J. M. isn't a mathematicianOct 3, 2010 at 0:39
-
$\begingroup$ 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"? $\endgroup$– Yaroslav BulatovOct 3, 2010 at 1:07
-
1$\begingroup$ 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. :) $\endgroup$– J. M. isn't a mathematicianOct 3, 2010 at 14:22
|
Show 2 more comments
2 Answers
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ It seems like Halley's method is a hybrid between 1st order Taylor expansion and second order Taylor expansion books.google.com/… $\endgroup$ Oct 2, 2010 at 22:57
$\begingroup$
$\endgroup$
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.
answered Dec 22, 2010 at 15:56