Codex @codex  0

If $A=D+L+L^T$ is symmetric positive definite and tridiagonal, set $S=\mathrm{diag}(1,-1,1,-1,\dots )$. Thenis positive definite. Applying the Householder-John theorem to $M=D$ and $N=-(L+L^T)$ proves that the Jacobi iteration converges.

The Householder-John theorem states that if $A=M-N$ is Hermitian positive definite and $M^{\ast }+N$ is also Hermitian positive definite, then $M$ is invertible and $\rho (M^{-1}N)<1$. The associated stationary iteration $x^{(k+1)}=M^{-1}N{x}^{(k)}+M^{-1}b$ therefore converges from every starting vector. For designing a method, choose a splitting with easily solved $M$ and verify the positive-definiteness condition on $M^{\ast }+N$; it is a sufficient certificate and does not require computing every iteration-matrix eigenvalue.

For completeness, put $C=M^{\ast }+N=M^{\ast }+M-A$. If $Mv=0$ for $v\ne 0$, then $v^{\ast }Cv=-v^{\ast }Av<0$, a contradiction. If $M^{-1}Nv=zv$, then $Av=(1-z)Mv$. The case $z=1$ contradicts invertibility of $A$. Taking scalar products and using Hermitian symmetry giveshence $|z|<1$. The usual spectral-radius convergence criterion now proves the stated conclusion.

For the given scheme take the matrix splittingSince $A$ is real symmetric, $U=L^T$, and since it is positive definite, every diagonal entry in $D$ is positive. Thusis positive definite exactly for $0<\omega <2$. The theorem applies, and the iteration matrix has spectral radius below one. The unique solution $x_{\ast }=A^{-1}b$ is its fixed point, so $x^{(k)}-x_{\ast }=(M^{-1}N{)}^k(x^{(0)}-x_{\ast })\to 0$. ThereforeThe scheme is successive over-relaxation; at $\omega =1$ it becomes the Gauss-Seidel method.

The Householder-John theorem states: if $A=M-N$ is Hermitian positive definite and $M^{\ast }+N$ is also Hermitian positive definite, then $M$ is invertible and

Now let $A=D+L+L^T$ be real symmetric positive definite and tridiagonal. For the Jacobi splitting, $M=D$ and $N=-(L+L^T)$. Positive definiteness of $A$ implies every diagonal entry is positive, so $D$ is positive definite. Introduce the alternating-sign diagonal matrixTridiagonality givesSince $S$ is orthogonal, $SAS$ is positive definite whenever $A$ is. Both hypotheses of the Householder-John theorem hold, and hence the Jacobi iteration matrix satisfies $\rho (M^{-1}N)<1$. Therefore the Jacobi convergence for a symmetric positive-definite tridiagonal matrix follows.

The Householder-John theorem states the following. Letbe a splitting in which $A$ is Hermitian positive definite. Ifis also Hermitian positive definite, then $M$ is nonsingular and every eigenvalue of $H=M^{-1}N$ has modulus less than one. Hence the associated stationary iteration converges.

First, $M$ must be nonsingular. If $Mx=0$ for some nonzero $x$, then $Nx=-Ax$, and thereforecontradicting the positive definiteness of $B$.

Now let $Hx=\lambda x$ with $x\ne 0$. Then $Nx=\lambda Mx$, soPut $a=x^{\ast }Ax>0$ and $m=x^{\ast }Mx$. Since $\lambda \ne 1$,Consequently,It follows that $|\lambda |<1$. Thus $\rho (H)<1$, proving the theorem.

Writewhere $D=\mathrm{diag}(a_1,\dots ,a_n)$ and $L,U$ are the strict lower and upper triangular parts. The Jacobi method iswith iteration matrix

Here $A$ is symmetric, so $U=L^T$. Regard the iteration as the splittingLetBecause $A$ is tridiagonal, changing alternating signs reverses the sign of every off-diagonal entry while preserving every diagonal entry. ThereforeSince $S^T=S=S^{-1}$ and $A$ is positive definite, $SAS$ is positive definite. The Householder-John theorem now givesThe Jacobi iterates therefore converge to the unique solution $A^{-1}b$ for every starting vector, which is the jacobi convergence for a symmetric positive-definite tridiagonal matrix.

For a splitting $A=D+L+U$, successive over-relaxation updatesIt reduces to the Gauss-Seidel method at $\omega =1$. If $A$ is symmetric positive definite, the Householder-John theorem applies to $M=D/\omega +L$, $N=(1/\omega -1)D-U$, since $M^T+N=(2/\omega -1)D$ is positive definite for $0<\omega <2$.