3
$\begingroup$

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 https://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$?

$\endgroup$

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
0
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .