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.

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!

share|improve this question
    
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. –  J. M. 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

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer

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

share|improve this answer
    
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

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.