poly 教程

本教程在某点处对 luna-poly 多项式求导。你将得到稠密和稀疏多项式的值与斜率，在更大的被求导表达式中使用多项式，并对多项式运行牛顿法。相关数学见 poly 设计。

快速上手

moon add Luna-Flow/autodiff@0.2.0
moon add Luna-Flow/luna-poly

import {
  "Luna-Flow/autodiff",
  "Luna-Flow/autodiff/poly",
  "Luna-Flow/luna-poly/immut/dense",
}

fn main {
  // p(x) = 1 + 2x + x^2, coefficients from degree 0 upwards
  let p = @dense.DensePolynomial::from_coefficients([1.0, 2.0, 1.0])
  let (value, slope) = @poly.dense_value_and_derivative_at(p, 3.0)
  println("p(3) = \{value}, p'(3) = \{slope}")
}

p(3) = 16, p'(3) = 8

日常任务

列出导数值表

fn main {
  // p(x) = x^3 - 3x
  let p = @dense.DensePolynomial::from_coefficients([0.0, -3.0, 0.0, 1.0])
  for x in [-2.0, -1.0, 0.0, 1.0, 2.0] {
    println("p'(\{x}) = \{@poly.dense_derivative_at(p, x)}")
  }
}

p'(-2) = 9
p'(-1) = 0
p'(0) = -3
p'(1) = 0
p'(2) = 9

导数 $3x^2 - 3$ 在临界点 $\pm 1$ 处为零。

整数多项式的精确导数

只需要 Semiring，因此整数系数会得到精确结果：

fn main {
  // p(x) = 7 + 5x^4
  let p : @dense.DensePolynomial[Int] = @dense.DensePolynomial::from_coefficients([
    7, 0, 0, 0, 5,
  ])
  let (value, slope) = @poly.dense_value_and_derivative_at(p, 3)
  println("p(3) = \{value}, p'(3) = \{slope}")
}

p(3) = 412, p'(3) = 540

间隔很大的稀疏多项式

对于项数很少而次数很高的多项式，请使用稀疏表示；每一项的代价为 $O(\log e)$ ：

fn main {
  // p(x) = x^100 + 2x
  let p = @sparse.SparsePolynomial::from_array([([100U], 1.0), ([1U], 2.0)])
  let (value, slope) = @poly.sparse_univariate_value_and_derivative_at(p, 1.0)
  println("p(1) = \{value}, p'(1) = \{slope}")
}

p(1) = 3, p'(1) = 102

在更大的表达式中使用多项式

eval_dual 接受对偶数输入，因此链式法则会贯穿它继续传播。这里计算 $\frac{d}{dx}\,p(\sin x)$ 在 $x = 0.5$ 处的值：

fn main {
  let p = @dense.DensePolynomial::from_coefficients([0.0, 0.0, 1.0]) // s^2
  let d = @autodiff.diff(x => @poly.eval_dual(p, x.sin()), 0.5)
  println("d/dx sin(x)^2 = \{d}")
  println("sin(2x)       = \{@math.sin(1.0)}")
}

d/dx sin(x)^2 = 0.8414709848078965
sin(2x)       = 0.8414709848078965

对多项式运行牛顿法

fn main {
  // p(x) = x^2 - 2
  let p = @dense.DensePolynomial::from_coefficients([-2.0, 0.0, 1.0])
  let mut x = 1.0
  for _ in 0..<6 {
    let (v, d) = @poly.dense_value_and_derivative_at(p, x)
    x = x - v / d
  }
  println("sqrt(2) = \{x}")
}

sqrt(2) = 1.414213562373095

深入学习

与形式导数的一致性

luna-poly 也能构建导数多项式。两种途径给出相同的数值；在对偶数上求值则无需第二个多项式：

fn main {
  let p = @dense.DensePolynomial::from_coefficients([5.0, -1.0, 0.0, 3.0])
  let formal = p.derivative().eval(2.0)
  let dual = @poly.dense_derivative_at(p, 2.0)
  println("formal \{formal}, dual \{dual}")
}

formal 35, dual 35

多元多项式

稀疏桥接是一元的。要对上下文多项式关于某一个变量求导，请先用 luna-poly/immut/context 中的 ContextPolynomial::eval_partial 对其他变量求值，把剩余各项转换为关于该变量的稀疏多项式，再调用 sparse_univariate_value_and_derivative_at。本仓库的集成测试 src/tests/linalg_poly_test.mbt 展示了完整的转换过程。

常见陷阱

系数顺序。 DensePolynomial::from_coefficients 从常数项开始依次接受 $c_0, c_1, \dots$ 。
出现第二个变量会中止。 sparse_univariate_* 只用一个值求值；含有其他变量的项会使程序终止。
旧名称。 derivative_at 和 sparse_derivative_at 是 dense_ 和 sparse_univariate_ 函数的别名，而不是多元版本。
浮点抵消。 在重根附近， $p'(x)$ 是大项之间的微小差值；见 poly 设计中的误差界。

后续阅读

poly API 列出了每个函数及其别名。
poly 设计推导了对偶数上的 Horner 法则及其误差界。
luna-poly 记录了多项式类型。