at the moment I am working on an application where I have to solve some systems of linear equations during the whole algorithm.
Because the programming-language I have to use is something related to Fortran77 (which uses 'float' as number-format) and sometimes the Matrices are badly scaled, I choose this gaussian-elimination-with-pivoting-script and adapted it for my programming-language. This works pretty well.
Now I have the problem that sometimes the equation-system is over-determined and this couldn't be handled by the script I mentionned before.
Does anyone know if there is somewhere an efficient script to solve determined systems as well as over-determined systems which I can use (e.g. with QR-decomposition [determined] and least-squares [over-determined])?
Here are 2 examples of typical matrices that can occur (A is the coefficient-matrix and b the disturbing-vector):
[the determined one]
A = [ 3.91126953294906e-13 0.000290530407713016 0.118719995662381 0.999861140092325;
-7.47034897265332e-13 -0.000158174186504138 -0.0169130360585405 -9.28246904902663e-06;
1.42680307002891e-12 8.61151625166872e-05 0.00240945754016845 8.61761980650444e-11;
-2.72512972030656e-12 -4.68838903437727e-05 -0.000343255085472549 -8.00038984641107e-16 ]
b = [ -0.000272415115940619; -9.83039417624391e-07; 1.42984225458907e-07; 3.29280620635692e-09 ]
(in Matlab i get: rank(A) = 4 and rank([A, b]) = 4 $\rightarrow$ one solution exists)
[the over-determined one]
A = [ 9.71932695068104e-21 1.95542531016539e-06 0.0319594622483047 0.999775498752868;
-7.90937295921570e-21 -4.53931579859449e-07 -0.00194341016115096 -3.96425686254142e-06;
6.43647249705794e-21 1.05375479248690e-07 0.000118176051434193 1.57188613761892e-11;
-5.23785873026922e-21 -2.44618178588262e-08 -7.18612026002067e-06 -6.23275967050862e-17 ]
b = [ 4.42616984297712e-05; -1.36475494887893e-06; 9.48249135038941e-08; 3.66966454607991e-09 ]
(in Matlab this leads to rank(A) = 3 and rank([A, b]) = 4 $\rightarrow$ over-determined
So ... now I am looking for a code-snippet or something like this which can find solutions for both systems. I don't know if there exist one or which method is the best. Is it a QR-decomposition (with least squares) ...
I hope that somebody has a little hint for me or can help me ... that would be great. Thank you in advance!
Hint
Say that you have $n$ nonlinear equations to solve for $m$ variables $$f_i=f_i(x_1,x_2,\cdots,x_m)=0$$ What you can do is to minimize $$\Phi(x_1,x_2,\cdots,x_m)=\sum_{i=1}^n f_i^2$$ Now, the Jacobian of $\Phi$ gives you as many equations as variables.
Gauss-Newton method is a good candidate, provided "reasonable" starting values (except if the $f_i$ are just linear functions; in such a case, the solution is direct).
As you mentionned, the problem is very similar to least-square fit.