scipy LU分解置换矩阵 [英] scipy LU factorization permutation matrix

问题描述

据我了解LU分解，这意味着对于下三角矩阵L和上三角矩阵U，矩阵A可以写成A = LU.

但是，scipy中与LU因式分解相关的功能( lu ，

解决方案

考虑高斯消除过程.如果枢轴上有零，该怎么办?您必须切换行，这会引入P矩阵.

此外，非常小的非零枢轴值会导致浮点环境中的数值不稳定.基本算法通过在数据透视表列中搜索具有最大绝对值的条目并将相应的行与数据透视表行切换来避免这种情况.

此开关可能很昂贵，因此通常最大输入的绝对值必须比支点的绝对值大一些，例如10，进行切换.这样可以减少开关的数量，但可以保留限制浮点误差所需的那些开关.

搜索部分透视的LU分解"以查找有关此问题的大量良好资源.

注意:由于P是置换矩阵，所以P ^ T = P ^(-1).因此，Ax = b与LUx = P ^ T b具有相同的解决方案(某些实现返回您称为P的内容，而其他实现则返回您称为P ^ T的内容并将其称为P －确保您知道它是哪一个是."PA = LU"和"A = PLU"之间的区别-每种情况下P都不相同.

As I understand LU factorization, it means that a matrix A can be written as A = LU for a lower-triangular matrix L and an upper-triangular matrix U.

However, the functions in scipy relating to LU factorizations (lu, lu_factor, lu_solve) seem to involve a third matrix P, such that A = PLU and P is a permutation matrix (and L, U are as before).

What is the point of this permutation matrix? If a "true" LU factorization is always possible, why ever have P be something other than the identity matrix?

解决方案

Consider the Gaussian elimination process. What do you do if there's a zero on the pivot? You have to switch rows, which introduces a P matrix.

Moreso, very small non-zero pivot values lead to numerical instability in a floating point environment. Basic algorithms avoid this by searching for the entry with the largest absolute value in the pivot column and switching the corresponding row with the pivot row.

This switch can be expensive, so often the largest absolute value entry will have to be bigger than the pivot's absolute value by some factor, e.g. 10, for the switch to occur. This reduces the number of switches, but keeps those that would be necessary to limit floating point errors.

Search "LU factorization with partial pivoting" for any number of good resources on the issue.

Note: Since P is a permutation matrix, P^T = P^(-1). Thus, Ax = b has the same solution as LUx = P^T b (some implementations return what you've called P, while others return what you'd call P^T and call it P - make sure you know which one it is. It's the difference betwee 'PA = LU', and 'A = PLU' - the P's are not the same in each case).

这篇关于scipy LU分解置换矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！