Lab 5: Conditioning Lab · Numerical Methods

Move the slider to change one number of the system slightly. Watch the crossing point and the amplification factor.

The same exact formula, run forward (unstable) and backward (stable). Every correct value lies between 0 and 1/(n+1).

Condition number of a 2×2 system

Try this

Run it. How much does the solution move?
Change d to 2.0 (a well-conditioned matrix with a = c = 1). Repeat.
Change d to 1.00000001. What happens to kappa?

Hilbert matrix

Try this

Run it. At which n is the error above 1e-6?
Add n = 13 and 14. What happens?
Explain: is the algorithm or the problem to blame?

Forward vs backward recurrence

Try this

Run it. Where does forward go wrong?
Start the backward loop from n = 30 instead of 40. Is it still accurate at n = 20?

Q1 Define the condition number of a function and compute it for

f(x) = \sqrt{x}

and

f(x) = x - 1

.

\kappa_f = |xf'(x)/f(x)|

.

\sqrt{x}

:

\kappa = \tfrac12

(well-conditioned for all

x > 0

).

x - 1

:

\kappa = |x/(x-1)|

, which is huge near

x = 1

.

Q2 Compute

\kappa_\infty(A)

for

A = \begin{pmatrix} 4 & 1 \\ 2 & 3 \end{pmatrix}

.

\det = 10

,

A^{-1} = \tfrac{1}{10}\begin{pmatrix} 3 & -1 \\ -2 & 4\end{pmatrix}

.

\|A\|_\infty = 5

,

\|A^{-1}\|_\infty = 0.6

, so

\kappa = 3

: well-conditioned.

Q3 Distinguish an ill-conditioned problem and an unstable algorithm, with one example each.

Ill-conditioned: exact answer very sensitive to data; e.g.

x + y = 2

,

x + 1.0001y = 2.0001

(

\kappa\approx4\times10^4

). Unstable: the algorithm amplifies its own rounding errors; e.g.

I_n = 1 - nI_{n-1}

forward, which gives

I_{20} = -30.19

although

0 < I_{20} < 1/21

.

Q4 A matrix has

\kappa = 10^{12}

. How many correct digits do you expect in single and double precision?

Double: about

16 - 12 = 4

. Single: about

7 - 12 < 0

, so none.

Q5 Explain forward and backward error using the computed root

\tilde{x} = 1.4142

of

x^2 = 2

.

Forward error

|\tilde{x} - \sqrt2| = 1.36\times10^{-5}

. Backward error:

\tilde{x}^2 = 1.99996164

, so

\tilde{x}

solves

x^2 = 1.99996164

exactly; the data changed by

3.8\times10^{-5}

.

Q6 Is a matrix with a very small determinant always ill-conditioned? Explain.

No.

10^{-10}I

has determinant

10^{-30}

(3×3) but

\kappa = 1

. Conditioning depends on

\|A\|\|A^{-1}\|

, not on the size of the determinant.