現在,理工学の様々な分野において,行列に関する数値計算は広く応用されている.本論文では,行列の特異値および固有値の数値計算法に対する理論解析を行っている.

前半では,特異値計算を扱っている.応用上,全特異値を必要とする場合もあれば,最大特異値のみ必要とする場合,あるいは大きい方からいくつかの特異値を必要とする場合もあり,目的に応じて用いるアルゴリズムは異なってくる.本論文では,すべての特異値を数値計算するアルゴリズムについて考える,この場合,最初に与えられた行列を直交同値変換により上 2 重対角行列に変換し,この上 2 重対角行列に対してある種の反復計算を行うことで特異値を求めるのが標準的である.上 2 重対角行列の特異値計算アルゴリズムとしては,従来 QR 法に基づくものが定番であったが,1994年にFernando-Parlettにより提案されたdqds (differential quotient difference with shifts) 法が近年注目されている.このdqds 法は,数値安定性に優れており,シフトというものを適切に設定することで高速な特異値計算が可能であることから,線形計算用ライブラリ LAPACKにおいて DLASQとして実装されており,また特異値分解および固有値分解のためのMRRR (Multiple Relatively Robust Representations) 法と呼ばれる一連の手法の中に組み込まれており,よく用いられるアルゴリズムである.

dqds 法の理論的側面について,最近,著者らは初等的かつ直接的な収束証明を与え,これにより漸近的な収束速度を明らかにすることが可能となった.収束速度はシフトに依存するが,著者らは Johnson シフトを用いる場合の漸近収束速度が 1.5 次であることを示し,その後,山本らはこの方針に基づき,いくつかのシフト戦略に対して漸近収束次数を明らかにしている.例えば,Ostrowski シフトで 1.5 次,Brauer シフトで超 1.5 次の収束速度を実現することが示されている.また,木村らにより一般化 Newton シフトが提案され,これを用いることでより高次の収束速度が達成されることも報告されている.本論文のdqds 法に対する成果も,こういった収束速度に関する一連の研究に属するものである.

まず超 2 次収束が達成されるシフト戦略を新たに提案する.従来のシフト戦略の構成法としては,反復過程において現れる上2 重対角行列の最小特異値のシャープな下界を見積もることを目指してきたが,本論文では dqds 法の収束定理を基にアルゴリズムから直接的に超 2 次収束シフトを導出している点に特色がある.

次に,Rutishauser シフトにより dqds 法が 3 次収束することの厳密な証明を与える.もともとこのシフトは,Rutishauser が,反復の終盤のある 1 反復で 3 次収束を実現するために提案したものであって,漸近的な意味での3 次収束性を実現するシフト戦略は与えられていなかった.そこで本論文では,Rutishauserシフトを基に漸近的に3 次収束する具体的なシフト戦略を構成し,その3 次収束性の厳密な証明を与えた.そしてさらに詳細な収束性解析を行い,Rutishauser シフトが設定可能な条件は,反復過程において一旦満たされれば,その後の反復でも常に満たされることを示している.これは切り替えが必要なシフトの中で,Rutishuaser シフトに対してのみ成り立つ特徴的な性質である.

さらに,実際にLAPACKに実装されている DLASQ ルーチンの収束速度が超 2 次であることを示している.DLASQでは,高速化のため様々なシフトが併用されており,そのアルゴリズムは非常に複雑なものとなっているが,収束定理を基にした解析により,比較的単純な議論で収束速度を導出している.

本論文の後半では,対称行列の固有値計算を扱っている.対称行列のすべての固有値を計算する場合,特異値計算と同様,計算量の観点から前処理的に行列を対称 3 重対角行列に変換し,この対称 3 重対角行列に対してある種の反復計算を行うことで固有値を求めるのが標準的である.対称 3 重対角行列の固有値計算アルゴリズムとしては,QR 法がよく知られており,収束加速のために,通常,Wilkinson シフトが用いられ,この場合大域的収束性と 2 次以上の収束速度が理論保証されている.近年,行列の大規模化に伴い並列計算に適したアルゴリズムが必要とされているが,通常のWilkinson シフト付 QR 法を並列化することは困難である.これに対し 1989年,Bai-Demmelは,QR 法にシフトを複数導入することで並列計算に適した QR 法を提案した.これはマルチシフト QR 法と呼ばれるもので,後にBraman,Byers,Mathiasにより優れた実装が与えられ,現在 LAPACKにDHSEQR ルーチンとして組み込まれている.

本論文では,まず通常のシングルシフトのQR 法について考え,Wilkinson シフト付き QR 法の収束性解析を行っている.Wilkinson シフト付き QR 法の収束性解析については,1968年にWilkinson が収束証明を与えた後も,継続的に大域的収束の別証明や収束速度の評価が行われており,収束速度は行列に依存して 2 次の場合,3 次の場合に分類されることが知られている.本論文では,現状では 2 次収束までしか理論保証されていない行列に3 次収束するものが含まれていることを実験的考察により指摘し,これをもとに2 次となる場合,3 次となる場合を完全な形で分類する定理を与えている.

最後に,シフトを複数導入したマルチシフト QR 法に対して Wilkinson シフトを拡張したシフト戦略を提案し,このWilkinson 型マルチシフト QR 法の大域的収束性を示している.通常,反復過程において現れる対称 3 重対角行列の右下の副対角成分の収束を加速することを目的にシフト戦略は構成されるものであるが,従来のシフト戦略では,収束証明はあるものの右下とは異なる副対角成分が収束するような不自然な収束振舞をする場合があったのに対し,本論文で提案する Wilkinson 型マルチシフトQR 法においては,右下の副対角成分の収束を証明しており,自然な収束定理を与えている.

行列の特異値および固有値の数値計算法は、理工学分野を始め、様々な分野で用いられており、その研究の重要性は論を俟たないであろう。

特異値の数値計算においては、通常、最初に行列を上2重対角化し、この上2重対角行列に対して反復法を適用して特異値を計算する。この反復法として、近年、dqds(differential quotient difference with shifts)法と呼ばれる方法が主流となっている。一方、固有値計算においては、対称行列の場合、行列を3重対角化し、この対称3重対角行列に対して反復法を適用して固有値を計算する。反復法としてはQR法を用いるのが標準的である。非対称行列の場合には、行列をHessenberg化し、その後QR法を用いる。この数値計算法の反復法部分、dqds法やQR法の収束性は、dqds法やQR法のシフトと呼ばれる量をどのように選ぶか、すなわち、シフト戦略に拠るところが大きく、シフト戦略とその収束性の研究が理論、実験の両面から行われてきた。

本論文は、「行列の特異値および固有値の数値計算アルゴリズムの基礎研究」と題し、上2重対角行列に対するdqds法、および、対称3重対角行列に対するQR法に対して、様々なシフト戦略の収束性を理論的に明らかにしたものである。本論文の特徴は、従来の収束性解析の大半がいわゆる局所的であった、すなわち、十分収束した状況下、1ステップ進んだときの収束性を調べたものであったのに対して、大域的な収束性の解析、すなわち、漸近的にすべてのステップに渡って成立する収束性の解析を行ったという点にある。第1章「はじめに」,第9章「おわりに」を含め,9章からなる。前半2章から5章でdqds法を,後半6章から8章でQR法を扱っている。

第2章「特異値計算のためのdqds法の基本性質」では、dqds法のアルゴリズムとその基本的性質について述べている。特に、論文提出者が修士論文で証明したdqds法の大域的収束定理(dqds法が大域的に収束するためのシフト戦略が満たすべき条件を示したもの)について記されている。

第3章「dqds法における超2次収束シフト戦略」では、大域的に超2次収束が達成される新しいシフト戦略を提案している。従来のシフト戦略の構成法は、反復過程において現れる上2重対角行列の最小特異値のシャープな下界を与える公式を用いるのが標準的であるが、本論文ではdqds法のアルゴリズムから直接的に超2次収束性が期待されるシフトを導出し、実際に、そのシフトが大域的に超2次収束することを示している。

第4章「Rutishauserシフトを用いるdqds 法」では、Rutishauserが1960年に提案した局所収束次数が3次のシフトを用い、適切なシフト戦略を作成することにより、dqds法が大域的に3次収束することを証明している。そしてさらに詳細な収束解析を行い、Rutishauserシフトは、シフト戦略において一旦設定されれば、その後の反復でも常に設定されるという著しい性質をもつことが示されている。

第5章「dqds法の実装DLASQ ルーチンの超2次収束定理」では、線形計算ライブラリLAPACKに実装されているdqds法のルーチン(DLASQ)の収束速度が大域的に超2次であることを示している。DLASQでは、高速化のため様々なシフトが併用され、そのアルゴリズムは非常に複雑なものとなっている。しかし、本章では、2章で述べた収束定理をもとに比較的単純な議論によって超2次収束性が証明できることが示されている。

第6章「固有値計算のためのQR法の基本性質」では、QR法の歴史やアルゴリズムについて説明し、基本的な収束定理について述べている。

第7章「Wilkinsonシフト付QR法の収束速度の完全解析」では、対称3重対角行列に対するWilkinsonシフト付きQR 法の大域的収束速度の解析を行っている。先行研究により、その大域的収束速度は行列に依存して2次の場合、3次の場合に分類されることが知られていたが、本論文では、先行研究において2次収束までしか理論保証されていない行列の族に3次収束するものが含まれていることを指摘し、大域的収束次数が、2次となる場合、3次となる場合を完全に分類する収束定理を与えている。

第8章「Wilkinson型マルチシフトQR法」では、対称3重対角行列に対するWilkinsonシフトをマルチシフトになるように拡張したWilkinson型マルチシフトQR法を提案し、このWilkinson型マルチシフトQR法が大域的収束することを示している。収束性の良いWilkinsonシフトをマルチシフトに拡張するという発想は甚だ自然であり、Wilkinson型マルチシフトQR法の収束の振る舞いも自然であることが示されている。

以上を要するに、本論文は、特異値および固有値を計算する代表的なアルゴリズムであるdqds法およびQR法の大域的収束性について理論的に詳細に論じ、精緻かつ明快な結果を与えており、数理情報学の重要な分野である数値解析学の発展に大きく寄与するものである。

よって本論文は博士(情報理工学)の学位請求論文として合格と認められる。