英文:
Why does pivoting code bring failure to my LU decomposition?
问题
Sure, here's the translated content without the code parts:
Before speaking, I am writing this with a translator, not an English speaker. Therefore, I ask for your understanding even if my English is terrible.
After learning how to write a non-pivoting LU-decomposition code, I decided to try to write an LU-decomposition code that uses pivoting for homework. Since my non-pivoting code went well as below, so I thought it would be easy to make a pivoting LU-decomposition code. But it went bad, really bad...
My code is following. Please let me know where this code fails. I don't know why such a serious failure occurs even though I only put in the pivot part.
I tested with a 4x4 matrix A like this, and the answer comes like this. Really bad.
Tell me which part is the problem. All kinds of help are welcome. I will thank you in advance.
英文:
Before speaking, I am writing this with a translator, not an English speaker. Therefore, I ask for your understanding even if my English is terrible.
After learning how to write a non-pivoting LU-decomposition code, I decided to try to write a LU-decomposition code that uses pivoting for homework.
Since my non-pivoting code went well as below, so I thought it would be easy to make a pivoting LU-decomposition code.
But it went bad, really bad...
% non-pivoting code
function x = mylu_np(A)
[m,~] = size(A);
L = eye(m); U = A(:,:);
for i = 1:m-1
for j = i+1:m
L(j,i) = U(j,i)/U(i,i);
U(j,i) = 0;
U(j,i+1:m) = U(j,i+1:m) - L(j,i)*U(i,i+1:m);
end
end
x = [L U];
end
My code is following. Please let me know where this code fails. I don't know why such a serious failure occurs even though I only put in the pivot part.
function x = mylu_pp(A)
[m,~] = size(A);
P = eye(m); L = eye(m); U = A(:,:);
for i = 1:m-1
for j = i+1:m
if abs(U(i,i)) < abs(U(j,i))
U([i j],:) = U([j i],:);
P([i j],:) = P([j i],:);
end
end
for j = i+1:m
L(j,i) = U(j,i)/U(i,i);
U(j,i) = 0;
U(j,i+1:m) = U(j,i+1:m) - L(j,i)*U(i,i+1:m);
end
end
x = [P L U];
end
I tested with 4*4 matrix A like this
A = [0.0001 -5.0300 5.8090 7.8320;
2.2660 1.9950 1.2120 8.0080;
8.8500 5.6810 4.5520 1.3020;
6.7750 -2.2530 2.9080 3.9700];
W = mylu_pp(A)
P = W(1:4,1:4); L = W(1:4,5:8); U = W(1:4,9:12);
P*A - L*U
and the answer comes like this. Really bad.
ans = [0.0000 0.0000 0.0000 0.0000;
6.7749 4.3489 3.4847 0.9967;
-2.2659 -7.0250 -1.6521 2.1754
-4.5090 2.6761 -1.8326 -3.1721]
Tell me which part is the problem. All kinds of help are welcome. I will thank you in advance.
答案1
得分: 2
The issue is related to the matrix L. When swapping rows i and j in matrix U, we also have to swap the elements in the rows i and j of matrix L, but only the elements that were updated earlier (not the entire rows):
if i > 1
L([i j], 1:i-1) = L([j i], 1:i-1);
end
The way I am thinking about it is equivalent to renaming the variables in the equation system. Assume we have the equation system: A*v = b. Using LU decomposition, we are solving the equation as: L*U*v = b.
Assume:
[x
v = y
z
w]
After swapping two rows in matrix U, we have to keep equivalence to the original equation system. The way to keep equivalence is renaming the elements in v.
When swapping row 2 with row 4, we may swap the names of y and w and get new v:
[x
v0 = w
z
y]
The equivalence to name swapping is:
- Swapping the two rows in matrix
U. - Swapping the two rows in matrix
P.
P*Areorders the rows ofAto the new "swapped order". - We also have to swap the elements in the rows of matrix
L, but only the elements that were updated earlier (not the entire row). Swapping the relevant elements in rows 2 and 4 ofLfollows the equivalence of swapping the names ofyandw.
Code sample:
A = [0.0001 -5.0300 5.8090 7.8320;
2.2660 1.9950 1.2120 8.0080;
8.8500 5.6810 4.5520 1.3020;
6.7750 -2.2530 2.9080 3.9700];
[P, L, U] = mylu_pp(A);
P*A - L*U
function [P, L, U] = mylu_pp(A)
m = size(A, 1);
P = eye(m); L = eye(m); U = A;
for i = 1:m-1
for j = i+1:m
if abs(U(i,i)) < abs(U(j,i))
U([i j],:) = U([j i],:);
P([i j],:) = P([j i],:);
if i > 1
% Swap the relevant elements "1:i-1" in the row of matrix L (only the elements that were updated until now).
L([i j], 1:i-1) = L([j i], 1:i-1);
end
end
end
for j = i+1:m
L(j,i) = U(j,i)/U(i,i);
U(j,i) = 0;
U(j,i+1:m) = U(j,i+1:m) - L(j,i)*U(i,i+1:m);
end
end
%x = [P L U];
end
Output P*A - L*U:
ans =
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
英文:
The issue is related to the matrix L.
When swapping rows i and j in matrix U, we also have to swap the elements in the rows i and j of matrix L, but only the elements that were updated earlier (not the entire rows):
if i > 1
L([i j], 1:i-1) = L([j i], 1:i-1);
end
The way I am thinking about it is equivalent to renaming the variables in the equation system.
I am not a mathematician, and my explanation is not going to be very good...
Assume we have the equation system: A*v = b.
Using LU decomposition we are solving the equation as: L*U*v = b.
Assume:
[x
v = y
z
w]
After swapping two rows in matrix U, we have to keep equivalence to the original equation system.
The way of keep equivalence is renaming the elements in v.
When swapping row 2 with row 4, we may swap the names of y and w, and get new v:
[x
v0 = w
z
y]
The equivalence to names swapping is:
- Swapping the two rows in matrix
U. - Swapping the two rows in matrix
P.
P*Areorder the rows ofAto the new "swapped order". - We also have to swap the elements in the rows of matrix
L, but only the elements that were updated earlier (not the entire row).
Swapping the relevant elements in rows 2 and 4 ofLfollows the equivalence of swapping the names ofyandw.
Code sample:
A = [0.0001 -5.0300 5.8090 7.8320;
2.2660 1.9950 1.2120 8.0080;
8.8500 5.6810 4.5520 1.3020;
6.7750 -2.2530 2.9080 3.9700];
[P, L, U] = mylu_pp(A);
P*A - L*U
function [P, L, U] = mylu_pp(A)
m = size(A, 1);
P = eye(m); L = eye(m); U = A;
for i = 1:m-1
for j = i+1:m
if abs(U(i,i)) < abs(U(j,i))
U([i j],:) = U([j i],:);
P([i j],:) = P([j i],:);
if i > 1
% Swap the relevant elements "1:i-1" in the row of matrix L (only the elements that were updated until now).
L([i j], 1:i-1) = L([j i], 1:i-1);
end
end
end
for j = i+1:m
L(j,i) = U(j,i)/U(i,i);
U(j,i) = 0;
U(j,i+1:m) = U(j,i+1:m) - L(j,i)*U(i,i+1:m);
end
end
%x = [P L U];
end
Output P*A - L*U:
<!-- language: lang-none -->
ans =
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。


评论