solves systems of linear equations

Discussion in 'C++' started by e4321, Jan 13, 2009.

  1. e4321

    e4321 New Member

    Joined:
    Jan 13, 2009
    Messages:
    4
    Likes Received:
    0
    Trophy Points:
    0
    This question is to develop a program that solves systems of linear equations. Assume the number of equations is always the same as the number of unknowns. The general form of such a system is as follows:

    a11x1 + a12x2 + … + a1nxn = b1,
    a21x1 + a22x2 + … + a2nxn = b2,

    an1x1 + an2x2 + … + annxn = bn.

    Your program first asks the user to enter the number n of unknowns. Then ask the user to enter the coefficients and the constant term of each equation, one equation in one line. For instance, if n is 3, the user may enter the following:

    120 -32.1 20.4 50
    1.6 -3.5 2.7 1
    -0.2 0.15 0.09 0

    This input represents the following system of equations

    120x1 -32.1x2 + 20.4x3 = 50,
    1.6 x1 -3.5 x2 + 2.7 x3 = 1,
    -0.2x1 + 0.15x2 + 0.09 x3 = 0.

    A 2-dimensional array is built dynamically to store the input data (so-called the augmented matrix of the system of equations). Then use an algorithm, called scaled Gauss elimination with backward substitution, to solve this system of equations. The algorithm is as follows:

    First, divide each of the equations by the coefficient that has the largest absolute value (not including the constant term) to convert this system to a so-called normalized system of equations. Then use the Gauss elimination algorithm:

    Suppose the normalized system is as follows:

    a11x1 + a12x2 + … + a1nxn = b1,
    a21x1 + a22x2 + … + a2nxn = b2,

    an1x1 + an2x2 + … + annxn = bn.

    Find the coefficient in the first column (a11, a21, …, an1) with the largest absolute value. If ai1 is the largest, swap equation 1 with equation i. Then, we may assume a11 has the largest absolute value. If this value is zero, this system does not have a unique solution. Output an error message and terminate the program. Otherwise, denote the i-th equation by Ei. Replace Ei by Ei - E1 * (ai1 / a11), i = 2, 3, …, n. After that, in the first column, all coefficients under a11 become 0. The system has the following form:

    a11x1 + a12x2 + … + a1nxn = b1,
    a22x2 + … + a2nxn = b2,

    an2x2 + … + annxn = bn.

    Next, find the coefficient among a22, a32, …, an2 that has the largest absolute value. If aj2 has the largest absolute value, interchange E2 and Ej. Then we may assume a22 has the largest absolute value. If this value is zero, this system does not have a unique solution. Output an error message and terminate the program. Otherwise, Replace Ei, i = 3, 4, …, n, by Ei - E2 * (ai2 / a22). Then all coefficients under a22 become zero.

    Keep doing this. Finally, we have a system that has the so-called echelon form:

    a11x1 + a12x2 + a13x3 + … + a1nxn = b1,
    a22x2 + a23x3 + … + a2nxn = b2,

    annxn = bn,

    where aii are not zero, i = 1, 2, …, n.

    In the last step, find the values backwards: Form the last equation, we have

    xn = bn / ann.

    Substituting this value into the second last equation, we have

    xn-1 = (bn-1 - an-1, nxn-1) / an-1, n-1.

    In this way, we can find xn-2, xn-3, … . Finally,

    x1 = (b1 - a12x2 - a13x3 -- a1nxn) / a11.

    To make your calculation more accurate, all coefficients should be of the type long double. In this algorithm, we need to check whether a coefficient is zero. However, it is not good to compare a double value with zero because a real number may not be expressed by a binary number accurately. You should consider a value being zero if its absolute value is less than, say, 10-10.

    At the end of the program, don't forget to free the memory used by the dynamic array.

    2. This question is to review how to manipulate c-strings and linked lists. (Do not use C++ class string in this question).

    You know that there is a method called tokenize in Java, which separates a string into parts according to a set of specified characters called delimiters. Unfortunately, there is no such built-in function in C++. This question is to write such a function tokenize( ). This function accepts two strings. The first string is to be tokenized, and the second string contains all delimiters. For instance, if the first string is "sin(x)+cos(y)-tan(z)", and the second string is "+_()", then this function should separate the first string into the following tokens:

    "sin", "(", "x", ")", "+", "cos", "(", "y", ")", "-", "tan", "(", "z", ")"

    Each delimiter is also regarded as a token.

    Note that, if you have two delimiters side by side (as ")+" and ")-" in the previous example, you should not have an empty token between them.

    Your function should return a linked list that stores the tokens of the input string in the same order as they are in the input string. The node of the linked list has the type

    struct Node
    {
    char * token;
    Node * link;
    };

    The member token should point to a dynamic string on the heap.

    You will write another function, called sort ( ), that creates another linked list that stores the tokens in the first string but in increasing order. Use the function strcmp ( ) to compare the strings. The tokens stored in the second list should be independent of the ones stored in the first list. In other words, the nodes in the second list should use operator new to create a new memory location, and copy the token from a node in the first list to a node in the second list.

    In function main ( ), the program first asks the user to enter the delimiter string, and then enter the string to be tokenized. Use a separate function read_string ( ) to read these strings so that they are stored in dynamic strings on the heap with just enough space. In this read_string ( ) function, you may assume the length of the input strings is no more than 100. Then call function tokenize ( ) and function sort ( ) to build two lists of tokens. After these linked lists are constructed, output the tokens in the order as they are in these lists. In other words, the first output is the tokens in the same order as they are in the input string, and the second output is the tokens in an increasing alphabetical order.

    You should deal with the case that one or both input strings are empty.

    Don't forget to free the memory used by the strings and the nodes of the lists on the heap.
     
  2. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    Try giving better titles
     
  3. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
    Yes there is: strtok
    http://www.cplusplus.com/reference/clibrary/cstring/strtok.html

    It's probably as well to create a different thread per question so that comments about one don't get confused with the other. Or do you have to choose only one of these to do? (If so, I'd probably pick 1. because it's more interesting.)

    How far have you got with the project(s) and where are you stuck? Does the code you have written so far do something unexpected and you can't figure out why? What, in short, do you want us to help you with (other than the obvious implication of writing the whole program for you, which is dishonest and could get you a fail on the course and/or expulsion from the college - academia takes plagiarism very seriously and where not labelled "research" is often the ultimate sin)?
     
  4. e4321

    e4321 New Member

    Joined:
    Jan 13, 2009
    Messages:
    4
    Likes Received:
    0
    Trophy Points:
    0
    In the first part the procedure that I followed is as follows. Is it in accordance with the requirements.

    Code:
    class Main
    {
    public:
    Main(void);
    ~Main(void);
    void main(){
    double a[100][100], b[100][100], d[100][100], c[100], e[100], maxele, temp;
    cout<<" Please enter the number of unknowns: ";
    for(int i=0; i<n; i++){
    for(int j=0; j<n; j++)
    cin>>a[i][j];
    }
    for(int i=0; i<n; i++){
    cin>>c[i];
    }
    for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
    if(a[i][j]<0){
    b[i][j]=-1*a[i][j];
    }
    else{
    b[i][j]=a[i][j];
    }
    } 
    }
    int k=0;
    for(int i=0; i<n; i++){
    k<--i;
    while(j<n){
    if(a[i][j]>a[i][k]){
    temp<--a[i][k];
    a[i][k]<--a[i][j];
    a[i][j]<--temp;
    maxele<--a[i][k];
    j++;
    k++;
    }
    } 
    } 
    
    for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
    d[i][j]<--a[i][j]/a[i][1];
    }
    }
    for(int i=0; i<n; i++){
    if(a[i][1]<a[++i][1]){
    for(int j=0; j<n; j++){
    a[i][j]<--a[++i][j];
    }
    }
    }
    for(int i=0; i<n; i++){
    if(a[i][i]<1 && a[i][i]>1E-9){
    cout<<"the system does not have a unique solution";
    break;
    }
    else{
    for(int j=0; j<n; j++){
    a[i][j]<--a[i][j]-d[i][j];
    } 
    }
    }
    break;
    }
    static const int i=50;
    static const int j=50;
    while(i>0) do{
    while(j>0) do{
    if(a[i][j]<1 && a[i][j]>1E-9){
    break;
    }
    else{
    e[i]=(b[i]-a[i][--j])/a[i][j]; 
    }
    }
    }
    /*for(int i=sizeof a; i>0; i--){
    for(int j=sizeof a; j>0; j--){
    if(a[i][j]<1 && a[i][j]>1E-9){
    break;
    }
    else{
    e[i]=(b[i]-a[i][--j])/a[i][j]; 
    }
    }
    }*/
    }
    private:
    };
     
    Last edited by a moderator: Jan 16, 2009
  5. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
    It's not in accordance with the forum requirement to use code blocks.
    Also please use indenting; you may not see the point of it yet but it makes code a lot easier to read.

    As for whether it is in accordance with the project requirements, well, you tell us. Does it work?
    If not what does it do wrong? Give input and output, stating what the output should be.
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice