正交多项式的算法

Question

感谢您对我的问题的关注:)

我的问题是关于寻找一种(足够有效的)算法来寻找给定权重函数 f 的正交多项式。

我尝试简单地应用 Gram-Schmidt 算法，但这个算法不够有效。实际上，它需要 O(n^2) 积分。但我的目标是使用此算法找到 Hankel determinants一个函数f。因此，包含简单计算矩阵并取其行列式的“直接”计算仅需要 2*n - 1 个积分。

但我想使用定理来说明 f 的 n 阶 Hankel 行列式是 f 的正交多项式的 n 个第一前导系数的乘积。原因是当 n 变大(比如大约 20)时，Hankel 行列式变得非常大，我的目标是将它除以另一个大常数(对于 n = 20，常数为 10^103 阶)。我的想法是“稀释”前导系数乘积中常数的计算。

我希望有一个 O(n) 算法来计算 n 个第一个正交多项式 :) 我已经进行了一些挖掘，但没有发现一般函数 f 的那个方向(实际上 f 可以是任何平滑函数)。

编辑:我会在这里精确说明我所说的对象是什么。

1) n 阶 Hankel 行列式是方阵的行列式，它在斜对角线上是常数。因此例如

a b c

bcd

c d e

是大小为 3 x 3 的 Hankel 矩阵。

2) 如果你有一个函数 f : R -> R，你可以将它的“第 k 个时刻”关联到 f_k :=\int_{\mathbb{R }} f(x) x^k dx

有了这个，你可以创建一个 Hankel 矩阵 A_n(f)，其条目是 (A_n(f)){ij} = f{i+j-2}，这是喜欢

f_0 f_1 f_2

f_1 f_2 f_3

f_2 f_3 f_4

考虑到这一点，很容易定义 f 的 Hankel 行列式，它很简单H_n(f) := det(A_n(f))。 (当然，据了解，f 在无穷远处有足够的衰减，这意味着所有矩都已明确定义。f 的典型选择可以是高斯 f(x) = exp(-x^2)，或任何连续在一组紧凑的 R 上运行...)

3) 我所说的 f 的正交多项式是一组多项式 (p_n) 使得

\int_{\mathbb{R}} f(x) p_j(x) p_k(x) 如果 j = k 则为 1，否则为 0。

(之所以这样调用它们，是因为它们形成了多项式向量空间关于标量积的正交基

(p|q) =\int_{\mathbb{R}} f(x) p(x) q(x) dx

4) 现在，这是基本的线性代数，从配备标量积的向量空间的任何基础，你可以建立一个正交基础，这要归功于 Gram-Schmidt algorithm .这就是 n^2 集成的来源。你从基础 1, x, x^2, ..., x^n 开始。然后，您需要 n(n-1) 个积分才能使该族正交，并且还需要 n 个积分才能对其进行归一化。

5) 有一个定理说如果 f : R -> R 是一个在无穷远有足够衰减的函数，那么我们有它的 Hankel 行列式 H_n(f) 等于

H_n(f) =\prod_{j = 0}^{n-1}\kappa_j^{-2}

其中\kappa_j 是 f 的第 j+1 个正交多项式的首项系数。

谢谢您的回答!

(PS:我标记了 octave，因为我在 octave 工作，所以，幸运的是(但我对此表示怀疑)，有一个内置函数或一个包已经完成管理这种想法)

Answer 1

正交多项式服从递归关系，我们可以写成

P[n+1] = (X-a[n])*P[n] - b[n-1]*P[n-1]
P[0] = 1
P[1] = X-a[0]

我们可以通过以下方式计算a、b系数

a[n] = <X*P[n]|P[n]> / c[n]
b[n-1] = c[n-1]/c[n]

在哪里

c[n] = <P[n]|P[n]>

(这里 < | > 是你的内积)。

但是我不能保证这个过程在大范围内的稳定性。