1
$\begingroup$

Say I have $f(k)$ for all $k = 1, \ldots, 2^n$, and $0\le f(k)\le n$.

I would like to solve for $x$:

$$ x\sum _{k=1}^{2^n }\frac{1}{f(k)+x} =1. $$

And also this if possible,

$$\sum _{k=1}^{2^{n} }\exp\left(\frac{-f(k)^{2} }{x} \right) =1.$$

Any ideas?

  • 0
    Don't you have any more information you can give on your $f(k)$?2011-07-20
  • 0
    I can, but I don't think it will help... f(k) is a (normalized) distance measure from a vertex (indexed by k) of a unit hypercube of dimension n to a certain point within the hypercube. So it can range from 0 to n (since the metric is Manhattan). Helps...?2011-07-20
  • 0
    Leaving $f(k)$ unspecified is certainly less helpful than the information you gave. :)2011-07-20
  • 0
    Both are well-behaved functions of $x$, so a one-dimensional root finder should have no trouble returning a numeric solution.2011-07-20

3 Answers 3

1

Solving the second is equivalent to solving for $y$:

$$ \sum_{k=1}^{M} \exp(- a_k y ) = 1$$

for some given $M=2^n$, $ a_k = f(k)^2 $ (so $0 \le a_k \le n^2$), and $x = 1/y$ This is obviously not solvable analytically, but (as Felix points out) it's a nice function, smooth and decreasing, it have a single solution and it's easy to find numerically. Little more can be said withouth knowing $a_k$

  • 0
    Thanks, leonbloy and @FelixCQ. One more point - notice that there are an exponential (in n) number of summands. Thus for high n it becomes very hard to solve - is there any way to approximate a solution for x in this case, while avoiding exponential time?2011-08-10
  • 0
    @Omri: As long as you don't put any other restrictions on $a_k$, my equation is exactly as general as yours. Hence, I have $M$ summands (as many as $a_k$ coefficients ; I don't mind if $M=2^n$ or whatever; you can forget about it). You cannot expect some approximation if you don't know anything about $a_k$.2011-08-10
1

Multiplying both sides of the first equation by

$$\prod_{k=1}^{2^n} \big( f(k) + x\big)$$

reveals that solving your equation is equivalent to solving a polynomial of degree $2^n$, which is possible analytically for $n=0$, $n=1$ and $n=2$, but not in general for $n\geq 3$, unless your coefficients $f(k)$ have a particularly nice form.

  • 0
    Thanks, Chris. Any idea about the second equation?2011-07-20
1

About the second equation, it seems a solution exists for a unique positive $x$.

Solutions cannot be negative, since the left hand side would be bigger than $2^n$.

On $\mathbb{R}_+$, whe have:

  • The left hand side is a sum of increasing functions, so it is itself increasing.
  • Letting $x$ go to $0$, the left hand side goes to $0$.
  • Letting $x$ go to infinity, the left hand side goes to $2^n > 1$.

So there is a unique value in between that solves the equation, but I don't see how to solve it analytically.

Given its monotonic nature, it should be very easy to solve numerically, with a Newton-Raphson method, for example.