0
$\begingroup$

Could someone please provide and explain the derivation of Newton-Raphson method in higher dimensions?

The derivation of this method from the definition of the derivative is intuitive but I don't understand the derivation from it to higher dimensions.

$\endgroup$
  • 1
    $\begingroup$ See what the excellent "numerical recipes" says (numerical.recipes) says about that. $\endgroup$ – Jean Marie Aug 20 '16 at 17:19
3
$\begingroup$

You are given a function $f$ of type ${\mathbb R}^n\to{\mathbb R}^n$, defined on some open set $\Omega$, and you want to solve the equation $f(x)=0$. You suspect that the point $p\in\Omega$ is already quite near to a solution $\xi$ of this equation. You then argue as follows: For small increments $X$ attached at $p$ one has $$f(p+X)=f(p)+df(p).X+ o(X)\qquad (X\to0)\ .\tag{1}$$ The aim is to choose $X$ such that $f(p+X)=0$. Neglecting the error term in $(1)$ this amounts to solving the linear equation (resp., system of $n$ equations in $n$ unknowns) $$df(p).X=-f(p)\ .$$ Technical assumptions aside one obtains the solution $$X=-\bigl(df(p)\bigr)^{-1}.f(p)\ ,$$ so that one is led to proposing $$q:= p-\bigl(df(p)\bigr)^{-1}.f(p)\tag{2}$$ as a better approximation to $\xi$ than $p$ was. This idea leads to the following iterative algorithm: $$x_0:=p,\qquad x_{n+1}:= x_n-\bigl(df(x_n)\bigr)^{-1}.f(x_n)\qquad(n\geq1)\ .$$ Of course it is a grand project (i) to set up exact assumptions that guarantee $\lim_{n\to\infty}x_n=\xi$, and (ii) to analyze the speed of convergence in case it actually takes place.

$\endgroup$
  • $\begingroup$ Thank you very much for your answer. I've a question about your notation: What is the meaning of $.$? The $df(p)$ is a matrix of derivatives like the hessian? $\endgroup$ – Bastian Aug 21 '16 at 8:05
  • $\begingroup$ The . should help the "parsing" by the reader. To the left of the . there is a linear map, $df(p)$ or $\bigl(df(p)\bigr)^{-1}$, and to the right of the . there is the vector to which this map is applied. $\endgroup$ – Christian Blatter Aug 21 '16 at 8:34
2
$\begingroup$

Let us admit that you need to solve $$f(x,y)=0 \qquad g(x,y)=0$$ and you have a starting point $(x_0,y_0)$. As, just as for Newton method with a single variable, approximate the function by its first order Taylor expansion (or its tangent plane if you prefer).

So, ignoring higher order terms,

$$f(x,y)\approx f(x_0,y_0)+(x-x_0) \frac{\partial f(x,y)}{\partial x}+(y-y_0) \frac{\partial f(x,y)}{\partial y}$$ $$g(x,y)\approx g(x_0,y_0)+(x-x_0) \frac{\partial g(x,y)}{\partial x}+(y-y_0) \frac{\partial g(x,y)}{\partial y}$$ all partial derivatives being computed at $(x_0,y_0)$. So, locally, let us write $$f(x_0,y_0)+(x-x_0) \frac{\partial f(x,y)}{\partial x}+(y-y_0) \frac{\partial f(x,y)}{\partial y}=0$$ $$g(x_0,y_0)+(x-x_0) \frac{\partial g(x,y)}{\partial x}+(y-y_0) \frac{\partial g(x,y)}{\partial y}=0$$ So, you have two linear equations to solve (variables being $x-x_0$ and $y-y_0$); get $x$ and $y$ and repeat the process for the newt step using $x_0=x$ and $y_0=y$; do that as long as the convergence criteria is not satisfied.

I am sure that you see how this generalizes to $n$ equations and variables.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.