algorithm - 反向复数二维查找表

Question

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

自 在计算上很昂贵我的想法是使用查找表方法。我可以生成维度为 的二维查找表(正向查找表)，但我真正需要的是这个查找表的逆向——产生 基于给定的 .

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

在哪里 , 是常数并且 , 是 .

Answer 1

1. 对于f(x,y)，您可以使用f(x,y)->(a,b) 2D LUT(看上表)

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

   如果要使用线性插值，则局部最小值/最大值必须是 LUT 内的点，因为并不总是需要更高阶的多项式插值。我会用 4 point cubic interpolation

2. 如何计算g(a,b)->(x,y)

   • 首先反向映射是否可行？
   • 那么有多少 (x,y) 点返回相同的 (a,b)=f(x,y) ？
   • 同问:f是否有函数？

   如果 f 不起作用，那么您遇到了问题，您无法解决这个问题，除非以某种方式将范围分割为 f 起作用的子范围，然后您将必须根据一些规则选择适当的范围，具体取决于您要做什么。所以假设 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)你可以在那里使用我的近似类

近似值的嵌套是这样完成的:

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 表......

• 每个递归将步骤除以 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)
• 不要忘记将最小值、最大值更改为您使用的范围...