钟鼓楼

一、有序和单调

二分本质上是一种更加智能的搜索状态空间的方式，他需要状态空间的状态呈现一种“有序的一维数组”的形式，然后再进行搜索。所以一开始的排序是无法避免的。

因为二分的写法问题，所以应当怎样排序也是有一定讲究的，所以排序的时候就可以定义一定的比较方式。

如果更加细致的讨论的话，其实有序只是一个“小条件”，比如说很多枚举、搜索类的题目的状态空间也是有序的，但是我们却没有用二分法，这是因为其核心是，适用于二分法的题目，它的状态和解之间的关系是单调的，如下所示

一、内积的形式

向量 $X$ 与向量 $Y$ 的内积为

$$X^TY$$

这个时候我们熟悉的转置（准确说是熟悉由陌生，因为转置的意义并不好理解）就出现了。

如果 $X, Y$ 仅仅是坐标，需要在基 $A$ 的作用下发挥作用，那么写出来的效果就更神奇了

$$(AX)^T(AY) = X^TA^TAY$$

也就是说，此时出现了我们最为熟悉的 $A^TA$ 结构。

一、最小二乘法

1.1 总论

最小二乘法的命名来自于对于拟合的评价指标，采用最小二乘法估计的方式，也就是如下所示

$$E = \sum^n (\hat y_i - y_i)^2$$

我们希望让 $E$ 达到最小，其中 $\hat y_i$ 是第 $i$ 个预测值，$y_i$ 是第 $i$ 个实际值 。

而之所以“最小二乘法”被提炼成一种方法，是因为 $E$ 的形式恰好可以表示成一种更加“线性代数的形式”，即

一、线性规划（LP）

1.1 标准型

线性规划可以转化成标准型，但是可以发现有两种标准型，分别对应软件程序和数学形式，如下所示：

LP 求解器一般接口

一、定义

$k$ 阶、齐次、常系数、差分方程

$$y_{n + k} + a_{k - 1}y_{n + k - 1} + a_{k - 2}y_{n + k - 2} + \dots + a_0y_{n} = 0$$

$k$ 阶、非齐次、常系数、差分方程

$$y_{n + k} + a_{k - 1}y_{n + k - 1} + a_{k - 2}y_{n + k - 2} + \dots + a_0y_{n} = f(n)$$

$k$ 阶、齐次、常系数、差分方程的特征方程

$$\lambda_{n + k} + a_{k - 1}\lambda_{n + k - 1} + a_{k - 2}\lambda_{n + k - 2} + \dots + a_0\lambda_{n} = 0$$

---

一、例子

之后的所有讲解，都是基于这个例子的，所以在头部统一列出

假定某消费者购房需要贷款 30 万元，期限为 30 年，已知贷款年利率为 5.1%，问每月应还款多少？

符号约定如下