I am in search of an introduction into numerical linear algebra - or, at least, pure linear algebra - that treats the case when the input data are random variables.

A typical application would be to derive an estimate for the expected numerical error when the input variables are subject to random noise. Note that this neither implies that algorithms has access to a perfect coin, nor that the errors in inexact arithmetic obey any probability distribution.

  • $\begingroup$ Ouch, how do you know errors do not obey any probability distribution? Have you plotted the errors? Mostly these books are called "Introductory Statistics"... There's also the good ol' Nicholas J. Higham "Accuracy and stability of numerical algorithms" (SIAM, 2002). $\endgroup$ – Deer Hunter Jan 19 '13 at 19:36
  • $\begingroup$ I'm sure your arithmetic obeys some probability distribution. You may simply not be able to say which one by giving a particular formula for it. But it would likely be obtainable experimentally, and you can give it a symbol, compute mean values and other statistics as necessary. $\endgroup$ – Wolfgang Bangerth Jan 20 '13 at 17:05

It isn't clear here whether you're really interested in just the effects of floating point round off error within a computation or the effects of uncertain/noisy inputs to a computation. In most practical situations, assuming that you've been reasonably careful in selecting an appropriate numerical method, and assuming that the problem you're trying to solve isn't inherently ill-conditioned/ill-posed, the effects of uncertain or noisy inputs to the model are much larger than the effects of floating point round off. There's a burgeoning field of "uncertainty quantification" which attempts to deal with this question.

Some simple cases are quite easy. For example, if $x$ has a multivariate normal distribution, a matrix $A$ is known exactly, and $y=Ax$, then $y$ also has a multivariate normal distribution, with $E[y]=AE[x]$, and $\mbox{cov}(y)=A\mbox{cov}(x)A^{T}$. If $y=f(X)$, where $f$ is nonlinear, then $y$ won't have a multivariate normal distrubiton, but as long as $f$ isn't strongly nonlinear and the uncertainty in $x$ is small, it may be possible to use a linear approximation to $f$ to get an approximate multivariate normal distribution for $y$.

A very general technique is Monte Carlo simulation. If $x$ is an uncertain input with known distribution, generate lots of random values of the $x$ vector, compute $y=f(x)$ for each of these random vectors, and then look at the empirical distribution of $y$. There's a whole literature on methods such as "importance sampling" for making this process more efficient.

Recently there has been a lot of interest in "polynomial chaos expansions", a non Monte Carlo approach to analyzing the uncertainty in differential equation models of dynamical systems.

  • $\begingroup$ Thank you very much. Could you give me a book recommendation? - I agree that round-off errors are mostly unimportant in practice; my interest is merely theoretical. $\endgroup$ – shuhalo Jan 20 '13 at 15:28
  • $\begingroup$ This is a very large subject that no single book covers. I can suggest books about particular aspects of this but I'm not aware of any all-encompassing reference. It's also hard to make a recommendation without knowing something about your background. The theory of multivariate normal distributions and linear transformations of MVN vectors is covered in many textbooks on probability. There are many textbooks on Monte Carlo simulation. Polynomial chaos expansions are a recent topic, and I'm not aware of any good textbooks on this topic yet. $\endgroup$ – Brian Borchers Jan 20 '13 at 18:30

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.