5
$\begingroup$

I am seeking a general solution to a system of non linear equations with a specific pattern:

Order 1:

$$ x_0 = a^2 + b^2 $$ $$ x_1 = 2ab $$

Order 2:

$$ x_0 = a^2 + b^2 + c^2 $$ $$ x_1 = 2ab + 2bc $$ $$ x_2 = 2ac $$

Order 3:

$$ x_0 = a^2 + b^2 + c^2 + d^2 $$ $$ x_1 = 2ab + 2bc + 2cd $$ $$ x_2 = 2ac + 2bd $$ $$ x_3 = 2ad $$

Order 4:

$$ x_0 = a^2 + b^2 + c^2 + d^2 + e^2 $$ $$ x_1 = 2ab + 2bc + 2cd + 2de $$ $$ x_2 = 2ac + 2bd + 2ce $$ $$ x_3 = 2ad + 2be $$ $$ x_4 = 2ae $$

The values $x_n$ are constant and known. The values $a, b, c, ...$ need to be solved. It's easily solvable for Order 1. Order 2 is a little more tricky but solvable. It quickly becomes very hard for order greater than or equal to 3.

I don't want to have to resort to say a quadratic programming method. Are there any tricks to this particular set of equations or any numerical methods that may help me? Given the nature of the pattern it looks like there might be a general solution using a specific technique I'm not familiar with. For instance, a change of variable might reduce this to a root finding problem perhaps.

$\endgroup$
1
  • $\begingroup$ Have you tried solving less complex systems, for example all these systems without the first equation ($a^2 + b^2 + ...$), or just the first two equations? or where $x^i$ all equal 0? Those kinds of simplifications may (or may not) be easier to solve and may give hints on how to solve the bigger problems. $\endgroup$ – Mitch May 26 '15 at 0:28
1
$\begingroup$

Let us rename the unknowns $a,b,c,\ldots$ to $v_0,\ldots,v_n$, assume these to be complex numbers, and define the (yet unknown) polynomial $$f(z) = \sum_{k=0}^n v_k z^k \tag{1}$$ Then we have $$f(z)\,f\left(\frac{1}{z}\right) = x_0 + \frac{x_1}{2}\left(z+\frac{1}{z}\right) + \frac{x_2}{2}\left(z^2+\frac{1}{z^2}\right) + \cdots + \frac{x_n}{2}\left(z^n+\frac{1}{z^n}\right)$$ Using the Chebyshev polynomials of the first kind $T_k(X)$, we can write $$\begin{align} \frac{1}{2}\left(z^k+\frac{1}{z^k}\right) &= T_k(X) \\ \text{where}\quad X &= \frac{1}{2}\left(z+\frac{1}{z}\right) \tag{2}\\ \text{thus}\quad f(z)\,f\left(\frac{1}{z}\right) &= g(X) \tag{3}\\ \text{where}\quad g(X) &= \sum_{k=0}^n x_k T_k(X) \tag{4} \end{align}$$ Note that $g(X)$ is a polynomial in $X$ that can be determined from the given $x_k$ via $(4)$. Now we need to find a (non-unique) polynomial factor $f(z)$ fulfilling $(3)$.

If $g=0$, that is, all $x_k = 0$, then $(3)$ implies $f=0$, hence all $v_k=0$.

In the following, I will assume that not all $x_k = 0$.

Let $m = \deg g$, so $0\leq m\leq n$. Let $g_m$ be the (nonzero) coefficient of $X^m$ in $g(X)$. We can deduce from the defining equations for $x_m,\ldots,x_n$ (working from index $n$ downwards) that there is $r\in\{0,\ldots,n-m\}$ such that $v_k = 0$ for $k\in\{0,\ldots,r-1,m+r+1,\ldots,n\}$ and $v_k\neq0$ for $k\in\{r,m+r\}$. So basically $f(z)$ is the product of $z^r$ with a degree-$m$ polynomial. (And $g_m = 2^m v_r v_{m+r}$, but we do not need this.)

The idea is to find suitable $f(z)$ by looking at the zeros of $g(X)$. Therefore, find the $m$ (possibly complex) roots of $g(X)=0$, and name these $X_1,\ldots,X_m$. For each such root $X=X_j$, solve $(2)$ for $z$. There will be two solutions; pick one of these and name it $z_j$, then the other solution will be $\frac{1}{z_j}$. Keep in mind that both solutions for $z$ are nonzero. We will consider $z_j$ a root of $f(z)=0$; this makes $\frac{1}{z_j}$ a root of $f\left(\frac{1}{z}\right)=0$ automatically. Now we can write $$\begin{align} f(z) &= v_{m+r} z^r\prod_{j=1}^m (z - z_j) \tag{5}\\ &\quad\text{with arbitrary}\quad r\in\{0,\ldots,n-m\} \end{align}$$ so $(3)$ becomes $$v_{m+r}^2\prod_{j=1}^m \underbrace{(z - z_j)\left(\frac{1}{z} - z_j\right)}_ {-2z_j (X - X_j)} = g(X)$$ Equating coefficients for $X^m$, we get $$v_{m+r} = \pm\sqrt{\frac{g_m}{(-2)^m\prod_{j=1}^m z_j}} \tag{6}$$ Choose a sign for $v_{m+r}$, then expand the product for $f(z)$ in $(5)$ to get the representation $(1)$. You can read the coefficients $v_0,\ldots,v_n$ from that.

In general, the choices you make for $r$, for $z_j$ versus $\frac{1}{z_j}$, and for the sign of $v_{m+r}$ all affect the solution, so there are $2^{m+1}(n-m+1)$ (not necessarily distinct) solution tuples $(v_0,\ldots,v_n)$. Some particular variations are:

  • Varying $r$: This results in rotating $(v_0,\ldots,v_n)$ as long as only leading/trailing zeros are wrapped around.
  • Replacing all $z_j$ with $\frac{1}{z_j}$: This results in the reversal $(v_r,\ldots,v_{m+r}) \mapsto (v_{m+r},\ldots,v_r)$.
  • Flipping the sign of $v_{m+r}$ in $(6)$: This results in sign flips of all $v_k$.
$\endgroup$
0
$\begingroup$

I couldn't solve the problem, but I have done some manipulations that maybe could help. They are too long for a comment.

For order $n$ we have that

$$\sum_{k=1}^{n+1}a_k=\pm\sqrt{\sum_{k=0}^nx_k}\qquad(1)$$

I have renamed the variables $a$, $b$, $c$... to $a_1$, $a_2$, $a_3$,...

Last equation says $$a_1a_{n+1}=x_n$$ so we can solve for $a_{n+1}$ and substitute in $(1)$. Assuming that $x_n\neq 0$, we have now

$$\frac{x_n}{a_1}+\sum_{k=1}^{n}a_k=\pm\sqrt{\sum_{k=0}^nx_k}\qquad(2)$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.