<p>In this paper we give the detailed error analysis of two algorithms <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\varvec{W}_{\varvec{1}}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mrow> <mi mathvariant="bold-italic">W</mi> </mrow> <mrow> <mn mathvariant="bold">1</mn> </mrow> </msub> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(\varvec{W}_{\varvec{2}}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mrow> <mi mathvariant="bold-italic">W</mi> </mrow> <mrow> <mn mathvariant="bold">2</mn> </mrow> </msub> </math></EquationSource> </InlineEquation> for computing the symplectic factorization of a symmetric positive definite and symplectic matrix <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(\varvec{A} \varvec{\in } \mathbb {R}^{\varvec{2n \times 2n}}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mi mathvariant="bold-italic">A</mi> </mrow> <mrow> <mo mathvariant="bold">∈</mo> </mrow> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mrow> <mn mathvariant="bold">2</mn> <mi mathvariant="bold-italic">n</mi> <mo mathvariant="bold">×</mo> <mn mathvariant="bold">2</mn> <mi mathvariant="bold-italic">n</mi> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation> in the form <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(\varvec{A}\varvec{=}\varvec{LL}^{\varvec{T}}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mi mathvariant="bold-italic">A</mi> </mrow> <mrow> <mo mathvariant="bold">=</mo> </mrow> <msup> <mrow> <mi mathvariant="bold-italic">LL</mi> </mrow> <mrow> <mi mathvariant="bold-italic">T</mi> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(\varvec{L} \varvec{\in } \mathbb {R}^{\varvec{2n \times 2n}}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mi mathvariant="bold-italic">L</mi> </mrow> <mrow> <mo mathvariant="bold">∈</mo> </mrow> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mrow> <mn mathvariant="bold">2</mn> <mi mathvariant="bold-italic">n</mi> <mo mathvariant="bold">×</mo> <mn mathvariant="bold">2</mn> <mi mathvariant="bold-italic">n</mi> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation> is a symplectic block lower triangular matrix. We prove that Algorithm <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(\varvec{W}_{\varvec{2}}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mrow> <mi mathvariant="bold-italic">W</mi> </mrow> <mrow> <mn mathvariant="bold">2</mn> </mrow> </msub> </math></EquationSource> </InlineEquation> is numerically stable for a broader class of symmetric positive definite matrices <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(\varvec{A} \varvec{\in } \mathbb {R}^{\varvec{2n \times 2n}}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mi mathvariant="bold-italic">A</mi> </mrow> <mrow> <mo mathvariant="bold">∈</mo> </mrow> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mrow> <mn mathvariant="bold">2</mn> <mi mathvariant="bold-italic">n</mi> <mo mathvariant="bold">×</mo> <mn mathvariant="bold">2</mn> <mi mathvariant="bold-italic">n</mi> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation>. It means that Algorithm <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(\varvec{W}_{\varvec{2}}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mrow> <mi mathvariant="bold-italic">W</mi> </mrow> <mrow> <mn mathvariant="bold">2</mn> </mrow> </msub> </math></EquationSource> </InlineEquation> is producing the computed factors <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(\varvec{\tilde{L}}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mover accent="true"> <mi mathvariant="bold-italic">L</mi> <mo mathvariant="bold" stretchy="false">~</mo> </mover> </mrow> </math></EquationSource> </InlineEquation> in floating-point arithmetic with machine precision <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\(\varvec{u}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">u</mi> </mrow> </math></EquationSource> </InlineEquation> such that <InlineEquation ID="IEq13"> <EquationSource Format="TEX">\(\varvec{\Vert }{\varvec{A-\tilde{L} {\tilde{L}}}^{\varvec{T}}}\varvec{\Vert }_{\varvec{2}}\varvec{=} \varvec{\mathcal {O}}\varvec{(n}^{\varvec{2}} \varvec{u} \varvec{\Vert A\Vert _2}\varvec{)}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mo mathvariant="bold" stretchy="false">‖</mo> </mrow> <msup> <mrow> <mi mathvariant="bold-italic">A</mi> <mo mathvariant="bold">-</mo> <mover accent="true"> <mi mathvariant="bold-italic">L</mi> <mo mathvariant="bold" stretchy="false">~</mo> </mover> <mover accent="true"> <mi mathvariant="bold-italic">L</mi> <mo mathvariant="bold" stretchy="false">~</mo> </mover> </mrow> <mrow> <mi mathvariant="bold-italic">T</mi> </mrow> </msup> <msub> <mrow> <mo mathvariant="bold" stretchy="false">‖</mo> </mrow> <mrow> <mn mathvariant="bold">2</mn> </mrow> </msub> <mrow> <mo mathvariant="bold">=</mo> </mrow> <mrow> <mi mathvariant="bold-script">O</mi> </mrow> <msup> <mrow> <mo mathvariant="bold" stretchy="false">(</mo> <mi mathvariant="bold-italic">n</mi> </mrow> <mrow> <mn mathvariant="bold">2</mn> </mrow> </msup> <mrow> <mi mathvariant="bold-italic">u</mi> </mrow> <mrow> <msub> <mrow> <mo mathvariant="bold" stretchy="false">‖</mo> <mi mathvariant="bold-italic">A</mi> <mo mathvariant="bold" stretchy="false">‖</mo> </mrow> <mn mathvariant="bold">2</mn> </msub> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. On the other hand, Algorithm <InlineEquation ID="IEq14"> <EquationSource Format="TEX">\(\varvec{W}_{\varvec{1}}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mrow> <mi mathvariant="bold-italic">W</mi> </mrow> <mrow> <mn mathvariant="bold">1</mn> </mrow> </msub> </math></EquationSource> </InlineEquation> is unstable, in general, for symmetric positive definite and symplectic matrix <InlineEquation ID="IEq15"> <EquationSource Format="TEX">\(\varvec{A}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">A</mi> </mrow> </math></EquationSource> </InlineEquation>. In this paper we also give corresponding bounds for Algorithm <InlineEquation ID="IEq16"> <EquationSource Format="TEX">\(\varvec{W}_{\varvec{1}}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mrow> <mi mathvariant="bold-italic">W</mi> </mrow> <mrow> <mn mathvariant="bold">1</mn> </mrow> </msub> </math></EquationSource> </InlineEquation> that are weaker. We show that the factorization error depends on the conditioning of the principal submatrix <InlineEquation ID="IEq17"> <EquationSource Format="TEX">\(\varvec{A}_{\varvec{11}} \varvec{\in } \mathbb {R}^{{\varvec{n}} \varvec{\times } \varvec{n}}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mrow> <mi mathvariant="bold-italic">A</mi> </mrow> <mrow> <mn mathvariant="bold">11</mn> </mrow> </msub> <mrow> <mo mathvariant="bold">∈</mo> </mrow> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mrow> <mrow> <mi mathvariant="bold-italic">n</mi> </mrow> <mrow> <mo mathvariant="bold">×</mo> </mrow> <mrow> <mi mathvariant="bold-italic">n</mi> </mrow> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation>, located in the upper-left block of <InlineEquation ID="IEq18"> <EquationSource Format="TEX">\(\varvec{A}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">A</mi> </mrow> </math></EquationSource> </InlineEquation>. Bounds for the loss of symplecticity of the lower block triangular matrices <InlineEquation ID="IEq19"> <EquationSource Format="TEX">\(\varvec{L}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">L</mi> </mrow> </math></EquationSource> </InlineEquation> for both Algorithms <InlineEquation ID="IEq20"> <EquationSource Format="TEX">\(\varvec{W}_{\varvec{1}}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mrow> <mi mathvariant="bold-italic">W</mi> </mrow> <mrow> <mn mathvariant="bold">1</mn> </mrow> </msub> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq21"> <EquationSource Format="TEX">\(\varvec{W}_{\varvec{2}}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mrow> <mi mathvariant="bold-italic">W</mi> </mrow> <mrow> <mn mathvariant="bold">2</mn> </mrow> </msub> </math></EquationSource> </InlineEquation> that hold in exact arithmetic for a broader class of symmetric positive definite matrices <InlineEquation ID="IEq22"> <EquationSource Format="TEX">\(\varvec{A}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">A</mi> </mrow> </math></EquationSource> </InlineEquation> (but not necessarily symplectic) are also given. The tests performed in <i>MATLAB</i> illustrate that our error bounds for considered algorithms are reasonably sharp.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Numerical stability of the symplectic \(LL^T\) factorization

  • Maksymilian Bujok,
  • Miroslav Rozložník,
  • Agata Smoktunowicz,
  • Alicja Smoktunowicz

摘要

In this paper we give the detailed error analysis of two algorithms \(\varvec{W}_{\varvec{1}}\) W 1 and \(\varvec{W}_{\varvec{2}}\) W 2 for computing the symplectic factorization of a symmetric positive definite and symplectic matrix \(\varvec{A} \varvec{\in } \mathbb {R}^{\varvec{2n \times 2n}}\) A R 2 n × 2 n in the form \(\varvec{A}\varvec{=}\varvec{LL}^{\varvec{T}}\) A = LL T , where \(\varvec{L} \varvec{\in } \mathbb {R}^{\varvec{2n \times 2n}}\) L R 2 n × 2 n is a symplectic block lower triangular matrix. We prove that Algorithm \(\varvec{W}_{\varvec{2}}\) W 2 is numerically stable for a broader class of symmetric positive definite matrices \(\varvec{A} \varvec{\in } \mathbb {R}^{\varvec{2n \times 2n}}\) A R 2 n × 2 n . It means that Algorithm \(\varvec{W}_{\varvec{2}}\) W 2 is producing the computed factors \(\varvec{\tilde{L}}\) L ~ in floating-point arithmetic with machine precision \(\varvec{u}\) u such that \(\varvec{\Vert }{\varvec{A-\tilde{L} {\tilde{L}}}^{\varvec{T}}}\varvec{\Vert }_{\varvec{2}}\varvec{=} \varvec{\mathcal {O}}\varvec{(n}^{\varvec{2}} \varvec{u} \varvec{\Vert A\Vert _2}\varvec{)}\) A - L ~ L ~ T 2 = O ( n 2 u A 2 ) . On the other hand, Algorithm \(\varvec{W}_{\varvec{1}}\) W 1 is unstable, in general, for symmetric positive definite and symplectic matrix \(\varvec{A}\) A . In this paper we also give corresponding bounds for Algorithm \(\varvec{W}_{\varvec{1}}\) W 1 that are weaker. We show that the factorization error depends on the conditioning of the principal submatrix \(\varvec{A}_{\varvec{11}} \varvec{\in } \mathbb {R}^{{\varvec{n}} \varvec{\times } \varvec{n}}\) A 11 R n × n , located in the upper-left block of \(\varvec{A}\) A . Bounds for the loss of symplecticity of the lower block triangular matrices \(\varvec{L}\) L for both Algorithms \(\varvec{W}_{\varvec{1}}\) W 1 and \(\varvec{W}_{\varvec{2}}\) W 2 that hold in exact arithmetic for a broader class of symmetric positive definite matrices \(\varvec{A}\) A (but not necessarily symplectic) are also given. The tests performed in MATLAB illustrate that our error bounds for considered algorithms are reasonably sharp.