subroutine to solve linear algebraic equations - fewer unknowns than equations
-
Thanks for the useful comments. Yes, the subroutine would check the linear - dependency between equations and exclude those redundent equations. Yes, a least square technique is required to fine the mean and standard deviations.
I'm not sure how to remove redundant equations, but in case you need to use least squares to estimate a likely set of parameter values, you'll need to use statistical methods to estimate the precision. In a typical least squares solution, you would look at the variance-covariance matrix and use that to estimate the standard errors in the parameter estimates. In typical least squares there are some empirical methods to do all of that, but I'm not aware of a general algorithm.
CQ de W5ALT
Walt Fair, Jr., P. E. Comport Computing Specializing in Technical Engineering Software
-
Actually, if there are fewer unknowns than equations, you can have multiple means to solve for the unknowns. This is commonly exploited to check the consistency of equations, etc. The problem is how to ensure that some of the equations are not redundant. If the equations are inconsistent due to measurement errors or such, then you can use least squares and other techniques to come up with the best estimates (according to some criteria).
CQ de W5ALT
Walt Fair, Jr., P. E. Comport Computing Specializing in Technical Engineering Software
Walt Fair, Jr. wrote:
The problem is how to ensure that some of the equations are not redundant.
Walt Fair, Jr. wrote:
Actually, if there are fewer unknowns than equations
If such equations are not redundant then they are incompatible. :)
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler. -- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong. -- Iain Clarke
[My articles] -
You are right. I expect the subroutine can determine and exclude those equations linearly dependent to keep only those linearly independent. Then the subroutine solve those linearly independent equations. I assume the number of those linearly independent equations N>M (M is the number of unknowns) still. So the subroutine will get the mean and standard deviation for each unknowns. Thanks
Have a look at "Numerical Recipes in C", available for free here[^]: chapter 2 looks promising. :)
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler. -- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong. -- Iain Clarke
[My articles] -
Walt Fair, Jr. wrote:
The problem is how to ensure that some of the equations are not redundant.
Walt Fair, Jr. wrote:
Actually, if there are fewer unknowns than equations
If such equations are not redundant then they are incompatible. :)
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler. -- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong. -- Iain Clarke
[My articles]Well, if everything is perfect, then they would be incompatible. If there are measurement errors or other uncertainties, then they may all be valid estimates. That's exactly the situation that least squares estimates are designed to handle.
CQ de W5ALT
Walt Fair, Jr., P. E. Comport Computing Specializing in Technical Engineering Software
-
Well, if everything is perfect, then they would be incompatible. If there are measurement errors or other uncertainties, then they may all be valid estimates. That's exactly the situation that least squares estimates are designed to handle.
CQ de W5ALT
Walt Fair, Jr., P. E. Comport Computing Specializing in Technical Engineering Software
In the least square estimate you find the set of parameters that best fits the experimental data into the given equation. You have not incompatible equations. Generally speaking, if you have more independent equations than unknows then you cannot find a solution. :)
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler. -- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong. -- Iain Clarke
[My articles] -
In the least square estimate you find the set of parameters that best fits the experimental data into the given equation. You have not incompatible equations. Generally speaking, if you have more independent equations than unknows then you cannot find a solution. :)
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler. -- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong. -- Iain Clarke
[My articles]And Walt is correct that there's a linear algebra method for doing least squares to find the "best" solution to the equations. If you have M equations and N unknowns, you have an MxN matrix times a Nx1 vector of unknowns giving a known Nx1 vector. You multiply both sides by the transpose of the matrix giving an (NxM) x (MxN) x (Nx1) = (Nx1) so you end up with an NxN matrix to do your solution with. If I remember right, the underlying principle is finding the best "projection".
Once you agree to clans, tribes, governments...you've opted for socialism. The rest is just details.
-
And Walt is correct that there's a linear algebra method for doing least squares to find the "best" solution to the equations. If you have M equations and N unknowns, you have an MxN matrix times a Nx1 vector of unknowns giving a known Nx1 vector. You multiply both sides by the transpose of the matrix giving an (NxM) x (MxN) x (Nx1) = (Nx1) so you end up with an NxN matrix to do your solution with. If I remember right, the underlying principle is finding the best "projection".
Once you agree to clans, tribes, governments...you've opted for socialism. The rest is just details.
Simply put, you cannot solve:
x + y = 2
x - y = 0
x + 3y = 4:)
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler. -- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong. -- Iain Clarke
[My articles] -
Simply put, you cannot solve:
x + y = 2
x - y = 0
x + 3y = 4:)
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler. -- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong. -- Iain Clarke
[My articles]CPallini wrote:
Simply put, you cannot solve: x + y = 2 x - y = 0 x + 3y = 4
You most certainly can find a solution. Whether it makes sense or not depends on what the equations represent. If, due to measurement or statistical errors, they really are representing the same set of parameters, then you can use least squares. If all have the same importance and have been correctly normalized, etc., blah, blah, you simply find the minimum of:
[(x + y - 2)^2 + (x - y)^2 + (x + 3*y - 4)^2] w.r.t. x and y
If the minimum happens to be zero, the solution is exact. Otherwise it is an estimate of the parameters. The formal mathematical statement of the problem is something like
Find the set of xi that minimizes S = Sum{[fj(xi) - Cj]^2}.
You can also add additional constraints to bound the problem and turn it into a nonlinear optimization problem.
CQ de W5ALT
Walt Fair, Jr., P. E. Comport Computing Specializing in Technical Engineering Software
-
CPallini wrote:
Simply put, you cannot solve: x + y = 2 x - y = 0 x + 3y = 4
You most certainly can find a solution. Whether it makes sense or not depends on what the equations represent. If, due to measurement or statistical errors, they really are representing the same set of parameters, then you can use least squares. If all have the same importance and have been correctly normalized, etc., blah, blah, you simply find the minimum of:
[(x + y - 2)^2 + (x - y)^2 + (x + 3*y - 4)^2] w.r.t. x and y
If the minimum happens to be zero, the solution is exact. Otherwise it is an estimate of the parameters. The formal mathematical statement of the problem is something like
Find the set of xi that minimizes S = Sum{[fj(xi) - Cj]^2}.
You can also add additional constraints to bound the problem and turn it into a nonlinear optimization problem.
CQ de W5ALT
Walt Fair, Jr., P. E. Comport Computing Specializing in Technical Engineering Software
Yes, you may indeed solve another problem, namely:
Given
f(x,y)=(x+y-2)^2 + (x-y)^2 + (x+3*y-4)^2
find the value of the pair {x,y} which minimize f(x,y).
However, that has not to do with the original linear algebric system. The algebric system has not solutions according to the Rouché-Capelli theorem (and common sense). Anyway, might be the OP really needed the solution to the least squares problem (i.e. I misunderstood his requirements), who knows? :)
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler. -- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong. -- Iain Clarke
[My articles] -
Simply put, you cannot solve:
x + y = 2
x - y = 0
x + 3y = 4:)
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler. -- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong. -- Iain Clarke
[My articles]Yes, but you can solve
x + y = 2 + a
x - y = 0 + b
x + 3y = 4 + cto find the x and y that makes a2+b2+c2 the minimum possible. Clearly they will be not the "solution" of the system, but the value that minimize the "error" in having AX != B Also note that - even in case of linear dependency - the method works well (it just gives the solution with a null minimum squared error, that is the -at that point- one and only solution). Note also (not directly related to the post in answer) that saying that one particular equation is redundant is improper: all equation have the same dignity. Hence "find which equation to exclude" is a mis-posed problem. I can exclude another and get the same solution.
2 bugs found. > recompile ... 65534 bugs found. :doh:
-
Yes, but you can solve
x + y = 2 + a
x - y = 0 + b
x + 3y = 4 + cto find the x and y that makes a2+b2+c2 the minimum possible. Clearly they will be not the "solution" of the system, but the value that minimize the "error" in having AX != B Also note that - even in case of linear dependency - the method works well (it just gives the solution with a null minimum squared error, that is the -at that point- one and only solution). Note also (not directly related to the post in answer) that saying that one particular equation is redundant is improper: all equation have the same dignity. Hence "find which equation to exclude" is a mis-posed problem. I can exclude another and get the same solution.
2 bugs found. > recompile ... 65534 bugs found. :doh:
emilio_grv wrote:
Yes, but you can solve x + y = 2 + ax - y = 0 + bx + 3y = 4 + c to find the x and y that makes a2+b2+c2 the minimum possible.
That is just another 'new' different problem. And what would be the 'practical' usefulness of the solution of such new problem is questionable. Consider, for instance, if the original system is, by remote chance:
x = 1000
x = 0emilio_grv wrote:
Note also (not directly related to the post in answer) that saying that one particular equation is redundant is improper: all equation have the same dignity. Hence "find which equation to exclude" is a mis-posed problem. I can exclude another and get the same solution.
It was a quick way to say: "when you have two linearly dependent equations, you may esclude one of them to find the solution", of course all the equations have the same dignity in the system, anyway you can arbitrarly choose one to solve the system. :)
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler. -- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong. -- Iain Clarke
[My articles]modified on Saturday, July 10, 2010 11:21 AM
