计算机图形学基础-线性代数

基础

向量Vector

基本定义

(欧几里得)向量是一个具有大小和方向的实体。

对于零向量,有:

向量可以堆叠起来表示高维向量,通常用于描述对象的状态。假设有向量,则这几个向量堆叠起来可以表示为:

这是一个堆叠向量,而不是方向向量。

另外,向量也可以用于表示一个点、速度、力或直线/射线/线段。

表示从点开始沿向量移动个时刻后的一个点,或是表示该点和点之间的线段。

同时,若有两个点,则可以用如下公式表示两点之间任意的一个点(即线性插值):

我们用这一符号表示向量的长度(两点之间的距离):

其中,我们定义单位向量为:

基于此,我们可以通过这一公式将任意向量转换为指向该方向的单位向量:

这一过程被称为向量的标准化。其中,表示向量的标准化形式。

在剩余内容中,为方便表示,当等式中仅存在向量时,将直接以字母本身来表示向量,去除字母上的箭头。

向量的范数

对于任意向量,其向量**范数(norm)**代表了它在某种意义下的长度。举个例子,向量的欧几里得长度即为向量的二阶范数(欧几里得范数):

通常情况下我们会省略二阶范数的下标2。

向量的阶范数可以表示为:

点乘

对于两个向量的点乘(内积),我们可以将其记作:

其中,是两向量的夹角。同时,向量的点乘也可以表示为

向量的点乘遵循交换律和结合律,即:

一个向量点乘它自己可以得到其二阶范数的平方,即:

向量在向量上的投影长度也可以表示为点乘:

我们可以使用一个平面的法向量与点的点乘来判断该点与平面的位置关系。假设法向量与平面的交点为,则有:

叉乘

叉乘的结果是一个与原向量分别正交(垂直)的向量:

这个向量满足:

同时,叉乘向量的值可以表示为:

向量的叉乘不满足交换律,但满足结合律:

对于任意三角形,我们可以使用叉乘求其法线及面积:

叉乘也用于判断二维平面中一个点是否在三角形内。假设目前要判断点和三角形的关系,则有:

若对于按顺序的任意,计算该等式的符号均一致,则该点在三角形内部,否则在三角形外部。

通过任意一点与三角形三边的叉积,将三角形面积分为三份,可以得到三角形的重心坐标系。设平面三角形面积为,则有:

即为重心坐标系的系数。

叉乘也用于计算四面体。设有四面体,其上有四个相邻顶点,则四面体的面积可以表示为:

通过四面体体积公式,也可以得到体积化的重心坐标系。同时,当点与三角面构成的四面体体积为0时,点在三角形面上。

矩阵Matrix

基本定义

一个实数矩阵指一系列以行排列的元素。

定义如下矩阵,分别为转置矩阵(Transpose)、对角矩阵(Diagonal)和单位矩阵(Identity)。

对于对称矩阵,有

矩阵不满足交换律,但满足结合律:

对于转置矩阵,有:

对于一个矩阵,我们称A^{-1}A$
不是所有的矩阵都有逆矩阵。

正交矩阵

我们可以用多个向量组合,来形成矩阵。

若这些向量分别垂直,且这些向量都是单位向量,则称为正交矩阵。有:

对于正交矩阵,其本身与其转置相乘,有:

正交矩阵可以用于表示旋转。对于物体原本的坐标轴,使用正交矩阵与其相乘,可得:

物体旋转后的新坐标轴为。同理,我们用对角矩阵来表示物体的缩放。

奇异值分解与特征值分解

假设有任意矩阵,其可以被分解为,其中是正交矩阵,是对角矩阵。其中,的元素值即为矩阵的奇异值。易知,任意矩阵的线性变换都能通过旋转-缩放-旋转来表示。(因为物体只能向坐标轴方向缩放,因此要先将物体旋转至缩放方向)

假设有对称矩阵,其可以被分解为,其中是对角矩阵,是正交矩阵。其中,的元素值被称为的特征值。

正定矩阵

我们将一个矩阵称之为正定矩阵(s.p.d),当且仅当

我们将一个矩阵称为半正定矩阵,当且仅当

推论:对称矩阵如果特征值均为正数,那么这个对称矩阵一定是正定矩阵。

推论2:每一行对角线上的值大于其他值之和的矩阵对角占优,对角占优的矩阵一定正定。

线性系统和线性问题

线性问题

任何线性问题,都可以被写作这一形式:

其中是一个矩阵,是一个矢量。

最容易想到的方法是在等式两边同时乘以矩阵的逆矩阵,以此来解决问题。然后,在实际应用时,矩阵的逆十分难以计算,对稀疏矩阵求逆矩阵也并不方便。因此通常来说,我们会使用其他方法来解出这一线性问题,这一过程就是求解线性系统

直接方法

直接方法通过对矩阵进行分解来求出答案,常见的变种有:Cholesky,LDLT等等,这些方法通常在内存占用上有所不同。朴素的会方法将矩阵分解为上三角矩阵与下三角矩阵:

在进行分解后就可以很方便地解线性系统。例如,我们将分解为后,先解决:

此时,由于是下三角矩阵,因此我们可以很容易地得到:

随后,我们再以同样的方式解出:

合并两个式子,此时得到的即为原线性系统的解。在这一方法中,如果是一个稀疏矩阵,则的稀疏性将会较差。此时,的稀疏性和原矩阵的数值排列方式有关,因此我们会先常常用一定方法修改原矩阵的排列顺序,然后再求解线性系统。

迭代法

迭代法通常是这样的一种形式:

随迭代次数增加,将逐渐收敛至正确的数值解。通常,有多种选取的方法,例如Jacobi方法和Gauss-Seidel方法。同时,在这一过程中,我们会使用切比雪夫加速、梯度共轭等额外方法进行加速。

迭代法 的好处是十分容易实现,而且其数值解的求解速度较快,其过程也可以并行。然而,迭代法的收敛性较难确定,且精确解的求解十分缓慢。

微积分

一阶导数

如果是一个实数域的函数,其一阶导数可以写作:

即,对矢量求导相当于对其各个标量分别求导。有时,我们会使用转置后的一阶导数,即梯度(gradient):

梯度的含义即为函数上升的最快方向。

对于矩阵求导,例如:

则有Jacobian矩阵:

其中,我们将矩阵对角线之和称作求导的散度(Divergence):

同时,我们将得到一个矩阵的旋度(Curl):

二阶导数

进行二阶求导,可以得到如下Hessian矩阵:

Hessian矩阵的对角被称为Laplacian:

我们学过常数形式的泰勒展开,对于,有:

对于,则有:

其中,可以发现可能存在的正定矩阵:

同时,向量大小的梯度为: