高斯消去法與高斯─約當法的運算量

本文的閱讀等級:初級

高斯消去法 (Gaussian elimination) 是當今普遍用於解線性聯立方程組的演算法。高斯─約當法 (Gauss-Jordan method) 是高斯消去法的一種變形,主要應用於計算逆矩陣。關於這兩個算法的詳細介紹請見“高斯消去法”和“高斯─約當法”,本文僅討論它們耗費的運算量。

繼續閱讀

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

每週問題 August 11, 2014

這是關於 Gramian 矩陣 A^TAAA^T 的正定性判別問題,修改自“台聯大2013年碩士班招生考試試題 (電機類工程數學C)”。

Consider an m\times n real matrix A with linearly independent columns, and m>n. Which of the following statements are true?

(a) A^TA is positive definite.
(b) AA^T is positive definite.
(c) The column space of A is spanned by all the eigenvectors of AA^T.
(d) The row space of A is spanned by all the eigenvectors of A^TA.
(e) A and AA^TA have the same column space.

繼續閱讀

張貼在 pow 二次型, 每週問題 | 標記 , | 發表留言

每週問題 August 4, 2014

這是矩陣秩的計算問題,取自“台聯大2014年碩士班招生考試試題 (電機類工程數學D)”。

Let

\displaystyle  A=\frac{1}{2}\left[\!\!\begin{array}{crrr}  1&1&\sqrt{2}&0\\  1&1&-\sqrt{2}&0\\  1&-1&0&\sqrt{2}\\  1&-1&0&-\sqrt{2}  \end{array}\!\!\right]\left[\!\!\begin{array}{ccr}  1&1&0\\  0&2&0\\  0&0&-2\\  0&0&0  \end{array}\!\!\right]\left[\!\!\begin{array}{rrc}  \frac{1}{\sqrt{2}}&\frac{1}{\sqrt{6}}&\frac{1}{\sqrt{3}}\\[0.5em]  -\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{6}}&\frac{1}{\sqrt{3}}\\[0.5em]  0&-\frac{2}{\sqrt{6}}&\frac{1}{\sqrt{3}}\end{array}\!\!\right].

Find \text{rank}\begin{bmatrix}  AA^T&A\\  A^T&A^TA  \end{bmatrix}.

繼續閱讀

張貼在 pow 向量空間, 每週問題 | 標記 , | 發表留言

每週問題 July 28, 2014

這是從特徵值推論矩陣性質的問題,修改自“台聯大2013年碩士班招生考試試題 (電機類工程數學C)”。

Consider a 4\times 4 real matrix A with three different eigenvalues 0,1,2. Which of the following statements are true?

(a) The determinant of A is 0.
(b) There are three linearly independent eigenvectors.
(c) The rank of A is 2.
(d) The trace of A is 3.
(e) The column space of A is spanned by the eigenvectors corresponding to eigenvalues 1 and 2.

繼續閱讀

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

每週問題 July 21, 2014

這是內積空間於傅立葉級數的應用問題,取自“台聯大2014年碩士班招生考試試題 (電機類工程數學A)”。

Let f(t) be defined as follows:

\displaystyle  f(t)=\left\{\begin{array}{rl}  1,&\text{if~}0\le t<\pi\\  -1,&\text{if~}-\pi<t<0.  \end{array}\right.

Also, define

\displaystyle  g(t)=a\cos t+b\cos 2t+c\sin t.

Find the coeffiicents (a,b,c) such that E=\int_{-\pi}^{\pi}\vert g(t)-f(t)\vert^2 dt is minimized.

繼續閱讀

張貼在 pow 內積空間, 每週問題 | 標記 , | 3 則迴響

每週問題 July 14, 2014

這是關於二次型的性質與判別問題,取自“台聯大2014年碩士班招生考試試題 (電機類工程數學D)”。

Let A be an n\times n real matrix. Which of the following statements are true?

(a) If all the eigenvalues of A are positive, then \mathbf{x}^TA\mathbf{x}>0 for every nonzero \mathbf{x}\in\mathbb{R}^n.
(b) If all the eigenvalues of A are positive, then \det(A+A^T)>0.
(c) If \mathbf{x}^TA\mathbf{x}>0 for every nonzero \mathbf{x}\in\mathbb{R}^n, then \det A>0.
(d) If \mathbf{x}^TA\mathbf{x}<0 for every nonzero \mathbf{x}\in\mathbb{R}^n, then \det A<0.
(e) If \mathbf{x}^TA\mathbf{x}>0 for every nonzero \mathbf{x}\in\mathbb{R}^n, then \det (A+A^T)>0.

繼續閱讀

張貼在 pow 二次型, 每週問題 | 標記 , | 發表留言

每週問題 July 7, 2014

這是關於冪矩陣的計算問題,取自“台聯大2014年碩士班招生考試試題 (電機類工程數學A)”的部分試題。

Let

\displaystyle  A=\left[\!\!\begin{array}{cr}  1&-1\\  1&0  \end{array}\!\!\right].

Find the minimum positive integer n such that A^n=I.

繼續閱讀

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

2014 年大學指考數甲的線性代數問題

今年大學指考的數學甲試題比往年的難度大為提高,平易近人的基本觀念問題較少 (2014 年大學指考數甲試題)。補教老師說[1]:「今年數甲很多題目,以往考古題及學校模擬考都沒見過,恐怕有很多學生寫不完,程度好的學生也可能被考倒,試題反而缺乏鑑別度。」報導說:「多選題第八題最難,考『克拉碼公式』,是大學常用到的公式,但高中並不常見,計算耗時,連補教老師都花廿分鐘才解出答案。」下面抄錄這則最難的考題。

 
問題:考慮 x,y,z 的方程組 \left\{\begin{array}{l}  2^x-3^y+5^z=-1\\  2^{x+1}+3^y-5^z=4\\  2^{x+1}+3^{y+1}+a5^z=8  \end{array}\right.,其中 a 為實數。請選出正確的選項:

(1) 若 (x,y,z) 為此方程組的解,則 x=0

(2) 若 (x,y,z) 為此方程組的解,則 y>0

(3) 若 (x,y,z) 為此方程組的解,則 y<z

(4) 當 a\neq -3 時,恰有一組 (x,y,z) 滿足此方程組

(5) 當 a=-3 時,(x,y,z) 滿足此方程組的所有解 (x,y,z) 會在一條直線上

繼續閱讀

張貼在 隨筆雜談 | 標記 | 2 則迴響

每週問題 June 30, 2014

這是揉合特徵值、特徵向量、線性方程和正交投影的問題,取自“台聯大2014年碩士班招生考試試題 (電機類工程數學D)”的部分試題。

Let

\displaystyle  A=\left[\!\!\begin{array}{rcc}  3&3&3\\  -6&6&2\\  7&1&2  \end{array}\!\!\right]\left[\!\!\begin{array}{ccr}  3&0&0\\  0&0&0\\  0&0&-2  \end{array}\!\!\right]\left[\!\!\begin{array}{rcc}  3&3&3\\  -6&6&2\\  7&1&2  \end{array}\!\!\right]^{-1}

and \mathbf{b}=\left[\!\!\begin{array}{r}  15\\  -14\\  25  \end{array}\!\!\right].

(a) Find the general solution (also called the complete solution) of A\mathbf{x}=\mathbf{b}.
(b) Find the distance from \mathbf{b} to the row space of A.

繼續閱讀

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

共形映射

本文的閱讀等級:中級

A 為一 n\times n 階實矩陣。我們可以將 A 視為一個從幾何向量空間 \mathbb{R}^n 映至 \mathbb{R}^n 的線性變換:\mathbf{x}\mapsto A\mathbf{x},其中 \mathbf{x}\in\mathbb{R}^n。如果線性變換 A 不改變向量長度,則 A 稱為保長 (length-preserving) 映射或等距同構 (isometry)。保長映射 A 有下列等價的定義方式 (見“等距同構與么正矩陣”):

  1. A 是一正交 (orthogonal) 矩陣,即 A^TA=AA^T=I
  2. 對於每一 \mathbf{x}\in\mathbb{R}^n\Vert A\mathbf{x}\Vert=\Vert\mathbf{x}\Vert
  3. 對於任意 \mathbf{x},\mathbf{y}\in\mathbb{R}^n\Vert A\mathbf{x}-A\mathbf{y}\Vert=\Vert\mathbf{x}-\mathbf{y}\Vert
  4. 對於任意 \mathbf{x},\mathbf{y}\in\mathbb{R}^n(A\mathbf{x})^T(A\mathbf{y})=\mathbf{x}^T\mathbf{y}

保長映射的定義條件相當嚴苛,我們可以將它稍微放鬆。根據實向量的內積定義 (見“內積的定義”),

\displaystyle  \mathbf{x}^T\mathbf{y}=\Vert\mathbf{x}\Vert \Vert\mathbf{y}\Vert\cos\theta

其中 \theta 是向量 \mathbf{x}\mathbf{y} 的夾角。對於任意非零向量 \mathbf{x},\mathbf{y}\in\mathbb{R}^n,若線性變換 A 不改變 \mathbf{x}\mathbf{y} 的夾角,也就是說,

\displaystyle  \frac{(A\mathbf{x})^T(A\mathbf{y})}{\Vert A\mathbf{x}\Vert\Vert A\mathbf{y}\Vert}=\frac{\mathbf{x}^T\mathbf{y}}{\Vert \mathbf{x}\Vert\Vert \mathbf{y}\Vert}

A 稱為保角 (angle-preserving) 映射。這個定義隱含了 A 必須是一個可逆矩陣,否則存在 \mathbf{x}\neq\mathbf{0} 使得 A\mathbf{x}=\mathbf{0},如此便無從計算夾角。

繼續閱讀

張貼在 特別主題, 主題專欄 | 標記 , , , , , , | 2 則迴響