您當前的位置：首頁 > 動漫

數值計算方法第三章線性代數方程組的直接解法（2）

作者：由好吧發表于動漫時間：2020-04-16

四、範數介紹

由於不同的演算法計算效果不同，因此必須進行誤差分析。向量和矩陣的範數及矩陣的條件數在研究用數值方法所求得的線性方程組解的誤差分析中起著十分重要的作用。

1、向量範數

向量範數用來度量向量的大小。

定義

：

上的實函式

$|| \ ||$

，且滿足以下條件，其中

$x,y\in R^n，\alpha\in R$

非負性：

$|| x || \ge 0$

，且

$|| x || = 0 \Leftrightarrow x = 0$

齊次性：對於任意實數

$\alpha$

，有

$||\alpha x|| =\alpha || x ||$

滿足三角不等式：

$|| x + y ||\le || x || + || y ||$

則稱

$|| \ ||$

為

上的向量範數。設

$x,y\in R^n$

則

是

與

的距離。

常見的範數：p-範數

定理1：

定義在

上的實函式，

$|| x ||_p = (\sum_{j=1}^n |x_j|^p)^{1/p},\ \ p \ge 1,x\in R^n$

，則此向量範數稱為p-範數，是最常用的向量範數。

①歐幾里得範數

（2-範數）：

$|| x ||_2 = \sqrt{\sum_{i=1}^n x_i^2}$

②1-範數

：

$|| x ||_1 =\sum_{i=1}^n |x_i|$

③無窮範數

，即絕對值最大的元素的絕對值：

$|| x ||_{\infty} = \max_{1 \le j \le n} | x_j |$

定理2：向量範數是連續函式

證明：利用三角不等式

$|\ || x || - || y ||\ | \le || x - y ||$

，從當

$x\rightarrow y$

時，右端取模，就把向量的模與單位向量範數的數量分開了，易證模趨於0，單位向量範數的數量有界。

定義：

對於

上兩個不同的範數

$||\cdot ||_\alpha$

和

$||\cdot ||_\beta$

，任意向量

$x\in R^n$

，都存在一組正常數

$c_1,c_2\in R^+$

使得

$c_1 || x ||_\alpha \le || x ||_\beta \le c_2 || x ||_\alpha$

，則稱這兩種範數等價。有

$\lim_{k \rightarrow \infty}{||x^{(k)}-x||_\alpha=0}\Leftrightarrow \lim_{k \rightarrow \infty}{||x^{(k)}-x||_\beta=0}$

對於前面的①②③常見的p-範數，我們可以得到

$||x||_2\le||x||_1\le\sqrt{n}||x||_2$

（左邊展開證就行直接放，右邊柯西）

$||x||_\infty\le||x||_2\le\sqrt{n}||x||_\infty$

（左邊直接放掉n-1個未知量，右邊用方冪均值）

$||x||_\infty\le||x||_1\le n||x||_\infty$

定理3：

上所有向量範數等價（證明大概就是一邊直接放縮一邊用柯西）

定義：向量序列收斂

設

$x^{(1)},x^{(2)},...$

為

中的向量序列，其中

$x^{(k)}=[x_1^{(k)},...x_n^{(k)}]^T,k=1,2,3...$

設

$x=[x_1,...x_n]^T \in R^n$

，若

$\lim_{k \rightarrow \infty}{x_i^{(k)}}=x_i,i=1:n$

，即

$\lim_{k \rightarrow \infty}{||x^{(k)}-x||_\infty=0}$

，則稱向量序列

$x^{(1)},x^{(2)},...$

收斂於

，記為

$\lim_{k \rightarrow \infty}{x^{(k)}}=x$

。

定理4：

$\lim_{k \rightarrow \infty}{x^{(k)}}=x\Leftrightarrow\lim_{k \rightarrow \infty}{||x^{(k)}-x||=0}$

，即向量序列按範數收斂等價於向量的所有分量構成的序列收斂。

2、矩陣範數（矩陣條件數）

矩陣範數是對矩陣大小的度量。

全體

階方陣構成的空間可以看做

維的向量空間，自然想到將向量防暑範數的概念直接推廣到矩陣上。但這樣的推廣是有問題的，應考慮矩陣乘法運算。實用的矩陣範數除了滿足於向量範數對應的3個條件外，還應考慮到矩陣乘法運算的需要，在向量範數定義的基礎上增加相容性條件，得到如下定義。

①定義

：

$R^{n\times n}$

上的實函式

$|| \ ||$

，且滿足以下條件，其中

$A,B\in R^{n\times n}，\alpha\in R$

非負性：

$|| A || \ge 0$

，且

$|| A || = 0 \Leftrightarrow A = 0$

齊次性：對於任意實數

$\alpha$

，有

$||\alpha A|| =\alpha || A ||$

三角不等式：

$|| A + B ||\le || A || + || B ||$

相容性：

$||AB||\le||A||\cdot ||B||$

（

在誤差分析中經常會用到)

則稱

$|| \ ||$

為

$R^{n\times n}$

上的向量範數。設

$A,B\in R^{n\times n}$

，則

是

與

的距離。

矩陣範數可以看做是向量範數，所以矩陣範數具有向量範數的一切性質。例如，

$R^{n\times n}$

上任意兩個矩陣範數是等價的。

②定義（矩陣序列收斂）：

太長了。通俗說就是若所有位置元素序列收斂，則矩陣序列收斂。

由矩陣範數等價性可得：

$\lim_{k \rightarrow \infty}{A^{(k)}}=A\Leftrightarrow\lim_{k \rightarrow \infty}{||A^{(k)}-A||=0}$

，其中

$||\cdot||$

為

$R^{n\times n}$

上的任一範數。

1-範數是最大的列（絕對值）求和，∞-範數是最大的行（絕對值）求和

③定義（矩陣範數與向量範數的相容性）

：若矩陣範數

$||\cdot||_M$

和向量範數

$||\cdot||_V$

滿足

$||Ax||_M\le||A||_M||x||_V$

，

$A\in R^{n\times n},x \in R^{n}$

，則稱矩陣範數

$||\cdot||_M$

和向量範數

$||\cdot||_V$

是相容的。

事實上，給定任意向量範數，都可構造一個矩陣範數與它相容。

定理5：

設

$||\cdot ||$

是

上的一個向量範數，定義相應的矩陣函式

$f:R^{n\times n}\rightarrow R$

，

$f(A)=\max_{||x||=1,x\in R^n}{||Ax||}$

，

$\forall A\in R^{n\times n}$

，則

為矩陣範數。

此定理中定義的矩陣範數

$||\cdot||_M$

稱為從屬於向量範數

$||\cdot||_V$

的矩陣範數，也稱其為向量範數

$||\cdot||_V$

誘匯出的運算元範數。

可從

$R^{n}$

上最常用的p-範數得到

$R^{n\times n}$

上的運算元範數

$||\cdot||_p$

：

$|| A ||_p = \max_{x\ne 0} \frac{|| Ax ||_p}{|| x ||_p} = \max_{|| x ||_p = 1} || Ax ||_p , A\in R^{n\times n}$

對於

$p=1,2,...\infty$

所對應的運算元範數，有如下定理。

定理6：設

$A=[a_{ij}]\in R^{n\times n}$

則有

矩陣的1範數（列範數）：

$|| A ||_1 = \max_{1\le j \le n} || a_{(:,j)} ||_1$

矩陣的

$\infty$

範數（行範數）：

$|| A ||_{\infty} = \max_{1\le i \le n} || a_{(i,:)} ||_1$

矩陣的2範數：

$|| A ||_{2} =\sqrt{\lambda_{max}(A^TA)}$

，

$\lambda_{max}(A^TA)$

表示

的最大特徵值

除此之外還有一種範數，不是誘匯出的。

F範數：

$|| A ||_F=\sqrt{\sum_{i=1}^{n}\sum_{j=1}^{n}{a_{ij}^2}}$

矩陣的F-範數可以認為是向量2-範數的直接推廣，即將

階方陣看作

#FormatImgID_93# 維向量所得到。

還有幾個定理：

定理7（譜範數的性質）：設

$A\in R^{n\times n}$

，則

$①\ \ \||A||_2=max\{|y^TAx|:x,y\in C^n,||x||_2=||y||_2=1\}$

$②\ \ ||A^T||_2=||A||_2=\sqrt{||A^TA||_2}$

$③\ \$

對任意正交矩陣

和

有，

定理8（譜半徑與矩陣範數之間的關係）：設

$A\in C^{n\times n}$

，則有

$①\ \$

對

$C^{n\times n}$

上任意矩陣範數

$||\cdot||$

，都有

$\rho(A)\le||A||$

$②\ \$

對任意的

$\varepsilon>0$

，存在

$C^{n\times n}$

上的運算元範數

$||\cdot||$

，使得

$||A||\le\rho(A)+\varepsilon$

定理9：設

$A\in C^{n\times n}$

，則

$\lim_{k\rightarrow\infty}{A^k=0}\Leftrightarrow\rho(A)=1$

定理10：設

$||\cdot||$

是

$C^{n\times n}$

上的一個滿足條件

的矩陣範數，設

$A\in C^{n\times n}$

滿足

，則

可逆且有

$||(I-A)^{-1}||\le\frac{1}{1-||A||}$

定理11：設

$A\in C^{n\times n}$

，則有

$①\ \ \sum_{k=0}^{\infty}{A^k}$

收斂的充分必要條件是

$\rho(A)<1$

$②\ \$

當

$\sum_{k=0}^{\infty}{A^k}$

收斂時，有

$\sum_{k=0}^{\infty}{A^k}=(I-A)^{-1}$

，而且存在

$C^{n\times n}$

上的運算元範數

$||\cdot||$

，使得

$||(I-A)^{-1}-\sum_{k=0}^{m}{A^k}||\le\frac{||A||^{m+1}}{1-||A||},\forall m \ge0$

五、敏度分析

矩陣的誤差可以用矩陣範數表示。

設

是

的近似矩陣，

和

分別稱為矩陣

的關於範數

$||\cdot||$

的絕對誤差和相對誤差。

1、方程組的狀態與條件數

一個實際問題化為數學問題，初始資料往往會有誤差，即有擾動，從而使計算結果產生誤差，因此需要研究擾動對解的影響。

一圖直觀感受擾動影響：

一個方程組，由於係數矩陣或右端項的微小擾動，而引起解發生巨大變化時，稱該方程組是“病態”的。為了定量刻畫方程組“病態”的程度，下面對方程組進行討論。

①首先考察右端項

的擾動對解的影響。

設

有擾動

$\delta b$

，相應的解

的擾動為

$\delta x$

，則有

$A(x+\delta x)=b+\delta b$

，推導如下：

②考察左端項

的擾動對解的影響

③綜上

：一般地，若係數矩陣

有擾動

$\delta A$

，

有擾動

$\delta b$

，相應的解

的擾動為

$\delta x$

，則有

$\frac{||\delta x||}{||x||}\le\frac{||A||\ ||A||^{-1}}{1-||A||\ ||A||^{-1}\frac{||\delta A||}{||A||}}(\frac{||\delta A||}{||A||}+\frac{||\delta b||}{||b||})\tag{*}$

即，當係數矩陣或右端項有擾動時，數

$||A||\ ||A||^{-1}$

控制瞭解的擾動程度。也就是說，數

$||A||\ ||A||^{-1}$

可以反應方程組的狀態。

定義：

對非奇異矩陣

，稱數

$||A||\ ||A||^{-1}$

為矩陣

的條件數，記為

$cond(A)=||A||\ ||A||^{-1}$

係數矩陣

的條件數刻畫了方程組

的“病態”程度，條件數越大，“病態”越嚴重。如果係數矩陣

非奇異，且條件數

很大，則稱

是病態方程組或稱

為病態矩陣。如果條件數

相對很小，則稱

為

良態方程組

，或稱

為良態矩陣。

矩陣的條件數與所取範數有關：

其中

$\lambda_1$

分和

$\lambda_n$

別為矩陣

的最大的特徵值和最小特徵值，故又稱

為譜條件數。

條件數有以下性質：

（1）對任意

階方陣

，都有

$cond(A)\ge1$

$cond(A)=||A||\ ||A^{-1}||\le||AA^{-1}||=||I||=1$

（2）對任意非零實數

$\alpha$

，

$cond(\alpha A)=\ cond(A)$

（3）若為正交矩陣，則

還有一些定理都比較獨立，直接上圖了。

2、病態問題：

①病態問題的判斷

計算條件數需要要求矩陣的逆，因而比較困難。根據數值經驗，在下列情況下，方程組常是“病態”的。

在用主元素法時出現小主元；

係數矩陣中有行（或列）近似線性相關，或係數行列式的值近似於零。但這不是絕對的，如當

$A=\varepsilon I$

時，有

$det(A)\approx 0$

，

，方程組狀態良好；

係數矩陣

的元素數量級相差很大，並且無一定規律時可能病態；

解

出現一個很大的解；

②病態問題的處理方法

若

是病態的，可

採用高精度的數值運算

採用預處理方法

採用某些特殊的數值方法求解

重新尋找出現病態的原因，改變原問題的提法

③病態方程預處理方法

標簽：範數矩陣向量病態定理

上一篇:置信區間

下一篇：騙子密碼：倖存者偏差

猜你喜歡