# Newton algorithm for a function in $\mathbf{R}^n\rightarrow \mathbf{R}$

I am curious on how the Newton algorithm would work to solve an equation of the type: $f(x_1,\dots,x_n)=0$.

As far as I understand, in dimension $1$, one solves $f(x)=0$ by starting with some $x_0$, and building the sequence $(x_n)$ defined by $x_{n+1} = x_n-\frac{f(x_n)}{f'(x_n)}$.

My concern is that I don't see how to generalize this in multiple dimension. Indeed, if I start the algorithm with $x^0=(x_1^0,\dots,x_n^0)$, then I will approximate my equation $f(x_1,\dots,x_n)=0$ by $f(x_1^0,\dots,x_n^0)+\displaystyle\sum_{i=0}^n \frac{\partial f(x^0)}{\partial x_i}(x^1_i-x^0_i)=0$, and then I don't see how I can find $x^1$ as this equation will have an infinite number of solutions...

Please let me know if I am missing something obvious, or if there is a smart trick to choose $x^1$.

Thanks!

-
In fact, for a smooth function $f(x,y)=0$ represents a curve, not a single point. –  enzotib Aug 12 '12 at 14:47
@enzotib errr... Yes, that's the obvious thing I was missing! Well, I guess that answers my question... you can put your comment as an answer then and I will accept it. –  S4M Aug 12 '12 at 14:51
In fact, as always, you need $n$ equations and $n$ unknowns to do something like Newton-Raphson. In particular, your derivative is now replaced with inverting the Jacobian of your system of equations. –  Guess who it is. Aug 12 '12 at 14:58
You could pick a variable, or a line of the form $\phi(t) = x + t h$ and apply Newton's method to $f \circ \phi$? –  copper.hat Aug 12 '12 at 15:11

For a smooth function of more than one variable, the solution to the equation $$f(x_1,\ldots,x_n)=0$$ is not a single point in $\mathbb{R}^n$ but zero or more hypersurfaces (that only in some particular situation could reduce to a single point).

For example, in the simple case of two variable $f(x,y)=0$ represents a curve.

-

The first order Taylor series expansion of $f(\mathbf{x})$ about $\mathbf{x} = \mathbf{x}_t$ is:

$f(\mathbf{x}) \approx f(\mathbf{x}_t) + \nabla f(\mathbf{x}_t)^T(\mathbf{x} - \mathbf{x}_t)$

where $\nabla f(\mathbf{x}_t)$ is the gradient vector at $\mathbf{x} = \mathbf{x}_t$. Setting the above approximation to $\mathbf{0}$, we get:

$\nabla f(\mathbf{x}_t)^T(\mathbf{x} - \mathbf{x}_t) = -f(\mathbf{x}_t)$

In general, this equation will have multiple solutions of $\mathbf{x}$. Thus, you will end up with a family of new points $\mathbf{x}_{t+1}$, and ultimately, a family of solutions satisfying $f(\mathbf{x}) = 0$.

-
Yes, that's is what @enzotib mentionned, and that I completely didn't realize when asking the question. –  S4M Aug 12 '12 at 15:28
Right. Do you have any additional constraints on $x$ and $y$ which might make the solution unique? –  Kartik Audhkhasi Aug 12 '12 at 16:12
I am not solving any problem requiring the Newton algorithm right now, I was just asking in the general case... –  S4M Aug 12 '12 at 17:39