1
$\begingroup$

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.)

$\endgroup$
0

0

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.