求解 f(x) = 0
许多量化问题归结为求函数穿过零点的 x：给债券定价的收益率、与期权匹配的波动率、使项目价值为零的利率。f 的根就是满足 f(x) = 0 的 x。通常没有公式，所以程序要逐步逼近。两种方法几乎承担了全部工作：二分法慢但可靠；牛顿法快但需要小心。两者都把函数本身当作参数接收，这在 Python 中可行，因为函数就是值。
def bisection(f, a, b, tol=1e-10):
if f(a) * f(b) > 0:
raise ValueError("f(a) and f(b) must have opposite signs")
while b - a > tol:
mid = (a + b) / 2
if f(a) * f(mid) <= 0: # the root is in the left half
b = mid
else:
a = mid
return (a + b) / 2
root = bisection(lambda x: x * x - 2, 0, 2)
print(root) # 1.414213562355144
print(root * root) # 1.9999999999492266二分法：慢而稳
如果 f 连续，且 f(a) 与 f(b) 符号相反，两者之间就有一个根。计算中点：两个半区间中必有一个端点符号仍相反，根就被困在那里。无论 f 长什么样，每一步都把区间减半，所以 n 步后的误差是 (b - a) / 2**n，并且可以提前知道需要多少步：ceil(log2((b - a) / tol))。这种不需要导数的保证，使二分法成为安全的默认选择。
# How many halvings does a given tolerance cost? About 3.3 per decimal digit
import math
def bisection_steps(a, b, tol):
if b - a <= tol:
return 0
return math.ceil(math.log2((b - a) / tol))
for tol in (1e-2, 1e-4, 1e-8, 1e-12):
print(tol, bisection_steps(0, 2, tol)) # 1e-2: 8, 1e-4: 15, 1e-8: 28, 1e-12: 41牛顿法：沿着切线走
牛顿法用当前猜测点处的切线代替 f，并跳到这条直线穿过零点的位置：x_new = x - f(x) / df(x)。在单根附近，误差每一步大致被*平方*，正确位数翻倍：四步内从 1 位到 2、4、8、16 位。它需要导数 df（对隐含波动率就是你已有的 vega）和一个好的起点。
# Newton for sqrt(2): print every iterate and the error that remains
import math
def newton_step(f, df, x):
return x - f(x) / df(x)
f = lambda x: x * x - 2
df = lambda x: 2 * x
x = 1.0
for step in range(6):
print(step, x, abs(x - math.sqrt(2)))
x = newton_step(f, df, x)# Newton on the implied volatility of a call, using vega as the derivative
import math
def norm_cdf(x):
return 0.5 * (1 + math.erf(x / math.sqrt(2)))
def norm_pdf(x):
return math.exp(-0.5 * x * x) / math.sqrt(2 * math.pi)
def bs_call(spot, strike, rate, sigma, t):
d1 = (math.log(spot / strike) + (rate + 0.5 * sigma ** 2) * t) / (sigma * math.sqrt(t))
return spot * norm_cdf(d1) - strike * math.exp(-rate * t) * norm_cdf(d1 - sigma * math.sqrt(t))
def vega(spot, strike, rate, sigma, t):
d1 = (math.log(spot / strike) + (rate + 0.5 * sigma ** 2) * t) / (sigma * math.sqrt(t))
return spot * norm_pdf(d1) * math.sqrt(t)
market = 8.0
sigma = 0.5 # a rough start
for step in range(1, 6):
error = bs_call(100, 100, 0.05, sigma, 0.5) - market
sigma -= error / vega(100, 100, 0.05, sigma, 0.5)
print(step, round(sigma, 10))牛顿法何时失败
切线只是局部的图像。导数为零或极小时，跳跃会巨大或无定义；起点离根太远时，迭代值可能飞出去或来回循环（对 atan(x) 从 x = 2 开始，它们会无限增大）。所以稳健的求解器会保护除法、限制迭代次数，并在失败时抛出错误，而不是返回错误的数。许多库先给出括号区间，在其中使用牛顿法，一旦某一步跳出区间就退回二分法。
如何选择二分法需要括号区间，大约每三步多得一位精度，但只要符号相反就不会失败。牛顿法需要导数和一个像样的起点，精度提升爆炸式，但可能悄悄失败。在定价代码中，常见模式是：用无套利边界得到括号区间，用牛顿法精修，两者都不收敛时明确报错。
f的根是满足f(x) = 0的x；求解器把f（和df）作为函数参数接收。- 二分法：保留符号变化的那一半；
ceil(log2((b - a) / tol))步，有保证，无需导数。 - 牛顿法：
x - f(x) / df(x)；单根附近每步位数翻倍，但需要df、好的起点以及保护措施（导数为零、不收敛）。
下一节：二叉树，让股价上下跳动并倒推，为期权定价。
实验：评分内容
- 用
bisection通过对半切来夹住根25 分 - 用
bisection_steps计算对半切的次数25 分 - 用
newton_step沿切线走一步25 分 - 用
newton收敛到根25 分