C / C++ / MFC

Re: subroutine to solve linear algebraic equations - fewer unknowns than equations

8-Jul-10 7:50

mrby123 wrote:
Hi I am looking for subroutines to solve linear algebraic equations - fewer unknowns than equations

If I remember well, unless some of the equations are linearly dependent, you'll get no solutions for the unknows.
Smile | :)

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]

mrby1238-Jul-10 8:00

mrby123

8-Jul-10 8:00

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

Re: subroutine to solve linear algebraic equations - fewer unknowns than equations

CPallini8-Jul-10 9:59

Re: subroutine to solve linear algebraic equations - fewer unknowns than equations

8-Jul-10 9:59

Have a look at "Numerical Recipes in C", available for free here[^]: chapter 2 looks promising.
Smile | :)

Dr.Walt Fair, PE8-Jul-10 8:28

Re: subroutine to solve linear algebraic equations - fewer unknowns than equations

8-Jul-10 8:28

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

mrby1238-Jul-10 8:39

mrby123

8-Jul-10 8:39

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.

Re: subroutine to solve linear algebraic equations - fewer unknowns than equations

Dr.Walt Fair, PE8-Jul-10 8:51

Re: subroutine to solve linear algebraic equations - fewer unknowns than equations

8-Jul-10 8:51

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

CPallini8-Jul-10 9:22

Re: subroutine to solve linear algebraic equations - fewer unknowns than equations

8-Jul-10 9:22

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. Smile | :)

Dr.Walt Fair, PE8-Jul-10 18:09

Re: subroutine to solve linear algebraic equations - fewer unknowns than equations

8-Jul-10 18:09

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

CPallini8-Jul-10 21:22

Re: subroutine to solve linear algebraic equations - fewer unknowns than equations

8-Jul-10 21:22

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.
Smile | :)

Tim Craig8-Jul-10 21:38

Tim Craig

8-Jul-10 21:38

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.

Re: subroutine to solve linear algebraic equations - fewer unknowns than equations

CPallini8-Jul-10 22:19

Re: subroutine to solve linear algebraic equations - fewer unknowns than equations

8-Jul-10 22:19

Simply put, you cannot solve:

x + y  = 2
x - y  = 0
x + 3y = 4

Dr.Walt Fair, PE9-Jul-10 4:06

Re: subroutine to solve linear algebraic equations - fewer unknowns than equations

9-Jul-10 4:06

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 x<small>i</small> that minimizes S = Sum{[f<small>j</small>(x<small>i</small>) - C<small>j</small>]^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

CPallini9-Jul-10 4:22

Re: subroutine to solve linear algebraic equations - fewer unknowns than equations

9-Jul-10 4:22

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?

Smile | :)

Emilio Garavaglia10-Jul-10 4:29

Emilio Garavaglia

10-Jul-10 4:29

Yes, but you can solve

x + y  = 2 + a
x - y  = 0 + b
x + 3y = 4 + c

to find the x and y that makes a²+b²+c² 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.
D'Oh! | :doh:

Re: subroutine to solve linear algebraic equations - fewer unknowns than equations [modified]

CPallini10-Jul-10 5:05

Setting File Creation Time

10-Jul-10 5:05

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 = 0

emilio_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.
Smile | :)

modified on Saturday, July 10, 2010 11:21 AM

Fareed Rizkalla8-Jul-10 6:53

Fareed Rizkalla

8-Jul-10 6:53

I've been trying to put some code together for setting a desired file creation date/time.
I also got introduced to the FILETIME structure (2 DWORD).
DWORD unsigned long 4,294,967,296 (possibles, including zero)

Hopefully I can get a string to be processed and set the file creation date/time.

So these would be the variables for the DWORD:

1 second 100
1 minute 6,000
1 hour 360,000
24 hours 8,640,000
1 year 3,153,600,000

Current resources on MSDN use SystemTime functions, out of fear of guiding someone to fake copyrighted material.

HANDLE File = CreateFile(L"My File.txt", GENERIC_WRITE, FILE_SHARE_WRITE, NULL, OPEN_ALWAYS, FILE_WRITE_ATTRIBUTES, NULL);
SetFileTime( File, &CreationTime, NULL, NULL);
CloseHandle(File);

CPallini8-Jul-10 6:58

8-Jul-10 6:58

What's your point?
Confused | :confused:

Fareed Rizkalla8-Jul-10 7:47

Fareed Rizkalla

8-Jul-10 7:47

i want to set the file creation date to a specific time

CPallini8-Jul-10 22:52

8-Jul-10 22:52

This is what you want to do. Now, what is the question or problem?
Smile | :)

Maximilien8-Jul-10 7:11

Maximilien

8-Jul-10 7:11

what's the question ?

Watched code never compiles.

Fareed Rizkalla8-Jul-10 8:13

Fareed Rizkalla

8-Jul-10 8:13

i want to set the file creation date/time to a desired date/time