# Tridiagonal Matrix Algorithm

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 11-02-2009
eholbro1
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!!!!
• 11-02-2009
eholbro1
• 11-02-2009
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).
• 11-02-2009
eholbro1
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.
• 11-02-2009
Quote:

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.
• 11-02-2009
Heres a "short" (i.e. extremely detailed and useful) list: List of numerical analysis software - Wikipedia, the free encyclopedia
• 11-03-2009
YuJunheng
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]; } }```
• 11-03-2009
eholbro1
Thanks for the help but this code wouldn't compile in Dev-C++
• 11-03-2009
m37h0d
matlab is a much better choice for this.
• 11-03-2009
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-03-2009
eholbro1
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
• 11-03-2009
tabstop
Quote:

Originally Posted by eholbro1
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.
• 11-03-2009
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").

Quote:

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

Quote:

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.
• 11-03-2009
eholbro1
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
• 11-03-2009