Algorithms Homework 1

Course policies and AI category¶

Read the Artificial Intelligence Policy and Collaboration Policy and Honor Code before starting. Assignment-specific directions control. The categories are No AI, AI permitted after independent work, and AI required.

Unless a problem says otherwise, its category is AI permitted after independent work. Spend about 30 minutes on each top-level problem without AI, solution pages, or another person’s help, stopping early if complete. You may consult lecture notes, textbooks, and nonsolution pages of the course website; bias toward those course sources. Afterward, AI and genuine collaboration, including coding together, are permitted. Everyone must contribute intellectually, understand the work, and verify it.

At the end of each top-level problem, add a concise AI and independent-work report: approximately how long the independent attempt took, how far you got, where you became stuck, any AI or collaborative help used afterward, and how you verified it. If you used no AI, say so. Do not submit prompts or transcripts. Time estimates help the instructor improve the assignment and are not a speed test.

# Load required Python libraries.
import matplotlib.pyplot as plt
import numpy as np
from scipy import linalg

Linear Algebra Review¶

Exact solution¶

Solve the following system of linear equations BY HAND with exact arithmetic:

3 x_1 + 2 x_2 + x_3 = 6

(1)

-x_1 + 4 x_2 + 5x_3 = 8

(2)

2x_1 -8 x_2 + 10 x_3 = 4

(3)

Turn in your work via Gradescope.

Solve using the inverse¶

Solve the same linear system by first inverting the matrix A and performing matrix multiplication. You should use Python and SciPy.

Tutorials and documentation: https://docs.scipy.org/doc/scipy-1.1.0/reference/tutorial/linalg.html

# Add your solution here

# Add your solution here

# Add your solution here

Solve using LU decomposition¶

Do the following:

Use linalg.lu(A) to calculate $P$ , $L$ , and $U$ .
Write a function to solve any linear system given the factorization and $b$ . You may not use linalg.solve in your function. Instead, you should write loops to implement back substitution.
Use your function to solve the linear system.

# You need to define the matrix A1 somewhere (or change the variable name)
P, L, U = linalg.lu(A1)

# Permutation matrix
print(P)

# Lower diagonal matrix
print(L)

# Upper diagonal matrix
print(U)

[[1. 0. 0.]
 [0. 0. 1.]
 [0. 1. 0.]]
[[ 1.          0.          0.        ]
 [ 0.66666667  1.          0.        ]
 [-0.33333333 -0.5         1.        ]]
[[ 3.          2.          1.        ]
 [ 0.         -9.33333333  9.33333333]
 [ 0.          0.         10.        ]]

Tip: We discussed this algorithm in class. First write pseudocode on paper (how to translate our notes into loops, logical statements, etc.?). Once you are happy with the logic, code it up.

# Write function here.
def my_lu_solve(P, L, U, b, LOUD=True):
    """
    Solves linear system Ax = b given PLU decomposition of A

    Arguments:
        P - N by N permutation matrix
        L - N by N lower triangular matrix with 1 on diagonal
        U - N by N upper triangular matrix
        b - N by 1 vector

    Returns:
        x - N by 1 solution to linear system
    """

    # Define x so this does not give an error. You can delete the line below.
    x = []

    # Add your solution here

    return x

x = my_lu_solve(P, L, U, b, LOUD=True)

Solve using `linalg.solve`¶

# Add your solution here

Eigenvalues¶

Calculate eigenvalues by hand (on paper)¶

Calculate the eigenvalues for the following matrix:

A = \begin{bmatrix} 0 & -4 & -6 \\ -1 & 0 & -3 \\ 1 & 2 & 5 \end{bmatrix}

(4)

You may need to do this for a small system on an exam to characterize stationary points of an optimization problem. Hence I would like you to practice at least once on the homework.

Calculate eigenvalues using `linalg.eig`¶

Calculate the eigenvalues and corresponding (right) eigenvectors.

# Add your solution here

# Add your solution here

Definiteness¶

Based on your calculations above, is this matrix

positive definite
positive semi definite
negative definite
negative semi definite
indefinite or
cannot say without additional calculations?

Briefly comment to justify your answer.

Note: In this class, “briefly comment” means write a few sentences, sketch a picture, write an equation or some combination... whichever you feel is necessary to succinctly provide justification.

Singular Value Decomposition¶

TODO: Make this a separate problem (after the assignment is turned in this year).

SVD calculation using `linalg.svd`¶

Calculate the singular value decomposition of the following matrix using linalg.svd:

A_3 = \begin{bmatrix} 1 & 2 & 0 & -1 \\ 2 & 4 & 10^{-6} & -2 \\ 0 & 2 & -1 & 10^{-3} \end{bmatrix}

(5)

# Add your solution here

# Add your solution here

Condition number¶

What is the condition number of the matrix? Calculate it two ways:

Using SVD results
Using np.linalg.cond()

# Add your solution here

# Add your solution here

Linear system¶

Consider the linear system $A_4 \cdot x = b$ with $b = [1, 0, 3]^T$ and

A_4 = \begin{bmatrix} 1 & 2 & 0 \\ 2 & 4 & 10^{-1} \\ 0 & 2 & -1 \end{bmatrix} ~.

(6)

Approximately how much uncertainty $||\Delta b||_2$ can you tolerate if you want the uncertainty $||\Delta x||_2$ to be less than 10^-2?

# Add your solution here

Answer:

Make it singular¶

Do/answer the following:

Propose a change to a single entry in $A_4$ to make it singular.
What are the singular values and condition number after this change?
What can you say about the solution to $A_4 \cdot x=b$ after the change?

Answer:

Convexity¶

Please turn in via Gradescope.

Determine if the following functions are convex¶

$x^2 + ax + b, ~x \in \mathbb{R}$
$x^3, ~x \in \mathbb{R}$
$| x |, ~ x \in [ -5, 5]$
$x + y, ~ x \in \mathbb{R}, ~ y \in \mathbb{R}$
$x \cdot y, ~ x \in \mathbb{R}, ~ y \in \mathbb{R}$
$\log(x), ~ x \in (0,1]$

Prove the following properties¶

Consider twice differentiable function $f(x): \mathbb{R}^n \rightarrow \mathbb{R}$ .

Recall that $f(x)$ is convex on $x \in \mathbb{R}^n$ if and only if

$f(x+p) \geq f(x) + \nabla f(x)^T p$ for all $x, p \in \mathbb{R}^n$

PSD implies Convexity¶

Prove that if $\nabla^2 f(x)$ is positive semidefinite for all $x \in \mathbb{R}^n$ , then $f(x)$ must be convex.

Convexity implies PSD¶

Prove that if $f(x)$ is convex then $\nabla^2 f(x)$ must be positive semidefinite.

PD implies Strictly Convex¶

Prove that if $\nabla^2 f(x)$ is positive definite for all $x \in \mathbb{R}^n$ , then $f(x)$ must be strictly convex.

Course policies and AI category¶

Linear Algebra Review¶

Exact solution¶

Solve using the inverse¶

Solve using LU decomposition¶

Solve using linalg.solve¶

Eigenvalues¶

Calculate eigenvalues by hand (on paper)¶

Calculate eigenvalues using linalg.eig¶

Definiteness¶

Singular Value Decomposition¶

SVD calculation using linalg.svd¶

Condition number¶

Linear system¶

Make it singular¶

Convexity¶

Determine if the following functions are convex¶

Prove the following properties¶

PSD implies Convexity¶

Convexity implies PSD¶

PD implies Strictly Convex¶

Solve using `linalg.solve`¶

Calculate eigenvalues using `linalg.eig`¶

SVD calculation using `linalg.svd`¶