反向复杂二维查找 table

Question

我有一些函数，它将一些输入映射到输出。输出是一个复数。我真正感兴趣的是反函数。但是由于这种反演不能以分析的方式完成，我需要用数值近似来完成。

由于的计算成本很高，我的想法是使用查找 table 方法。我可以生成尺寸为的 2D 查找 table（正向查找 table），但我实际需要的是此查找 table 的逆向结果基于给定的 .

对于查找的反转 table 我能想到的最简单的方法是使用正向查找的条目 table 作为顶点并在规则网格中在它们之间插值产生反向查找table。如果反向查找 table 对于所需的精度来说太大了，我会生成粗略的 table 并将这些值用作优化算法的起始值。有没有我遗漏的更简单的方法？

其中、是常量，、是。

Answer 1

对于 f(x,y) 你可以使用 f(x,y)->(a,b) 2D LUT（查找 Table）

但是存储的网格点必须 select 非常密集，以便每个网格矩形最多有一个凹凸，否则插值将无法正常工作。

如果要使用线性插值，则局部 min/max 必须是 LUT 内的点，因为并不总是需要更高阶的多项式插值。我会使用 4 point cubic interpolation
如何计算g(a,b)->(x,y)
- 首先可以反向映射吗？
- 有多少 (x,y) 点 return 相同 (a,b)=f(x,y) ?
- 同问：f函数有没有？
如果 f 不起作用那么你遇到了问题并且你无法解决这个问题，除非以某种方式将范围细分为 f 起作用的子范围然后你将不得不 select 根据一些规则的适当范围取决于你想做什么。所以假设 f 是函数

那么如何计算 (x,y)=g(a,b) 即 f(x,y)=(a,b)？
1. 我将从结果的近似值开始。因此，在整个范围内尝试足够的 (x,y) 值并存储最接近所需输出的点，以便 |f(x,y)-(a,b)| 最小。
2. 然后再次开始，但不是全范围而是围绕这一点
  - 递归地提高准确度到你需要的点。
  - 看这里 Increasing accuracy of solution of transcendental equation 我正在计算类似的问题有 2D 点的 1D LUT (a(t),y(t)) 并且需要逆 3D 点 (a0,y0,z0) 你可以使用我的近似值 class那里

近似嵌套是这样完成的：

int n=5;  // recursions
double e; // Error Of Solution Variable
approx ax,ay;
//            min    max   step   
for (ax.init(-100.0,+100.0,10.0,n,&e);!ax.done;ax.step())
for (ay.init(-100.0,+100.0,10.0,n,&e);!ay.done;ay.step())
    {
    e=|f(ax.a,ay.a)-(a,b)|;
    }
// here (ax.a,ay.a) should hold your solution for input point `(a,b)`

初始步骤应该尽可能小，这样就不会遗漏颠簸
如果您的 g(a,b) 形状太复杂，那么这可能无法正常工作

据此您可以计算反 LUT table ...

每次递归将步数除以 10，因此明智地选择 n。

对于2D和奇点来说这个性能还不错O((log(N))^2)。我在 3D O((log(N))^3) 上执行此操作，每次 e 计算得到 100 点，这非常慢（大约 35 秒）

其中N=(10^n)*(max-min)/step，n是递归的次数
准确度是 step/(10^n)
不要忘记将最小值、最大值更改为您使用的范围...

反向复杂二维查找 table

Reverse complex 2D lookup table

algorithm

math

2d

interpolation

lookup-tables