Given an n by n matrix <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\textbf{A}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="bold">A</mi> </math></EquationSource> </InlineEquation> and an n-vector <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\textbf{b}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="bold">b</mi> </math></EquationSource> </InlineEquation>, along with a rational function <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$R(z):= D(z )^{-1} N(z)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>R</mi> <mrow> <mo stretchy="false">(</mo> <mi>z</mi> <mo stretchy="false">)</mo> </mrow> <mo>:</mo> <mo>=</mo> <mi>D</mi> <msup> <mrow> <mo stretchy="false">(</mo> <mi>z</mi> <mo stretchy="false">)</mo> </mrow> <mrow> <mo>-</mo> <mn>1</mn> </mrow> </msup> <mi>N</mi> <mrow> <mo stretchy="false">(</mo> <mi>z</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, we show how to find the optimal approximation to <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$R(\textbf{A}) \textbf{b}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>R</mi> <mo stretchy="false">(</mo> <mi mathvariant="bold">A</mi> <mo stretchy="false">)</mo> <mi mathvariant="bold">b</mi> </mrow> </math></EquationSource> </InlineEquation> from the Krylov space, <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\text{ span }( \textbf{b}, \textbf{A}\textbf{b}, \ldots , \textbf{A}^{k-1} \textbf{b})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mspace width="0.333333em" /> <mtext>span</mtext> <mspace width="0.333333em" /> <mo stretchy="false">(</mo> <mi mathvariant="bold">b</mi> <mo>,</mo> <mi mathvariant="bold">A</mi> <mi mathvariant="bold">b</mi> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msup> <mi mathvariant="bold">A</mi> <mrow> <mi>k</mi> <mo>-</mo> <mn>1</mn> </mrow> </msup> <mi mathvariant="bold">b</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, using the basis vectors produced by the Arnoldi algorithm. To find this optimal approximation requires running <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\max \{ \text{ deg } (D), \text{ deg } (N) \} - 1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo movablelimits="true">max</mo> <mo stretchy="false">{</mo> <mspace width="0.333333em" /> <mtext>deg</mtext> <mspace width="0.333333em" /> <mo stretchy="false">(</mo> <mi>D</mi> <mo stretchy="false">)</mo> <mo>,</mo> <mspace width="0.333333em" /> <mtext>deg</mtext> <mspace width="0.333333em" /> <mo stretchy="false">(</mo> <mi>N</mi> <mo stretchy="false">)</mo> <mo stretchy="false">}</mo> <mo>-</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> extra Arnoldi steps and solving a <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$k + \max \{ \text{ deg } (D), \text{ deg } (N) \}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>+</mo> <mo movablelimits="true">max</mo> <mo stretchy="false">{</mo> <mspace width="0.333333em" /> <mtext>deg</mtext> <mspace width="0.333333em" /> <mo stretchy="false">(</mo> <mi>D</mi> <mo stretchy="false">)</mo> <mo>,</mo> <mspace width="0.333333em" /> <mtext>deg</mtext> <mspace width="0.333333em" /> <mo stretchy="false">(</mo> <mi>N</mi> <mo stretchy="false">)</mo> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation> by k least squares problem. Here optimal is taken to mean optimal in the <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$D(\textbf{A})^{*} D(\textbf{A})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>D</mi> <mmultiscripts> <mrow> <mo stretchy="false">(</mo> <mi mathvariant="bold">A</mi> <mo stretchy="false">)</mo> </mrow> <mrow /> <mrow> <mrow /> <mo>∗</mo> </mrow> </mmultiscripts> <mi>D</mi> <mrow> <mo stretchy="false">(</mo> <mi mathvariant="bold">A</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>-norm. Similar to the case for linear systems, we show that eigenvalues alone cannot provide information about the convergence behavior of this algorithm and we discuss other possible error bounds for highly non-normal matrices.

Optimal polynomial approximation to rational matrix functions using the Arnoldi algorithm

期刊论文
发表日期：

2025年5月7日

查看全文

Tyler Chen,
Anne Greenbaum,
Natalie Wellen

摘要

Given an n by n matrix $\textbf{A}$ $A$ and an n-vector $\textbf{b}$ $b$ , along with a rational function $R(z):= D(z )^{-1} N(z)$ $R (z) : = D {(z)}^{- 1} N (z)$ , we show how to find the optimal approximation to $R(\textbf{A}) \textbf{b}$ $R (A) b$ from the Krylov space, $\text{ span }( \textbf{b}, \textbf{A}\textbf{b}, \ldots , \textbf{A}^{k-1} \textbf{b})$ $span (b, A b, \dots, A^{k - 1} b)$ , using the basis vectors produced by the Arnoldi algorithm. To find this optimal approximation requires running $\max \{ \text{ deg } (D), \text{ deg } (N) \} - 1$ $max {deg (D), deg (N)} - 1$ extra Arnoldi steps and solving a $k + \max \{ \text{ deg } (D), \text{ deg } (N) \}$ $k + max {deg (D), deg (N)}$ by k least squares problem. Here optimal is taken to mean optimal in the $D(\textbf{A})^{*} D(\textbf{A})$ $D {(A)}^{*} D (A)$ -norm. Similar to the case for linear systems, we show that eigenvalues alone cannot provide information about the convergence behavior of this algorithm and we discuss other possible error bounds for highly non-normal matrices.