Successive over-relaxation method - SOR - Revision history

Jasond at 02:08, 19 December 2005

2005-12-19T02:08:09Z

← Older revision		Revision as of 02:08, 19 December 2005
Line 1:		Line 1:
-	~~We seek the solution to set of linear equations: <br>~~	+	== Introduction ==

-	~~:<math> A \cdot \Phi = B </math>~~ <br>	+	We seek the solution to set of linear equations <br>

-	~~In matrix terms, the definition of the SOR method can be expressed as~~ : ~~<br>~~	+	:<math> A \phi = b. </math> <br>
-	<math>	+
-	\phi~~^{(k)}~~ = ~~\left( {D - \omega L} \right)^{ - 1} \left( {\omega U + \left( {1 - \omega } \right)D} \right)\phi^{(k - 1)} + \omega \left( {D - \omega L} \right)^{ - 1} B~~	+
-	~~</math><br>~~	+
-	~~Where '''D''','''L''' and '''U''' represent the diagonal, lower triangular and upper triangular matrices of coefficient matrix '''A''' and k is iteration counter~~.~~<br>~~	+
-	~~<math> \omega~~ </math> ~~is a relaxation factor.~~ <br>	+

-	~~The pseudocode for~~ the SOR ~~algorithm: <br>~~	+	In matrix terms, the successive over-relaxation (SOR) iteration can be expressed as

-	=== ~~Algorithm ===~~	+	:<math>
-	----	+	\phi^{(k+1)} = \left( {D - \omega L} \right)^{ - 1} \left( {\omega U + \left( {1 - \omega } \right)D} \right)\phi^{(k)} + \omega \left( {D - \omega L} \right)^{ - 1} b
-	: Chose an ~~intital~~ guess <math>\~~Phi~~^{0}</math> to the solution <br>	+	</math>
-	: for k := 1 step 1 ~~untill~~ convergence do <br>	+
		+	where <math>D</math>, <math>L</math>, and <math>U</math> represent the diagonal, lower triangular, and upper triangular parts of the coefficient matrix <math>A</math>, <math>k</math> is the iteration count, and <math> \omega </math> is a relaxation factor. This matrix expression is not usually used to program the method, and an element-based expression is used:
		+
		+	:<math>
		+	\phi^{(k+1)}_i = (1-\omega)\phi^{(k)}_i+\frac{\omega}{a_{ii}} \left(b_i - \sum_{j<i}a_{ij}\phi^{(k+1)}_j-\sum_{j>i}a_{ij}\phi^{(k)}_j\right),\, i=1,2,\ldots,n.
		+	</math>
		+
		+	Note that for <math>\omega = 1</math> that the iteration reduces to the [[Gauss-Seidel method\| Gauss-Seidel]] iteration. As with the [[Gauss-Seidel method]], the computation may be done in place, and the iteration is continued until the changes made by an iteration are below some tolerance.
		+
		+	The choice of relaxation factor is not necessarily easy, and depends upon the properties of the coefficient matrix. For symmetric, positive definite matrices it can be proven that <math>0<\omega<2</math> will lead to convergence, but we are generally interested in faster convergence rather than just convergence.
		+
		+	== Algorithm ==
		+	Chose an initial guess <math>\phi^{0}</math> to the solution <br>
		+	: for k := 1 step 1 until convergence do <br>
	:: for i := 1 step until n do <br>		:: for i := 1 step until n do <br>
	::: <math> \sigma = 0 </math> <br>		::: <math> \sigma = 0 </math> <br>
Line 29:		Line 37:
	:: check if convergence is reached		:: check if convergence is reached
	: end (k-loop)		: end (k-loop)
-	~~----~~
-

-	-~~---~~	+	''TODO - add references, more about relaxation factor''
-	~~<i> Return to [[Numerical methods \| Numerical Methods]] </i>~~	+

Tsaad: towards a uniform notation for linear systems : A*Phi = B

2005-12-15T20:49:52Z

towards a uniform notation for linear systems : A*Phi = B

← Older revision		Revision as of 20:49, 15 December 2005
Line 1:		Line 1:
	We seek the solution to set of linear equations: <br>		We seek the solution to set of linear equations: <br>

-	:<math> A \cdot X = Q </math> <br>	+	:<math> A \cdot \Phi = B </math> <br>

-	~~For the given matrix '''A''' and vectors '''X''' and '''Q'''. <br>~~
	In matrix terms, the definition of the SOR method can be expressed as : <br>		In matrix terms, the definition of the SOR method can be expressed as : <br>
	<math>		<math>
-	x^{(k)} = \left( {D - \omega L} \right)^{ - 1} \left( {\omega U + \left( {1 - \omega } \right)D} \right)x^{(k - 1)} + \omega \left( {D - \omega L} \right)^{ - 1} q	+	\phi^{(k)} = \left( {D - \omega L} \right)^{ - 1} \left( {\omega U + \left( {1 - \omega } \right)D} \right)\phi^{(k - 1)} + \omega \left( {D - \omega L} \right)^{ - 1} B
	</math><br>		</math><br>
	Where '''D''','''L''' and '''U''' represent the diagonal, lower triangular and upper triangular matrices of coefficient matrix '''A''' and k is iteration counter.<br>		Where '''D''','''L''' and '''U''' represent the diagonal, lower triangular and upper triangular matrices of coefficient matrix '''A''' and k is iteration counter.<br>
-	<math> \omega </math> is ~~extrapolation~~ factor. <br>	+	<math> \omega </math> is a relaxation factor. <br>

	The pseudocode for the SOR algorithm: <br>		The pseudocode for the SOR algorithm: <br>
Line 15:		Line 14:
	=== Algorithm ===		=== Algorithm ===
	----		----
-	: Chose an intital guess <math>X^{0}</math> to the solution <br>	+	: Chose an intital guess <math>\Phi^{0}</math> to the solution <br>
	: for k := 1 step 1 untill convergence do <br>		: for k := 1 step 1 untill convergence do <br>
	:: for i := 1 step until n do <br>		:: for i := 1 step until n do <br>
	::: <math> \sigma = 0 </math> <br>		::: <math> \sigma = 0 </math> <br>
	::: for j := 1 step until i-1 do <br>		::: for j := 1 step until i-1 do <br>
-	:::: <math> \sigma = \sigma + a_{ij} ~~x_j~~^{(k)} </math>	+	:::: <math> \sigma = \sigma + a_{ij} \phi_j^{(k)} </math>
	::: end (j-loop) <br>		::: end (j-loop) <br>
	::: for j := i+1 step until n do <br>		::: for j := i+1 step until n do <br>
-	:::: <math> \sigma = \sigma + a_{ij} ~~x_j~~^{(k-1)} </math>	+	:::: <math> \sigma = \sigma + a_{ij} \phi_j^{(k-1)} </math>
	::: end (j-loop) <br>		::: end (j-loop) <br>
-	::: <math> \sigma = {{\left( {~~q_i~~ - \sigma } \right)} \over {a_{ii} }} </math>	+	::: <math> \sigma = {{\left( {b_i - \sigma } \right)} \over {a_{ii} }} </math>
-	::: <math> ~~x_i~~^{(k)} = ~~x_i~~^{(k - 1)} + \omega \left( {\sigma - ~~x_i~~^{k - 1} } \right) </math>	+	::: <math> \phi_i^{(k)} = \phi_i^{(k - 1)} + \omega \left( {\sigma - \phi_i^{k - 1} } \right) </math>
	:: end (i-loop)		:: end (i-loop)
	:: check if convergence is reached		:: check if convergence is reached

Tsaad: fixed dot product notation

2005-12-15T20:33:51Z

fixed dot product notation

← Older revision		Revision as of 20:33, 15 December 2005
Line 1:		Line 1:
	We seek the solution to set of linear equations: <br>		We seek the solution to set of linear equations: <br>

-	:<math> A \~~bullet~~ X = Q </math> <br>	+	:<math> A \cdot X = Q </math> <br>

	For the given matrix '''A''' and vectors '''X''' and '''Q'''. <br>		For the given matrix '''A''' and vectors '''X''' and '''Q'''. <br>

Tsaad: Successive over-relaxation method moved to Successive over-relaxation method - SOR

2005-12-14T20:44:28Z

Successive over-relaxation method moved to Successive over-relaxation method - SOR

← Older revision

Revision as of 20:44, 14 December 2005

Zxaar at 06:24, 3 October 2005

2005-10-03T06:24:34Z

← Older revision		Revision as of 06:24, 3 October 2005
Line 31:		Line 31:
	: end (k-loop)		: end (k-loop)
	----		----
		+
		+
		+	----
		+	<i> Return to [[Numerical methods \| Numerical Methods]] </i>

Zxaar at 05:35, 15 September 2005

2005-09-15T05:35:27Z

New page

We seek the solution to set of linear equations: 

:<math> A \bullet X = Q </math> 

For the given matrix '''A''' and vectors '''X''' and '''Q'''. 
In matrix terms, the definition of the SOR method can be expressed as : 
<math>
x^{(k)} = \left( {D - \omega L} \right)^{ - 1} \left( {\omega U + \left( {1 - \omega } \right)D} \right)x^{(k - 1)} + \omega \left( {D - \omega L} \right)^{ - 1} q
</math> 
Where '''D''','''L''' and '''U''' represent the diagonal, lower triangular and upper triangular matrices of coefficient matrix '''A''' and k is iteration counter. 
<math> \omega </math> is extrapolation factor. 

The pseudocode for the SOR algorithm: 

=== Algorithm ===
----
: Chose an intital guess <math>X^{0}</math> to the solution 
: for k := 1 step 1 untill convergence do 
:: for i := 1 step until n do 
::: <math> \sigma = 0 </math> 
::: for j := 1 step until i-1 do 
:::: <math> \sigma = \sigma + a_{ij} x_j^{(k)} </math>
::: end (j-loop) 
::: for j := i+1 step until n do 
:::: <math> \sigma = \sigma + a_{ij} x_j^{(k-1)} </math>
::: end (j-loop) 
::: <math> \sigma = {{\left( {q_i - \sigma } \right)} \over {a_{ii} }} </math>
::: <math> x_i^{(k)} = x_i^{(k - 1)} + \omega \left( {\sigma - x_i^{k - 1} } \right) </math>
:: end (i-loop)
:: check if convergence is reached
: end (k-loop)
----