[線性代數]以SVD處理兩直線交點

自從學了線性代數以後，不光是多益成績大幅進步，食慾大增...每天我都能多吃兩碗飯，開了10年的老車油門也突然變得輕巧，更棒的是，兒子長到了180公分，腦袋也靈光許多，總之...線性代數改變了我的人生

摘自-攻殺小




這次是應用SVD處理國中經典問題：已知兩直線求交點，同樣地，不從直覺式幾何思考線路切入，使用線性代數的觀念來分析線性方程組的特徵，首先列出兩直線方程式（以general form表達）：

$$ line1 : a_{1}x+b_{1}y+c_{1}=0$$
$$ line1 : a_{2}x+b_{2}y+c_{2}=0$$

化成矩陣$Ax=0$型態：

$$\begin{bmatrix} 0\\0\end{bmatrix}=\begin{bmatrix} a_{1} & b_{1} & c_{1} \\ a_{2} & b_{2} & c_{2}\end{bmatrix} \begin{bmatrix} x \\y \\1 \end{bmatrix} = Ax$$

老套路，跟先前的以SVD處理已知兩點求直線系數 一樣手法，我們想找出$A$的零空間構成正交基，即是此問題的解（也可能沒有唯一解喔，嘿嘿），總之先來看看SVD分解吧：

$$A=UDV^{T}=\begin{bmatrix} u_{1}&u_{2} \end{bmatrix}_{2 \times 2}\begin{bmatrix} s_{1}&0&0\\0&s_{2}&0\end{bmatrix}_{2 \times 3}\begin{bmatrix} v_{1}\\v_{2}\\v_{3}\end{bmatrix}_{3 \times 3}$$

我們觀察此問題的$D$，顯然地只有$2 \times 3$，最多只有兩個不為零的對角係數，而$v_{3}$沒有放大係數可對應，顯然鐵定投射到零空間，會是解之一，再整理上式重新呈現會清楚許多：

$$A=\begin{bmatrix} u_{1}&u_{2} \end{bmatrix}\begin{bmatrix} s_{1}v_{1}\\s_{2}v_{2}\end{bmatrix}$$

最後，將$v_{3}$化為齊次座標（homogeneous coordinates）形式，也就是最後一個元素為1，才能符合問題所需的解形式

$$v_{3}=\begin{bmatrix} v_{31}\\v_{32}\\v_{33} \end{bmatrix} \Rightarrow \begin{bmatrix}x\\y\\1\end{bmatrix} = \begin{bmatrix} \frac{v_{31}}{v_{33}}\\\frac{v_{32}}{v_{33}}\\1\end{bmatrix}$$


喔！光看上面程序會發現有個可能BUG：若$v_{33}=0$不就出了問題了？除以0？X,Y為無窮大？

我們反過來推理，$v_{33}$何時會等於0？$v_{3}$向量作為零空間正交基，必定要與$ (a_{1},b_{1},c_{1}) , (a_{2},b_{2},c_{2})$ 二向量正交，也就是與此二向量內積為0，如果$a_{1}=a_{2}, b_{1}=b_{2}, c_{1} \neq c_{2} $，可能的解中，也只能讓$v_{33}=0$了，否則方程式是不可能協調

那麼$a_{1}=a_{2}, b_{1}=b_{2}, c_{1} \neq c_{2} $又何時會發生？答案就是平行線，兩條不一樣的直線斜率相同$a_{1}=a_{2}, b_{1}=b_{2}$，但截距不同$c_{1} \neq c_{2} $，在無窮遠處相交

這樣一切都說得通了👀

整理一下，實作兩直線求交點程序：

1. 兩直線以General form表達
2. 將兩直線係數整理，裝在矩陣$A$裡
3. SVD分解$A$
4. $V^{T}$的第三個向量$v_{3}$即為解向量
5. 解向量不等於交點座標，接著判定解向量第三個元素是否為0？若是，此題無解，表示是兩條平行線；若否，有解，需將解向量縮放到第三個元素為1，即為交點的齊次座標形式

最後感嘆一聲，偉哉，線代