Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I want to approximate a function $f(x)$ on [a,b]. The condition number for computing a function $f$ at a point $x$ is defined by

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

For my function $f$ this grows without bound as $x \rightarrow b$. So I make a change of variable $y=h(x)$ and as it happens the function $g(y)=f(h^{-1}(y))$ is alot simpler to approximate on $[h(a),h(b)]$. In particular the condition number of $g$ as $y\rightarrow h(b)$ is small, so I can easily construct an approximation for $g$ on $[h(a),h(b)]$. I can then approximate $f$ using my approximation $g_A$ to $g$ as follows.

$$ f(x)\approx g_A(h(x))$$

I have some questions relating I would like to clear up in my head.

1) I was wondering if this is a common approach in numerical analysis. i.e. if the condition number is large then to look for a change of variable which reduces it? If so can you point to any references? In particular in the context of function approximation.

2) My problem isn't exactly evaluating a function $f$ at $x$. More precisely it is to build some type of approximation $f_A$ to $f$ then approximate $f$ by $f_A$. So have I used the above definition of condition number out of context or am I right to observe that with this definition of $\kappa$ the problem is ill conditioned? I thought it made sense, since the library routines I'm using to build the approximation try and evaluate $f$ at hundreds of points, and they fail to build the approximant (I guess because the problem of evaluating $f$ is an ill conditioned one).

3) Key to success in numerical analysis is to apply stable algorithms to well conditioned problems. Does this mean that a stable algorithm can become unstable when applied to an ill conditioned problem?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

1.) Change of variables in numerical analysis, and indeed many types of solution approaches, is common, but not necessarily to reduce condition number. Condition number is a very loose measure of how "solvable" something is. One could have a very small condition number and an inaccurate solution. Likewise, one could have a large condition number and an exact solution.

It's unlikely that you'll find any real references to this as a strategy. Change of variables is an elementary analytical tool.

2.) This is more or less how condition numbers can be used, but see above in that they are not concrete heuristics.

3.) Yes, stable algorithm may fail to solve an ill-conditioned problem.

Consider the following system of equations:

$$\begin{pmatrix} 10^{-10000000000000} & 0 \\ 0 & 10^{-10000000000000} \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} 1 \\ 1\end{pmatrix}.$$

This (matrix) condition number is exceptionally small, and I can easily write the exact solution to this system. However, this may fail due to underflow/overflow issues.

In this case, a well-known stable algorithm (ie, solution to $b=ax$) fails on a well-conditioned problem.

Conversely, consider

$$\begin{pmatrix} 10^{14} & 0 \\ 0 & 10^{14} \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} 1 \\ 1\end{pmatrix}.$$

This has a large condition number, but is solvable by a stable algorithm.

Finally,

$$\begin{pmatrix} 10^{140} & 0 \\ 0 & 10^{140} \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} 1 \\ 1\end{pmatrix}.$$

This problem has a large condition number and is unsolvable by a stable algorithm.

(The above examples pre-assume some floating point format. Tweak exponents as necessary for your computing platform).

share|improve this answer

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.