前略.
特征值与特征向量
考察 的矩阵 . 我们发现考察形如 的方程是良有教益的.
容易发现 . 这是一个形如 的方程, 在 给定时是容易求解的. 解为一个线性空间. 我们考察什么样的 才能使 成立. 也即 不可逆, . 对于每一个 , 称其为矩阵 之特征值. 对于每一个 所对应的线性空间的基底的每一个向量, 称其为矩阵 之特征向量.
对角化
对于 的矩阵 , 若 恰有 个线性无关的特征向量 (不妨称这些特征值与对应的特征向量为 .) 那么 是可对角化的. 也即存在可逆矩阵 和对角矩阵 使得 . 且 使得 , .
我们首先用 右乘等式两端. 有 . 也即 , 这是显然成立的.
例题 1.1 给定矩阵 , 主对角线上数字互不相同的上三角矩阵 , 矩阵 . 求解 , 保证若有解则解不大于 .
考察 的对角化 . 原式等价于 , 用 右乘等式两端得 , 设 , 有 . 也即对所有 求解 , 跑一遍 BSGS 即可. 时间复杂度 .
最小范数解
求 的解集中的一个解, 使得 最小.
容易发现 的解集是形如 的形式. 我断言 为最小范数解当且仅当 . 这是容易证明的: 我们考察向量空间 中的点到 的最小距离, 显然这和原问题答案等价. 而正如点到直线的范数最小的向量是垂直于那条直线的一样, 得益于高维空间内类似勾股定理的定理依然成立, 我们可以断言, 如果 为最小范数解, 那么 . 同时通过 的线性无关性和 的维度容易发现这个条件也是充分的.
高斯消元解出 后再解一遍 即可.
例题2.1 求解方程组
求出 之最小范数解 . 容易通过 构造出 的解.