зачем в lu разложении перестановачная матрица?

[reseacher2011]

Почему метод LU разложения возвращает перестановочную матрицу, и только в этом случае LU-разложение происходит верно?

octave:4> [L,U,P]=lu([1 2 3; 4 5 6; 7 8 9])
L =

   1.00000   0.00000   0.00000
   0.14286   1.00000   0.00000
   0.57143   0.50000   1.00000

U =

   7.00000   8.00000   9.00000
   0.00000   0.85714   1.71429
   0.00000   0.00000  -0.00000

P =

Permutation Matrix

   0   0   1
   1   0   0
   0   1   0

octave:5> [L,U]=lu([1 2 3; 4 5 6; 7 8 9])
L =

   0.14286   1.00000   0.00000
   0.57143   0.50000   1.00000
   1.00000   0.00000   0.00000

U =

   7.00000   8.00000   9.00000
   0.00000   0.85714   1.71429
   0.00000   0.00000  -0.00000

ну, например, в книжке Вержбицкого В.М. Численные методы 2005, приводится на стр.66 приводятся четкие формулы для вычисления коэффициентов матрицы L и U:

$$ u_{ij}=a_{ij}-\sum\limits_{k=1}^{i-1}l_{ik}u_{kj}, \quad l_{ij}=\frac{1}{u_{ij}}\left( a_{ij} - \sum\limits_{k=1}^{j-1} l_{ik} u_{kj} \right) $$

нет никаких матриц перестановки.

[Vassil]

Посмотрите внимательно что написано в Хелп-е например бесплатного Scilab:

[L,U]= lu(A) produces two matrices L and U such that A = L*U with U upper triangular and L a general matrix without any particular structure. In fact, the matrix A is factored as E*A=B*U where the matrix B is lower triangular and the matrix L is computed from L=E'*B.

...

[L,U,E]= lu(A) produces three matrices L, U and E such that E*A = L*U with U upper triangular and E*L lower triangular for a permutation matrix E.

[reseacher2011]

Vassil в сообщении #482953 писал(а):

[L,U,E]= lu(A) produces three matrices L, U and E such that E*A = L*U with U upper triangular and E*L lower triangular for a permutation matrix E.

Так вопрос как раз в том, что : я хочу найти алгоритм который дает [L,U,E] и понять что это за матрица перестановок и зачем она нужна. В классических книгах ее нет.

[Vassil]

Можете увидеть то, что Вас ивтересует например в книге

Дж. Голуб, Ч.Ван Лоун Матричные вычисления, Москва "Мир", 1999, первод с английского под редакцией В. В. Воеводина

от стр. 107 и далее.

[Yuri Gendelman]

reseacher2011 в сообщении #482547 писал(а):

Почему метод LU разложения возвращает перестановочную матрицу, и только в этом случае LU-разложение происходит верно?

Для повышения точности решения численные методы алгебры часто реализуются с т.н. "выбором главного элемента". При этом на каждом шаге решения выполняется перестановка строк и/или столбцов исходной матрицы. Тогда на выходе получается LU-разложение не исходной матрицы, а матрицы с переставленными строками/столбцами.
Матрица перестановок необходима для восстановления решения для исходной матрицы.