## <p style="text-align: right;"> &#9989; Put your name here</p>

In order to successfully complete this assignment, you must follow all instructions in this notebook and upload your edited ipynb file with your answers on or before **11:59pm on Friday Jan. 25th**.

**Please read though the entire project before starting!**



# Homework 1: Iterative Methods




In this homework, you will study and compare the convergence rates of two different iterative solvers (Jacobi and Gauss-Seidel). These solvers are described in details in Section 7.4 of the textbook.


- Part 1: A General Jacobi Method
- Part 2: Matrix Testing
- Part 3: Adding Stopping Conditions
- Part 4: Gauss-Seidel Method


----
# Part 1: A General Jacobi Method

Consider the following system of linear equations:

$$ 6x + 2y - 2z = -2$$
$$ x + 4y + z = 4$$
$$ 2x + 2y + 5z = 32$$


##  Solve using Numpy

Let's find the solution to the above system of linear equation using the ```numpy.linalg.solv``` function. 

&#9989; <font color=red>**DO THIS:**</font>  create a $3 \times 3$ ```Numpy``` matrix for the left hand side of the above system of equations (Call this $A$ matrix):


```python
# Put your code here
import numpy as np
```

&#9989; **DO THIS:** Create a $3 \times 1$ ```Numpy``` matrix for the right hand side of the above system of equations (Call this $b$):


```python
# Put your code here
```

&#9989; **DO THIS:** Run the ```numpy.linalg.solv``` function on $A$ and $b$ to find a solution for $x$, $y$, and $z$


```python
# Put your code here
```

## Verify Results using Sympy 

Let's verify the above solution using symbolic methods.  In this case, we are going to convert the problem into an augmented matrix and solve it by putting it in it's reduced row echelon form.

&#9989; <font color=red>**DO THIS:**</font> Create a $3 \times 4$ augmented matrix for the above system of equations:


```python
# Put your code here
import sympy as sym
sym.init_printing(use_unicode=True)
```

**DO THIS:** Run the ```rref``` function on your augmented matrix to find a solution for $x,y$ and $z$. 


```python
# Put your code here
```

## Solve using Jacobi

The following code defines a function that can take an arbitrary augmented matrix as an input and solve the system with the Jacobi method using the same basic approach we used in class. 


```python
# Some basid libraries we are using
%matplotlib inline
import matplotlib.pyplot as plt

import numpy as np
import sympy as sym
sym.init_printing(use_unicode=True)
```


```python
def jacobi(m,numiter=100):
    
    #Number of rows determins the number of variables
    numvars = m.shape[0]
    
    #construct array for final iterations
    history = np.zeros((numvars,numiter))
    i = 1
    while(i < numiter): #Loop for numiter
        
        for v in range(numvars): # Loop over all variables
            current = m[v,numvars] # Start with left hand side (augmented side of matrix)
            for col in range(numvars): #Loop over columns
                if v != col: # Don't count colume for current variable
                    current = current - (m[v,col]*history[col, i-1]) #subtract other guesses form previous timestep
            current = current/m[v,v] #divide by current variable coefficent

            history[v,i] = current #Add this answer to the rest
        i = i + 1 #iterate
    
    #plot each variable
    for v in range(numvars):
        plt.plot(history[v,: i]);
    return history[:,i-1]
```


```python
jacobi(m)
```

&#9989; <font color=red>**QUESTION:**</font> Inspect the above graph. Approximately how many iterations did the jacobi method take to converge?

Put your answer to the above question here.

## Big Problems

Now consider the following large augmented matrix:


```python
big_matrix = np.matrix([[30, 2,   7,   1, -3,  8, 0, 0, 3, 5, 1], 
                        [0,  64,  15,  0,   7,  -4, 0, 7, 7, 7, 2], 
                        [4,  2,   -88, 11, -4,  8, 3, 3, 9, 10, 3], 
                        [6,  4,   7,   52, 0,   0, 10, 11, 0, -9, 3], 
                        [8,  2,   24,  1, -51, 8, 1, 2, -1, -2, 4], 
                        [0,  -20, 7,   0,  9,  43, 10, 9, 4, 3, 3], 
                        [8,  4,   17,  -4,  4,  8, 70, 10, 9, 4, 2], 
                        [6,  2,   3,   -3, -1,  8, 0, 38, 11, -11, 1], 
                        [0,  2,   5,   -3,  0,  8, 0, 0, 33, -22, 0], 
                        [-4, 16,  9,   -2,  1,  8, 0, 0, 3, 50, 10]])
sym.Matrix(big_matrix)
```

&#9989; <font color=red>**QUESTION:**</font> Verify that the following matrix has a single solution by caclulating it's Reduced row Echelon form using SymPy:


```python
# Put your code here.
```

&#9989; <font color=red>**QUESTION:**</font>  Run the above Jacobi function on the ```big_matrix1```.


```python
#put your code here
```


```python
jacobi(big_matrix)
```

# Part 2: Matrix Testing

From Theorem 7.1 in the book, we know that the Jacobi method converges when the absolute value of the diagonal elements of each row **dominate** the sum of the absolute value for the other elements in the same row. 

&#9989; <font color=red>**DO THIS:**</font> Write a function (Lets call it ```checkJacobi```) that takes in a matrix as input and returns ```True``` if the matrix can be solved using the Jacobi method and ```False``` if it can not.  

**Note:** You can assume that the matrix is already put into a diagonally dominant form (i.e. do not try to figure out if you need to swap rows).


```python
# Replace the following code with your answer

def checkJacobi(m):
    return False
```

Lets test the matrix from above


```python
checkJacobi(A)
```




    True




```python
checkJacobi(big_matrix)
```

    5 43 62
    7 38 45
    8 33 40





    False



The big_matrix does not satisfy the conidition, but Jacobi method still converges for this case. So this condition is sufficient  but not necessary.

&#9989; <font color=red>**QUESTION:**</font>  Come up with a new augmented matrix (let's call it $A1$) which represents a system of linear equations with a solution but fails the above ```checkJacobi``` test. 


```python
# Put your answer here

A1 = np.matrix()
```

Run the following code to verify there is a solution to your equation by checking it's Reduced Row Echelon form:


```python
# This should return an identiy matrix on the right hand side
sym.Matrix(A1).rref()
```

Run the following code to verify that the system of equations is not row dominant. (i.e. your checkJacobi function should return false)


```python

# This should return False
checkJacobi(A1)
```

    0 1 3
    1 1 2
    2 3 3





    False



Run the Jacobi function defined above on your new function ($A1$).


```python
jacobi(A1)
```

&#9989; <font color=red>**QUESTION:**</font>  Describe in words how the Jacobi method responds to your $A1$ matrix.

Put your answer here

# Step 3: Adding Stopping Conditions

&#9989; <font color=red>**DO THIS:**</font>  Copy and paste the Jacobi function from above into the following cell and add a stopping condition for when the iteration has converged.  We will define "converged" to mean that all three variables do not change too much, i.e. the values for the current iteration have changed less than some threshold ```e``` from the values for the previous iteration.  

Make the threshold ```e``` an input to the function and set the default value to 0.000001.


```python
#Put your code here
```

Test your code using the three matrices defined above:


```python
jacobi(m, 100, 0.000001)
```


```python
jacobi(big_matrix, 100, 0.000001)
```


```python
jacobi(A1, 100, 0.000001)
```

&#9989; <font color=red>**QUESTION:**</font>  What happens to the number of iterations if you increase ```e```?

Put your answer to the above question here.

&#9989; <font color=red>**QUESTION:**</font>  What happens to the number of iterations if you decrease ```e```?

Put your answer to the above question here.

---
# Step 4: Gauss-Seidel Method

Read the textbook on Section 7.4 of the textbook for the explaination of the Gauss-Seidel method.


&#9989; <font color=red>**DO THIS:**</font>  Write a solver for the system of equations using the Gauss-Seidel Method.    Call this function ```GaussSeidel```:


```python
#Put your code here
```

&#9989; <font color=red>**DO THIS:**</font>  Test your code on the three matrices we have developed so far:


```python
GaussSeidel(m, 100, 0.000001)
```


```python
GaussSeidel(big_matrix, 100, 0.000001)
```


```python
GaussSeidel(A1, 100, 0.000001)
```

&#9989; <font color=red>**QUESTION:**</font>  How are the approaches different? Which approach is better?  Why?

Put your answer to the above question here.

&#9989; <font color=red>**DO THIS:**</font>  Before turning in your notebook, verify you have answered all the questions.  
- Use the Red/Bold (<font color=red>**QUESTION**</font> and <font color=red>**DO THIS**</font> )  text as a guild to where you will be evaluated. 
- The check mark symbols (&#9989;) are provided to help you keep track of what you have completed. Feel free to remove the check mark after completing each item. 
- Before submitting your document, clear and restart the Kernel and rerun the entire notebook. **THERE SHOULD BE NO ERRORS**



---------
### Congratulations, you're done with your Homework assignment!


Now, you just need to submit this assignment by uploading it to the course <a href="https://d2l.msu.edu/">Desire2Learn</a> web page for today's dropbox (Don't forget to add your names in the first cell).

&#169; Copyright 2018,  Michigan State University Board of Trustees

d60171c0d4a8b97313e59c72757dbc0dab4c90c1
ipynb
Jupyter Notebook
HW1-IterativeMethods.ipynb
shyorange/TestGitCommit
da30ad87ffcdaff16dc3e44114effe74ad0a8a53
MIT
HW1-IterativeMethods.ipynb
shyorange/TestGitCommit
da30ad87ffcdaff16dc3e44114effe74ad0a8a53
MIT
HW1-IterativeMethods.ipynb
shyorange/TestGitCommit
da30ad87ffcdaff16dc3e44114effe74ad0a8a53
MIT
Qwen/Qwen-72B
1. YES
2. YES