Chapter 6 extra note 6

Operator norm
condition number

---

Operator norm of a linear transformation

Given

$T\in \mathcal{L}(V,W)$ where

$V$ and

$W$ are normed spaces. The operator norm of

$T$, denoted by

$\Vert T\Vert$, is defined as

$$\begin{array}{}\text{(1)}& \Vert T\Vert =\underset{\mathbf{v}\in \mathbf{V}\mathbf{,}\Vert \mathbf{v}\Vert \le \mathbf{1}}{max}\{\Vert T\mathbf{v}\Vert \}.\end{array}$$

Remark:
(1) is often called operator norm or natural norm.

Remark:
One should verify that (1) indeed defines a norm.

Proposition:

$$\begin{array}{}\text{(2)}& \Vert T\Vert =\underset{\mathbf{v}\in \mathbf{V}\mathbf{,}\Vert \mathbf{v}\Vert \mathbf{=}\mathbf{1}}{max}\{\Vert T\mathbf{v}\Vert \}.\end{array}$$

• Proof (idea):

  If

  $\Vert \mathbf{v}\Vert \le 1$, then
  

  $$\begin{array}{}\text{(3)}& T\mathbf{v}=\Vert \mathbf{v}\Vert T\left(\frac{\mathbf{v}}{\Vert \mathbf{v}\Vert }\right)\le T\left(\frac{\mathbf{v}}{\Vert \mathbf{v}\Vert }\right).\end{array}$$

Proposition:

$$\begin{array}{}\text{(4)}& \Vert T\mathbf{v}\Vert \le \Vert T\Vert \Vert \mathbf{v}\Vert .\end{array}$$

• Proof (idea):

  $$\begin{array}{}\text{(5)}& \Vert T\mathbf{v}\Vert =\Vert \Vert \mathbf{v}\Vert T\left(\frac{\mathbf{v}}{\Vert \mathbf{v}\Vert }\right)\Vert =\Vert \mathbf{v}\Vert \Vert T\left(\frac{\mathbf{v}}{\Vert \mathbf{v}\Vert }\right)\Vert \le \Vert \mathbf{v}\Vert \Vert T\Vert .\end{array}$$

Proposition:
Let

$V$ and

$W$ be inner product space, then

$\Vert T\Vert ={\sigma }_1$.

• Proof:

  Given

  $\Vert \mathbf{v}\Vert \le 1$, we have
  

  $$\begin{array}{}\text{(6)}& \Vert T\mathbf{v}{\Vert }^2=\sum _{i=1}^r{\sigma }_i^2⟨\mathbf{v},{\mathbf{v}}_i{⟩}^2\le {\sigma }_1^2\sum _{i=1}^r⟨\mathbf{v},{\mathbf{v}}_i{⟩}^2\le {\sigma }_1^2.\end{array}$$
  Also, choose

  $\mathbf{v}={\mathbf{v}}_1$, we have
  

  $$\begin{array}{}\text{(7)}& \Vert T{\mathbf{v}}_1\Vert ={\sigma }_1.\end{array}$$
  Therefore,

  $\Vert T\Vert ={\sigma }_1$.

Example:
Let

$A\in {\mathbb{M}}_{m\times n}$, then

$A$ defines a linear transfomration and

$A\in \mathcal{L}({\mathbb{R}}^n,{\mathbb{R}}^m)$, and the operator

$2$-norm of

$A$ is

$$\begin{array}{}\text{(8)}& \Vert A{\Vert }_2=\sqrt{\rho (A^{\ast }A)},\end{array}$$
where

$\rho (A^{\ast }A)$ denotes the largest eigenvalue of

$A^{\ast }A$.

Remark:
Be aware that the notation here is different from the textbook.

---

Condition number

To find

$x$ such that

$Ax=b$.

Given

$\hat{x}$, we define the residual as

$r=b-A\hat{x}$.

Question: If

$\Vert r\Vert \le ϵ$, do we have

$\Vert x-\hat{x}\Vert <ϵ$?

Answer: NO!

---

Condition number measures how sensitive the answer is to perturbation in the input data.

Assuming that

$A\hat{x}=b-ϵ$, we define

$\hat{x}=x-\delta$ to have

$$\begin{array}{}\text{(9)}& A(x-\hat{x})=b-(b-ϵ)=ϵ\Rightarrow \delta =A^{-1}ϵ.\end{array}$$
Also,

$$\begin{array}{}\text{(10)}& \Vert \delta \Vert =\Vert A^{-1}ϵ\Vert \le \Vert A^{-1}\Vert \Vert ϵ\Vert ,\end{array}$$
and as a result,

$$\begin{array}{}\text{(11)}& \frac{\Vert \delta \Vert }{\Vert x\Vert }\le \frac{\Vert A^{-1}\Vert \Vert ϵ\Vert }{\Vert x\Vert }\frac{\Vert b\Vert }{\Vert b\Vert }=\frac{\Vert A^{-1}\Vert \Vert ϵ\Vert }{\Vert x\Vert }\frac{\Vert Ax\Vert }{\Vert b\Vert }\le \Vert A\Vert \Vert A^{-1}\Vert \frac{\Vert ϵ\Vert }{\Vert b\Vert }.\end{array}$$

We define

$\kappa (A)=\Vert A\Vert \Vert A^{-1}\Vert$ as the condition number of a matrix

$A$. We have

$$\begin{array}{}\text{(12)}& \frac{\Vert \delta \Vert }{\Vert x\Vert }\le \kappa (A)\frac{\Vert ϵ\Vert }{\Vert b\Vert }.\end{array}$$

Remark:

$$\begin{array}{}\text{(13)}& 1=\Vert I\Vert =\Vert A{A}^{-1}\Vert \le \Vert A\Vert \Vert A^{-1}\Vert =\kappa (A).\end{array}$$
So the condition number of a matrix is always greater than or equals to one.

Remark:
Condition number depends on the chosen norm. If we choose to use the operator

$2$-norm, then

$$\begin{array}{}\text{(14)}& \kappa (A)=\frac{{\sigma }_{max}}{{\sigma }_{min}},\end{array}$$
where

${\sigma }_{max}$(

${\sigma }_{min}$) denotes the largest(smallest) singular values of

$A$.

• working example - 2-by-2 linear system

---

計算數學 lecture 0

Question:
考慮調和級數(Harmonic series)

$$\sum _{n=1}^{\mathrm{\infty }}\frac{1}{n}$$
是否能以程式判斷其收斂或發散?

如果我們以電腦完全依照這級數一項一項做加法, 則一定會收斂到某個數字. 因為可以將此級數拆解為

$$\sum _{n=1}^{{10}^{16}}\frac{1}{n}+\sum _{n={10}^{16}+1}^{\mathrm{\infty }}\frac{1}{n}.$$
後面那個級數裡的每一項都小於 machine epsilon, 所以當他們被加進級數和時會沒有任何作用.

因此若以程式將此級數一項一項做加法, 一定會不大於前面那個級數和.

Remark:
1.

$$\sum _{n=1}^N\frac{1}{n}\approx {\int }_1^N\frac{1}{x}dx=\ln (N).$$
2.

$\ln ({10}^{16})\approx 37$.

---

Image compression

• SVD demo
• Image compression using SVD
• Vision transformer (ViT)
• Better SVD approximation of images, using the SVD