In numerical analysis, there are algorithms which are either forwards stable or backwards stable. Forwards stability is strictly stronger, and is more desirable. Unfortunately, it is in many instances unattainable. A good example is for finding the SVD of a matrix. The SVD problem is uncomputable, as can be shown using a simple proof invoking Type Two Effectivity and basic linear algebra.

There is a work-around I believe, which is to introduce some indirection: For instance, let's talk about the eigendecomposition of symmetric matrices. Give a symmetric matrix $M$, we can produce the pair $(P,D)$ such that $P D P^{-1} \supseteq M$ and $P$ is not interval-valued, while $D$ is an interval-valued diagonal matrix. Note that we cannot compute the eigendecomposition of exactly $M$. Often the objective of eigendecomposition is to speed up the computation of a continuous function $f$, because often $f$ satisfies $f(PDP^{-1})=Pf(D)P^{-1}$, and computing the RHS might be faster than computing $f(M)$ directly. It's clear that if $PDP^{-1} \supseteq M$, then $P f(D) P^{-1} \supseteq f(M)$. In other words, we can lift $f$ so that it sends $(P,D)$ to $(P, f(D))$. There are no computability obstacles here.

Has this work to extend interval arithmetic to backwards stable problem been done before? (Is this sort of question appropriate here? I am an outsider to the area.)



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.