Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose we want to find the root of the equation $f(x)=\phi(x) - d = 0$, where d is a real constant and $f$ is continuously differentiable function.

The problem is well posed if the inverse $\phi^{-1}$ exists, since in that case $\phi^{-1} (d) = x$.

Now most numerical analysis books I read on the topic of solving nonlinear equations (for example this grad level book) open the discussion by introducing the condition number associated with the problem, in this case it happens to be.

$$ \kappa = \frac{1}{f^{\prime}(x)} = \frac{1}{\phi^{\prime}(x)}$$

From this equation we see that the condition number $\kappa$ is large when $\phi^{\prime}(x)$ is close to zero and we are told large $\kappa$ leads to ill conditioned problems.

But so what?? I can't think of an example for which say Newton Raphson or any other root finding shceme fails when the problem is ill conditioned.

I understand the condition number measures the sensitivity of finding roots of $f$ with respect to the input datum, $d$ in this case. But what practical implications does this have?

I can think of plenty of severely ill conditioned problems. But Newton raphson has no problems with them (I know there are situations in which Newton Raphson fails, but these are due to problems intrinsic to the algorithm and are not dependent on the condition number). Does any one know of an example where the condition number for the above problem is large and a root finding scheme fails? If not then whats the point of examining the condition number.

I apologize in advance if this question is not of the level of the forum. I thought since the answer cannot be found in an elementary text, here was a good place to ask.

share|improve this question
    
What are $f, \phi$, and $d$? I don't understand your notation. –  Qiaochu Yuan Oct 28 '12 at 4:25
    
clarified notation –  James77 Oct 28 '12 at 4:36
add comment

2 Answers 2

up vote 1 down vote accepted

In addition to the convergence speed (and radius) mentioned in Pietro Majer's answer, there is another factor: if the problem is ill-conditioned, the solution is sensitive to perturbations.

If you make an error of magnitude $\varepsilon$ in computing the iteration or the parameters data, then the solution is perturbed by a quantity $\kappa \varepsilon$, where $\kappa$ is the condition number. In practice, you have an error of at least one part in $10^{-16}$ in most computer implementations, and often an even larger one if your function depends on measured data or approximations. So Newton's method may converge without trouble, but the solution that you get could be total garbage.

share|improve this answer
    
That is interesting. Do you know of any examples? –  James77 Oct 28 '12 at 18:14
    
Take $\phi(x)=x^{16}$, $d=0$. If you perturb $d$ to $10^{-16}$, then the unique real solution of the equation changes from $x=0$ to $x=10^{-1}$. –  Federico Poloni Oct 28 '12 at 19:01
add comment

In the usual assumptions, the NR method has quadratic convergence: $E_{n+1}\le C E_n^2$, where the constant $C$ is a bound for $|f''/2f'|$. So, the smaller is $f'$ compared to $f''$, the slower is the (estimated) convergence. As a limit case, think what happens with $f(x)=x^2$: the corresponding iteration is $x_n:=x_0/2^n$.

share|improve this answer
    
I wish I could accept both answers, unfortunately I don't even have enough points for an up vote! Thanks for your input the argument is very insightful –  James77 Oct 28 '12 at 22:17
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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