MHB How to Translate Univariate Newton's Approximation to Multidimensional Systems?

[Purplepixie]

Hello,
I am having difficulty in translating the univariate Newton's approximation {Xn = Xn-1 - [ f(Xn-1) / f'(Xn-1)]} into the multidimensional case. My multidimensional equation system is y = F.x where y and x are (nx1) column vectors and the coefficients matrix F is (nxn), so that (nx1) = (nxn).(nx1) = (nx1).

I have translated the univariate Newton's approximation to the n-variate case as:
x2 = x1 - (F.x1 / F'.x1) <=> x1 - (F.x1).Inv(F'.x1)

But F'.x1 is a nx1 column vector and has no inverse. I then thought that perhaps the x1's cancel out . But if so then we would have x2 = x1 - F.Inv(F') with the last term a nxn matrix, so (nx1) = (nx1) - (nxn), which is not possible.

Your assistance would be greatly appreciated!

(This is my first post incidentally, so pls excuse any breaches of protocol)

 

[I like Serena]

Hello,
I am having difficulty in translating the univariate Newton's approximation {Xn = Xn-1 - [ f(Xn-1) / f'(Xn-1)]} into the multidimensional case. My multidimensional equation system is y = F.x where y and x are (nx1) column vectors and the coefficients matrix F is (nxn), so that (nx1) = (nxn).(nx1) = (nx1).

I have translated the univariate Newton's approximation to the n-variate case as:
x2 = x1 - (F.x1 / F'.x1) <=> x1 - (F.x1).Inv(F'.x1)

But F'.x1 is a nx1 column vector and has no inverse. I then thought that perhaps the x1's cancel out . But if so then we would have x2 = x1 - F.Inv(F') with the last term a nxn matrix, so (nx1) = (nx1) - (nxn), which is not possible.

Your assistance would be greatly appreciated!

(This is my first post incidentally, so pls excuse any breaches of protocol)

Hi Purplepixie, welcome to MHB!

First we have to establish what $F'$ is.
If it is a matrix that does not depend on any variable, then $F'$ is the matrix that contains only zeroes.
Consequently we won't really get any useful result.

Newton's approach aims to solve $f(x)=0$, and makes use of the fact that $f(x) \approx f(x_0) + f'(x)(x-x_0) \implies x_0\approx x - \frac{1}{f'(x)}\cdot f(x)$.
We might try to solve $F(x_1,\ldots,x_n)=(0,\ldots, 0)$ in a similar fashion. In this case $F$ is not a matrix, but a set of $n$ functions. And each function has $n$ parameters.
If we take the derivative, we don't have just 1 derivative, but instead we have the derivatives of $n$ functions with respect to each of the $n$ parameters.
The result is a matrix of $n\times n$ derivatives. Let's call it $DF(x)$ to denote that it's a matrix of functions that depend on $x$.
Now we can write Newton's approximation as $x^{(k+1)} = x^{(k)} - \Big(DF(x^{(k)})\Big)^{-1}\cdot F(x^{(k)})$, where $x^{(k)}$ denote the successive approximations of $x$.

 

[Purplepixie]

Dear Klaas,
Thank you for your clear and succinct explanation. I can now see where I was wrong. So much of mathematics would be simplified if representational systems could be improved!
All the best,
PP