3
$\begingroup$

I have this linear algebra question concerning the jacobi method and the frobenius norm that I am having a lot of trouble on, I have an exam soon and I would appreciate any help. NOTE: I have read the entire article of wikipedia on jacobi method and frobnenius norm but I have just started the linear algebra topic and there's only so much I can make out of it.

Consider the following system of equations... $$ \left\{ \begin{array}{c} 2x + y =5\\ x - 3y =6 \end{array} \right. $$ 1. Compute the Frobenius norm for the Matrix C under the Jacobi iterative method(would you expect this problem to converge)?

2.Starting at (x, y) = (0, 0) perform 2 iterations of Jacobi Iterative method for this problem.

I dont understand what the Frobenius norm is exactly, so I started at question 2...

First I converted the system of equations to the respective augmented matrix... $$ \begin{bmatrix} 2 & 1 & 5 \\ 1 & -3 & 6 \\ \end{bmatrix} $$

From here I can see that... $$ \left\{ \begin{array}{c} x^{new} = (-y^{old} + 5)/2\\ y^{new} = (6 - x^{old})/-3 \end{array} \right. $$

So I set up the array...

$$ \begin{array}{c|lcr} Iteration & \text{x^{old}} & \text{y^{old}} & \text{x^{new}} & \text{y^{new}}\\ \hline 1 & 0 & 0 & 2.5 & -2 \\ 2 & 2.5 & -2 & 3.5 & -7/6 \\ \end{array} $$

And that is my answer to number 2, any help with how to do number 1 would be greatly appreciated, thank you for your time.

$\endgroup$

2 Answers 2

4
$\begingroup$

Hint: The Frobenius norm of an $m \times n$ matrix $A$ is defined as the square root of the sum of the absolute squares of its elements.

Example: Consider matrix

$$A = \left( \begin{array}{ccc} ~~~~1 & -2 & ~~~~~~3 \\ -4 & ~~5 & ~-6 \\ ~~~7 & -8 & ~~~~~~9 \\ \end{array} \right)$$

$\lVert A \rVert _{F} = \sqrt (|1|^2+|-2|^2+|3|^2+|-4|^2+|5|^2+|-6|^2+|7|^2+|-9|^2 + |-8|^2) = \sqrt(285) = 16.8819$

For convergence of Jacobi iteration method you need to find iteration matrix $P = -D^{-1}(L+U)$. Note that the Jacobi iterative scheme will converge if $\lVert P\rVert_{F} $ is strictly less than $1$, where $F$ stands for the Frobenius norm. There may be some other matrix norm (such as the $1$-norm ) that is strictly less than $1$, in which case convergence is still guaranteed. In any case, however, the condition $\lVert P\rVert <1 $ is only a sufficient condition for convergence, not a necessary one.

For the given example

$D = \left( \begin{array}{ccc} ~~1 & ~0 & ~0 \\ ~~0 & ~5 & ~0 \\ ~~0 & ~0 & ~9 \\ \end{array} \right)$ $L = \left( \begin{array}{ccc} ~~~0 & ~~0 & ~0 \\ -4 & ~~0 & ~0 \\ ~~~~7 & -8 & ~0 \\ \end{array} \right)$ $U = \left( \begin{array}{ccc} ~~0 & -2 &~~3 \\ ~~0 & ~~~0 & -6 \\ ~~0 & ~~~0 & ~~~0 \\ \end{array} \right)$

Added: Consider to solve $3\times 3$ size system of linear equation $Ax = b$, where coefficient matrix $A = \left( \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21}& a_{22} & a_{23} \\ a_{31}& a_{32} & a_{32} \\ \end{array} \right)$

Assume coefficient matrix $A$ has no zeros on its main diagonal i.e. $a_{11}$, $a_{22}$, $a_{23}$ are non zeros, then $D = \left( \begin{array}{ccc} ~~\frac{1}{a_{11}} & 0 & 0 \\ 0 & \frac{1}{a_{22}} & ~0 \\ ~~0 & 0 & \frac{1}{a_{33}}\\ \end{array} \right)$

$L = \left( \begin{array}{ccc} 0 & 0 & 0 \\ a_{21} & 0 & ~0 \\ a_{31}& a_{32} & 0\\ \end{array} \right)$ $U = \left( \begin{array}{ccc} 0 & a_{12} & a_{13} \\ 0 & 0 & a_{23} \\ 0 & 0 & 0\\ \end{array} \right)$

$\endgroup$
6
  • $\begingroup$ does that mean my Matrix C will be...$$ \begin{bmatrix} 0 & -1/2 \\ 1/3 & 0 \\ \end{bmatrix} $$ So my frobenius norm is Square root of (1/3 squared + 1/2 squared) = 0.601(to 3dp)? $\endgroup$
    – Ogen
    Jun 14, 2013 at 4:37
  • $\begingroup$ In your case matrix $C$ is the same as the matrix $P$. $\endgroup$
    – Srijan
    Jun 14, 2013 at 4:43
  • $\begingroup$ That is going to take a loooong time to calculate even though the question is only worth 2 marks... $\endgroup$
    – Ogen
    Jun 14, 2013 at 4:45
  • 1
    $\begingroup$ @Clay You did correct. There are other ways also to check the convergence of the jacobi method. I don't think it will take much time to find the $2\times 2$ matrix $C$. $\endgroup$
    – Srijan
    Jun 14, 2013 at 4:50
  • $\begingroup$ Ok, I understand it now, thanks for the help $\endgroup$
    – Ogen
    Jun 14, 2013 at 4:55
3
$\begingroup$

To solve $Ax=b$, you can split $A=D+R$, where $D$ is the diagonal, and $R=A-D$. If $D$ is sufficiently 'dominant', the Jacobi method rewrites the equation as a fixed point computation as in $(D+R)x = b$, $D x = (b-Rx)$, and then $x= D^{-1}(b-Rx)$. I am guessing that by $C$ you mean $C=D^{-1} R$, so the equation becomes $x = D^{-1} b -Cx$.

If we write $f(x) = D^{-1} b -Cx$, then a sufficient condition for the fixed point iteration to converge is that $f$ is Lipschitz with rank less than one. We have $\|f(x)-f(y) \| = \|C (x-y) \|$ for any norm, if we choose a norm that satisfies $\|Ax\|\le \|A\| \|x\|$ (a 'compatible' norm), then we have $\|f(x)-f(y) \| \le \|C\| \|x-y\|$, and if that norm satisfies $\|C\| < 1$, then we see that $f$ is a contraction map and the fixed point iteration will converge to the unique fixed point (which is a solution of $Ax=b$).

The Frobenius norm is compatible with the Euclidean norm, and is easy to compute. That is, we have $\|A x \|_2 \le \|A \|_F \|x\|_2$, and $\|A\|_F = \sqrt{\sum_i \sum_j [A]_{ij}^2}$.

In your case, $C = \begin{bmatrix} 2&0\\0&-3\end{bmatrix}^{-1} \begin{bmatrix} 0&1\\1&0\end{bmatrix} = \begin{bmatrix} 0& \frac{1}{2}\\ -\frac{1}{3} &0\end{bmatrix}$, and $\|C\|_F = \sqrt{\frac{1}{9}+\frac{1}{4}} < 1$. Hence the scheme will converge.

$\endgroup$
0

You must log in to answer this question.

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