3D matrix

[Ester]

hey y'all
i have those equations, and need to solve them in a C/C++ code

110x - 50y - 20z = -4
-50x +140y - 30z = -13
-20x - 30y + 60z = -4

the code should take x, y, z as inputs then find their values according to the above equations..anyone has an idea how?
thx y'all

[kedaman]

have a search on google on matrix libraries, you can solve a system of linear equation by putting the coefficients in a matrix and inverse it, and multiply by the constants (as a vector)

[Guv]

Finding inverse and multiplying by it is way too much work. Gauss Jordan elimination will solve equations, invert a matrix, or do both. When used for solving equations only, it does less work, although for a 3X3 system, it will be so fast the the extra work does not matter. Search for Gauss Jordan elimination or perhaps search for matrix operations.

There is at least one thread at this forum which describes Gauss Jordan elimination and provides VB code, which should not be hard to convert to C Code. A search at this site for Gauss or matrix should find the threads.

[Guv]

Cramer’s rule is a theoretical method found in text books. It would be crazy to use it in practice.

You can solve equations using Gauss elimination for about the same amount of computations as calculating a determinant. Cramer’s rule requires calculating (n +1) determinants to solve n equations in n unknowns. Cramer’s rule was never used except in elementary math courses for 2X2 or 3X3 systems. Even for small systems, it is too much work compared to elimination and/or substitution methods.

[Ester]

Hello guys
i attached an algorithm here, could u help me out with the C/C++ code

[transcendental]

What's so difficult to find a determinant of 3x3 matrix and doing it 4 times.

Det = A11*(A22*A33-A23*A32)
- A21*(A12*A33-A13*A32)
+ A31*(A12*A23-A13*A22)

Cramer's rule: Manual computation is too many work for a lazy person like me. But now it is the computer which is doing it.

Gauss method:Good for manual computation for a lazy person like me. but not so good for writing it for an inexperienced programmer.

[transcendental]

|P X X|
|X P X|
|X X P|

In some cases, it is possible to end up with a zero or near zero pivot, in which case a division by zero error will occur when the pivot equation is normalised(i.e. P=1)
during the forward pass of the elimination procedure.

[Guv]

Transcendental: If the largest system you want to solve is a 3X3, Cramer is plausible. Doing 4 times as much work on a modern computer does not cost much, and the coding is fairly easy. Even manually it is plausible if you have a good hand calculator. Using pencil and paper, I would still prefer elimination methods.

BTW: If solving small systems is not an every day job, you can solve at least half a dozen small systems by hand faster than you can write, debug, and use the code. Unless you are solving a lot of small systems, writing a program is not a practical way to do the job, although it might be more fun that doing the arithmetic.

I stand by my opinion that Cramer is not a good method.

Beyond a 3X3 or 4X4 system, I would not want to do the coding for the Cramer method. If forced to code Cramer for a big system, I would probably use Gauss elimination to calculate the determinants, which would be silly because for essentially the same coding effort you could implement Gauss elimination. The alternative to Gauss for evaluating a determinant seems to be some recursive algorithm.

Furthermore, I would be concerned about the precision obtained using Cramer’s rule to solve a large system.

In elimination methods, zero divisors are usually avoided by using the largest (in absolute value) element as the pivot divisor. This requires some swapping of rows and/or columns in the resulting matrix.

For large systems, consideration of numerical precision is important. Elimination methods tend to provide good precision if the largest possible divisor is always used. It is not sufficient to search for nonzero divisors.

[Guv]

Ester: Your algorithm seems correct, assuming that there is only one variable i (You show it as upper and as lower case). I am not familiar with the C or Pascal language you are using, so I might be misinterpreting something. I do not understand why you use aij and mij. I assume that you are referring to the same matrix.

BTW: It would be easier to Grok if you always used j for a column number and i for a row number. I tend to use j & k instead of i & j because i can be confused with the square root of minus one and I can be confused with the number one or the identity matrix.

In Step 2, I suggest searching for the element which is largest in absolute value instead of for the first non zero element. This tends to improve precision for large systems.

Step 5 does not seem essential if you modify step 6 to use [ Ej - (aij / aii )*Ei ].

I have not analyzed step 9, which I assume it correct. I have neither implemented nor analyzed back substitution. Every application I have encountered required the inverse of the matrix as well as the solution of the linear system. Steps 1-7 are computations used by Gauss elimination and steps 7-8 are obvious, but 9 is foreign to my background and I am too lazy to analyze its implications.

[Guv]

Ester: Can you be sure that all divisors used in step 9 are non zero?

[transcendental]

I had just implemented the gauss elimination code for Ester at the C++ forum. This code is supposed to take in any size of the matrix, just change the constants and compile will do.

Frankly speaking, I had a hard time, 'deciphering' the Ester's given algorithm.(Yeah yeah ok, I know I am not a mathematican.) In the end, I gave up halfway. Anyway I knew gauss elimination. I coded it whatever my brain remembers.

I agree that cramer's rule is for 3x3 but never did I say it is suitable for anything bigger than 3x3. My cramer suggestion is for the 3x3 example, Ester gave.

I vaguely remember that one can find det of any matrix by some cross diagonally multiplication method without using gauss to transform to triangular matrix for matrices bigger than 3x3.


Guv: next time, just call me 'trans'

My nick is a unfriendly nick, I emailed and requested John to change. John said it is not the VB-World policy to change nick for its members.

[transcendental]

Originally posted by Guv

Furthermore, I would be concerned about the precision obtained using Cramer’s rule to solve a large system.

Can you explain more on it? I am interested to know.

[Guv]

Trans: Numerical analysis is a tricky and sometimes difficult subject. Solving large systems of linear equations is known to cause problems.

First note that calculating a determinant by brute force application of the definition is not possible for a large matrix. For a 2X2, you have 2 products each with 2 factors. For a 3X3, you have 6 products, each with 3 factors. In general, N! Factors with N factors. When N is greater than 10-15, The N! Is too outrageous to allow brute force code. This forces something like Gauss elimination, although recursive methods using the cofactor definition might be feasible. I have never heard of anybody using recursion, and would be interested to know of the efficiency and precision of such a program if one has been implemented and used extensively.

Ordinary roundoff error tends to gets worse as the number of computations increase, but counting computations is misleading. For example: Adding 1000 products, with each product involving 2 positive factors would normally cause less roundoff error than adding 100 products with 4 positive factors each.

More serious than roundoff error is the loss of precision resulting from subtracting two nearly equal values and using the result as a multiplier or divisor in many subsequent calculations. This sequence of operations is inherent in most methods used to solve equations, invert matrices, and/or evaluate determinants. There might be iterative methods which minimize this type of precision loss (I am not sure that such methods exist. I know that some eigenvalue & eignevector solving methods are iterative, and I might be remembering them).

You can solve a large system for about the same amount of computations as evaluating a determinant. For an NXN system you have to evaluate (N + 1) determinants to use Cramer’s rule. EG: For a 100X100 system, you evaluate 101 determinants. Oddly enough, the ordinary roundoff error is not increased by this extra arithmetic. However, the probability of encountering the other type of precision loss is drastically increased.

Using divisors whose absolute value is greatest, improves precision because such values are less likely to have resulted from the subtraction of two nearly equal values. This localizes the effect of the precision loss due to the subtraction.

BTW: Polynomial evaluation is often done incorrectly. For example: Consider evaluating the following.

a*x^3 + b*x^2 +c*x + d

You could compute a*x^3, b*x^2, c*x and then add the four factors to get the result.

You could also evaluate as follows.

[ (a*x +b )*x + c ]*x + d

The latter method can readily be programmed using a For-Loop and an array of coefficients, which is easier than using the other method for high order polynomials. For many of the polynomials encountered in practice, the latter method also results is far less loss of precision. For example, the series used to evaluate sine, cosine, and e for values of x less than one are evaluated far more precisely using the latter method. When evaluating e^x, it is a good idea to evaluate something like (e^v)^8 where v = x/8 (The eighth power is evaluated by squaring the initial result 3 times).

[transcendental]

That's a very good explanation. Thanks.