4

The book I follow and on net also, all that I can find is the algorithm to find the solution, but I don't quite understand the physical significance or logic behind the algorithm.

Can someone please help.

Hanul Jeon
  • 27,376
Manish
  • 565

2 Answers2

3

Let me give you an example.

Suppose we want to solve the following equation in an iterative way: $$\begin{cases}2x+y=6\\ x+2y=6\end{cases}$$ We write it in the following form to get a fixed point iteration: $$\begin{cases}x=-\frac{1}{2}y+3\\ y=-\frac{1}{2}x+3\end{cases}$$ Given initial guess $x^{(0)}=\begin{pmatrix}0\\0\end{pmatrix}$, we plug it into the right hand side of the system to get the next approximate solution $x^{(1)}$ and continue. You will eventually get close to the true solution $\begin{pmatrix}2\\2\end{pmatrix}$.

Here is a picture to illustrate the iteration: enter image description here If we switch the equations of the original problem,

$$\begin{cases}x+2y=6\\ 2x+y=6\end{cases}$$

it wouldn't work. You can try again using the initial guess $x^{(0)}=\begin{pmatrix}0\\0\end{pmatrix}$.

The following picture shows the second one:

enter image description here

The problem is the slopes $-2$ and $-2$ amplify the solutions and make them go to infinity.

So the Jacobi method is really a fixed point iteration, where we want the "slope" (derivative) of the right hand side less than 1.

Basically, we solve each equation in the system for its diagonal element, then iteratively plug in the old numbers to get new numbers.

If the "slope" is less than 1 (strictly diagonally dominant), then the method converges to the true solution.

I hope this helps.

KittyL
  • 16,965
  • This actually helps a lot. I want to know that was this just an observation or vice-versa, i.e. the method was created keeping this observation in mind. Like for eg. Newton's polynomial method uses the concept that the tangent keeps you giving closer approximations, and based on this logic it was put mathematically into a formula. So i was just curious that, did this method also have a mathematical formulation after observation. – Manish Feb 18 '15 at 18:44
  • That's an interesting question. I would rather think the method was developed to simulate the fixed point iteration in single equations. The theorem was then along the line. I don't know if there's resource on this though. – KittyL Feb 18 '15 at 19:10
  • :D Will try to find out – Manish Feb 18 '15 at 19:14
  • I'm having trouble seeing how this is a fixed point iteration. I mean, it just so happens that the solution to the system you chose lies on the y=x line, so it is indeed a fixed point of both equations. But what happens when the solution doesn't lie on y=x? – Stefan Dimeski Jul 26 '19 at 01:00
  • 1
    @user3071028: You can try $2x+y=6, x+3y=6$. The solution is $x=2.4, y=1.2$, not on the diagonal line, but the process would be the same. The fixed point is corresponding to the system, not to the individual equations. You can easily see it when you transform the system into the form $x=\cdots, y=\cdots$. – KittyL Jul 27 '19 at 08:53
2

You are trying to solve $A \textbf{x} = \textbf{b}$.

The matrix $A$ could be written $A = D + N$ where $D$ is diagonal. If the sequence $\textbf{x}^k$ generated by $D\textbf{x}^{k+1} = b - N\textbf{x}^k$ converges, then you have $D\textbf{x}^{\infty} = b - N\textbf{x}^{\infty}$ or $A \textbf{x}^{\infty} = \textbf{b}^{\infty}$.

If $A$ is diagonal, then $N=0$ and there is no iteration to do.

The condition for convergence is $|| D^{-1} N || < 1$. Intuitively, not super accurate but helpful, think that in the iteration $\textbf{x}^{k+1} = D^{-1} b- D^{-1} N\textbf{x}^{k}$, the error term $D^{-1} N\textbf{x}^{k}$ gets smaller after each iteration and the equation approaches $\textbf{x} \approx D^{-1} b $. There is a theorem for this, look up if you want rigor.

Quynh Nguyen
  • 31