3

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}$

J. M. ain't a mathematician
  • 75,051
Yaroslav Bulatov
  • 5,327

2 Answers2

1

What you probably want is the Euler-Chebychev method for functions $F:\Bbb R^n\to\Bbb R^n$, a multi-dimensional generalization of the Halley method.

You know that $s=-F'(x)^{-1}F(x)$ gives $F(x+s)=O(s^2)$ and thus $(x+s)-x^*=O(s^2)$. Now add a further refinement $v=O(s^2)$ based on the values at the point $x$ and disregard any terms $O(s^3)$, \begin{align} F(x+s+v)&=F(x)+F'(x)(s+v)+\frac12F''(x)[s+v,s+v]+O((s+v)^3)\\ &=F'(x)v+\frac12F''(x)[s,s]+O(s^3) \end{align} Thus with $v=-\frac12F'(x)^{-1}F''(x)[s,s]$ (which is indeed $O(s^2)$) you obtain a third order method, \begin{align} s_n&=-F'(x_n)^{-1}F(x_n)\\ x_{n+1}&=x_n+s_n-\frac12F'(x_n)^{-1}F''(x_n)[s_n,s_n] \end{align}

For non-square systems replace the inverse matrix by the Moore-Penrose pseudo-inverse of $F'(x_n)$ to get cubic convergence to a point of minimal error.

Lutz Lehmann
  • 126,666
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.

user061703
  • 3,877
John D. Cook
  • 7,038
  • 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. ain't a mathematician Sep 30 '10 at 23:44