6.2: Jacobi Method for solving Linear Equations

Last updated
Save as PDF

Page ID: 63897

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

During class today we will write an iterative method (named after Carl Gustav Jacob Jacobi) to solve the following system of equations:

\[ 6x + 2y - ~z = 4~ \nonumber \]

\[~ x + 5y + ~z = 3~ \nonumber \]

\[ 2x +~ y + 4z = 27 \nonumber \]

Here is a basic outline of the Jacobi method algorithm:

Initialize each of the variables as zero \( x_0 = 0, y_0 = 0, z_0 = 0 \)
Calculate the next iteration using the above equations and the values from the previous iterations. For example here is the formula for calculating \(x_i\) from \(y_{(i-1)}\) and \(z_{(i-1)}\) based on the first equation: \(x_i = \dfrac{4-2y_{(i-1)} + z_{(i-1)}}{6} \). Similarly, we can obtain the update for \(y_i\) and \(z_i\) from the second and third equations, respectively.
Increment the iteration counter \(i=i+1\) and repeat Step 2.
Stop when the answer “converges” or a maximum number of iterations has been reached. (ex. \(i = 100\))

Important Note

A sufficient (but not necessary) condition for the method to converge is that the matrix A is strictly or irreducibly diagonally dominant. Strict row diagonal dominance means that for each row, the absolute value of the diagonal term is greater than the sum of absolute values of other terms. - From Wikipedia

In other words, the Jacobi Methid will not work an all problems.

Do This

Write out the equations for \(x_i\), \(y_i\), and \(z_i\) based on \(x_{(i−1)}, y_{(i−1)}\), and \(z_{(i−1)}\).

Do This

Complete the following code by adding formulas for \(y_i\) and \(z_i\) to solve the above equations using the Jacobi method.

%matplotlib inline
import matplotlib.pylab as plt

x = []
y = []
z = []

#step 1: inicialize to zero
x.append(0)
y.append(0)
z.append(0)

for i in range(1,100):
    xi = (4 - 2*y[i-1]+ z[i-1])/6
#####Start your code here #####
    yi = 0 #Change this line
    zi = 0 #Change this line
#####End of your code here#####        
    #Add latest value to history
    x.append(xi)
    y.append(yi)
    z.append(zi)

#Plot History of values
plt.plot(x, label='x')
plt.plot(y, label='y')
plt.plot(z, label='z')
plt.xlabel('Iteration')
plt.ylabel('Value')
plt.legend(loc=1);

Question

What are the final values for \(x\), \(y\), and \(z\)?

\[ x = \nonumber \]

\[ y = \nonumber \]

\[ z = \nonumber \]

Do This

Write out each of the above equations and show that your final result is a solution to the system of equations:

# Put your code here

Question

By inspecting the graph, how long did it take for the algorithum to converge to a solution?

Question

How could you rewrite the above program to stop earlier.