HW 2 for CS 4220

You may (and probably should) talk about problems with the each other, with the TAs, and with me, providing attribution for any good ideas you might get. Your final write-up should be your own.

md"""

# HW 2 for CS 4220

You may (and probably should) talk about problems with the each other, with the TAs, and with me, providing attribution for any good ideas you might get. Your final write-up should be your own.

"""

164 μs

using LinearAlgebra

289 μs

using Plots

3.2 s

1: Norm!

Suppose $A \in \mathbb{R}^{m \times n}$ represents a mapping from $\mathbb{R}^n$ with the Euclidean norm to $\mathbb{R}^m$ with the infinity norm. Write a Julia function p1induced(A) to compute the induced norm for $A$. What is the value for $A = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}$?

Hint 1: You may use without proof that $\max_{\|x\|_2 = 1} c^T x = \|c\|_2$.

Hint 2: In Julia, eachrow can be used to iterate over the rows of a matrix. For example, to compute the infinity norm, beside writing opnorm(A, Inf), you could write

infnorm(A) = maximum(sum(abs(ai)) for ai in eachrow(A))

Note: In Julia's LinearAlgebra package, the opnorm function is used to compute operator norms or induced norms for matrices. The norm function computes vector norms even when applied to matrices. For example, opnorm([1.0 2.0; 3.0 4.0]) yields 7, but norm([1.0 2.0; 3.0 4.0]) yields 4.

md"""

#### 1: Norm!

Suppose $A \in \mathbb{R}^{m \times n}$ represents a mapping from $\mathbb{R}^n$ with the Euclidean norm to $\mathbb{R}^m$ with the infinity norm. Write a Julia function `p1induced(A)` to compute the induced norm for $A$. What is the value for $A = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}$?

*Hint 1*: You may use without proof that $\max_{\|x\|_2 = 1} c^T x = \|c\|_2$.

*Hint 2*: In Julia, `eachrow` can be used to iterate over the rows of a matrix. For example, to compute the infinity norm, beside writing `opnorm(A, Inf)`, you could write

infnorm(A) = maximum(sum(abs(ai)) for ai in eachrow(A))

*Note*: In Julia's `LinearAlgebra` package, the `opnorm` function is used to compute operator norms or induced norms for matrices. The `norm` function computes vector norms *even when applied to matrices*. For example, `opnorm([1.0 2.0; 3.0 4.0])` yields 7, but `norm([1.0 2.0; 3.0 4.0])` yields 4.

"""

1.9 ms

2: Diagonally Dominant

Suppose $A = D+F$ where $D$ is a diagonal matrix, and there exists $0 < \rho < 1$ such that for each $i$,

$$\rho |d_{ii}| > \sum_{j=1}^n |f_{ij}|$$

Argue that $\|D^{-1}\|_\infty = 1/(\min_i |d_{ii}|)$ and $\|D^{-1} F\|_\infty < \rho$. Argue from there that $D+F$ is invertible and

$$\|(D+F)^{-1}\|_\infty \leq \frac{1}{\left( \min_i |d_{ii}| \right) (1-\rho)}.$$

md"""

#### 2: Diagonally Dominant

Suppose $A = D+F$ where $D$ is a diagonal matrix, and there exists $0 < \rho < 1$ such that for each $i$,

$$\rho |d_{ii}| > \sum_{j=1}^n |f_{ij}|$$

Argue that $\|D^{-1}\|_\infty = 1/(\min_i |d_{ii}|)$ and $\|D^{-1} F\|_\infty < \rho$. Argue from there that $D+F$ is invertible and

$$\|(D+F)^{-1}\|_\infty \leq \frac{1}{\left( \min_i |d_{ii}| \right) (1-\rho)}.$$

"""

287 μs

3: Catastrophic cancellation

Suppose $f(x) = \sqrt{1+x}-\sqrt{1-x}$. As written, this is prone to catastrophic cancellation when $x \ll 1$. Write an equivalent expression that is accurate for very small values of $x$.

md"""

#### 3: Catastrophic cancellation

Suppose $f(x) = \sqrt{1+x}-\sqrt{1-x}$. As written, this is prone to catastrophic cancellation when $x \ll 1$. Write an equivalent expression that is accurate for very small values of $x$.

"""

162 μs