I am trying to use the Newton method to a non square system. The jacobian matrix is not square and I cannot inverse it. Can anyone help? How can I calculate this 'inverse'?.
[Math] Finding the Jacobian of non square inverse matrix
calculuslinear algebranewton raphson
Related Solutions
Let $A$ be an $n\times m$ matrix. This matrix represents a linear transformation $L_A\colon\mathbb{R}^m\to\mathbb{R}^n$. A left inverse would correspond to a linear transformation $T\colon\mathbb{R}^n\to\mathbb{R}^m$ such that $T\circ L_A = \mathrm{Id}_{\mathbb{R}^m}$. For the composition to be the identity, it is necessary that $L_A$ be one-to-one; in particular, we need $m\leq n$ and for $A$ to be of full rank.
A right inverse would correspond to a linear transformation $U\colon \mathbb{R}^n\to\mathbb{R}^m$ such that $L_A\circ U=\mathrm{Id}_{\mathbb{R}^n}$. For the composition to be the identity, we need $L_A$ to be onto; in particular, we need $m\geq n$ and for $A$ to be of full rank.
In other words, a necessary condition for $A$ to have a one-sided inverse is that it be of full rank (that is, $\mathrm{rank}(A)=\min(n,m)$).
In fact, the condition is sufficient as well:
Suppose first that $n\leq m$ and $\mathrm{rank}(A)=n$. Then $L_A$ is onto, so $A\mathbf{e}_1,\ldots,A\mathbf{e}_m$ span $\mathbb{R}^n$; so we pare the set down to a basis. If $i_1\lt\cdots\lt i_n$ are such that $A\mathbf{e}_{i_j}$ are a basis for $\mathbb{R}^n$, then define $U\colon\mathbb{R}^n\to \mathbb{R}^m$ by $U(A(\mathbf{e}_{i_j})) = \mathbf{e}_{i_j}$ and extend linearly. Since the $A\mathbf{e}_{i_j}$ are a basis, this can be done and defines $U$ uniquely; clearly, $L_A\circ U=I_{\mathbb{R}^n}$; computing the coordinate matrix of $U$ relative to the standard basis of $\mathbb{R}^n$ gives a right inverse for $A$.
Next, suppose that $n\geq m$ and $\mathrm{rank}(A)=m$. Then $A$ is one-to-one, so $A\mathbf{e}_1,\ldots, A\mathbf{e}_m$ are linearly independent. Complete to a basis for $\mathbb{R}^n$, $A\mathbf{e}_1,\ldots,A\mathbf{e}_m,\mathbf{w}_{m+1},\ldots,\mathbf{w}_n$, and define $T\colon \mathbb{R}^n\to\mathbb{R}^m$ by $T(A\mathbf{e}_i)=\mathbf{e}_i$, and $T(\mathbf{w}_j)$ arbitrary (say, $\mathbf{0}$). Then $T\circ L_A=I_{\mathbb{R}^m}$; computing the coordinate matrix of $T$ relative to the standard basis of $\mathbb{R}^n$ gives a left inverse for $A$.
Note, moreover, that if $n\neq m$, then there are many different one-sided inverses for $A$ (when $A$ has full rank); so one should not talk about "the" left (or right) inverse of $A$.
Most numerical packages give you the option of either computing the Jacobian yourself and passing it to the solver, or of numerically approximating it with a finite difference scheme. I imagine that in general while performing Newton's method or other methods expressed in terms of an inverse Jacobian, these packages do not actually compute the inverse for reasons of stability. Instead, they solve the linear system $J(x_n) x_{n+1} = J(x_n) x_n - f(x_n)$ for $x_{n+1}$ at each time step.
The Jacobian is not always invertible; in order to use Newton's method the Jacobian must be invertible, though. You can see this in one dimension, with a function $\mathbb{R} \to \mathbb{R}$ with a critical point which is not an extremum.
Best Answer
About the Nihl's post, the so called "pseudo Newton method" - when we use the pseudo-inverse of the derivative -
We consider a system of $n$ equations in $p$ unknowns with $n\not= p$.
If $n<p$, for instance $f(x,y)=0$, then the pseudo Newton method gives a particular point on the curve $f(x,y)=0$.
If $n>p$, for instance $f_1(x,y)=f_2(x,y)=f_3(x,y)=0$, then it is more complicated. In general, there are no solutions. Assume that the $3$ curves intersect in $3$ nearby points $A,B,C$ (we are in this case when the intersection exists but, during the previous calculations, we did approximations). Eventually, the pseudo Newton method gives a point $P$ that is pretty much in the triangle $ABC$. Yet, if we put some weight on the curve $f_1$ (change $f_1$ with $5f_1$ for instance), then $P$ comes closer to the curve $f_1=0$.