范数与矩阵条件数

向量范数

对于实向量xxx，下面给出几种常见的范数：

1-范数：

∣∣x∣∣1=∑i=1n∣xi∣||x||_1 = \sum _{i = 1}^n |x_i|∣∣x∣∣1​=i=1∑n​∣xi​∣

2-范数：

∣∣x∣∣2=(∑i=1n∣xi∣2)12=(xTx)12||x||_2 = (\sum _{i = 1}^n |x_i|^2)^{\frac{1}{2}} = (x^Tx)^{\frac{1}{2}}∣∣x∣∣2​=(i=1∑n​∣xi​∣2)21​=(xTx)21​

∞\infty∞-范数：

∣∣x∣∣∞=max1≤i≤n∣xi∣||x||_{\infty} = max_{1\le i \le n} |x_i|∣∣x∣∣∞​=max1≤i≤n​∣xi​∣

由此我们可以定义p-范数为：

∣∣x∣∣2=(∑i=1n∣xi∣p)1p,p≥1||x||_2 = (\sum _{i = 1}^n |x_i|^p)^{\frac{1}{p}},p\ge1∣∣x∣∣2​=(i=1∑n​∣xi​∣p)p1​,p≥1

向量范数的等价性

设∣∣x∣∣s||x||_s∣∣x∣∣s​ 和 ∣∣x∣∣t||x||_t∣∣x∣∣t​为RnR^nRn上任意两种向量范数，则存在常量c1,c2>0c_1,c_2 > 0 c1​,c2​>0，使得对一切x∈Rnx \in R^nx∈Rn有：

c1∣∣x∣∣s≤∣∣x∣∣t≤c2∣∣x∣∣sc_1||x||_s \le ||x||_t \le c_2 ||x||_sc1​∣∣x∣∣s​≤∣∣x∣∣t​≤c2​∣∣x∣∣s​

矩阵范数

在以上基础上，实际使用的矩阵范数还满足以下相容性条件：

∀A∈Rn×n,x∈Rn,∣∣Ax∣∣≤∣∣A∣∣ ∣∣x∣∣\forall A\in R^{n\times n},x\in R^n ,||Ax|| \le ||A|| \space||x||∀A∈Rn×n,x∈Rn,∣∣Ax∣∣≤∣∣A∣∣ ∣∣x∣∣

定义矩阵的算子范数为，这衡量了线性变换中对xxx伸缩的最大倍数。

∣∣A∣∣v=max⁡x≠0∣∣Ax∣∣v∣∣x∣∣v||A||_v = \max\limits_{x\ne 0} \frac {||Ax||_v}{||x||_v}∣∣A∣∣v​=x≠0max​∣∣x∣∣v​∣∣Ax∣∣v​​

我们需要在证明算子范数满足矩阵范数的条件（自己验证）

矩阵AAA的算子范数为:

1-范数：

∣∣A∣∣1=max⁡1≤j≤n∑i=1n∣aij∣||A||_1 = \max _{1\le j\le n}\sum_{i=1}^n |a_{ij}|∣∣A∣∣1​=1≤j≤nmax​i=1∑n​∣aij​∣

2-范数：

∣∣A∣∣2=λmax⁡(ATA),表示ATA的最大特征值||A||_2 = \sqrt{\lambda_{\max}(A^TA)}, \text{表示} A^TA\text{的最大特征值}∣∣A∣∣2​=λmax​(ATA)​,表示ATA的最大特征值

∞\infty∞-范数：

∣∣A∣∣∞=max1≤i≤n∑j=1n∣aij∣||A||_{\infty} = max_{1\le i \le n} \sum_{j = 1}^n|a_{ij}|∣∣A∣∣∞​=max1≤i≤n​j=1∑n​∣aij​∣

矩阵条件数

矩阵条件数是衡量非奇异矩阵的敏感程度，也就是方程Ax=bAx = bAx=b中ΔA\Delta AΔA、Δb\Delta bΔb的变化对矩阵的影响程度；我们不加证明的说明一下几个定理。

条件数定义：

cond=∣∣Δx∣∣/∣∣x∣∣∣∣Δb∣∣/∣∣b∣∣cond = \frac{||\Delta x||/||x||}{||\Delta b||/||b||}cond=∣∣Δb∣∣/∣∣b∣∣∣∣Δx∣∣/∣∣x∣∣​

设AAA为非奇异矩阵，则矩阵的条件数为：

cond(A)v=∣∣A∣∣v∣∣A−1∣∣=max⁡x≠0∣∣Ax∣∣∣∣x∣∣/min⁡x≠0∣∣Ax∣∣∣∣x∣∣cond (A)_v = ||A||_v ||A^{-1}||=\max\limits _{x \ne 0} \frac{||Ax||}{||x||} / \min\limits _{x \ne 0} \frac {||Ax||}{||x||}cond(A)v​=∣∣A∣∣v​∣∣A−1∣∣=x≠0max​∣∣x∣∣∣∣Ax∣∣​/x≠0min​∣∣x∣∣∣∣Ax∣∣​

根据条件数的定义，可以推导其和矩阵条件数的关系（考虑方程右边扰动）：

∵A(x+Δx)=b+Δb\because A(x +\Delta x) = b + \Delta b∵A(x+Δx)=b+Δb

AΔx=Δb⇒Δx=A−1Δb⇒∣∣Δx∣∣≤∣∣A−1∣∣ ∣∣Δb∣∣A \Delta x = \Delta b \Rightarrow \Delta x = A^{-1} \Delta b \Rightarrow ||\Delta x || \le ||A^{-1} ||\space ||\Delta b||AΔx=Δb⇒Δx=A−1Δb⇒∣∣Δx∣∣≤∣∣A−1∣∣ ∣∣Δb∣∣

Ax=b⇒∣∣b∣∣≤∣∣A∣∣ ∣∣x∣∣Ax = b \Rightarrow ||b || \le ||A|| \space ||x||Ax=b⇒∣∣b∣∣≤∣∣A∣∣ ∣∣x∣∣

∴cond=∣∣Δx∣∣/∣∣x∣∣∣∣Δb∣∣/∣∣b∣∣=∣∣Δx∣∣ ∣∣b∣∣∣∣Δb∣∣ ∣∣x∣∣≤∣∣A−1∣∣ ∣∣Δb∣∣ ∣∣A∣∣ ∣∣x∣∣∣∣Δb∣∣ ∣∣x∣∣=∣∣A∣∣ ∣∣A−1∣∣\therefore cond = \frac{||\Delta x||/||x||}{||\Delta b||/||b||} = \frac{||\Delta x||\space ||b||}{||\Delta b||\space||x||}\le \frac{||A^{-1}|| \space ||\Delta b|| \space ||A|| \space|| x||}{||\Delta b|| \space ||x||} = ||A|| \space ||A^{-1}||∴cond=∣∣Δb∣∣/∣∣b∣∣∣∣Δx∣∣/∣∣x∣∣​=∣∣Δb∣∣ ∣∣x∣∣∣∣Δx∣∣ ∣∣b∣∣​≤∣∣Δb∣∣ ∣∣x∣∣∣∣A−1∣∣ ∣∣Δb∣∣ ∣∣A∣∣ ∣∣x∣∣​=∣∣A∣∣ ∣∣A−1∣∣

矩阵的条件数为误差传递的上限，可衡量矩阵的敏感性

奇异矩阵的条件数为无穷大，因此cond(A)cond(A)cond(A)越大，越接近于奇异矩阵。

直观的来看，矩阵的条件数反映了矩阵的奇异程度，相对于行列式只能反映是否为奇异矩阵，是一个更好的度量方式。

矩阵的谱半径

设实矩阵A∈Rn×nA\in R^{n\times n}A∈Rn×n的特征值为λi\lambda_iλi​，称ρ\rhoρ为AAA的谱半径：

ρ(A)=max⁡1≤i≤n∣λi∣\rho (A) = \max\limits_{1\le i\le n}|\lambda_i|ρ(A)=1≤i≤nmax​∣λi​∣

注意，这里的谱半径是指模长（二范数），对于实数来说就是绝对值，对于复数来说是模长。

谱半径的大小不超过任何一种算子范数。

圆盘定理

∣λ−akk∣≤∑j=1,j≠kn∣akj∣|\lambda - a_{kk} |\le \sum\limits_{j =1,j \ne k } ^n |a_{kj}|∣λ−akk​∣≤j=1,j≠k∑n​∣akj​∣

直观的来看，在平面中，AAA的每个特征值都属于AAA的格什戈林圆盘中

可以用圆盘定理估计矩阵的特征值范围。

幂法

在矩阵AAA的特征值中，模最大的特征值称为主特征值，也叫“第一特征值”。对应的特征向量为主特征向量。

主特征值可能不唯一（正数负数复数）。

这里注意谱半径和主特征值的区别

谱半径是针对实矩阵而言，计算出来的是特征值的模长（一定大于零）；

主特征值是模长最大的那个特征值（对于复数来说不一样）

如果矩阵有唯一主特征值，则能通过幂法计算出主特征值和特征向量。幂法的计算过程是，首先任取一非零向量v0∈Rnv_0 \in R^nv0​∈Rn，再迭代计算

vk=Avk−1v_k = Av_{k-1}vk​=Avk−1​

根据vkv_kvk​求出主特征值和特征向量。

lim⁡k→∞vkλ1k=x1\lim\limits_{k \rightarrow \infty } \frac {v_k}{\lambda_1 ^k} = x_1k→∞lim​λ1k​vk​​=x1​

lim⁡k→∞(vk+1)j(vk)j=λ1\lim\limits_{k \rightarrow \infty } \frac {(v_{k+1})_ j}{(v_{k})_j } = \lambda_1k→∞lim​(vk​)j​(vk+1​)j​​=λ1​

如果模最大的特征值是重根且非亏损(代数重数等于几何重数)的话幂法适用，但是一旦出现亏损就容易出问题。

幻方矩阵的最大特征值为行和，即为n(n2+1)2\frac {n(n^2+1)}{2}2n(n2+1)​。