Norm
7-1:Norm
向量 Norm
Def 7.1
我們現在隨便給一個向量,我們需要定義怎麼測量他的長度,這個就叫做 norm,中文叫做「範」
假設我們現在給了向量 x, y,它們是
- 除了零向量以外,它的 norm 一定大於 0
- 零向量的 norm 為 0
- 裡面乘上任意一個實數,那個實數可以加絕對值提出來
- 三角不等式,兩個向量相加完取 norm 會小於等於兩個個別取 norm 相加

Def 7.2
那常見的 norm 有三個,這邊我們給一個
two norm
把每一個元素掛絕對值後平方加起來,再開根號
p norm
跟 two norm 很像,把每個元素掛絕對值後乘 p 次方加起來,再開 p 次方根
infinite norm
把所有的元素掛絕對值後取最大的那個

Def 7.5
另外,一個在

不一定要 two norm,N 通常是跟 epilson 有關的函數
Thm 7.3:柯西不等式
給兩個

Matrix norm
我們也可以對矩陣取 norm,這邊我們給一個在

A 的 norm 會等於 A 乘上一個向量 x 再除上 x 向量的 norm,這個 x 向量不能為零,然後這整個東西取 max
這邊我們可以看到我們要透過向量的 norm 來定義矩陣的 norm,我們也可以作改寫,像後面紅色框框那樣
那就像向量的 norm 有 one norm、two norm 等等,矩陣的 norm 也有這些 norm,那一個矩陣的這些 norm 我們該怎麼去定義它呢? 我們就這樣說:
A 是一個在

one norm 就是對一行(column) 裡面的每個元素取絕對值加起來,得到一個數字,然後再換下一行做一樣的事情,又得到一個數字,之後從這些數字裡面找最大的那個,這個最大的數字就是 A 的 one norm。 infinite norm 很像,只是是反過來對列(row) 來操作
然後有兩個重要的不等式:

Def 7.16
如果 A 自己一直乘下去會是一個零矩陣,我們說矩陣 A 收斂:

然後收斂會跟下面三點等價:

Chapter 7-2:特徵值與特徵向量
Def 7.13
定義相信大家都很清楚了,長這樣:

Def 7.14
但接下來這個大家可能就沒看過了,一個矩陣 A 的譜半徑(spectral radius) 定義為, 一個矩陣的特徵值掛上絕對值,再去取最大的那個,就是我們 A 矩陣的譜半徑:

Thm 7.15
接下來有一個很重要的定理,我們說 A 是一個在
- 你把
的譜半徑找出來再開根號就是 A 的 two norm - 一個矩陣的譜半徑一定小於等於 A 的 norm
證明如下:

Chapter 7-3 Jacobi 和 Gauss-Siedel 迭代法
什麼是一個迭代法呢? 我們可以想像說我們要解一個

紅色那根就是我們要求的向量,接著會有一個
我們要解一個
那什麼時候要用迭代法,什麼時候要用直接法呢? 答案很簡單,如果直接法能很快解出來,那我們就用直接法,不然就用迭代法。另外,如果 A 是一個稀疏矩陣,裡面有很多 0,那用迭代法也是個很好的選擇
迭代法會有一個初始條件

### Jacobi's Method
先給一個 A 矩陣:

下面推到第二列是我們把所有 i = j 的
但是我們要用這個式子我們仍需要知道右邊

可以看見這個數列基本上跟剛剛的等式一樣,差別就是我們在
看一下這個例子:

這邊

代入上面的數列的式子,一直代下去,最後就可以找到一個很接近的解

Matrix expression of Jacobi's method
前面我們推出來的公式,如果要用電腦來計算,可能得寫一堆判斷條件,為了方便寫程式來算,我們需要新的表示方式
我們先把 A 矩陣拆成 D + L + U:

這樣我們就有:

那我們就可以把 Jacobi 迭代法寫成:

如此一來,pseudo code 就會長得像這樣:

Step 4 的停止條件事可以被改寫的,上面這樣代表前一次迭代的值和現在的值兩個相減小於某個可容忍的值時就停止,這個叫做絕對誤差,我們也可以改得像這樣:
