LU分解は行列を下三角行列と上三角行列の積で表す方法でしたが、行・列の入れ替えを行わない場合と行う場合を区別する場合、後者をPLU分解（PLU decomposition/factorization）、LUP分解、部分ピボット選択付きLU分解などとよびます。
ピボットとは行簡約行列の主成分のことでした。行簡約階段形の正方行列であれば対角成分を指します。
別の行と入れ替えてピボットとする場合、これもピボットあるいはピボット選択とよびます。
LU分解を行えない場合でもPLU分解を行うことができる場合があります。
例えば次のような行列は、このままでは下三角行列と上三角行列に分解することはできません。
第\(1\)行と第\(2\)行を入れ替えるのであれば下三角行列と上三角行列に分解することは可能です。
また、数値計算においては行の並びによって丸め誤差の影響が大きくなることがあるため、これを避けるために行を入れ替える必要がある場合もあります。
これらのような目的で用いられるのがPLU分解です。
※行だけではなく列も入れ替えること（完全ピボット選択付きLU分解）も可能ですが、ここではPLU分解についてのみ述べます。また、基本的な原理のみを述べ、数値計算の手法などについては触れません。
方法
\(2\)行の入れ替えと等価な基本行列を\(P_1,P_2,P_3\)、ある行を定数倍して別の行に加える操作と等価な基本行列を\(L_1,L_2,L_3\)とし、これらにより以下のように上三角行列が得られたとします。
$$L_3P_3L_2P_2L_1P_1 A=U$$
\(L_3P_3L_2P_2L_1P_1\)が下三角行列であればこれを\(L^{-1}\)として\(A=LU\)にできるのですが、下三角行列であるとは限りません。
そこで、\(L_3P_3L_2P_2L_1P_1\)を下三角行列ではない行列と下三角行列に分離します。
\(P_1,P_2,P_3\)はそれぞれ\(2\)つの行を入れ替える基本行列なので、その逆行列は同じ行列です。つまり\(P_1P_1=I,\ P_2P_2=I,\ P_3P_3=I\)です。これらを上の式に挿入して、
$$L_3P_3L_2(P_3P_3)P_2L_1(P_2(P_3P_3)P_2)P_1 A=U$$
とすることができます。括りを変え、
$$(L_3)(P_3L_2P_3)(P_3P_2L_1P_2P_3)P_3P_2P_1 A=U$$
それぞれの括弧内を、
\begin{align}
L_3^{\prime}&=L_3\\
L_2^{\prime}&=P_3L_2P_3\\
L_1^{\prime}&=P_3P_2L_1P_2P_3\\
\end{align}
と置き換えると、
$$L_3^{\prime}L_2^{\prime}L_1^{\prime}P_3P_2P_1 A=U$$
さらに、
$$L=(L_3^{\prime}L_2^{\prime}L_1^{\prime})^{-1}$$
$$P=P_3P_2P_1$$
とすると、
$$PA=LU$$
と表すことができます。
\(L_3^{\prime}\)、\(L_2^{\prime}\)、\(L_1^{\prime}\)が下三角行列であればそれらの積も下三角行列であり、その逆数である\(L\)も下三角行列です。
以上により\(LU\)分解ができます。
\(L\)が下三角行列である理由は補足1を参照ください。
例
以下の行列を\(LU\)分解します。
\begin{align}
A=\begin{pmatrix}
7&1&5&4\\
7&5&9&6\\
42&10&37&34\\
21&15&45&73
\end{pmatrix}
\end{align}
(1) \(U\)の計算
\(A\)に\(L_{i}\)や\(P_{i}\)を掛けた行列を順に\(A^{(j)}\)とします。
第\(3\)行を第\(1\)行と入れ替えて第\(1\)列のピボットとするため、\(P_1\)を掛けます。
\begin{align}
A^{(1)}&=P_1 A\\&=
\begin{pmatrix}
0&0&1&0\\
0&1&0&0\\
1&0&0&0\\
0&0&0&1
\end{pmatrix}
\begin{pmatrix}
7&1&5&4\\
7&5&9&6\\
42&10&37&34\\
21&15&45&73
\end{pmatrix}\\
&=\begin{pmatrix}
42&10&37&34\\
7&5&9&6\\
7&1&5&4\\
21&15&45&73
\end{pmatrix}
\end{align}
第\(1\)列の第\(2-4\)行を消去するため\(L_1\)を掛けます。\(1\)つの成分だけではなく\(1\)度で\(3\)つの成分を消去している点に注意してください。\(L_1\)はそれぞれの基本行列の積です。
\begin{align}
A^{(2)}&=L_1 A^{(1)}\\&=
\begin{pmatrix}
1&0&0&0\\
-1/6&1&0&0\\
-1/6&0&1&0\\
-1/2&0&0&1
\end{pmatrix}
\begin{pmatrix}
42&10&37&34\\
7&5&9&6\\
7&1&5&4\\
21&15&45&73
\end{pmatrix}\\
&=
\begin{pmatrix}
42&10&37&34\\
0&10/3&17/6&1/3\\
0&-2/3&-7/6&-5/3\\
0&10&53/2&56
\end{pmatrix}
\end{align}
第\(4\)行を第\(2\)行と入れ替えて第\(2\)列のピボットとするため\(P_2\)を掛けます。
\begin{align}
A^{(3)}&=P_2 A^{(2)}\\&=
\begin{pmatrix}
1&0&0&0\\
0&0&0&1\\
0&0&1&0\\
0&1&0&0
\end{pmatrix}
\begin{pmatrix}
42&10&37&34\\
0&10/3&17/6&1/3\\
0&-2/3&-7/6&-5/3\\
0&10&53/2&56
\end{pmatrix}\\
&=
\begin{pmatrix}
42&10&37&34\\
0&10&53/2&56\\
0&-2/3&-7/6&-5/3\\
0&10/3&17/6&1/3\\
\end{pmatrix}
\end{align}
第\(2\)列の第\(3,4\)行を消去するため\(L_2\)を掛けます。
\begin{align}
A^{(4)}&=L_2 A^{(3)}\\&=
\begin{pmatrix}
1&0&0&0\\
0&1&0&0\\
0&1/15&1&0\\
0&-1/3&0&1
\end{pmatrix}
\begin{pmatrix}
42&10&37&34\\
0&10&53/2&56\\
0&-2/3&-7/6&-5/3\\
0&10/3&17/6&1/3\\
\end{pmatrix}\\
&=
\begin{pmatrix}
42&10&37&34\\
0&10&53/2&56\\
0&0&3/5&31/15\\
0&0&-6&-55/3\\
\end{pmatrix}
\end{align}
第\(3\)行を第\(4\)行と入れ替えて第\(3\)列のピボットにするため\(P_3\)を掛けます。
\begin{align}
A^{(5)}&=P_3 A^{(4)}\\&=
\begin{pmatrix}
1&0&0&0\\
0&1&0&0\\
0&0&0&1\\
0&0&1&0
\end{pmatrix}
\begin{pmatrix}
42&10&37&34\\
0&10&53/2&56\\
0&0&3/5&31/15\\
0&0&-6&-55/3\\
\end{pmatrix}\\
&=
\begin{pmatrix}
42&10&37&34\\
0&10&53/2&56\\
0&0&-6&-55/3\\
0&0&3/5&31/15\\
\end{pmatrix}
\end{align}
第\(3\)列の第\(4\)行を消去するため\(L_3\)を掛けます。
\begin{align}
A^{(6)}&=L_3 A^{(5)}\\&=
\begin{pmatrix}
1&0&0&0\\
0&1&0&0\\
0&0&1&0\\
0&0&1/10&1
\end{pmatrix}
\begin{pmatrix}
42&10&37&34\\
0&10&53/2&56\\
0&0&-6&-55/3\\
0&0&3/5&31/15\\
\end{pmatrix}\\
&=
\begin{pmatrix}
42&10&37&34\\
0&10&53/2&56\\
0&0&-6&-55/3\\
0&0&0&7/30\\
\end{pmatrix}
\end{align}
この\(A^{(6)}\)が\(U\)です。
\begin{align}
U=
\begin{pmatrix}
42&10&37&34\\
0&10&53/2&56\\
0&0&-6&-55/3\\
0&0&0&7/30\\
\end{pmatrix}
\end{align}
(2)\(L\)の計算
実は\(L_2’=P_3L_2P_3=P_3L_2,\ L_1’=P_3P_2L_1P_2P_3=P_3P_2L_1\)と省略できるのですが、ここでは省略せずに書いています。補足1を読んでいただければ省略できる理由はわかるのではないかと思いますが、詳細は省略します。
\begin{align}
L_3^{\prime}&=L_3
=\begin{pmatrix}
1&0&0&0\\
0&1&0&0\\
0&0&1&1\\
0&0&1/10&1
\end{pmatrix}\\ \\
L_2^{\prime}&=P_3L_2P_3\\
&=
\begin{pmatrix}
1&0&0&0\\
0&1&0&0\\
0&0&0&1\\
0&0&1&0
\end{pmatrix}
\begin{pmatrix}
1&0&0&0\\
0&1&0&0\\
0&1/15&1&0\\
0&-1/3&0&1
\end{pmatrix}
\begin{pmatrix}
1&0&0&0\\
0&1&0&0\\
0&0&0&1\\
0&0&1&0
\end{pmatrix}\\
&=
\begin{pmatrix}
1&0&0&0\\
0&1&0&0\\
0&-1/3&1&0\\
0&1/15&0&1
\end{pmatrix}\\ \\
L_1^{\prime}&=P_3P_2L_1P_2P_3\\
&=\scriptsize{
\begin{pmatrix}
1&0&0&0\\
0&1&0&0\\
0&0&0&1\\
0&0&1&0
\end{pmatrix}
\begin{pmatrix}
1&0&0&0\\
0&0&0&1\\
0&0&1&0\\
0&1&0&0
\end{pmatrix}
\begin{pmatrix}
1&0&0&0\\
-1/6&1&0&0\\
-1/6&0&1&0\\
-1/2&0&0&1
\end{pmatrix}
\begin{pmatrix}
1&0&0&0\\
0&0&0&1\\
0&0&1&0\\
0&1&0&0
\end{pmatrix}
\begin{pmatrix}
1&0&0&0\\
0&1&0&0\\
0&0&0&1\\
0&0&1&0
\end{pmatrix}
}\\
&=
\begin{pmatrix}
1&0&0&0\\
-1/2&1&0&0\\
-1/6&0&1&0\\
-1/6&0&0&1
\end{pmatrix}\\ \\
\end{align}
以上より、\(L\)を求めます。本ページ冒頭では
$$L=(L_3^{\prime}L_2^{\prime}L_1^{\prime})^{-1}$$
としましたが、積で表される行列の逆行列は個別の逆行列を入れ替えて掛けたものなので、
$$L=L_1^{\prime-1}L_2^{\prime-1}L_3^{\prime-1}$$
とできます。
この場合は\(L_1,L_2,L_3\)は単位行列に特定の行のみ定数を追加しただけの行列なので、その逆行列は定数の符号を反転するだけで済みます。
また、積は単位行列にこれらの定数を重ね合わせることで求められます（LU分解参照）。
\begin{align}
L&=(L_3^{\prime}L_2^{\prime}L_1^{\prime})^{-1}\\
&=L_1^{\prime-1}L_2^{\prime-1}L_3^{\prime-1}\\
&=
\begin{pmatrix}
1&0&0&0\\
-1/2&1&0&0\\
-1/6&0&1&0\\
-1/6&0&0&1
\end{pmatrix}^{-1}
\begin{pmatrix}
1&0&0&0\\
0&1&0&0\\
0&-1/3&1&0\\
0&1/15&0&1
\end{pmatrix}^{-1}
\begin{pmatrix}
1&0&0&0\\
0&1&0&0\\
0&0&1&1\\
0&0&1/10&1
\end{pmatrix}^{-1}\\
&=
\begin{pmatrix}
1&0&0&0\\
1/2&1&0&0\\
1/6&1/3&1&0\\
1/6&-1/15&-1/10&1
\end{pmatrix}
\end{align}
(3)\(P\)の計算
\begin{align}
P&=P_3P_2P_1\\
&=
\begin{pmatrix}
1&0&0&0\\
0&1&0&0\\
0&0&0&1\\
0&0&1&0
\end{pmatrix}
\begin{pmatrix}
1&0&0&0\\
0&0&0&1\\
0&0&1&0\\
0&1&0&0
\end{pmatrix}
\begin{pmatrix}
0&0&1&0\\
0&1&0&0\\
1&0&0&0\\
0&0&0&1
\end{pmatrix}\\
&=
\begin{pmatrix}
0&0&1&0\\
0&0&0&1\\
0&1&0&0\\
1&0&0&0
\end{pmatrix}
\end{align}
(4)PLU分解の結果
以上より\(PA=LU\)は、
\begin{align}
\scriptsize{
\begin{pmatrix}
0&0&1&0\\
0&0&0&1\\
0&1&0&0\\
1&0&0&0
\end{pmatrix}
\begin{pmatrix}
7&1&5&4\\
7&5&9&6\\
42&10&37&34\\
21&15&45&73
\end{pmatrix}
=
\begin{pmatrix}
1&0&0&0\\
1/2&1&0&0\\
1/6&1/3&1&0\\
1/6&-1/15&-1/10&1
\end{pmatrix}
\begin{pmatrix}
42&10&37&34\\
0&10&53/2&56\\
0&0&-6&-55/3\\
0&0&0&7/30\\
\end{pmatrix}
}
\end{align}
となります。
補足
補足1 \(L\)が下三角行列であることの確認
[su_spoiler title=”Lが下三角行列であることの確認” open=”no” style=”default” icon=”plus” anchor=”” anchor_in_url=”no” class=””]
\(L\)が下三角行列であることをを前項の例に沿って確認してみましょう。
以下のように定義したので、
$$L=(L_3^{\prime}L_2^{\prime}L_1^{\prime})^{-1}$$
\(L_1^{\prime},L_2^{\prime},L_3^{\prime}\)それぞれが下三角行列であれば\(L\)も下三角行列であるといえます。そこでその\(1\)つの
$$L_2^{\prime}=P_3L_2P_3$$
が下三角行列であること確認します。複雑なので\(L_2,L_2P_3,P_3L_2P_3\)の順にみていきます。
この後で\(A^{(3)}\)と\(A^{(4)}\)が出てきますが、これらは\(A\)から\(U\)への変形の過程で現れる行列で、以下のように\(L_2\)と\(P_3\)によって変形されます。
$$A^{(4)}=L_2 A^{(3)}$$
$$A^{(5)}=P_3 A^{(4)}$$
(1)\(L_2\)
\(L_2\)は\(A^{(3)}\)の第\(2\)列のピボットより下にある成分を消去するための基本行列の積でした。ある行を定数倍して別の行を消去する場合、基本行列は単位行列にその定数を追加したものです。この場合は下の図の水色の部分です。これらは消去する成分（ベージュ色）と同じ位置に追加されます。
消去する成分はピボット（赤色）より下にあります。正方行列の場合、ピボットは対角成分です。したがって\(L_2\)は下三角行列です。
(2)\(L_2P_3\)
以下、\(3\)つの項目に分けて説明します。
・\(P_3\)は\(L_2\)の行を入れ替える？
\(P_3\)は\(A^{(4)}\)の第\(3\)列のピボット（下の図の赤色）を別の行の成分（紫色）と入れ替えるためのものでした。
では\(L_2\)も同じように第\(3\)行と第\(4\)行が入れ替わるのでしょうか。
\(A^{(4)}\)に対しては\(P_3\)を左から掛けました。しかし\(L_2\)に対しては（\(1\)つの\(P_3\)は）右から掛けます。これは行基本変形ではなく列基本変形であると考えるべきです。
つまり、\(L_2\)に右から\(P_3\)を掛けると第\(3\)列と第\(4\)列が入れ替わります。
・\(A^{(3)}\)における消去する成分がある列と\(A^{(4)}\)におけるピボット選択をする成分がある列の位置関係
右から掛ける\(P_3\)により\(L_2\)の\((3,3)\)と\((4,4)\)の対角成分は移動しますが、定数（上の図の青色）の部分は入れ替え対象の列ではないために移動しません。これは偶然ではなく、入れ替えを行う列が定数の存在する列より必ず右にあるからです。なぜ必ず右にあるのでしょう。
\(L_{1}^{\prime},L_{2}^{\prime},L_{3}^{\prime}\)に現れる\(L\)と\(P\)の添え字を比較してみてください。必ず\(L\)の添え字が\(P\)の添え字より小さい値です。この場合であれば\(L\)は\(2\)、\(P\)は\(3\)です。
下記のように、添え字の値が小さいほど\(A^{(i)}\)に対する演算が先に行われる行列です。
\(\color{white}{\rightarrow}\)\(P_1\):第\(1\)列のピボット選択\(\rightarrow\)\(L_1\):第\(1\)列の成分消去
\(\rightarrow\)\(P_2\):第\(2\)列のピボット選択\(\rightarrow\)\(L_2\):第\(2\)列の成分消去
\(\rightarrow\)\(P_3\):第\(3\)列のピボット選択\(\rightarrow\)\(L_3\):第\(3\)列の成分消去
したがって\(A^{(4)}\)におけるピボット選択を行う列は、\(A^{(3)}\)における消去する成分のある列より右になります。
・\(L_2\)における定数がある列と入れ替えが行われる列の位置関係
\(L_2\)における定数（青色）は\(A^{(3)}\)における消去される成分（ベージュ色）と同じ位置なので、前者の列を\(c_{le}\)、後者の列を\(c_{ai}\)とすると、
$$c_{le}=c_{ae}$$
入れ替えを行う成分がある列を\(c_{ai}\)とすると、
$$c_{ae} \lt c_{ai}$$
正方行列におけるピボットは対角成分なので行を入れ替えるピボットがある行を\(r_{ai1}\)とすると、
$$c_{ai}=r_{ai1}$$
入れ替え先の行を\(r_{ai2}\)とすると、
$$r_{ai1} \lt r_{ai2}$$
\(L_2\)における入れ替えを行う列のうち左側を\(c_{li1}\)、右側を\(c_{li2}\)とすると、
$$c_{li1}=r_{ai1}$$
$$c_{li2}=r_{ai2}$$
以上より、
$$c_{le}=c_{ae} \lt c_{ai} = r_{ai1} = c_{li1} \lt r_{ai2} = c_{li2}$$
つまり、
$$c_{le} \lt c_{i1} \lt c_{i2}$$
となります。
(3) \(P_3L_2P_3\)
\(L_2P_3\)に対しては左から\(P_3\)を掛けるのでこれを行の入れ替えと考えることができます。
\(c_{le}\)の列の対角成分がある行を\(r_{le}\)、\(A^{(3)}\)における消去を行うための基準となるピボットがある行を\(r_{ae}\)とすると、
$$r_{le}=r_{ae}$$
ピボット選択を行う列は消去を行う列より右にあるので、
$$r_{ae} \lt r_{ai1} \lt r_{ai2}$$
\(L_2P_3\)において入れ替えを行う行のうち上側を\(r_{li1}\)、下側を\(r_{li2}\)とすると、
$$r_{li1}=r_{ai1}$$
$$r_{li2}=r_{ai2}$$
したがって、
$$r_{le} =r_{ae} \lt r_{ai1} =r_{li1}\lt r_{li2}=r_{ai2}$$
つまり、
$$r_{le} \lt r_{li1} \lt r_{li2}$$
したがって、\(P_3\)を左から掛けることにより\(L_2P_3\)の中の定数の成分は移動することがありますが、それらは必ず対角成分より下で行われます。
以上より\(L_2^{\prime}=P_3L_2P_3\)は下三角行列であることがわかりました。
\(L_3,L_1’\)も同様です。いずれも下三角行列なので\(L\)は下三角行列です。
[/su_spoiler]
補足2 PLU分解の演算順序
本ページでは、PLU分解を以下の手順で行うことを前提として述べています。
\(\color{white}{\rightarrow}\)\(P_1\):第\(1\)列のピボット選択\(\rightarrow\)\(L_1\):第\(1\)列の成分消去
\(\rightarrow\)\(P_2\):第\(2\)列のピボット選択\(\rightarrow\)\(L_2\):第\(2\)列の成分消去
\(\rightarrow\)\(P_3\):第\(3\)列のピボット選択\(\rightarrow\)\(L_3\):第\(3\)列の成分消去
例えば、第\(1\)列のピボット選択と第\(1\)列の成分消去を行った後にもう一度第\(1\)列のピボット選択を行うと\(L\)が下三角行列にならないかもしれないので注意してください。