1 基本概念
三角分解は、行列を上三角行列や下三角行列、あるいはそれらに近い構造の積として表す手法の総称である。多くの場合、元の行列を直接扱うよりも、階段状に整理された因子へ分けることで、連立一次方程式の解法、行列式の算出、逆行列の評価を効率化する。数値線形代数では、計算の見通しをよくし、誤差の蓄積を抑える基礎技術として位置づけられる。
1.1 定義
一般には、正方行列 A を上三角行列 U と下三角行列 L の積に分ける操作を指す。ただし、文脈によっては、対角行列を含む分解や、対称性・正定値性を利用した分解も含めて三角分解と呼ぶことがある。どの形式を採るかは、対象行列の性質と計算目的によって決まる。
1.2 分解の目的
主な目的は、複雑な行列計算を扱いやすい段階的な問題へ置き換えることにある。三角行列は前進代入や後退代入によって容易に解けるため、連立方程式の処理が簡潔になる。また、分解後は行列式が対角成分の積として求められ、逆行列の構成や固有値計算の下準備としても役立つ。
1.3 記法と前提条件
記法は分野ごとに差があるが、L は下三角、U は上三角を表すのが一般的である。行列が正方であることを前提とする場合が多いが、長方行列に対しても関連する分解が定義される。さらに、成分の零・非零の配置、対称性、正則性、正定値性などが成立条件として重要になる。
2 代表的な三角分解
三角分解には複数の代表形があり、行列の構造に応じて使い分けられる。単純な上三角・下三角の形に加え、ピボット操作を伴うもの、対称行列向けのもの、正定値行列に特化したものがよく知られている。これらは互いに独立ではなく、共通の消去原理や因子化の考え方を共有している。
2.1 上三角分解
上三角分解は、消去操作の結果として上三角成分を主要因子に取り出す形で現れる。行列の下側を順に消していくことで、計算の最後に上三角行列が残る。連立方程式では、未知数を後ろから決める後退代入と相性がよい。
2.2 下三角分解
下三角分解は、上三角とは逆に、下側へ情報を蓄える形の因子化である。前進代入と結びつきやすく、段階的に未知数を確定できる。理論上は上三角分解と対称的な位置づけにあり、転置を通じて互いに対応することも多い。
2.3 ルー分解
ルー分解は、行列を下三角行列 L と上三角行列 U に分ける代表的な方法である。ガウス消去法を因子化として整理したものであり、連立一次方程式の反復的な解法や複数右辺への再利用に強みを持つ。計算の途中で得られる消去係数が L に、最終的な残差構造が U に対応する。
2.3.1 ピボット選択
ピボット選択は、消去の各段階で基準となる成分を選ぶ操作である。適切なピボットを採ることで、ゼロ割や数値誤差の増大を避けやすくなる。実装では部分ピボットや完全ピボットが用いられ、安定性と計算負荷の折り合いを取る。
2.3.2 存在条件
ルー分解は、一般にはすべての行列にそのまま適用できるわけではない。途中の主小行列式が消えないことや、適切な行交換を許すことが、存在の重要な条件となる。正則な行列では、ピボット操作を認めることで分解可能になる場合が多い。
2.4 ショール分解
ショール分解は、複素行列や実行列に対して、対称成分を保ちながら分解を行う考え方に属する。文脈によって名称の扱いが異なるが、特定の対称構造を反映した因子化として使われることがある。対称性を前提とするため、一般のLU分解よりも構造保存の利点が大きい。
2.5 チョレスキー分解
チョレスキー分解は、対称かつ正定値な行列を、ある下三角行列とその転置の積に分ける方法である。通常、A = LL^T の形で表され、LU分解より少ない計算で済むことが多い。正定値性があるため、平方根を含む因子化であっても実用上扱いやすい。
2.5.1 対称行列への適用
対称行列では、上側と下側の情報が重複するため、片側だけを計算すれば十分になる。チョレスキー分解はこの冗長性を削減し、記憶量と演算量を抑える。対称構造を壊さない点も大きな利点である。
2.5.2 正定値条件
この分解が成立するには、対象行列が正定値でなければならない。正定値でない場合、計算途中で平方根が定義できない、あるいは因子が実数として構成できないことがある。したがって、適用前には行列の性質確認が不可欠である。
3 理論的性質
三角分解は単なる計算手順ではなく、行列の構造を反映する理論的対象でもある。因子の一意性、存在の可否、階数や特異性との関係は、分解の意味を理解するうえで重要である。これらの性質は、アルゴリズムの設計にも直接影響する。
3.1 一意性
一意性は、分解がどの程度まで独立に定まるかを示す概念である。対角成分の規約を置くと、一意性が得られる場合がある。反対に、対角に自由度が残る形式では、複数の分解が同じ行列に対応しうる。
3.2 存在条件
分解の存在は、行列の正則性、主小行列式、対称性、正定値性などに左右される。一般のLU分解では、途中の消去で零ピボットが現れると、そのままでは進められない。条件を満たさない場合でも、行列の並べ替えや別形式の分解で回避できることがある。
3.3 行列の階数との関係
階数は、分解後の因子に現れる非零の独立成分数と結びつく。特異行列では、三角因子の対角に零が現れることがあり、これは解の非一意性や存在しない解を示唆する。したがって、分解は階数判定の補助手段としても用いられる。
3.4 行列式と逆行列への応用
三角行列の行列式は対角成分の積で与えられるため、分解後は元の行列式を容易に計算できる。逆行列についても、三角因子ごとに解を求めることで間接的に構成可能である。ただし、実際の数値計算では、逆行列を明示的に作るより、連立方程式を直接解くほうが安定な場合が多い。
4 計算法
三角分解は、理論的な存在だけでなく、実際にどう計算するかが重要である。消去法、代入法、反復計算との組み合わせにより、高速かつ安定な処理が実現される。演算量と誤差制御の両面から、実装上の工夫が積み重ねられてきた。
4.1 ガウス消去法との関係
ガウス消去法は、三角分解を構成する基本的手続きとみなせる。行基本変形によって下側成分を消し、最終的に上三角形へ変換する過程は、LU分解そのものの計算過程に対応する。つまり、分解は消去法を再利用可能な因子に整理した表現である。
4.2 前進代入
前進代入は、下三角行列を含む方程式を上から順に解く方法である。最初の未知数から順次値を確定できるため、手順が単純で計算しやすい。ルー分解やチョレスキー分解の前半でしばしば利用される。
4.3 後退代入
後退代入は、上三角行列に対して最後の未知数から順に解く手続きである。各段階で既知の変数を代入しながら進めるため、アルゴリズムが明快である。三角分解の後段では、この方法によって最終解が得られる。
4.4 計算量
三角分解の計算量は、行列サイズが n のとき概ね三次オーダーで増加する。とはいえ、一度分解しておけば、複数の右辺に対しては代入だけで解けるため、総合的には有利である。大規模計算では、この再利用性が特に重要になる。
4.5 数値安定性
数値安定性は、丸め誤差が計算結果に与える影響を評価する観点である。ピボット選択や対称構造の活用は、誤差の増幅を抑えるための代表的対策である。安定性が低い分解を無批判に使うと、理論上は正しい手順でも実用的には不十分な結果になることがある。
5 応用
三角分解は、純粋な行列論だけでなく、工学・物理・統計・情報処理など幅広い分野で使われる。大規模な数値問題を段階的に処理できるため、実用計算の中核を担う。特に、同じ行列に対して多数の計算を繰り返す場面で効果が大きい。
5.1 連立一次方程式の解法
連立一次方程式では、まず行列を三角因子へ分け、その後に前進代入と後退代入で解を求める。これにより、直接解法として高い効率が得られる。右辺ベクトルが複数ある場合は、分解を使い回すことで計算の重複を減らせる。
5.2 最小二乗法
最小二乗法では、過剰決定系を扱うために、正規方程式やQR系の方法と関連する分解が用いられる。三角化は、誤差を含むデータから最適解を求める際の計算骨格を与える。安定性の高い手順を選ぶことで、推定結果の信頼性が向上する。
5.3 固有値問題への利用
固有値計算では、三角分解が反復法や変換法の内部で重要な役割を果たす。行列を三角形へ近づけることで、固有値の抽出がしやすくなる。特に大規模問題では、直接計算よりも分解を介したアルゴリズムが現実的である。
5.4 科学技術計算
数値シミュレーション、構造解析、電磁場計算、統計モデリングなどでは、巨大な線形方程式系が頻出する。三角分解は、それらを解く基本モジュールとして組み込まれている。高速化と安定化の両立により、実用計算の基盤を支えている。
6 変種と拡張
三角分解は、単一の形式にとどまらず、実用上の要請に応じて多様に拡張される。ブロック構造、疎性、行列の並び順、反復法との併用などが代表的である。これらの拡張は、大規模かつ複雑な問題への対応力を高める。
6.1 ブロック三角分解
ブロック三角分解は、行列を小さな部分行列の集合として扱う方法である。個々の成分ではなくブロック単位で三角化するため、メモリ効率や並列計算との相性がよい。大規模行列では、構造を保ちながら処理を進める利点がある。
6.2 疎行列に対する分解
疎行列では、零成分が多いため、通常の分解をそのまま行うと不要な非零要素が増えやすい。疎性を保つ工夫を施した分解では、計算量と記憶量を抑えられる。実際の応用では、この性質が計算可能性を左右することも多い。
6.3 行列の順序付け
順序付けは、行や列の並べ替えによって分解の性質を改善する操作である。適切な順序を選ぶと、ピボットの安定化やフィルインの削減が期待できる。疎行列では特に重要で、前処理の一部として扱われることが多い。
6.4 繰り返し計算法との併用
繰り返し計算法では、三角分解が前処理として用いられることがある。近似的な因子化を先に作っておくことで、反復の収束を速めやすくなる。直接法と反復法の中間に位置する実践的手段として、多くの大規模問題で採用されている。
</INTERNAL_LINK_CANDIDATES> LU分解（行列を下三角行列と上三角行列へ因子化する方法） ガウス消去法（連立一次方程式を段階的に解く消去手順） 前進代入（下三角行列の方程式を先頭から順に解く方法） 後退代入（上三角行列の方程式を末尾から逆向きに解く方法） ピボット選択（消去計算で基準成分を選び安定性を高める操作） チョレスキー分解（対称正定値行列を下三角因子とその転置に分ける方法） 正定値行列（非零ベクトルに対し二次形式が正になる行列） 固有値問題（行列の固有値と固有ベクトルを求める問題） 最小二乗法（誤差の二乗和を最小にする推定法） 疎行列（零成分が非常に多い行列） ブロック行列（行列を部分行列に区切って扱う表現） 順序付け（行や列の並べ替えによる構造改善） 数値安定性（丸め誤差に対する計算の頑健さ） フィルイン（消去により新たに現れる非零成分） 行列式（行列から定まるスカラー量） 逆行列（掛け合わせると単位行列になる行列） 正則性（逆行列が存在する性質） 階数（行列が持つ独立な情報の次元） 部分ピボット（各段階で列内の最大要素を選ぶピボット法） QR分解（直交行列と上三角行列への分解）