Give an example of a matrix $B \in \mathbb{R}^{n\times n}$ such that $\|B\|\geq 1.$

Question

Give an example of a matrix $B \in \mathbb{R}^{n\times n}$ such that $\|B\|\geq 1$ (for any norm) but the iterations $x^{m+1}=Bx^m+b$ converge to a fixed point such that $x=Bx+b$ (Suggestion: look the matrices of the form $\begin{bmatrix}\lambda & \gamma\\0 & \lambda\end{bmatrix}$)

Since $\|B\|\geq1$, $\lambda$ should be greater or equal than one. But I can't find in this case an example that converges. Actually, I find the opposite: diverges every time. Also, I'm thinking of the error, that this should mean that, in the better case, I can keep it constant from the beggining, but for that I should be able to choose $b$ which I can't in this case.

Answer 1

The usual definition of matrix norm is that $\|B\|$ is the greatest value that can be obtained as the usual vector norm of $Bt$ where $t$ ranges over all possible "test vectors" of norm $1$.

So for example, the norm of $\pmatrix{\frac12 & 5 \\ 0 & \frac12}$ is at least -- based on the test vector $\pmatrix{0\\1}$ -- $\sqrt{25 + \frac14} > 1$.

So the question comes down to finding a matrix with norm greater than $1$ and all eigenvalues less than $1$. Because the eigenvalue spectrum is what determines the worst-test-case convergence properties.

Can you find such a matrix?

Answer 2

Hint (assuming you're using the 2-norm):

The iterative method that you're given is called the Picard method. It converges iff $p(B)<1$, where $p(B)$ is the biggest eigenvalue of $B$ in module.

Symmetric matrices have the following property: $||B||_2=p(B)$, so if you're looking for a matrix $B$ such that $p(B)<1$ and $||B||_2 \geq 1$, then $B$ can't be symmetric, i.e. $\gamma \neq0$.

Eigenvalues of tridiagonal matrices are the values in its diagonal, so look for a non-symmetric matrix such that all the elements in its diagonal are less than 1.