Residual-error conjecture for the recursive tridiagonal inversion algorithm

Let ARn×nA\in\mathbb{R}^{n\times n} be a nonsingular matrix whose inverse has only nonzero elements in the lower triangle. Let XX be the inverse computed numerically by algorithm (KWbasic), let ε\varepsilon denote the machine precision, let cond(A)\operatorname{cond}(A) denote the condition number of AA, and assume that εncond(A)<C\varepsilon n\operatorname{cond}(A)<C for some constant CC. Residual-error conjecture. The computed inverse satisfies

\max\left\\{\left\\|XA-I\right\\|_1,\left\\|AX-I\right\\|_1\right\\}\leq\varepsilon K(n)\operatorname{cond}(A),

for some K(n)=O(n)K(n)=O(n). This is obtained conditionally from the authors' preceding presumption about the computed inverse norm; the text says that a formal proof of that assumption may be difficult, so the claim remains open.

Sources & referencesView supporting material

Primary source

Paweł Keller and Iwona Wróbel, “On recursive algorithms for inverting tridiagonal matrices”, arXiv:1509.09264 (2015).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.