Looking for an example of a Successive over-relaxation

[hahaha158]

Hi

I am working on a programming assignment that requires me to implement the successive over-relaxation algorithm. We are given the wikipedia page for this: http://en.wikipedia.org/wiki/Successive_over-relaxation.

I have read through the wikipedia page for this numerous times but am still quite unsure of the process.

If given a 3x3 matrix for A, let's say [[1,2,3][5,1,-3][3,1,2]] and a vector for B = [1,-1,2], how can I use this method to solve for x? Sorry if the A and B I gave are not even solvable.

I think that we need to find a w between 1 and 2, so I just arbitrarily chose 1.5, then we need to choose an initial value of x? Can anyone either please give a simple example demonstrating this method, or help explain the wikipedia write up in simpler terms?

Thanks

 

[phyzguy]

The Wikipedia page is quite clear. What part didn't you understand? Can you write down the matrices D, L, and U?

 

[hahaha158]

I have D = [[1,0,0][0,1,0][0,0,2]], L = [[0,0,0],[5,0,0][3,1,0]] U = [[0,2,3][0,0,-3][0,0,0]]. From here do I plug into the x^(k+1) equation? How do I find x^(k). What is the xi^(k+1) equation?

 

[phyzguy]

You're iterating. You start with a guess for x. Say your guess is (1,2,3). k is the index of the iterations. So your guess is x⁽⁰⁾. So x₀⁽⁰⁾ = 1, x₁⁽⁰⁾ = 2, x₂⁽⁰⁾ = 3. So given x⁽⁰⁾, you use the equation to calculate x⁽¹⁾, which is a better approximation to the answer. You keep iterating until the answer stops changing to some degree of accuracy. Do you see?

 

[hahaha158]

Under the algorithm section, i guess they use

for the x and σ for the change from x^k to x^(k+1)? Are these assumptions correct? If so, is finding σ just x^(k+1) - x^k, and I want to keep iterating until σ < (arbitrary minimum i choose?)

 

[phyzguy]

Yes. In the algorithm section φ is the same as x up above, and σ is just a shorthand for the product Ax (or Aφ).

 

[hahaha158]

ok, so since σ is not used for testing convergence like I assumed, can I choose an arbitrary value of let's say 0.001, and then in the section under algorithm that says test for convergence, can I just check to see whether φ^k+1 - φ^k < 0.001, and exit the loop if so?

 

[phyzguy]

I'm still not sure you've got it. Yes, you can just check to see whether φ^k+1 - φ^k < 0.001, and exit the loop if so. But you can't assume value for σ. You have to calculate σ, it is the product of A and φ.

 

[hahaha158]

Sorry, my last reply was worded poorly. I meant to choose an arbitrary value for φ^k+1 - φ^k, i didn't mean to imply that the value is equal to σ. In any case, it doesn't seem like you actually need to calculate σ, since in the algorithm it is initialized as 0, and they have a line that computes it inside the j loop, correct?

 

[phyzguy]

Yes, correct. They are just showing you how to calculate it.

 

[hahaha158]

thank you!

your explanations helped a lot