Tridiagonal Matrix Algorithm

This is a discussion on Tridiagonal Matrix Algorithm within the C++ Programming forums, part of the General Programming Boards category; I'm taking a Linear Algebra and Matrices class and we have a big programming assignment.... Problem is that I've never ...

  1. #1
    Registered User
    Join Date
    Nov 2009
    Posts
    8

    Tridiagonal Matrix Algorithm

    I'm taking a Linear Algebra and Matrices class and we have a big programming assignment.... Problem is that I've never taking a programming class....

    Here is the Question

    Solve using a computer the tridiagonal system of 100 equations in 100
    unknowns given by
    2x1 − x2 = 101
    −xi−1 + 2xi − xi+1 = 0 for 2<=  i <= 99
    −x99 + 2x100 = 0
    Solve this system by first computing a LU decomposition and then performing
    forward and backward substitution to obtain the solution.

    I would greatly appreciate any and all help!!!!

  2. #2
    Registered User
    Join Date
    Nov 2009
    Posts
    8
    Help please!!!!!!!!!!!!!

  3. #3
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    Well, as the question even states, first you need the LU decomposition. You will be able to find examples of this, not necessarily in C++ (though Im sure youll find those too), but mainly in "math" languages, i.e. Matlab, Maple, etc. These should be straightforward enough to convert to C++, or just find a C++ example. If all else fails, program one yourself. Im guessing your a math major? Use your knowledge of what an algorithm is to write the C++ code for it (or at least an English description of it)--after all, algorithm is a mathematical concept. For your C++ (or even plain-English description/algorithm/pseudocode), if you run into problems post your attempt and we'll help. Im sure whatever book your using actually has this English/mathematical algorithm, you just have to convert it to C++.

    That would be the trickier part (probably). After you have that, then work on the forward and backward substitution...one step at a time.

    EDIT: Afte re-reading the question, do you even have to use C++ to program this? Can you just use one of the linear algebra programs? They usually have this stuff built in. I doubt this would be the first programming assignment, and since no where does it mention programming, I take it that you dont have to write a program (unless you left those details out).
    Last edited by nadroj; 11-02-2009 at 08:19 PM.

  4. #4
    Registered User
    Join Date
    Nov 2009
    Posts
    8
    Thanks for your response.... It doesn't have to be in c++ but that's the language that I heard people were using to try to complete the problem. I figured he wanted a program because he wanted us to submit the source code. I found a few examples but nothing seems to compile right.

  5. #5
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    I figured he wanted a program because he wanted us to submit the source code
    This does not mean "Write a C++ program to [...]". The source code could be any language, including math/algebra-oriented languages such as Matlab. Of course this isnt true if the course (or what/who-ever) says "use [programming language here] to do this". If, based on what the requirements are and your intuition, you think it would be acceptable to use something besides C++, I would recommend to use an existing program for some algebra software system to do it, and just provide that source (as well as a stating the reference). Also, obviously, if it is to be written yourself then what I said doesnt help.

    Basically, if you have to write it yourself, theres no way around that and you cant copy an existing program (though you can use it for reference to understand the concept in parts--not taking the entire thing). The other thing is, if your told what language to use, you cant get around that either of course. If this is the case, do as I suggested above and look through your notes/book/internet for the algorithm for LU decomposition, attempt either pseudocode or C++ code, post what you end up with and whats wrong with it/what you dont understand/error messages, etc.

  6. #6
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    Heres a "short" (i.e. extremely detailed and useful) list: List of numerical analysis software - Wikipedia, the free encyclopedia

  7. #7
    Registered User
    Join Date
    Nov 2009
    Posts
    2

    The Solution For You!

    Code:
    struct coefficient
    {
    int k;
    int b;
     
    coefficient( int i, int ii ): k( i ), b( ii ) {}
    coefficient(): k( 0 ), b( 0 ) {}
    };
     
    coefficient operator*( int a, const coefficient& coef )
    {
    coefficient temp = coef;
    temp.k *= a;
    temp.b *= a;
    return temp;
    }
     
    coefficient operator*( const coefficient& coef, int a )
    {
    coefficient temp = coef;
    temp.k *= a;
    temp.b *= a;
    return temp;
    }
     
    coefficient operator-( const coefficient& lhs, const coefficient& rhs )
    {
    coefficient temp = lhs;
    temp.k -= rhs.k;
    temp.b -= rhs.b;
    return temp;
    }
     
    coefficient operator+( const coefficient& lhs, const coefficient& rhs )
    {
    coefficient temp = lhs;
    temp.k += rhs.k;
    temp.b += rhs.b;
    return temp;
    }
     
    void run( std::vector<int>& result )
    {
    // X[0] = 1X[0]+0
    coefficient last_coef( 1, 0 );
     
    // X[1] = 2X[0]-101
    coefficient current_coef( 2, -101 );
     
    // X[i+1] = 2X[i] - X[i-1]
    for ( int i = 2; i < 100; i++ )
    {
    coefficient temp_coef = current_coef * 2 - last_coef;
    last_coef = current_coef;
    current_coef = temp_coef;
    }
     
    // X[99] = current_coef.k*X[0] + current_coef.b;
    // X[98] = last_coef.k*X[0] + last_coef.b;
    // X[98] = 2X[99];
     
    // 2current_coef-last_coef = 0;
    // X[0] = ??
     
    coefficient result_coef = current_coef * 2 - last_coef;
    int X0 = -result_coef.b / result_coef.k;
    int X1 = 2 * X0 - 101;
     
    result.clear();
    result.resize( 100 );
     
    result[0] = X0;
    result[1] = X1;
     
    for ( i = 2; i < 100; i++ )
    {
    result[i] = 2 * result[i-1] - result[i-2];
    }
    }

  8. #8
    Registered User
    Join Date
    Nov 2009
    Posts
    8
    Thanks for the help but this code wouldn't compile in Dev-C++

  9. #9
    3735928559
    Join Date
    Mar 2008
    Location
    RTP
    Posts
    839
    matlab is a much better choice for this.

  10. #10
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    Not only does the code not compile (apparently), but you dont know what the hell it does, and you havent learned anything. If you just want an answer/solution given to you, then:
    1) Cheat
    2) Steal (someones solution--many, many online, its not that hard to find)
    3) Pay someone (there are sites dedicated to this, and a much smarter choice than coming here and asking for complete answers).

    Doing it this way you may succeed. By succeed I mean you may get 100% of that total 1%-5% that its worth that the small assignment is for. However, come a real evaluation (25%-60% of your total mark) such as tests or exams, you will get 0% if you didnt learn anything from assignments. So you end up with a solid F- (or just F, if your school doesnt want to hurt your feelings enough by giving you an F-).

    Nothing has higher priority than learning.

  11. #11
    Registered User
    Join Date
    Nov 2009
    Posts
    8
    not one time did you see me ask for a solution... I asked for help...I've seen the one's online but there too complicated. The professor says it should be able to be done in 10 lines of code. If your gonna offer me help then do so, if not then there's no need to comment..... moving right along

  12. #12
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by eholbro1 View Post
    not one time did you see me ask for a solution... I asked for help...I've seen the one's online but there too complicated. The professor says it should be able to be done in 10 lines of code.
    Not in C++, it can't. I mean maybe the LU decomposition in ten lines of code, given the matrix operators, which would have to be written. In MATLAB, ten lines seems pretty reasonable.

  13. #13
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    As I mentioned above, and others have mentioned, using an algebra system is the obvious smart choice--especially if, as I described above, you arent limited to what language/tool you use (as long as you provide its "source code").

    not one time did you see me ask for a solution
    Not once did you see me say you asked for the solution.

    Thanks for the help but this code wouldn't compile in Dev-C++
    If he has given the "solution", and if it doesnt compile, the best place to start is to...fix it. Fixing an existing "solution" is probably easier than re-writing your own from scratch. So you could try and fix that one, or at least give us the errors you see when you try to compile it (and of course post the code your compiling, as, of course, the code that was given to you wont compile, it doesnt even have any includes, main(), etc).

    We are here to help, and we are helping. We have suggested that, given the unrestricted choice of language to implement the task in, we suggest a tool built for that task, i.e. MATLAB. If you still insist on making a C++ algorithm, which is likely much more complicated, especially if you "have never programmed", then we'll help still. Just, as I also mentioned earlier, post whatever code you start with for an attempt at the solution, and describe the problem you run into.

  14. #14
    Registered User
    Join Date
    Nov 2009
    Posts
    8
    thanks for your replies. I'm no longer using c++. I'm using Maple(never used this before) since I don't have a copy of Matlab

  15. #15
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    For previous work I had to do, we were required to use Matlab. However, I, like you, dont have a copy of Matlab (its also extremely expensive). So I searched around and found a free alternative, that is compatible with MATLAB syntax (meaning if you learn/find Matlab examples, it should work directly in the alternative also). its called GNU Octave - Wikipedia, the free encyclopedia, and it works on a number of different platforms. You can download it from here Downloading Octave.

    EDIT: I have a copy of Maple, but have never used it so I dont know what it can do. However, if that suits your needs then great and good luck. Otherwise, if you need something Matlab-like, I suggest Octave.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C - access violation
    By uber in forum C Programming
    Replies: 2
    Last Post: 07-08-2009, 01:30 PM
  2. Matrix Help
    By HelpmeMark in forum C++ Programming
    Replies: 27
    Last Post: 03-06-2008, 04:57 PM
  3. What is a matrix's purpose in OpenGL
    By jimboob in forum Game Programming
    Replies: 5
    Last Post: 11-13-2004, 11:19 PM
  4. Matrix and vector operations on computers
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 05-11-2004, 06:36 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21