0

I have a matrix of the form:

A1 A2 A3 A4 A5 A6  ... An P |
1   0 0  0  0   0  ... 0 -1 | c * f1
f1  1 0  0  0   0  ... 0 -1 | c * f2
f2 f2 1  0  0   0  ... 0 -1 | c * f3
f3 f3 f3 1  0   0  ... 0 -1 | c * f4
f4 f4 f4 f4 1   0  ... 0 -1 | c * f5
f5 f5 f5 f5 f5  1  ... 0 -1 | c * f6
........................ -1 | ......
fn fn fn fn fn fn  ... 1 -1 | c * fn
 1  1  1  1  1  1  ... 1  0 | c

I need to solve this linear system, but i just need to calculate the value of 1 variable (preferably P), the values of f1 to fn are known.

I'm supposed to write an algorithm to solve this one, but the matrix will have big ranks (n = 400 more or less) so solving by getting the inverse or by crammer rule is a little expensive for me. Is there a quicker solution? given that this matrix looks a lot like a triangular one, but i cant get it to take the correct form :(

Also, for the input im expecting, is inverting with gaussian elimination or crammers rule good enough?

I'm very bad at math, let alone linear algebra, but iI can see there is a pattern there, but I can't figure it out

cpacheco
  • 3

1 Answers1

2

The system can be written in the block form $$\tag{1} Ax:=\begin{bmatrix}L & -e \\ e^T & 0\end{bmatrix}\begin{bmatrix}a\\ p\end{bmatrix}=\begin{bmatrix}f \\ g \end{bmatrix}=:b, $$ where $a:=[a_1,\ldots,a_n]^T$, $e:=[1,\ldots,1]^T$, etc. Note that $L$ is lower triangular. To solve this is simple (no need to factorize anything or, worse, to actually attempt to use the Cramer's rule (please don't mention this rule in the numerical linear algebra section)). The first equation in (1) reads: $La-ep=f$; hence we have $a=L^{-1}(f+ep)$. The second equation in (1), $e^Ta=g$, gives hence $e^TL^{-1}(f+ep)=g$ and thus $$\tag{2} e^TL^{-1}e=g-e^TL^{-1}f. $$ To solve this efficiently, first solve $$ L^Th=e, $$ which can be done simply by the back substitution ($L^T$ is upper triangular). This transforms (2) to $$ (h^Te)p=g-h^Tf, $$ which is a scalar equation, and therefore $$ p=\frac{g-h^Tf}{h^Te}. $$

Algebraic Pavel
  • 22,928