SciPy的LU分解置換矩陣

Question

據我所知LU分解，這意味着一個矩陣A可被寫爲A = LU爲下三角矩陣L和上三角矩陣U.

但是，函數在涉及LU因子分解（lu,lu_factor, lu_solve）的scipy中似乎涉及第三個矩陣P，使得A = PLU和P是置換矩陣（並且L，U如前所述）。

這個置換矩陣的要點是什麼？如果一個「真正的」LU分解總是可能的話，爲什麼有P是除了單位矩陣之外的東西？

Answer 1

不是所有的矩陣都有LU分解。但是每個方形矩陣至少有一個具有LU分解的行排列。

Answer 2

考慮高斯消除過程。如果樞軸上有一個零點，你會怎麼做？您必須切換行，這會引入P矩陣。

此外，非常小的非零樞紐值會導致浮點環境中的數值不穩定。基本算法通過在數據透視列中搜索具有最大絕對值的條目並使用數據透視行切換相應的行來避免這種情況。

該開關可能很昂貴，所以通常最大的絕對值輸入必須大於主軸的絕對值一定的因數，例如， 10，爲切換髮生。這減少了開關的數量，但保留了那些限制浮點錯誤所必需的開關。

在這個問題上搜索任何數量的優秀資源的「部分樞軸LU分解」。

注意：由於P是置換矩陣，因此P^T = P ^（ - 1）。因此，Ax = b與LUx = P^T b有相同的解決方案（有些實現返回你稱之爲P的東西，而有些實現返回你稱之爲P^T的東西並稱之爲P - 確保你知道它是哪一個是，這是'PA = LU'和'A = PLU'之間的差異 - 在每種情況下P都不相同）。

Answer 3

要添加到@DomJack： 更改置換（又稱重新排序）也會影響L和U因子中非零的數量。因此，重新排序可以導致更有效的因式分解。