Jacobi Method

• After reordering;
  $$\begin{array}{l} 6x_1 - 2x_2 + x_3 = 11\\ -2x_1 + 7x_2 + 2x_3 = 5\\ x_1 + 2x_2 - 5x_3 = -1\\ \end{array}$$
  Is the solution same? Check it out as an exercise.
• The iterative methods depend on the rearrangement of the equations in this manner:
  $$x_i=\frac{b_i}{a_{ii}}- \sum_{j=1,j\neq i}^n \frac{a_{ij}}{a_{ii}... ...\ldots, n,\mapsto x_1=\frac{11}{6}-\left(\frac{-2}{6}x_2+\frac{1}{6}x_3\right)$$

• Each equation now solved for the variables in succession:

  $$\begin{array}{l} x_1 = 1.8333 + 0.3333x_2 - 0.1667x_3 x_2 ... ....2857x_3 x_3 = 0.2000 + 0.2000x_1 + 0.4000x_2 \end{array}$$ (4.1)

  
  

• We begin with some initial approximation to the value of the variables.
• Say initial values are; $x_1=0,x_2=0,x_3=0$.
• Each component might be taken equal to zero if no better initial estimates are at hand.

• Note that this method is exactly the same as the method of fixed-point iteration for a single equation that was discussed in Section 3.7.
• But it is now applied to a set of equations; we see this if we write Eqn. 4.1 in the form of
  $$x^{(n+1)}=G(x^{(n)})= b' - Bx^{n}$$
  which is identical to $x_{n+1}= g(x_n)$ as used in Section 3.7.
• The new values are substituted in the right-hand sides to generate a second approximation,
• and the process is repeated until successive values of each of the variables are sufficiently alike.
• Now, general form

  $$\begin{array}{l} x_1^{(n+ 1)} = 1.8333 + 0.3333x_2^{(n)}- 0.1... ... 1)} = 0.2000 + 0.2000x_1^{(n)} + 0.4000x_2^{(n)} \end{array}$$ (4.2)

  
  

• Starting with an initial vector of $x^{(0)}=(0,0,0,)$, we obtain Table 4.4
  

  Table 4.4: Successive estimates of solution (Jacobi method)

  	First	Second	Third	Fourth	Fifth	Sixth	$\ldots$	Ninth
  $x_1$	0	1.833	2.038	2.085	2.004	1.994	$\ldots$	2.000
  $x_2$	0	0.714	1.181	1.053	1.001	0.990	$\ldots$	1.000
  $x_3$	0	0.200	0.852	1.080	1.038	1.001	$\ldots$	1.000

  
  
• In the present context, $x^{(n)}$ and $x^{(n+1)}$ refer to the $n^{th}$ and $(n+1)^{st}$ iterates of a vector rather than a simple variable, and $g$ is a linear transformation rather than a nonlinear function.
• Rewrite in matrix notation; let $A = L + D + U$,
  $$Ax=b, \left[ \begin{array}{rrr} 6 &-2 & 1 \\ -2 & 7 & 2 \... ...left[ \begin{array}{r} 11\\ 5\\ -1\\ \end{array}\right]$$
  $$L=\left[ \begin{array}{rrr} 0 & 0 & 0 \\ -2 & 0 & 0 \\ ... ...&-2 & 1 \\ 0 & 0 & 2 \\ 0 & 0 & 0 \\ \end{array} \right]$$

$$\begin{array}{l} Ax = (L + D + U)x= b \\ Dx = -(L + U)x + b\\ x = -D^{-1}(L + U)x + D^{-1}b\\ \end{array}$$

• From this we have, identifying $x$ on the left as the new iterate,
  $$x^{(n+1)} = -D^{-1}(L + U)x^{(n)} + D^{-1}b$$
  In Eqn. 4.2,
  $$b'=D^{-1}b=\left[ \begin{array}{l} 1.8333 \\ 0.7143 \\ 0.2000 \\ \end{array} \right]$$
  $$D^{-1}(L + U)=\left[ \begin{array}{rrr} 0 &-0.3333 & 0.1667... ... 0 & 0.2857 \\ -0.2000 & -0.4000 & 0 \\ \end{array} \right]$$

• This procedure is known as the Jacobi method, also called ''the method of simultaneous displacements'',
• because each of the equations is simultaneously changed by using the most recent set of $x$-values (see Table 4.4).