Mathematics of Computation · 2004 · 80 citations · 15 references
ComputingComputer ScienceAlgorithmsOptimizationScientific ComputingIterative SolversMatrix ComputationNumerical AlgorithmsNumerical AnalysisNumerical Linear AlgebraConvergenceMatrix Equation SolversNewton ConvergenceRapid Convergence Techniques
The two matrix iterations <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper X Subscript k plus 1 Baseline equals upper I minus-or-plus upper A Superscript asterisk Baseline upper X Subscript k Superscript negative 1 Baseline upper A"> <mml:semantics> <mml:mrow> <mml:msub> <mml:mi>X</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>k</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msub> <mml:mo>=</mml:mo> <mml:mi>I</mml:mi> <mml:mo> ∓ </mml:mo> <mml:msup> <mml:mi>A</mml:mi> <mml:mo> ∗ </mml:mo> </mml:msup> <mml:msubsup> <mml:mi>X</mml:mi> <mml:mi>k</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo> − </mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msubsup> <mml:mi>A</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">X_{k+1}=I\mp A^*X_k^{-1}A</mml:annotation> </mml:semantics> </mml:math> </inline-formula> are known to converge linearly to a positive definite solution of the matrix equations <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper X plus-or-minus upper A Superscript asterisk Baseline upper X Superscript negative 1 Baseline upper A equals upper I"> <mml:semantics> <mml:mrow> <mml:mi>X</mml:mi> <mml:mo> ± </mml:mo> <mml:msup> <mml:mi>A</mml:mi> <mml:mo> ∗ </mml:mo> </mml:msup> <mml:msup> <mml:mi>X</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo> − </mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> <mml:mi>A</mml:mi> <mml:mo>=</mml:mo> <mml:mi>I</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">X\pm A^*X^{-1}A=I</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , respectively, for known choices of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper X 0"> <mml:semantics> <mml:msub> <mml:mi>X</mml:mi> <mml:mn>0</mml:mn> </mml:msub> <mml:annotation encoding="application/x-tex">X_0</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and under certain restrictions on <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper A"> <mml:semantics> <mml:mi>A</mml:mi> <mml:annotation encoding="application/x-tex">A</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . The convergence for previously suggested starting matrices <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper X 0"> <mml:semantics> <mml:msub> <mml:mi>X</mml:mi> <mml:mn>0</mml:mn> </mml:msub> <mml:annotation encoding="application/x-tex">X_0</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is generally very slow. This paper explores different initial choices of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper X 0"> <mml:semantics> <mml:msub> <mml:mi>X</mml:mi> <mml:mn>0</mml:mn> </mml:msub> <mml:annotation encoding="application/x-tex">X_0</mml:annotation> </mml:semantics> </mml:math> </inline-formula> in both iterations that depend on the extreme singular values of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper A"> <mml:semantics> <mml:mi>A</mml:mi> <mml:annotation encoding="application/x-tex">A</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and lead to much more rapid convergence. Further, the paper offers a new algorithm for solving the minus sign equation and explores mixed algorithms that use Newton’s method in part.
15
The Algebraic Eigenvalue Problem
E. I., J. H. Wilkinson · Mathematics of Computation · 1966 · 5.2K citations