牛顿法用切线代替曲线：在当前点画一条切线，交横轴的地方就是下一个猜测。 它每轮把正确答案的位数翻倍——六轮就把误差压到 2.22e-16。 高斯消元两步：先把左下角消成 0，再从最后一行往回代。
前两章都是「在一堆数据里找一个」，这一章换个题：求一个满足条件的数。 解方程没有「试完所有可能」的路子，只能一点点逼近——这叫数值方法。 这一篇的两个算法各代表一种思路：牛顿法是迭代逼近，高斯消元是化繁为简。
一、牛顿法：用切线一点点逼近
要求「x 的平方等于 2」，也就是解 x*x - 2 = 0。这个方程没有漂亮的整数解。
牛顿法的做法：随便猜一个数，然后不断用切线修正它。
具体说：在当前这一点给曲线画一条切线，看切线和横轴交在哪儿，那个交点就是下一轮的猜测值。
为什么用切线？
因为切线是直线，直线好算。曲线难解，但它的切线在附近和它很像——用近似值去换「能算」。
演示里从 1 起步，六轮收敛到 1.4142135624。真值 sqrt(2) 也是这个数，六轮之后误差 2.22e-16。
这个精度意味着什么？
双精度浮点数一共才 16 位左右有效数字，所以这已经是这台机器能给的最准答案了。
二、误差每轮砍一大截：二次收敛
演示里那张表的前两列最有说服力：x 是 1、1.5、1.4167、1.41422，代入值（也就是误差的量级）是 -1、 0.25、0.0069、0.0000060。 每一轮的误差差不多是上一轮误差的平方。0.25 的平方是 0.06，实际到 0.0069，量级对得上； 再平方就是 5e-5，实际 6e-6。 这种速度叫二次收敛。它比「每轮砍一半」快得多：砍一半要三十轮才到 1e-9，位数翻倍五轮就到了。
所以牛顿法在数值计算里非常受宠：只要它收敛，就是几轮的事。 注意「只要它收敛」这五个字。下一段说的是它什么时候不收敛。
三、牛顿法的条件：能求导，起点别太远
演示末尾那两行提醒是这一节的关键：牛顿法要求函数能求导，还得从「离答案不太远」的地方起步。 为什么要求导？因为切线的斜率就是导数。不会求导就画不出切线，方法没法启动。 为什么起点要近？因为切线只在「附近」和曲线像。 离得远的时候，切线和曲线根本不是一个方向，交点可能跑到更远的地方去。
演示里那句原话很实在：起点选在拐弯处，可能越算越远——它快，但不保证一定收敛。 这是数值方法共同的毛病： 给你一个「通常很好用」的办法，而不是一个「永远保证对」的办法。 工程上靠的是「跑完检查一下结果像不像」。
四、高斯消元：解三个未知数
换一个题：三个方程三个未知数。手算的做法是「消元」——用一个方程把另一个方程里的 x 消掉。 高斯消元把这个动作系统化：一列一列地消，把左下角全部变成 0。 演示里原始方程组是三行四列（三个系数加一个右边的值）。 消元之后左下角全是 0，形状变成一个「三角形」。
为什么变成三角形就好解？因为最后一行只剩一个未知数——直接算出来。 然后往上代：知道 z 了，倒数第二行只剩 y 和 z，y 也就出来了。这叫回代。 演示里解出 x = 2、y = 3、z = -1。 手算三元就是这一套，电脑算三百元也是同一套，只是循环多跑几万次。
五、选主元：先换行，再消元
演示里有一句话容易漏过去：消元后的第一行不是原来那行。 原来的第一行第一个系数是 2，但程序把绝对值最大的 -3 那一行换到了最上面。这个动作叫选主元。 为什么必须换？两个理由。第一，如果主元是 0，下一步要除以它，直接除零崩掉。
第二，就算主元不是 0 但很小，除以它会放大误差。 除以 0.0001 等于乘一万，原来那点舍入误差也被放大一万倍。 所以「把绝对值最大的换到当前行」既是防崩，也是防误差。 这一行代码不写，很多方程组算出来的答案会莫名其妙地不准。
六、两个算法，两种思路
牛顿法是迭代：从一个猜测出发，每轮改一点，越来越接近答案。 高斯消元是变换：不改答案，只改方程组的写法，把它换成一眼能解的形状。 这两种思路覆盖了数值计算的大半：要么一点点逼近，要么换个形式让它变简单。
它们还有个共同点：都是「有限步内做完」，但结果可能是近似值。这和第 1 章说的「算法要有穷、
要能验证」对得上——验证的办法就是代回去看等号成不成立。
这一条很实用：牛顿法算出的 1.4142135624 代回 x*x 得 2.0000000000000004，
差一点点，但这点差在浮点数里已经是最好了。
七、动手 Demo：牛顿法求根号 2，高斯消元解三个未知数
先用牛顿法解 x*x - 2 = 0，把每一轮的 x、代入值和误差都打出来。
再解一个三元一次方程组：先选主元消元，把左下角消成 0，再回代。
def f(x):
return x * x - 2
def df(x):
return 2 * x
x = 1.0
for i in range(6):
nxt = x - f(x) / df(x)
print(i, '%.10f' % x, '%.10f' % f(x), '%.10f' % nxt)
x = nxt
import math
print('误差', abs(x - math.sqrt(2)))
M = [[2.0, 1.0, -1.0, 8.0],
[-3.0, -1.0, 2.0, -11.0],
[-2.0, 1.0, 2.0, -3.0]]
for col in range(3):
piv = max(range(col, 3), key=lambda r: abs(M[r][col]))
M[col], M[piv] = M[piv], M[col]
for r in range(col + 1, 3):
k = M[r][col] / M[col][col]
for c in range(col, 4):
M[r][c] -= k * M[col][c]
for row in M:
print(' '.join('%8.3f' % v for v in row))
s = [0.0] * 3
for i in (2, 1, 0):
s[i] = (M[i][3] - sum(M[i][j] * s[j] for j in range(i + 1, 3))) / M[i][i]
print('解', s)
实跑输出：
--------------------------------------------------------------------
牛顿法与高斯消元
--------------------------------------------------------------------
① 牛顿法：用切线一点点逼近
--------------------------------------------------------------------
求 x 的平方等于 2，也就是 x*x - 2 = 0
| 第几轮 | 当前 x | 代入的值 | 下一轮的 x |
|---:|---:|---:|---:|
| 0 | 1.0000000000 | -1.0000000000 | 1.5000000000 |
| 1 | 1.5000000000 | 0.2500000000 | 1.4166666667 |
| 2 | 1.4166666667 | 0.0069444444 | 1.4142156863 |
| 3 | 1.4142156863 | 0.0000060073 | 1.4142135624 |
| 4 | 1.4142135624 | 0.0000000000 | 1.4142135624 |
| 5 | 1.4142135624 | 0.0000000000 | 1.4142135624 |
真值 sqrt(2) = 1.4142135624
六轮之后误差：2.22e-16
每一轮都在当前这一点画一条切线，切线与横轴的交点就是下一个 x。切线比曲线好算，所以用它代替。
注意收敛得多快：误差从 1 掉到 1e-2，再掉到 1e-4、1e-8——每轮大约把位数翻倍。
这叫二次收敛，是牛顿法值钱的地方。
! 牛顿法要求函数能求导，还得从「离答案不太远」的地方起步。
起点选在拐弯处，可能越算越远——它快，但不保证一定收敛。
② 高斯消元：解三个未知数
--------------------------------------------------------------------
原方程组（每行四个数：x、y、z 的系数和右边的值）：
2.000 1.000 -1.000 8.000
-3.000 -1.000 2.000 -11.000
-2.000 1.000 2.000 -3.000
消元之后（左下角全是 0）：
-3.000 -1.000 2.000 -11.000
0.000 1.667 0.667 4.333
0.000 0.000 0.200 -0.200
第一行不是原来那行——选主元时把绝对值最大的 -3 那行换到了最上面，免得一开始就除以一个很小的数。
从最后一行往回代：x = 2，y = 3，z = -1
两步：先一列一列把左下角消成 0（消元），再从最后一行往上一行行解出来（回代）。
手算三元就是这一套，电脑算三百元也是同一套。
上面那个「把绝对值最大的行换到当前行」叫选主元。不做这一步，遇到主元是 0 就会除零；
做了这一步，数值误差也小得多。
①牛顿法那一行 x - f(x)/df(x) 就是「画切线、求交点」的公式。
它没有魔法，只是把几何动作写成了算术。
②第二轮起 x 就接近 1.41 了，第三轮已经 1.4142。位数一轮一轮翻倍，这就是二次收敛。
③消元那段 piv = max(..., key=lambda r: abs(...)) 就是选主元：在剩下的行里挑绝对值最大的。
④消元后打印的三行左下角全是 0.000，形状是三角形。回代从 i = 2 开始往上走。
⑤' '.join('%8.3f' % v ...) 是为了对齐输出。
直接打印 Python 的列表会带引号和方括号，看不出三角形的形状。
30 秒实验
- 把牛顿法的起点从 1.0 改成 100.0，看要几轮收敛。
- 把起点改成 0.0，会怎样？（
df(0)是 0，会除零） - 把消元那段里的选主元整行删掉，看解出来的答案还对不对。
常见误区
- 「牛顿法一定能算出答案。」它要求能求导、起点别太远。起点糟糕时会越算越远。
- 「误差 2.22e-16 说明算错了。」那已经是双精度浮点的极限精度，再准不了。
- 「选主元只是为了防除零。」也为了防误差放大——除以一个很小的数会放大舍入误差。
自测三问（点开对答案）
1. 牛顿法每一轮在做什么？ —— 在当前点画切线，求切线与横轴的交点，把它当作下一个猜测值。 2. 为什么叫二次收敛？ —— 每轮误差大约变成上一轮的平方，位数翻倍。比「砍一半」快得多。 3. 高斯消元的两步是什么？ —— 先选主元、一列一列把左下角消成 0；再从最后一行往上回代。解方程要「逼近」。那算面积呢？下一节把面积切成条，一个一个加起来——顺带讲一个特别聪明的筛法。
- ☐ （本篇完，下一篇 7.2 梯形法与埃氏筛）