Residual-error conjecture for the recursive tridiagonal inversion algorithm

At least 10 years old · documented by

Let A∈Rn×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.

References

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.