Equation solver

RazoR · #1 17-May-2008, 01:51

I'm supposed to make a program that would solve a system of linear equations that has n equations and the same number of unknowns and the equations have to be read from a text file. e.g. I have 5 equations and 5 unknowns, the program reads them from a file and give me the solutions. It doesn't matter what method I use.

This is actually a part of my calculator program that I have to make for a school project and it's the last part.

If anyone has any ideas pls help.

davekw7x · #2 17-May-2008, 10:20

Quote:

Originally Posted by RazoR

...program that would solve a system of linear equations...

Maybe you could start here: Gaussian Elimination on Wikipedia

There is some pseudo-code for solving the system. Since this is obviously not your first program, maybe you can figure out how to make a real C program out of it. If you have problems implementing the program, then show us what you came up with and ask specific questions.

You can follow other links (from Wikipedia, or do your own web search) for topics like "Gauss Reduction", "Gauss-Jordan," and such things.

Regards,

Dave

RazoR · #3 17-May-2008, 16:47

Although this is not my first program, I am a noob and I'm having trouble with some parts of my program.
The first big problem is turning a system of equations into a matrix. I know it has to be done with a loop, but I have no idea how should that loop look like.
You don't have to write the whole code, just give me a hint or something.

davekw7x · #4 18-May-2008, 09:24

Quote:

Originally Posted by RazoR

...The first big problem is ...

No. The first big problem is to make a more precisely stated program specification that describes what the input is to the program and what the output is and what the program is supposed to do as it works on the input to get the output. If you weren't given a precisely stated program specification, then you should write one and submit it with your assignment. Sometimes I actually put the specification into comments at the beginning of the program file so that I know it won't get "lost" if I need it in the future (or if I give the program to someone else)>

For example, I assume that you want a general-purpose equation solver that can handle different problem sizes, not just a program that solves systems of, say, five equations and five unknowns.

You indicate that you want to get problem information from a file. This means the program is to read matrix and right-hand side vector values from a file. How is the program supposed to know the size of the system? I'm thinking that it should read that from the file also.

So, for starters you can define the problem as follows:

1. The program will read a positive integer value from the file. This will indicate the size of the system.

2. Then the program will read the matrix values from the file. The values are presented in row-major order. That is, if the size is n the program will read m[0][0],m[0][1],...m[0][n-1],m[1][0],m[1][1],...,m[1][n-1],...,m[n-1][0],...,m[n-1][n-1]

3. Then the program will read the values of the right-hand side vector b[0],b[1],...,b[n-1]

4. If the program cannot obtain a valid value for n (that is, n must be greater than or equal to 2, for example), or if there is a problem reading any of the other values, the program will report the exact nature of the problem to the user and exit.

5. Assuming input was valid, then the program will solve the system ax=b and print the solution vector x[0],x[1],...,x[n-1]

6. If the system does not have a unique solution (that is, if matrix m is singular) the program will report that to the user.

Now, after writing the program specification you must address implementation details. This includes the program structure as well as an indication of what approach you will use to solve the system.

A reasonable program structure would be to put the actual solving part into a function. I say this for two reasons:

1. For now, you can concentrate on reading the problem information from the user's file and defer implementation of the solution for later. You can write a complete program with a "dummy" function that actually doesn't solve the system.

2. If you decide to solve the system with Gauss Reduction and back substitution and later decide to try Gauss-Jordan or LU decomposition or SVD decomposition or some other method, the main() function (and all of the work done to read input values) will not have to be changed. You simply change the solution function.

I strongly recommend that you visualize and specify a complete program (that calls the "dummy" function) before actually starting to write code. I know you are impatient to get started, but I am suggesting that you organize things first.

Now, write an interface specification for the solution function. Suppose we call the function ??? solve(???).

What are the parameters for this function? What does it have to get and what does it have to give back to the calling function?

It has to be told the size of the system. (How else would it know how to perform the various operations on the matrix and right-hand side?)

It has to be given the n-squared matrix values and the n values of the right-hand side vector.

It has to give back the n values of the solution vector if one exists. If the matrix turns out to be singular (so that a unique solution does not exist), it should let the calling program know, somehow, that it failed.

Now, in C, you can not pass an array to a function. A function can not return an array. You can't do it. Period.

What you can do is pass pointers back and forth.

Here's one generic description of the functions interface:

1. Integer input parameter indicating the size of the system.

2. Pointer input parameter. It points to a 2-D array, which contains the matrix values.

3. Pointer input parameter. It points to a 1-D array, which contains the right-hand side vector.

4. Pointer input parameter. It points to a 1-D array, which contains the solution vector.

Return value is an integer. A return value of 0 means that no solution is possible. A return value of 1 means that the solution has been stored in memory pointed to by the fourth input parameter.

Now, for the very first time, we get into some implementation details. If you have already written parts of the program, you might have to throw them away and start all over again. (Or, maybe not. Maybe you won't have to throw anything away; I just know that when I start implementing too soon I often have to undo and redo in a different way.)

Since the size of the system is not known ahead of time (it's part of the input part of the program specification), we can't allocate arrays ahead of time.

Now a little bifurcation, depending on what you have had in class and what you are expected to use in your project.

Actually, we could simply allocate some fixed arrays for the matrix and vectors. We would make their sizes larger than the largest expected system sizes. Suppose we decide to declarations as

CPP / C++ / C Code:

    double a[10][10];
    double b[10];
    double x[10];

Now if we read a value of n from the user that is greater than 10, we would tell the user that his system is too large and the program would bail out. For beginners, that may not be an unreasonable restriction (we could make the sizes 100 if we wanted to), and we could rewrite the program specification to indicate what the maximum size if the system can be.

Since I don't know whether you were given a program specification or not, I can't say whether this is acceptable or not. I also don't know what you have covered in class, so I don't know whether you are expected to use dynamic memory allocation (functions like malloc()). I will say that for practical C programs using matrices and vectors whose exact sizes are not known until run time, that dynamic storage allocation is really the way to go.

So: Have you had 2-D dynamic memory allocation or not?

The thing is, that the actual program details will have statements like

CPP / C++ / C Code:

   
    for (i = 0; i < n; i++) {
        for (j = 0; j < n ; j++) {
            /* do some stuff with a[i][j] and maybe b[j]*/
        }
    }

In other words the notation inside the function is the same whether you declare a the matrix with fixed size or whether you use dynamic array allocation for the matrix. The parameter declaration is different and incompatible. So you have to decide right now (before you start actually writing code) the exact nature of the function parameters.

For dynamic allocation, your program skeleton would be

CPP / C++ / C Code:

#include <stdio.h>

int solve(int, double **, double *, double *);

int main()
{
    int result;
    int n;      /* The size of the sysem               */
    double **a; /* The matrix of equation coefficients */
    double *b;  /* The right-hand side vector          */
    double *x;  /* The solution vector                 */

    /* 
     * Put stuff here to read n and allocate storage
     * for the matrix and vectors
     */

    result = solve(n, a, b, x);

    return 0;
}

int solve(int n, double ** a, double *b, double *x)
{
    /* Put stuff here to solve the system.
     *
     * It will involve a[i][j], b[i], x[i]
     * where i and j are greater than or equal to
     * 0 and less than n
     *
     */

    return 1;
}

If you decide to use fixed arrays, the program skeleton could be:

CPP / C++ / C Code:

#include <stdio.h>
/* 
 * Note that MAX_SIZE is only needed if we are
 * going to use fixed size arrays
 *
 * By expressing the largest acceptable system size
 * as a macro, we can change it without changing
 * any other source code in the entire program
 *
 */

#define MAX_SIZE 10

int solve(int, double [][MAX_SIZE], double *, double *);

int main()
{
    int result;
    int n;      /* The size of the sysem               */
    double a[MAX_SIZE][MAX_SIZE]; /* The matrix of equation coefficients */
    double b[MAX_SIZE];           /* The right-hand side vector          */
    double x[MAX_SIZE];           /* The solution vector                 */

    /* 
     * Put stuff here to read n. If n is greater
     * than MAX_SIZE then inform the user and
     * bail out
     */

    result = solve(n, a, b, x);

    return 0;
}

int solve(int n, double a[][MAX_SIZE], double *b, double *x)
{
    /* Put stuff here to solve the system.
     *
     * It will involve a[i][j], b[i], x[i]
     * where i and j are greater than or equal to
     * 0 and less than n
     *
     */
    return 1;
}

Note that the actual source code inside the function will be exactly the same for either case. The code that the compiler generates for the functions is vastly different.

Now, as for your question about reading values from a file into the matrix:

CPP / C++ / C Code:

    char *inname = "data.txt";
    FILE *infile;
    infile = fopen(inname, "r");
    if (infile == NULL) {
        printf("Can't open file %s for reading.\n", inname);
        return 0;
    }
    printf("Opened file %s for reading.\n", inname);
    if (fscanf(infile, "%d", &n) != 1) {
        printf("There was a problem reading n from the file.\n");
        return 0;
    }
    if ((n < 2) || (n > MAX_SIZE)) {
        printf("%d is an invalid value for n\n", n);
        return 0;
    }

    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (fscanf(infile,"%lf",&a[i][j]) != 1) {
                printf("There was a problem reading a[%d][%d]\n", i, j);
                return 0;
            }
        }
    }

Main points:
1. Check for valid input as much as you possibly can. Never trust the input to be correct.
2. Be as explicit as you can when the program terminates abnormally. Make it as "user friendly" as humanly possible (or as programatically possible).

Regards,

Dave

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
sudoku solver	seprich	C Programming Language	7	17-Oct-2007 08:27
Heat Equation	degoman	C Programming Language	1	20-Jun-2007 14:53
MPI with C (Solving Linear Equation using Gauss-Seidel Iteration)	trainz13	C Programming Language	7	01-May-2007 22:38
How to print an equation in order of precedence of operators	shoegoe	C Programming Language	7	02-Nov-2006 14:14
::Need help Please:: using If & Switch in Quadratic equation.	internetbug	C Programming Language	6	07-Apr-2005 17:36

Equation solver

Re: Equation solver

Re: Equation solver

Re: Equation solver