# Least Square fit of a system of equations

I've a matrix equation $$\bar z^{(r)}(k + 1) = \bar{DF} ~ \bar z^{(r)}(k)$$. Now the $$\bar z$$'s and $$\bar{DF}$$ are $$d \times d$$ matrices. Now $$\bar{DF} = \begin{pmatrix} 0 & 1 & 0 & 0 & \cdots & 0 \\ 0 & 0 & 1 & 0 & \cdots & 0 \\ \vdots & & & & \\ 0 & 0 & 0 & 0 & \cdots & 1 \\ DF_{d1} & DF_{d2} & DF_{d3} & DF_{d4} & \cdots & DF_{dd} \\ \end{pmatrix}$$.

So my matrix equation boils down to, $$\bar z^{(r)}_{dj}(k+1) = \bar{DF}_{dk}\bar{z}^{(r)}_{kj}(k)$$.

There are $$d$$ unknowns and $$d$$ equations to solve them, and hence the problem can be solved. I know the $$\bar{z}$$ matrices.

My question is how can I evaluate this $$\bar{DF}$$ using least-square fit? My language of interest is Python, so pointers using numpy/scipy would be highly appreciated.

• Ok, so you know both $z$'s on the left- and right-hand side, and you want to evaluate the last row of the $DF$ matrix? If the $z$ would be vectors, you could solve for it exactly. As they're matrices, you get multiple equations for one element $DF_{di}$. First I would derive these equations, and only then I'd care about the (least square) solution. So can you add these equations to your question? Oct 5 '20 at 7:11
• @davidhigh Multiple equations for the $DF_{dj}$'s? I mean sure you need atleast $d$ equations to find $d$ unknows. But if I look at the right side, $\bar{DF} \bar z^{(r)}(k)$ and just multiply them out, wouldn't the last row of $\bar{DF}$ just multiply with the last col of $\bar z^{(r)}$ matrix? So its just one equation with all the $d$'s? I sure I'm missing something, but can't figure it! Could you shed some light?
– sbp
Oct 5 '20 at 8:03
• You get one equation for $DF_{dj}$ for each column of the $z$ matrix. And then, when you have multiple eauqtions for one unknown, you can't solve them exactly and thus use least squares. Oct 5 '20 at 8:32
• @davidhigh Right! I forgot that $\bar z$'s are $d \times d$ dimensional. Editing the ques. with the explicit equations. I thought the matrices would be a better alternative as I can then use Linear Algebra to simplify the problem at hand.
– sbp
Oct 5 '20 at 8:55

Ok, now it's too long for a comment, so I can try to answer your question right away. Let's write your matrix $$DF$$ as $$D+F$$ where $$D$$ is a matrix with only the last row filled with unknowns and $$F$$ has as only non-zero entries ones on the first subdiagonal. Then your equation becomes

$$z^{k+1} = (D + F) z^{k}\\ \rightarrow z^{k+1} - F z^{k} = D z^{k}$$ Writing it out element-wise leads to $$(z^{k+1} - F z^{k})_{ij} = \sum_{l=1}^d D_{il} z^{k}_{lj}$$ and due to the fact that only the last row of $$D$$ is nonzero this becomes (using the Kronecker-Delta) $$(z^{k+1} - F z^{k})_{ij} = \delta_{id} \sum_{l=1}^d D_{dl} z^{k}_{lj}$$

You see that a solution can only exists if the first $$(d-1)$$ rows of $$(z^{k+1} - F z^{k})_{ij}$$ are zero anyways. Moreover, with your choice of $$D$$, you have no effect in these dimensions. This means that when you want to find a least-squares solution, you are basically minimizing in the last dimension only. I'm not sure whether this is what you want.

But let's asusme it is intended. Then, for the last row, as $$(Fz^{k})_{dj} = 0$$, one gets $$z^{k+1}_{dj} = \sum_{l=1}^d D_{dl} z^{k}_{lj} \\ \rightarrow \sum_{l=1}^d (z^{k})^T_{jl} D_{dl} = z^{k+1}_{dj}$$ which is a linear equation for the unknown coefficients $$D_{dl}$$ with coefficient matrix $$(z^{k})^T$$, where $$T$$ means transpose, and right-hand side $$z^{k+1}_{dj}$$. And this you can solve with SciPy and whatever.

And again, what you get is a form of least square solution, but quite a special one where you solve in only one dimension exactly (at least if a solution exists), and do nothing in the all the other dimensions. (Put in geometrical terms: there is only one non-vanishing singular value of the matrix $$DF$$)

• Is there a problem with the indices of the last equation? As the expression stands now, the multiplication doesn't make sense.
– sbp
Oct 6 '20 at 6:27
• Plus you definitely meant $F$ to be a matrix with superdiag elements $1$ and rest all $0$, right?
– sbp
Oct 6 '20 at 7:11
• Yes, sorry, I meant superdiagonal, not subdiagonal. The multiplication makes sense, although it's not the "usual" form of the matrix product -- but it's the form that corresponds to the "usual" form of a linear system that you can directly translate to your code. Just consider the $D_{dl}$ and $z^{k+1}_{dj}$ as column vectors (and forget about the constant index $d$). Oct 6 '20 at 8:11
• Okay. Let me write this out, and if I have any issues, I'll get back. Thanks.
– sbp
Oct 6 '20 at 8:14
• This is what I did: $z^k$ is my $d \times d$ matrix, and $z^{k+1}$ is my vector containing the $d$'th element. And I did a numpy.lstsq($z^k$, $z^{k+1}$). The first out with $d$ elements is my least square fit. Does this sounds fine?
– sbp
Oct 6 '20 at 20:37