每週問題 January 4, 2016

計算可交換矩陣構成的分塊矩陣的特徵值。

Let A and B be n\times n matrix. If AB=BA, find the eigenvalues of

\begin{bmatrix}  A&B\\  B&-A  \end{bmatrix}.

繼續閱讀

張貼在 pow 特徵分析, 每週問題 | 標記 , , | 發表留言

內積與外積是怎麼來的?

本文的閱讀等級:初級

在歐幾里得空間 \mathbb{R}^3,兩個向量的內積與外積是怎麼來的?從決定論 (determinism) 的觀點,內積與外積之所以如此定義,可以用先前的數學發展和事態來解釋。愛爾蘭數學家哈密頓 (William Rowan Hamilton) 於1843年提出四元數 (quaternion) 的概念。一個四元數是一個實數加上三個虛部 (見“四元數”),記為 q=a+bi+cj+dk,其中 a,b,c,d 是實數,虛數單位 i,j,k 滿足基本公式 i^2=j^2=k^2=ijk=-1。1878年,英國數學家克利福德 (William Kingdon Clifford)[1] 出版 Elements of Dynamic,書中首次用純量積 (scalar product) 與向量積 (vector product) 表示兩個四元數的積。今天,我們習慣稱純量積為點積 (dot product) 或內積 (inner product),向量積則稱為外積或叉積 (cross product)。令 \mathbf{i}=(1,0,0)\mathbf{j}=(0,1,0)\mathbf{k}=(0,0,1)\mathbb{R}^3 的標準單位向量。一個四元數可用純量─向量和表示為 q=a+\mathbf{v},其中 a\in\mathbb{R}\mathbf{v}=b\mathbf{i}+c\mathbf{j}+d\mathbf{k}\in\mathbb{R}^3,並滿足單位向量乘法規則 \mathbf{i}^2=\mathbf{j}^2=\mathbf{k}^2=\mathbf{i}\mathbf{j}\mathbf{k}=-1。給定兩個四元數 q_1=a_1+\mathbf{v}_1q_2=a_2+\mathbf{v}_2,乘法運算結果如下 (見“四元數與三維空間旋轉”):

q_1q_2=(a_1+\mathbf{v}_1)(a_2+\mathbf{v}_2)=(a_1a_2-\mathbf{v}_1\cdot\mathbf{v}_2)+(a_1\mathbf{v}_2+a_2\mathbf{v}_1+\mathbf{v}_1\times\mathbf{v}_2)

其中 \mathbf{v}_1\cdot\mathbf{v}_2 為內積,\mathbf{v}_1\times\mathbf{v}_2 為外積。克利福德英年早逝,不及推廣他的內積與外積運算。1901年,美國物理學家吉布斯 (Josiah Willard Gibbs)[2] 的學生將他的課堂講義整理成書,名為《向量分析 (Vector Analysis)》。這本影響深遠的教科書不僅制定內積與外積符號並建立代數運算規則,從而推廣內積與外積至物理學與幾何學 (事實上,自1881年,吉布斯的講義即已廣泛流傳於歐美學界)。從目的論 (teleology) 的觀點,內積與外積之所以如現在這般,可以用它們的最終目的來解釋。不過,即便內積與外積在物理學與幾何學有廣泛的應用,但它們並不具備某個大眾認同的特定最終目的。撇開決定論與目的論,純粹從學習探索的角度,為尋思內積與外積的由來,本文通過設計滿足某些數學性質的函數來推導內積與外積的操作型定義。

繼續閱讀

張貼在 內積空間, 主題專欄 | 標記 , , , , | 發表留言

每週問題 December 28, 2015

計算 \begin{bmatrix} A&A\\ A&A \end{bmatrix} 的特徵值。

Let A be an n\times n matrix. Find the eigenvalues of \begin{bmatrix} A&A\\ A&A \end{bmatrix} in terms of those of A.

繼續閱讀

張貼在 pow 特徵分析, 每週問題 | 標記 , | 發表留言

利用舒爾引理證明可交換矩陣同時可三角化

本文的閱讀等級:中級

\mathfrak{F}=\{A_1,\ldots,A_m\} 為一 n\times n 階兩兩可交換 (commuting) 矩陣集,也就是說任兩矩陣 A_iA_j 滿足 A_iA_j=A_jA_i。以下考慮 n\ge 2。可交換矩陣集 \mathfrak{F} 的所有矩陣同時可三角化,具體而言,存在一么正 (unitary) 矩陣 UU^\ast=U^{-1},使得 U^{\ast}A_iUi=1,\ldots,m,為上三角矩陣 (見“同時可三角化矩陣”)。本文介紹一個利用舒爾引理 (Schur’s lemma) 的證明方法。

繼續閱讀

張貼在 特徵分析, 主題專欄 | 標記 , , , | 發表留言

Jordan-Chevalley 分解

本文的閱讀等級:高級

對於一 n\times n 階複矩陣 A,Jordan-Chevalley 分解[1]是指存在唯一的可對角化矩陣 S 與冪零 (nilpotent) 矩陣 N 使得 A=S+NSN=NS (稱為可交換)。對於複矩陣,Jordan-Chevalley 分解很容易以 Jordan 典型形式表達 (見“Jordan 形式大解讀 (上)”)。我們利用 Jordan 形式證明 Jordan-Chevalley 分解的存在性與唯一性。

繼續閱讀

張貼在 典型形式, 主題專欄 | 標記 , , , | 3 則迴響

每週問題 December 21, 2015

這是計算一線性變換的特徵值與特徵向量。

Let A be an n\times n matrix, and T be the linear transformation defined by T(A)=\frac{A+A^T}{2}. For n>1, find the eigenvalues and corresponding eigenvectors of T.

繼續閱讀

張貼在 pow 特徵分析, 每週問題 | 標記 , , | 發表留言

交換子的充要條件

本文的閱讀等級:中級

C 為一 n\times n 階矩陣。我們稱 C 為交換子 (commutator),如果存在 n\times n 階矩陣 AB 使得 C=AB-BA (見“交換子與可交換矩陣”)。判定方陣 C 是否為交換子的方法非常簡單:C 為交換子的一個充要條件是 \hbox{trace}\,C=0。例如,單位矩陣 I_n 不是交換子,因為 \hbox{trace}\,I_n=n>0。若 C 為交換子,使用跡數循環不變性 (見“跡數的性質與應用”),可得

\hbox{trace}\,C=\hbox{trace}(AB-BA)=\hbox{trace}(AB)-\hbox{trace}(BA)=0

下面證明:若 \hbox{trace}\,C=0,則 C 是一個交換子。證明包含三個部分,分述於下。

繼續閱讀

張貼在 向量空間, 主題專欄 | 標記 , | 發表留言

從滿正交法 (FOM) 推導共軛梯度法 (CG)

本文的閱讀等級:高級

考慮線性方程 A\mathbf{x}=\mathbf{b},其中 An\times n 階可逆實矩陣,\mathbf{b}\in\mathbb{R}^n 是非零向量。在線性方程的迭代解法中,滿正交法 (full orthogonalization method,簡稱 FOM) 適用於一般非對稱矩陣,共軛梯度法 (conjugate gradient method,簡稱 CG) 則限定於實對稱正定矩陣。令 \mathbf{x}_0 為初始猜測解,\mathbf{r}_j=\mathbf{b}-A\mathbf{x}_j 為對應近似解 \mathbf{x}_j 的殘差 (residual),以及 Krylov 子空間 \mathcal{K}_j=\hbox{span}\{\mathbf{r}_0,A\mathbf{r}_0,\ldots,A^{j-1}\mathbf{r}_0\}。FOM 與 CG 同屬 Krylov 子空間法,而且有同樣的定義條件:

  1. \mathbf{x}_j-\mathbf{x}_0\in\mathcal{K}_j
  2. \mathbf{r}_j\perp\mathcal{K}_j

本文從 FOM 推導 CG,證明 CG 是 FOM 的一種簡約表達。關於 FOM 與 CG 的介紹,請參閱“Krylov 子空間法──線性方程的數值解法 (二):GMRES 與 FOM”和 “Krylov 子空間法──線性方程的數值解法 (三):共軛梯度法”。

繼續閱讀

張貼在 數值線性代數, 主題專欄 | 標記 , , , | 發表留言

每週問題 December 14, 2015

這是可交換矩陣的秩不等式證明問題。

Let A and B be n\times n matrices. If AB=BA, show that

\hbox{rank}(A+B)\le\hbox{rank}A+\hbox{rank}B-\hbox{rank}(AB).

繼續閱讀

張貼在 pow 向量空間, 每週問題 | 標記 , , | 2 則迴響

Krylov 子空間法──線性方程的數值解法 (三):共軛梯度法

本文的閱讀等級:高級

共軛梯度法 (conjugate gradient method) 是一個適用於實對稱正定矩陣的線性方程數值解法。顧名思義,共軛梯度法的核心是共軛 (conjugacy) 和梯度 (一階導數)。共軛能夠加快收斂,梯度則提供正交基底。因為這兩個特性,共軛梯度法的結構簡單優美,儲存量及運算量少,並且無須設定參數。對於大尺寸矩陣,我們往往無法使用直接法求解,譬如 Cholesky 分解 (見“Cholesky 分解”),這時候可以採用以迭代方式計算的共軛梯度法。此外,對於大型非線性最佳化問題,共軛梯度法也是最有效的數值算法之一。

繼續閱讀

張貼在 數值線性代數, 主題專欄 | 標記 , , , , | 發表留言