Question

Root

找到确切的输入数值，让输出数值是零，称作“求根”。这样的输入，称作“根”，可能有许多个、也可能不存在。

以函数图形表达函数的根：当输入变数只有一个，是函数曲线与 X 轴的相交之处。当输入变数只有两个，是函数曲面与 XY 平面的相交之处。当输入变数有许多个，请读者自行推广。

中学数学谈过多项式函数的求根，相信大家印象深刻。比如一元二次多项式函数的求根（解一元二次多项式方程式），有个号称数学界最难背的公式：二 a 分之负 b 正负根号 b 平方减四 ac。

          _________
    -b ± V b2 - 4ac
x = ---------------
          2a

以下则是谈一般的函数的求根。多项式函数，性质优美，拥有特定公式；一般的函数，杂乱无章，没有固定公式，只好利用电脑了。最简单的求根演算法，就是穷举法：穷举各种输入，看看输出是不是零。

Root Finding: Bisection Method

用途

用来找到连续函数的根。bi-这个字首是“双”的意思，而 section 是“分段”的意思。中文译作“二分法”。

勘根定理

解释演算法之前，得先複习一下高中数学的“勘根定理”。

连续函数的图形当中，当起点与终点分别在 X 轴的两侧，那麽一定在某处穿过 X 轴。换句话说，在某处有根。换句话说，至少有一个根。

以数学符号说明勘根定理

连续函数 f(x)，任意区间[a,b]。a 和 b 分别代入 f(x)，得到 f(a) 和 f(b)。

如果 f(a) 和 f(b) 是一正一负、是异号，即 f(a) f(b) < 0，就表示座标(a, f(a)) 和座标(b, f(b)) 这两点位于 X 轴的两侧。因为 f 是连续函数，所以座标(a, f(a)) 到座标(b, f(b)) 的路线，一定碰到 X 轴至少一次──区间[a,b]裡面至少有一个根。

如果 f(a) 和 f(b) 是同号，即 f(a) f(b) > 0，就表示座标(a, f(a)) 和座标(b, f(b)) 这两点位于 X 轴的同侧──区间[a,b]裡面可能有根，也可能无根。

如果 f(a) 和 f(b) 有零，即 f(a) f(b) = 0，此时 a 和 b 就是根──区间[a,b]裡面可能还有其他根，也可能无根。

另外，当[a,b]的端点恰好没有定义在 f(x) 当中，则无法计算出 f(a) 和 f(b) 的值。要解决这个问题，可以将区间略微缩小一些，像是[a + 0.001, b - 0.001]，即可避免端点没有定义的情况。

比较差的演算法

将区间切两半，递迴缩小区间，夹挤、逼近根。

这种方式有个很大的问题：如果左右两个区间都做检查，结果就跟穷举法没两样。

二分法

不如只检查其中一个区间吧！

只检查确定有根的区间，即 f(a) 和 f(b) 异号的区间。如果左右两个区间都确定有根，那麽就只检查左边区间。一旦找到根，就马上结束递迴。

至于 f(a) 和 f(b) 同号的区间、f(a) 和 f(b) 为零的区间，就无法处理了。

这就是二分法。二分法其实也正是 Binary Search。

找到所有根

整条数线细分成许多微小区间。f(a) 和 f(b) 同号的区间，视作没有根；f(a) 和 f(b) 为零的区间，视作只有端点有根；f(a) 和 f(b) 异号的区间，视作刚好有一个根，实施二分法找到根。

只要细分的足够细腻，理论上可以找到所有根，除了一种例外：根恰好是区域极值。此时必须配合其他的求根方法，才能处理这个例外。

精确度

分割区间越多次，答案就越精确。

float、double 变数，能够储存的位数有限，不可能精确，有著一个极限。不断分割区间，就能到达极限。一个 float 变数的范围约为 10^38 到 10^-38，分割区间 log₂(10^76) ≒ 252 次，定能得到 float 变数所能储存的最精确的数值。

根据个人测试，不管迴圈计算多少遍，a b 的大小关係永远不变，而 c 永远会在[a,b]当中，不会超出范围。

迴圈不断计算之后，有些函数造成 a b 最终相等，也有些函数造成 a b 永远不相等，永远相差一个最小精确度的值。要解决不相等的问题，只需判断 c 是 a 或是 b 即可。

范例：求平方根

严格递增函数

连续函数，严格递增（减）；若有根，保证只有一个根。

Root Finding: Secant Method

割线法

一张图胜过千言万语。

一开始选定的两点，如果不够靠近根，割线可能会乱跑。

运气不好时，割线呈水平线，割线法会故障；割线趋近水平线，下一点会溢位。

Root Finding: Newton's Method

牛顿法

割线法採用割线，牛顿法採用切线。牛顿法的收敛速度比较快，但是计算时间比较多。

如果给定的函数，其导数不需要 dx，例如多项式函数，那麽我们可以预先用纸笔推导导数式子，让计算结果更精准。

凸函数

连续函数，斜率严格递增（减）；若有根，牛顿法能找到根。

以斜率的观点来看牛顿法，牛顿法不断地缩小斜率范围。

连续函数，斜率严格递增（减），正是凸（凹）函数：函数图形上面任意划一道割线，总是凸出来的函数。

Fixed Point Finding

Fixed Point

找到特定的输入数值，让输出和输入完全一样。这样的输入称作“不动点”。可能有许多个，也可能不存在。

以函数图形表达函数的不动点：当输入变数只有一个，是函数曲线与直线 y = x 的相交之处。当输入变数超过一个，此处不讨论。

求根、求不动点，本质上是同一件事情。求根变成求不动点：等号两边同时加上 x。求不动点变成求根：等号两边同时减去 x。

  f(x) = 0   <--->   f(x) + x = x   <--->   g(x) = x

数学系课程才会介绍不动点，相信大家完全没印象。然而在计算学当中，不动点拥有超高效率演算法，是一大利器。

Eigenpoint【尚无专有名词】

找到特定的输入数值，让输出是输入的倍数，倍数是某个定值。这样的输入称作“特徵点”。可能有许多个，也可能不存在。

以函数图形表达函数的特徵点：当输入变数只有一个，是函数曲线与直线 y = λx 的相交之处。当输入变数超过一个，此处不讨论。

求根、求特徵点，本质上是同一件事情。求根时，将函数乘上任意倍率，根依然相同──如此就变成了求特徵点。

  f(x) = 0   <--->   f(x) + x = x
λ f(x) = 0   <--->   λ (f(x) + x) = λx   <--->   g(x) = λx

Fixed Point Finding: Fixed Point Iteration

不动点递推法

不断代入上次求得的数值。就这麽简单。

即是在函数图形与 45°斜线之间往返。越走越小圈、越走越近。

运气不好时，无法得到不动点。

越走越大圈、越走越远。

程式码很短，只有一个迴圈。

斜率绝对值小于 1 的连续函数

遭遇不动点，其中一种情况，就是步伐越来越短。测量 X 轴方向的步伐大小，即是 x₀ x₁ x₂……之间的间距。当间距越来越小，最后 xₙ = xₙ₊₁ = f(xₙ) 就会趋近相等、就会收敛，保证遭遇不动点 xₙ。

此处只讨论这种抓抓脑袋就能想到的特例。

|x₁ - x₀| > |x₂ - x₁| > |x₃ - x₂| > ......

|x₁ - x₀| > |x₂ - x₁|   此处以开头两项为例。事实上任意相邻两项都成立。

|x₁ - x₀| > |f(x₁) - f(x₀)|

    |f(x₁) - f(x₀)|   
1 > ——————————————— = |slope|
       |x₁ - x₀|      

|slope| < 1

-1 < slope < 1

先后间距变小，移项之后，割线的斜率的绝对值小于 1。

也就是说，如果有一种连续函数，任取两点的割线的斜率的绝对值都小于 1，那麽这样的连续函数，保证有不动点。而且无论从哪裡当起点，都能找到不动点。

观察割线们当中的切线们，那麽这样的连续函数，也就是每一点的切线的斜率的绝对值都小于 1，不太斜的连续函数。

特徵点递推法

在函数图形与斜率λ的直线之间往返。上次求得的数值，除以λ之后才代入。

斜率绝对值小于|λ|的连续函数

遭遇特徵点，其中一种情况，就是步伐越来越短。中略。也就是每一点的切线的斜率的绝对值都小于|λ|的函数。

|x₁ - x₀| > |x₂ - x₁| > |x₃ - x₂| > ......

|x₁ - x₀| > |x₂ - x₁|   此处以开头两项为例。事实上任意相邻两项都成立。

|x₁ - x₀| > |f(x₁/λ) - f(x₀/λ)|   上次求得的数值，除以λ之后才代入。

|λχ₁ - λχ₀| > |f(χ₁) - f(χ₀)|     变数替换

|λ| |χ₁ - χ₀| > |f(χ₁) - f(χ₀)|

      |f(χ₁) - f(χ₀)|   
|λ| > ——————————————— = |slope|
         |χ₁ - χ₀|      

|slope| < |λ|

-|λ| < slope < |λ|               夹在±λ之间

Lipschitz Function

方才的函数条件，再添上等号，称作 Lipschitz Function。

Equation Solving

Equation

由未知数（变数）、已知数（常数）的各种运算来构成式子。两个相等的式子，就叫作“方程式”。

2x + 1 = (4x² + 3) / (x - 1)

方程二字借自中国古代数学书籍，意义相去甚远，是个不精准的翻译。按照英文字面意义来翻译，应该称作“等式”才对。

中学数学教了很多方程式的计算，例如解一元二次方程式、解联立方程式，并且搭配几何学一起讲解。大学指考前，算了千百次，应当难不倒各位。

方程式有什麽用途呢？其实就是设 x、解 x。这两件事情很难用中文讲个明白，不过只要经历许多数学题目之后，自然而然就能体会到设 x、解 x 的精神所在。

方程式重新整理成函数的模样，就能求解。

2x + 1 = (4x² + 3) / (x - 1)

等量减法公理，两边同减一样多的东西。（移项）
2x + 1 - (4x² + 3) / (x - 1) = 0

整理成函数的模样，然后求根即可！
f(x) = 2x + 1 - (4x² + 3) / (x - 1)

求根、求不动点、求特徵点、求解，本质上是同一件事情。

f(x) = 0                                  root finding
f(x) + x = x          --->  g(x) = x      fixed point finding
λf(x) + λx = λx       --->  h(x) = λx     eigenpoint finding
λf(x) + λq(x) = q(x)  --->  p(x) = q(x)   equation solving

UVa 358 10341 10428 10566 10668 11277

容易求根、求不动点、求特徵点、求解的函数类型

Increasing Function：递增函数。输入变大，输出也跟著变大的函数。适合 Bisection Method。

Convex Function：凸函数。随便划一道割线，函数曲线总是凹下去的函数。凸函数的斜率是递增函数。适合 Newton Method。

Lipschitz Function：平缓函数。随便划一道割线，斜率的绝对值小于等于一个定值，不太斜的函数。适合 Fixed Point Iteration。

Polynomial Function：多项式函数。可以手工推导公式解，也可以使用上述演算法求解。

System of Equations（Simultaneous Equations）

许多道方程式同时成立，整体称作“方程组”或者“联立方程式”。

{ 1 x + 2 y - 4 sin(z) = 1
{ 2 x - 4 y + 2 cos(z) = 2
{ 3 x + 1 y + 1 exp(z) = 3

我没有研究。