Author: David Merkley
Language: Python
Task 1
Routine Name: UpperTriangle
Description/Purpose: This routine is designed to give an upper triangular matrix. Along with backsubstitution and matrix vector multiplication. I have added the code to my shared library.
Implementation/Code:
def UpperTriangle(n):
return [[i + j - 1 if j >= i else 0 for j in range(1, n + 1)] for i in range(1, n + 1)]
def matrixVectorMultiply(A, b):
n = len(b)
ans = [0] * n
for i in range(n):
for j in range(n):
ans[i] += A[i][j] * b[j]
return ans
def backSub(A, b):
n = len(b)
ans = [x for x in b]
for i in range(n - 1, -1, -1):
for j in range(n - 1, i, -1):
ans[i] -= A[i][j] * ans[j]
ans[i] /= A[i][i]
return ans
A = UpperTriangle(6)
print(A)
b = [1] * 5
ans = backSub(A, b)
print(ans)
Output:
[[1, 2, 3, 4, 5, 6]
[0, 3, 4, 5, 6, 7]
[0, 0, 5, 6, 7, 8]
[0, 0, 0, 7, 8, 9]
[0, 0, 0, 0, 9, 10]
[0, 0, 0, 0, 0, 11]]
[0.20317460317460312, 0.05079365079365078, 0.025396825396825407, 0.01587301587301588, 0.1111111111111111]
Task 2
Routine Name: LowerTriangle
Description/Purpose: This creates a lower triangular matrix and does forward substitution. I have also added this code to my shared library.
Implementation/Code:
def LowerTriangle(n):
return [[i + j - 1 if j <= i else 0 for j in range(1, n + 1)] for i in range(1, n + 1)]
def forwardSub(A, b):
n = len(b)
ans = [x for x in b]
for i in range(n):
for j in range(i):
ans[i] -= A[i][j] * ans[j]
ans[i] /= A[i][i]
return ans
A = LowerTriangle(6)
print(A)
b = [1] * 6
ans = forwardSub(A, b)
print(ans)
Output:
[[1, 0, 0, 0, 0, 0]
[2, 3, 0, 0, 0, 0]
[3, 4, 5, 0, 0, 0]
[4, 5, 6, 7, 0, 0]
[5, 6, 7, 8, 9, 0]
[6, 7, 8, 9, 10, 11]]
[1.0, -0.3333333333333333, -0.13333333333333336, -0.07619047619047618, -0.05079365079365077, -0.03694083694083698]
Task 3
Routine Name: RandomMatrix
Description/Purpose: This creates random matrices of any size for square matrices and the upper and lower and diagonal matrices. I have added this code to my shared library as well.
Implementation/Code:
import random
random.seed(0)
def randomSquare(n):
return [[random.random() for j in range(n)] for i in range(n)]
def LowerTriangleRandom(n):
return [[random.random() if j <= i else 0 for j in range(n)] for i in range(n)]
def UpperTriangleRandom(n):
return [[random.random() if j >= i else 0 for j in range(n)] for i in range(n)]
def DiagonalRandom(n):
return [[random.random() if j == i else 0 for j in range(n)] for i in range(n)]
n = 3
print(randomSquare(n))
print(UpperTriangleRandom(n))
print(LowerTriangleRandom(n))
print(DiagonalRandom(n))
Output:
[[0.8444218515250481, 0.7579544029403025, 0.420571580830845]
[0.25891675029296335, 0.5112747213686085, 0.4049341374504143]
[0.7837985890347726, 0.30331272607892745, 0.4765969541523558]]
[[0.5833820394550312, 0.9081128851953352, 0.5046868558173903]
[0, 0.28183784439970383, 0.7558042041572239]
[0, 0, 0.6183689966753316]]
[[0.25050634136244054, 0, 0]
[0.9097462559682401, 0.9827854760376531, 0]
[0.8102172359965896, 0.9021659504395827, 0.3101475693193326]]
[[0.7298317482601286, 0, 0]
[0, 0.8988382879679935, 0]
[0, 0, 0.6839839319154413]]
Task 4
Routine Name: RandomMatrix
Description/Purpose: I was struggling to understand how this was different from the diagonal random matrix that I created in the task beforehand. I just ended up using the diagonal matrix random from the previous task.
Implementation/Code:
def DiagonalRandom(n):
return [[random.random() if j == i else 0 for j in range(n)] for i in range(n)]
Output:
[[0.7298317482601286, 0, 0]
[0, 0.8988382879679935, 0]
[0, 0, 0.6839839319154413]]
Task 5
Routine Name: RowEchelon
Description/Purpose: This code puts the matrix in row echelon form. It still calculates the zeroes, and doesn’t check the pivots, but I still added it to my shared library.
Implementation/Code:
import random
def rowEchelon(A):
A = [[x for x in row] for row in A]
n = len(A[0])
for row in range(n - 1):
factor1 = A[row][row]
for i in range(row + 1, n):
factor2 = A[i][row]
for j in range(0, n):
A[i][j] = A[i][j] * factor1 - A[row][j] * factor2
return A
def randomSquare(n):
return [[random.random() for j in range(n)] for i in range(n)]
A2 = randomSquare(3)
print(rowEchelon(A2))
Output:
[[0.9103538994339362, 0.9371788207292169, 0.2992972567242699]
[0.0, 0.3504460209672572, 0.5528358018346146]
[0.0, 0.0, 0.2967427018084038]]
Task 6
There are different conditions for matrices and the pdf talks about how some inputs and roundoff errors can make your calculations go all out of whack. They use the equation Ax=b and try adding small numbers and get big changes. The wikipedia page talks about how the condition number actually measures how much the output can change for a small change in the input. It then goes into well and ill-conditioned numbers like we talked about in class.