How do I solve for the zeros of a Chebyshev polynomical? (on a computer)

Question

I am working on a computer program and have a method that returns a number for a given $x$, $y$. So $f(x, y) = z$, where $f$ is my method.

if I know $y$ and $z$, can I find what $x$ will be, without being able to write an explicit equation for $f$? Is there an iteration method or something? I would need to find all real $x$ that are solutions.

I doubt the code is useful but I am providing it, if only so that it can be shown that a explicit equation is not possible. tx[ ], ty[ ], and v[ ] are lists which hold the final terms of the polynomial,
c[ ] is a list of constant coefficients, and tcnt and order are integers which specify how many times to loop to get those coefficients. In this $x$ and $y$ are normalized.

        tx[1] = 1.0;
        ty[1] = 1.0;
        tx[2] = x;
        ty[2] = y;

        for (int j = 3; j <= tcnt; j++)
        {
            tx[j] = 2 * x * tx[j - 1] - tx[j - 2];
            ty[j] = 2 * y * ty[j - 1] - ty[j - 2];
        }

        int iv = 1;
        for (int j = 1; j <= tcnt; j++)
        {
            for (int m = j; m >= 1; m--)
            {
                v[iv] = tx[m] * ty[j - m + 1];
                iv = iv + 1;
            }
        }
        double z = 0.0;
        for (int j = 1; j <= order + 1; j++)
        {
            z = z + c[j] * v[j];
        }
        return z;

Answer 1

From what I understand, you have $f(x,y)$ in the form of computer code, but maybe not in explicit form. Given some value of $Y$, and it's target value $Z$ corresponding to some $x$, you want to compute $x$ such that $f(X,Y) = Z$.

Let us re-write this as $$F_Y(x) = f(x,Y)$$ where $Y$ represents a fixed, known value. If I am not mistaken, you wish to compute $$G(x) \stackrel{\textrm{def}}{=} F_Y(x) -Z = 0,$$ where there is an expectation that $F$ is polynomial in $x$ of fixed known order.

If there are assurances that $G$ has no repeated roots, then the Durand-Kerner method might be suitable for computing all the roots simultaneously.

In essence, we presume that $G(x)$ has roots at $x^{(1)}, x^{(2)}, \ldots, x^{(n)}$. Since $G$ is polynomial (and presumably scaled to have a leading coefficient of unity), we may re-write it as

$$G(x) = (x-x^{(1)})(x-x^{(2)})\cdots(x-x^{(n)}).$$

This enables us to create a family of fixed-point iteration of the forms

$$\begin{align*} x^{(1)}_k &= x^{(1)}_{k-1} - \frac{G\left(x^{(1)}_{k-1}\right)}{\left(x^{(1)}_{k-1}-x^{(2)}_{k-1}\right)\cdots\left(x^{(1)}_{k-1}-x^{(n)}_{k-1}\right)}, \\ x^{(2)}_k &= x^{(2)}_{k-1} - \frac{G\left(x^{(2)}_{k-1}\right)}{\left(x^{(2)}_{k-1}-x^{(1)}_{k-1}\right)\cdots\left(x^{(2)}_{k-1}-x^{(n)}_{k-1}\right)}, \\ &\vdots \end{align*}$$

Since you can compute $F_Y$ (and hence $G$) directly, then this should be fairly simple to implement. Note that one of the complications is that you must know a priori the order of the polynomial and that you must use complex arithmetic.