2
$\begingroup$

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!

  • 0
    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$?2012-08-12

2 Answers 2

2

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.

2

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

  • 0
    I am not solving any problem requiring the Newton algorithm right now, I was just asking in the general case...2012-08-12