xsf/scipy_special/orthogonal_roots.rs
1//! Translated from `scipy/special/_orthogonal.py` (scipy/scipy@7d279ba)
2//!
3//! - <https://github.com/scipy/scipy/blob/7d279ba/scipy/special/_orthogonal.py>
4//!
5//! The nodes are in ascending order, and the weights sum to the integral of the weight function.
6
7use core::f64::consts::{LN_2, PI, SQRT_2};
8
9use super::orthogonal_eval::{
10 eval_gegenbauer, eval_genlaguerre, eval_hermite_h, eval_hermite_he, eval_jacobi, eval_legendre,
11};
12use crate::ext::ln_gamma;
13use crate::ext::tridiag::eigvals;
14use crate::utils::{SQRT_PI, SQRT_TAU_DOWN};
15use crate::xsf::cephes::consts::MAXLOG;
16use crate::xsf::cephes::dd_real::{DoubleDouble as Dd, LOG2, ldexp_f64, two_sum};
17use crate::xsf::cephes::incbet_lnpow;
18use Nodes::{Plain, Shifted, Symmetric};
19
20/// Corresponds to `_gen_roots_and_weights`: Gauss quadrature by the Golub-Welsch algorithm
21///
22/// The monic orthogonal polynomials satisfy `p_{k+1}(x) = (x - a_k) p_k(x) - b_k^2 p_{k-1}(x)`,
23/// so the roots of `f(n, x)` are the eigenvalues of the tridiagonal matrix with diagonal `a_k` and
24/// off-diagonal `b_k`. They are refined by a Newton step with the derivative `df(n, x)`.
25///
26/// The weights sum to `mu0`, and are proportional to `1 / (sigma(x) df(n, x)^2)` at the roots,
27/// where `sigma f'' + tau f' + lambda f = 0` (DLMF Table 18.8.1). For a root `x + dx` with the
28/// rounding error `dx`, `sigma(x, dx)` is `sigma(x + dx)`, and `df(n, x + dx)` is
29/// `df(n, x) (1 - tau(x) dx / sigma)` to first order, since `f(n, x + dx) = 0`.
30fn gen_roots_and_weights(
31 n: usize,
32 mu0: f64,
33 an: impl Fn(f64) -> f64,
34 bn: impl Fn(f64) -> f64,
35 f: impl Fn(i32, f64) -> f64,
36 df: impl Fn(i32, f64) -> f64,
37 sigma: impl Fn(f64, f64) -> f64,
38 tau: impl Fn(f64) -> f64,
39 nodes: Nodes,
40) -> (Vec<f64>, Vec<f64>) {
41 let d: Vec<f64> = (0..n).map(|k| an(k as f64)).collect();
42 let e: Vec<f64> = (1..n).map(|k| bn(k as f64)).collect();
43 let mut x = eigvals(&d, &e);
44
45 // improve roots by Newton's method
46 //
47 // Unlike in SciPy, which takes one step, at most 4 steps are taken while
48 // `step^2 > eps sigma^2`, i.e. while the error of a step, about `step^2 / sigma`, matters for
49 // `sigma` and thus for the weights. This only happens for a root very close to an endpoint (a
50 // zero of `sigma`), e.g. within 1e-14 of -1 for alpha and beta near -1.
51 //
52 // Unlike in SciPy, a root and its weight where the polynomials overflow (e.g. `L_n` for
53 // n >= 400) are the eigenvalue and 0, instead of NaN for all.
54 let n = i32::try_from(n).expect("n is too large");
55 // the rounding errors of the refined roots
56 let mut dx = vec![0.0; x.len()];
57 for (xi, dxi) in x.iter_mut().zip(&mut dx) {
58 for _ in 0..4 {
59 let step = f(n, *xi) / df(n, *xi);
60 if !step.is_finite() {
61 break;
62 }
63 (*xi, *dxi) = two_sum(*xi, -step);
64 let s = sigma(*xi, *dxi);
65 if step * step <= f64::EPSILON * s * s {
66 break;
67 }
68 }
69 }
70
71 // Unlike in SciPy, the weights are computed from `df` at the refined roots, instead of
72 // `1 / (f(n - 1, x) df(n, x))` with `df` at the eigenvalues, which is more sensitive to the
73 // rounding of `x` (about n^2 times near x = +-1).
74 //
75 // They are `mu0 / sum(1 / r^2) / r^2`, with `r = sqrt(sigma) df` scaled to `r >= 1`, so that
76 // only the weights that are tiny relative to `mu0 / n` underflow. A non-finite `r` is an
77 // overflow, with weight 0.
78 let r: Vec<f64> = x
79 .iter()
80 .zip(&dx)
81 .map(|(&xi, &dxi)| {
82 let s = sigma(xi, dxi);
83 s.sqrt() * df(n, xi) * (1.0 - tau(xi) * dxi / s)
84 })
85 .collect();
86 // A zero `r` is an underflow, with weight NaN, and the others 0 (relatively tiny), instead of
87 // NaN for all.
88 let r_min = r
89 .iter()
90 .map(|ri| ri.abs())
91 .filter(|&ri| ri > 0.0)
92 .fold(f64::INFINITY, f64::min);
93 let r: Vec<f64> = r
94 .iter()
95 .map(|&ri| {
96 if ri.is_finite() {
97 ri / r_min
98 } else {
99 f64::INFINITY
100 }
101 })
102 .collect();
103 let scale = mu0 / r.iter().map(|ri| 1.0 / (ri * ri)).sum::<f64>();
104 let mut w: Vec<f64> = r.iter().map(|ri| scale / ri / ri).collect();
105
106 match nodes {
107 Plain => {},
108 Symmetric => {
109 w = w
110 .iter()
111 .zip(w.iter().rev())
112 .map(|(a, b)| (a + b) / 2.0)
113 .collect();
114 x = x
115 .iter()
116 .zip(x.iter().rev())
117 .map(|(a, b)| (a - b) / 2.0)
118 .collect();
119 },
120 Shifted => {
121 x = x
122 .iter()
123 .zip(&dx)
124 .map(|(xi, dxi)| ((xi + 1.0) + dxi) / 2.0)
125 .collect();
126 },
127 }
128 (x, w)
129}
130
131/// What [`gen_roots_and_weights`] does with the roots
132#[derive(Clone, Copy)]
133enum Nodes {
134 Plain,
135 /// Makes the roots antisymmetric and the weights symmetric
136 Symmetric,
137 /// Shifts the roots `x` to `[0, 1]` as `(x + 1) / 2`, but with their rounding errors, so that
138 /// the ones near 0 have a small relative error
139 Shifted,
140}
141
142/// The rule for `f(x / s)` from the one for `f(x)`
143fn scale((x, w): (Vec<f64>, Vec<f64>), s: f64) -> (Vec<f64>, Vec<f64>) {
144 let x = x.into_iter().map(|xi| xi * s).collect();
145 let w = w.into_iter().map(|wi| wi * s).collect();
146 (x, w)
147}
148
149/// `(m, e)` with `m 2^e = exp(l)`, and `e >= 0` only as large as needed for a finite `m`
150fn exp_scaled(l: Dd) -> (f64, f64) {
151 let e = ((l.hi - MAXLOG) / LN_2).ceil().max(0.0);
152 let r = l - LOG2 * e;
153 (r.hi.exp() * (1.0 + r.lo), e)
154}
155
156/// The rule with the weights multiplied by `2^e`, for weights computed with `mu0 / 2^e`
157fn ldexp_weights((x, w): (Vec<f64>, Vec<f64>), e: f64) -> (Vec<f64>, Vec<f64>) {
158 (x, w.into_iter().map(|wi| ldexp_f64(wi, e as i32)).collect())
159}
160
161/// `1 - (x + dx)^2` for `|dx| <= ulp(x)`, with a small relative error near `x + dx = +-1`
162fn one_minus_x2(x: f64, dx: f64) -> f64 {
163 ((1.0 - x) - dx) * ((1.0 + x) + dx)
164}
165
166/// Panics if `n` is zero, like the `ValueError` in SciPy
167fn check_n(n: usize) {
168 assert!(n >= 1, "n must be a positive integer");
169}
170
171/// Gauss-Jacobi quadrature
172///
173/// Corresponds to [`scipy.special.roots_jacobi`][docs].
174///
175/// [docs]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.roots_jacobi.html
176///
177/// The nodes are the roots of the Jacobi polynomial $P_n^{(\alpha,\beta)}$, and the rule is exact
178/// for polynomials of degree $2n - 1$ with the weight function $(1 - x)^\alpha (1 + x)^\beta$ on
179/// $[-1, 1]$ (A&S 22.2.1).
180///
181/// # Panics
182/// - if `n` is zero
183/// - if $\alpha \le -1$ or $\beta \le -1$
184///
185/// # See also
186/// - [`eval_jacobi`]: Evaluate Jacobi polynomials, $P_n^{(\alpha,\beta)}$
187#[must_use]
188pub fn roots_jacobi(n: usize, alpha: f64, beta: f64) -> (Vec<f64>, Vec<f64>) {
189 check_jacobi(n, alpha, beta);
190 if alpha == 0.0 && beta == 0.0 {
191 return roots_legendre(n);
192 }
193 // Unlike in SciPy, the rule for alpha == beta < -1/2 isn't the Gauss-Gegenbauer one, which is
194 // less accurate near -1 (see `roots_gegenbauer`).
195 if alpha == beta && alpha >= -0.5 {
196 return roots_gegenbauer(n, alpha + 0.5);
197 }
198
199 let (a, b) = (alpha, beta);
200 // Unlike in SciPy, the weights sum to `m` and are then scaled by `2^e`, with
201 // `m 2^e = mu0 = 2^s B(p, q)` for `s = a + b + 1`, `p = a + 1` and `q = b + 1`, so that they
202 // can be finite where `mu0` overflows. Where `B(p, q)` underflows, `ln(mu0)` is computed by
203 // `incbet_lnpow` (for `p, q >= 13`), instead of `s ln(2) + betaln(p, q)`, which cancels.
204 let (s, p, q) = (a + b + 1.0, a + 1.0, b + 1.0);
205 let beta_pq = crate::beta(p, q);
206 let (m, e) = if beta_pq.is_normal() || p.min(q) < 13.0 {
207 // `2^(s - e) <= 2^1000`, and also `2^(s - e) B(p, q) <= 2^1000` if `B(p, q) > 1`
208 let e = (s - 1000.0 + beta_pq.log2().max(0.0)).ceil().max(0.0);
209 ((s - e).exp2() * beta_pq, e)
210 } else {
211 // `ln(2^-(p + q) / B(p, q))` is symmetric, but `incbet_lnpow` needs `p >= q`
212 exp_scaled(Dd::new(-incbet_lnpow(p.max(q), p.min(q), 0.5, 0.5) - LN_2))
213 };
214 let nodes = if a == b { Symmetric } else { Plain };
215 ldexp_weights(jacobi(n, a, b, m, nodes), e)
216}
217
218/// Panics if `n` is zero, or if `alpha <= -1` or `beta <= -1`, like the `ValueError` in SciPy
219fn check_jacobi(n: usize, alpha: f64, beta: f64) {
220 check_n(n);
221 assert!(
222 alpha > -1.0 && beta > -1.0,
223 "alpha and beta must be greater than -1"
224 );
225}
226
227/// The Gauss-Jacobi rule, with the weights summing to `mu0`
228///
229/// Unlike in SciPy, `2 + a + b` is `(a + 1) + (b + 1)` and `b^2 - a^2` is `(b - a) (b + a)`, which
230/// don't cancel for `a, b` near -1.
231fn jacobi(n: usize, a: f64, b: f64, mu0: f64, nodes: Nodes) -> (Vec<f64>, Vec<f64>) {
232 let ab2 = (a + 1.0) + (b + 1.0);
233 let an = |k: f64| {
234 if k == 0.0 {
235 (b - a) / ab2
236 } else {
237 (b - a) * (b + a) / ((2.0 * k - 2.0 + ab2) * (2.0 * k + ab2))
238 }
239 };
240 let bn = |k: f64| {
241 let r = if k == 1.0 {
242 1.0
243 } else {
244 (k * (k - 2.0 + ab2) / (2.0 * k - 3.0 + ab2)).sqrt()
245 };
246 let s = ((k - 1.0 + (a + 1.0)) * (k - 1.0 + (b + 1.0)) / (2.0 * k - 1.0 + ab2)).sqrt();
247 2.0 / (2.0 * k - 2.0 + ab2) * s * r
248 };
249 let f = |n, x| eval_jacobi(n, a, b, x);
250 let df = |n, x| 0.5 * (f64::from(n) - 1.0 + ab2) * eval_jacobi(n - 1, a + 1.0, b + 1.0, x);
251 gen_roots_and_weights(
252 n,
253 mu0,
254 an,
255 bn,
256 f,
257 df,
258 one_minus_x2,
259 |x| b - a - ab2 * x,
260 nodes,
261 )
262}
263
264/// Gauss-Jacobi (shifted) quadrature
265///
266/// Has no corresponding function in `scipy.special`, see [`roots_gengegenbauer`] instead.
267///
268/// The nodes are the roots of the shifted Jacobi polynomial $P_n^{*(\alpha,\beta)}$, and the rule
269/// is exact for polynomials of degree $2n - 1$ with the weight function
270/// $(1 - x)^\alpha x^\beta$ on $[0, 1]$.
271///
272/// # Panics
273/// - if `n` is zero
274/// - if $\alpha \le -1$ or $\beta \le -1$
275///
276/// # See also
277/// - [`eval_sh_jacobi`](crate::eval_sh_jacobi): Evaluate shifted Jacobi polynomials,
278/// $P_n^{*(\alpha,\beta)}$
279/// - [`roots_jacobi`]: Gauss-Jacobi quadrature
280#[must_use]
281pub fn roots_sh_jacobi(n: usize, alpha: f64, beta: f64) -> (Vec<f64>, Vec<f64>) {
282 check_jacobi(n, alpha, beta);
283 // the weights sum to `B(alpha + 1, beta + 1)`, without the factor `2^(alpha + beta + 1)` of
284 // `roots_jacobi`, which can overflow
285 let mu0 = crate::beta(alpha + 1.0, beta + 1.0);
286 jacobi(n, alpha, beta, mu0, Shifted)
287}
288
289/// Gauss-Jacobi quadrature for the generalized Gegenbauer polynomials
290///
291/// Corresponds to [`scipy.special.roots_sh_jacobi`][docs], which, despite its name, isn't
292/// [`roots_sh_jacobi`] (see [`eval_gengegenbauer`](crate::eval_gengegenbauer)).
293///
294/// [docs]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.roots_sh_jacobi.html
295///
296/// The nodes are the roots of $G_n^{(p,q)}$, and the rule is exact for polynomials of degree
297/// $2n - 1$ with the weight function $(1 - x)^{p-q} x^{q-1}$ on $[0, 1]$ (A&S 22.2.2).
298///
299/// For small $q$, the nodes and weights have relative errors up to about $2^{-54} / q$, from the
300/// rounding of $q - 1$ (also in SciPy).
301///
302/// # Panics
303/// - if `n` is zero
304/// - if $p - q \le -1$ or $q \le 0$, or if $q - 1$ rounds to $-1$ (for $q < 2^{-54}$)
305///
306/// # See also
307/// - [`eval_gengegenbauer`](crate::eval_gengegenbauer): Evaluate generalized Gegenbauer
308/// polynomials, $G_n^{(p,q)}$
309#[must_use]
310pub fn roots_gengegenbauer(n: usize, p: f64, q: f64) -> (Vec<f64>, Vec<f64>) {
311 assert!(
312 p - q > -1.0 && q > 0.0,
313 "(p - q) must be greater than -1, and q must be greater than 0"
314 );
315 roots_sh_jacobi(n, p - q, q - 1.0)
316}
317
318/// Gauss-Gegenbauer quadrature
319///
320/// Corresponds to [`scipy.special.roots_gegenbauer`][docs].
321///
322/// [docs]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.roots_gegenbauer.html
323///
324/// The nodes are the roots of the Gegenbauer polynomial $C_n^{(\alpha)}$, and the rule is exact
325/// for polynomials of degree $2n - 1$ with the weight function $(1 - x^2)^{\alpha - 1/2}$ on
326/// $[-1, 1]$ (A&S 22.2.3). For $\alpha = 0$, these are the roots of $T_n$, see
327/// [`roots_chebyshev_t`].
328///
329/// The weights are NaN if $C_n^{(\alpha)}$ overflows at all nodes, e.g. for $n = 150$ and
330/// $\alpha = 10^4$ (also in SciPy). Near $\alpha = -1/2$, they lose accuracy (also in SciPy): for
331/// odd $n$, the relative error is about $n \cdot 10^{-16} / (\alpha + 1/2)$, and within about
332/// $10^{-15}$ of $-1/2$, some can be NaN. [`roots_jacobi`] with $\alpha - 1/2$ for both
333/// parameters doesn't have this problem.
334///
335/// # Panics
336/// - if `n` is zero
337/// - if $\alpha \le -1/2$
338///
339/// # See also
340/// - [`eval_gegenbauer`]: Evaluate Gegenbauer polynomials, $C_n^{(\alpha)}$
341#[must_use]
342pub fn roots_gegenbauer(n: usize, alpha: f64) -> (Vec<f64>, Vec<f64>) {
343 check_n(n);
344 assert!(alpha > -0.5, "alpha must be greater than -0.5");
345 // Unlike in SciPy, a subnormal alpha is treated as 0, where `C_n` at the central root would
346 // underflow.
347 if alpha.abs() < f64::MIN_POSITIVE {
348 // C(n,0,x) == 0 uniformly, however, as alpha->0, C(n,alpha,x)->T(n,x)
349 return roots_chebyshev_t(n);
350 }
351
352 // Unlike in SciPy, `B(1/2, alpha + 1/2)` doesn't overflow, so it needs no approximation for
353 // large alpha.
354 let mu0 = crate::beta(0.5, alpha + 0.5);
355 let an = |_| 0.0;
356 let bn = |k: f64| {
357 if k == 1.0 {
358 // the general case, without the cancelling factors `2 alpha` for small alpha
359 (1.0 / (2.0 * (1.0 + alpha))).sqrt()
360 } else {
361 (k * (k + 2.0 * alpha - 1.0) / (4.0 * (k + alpha) * (k + alpha - 1.0))).sqrt()
362 }
363 };
364 let f = |n, x| eval_gegenbauer(n, alpha, x);
365 let df = |n: i32, x: f64| {
366 let c = f64::from(n);
367 (-c * x * f(n, x) + ((c - 1.0) + 2.0 * alpha) * f(n - 1, x)) / one_minus_x2(x, 0.0)
368 };
369 gen_roots_and_weights(
370 n,
371 mu0,
372 an,
373 bn,
374 f,
375 df,
376 one_minus_x2,
377 |x| -(2.0 * alpha + 1.0) * x,
378 Symmetric,
379 )
380}
381
382/// Gauss-Legendre quadrature
383///
384/// Corresponds to [`scipy.special.roots_legendre`][docs].
385///
386/// [docs]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.roots_legendre.html
387///
388/// The nodes are the roots of the Legendre polynomial $P_n$, and the rule is exact for
389/// polynomials of degree $2n - 1$ on $[-1, 1]$ (A&S 22.2.10).
390///
391/// # Panics
392/// - if `n` is zero
393///
394/// # See also
395/// - [`eval_legendre`]: Evaluate Legendre polynomials, $P_n$
396#[must_use]
397pub fn roots_legendre(n: usize) -> (Vec<f64>, Vec<f64>) {
398 check_n(n);
399 let an = |_| 0.0;
400 let bn = |k: f64| k * (1.0 / (4.0 * k * k - 1.0)).sqrt();
401 let f = |n, x| eval_legendre(n, x);
402 let df = |n: i32, x: f64| {
403 let c = f64::from(n);
404 (-c * x * f(n, x) + c * f(n - 1, x)) / one_minus_x2(x, 0.0)
405 };
406 gen_roots_and_weights(n, 2.0, an, bn, f, df, one_minus_x2, |x| -2.0 * x, Symmetric)
407}
408
409/// Gauss-Legendre (shifted) quadrature
410///
411/// Corresponds to [`scipy.special.roots_sh_legendre`][docs].
412///
413/// [docs]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.roots_sh_legendre.html
414///
415/// The nodes are the roots of the shifted Legendre polynomial $P_n^*$, and the rule is exact for
416/// polynomials of degree $2n - 1$ on $[0, 1]$ (A&S 22.2.11).
417///
418/// # Panics
419/// - if `n` is zero
420///
421/// # See also
422/// - [`eval_sh_legendre`](crate::eval_sh_legendre): Evaluate shifted Legendre polynomials, $P_n^*$
423#[must_use]
424pub fn roots_sh_legendre(n: usize) -> (Vec<f64>, Vec<f64>) {
425 // Unlike in SciPy, the nodes near 0 aren't `(x + 1) / 2` with the nodes `x` of
426 // `roots_legendre`, which cancels.
427 roots_sh_jacobi(n, 0.0, 0.0)
428}
429
430/// Gauss-Chebyshev (first kind) quadrature
431///
432/// Corresponds to [`scipy.special.roots_chebyt`][docs].
433///
434/// [docs]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.roots_chebyt.html
435///
436/// The nodes are the roots of the Chebyshev polynomial $T_n$, and the rule is exact for
437/// polynomials of degree $2n - 1$ with the weight function $1 / \sqrt{1 - x^2}$ on $[-1, 1]$
438/// (A&S 22.2.4).
439///
440/// # Panics
441/// - if `n` is zero
442///
443/// # See also
444/// - [`eval_chebyshev_t`](crate::eval_chebyshev_t): Evaluate Chebyshev polynomials of the first
445/// kind, $T_n$
446#[doc(alias = "roots_chebyt")]
447#[must_use]
448pub fn roots_chebyshev_t(n: usize) -> (Vec<f64>, Vec<f64>) {
449 check_n(n);
450 let m = n as f64;
451 // `sin(pi k / (2n))` for `k = 1 - n, 3 - n, ..., n - 1`
452 let x = (0..n).map(|i| crate::sinpi((2.0 * i as f64 + 1.0 - m) / (2.0 * m)));
453 (x.collect(), vec![PI / m; n])
454}
455
456/// Gauss-Chebyshev (second kind) quadrature
457///
458/// Corresponds to [`scipy.special.roots_chebyu`][docs].
459///
460/// [docs]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.roots_chebyu.html
461///
462/// The nodes are the roots of the Chebyshev polynomial $U_n$, and the rule is exact for
463/// polynomials of degree $2n - 1$ with the weight function $\sqrt{1 - x^2}$ on $[-1, 1]$
464/// (A&S 22.2.5).
465///
466/// # Panics
467/// - if `n` is zero
468///
469/// # See also
470/// - [`eval_chebyshev_u`](crate::eval_chebyshev_u): Evaluate Chebyshev polynomials of the second
471/// kind, $U_n$
472#[doc(alias = "roots_chebyu")]
473#[must_use]
474pub fn roots_chebyshev_u(n: usize) -> (Vec<f64>, Vec<f64>) {
475 check_n(n);
476 let m = n as f64 + 1.0;
477 // Unlike in SciPy, `cos(t)` and `sin(t)` with `t = pi k / (n + 1)` are `sinpi` of arguments in
478 // `[-1/2, 1/2]`, as in `roots_chebyshev_t`, which is more accurate near `t = 0` and `t = pi`.
479 let rule = (1..=n).rev().map(|k| {
480 let sin = crate::sinpi(k.min(n + 1 - k) as f64 / m);
481 (
482 crate::sinpi((m - 2.0 * k as f64) / (2.0 * m)),
483 PI * sin * sin / m,
484 )
485 });
486 rule.unzip()
487}
488
489/// Gauss-Chebyshev (first kind) quadrature on $[-2, 2]$
490///
491/// Corresponds to [`scipy.special.roots_chebyc`][docs].
492///
493/// [docs]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.roots_chebyc.html
494///
495/// The nodes are the roots of $C_n(x) = 2 T_n(x / 2)$, and the rule is exact for polynomials of
496/// degree $2n - 1$ with the weight function $1 / \sqrt{1 - (x/2)^2}$ on $[-2, 2]$ (A&S 22.2.6).
497///
498/// # Panics
499/// - if `n` is zero
500///
501/// # See also
502/// - [`eval_chebyshev_c`](crate::eval_chebyshev_c): Evaluate $C_n$
503#[doc(alias = "roots_chebyc")]
504#[must_use]
505pub fn roots_chebyshev_c(n: usize) -> (Vec<f64>, Vec<f64>) {
506 scale(roots_chebyshev_t(n), 2.0)
507}
508
509/// Gauss-Chebyshev (second kind) quadrature on $[-2, 2]$
510///
511/// Corresponds to [`scipy.special.roots_chebys`][docs].
512///
513/// [docs]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.roots_chebys.html
514///
515/// The nodes are the roots of $S_n(x) = U_n(x / 2)$, and the rule is exact for polynomials of
516/// degree $2n - 1$ with the weight function $\sqrt{1 - (x/2)^2}$ on $[-2, 2]$ (A&S 22.2.7).
517///
518/// # Panics
519/// - if `n` is zero
520///
521/// # See also
522/// - [`eval_chebyshev_s`](crate::eval_chebyshev_s): Evaluate $S_n$
523#[doc(alias = "roots_chebys")]
524#[must_use]
525pub fn roots_chebyshev_s(n: usize) -> (Vec<f64>, Vec<f64>) {
526 scale(roots_chebyshev_u(n), 2.0)
527}
528
529/// Gauss-Chebyshev (first kind, shifted) quadrature
530///
531/// Corresponds to [`scipy.special.roots_sh_chebyt`][docs].
532///
533/// [docs]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.roots_sh_chebyt.html
534///
535/// The nodes are the roots of $T_n^*(x) = T_n(2x - 1)$, and the rule is exact for polynomials of
536/// degree $2n - 1$ with the weight function $1 / \sqrt{x - x^2}$ on $[0, 1]$ (A&S 22.2.8).
537///
538/// # Panics
539/// - if `n` is zero
540///
541/// # See also
542/// - [`eval_sh_chebyshev_t`](crate::eval_sh_chebyshev_t): Evaluate $T_n^*$
543#[doc(alias = "roots_sh_chebyt")]
544#[must_use]
545pub fn roots_sh_chebyshev_t(n: usize) -> (Vec<f64>, Vec<f64>) {
546 let (_, w) = roots_chebyshev_t(n);
547 let m = n as f64;
548 // Unlike in SciPy, the nodes are `sin(t / 2 + pi / 4)^2` instead of `(1 + sin(t)) / 2`, with
549 // `sin(t)` the nodes of `roots_chebyshev_t`, which cancels near 0.
550 let x = (0..n).map(|i| crate::sinpi((2.0 * i as f64 + 1.0) / (4.0 * m)).powi(2));
551 (x.collect(), w)
552}
553
554/// Gauss-Chebyshev (second kind, shifted) quadrature
555///
556/// Corresponds to [`scipy.special.roots_sh_chebyu`][docs].
557///
558/// [docs]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.roots_sh_chebyu.html
559///
560/// The nodes are the roots of $U_n^*(x) = U_n(2x - 1)$, and the rule is exact for polynomials of
561/// degree $2n - 1$ with the weight function $\sqrt{x - x^2}$ on $[0, 1]$ (A&S 22.2.9).
562///
563/// # Panics
564/// - if `n` is zero
565///
566/// # See also
567/// - [`eval_sh_chebyshev_u`](crate::eval_sh_chebyshev_u): Evaluate $U_n^*$
568#[doc(alias = "roots_sh_chebyu")]
569#[must_use]
570pub fn roots_sh_chebyshev_u(n: usize) -> (Vec<f64>, Vec<f64>) {
571 let (_, w) = roots_chebyshev_u(n);
572 let m = n as f64 + 1.0;
573 // Unlike in SciPy, the nodes are `cos(t / 2)^2` instead of `(1 + cos(t)) / 2`, with `cos(t)`
574 // the nodes of `roots_chebyshev_u`, which cancels near 0.
575 let x = (1..=n).map(|k| crate::sinpi(k as f64 / (2.0 * m)).powi(2));
576 // the weights sum to `B(3/2, 3/2) = pi/8` instead of `pi/2`
577 (x.collect(), w.into_iter().map(|wi| wi / 4.0).collect())
578}
579
580/// Gauss-generalized Laguerre quadrature
581///
582/// Corresponds to [`scipy.special.roots_genlaguerre`][docs].
583///
584/// [docs]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.roots_genlaguerre.html
585///
586/// The nodes are the roots of the generalized Laguerre polynomial $L_n^{(\alpha)}$, and the rule
587/// is exact for polynomials of degree $2n - 1$ with the weight function $x^\alpha e^{-x}$ on
588/// $[0, \infty)$ (A&S 22.3.9).
589///
590/// # Panics
591/// - if `n` is zero
592/// - if $\alpha \le -1$
593///
594/// # See also
595/// - [`eval_genlaguerre`]: Evaluate generalized Laguerre polynomials, $L_n^{(\alpha)}$
596#[must_use]
597pub fn roots_genlaguerre(n: usize, alpha: f64) -> (Vec<f64>, Vec<f64>) {
598 check_n(n);
599 assert!(alpha > -1.0, "alpha must be greater than -1");
600
601 let mu0 = crate::gamma(alpha + 1.0);
602 if n == 1 {
603 return (vec![alpha + 1.0], vec![mu0]);
604 }
605
606 let an = |k: f64| 2.0 * k + alpha + 1.0;
607 let bn = |k: f64| -(k * (k + alpha)).sqrt();
608 let f = |n, x| eval_genlaguerre(n, alpha, x);
609 // Unlike in SciPy, the derivative is `-L_{n-1}^(alpha+1)` (DLMF 18.9.23), which doesn't cancel
610 // for alpha near -1.
611 let df = |n: i32, x: f64| -eval_genlaguerre(n - 1, alpha + 1.0, x);
612
613 // Unlike in SciPy, the weights can be finite where `mu0` overflows (alpha > 170.6), with
614 // `ln(mu0)` in double-double.
615 let (mu0, e) = if mu0.is_finite() {
616 (mu0, 0.0)
617 } else {
618 ln_gamma(Dd::new(alpha) + 1.0).map_or((f64::NAN, 0.0), |(l, _, _)| exp_scaled(l))
619 };
620 let rule = gen_roots_and_weights(
621 n,
622 mu0,
623 an,
624 bn,
625 f,
626 df,
627 |x, dx| x + dx,
628 |x| alpha + 1.0 - x,
629 Plain,
630 );
631 ldexp_weights(rule, e)
632}
633
634/// Gauss-Laguerre quadrature
635///
636/// Corresponds to [`scipy.special.roots_laguerre`][docs].
637///
638/// [docs]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.roots_laguerre.html
639///
640/// The nodes are the roots of the Laguerre polynomial $L_n$, and the rule is exact for
641/// polynomials of degree $2n - 1$ with the weight function $e^{-x}$ on $[0, \infty)$
642/// (A&S 22.2.13).
643///
644/// # Panics
645/// - if `n` is zero
646///
647/// # See also
648/// - [`eval_laguerre`](crate::eval_laguerre): Evaluate Laguerre polynomials, $L_n$
649#[must_use]
650pub fn roots_laguerre(n: usize) -> (Vec<f64>, Vec<f64>) {
651 roots_genlaguerre(n, 0.0)
652}
653
654/// The largest `n` for which the Hermite rules use [`gen_roots_and_weights`] instead of
655/// [`roots_hermite_asy`], like in SciPy
656const HERMITE_GW_MAX: usize = 150;
657
658/// Gauss-Hermite (physicist's) quadrature
659///
660/// Corresponds to [`scipy.special.roots_hermite`][docs].
661///
662/// [docs]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.roots_hermite.html
663///
664/// The nodes are the roots of the Hermite polynomial $H_n$, and the rule is exact for polynomials
665/// of degree $2n - 1$ with the weight function $e^{-x^2}$ on $(-\infty, \infty)$ (A&S 22.2.14).
666/// For $n > 150$, they are computed by the asymptotic method of Townsend, Trogdon, and Olver
667/// [^TTO].
668///
669/// [^TTO]: A. Townsend, T. Trogdon, and S. Olver, "Fast computation of Gauss quadrature nodes and
670/// weights on the whole real line", IMA J. Numer. Anal. 36 (2016),
671/// <https://arxiv.org/abs/1410.5286>
672///
673/// # Panics
674/// - if `n` is zero
675///
676/// # See also
677/// - [`eval_hermite_h`]: Evaluate physicist's Hermite polynomials, $H_n$
678#[doc(alias = "roots_hermite")]
679#[must_use]
680pub fn roots_hermite_h(n: usize) -> (Vec<f64>, Vec<f64>) {
681 check_n(n);
682 if n > HERMITE_GW_MAX {
683 return roots_hermite_asy(n);
684 }
685 let an = |_| 0.0;
686 let bn = |k: f64| (k / 2.0).sqrt();
687 let f = |n: i32, x| eval_hermite_h(n as u32, x);
688 let df = |n: i32, x| 2.0 * f64::from(n) * f(n - 1, x);
689 let tau = |x: f64| -2.0 * x;
690 gen_roots_and_weights(n, SQRT_PI, an, bn, f, df, |_, _| 1.0, tau, Symmetric)
691}
692
693/// Gauss-Hermite (statistician's) quadrature
694///
695/// Corresponds to [`scipy.special.roots_hermitenorm`][docs].
696///
697/// [docs]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.roots_hermitenorm.html
698///
699/// The nodes are the roots of the Hermite polynomial $He_n$, and the rule is exact for
700/// polynomials of degree $2n - 1$ with the weight function $e^{-x^2/2}$ on $(-\infty, \infty)$
701/// (A&S 22.2.15). For $n > 150$, they are scaled from [`roots_hermite_h`].
702///
703/// # Panics
704/// - if `n` is zero
705///
706/// # See also
707/// - [`eval_hermite_he`]: Evaluate probabilist's Hermite polynomials, $He_n$
708#[doc(alias = "roots_hermitenorm")]
709#[must_use]
710pub fn roots_hermite_he(n: usize) -> (Vec<f64>, Vec<f64>) {
711 check_n(n);
712 if n > HERMITE_GW_MAX {
713 return scale(roots_hermite_asy(n), SQRT_2);
714 }
715 let an = |_| 0.0;
716 let bn = |k: f64| k.sqrt();
717 let f = |n: i32, x| eval_hermite_he(n as u32, x);
718 let df = |n: i32, x| f64::from(n) * f(n - 1, x);
719 gen_roots_and_weights(
720 n,
721 SQRT_TAU_DOWN,
722 an,
723 bn,
724 f,
725 df,
726 |_, _| 1.0,
727 |x| -x,
728 Symmetric,
729 )
730}
731
732/// Corresponds to `_compute_tauk`: the root of `tau - sin(tau) = c` of Lemma 3.1 in [^TTO], by
733/// 5 Newton steps
734///
735/// [^TTO]: see [`roots_hermite_h`]
736fn compute_tauk(n: usize, k: f64) -> f64 {
737 let a = (n % 2) as f64 - 0.5;
738 let h = (n / 2) as f64;
739 let c = (4.0 * h - 4.0 * k + 3.0) * PI / (4.0 * h + 2.0 * a + 2.0);
740 let mut xi = 0.5 * PI;
741 for _ in 0..5 {
742 xi -= (xi - xi.sin() - c) / (1.0 - xi.cos());
743 }
744 xi
745}
746
747/// Corresponds to `_initial_nodes_a`: Tricomi's approximation of the square of the `k`-th
748/// positive root of `H_n` (Lemma 3.1 in [^TTO]), except near `sqrt(2n + 1)`
749///
750/// [^TTO]: see [`roots_hermite_h`]
751fn initial_nodes_a(n: usize, k: f64) -> f64 {
752 let tauk = compute_tauk(n, k);
753 let sigk = (0.5 * tauk).cos().powi(2);
754 let a = (n % 2) as f64 - 0.5;
755 let nu = 4.0 * (n / 2) as f64 + 2.0 * a + 2.0;
756 // Initial approximation of Hermite roots (square)
757 nu * sigk - 1.0 / (3.0 * nu) * (5.0 / (4.0 * (1.0 - sigk).powi(2)) - 1.0 / (1.0 - sigk) - 0.25)
758}
759
760/// Corresponds to `_initial_nodes_b`: Gatteschi's approximation of the square of the `k`-th
761/// positive root of `H_n` from the top (Lemma 3.2 in [^TTO]), given the `k`-th zero `ak` of Ai
762///
763/// [^TTO]: see [`roots_hermite_h`]
764fn initial_nodes_b(n: usize, ak: f64) -> f64 {
765 let a = (n % 2) as f64 - 0.5;
766 let nu = 4.0 * (n / 2) as f64 + 2.0 * a + 2.0;
767 // Initial approximation of Hermite roots (square)
768 nu + 2.0_f64.powf(2.0 / 3.0) * ak * nu.powf(1.0 / 3.0)
769 + 1.0 / 5.0 * 2.0_f64.powf(4.0 / 3.0) * ak.powi(2) * nu.powf(-1.0 / 3.0)
770 + (9.0 / 140.0 - 12.0 / 175.0 * ak.powi(3)) * nu.powi(-1)
771 + (16.0 / 1575.0 * ak + 92.0 / 7875.0 * ak.powi(4))
772 * 2.0_f64.powf(2.0 / 3.0)
773 * nu.powf(-5.0 / 3.0)
774 - (15152.0 / 3031875.0 * ak.powi(5) + 1088.0 / 121275.0 * ak.powi(2))
775 * 2.0_f64.powf(1.0 / 3.0)
776 * nu.powf(-7.0 / 3.0)
777}
778
779/// Corresponds to `_initial_nodes`: approximations of the non-negative roots of `H_n`, by
780/// [`initial_nodes_a`] up to the turnover point, and [`initial_nodes_b`] above it
781fn initial_nodes(n: usize) -> Vec<f64> {
782 // Turnover point
783 // linear polynomial fit to error of 10, 25, 40, ..., 1000 point rules
784 let fit = 0.49082003 * n as f64 - 4.37859653;
785 let turnover = fit.round_ties_even() as usize;
786 let h = n / 2;
787 // the indices `k` of `initial_nodes_b`, from `kmax` down to 1
788 let kmax = h.saturating_sub(turnover + 1);
789 let ak = crate::xsf::airy_ai_zeros_vec(kmax);
790
791 // Central node is always zero
792 let zero = (n % 2 == 1).then_some(0.0);
793 let xa = (1..=h.min(turnover + 1)).map(|k| initial_nodes_a(n, k as f64));
794 let xb = ak.into_iter().rev().map(|ak| initial_nodes_b(n, ak));
795 zero.into_iter()
796 .chain(xa.chain(xb).map(f64::sqrt))
797 .collect()
798}
799
800/// Corresponds to `_pbcf`: the parabolic cylinder function `U(a, x)` (DLMF 12.10.35) and its
801/// derivative (DLMF 12.10.36), with `a = -n - 1/2` and `x = sqrt(2n + 1) cos(theta)`, by its
802/// asymptotic expansion in Airy functions (Sections 3.2 and 3.3 of [^TTO], with one more term)
803///
804/// [^TTO]: see [`roots_hermite_h`]
805#[rustfmt::skip]
806fn pbcf(n: usize, theta: f64) -> (f64, f64) {
807 let (st, ct) = theta.sin_cos();
808 // https://dlmf.nist.gov/12.10#vii
809 let mu = 2.0 * n as f64 + 1.0;
810 // https://dlmf.nist.gov/12.10#E23
811 let eta = 0.5 * theta - 0.5 * st * ct;
812 // https://dlmf.nist.gov/12.10#E39
813 let zeta = -(3.0 * eta / 2.0).powf(2.0 / 3.0);
814 // https://dlmf.nist.gov/12.10#E40
815 let phi = (-zeta / st.powi(2)).powf(0.25);
816 // Coefficients
817 // https://dlmf.nist.gov/12.10#E43
818 let a0 = 1.0;
819 let a1 = 0.10416666666666666667;
820 let a2 = 0.08355034722222222222;
821 let a3 = 0.12822657455632716049;
822 let a4 = 0.29184902646414046425;
823 let a5 = 0.88162726744375765242;
824 let b0 = 1.0;
825 let b1 = -0.14583333333333333333;
826 let b2 = -0.09874131944444444444;
827 let b3 = -0.14331205391589506173;
828 let b4 = -0.31722720267841354810;
829 let b5 = -0.94242914795712024914;
830 // Polynomials
831 // https://dlmf.nist.gov/12.10#E9
832 // https://dlmf.nist.gov/12.10#E10
833 let ctp = |k: i32| ct.powi(k);
834 let u0 = 1.0;
835 let u1 = (1.0 * ctp(3) - 6.0 * ct) / 24.0;
836 let u2 = (-9.0 * ctp(4) + 249.0 * ctp(2) + 145.0) / 1152.0;
837 let u3 = (-4042.0 * ctp(9) + 18189.0 * ctp(7) - 28287.0 * ctp(5)
838 - 151995.0 * ctp(3) - 259290.0 * ct) / 414720.0;
839 let u4 = (72756.0 * ctp(10) - 321339.0 * ctp(8) - 154982.0 * ctp(6)
840 + 50938215.0 * ctp(4) + 122602962.0 * ctp(2) + 12773113.0) / 39813120.0;
841 let u5 = (82393456.0 * ctp(15) - 617950920.0 * ctp(13) + 1994971575.0 * ctp(11)
842 - 3630137104.0 * ctp(9) + 4433574213.0 * ctp(7) - 37370295816.0 * ctp(5)
843 - 119582875013.0 * ctp(3) - 34009066266.0 * ct) / 6688604160.0;
844 let v0 = 1.0;
845 let v1 = (1.0 * ctp(3) + 6.0 * ct) / 24.0;
846 let v2 = (15.0 * ctp(4) - 327.0 * ctp(2) - 143.0) / 1152.0;
847 let v3 = (-4042.0 * ctp(9) + 18189.0 * ctp(7) - 36387.0 * ctp(5)
848 + 238425.0 * ctp(3) + 259290.0 * ct) / 414720.0;
849 let v4 = (-121260.0 * ctp(10) + 551733.0 * ctp(8) - 151958.0 * ctp(6)
850 - 57484425.0 * ctp(4) - 132752238.0 * ctp(2) - 12118727.0) / 39813120.0;
851 let v5 = (82393456.0 * ctp(15) - 617950920.0 * ctp(13) + 2025529095.0 * ctp(11)
852 - 3750839308.0 * ctp(9) + 3832454253.0 * ctp(7) + 35213253348.0 * ctp(5)
853 + 130919230435.0 * ctp(3) + 34009066266.0 * ct) / 6688604160.0;
854 // Airy Evaluation (Bi and Bip unused)
855 let [ai, aip, _, _] = crate::airy(mu.powf(4.0 / 6.0) * zeta);
856 // Prefactor for U
857 let p = 2.0 * SQRT_PI * mu.powf(1.0 / 6.0) * phi;
858 // Terms for U
859 // https://dlmf.nist.gov/12.10#E42
860 let phip = |k: i32| phi.powi(6 * k);
861 let a_0 = b0 * u0;
862 let a_1 = (b2 * u0 + phip(1) * b1 * u1 + phip(2) * b0 * u2) / zeta.powi(3);
863 let a_2 = (b4 * u0 + phip(1) * b3 * u1 + phip(2) * b2 * u2 + phip(3) * b1 * u3
864 + phip(4) * b0 * u4) / zeta.powi(6);
865 let b_0 = -(a1 * u0 + phip(1) * a0 * u1) / zeta.powi(2);
866 let b_1 = -(a3 * u0 + phip(1) * a2 * u1 + phip(2) * a1 * u2 + phip(3) * a0 * u3)
867 / zeta.powi(5);
868 let b_2 = -(a5 * u0 + phip(1) * a4 * u1 + phip(2) * a3 * u2 + phip(3) * a2 * u3
869 + phip(4) * a1 * u4 + phip(5) * a0 * u5) / zeta.powi(8);
870 // U
871 // https://dlmf.nist.gov/12.10#E35
872 let u = p * (ai * (a_0 + a_1 / mu.powi(2) + a_2 / mu.powi(4))
873 + aip * (b_0 + b_1 / mu.powi(2) + b_2 / mu.powi(4)) / mu.powf(8.0 / 6.0));
874 // Prefactor for derivative of U
875 let pd = SQRT_TAU_DOWN * mu.powf(2.0 / 6.0) / phi;
876 // Terms for derivative of U
877 // https://dlmf.nist.gov/12.10#E46
878 let c_0 = -(b1 * v0 + phip(1) * b0 * v1) / zeta;
879 let c_1 = -(b3 * v0 + phip(1) * b2 * v1 + phip(2) * b1 * v2 + phip(3) * b0 * v3)
880 / zeta.powi(4);
881 let c_2 = -(b5 * v0 + phip(1) * b4 * v1 + phip(2) * b3 * v2 + phip(3) * b2 * v3
882 + phip(4) * b1 * v4 + phip(5) * b0 * v5) / zeta.powi(7);
883 let d_0 = a0 * v0;
884 let d_1 = (a2 * v0 + phip(1) * a1 * v1 + phip(2) * a0 * v2) / zeta.powi(3);
885 let d_2 = (a4 * v0 + phip(1) * a3 * v1 + phip(2) * a2 * v2 + phip(3) * a1 * v3
886 + phip(4) * a0 * v4) / zeta.powi(6);
887 // Derivative of U
888 // https://dlmf.nist.gov/12.10#E36
889 let ud = pd * (ai * (c_0 + c_1 / mu.powi(2) + c_2 / mu.powi(4)) / mu.powf(4.0 / 6.0)
890 + aip * (d_0 + d_1 / mu.powi(2) + d_2 / mu.powi(4)));
891 (u, ud)
892}
893
894/// Corresponds to `_newton`: at most 5 Newton steps in `theta` (see [`pbcf`]) from the
895/// approximate non-negative roots `x` of `H_n`, and the weights of those roots
896fn newton(n: usize, x: &[f64]) -> (Vec<f64>, Vec<f64>) {
897 // Variable transformation
898 let mu = (2.0 * n as f64 + 1.0).sqrt();
899 let mut theta: Vec<f64> = x.iter().map(|xi| (xi / mu).acos()).collect();
900 let mut ud = Vec::new();
901 // Newton iteration
902 for _ in 0..5 {
903 let (u, d): (Vec<f64>, Vec<f64>) = theta.iter().map(|&t| pbcf(n, t)).unzip();
904 let mut max = 0.0_f64;
905 for ((t, ui), udi) in theta.iter_mut().zip(u).zip(&d) {
906 let dtheta = ui / (SQRT_2 * mu * t.sin() * udi);
907 *t += dtheta;
908 max = max.max(dtheta.abs());
909 }
910 ud = d;
911 if max < 1e-14 {
912 break;
913 }
914 }
915 // Undo variable transformation
916 let mut x: Vec<f64> = theta.iter().map(|t| mu * t.cos()).collect();
917 // Central node is always zero
918 if n % 2 == 1 {
919 x[0] = 0.0;
920 }
921 // Compute weights
922 let w: Vec<f64> = x
923 .iter()
924 .zip(ud)
925 .map(|(xi, udi)| (-xi * xi).exp() / (2.0 * udi * udi))
926 .collect();
927 (x, w)
928}
929
930/// Corresponds to `_roots_hermite_asy`: [`roots_hermite_h`] for large `n`, in linear time
931fn roots_hermite_asy(n: usize) -> (Vec<f64>, Vec<f64>) {
932 let (nodes, weights) = newton(n, &initial_nodes(n));
933 // Combine with negative parts (without the central zero of odd n)
934 let skip = n % 2;
935 let x = nodes
936 .iter()
937 .skip(skip)
938 .rev()
939 .map(|x| -x)
940 .chain(nodes.iter().copied());
941 let w: Vec<f64> = weights
942 .iter()
943 .skip(skip)
944 .rev()
945 .chain(&weights)
946 .copied()
947 .collect();
948 // Scale weights
949 let scale = SQRT_PI / w.iter().sum::<f64>();
950 (x.collect(), w.into_iter().map(|wi| wi * scale).collect())
951}