Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose a function $$f(x)=\frac{1}{2}x^TAx-b^Tx$$ is given, for some symmetric $A\in\mathbb{R}^{n\times n}$ for which all off-diagonal entries of A are nonpositive, and every diagonal entry of A is positive and is the sum of absolute values of all other entries in the row. Hence, given that $D$ is a diagonal matrix containing the elements of $A$, the Gershgorin theorem states that the spectrum of $D^{-1}A$ is in $[0, 2]$.

Given an initial $x_0$, I'm interested what happens with $f(x_0)$ after $x_0$ has been updated as in Jacobi iteration to the system $Ax=b$. According to http://scicomp.stackexchange.com/questions/1478/jacobi-iteration-to-reduce-the-quadratic-function (the accepted answer) the function values always decrease, but I'm not sure about the spectra bound used.

Can the value of $f(x)$ increase after Jacobi iteration has been applied to any $x_0$?

share|improve this question

2 Answers 2

I have some misgivings about your question setting. You said that in $A$, "the positive diagonal entries are summations of absolute values of non-positive off-diagonal entries". If I take it literally, this means the matrix could have negative diagonal entries or positive off-diagonal entries, but I think that is perhaps not what you really meant.

So, I suppose all off-diagonal entries of $A$ are nonpositive, and every diagonal entry of $A$ is positive and is the sum of absolute values of all other entries in the row. But then $A$ is necessarily singular and hence the Jacobi method may not converge at all. For instance, consider $$ A = \begin{pmatrix}1&-1\\-1&1\end{pmatrix},\ b=\begin{pmatrix}1\\-1\end{pmatrix} $$ If $x_0 = (1,1)^T$, the Jacobi iterates will form a cycle $(1,1)^T\rightarrow(2,0)^T\rightarrow(1,1)^T\rightarrow\ldots$ and never converge (though their function values do remain constant and are nonincreasing). Often, when speak of the Jacobi method, we assume that $A$ is strictly diagonally dominant, so that the method is guaranteed to converge. Your $A$ is an exception, however.

At any rate, we will turn to your question. I am not sure if the calculations in the post you linked to are correct, but in general, if $Ax=b$ has a solution $x=x^\ast$ and you perform an iterative method $x_{k+1} = Gx_k + h$ (in our case, $G=-D^{-1}R$ and $h=D^{-1}b$), then the error term $e_k = x-x^\ast$ will satisfy the equation $e_{k+1}=Ge_k$. Hence \begin{align} f(x_{k+1}) - f(x_k) &= f(x^\ast + e_{k+1}) - f(x^\ast + e_k)\\ &= \frac12 (x^\ast + e_{k+1})^TA(x^\ast + e_{k+1})-b^T(x^\ast + e_{k+1})\\ &\phantom{=}- \frac12 (x^\ast + e_k)^TA(x^\ast + e_k) + b^T(x^\ast + e_k)\\ &= \frac12 \left(e_{k+1}^TA e_{k+1} - \frac12 e_k^TA e_k\right) \quad (\textrm{as } Ax^\ast=b)\\ &= \frac12 e_k^T \left(G^TAG - A\right) e^k. \end{align} Yet \begin{align} G^TAG - A &= RD^{-1}AD^{-1}R - A\\ &= (A-D)D^{-1}AD^{-1}(A-D) - A\\ &= AD^{-1}AD^{-1}A - 2AD^{-1}A\\ &= AD^{-1}(A-2D)D^{-1}A\\ &= AD^{-1}(R-D)D^{-1}A. \end{align} By Gershgorin disc theorem, the spectrum of $R-D$ must be nonpositive (negative if $A$ is strictly diagonally dominant). Therefore $G^TAG-A$ is negative semidefinite and the function values of the Jacobi iterates are always nonincreasing.

share|improve this answer
up vote 0 down vote accepted

The answer considering the cited answer: the misconception is in the step 3. of the cited answer: the bound is [0,2]. Therefore, spectra of matrix from 1. is nonpositive (negative if A is strictly diagonally dominant) and the function values are non-increasing.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.