Gauss-Seidl, Gauss-Southwell, Jacobi

  • Thread starter onako
  • Start date
  • Tags
    Jacobi
In summary: This would give you the vector y such that y=A*x-b*(1-x)In summary, the couple of days ago, I downloaded a book on numerical optimization, hoping to get a better understanding of some techniques. However, I found that some concepts were not clearly separated from one another, and that there are multiple names for one technique. For example, Gauss-Southwell is referred to as "cyclic descent method," while the Jacobi method is a "hold on" version of Gauss-Seidl. Another question is regarding the eigenvalues of a matrix, and how to proceed with the proof of a claim if it is not clear which eigenvalues correspond to
  • #1
onako
86
0
Couple of days ago I downloaded a book on numerical optimization, hoping to get clearer picture on some techniques.
But, I'm surprised that some of the concepts were not precisely separated from one another.

Namely, in the part of "coordinate descent methods" (cdm), I found that, in the case the contribution of each point
to the function in question is known, one applied the Gauss-Southwell approach to select the point to be updated.
In case the update is done is a sequence from 1 to n, the the approach is referred to as the "cyclic descent method" (cydm).
However, on some other places I've found that Gauss-Seidl method's principle is close to cydm's.
Is Gauss-Seidl actually another name for cydm? I hope someone will clarify this for me.

Another question is regarding the Jacobi method, which is a "hold on" version of Gauss-Seidl, in my understanding
(regarding the point update at the end of iteration). Given certain function f(x) which is quadratic in x,
in order to obtain its minimal, I set the derivative to 0, and obtain the following linear system

Ax=b

which I decide to solve by Jacobi iteration. Given that A is strictly diagonally dominant, is it true that the value of
f(x1), where x1 is obtained by a single Jacobi iteration on some arbitrary x0 (but not the stationary point) satisfies
f(x1)<f(x0)?
 
Physics news on Phys.org
  • #2
Let me clarify what I'm looking for : given a function
[tex]
f(x)=\frac{1}{2}x^TAx - b^Tx,
[/tex]
and the update
[tex]
x_1=D^{-1}(b-Rx_0)
[/tex]
where A=D+R, with the being the diagonal matrix with diagonal entries of A (and R containing the off-diagonal entries of A), how could I show
[tex]
f(x_0)>f(x_1)
[/tex]
 
  • #3
What you want to show is false, in general. For example take
##A = \begin{bmatrix}1 & 2 \\ 2 & 1 \end{bmatrix}, \quad
b = \begin{bmatrix} 0 \\ 0 \end{bmatrix}, \quad
x_0 = \begin{bmatrix} 1 \\ 1 \end{bmatrix}##
 
  • #4
Your A is not strictly diagonally dominant (which is necessary for convergence of Jacobi method).
 
  • #6
Many thanks for the suggestion. Note that following:
[tex]
D^{-1}R=D^{-1}(V-D)=D^{-1}V-I
[/tex]
In my choice of V, the matrix [tex]D^{-1}V[/tex]
reduces to a symmetric matrix with the only non-negative elements on the diagonal begin equal to 1:
[tex]
D^{-1}V=\left(\begin{array}{ccccc}
1 & & & & \\
& \ddots & & -c_{ij} \\
& & \ddots & & \\
& -c_{ij} & & \ddots & \\
& & & & 1
\end{array}\right) \in\mathbb{R}^{n\times n}
[/tex]
such that the sum of the absolute values of all the off-diagonal elements in each row and column sum to 1, which is
the corresponding diagonal element. By matrix difference $D^{-1}V-I$, this implies that the diagonal elements of the matrix $D^{-1}R$ are zero, and in terms of the proposed Gershgorin circle theorem, this would correspond to
n disks D(0, 1), meaning that eigenvalues of [tex]eigs(D^{-1}R)\leq 1[/tex] (correct me if I'm wrong).
How to proceed with the proof further?
 
  • #7
You can get rid of the vector b by shifting the origin so the solution vector is zero, i.e ##y = x - \bar x## where ##A \bar x - b = 0##.

Then use the fact that any vector y is a linear combination of the eigenvectors of ##D^{-1}R##.
 

1. What is the difference between Gauss-Seidl and Gauss-Southwell?

Gauss-Seidl and Gauss-Southwell are both iterative methods used to solve systems of linear equations. The main difference between the two is the way they update the solution at each iteration. Gauss-Seidl updates the solution using the most recently calculated values, while Gauss-Southwell uses a weighted average of the previous and current values. This results in Gauss-Seidl typically converging faster than Gauss-Southwell.

2. How does the Jacobi method compare to Gauss-Seidl and Gauss-Southwell?

The Jacobi method is another iterative method for solving linear systems, but it differs from Gauss-Seidl and Gauss-Southwell in the way it updates the solution. Jacobi updates all of the solution values simultaneously, rather than one at a time like Gauss-Seidl and Gauss-Southwell. This makes Jacobi less efficient, but it can be useful for certain types of systems.

3. What are the advantages of using Gauss-Seidl over other iterative methods?

Gauss-Seidl is known for its fast convergence rate, making it a popular choice for solving linear systems. It also typically requires fewer iterations than other methods, which can save time and computational resources. Additionally, Gauss-Seidl is relatively easy to implement and can handle a wide range of systems.

4. Are there any limitations to using the Jacobi method?

While the Jacobi method can be an effective way to solve linear systems, it does have some limitations. One major limitation is that it may not converge for all types of systems, particularly those with large differences in the magnitudes of the solution values. Additionally, Jacobi can be slower and less accurate than other methods, so it may not be the best choice for certain applications.

5. How do these iterative methods compare to direct methods for solving linear systems?

Direct methods, such as Gaussian elimination, are typically faster and more accurate than iterative methods for solving linear systems. However, direct methods can be computationally expensive and may not be feasible for large systems. Iterative methods, on the other hand, can handle larger systems and are more versatile, but they may require more iterations to reach a solution. The choice between these methods depends on the specific needs of the problem at hand.

Similar threads

  • Linear and Abstract Algebra
Replies
5
Views
2K
  • Linear and Abstract Algebra
Replies
1
Views
1K
  • General Math
Replies
5
Views
766
  • Programming and Computer Science
Replies
1
Views
2K
  • General Math
Replies
12
Views
1K
  • Precalculus Mathematics Homework Help
Replies
3
Views
3K
  • Linear and Abstract Algebra
Replies
6
Views
2K
  • Advanced Physics Homework Help
Replies
1
Views
2K
Replies
5
Views
6K
  • Electrical Engineering
Replies
3
Views
2K
Back
Top