之前提到，求解线性方程组 \(A x = b\) 等价于求下面二次型的极小值 \[f(x) = \frac 1 2 x^T A x - x^T b\] 在最速下降算法中，迭代点沿负梯度方向移动，这就导致迭代点走位太罗嗦，具体来说，若函数的等高线是很狭窄的椭圆，如果初始点取得不好，那么将会产生如下图所示低效的迭代路径 仅仅是二阶矩阵就需要如此多的迭代显然是不可接受的，那么是否有使用极少迭代次数便成功收敛的算法呢？答案是显然的，在上一节讨论最速下降算法的时候，我们谈到了一种特殊情况，即迭代点刚好落在椭圆的轴上，便只用执行一次迭代。所以现在的想法是能不能将初始点经过一次迭代就移动到椭圆的轴上，类似于下图 虽说这是很理想的方案，但此时迭代步长和方向都是未知的，我们可以先分别假设...

算法推导 已知待求解的线性方程组 \[A x = b\] 其中 A 为对称正定矩阵，x 为向量。上述问题等价于求解如下二次型的极小值 \[f(x) = \frac 1 2 x^T A x - x^T b\] 为了说明这种关系，考虑对 \(f(x)\) 求导 \[f'(x) = \frac 1 2 A x + \frac 1 2 x^T A - b\] 由于 A 为对称正定矩阵，所以 \[f'(x) = A x - b\] 而 \(f(x)\) 取得极小值的条件是 \(f'(x) = 0\)，即 \(A x - b =0\)，这就说明两个问题其实是等价的。事实上，若 A 为二阶矩阵，那么 \(f(x)\) 的图像是空间上的抛物面，且开口向上 而其等高线则如下图所示...

之前在SICP上看到一个很厉害的东西，考虑三个问题： 计算从 a 到 b 间所有整数的和 计算从 a 到 b 间所有整数的三次方之和 求解序列 \(\frac{1}{1 \cdot 3} + \frac{1}{5 \cdot 7} + \frac{1}{9 \cdot 11} + ....\) 下面的三段代码可以分别解决这三个问题 (define (sum-integers a b) (cond ((> a b) 0) (else (+ a (sum-integers (+ a 1) b))))) (define (sum-cubes a b) (define (cube k) (* k k k)) (cond ((&g...

不知道是不是我一开始想多了，在做本科毕业论文的时候，为了更方便地运行程序，绞尽脑汁写了一个命令行解析器。而后又经过几次迭代，感觉成熟了不少，但是回过头发现好像并用不着这样的解析器。。。当然主体程序跟现在要讨论的内容不相关就不说了，只是花了精力实现的东西还是希望记录下思路。 行为树的原理，简单来说，系统的状态从根节点出发，接收外部信息，每接受一个信息，就按照预定义的跳转表进行状态跳转。当所有信息都处理完之后，最终停留的那个状态一般都有个动作，运行之后便完成了对程序的控制。 所以实际上要完成两个阶段的任务，首先是利用待实现的命令行语句构建一颗行为树，语句里的每个单词都是一个状态跳转指示。然后实现一个语句解析器，负责读取语句，并进行相应的状态跳转。 构造行为树 预定义一颗行为树的方法...

哈希表是一种常用而强大的数据结构，有鉴于此，许多语言都自带其实现，这就为我们这些使用者带来了很多方便。在Java中，HashMap是使用率最高的哈希表，本文将对其源码进行详细的解读。 HashMap是一个比较大的类，有两千多行代码，继承了一个类，实现了三个接口，以及大量的方法。如果上来就一行一行的读，那么将很快就陷入泥潭，无法自拔。所以我决定在看源码的同时，写一个简化版本的哈希表，一开始只关注哈希表本身，然后再逐步添加实际应用层面的功能（比如，我将先不考虑HashMap中的最大容量、序列化等等与哈希表结构无关的内容）。然后我想说下，我发现在IDEA中类名使用小写首字母并不会弹出警告，所以我决定在不造成困扰的情况下不遵从Java常用的驼峰命名规则，比如接下来我要实现的简化哈希表就叫has...