0
$\begingroup$

Consider the problem of computing $y(x) = \frac{(1+x)}{(1-x)}$ as a function of x, for $x \in (\frac{1}{2},1)$ and also for $x \in (-1,0)$ On which of the two intervals is this problem better conditioned with respect to the perturbations of x?

I'm struggling to understand how to check if a problem is well-conditioned, and my textbook hasn't been much help (it's not a book for beginners, which I am). I've determined the derivative, $y'(x)=\frac{2}{(1-x)^2}$, and can clearly see it has issues around $x=1$.

I think $(-1,0)$ is the better interval because the derivative increases rapidly between $(\frac{1}{2},1)$. Am I $\require{enclose} \enclose{horizontalstrike}{over}$thinking about this the right way?

$\endgroup$
  • 1
    $\begingroup$ I'm not an expert by any means, but I believe that you are thinking about it the right way. Basically, if your input varies by a tiny bit, how is your output affected? Does it change by "a lot" or only "a little". You have the right logic: by 1, your output changes "a lot". For more, and probably a better answer, look here: math.stackexchange.com/questions/1916682/… $\endgroup$ – QC_QAOA Sep 3 '17 at 6:55
2
$\begingroup$

In general we can define the condition number in the following way.

Suppose we calculate a finite amount of (output) values $y_i$, $i=1,…,n$, for some input data $x_j$, $j=1…,m$ with some algorithm, given as functions: $$y_i:=f_i(x_1,…,x_m).$$

This above describes what we call "a problem".

Suppose we have some perturbation in the data, $x_i+δx_i$, we are interested in the behavior of the output values: $$y_i+δy_i.$$

Using Taylors Expansion, cutting after the term of first order, we get: $$δy_i =f_i(x+δx)-f_i(x)=\sum_{j=1}^m\frac{∂f_i}{∂x_j}(x)δx_j + R_i^f(x;δx)\approx \sum_{j=1}^m\frac{∂f_i}{∂x_j}(x)δx_j.$$

Note that we need that $f$ is two times differentiable.

It follows: $$\frac{δy_i}{y_i} \approx \sum_{j=1}^m\frac{∂f_i}{∂x_j}(x)\frac{δx_j}{y_i}= \sum_{j=1}^m\underbrace{\frac{∂f_i}{∂x_j}(x)\frac{x_j}{f_i(x)}}_{:=k_{ij}(x)}\frac{δx_j}{x_j}$$ So the condition number describes how the relative error in the input $x$ transfers to the relative error in the output $y$.
The cutting after the first term is ok, if $|δx|=o(|y_i|)\quad i=1,…,n$.

If $|κ_{ij}|>>1$ we call the problem ill-conditioned.


Example: Adding numbers $y=f(x_1,x_2) = x_1+x_2$
We get \begin{align*} k_1 = \frac{∂f}{∂x_1}\frac{x_1}{f} = 1\cdot \frac{x_1}{x_1+x_2} = \frac{1}{1+x_2/x_1} \\ k_2 = \frac{∂f}{∂x_2}\frac{x_2}{f} = 1\cdot \frac{x_2}{x_1+x_2} = \frac{1}{1+x_1/x_2} \end{align*} Hence addition is ill-conditioned if $x_1/x_2\approx -1$.


Back to your question: Calculating the derivative is the first step, but not enough. You can see that in the example above, where the derivative is constant. Using your argument it would follow, that adding numbers is always well-conditioned, which is not true.

Can you solve your problem now?


EDIT: The derivative is given by $$f'(x)=\frac{2}{(x-1)^2}.$$ So for the condition number we get: $$κ=\frac{2x}{(1-x)(1+x)}.$$

This number "seems to be bad" at $x=1$ or $x=-1$, which would mean, that both intervals $(-1,0)$ and $(1/2,1)$ are "bad". But that might be a false conclusion, as we did not simplify $κ$ in a way, that we actually can see something. (And that conclusion is in fact wrong!)

Do you understand how $κ$ was calculated?
Can you interpret our condition number?
(Have a look at the example above)

$\endgroup$
  • $\begingroup$ Ahhhhh... that makes a lot of sense. Thank you for the counterexample. However something's still not clicking for me. Although I get it intuitively, how would I explain why $(-1,0)$ is the better choice? $\endgroup$ – p3ngu1n Sep 4 '17 at 16:18
  • $\begingroup$ @p3ngu1n I edited the answer to explain the next step. $\endgroup$ – P. Siehr Sep 5 '17 at 8:11
  • $\begingroup$ @p3ngu1n After you ask a question here, if you get an acceptable answer, you should "accept" the answer by clicking the check mark ✓ next to it. This scores points for you and for the person who answered your question. You can find out more about accepting answers here: How do I accept an answer?, Why should we accept answers?. $\endgroup$ – P. Siehr Sep 22 '17 at 9:18

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.