lu

LU 행렬 분해(Matrix Factorization)

구문

[L,U] = lu(A)

[L,U,P] = lu(A)

[L,U,P] = lu(A,outputForm)

[L,U,P,Q] = lu(S)

[L,U,P,Q,D] = lu(S)

[___] = lu(S,thresh)

[___] = lu(___,outputForm)

설명

[L,U] = lu(A)는 비희소 또는 희소 행렬 A를 A = L*U가 되도록 상부 삼각 행렬 U와 치환된 하부 삼각 행렬 L로 분해합니다.

[L,U,P] = lu(A)는 A = P'*L*U를 충족하는 치환 행렬 P도 반환합니다. 이 구문에서 L은 단위 하부 삼각 행렬이고 U는 상부 삼각 행렬입니다.

[L,U,P] = lu(A,outputForm)은 outputForm에서 지정된 형식으로 P를 반환합니다. P를 A(P,:) = L*U를 충족하는 치환 벡터로 반환하려면 outputForm을 'vector'로 지정하십시오.

[L,U,P,Q] = lu(S)는 희소 행렬 S를 P*S*Q = L*U가 되도록 단위 하부 삼각 행렬 L, 상부 삼각 행렬 U, 행 치환 행렬 P와 열 치환 행렬 Q로 분해합니다.

[L,U,P,Q,D] = lu(S)는 P*(D\S)*Q = L*U를 충족하는 대각 스케일링 행렬 D도 반환합니다. 일반적으로, 행 스케일링을 수행하면 희소성이 더 커지고 더욱 안정적으로 행렬 분해를 수행할 수 있게 됩니다.

[___] = lu(S,thresh)는 lu가 사용하는 피벗 연산 전략의 임계값을 위에 열거된 출력 인수의 임의의 조합을 사용하여 지정합니다. 지정된 출력 인수의 개수에 따라 thresh 입력값의 디폴트 값과 요구 사항이 달라집니다. 자세한 내용은 thresh 인수 설명을 참조하십시오.

[___] = lu(___,outputForm)은 outputForm으로 지정된 형식으로 P와 Q를 반환합니다. P와 Q를 치환 벡터로 반환하려면 outputForm을 'vector'로 지정하십시오. 위에 열거된 구문에 나와 있는 입력 인수를 원하는 대로 조합하여 사용할 수 있습니다.

예제

행렬의 LU 분해

행렬의 LU 분해를 계산하고 결과로 출력되는 인수를 검토합니다. LU 분해는 행렬 $\mathit{A}$를 $\mathrm{PA}=\mathrm{LU}$가 되도록 상부 삼각 행렬 $\mathit{U}$, 하부 삼각 행렬 $\mathit{L}$과 치환 행렬 $\mathit{P}$로 분해하는 한 가지 방법입니다. 이들 행렬은 행렬이 기약행 사다리꼴이 될 때까지 행렬에 대한 가우스 소거법을 수행하는 데 필요한 단계를 설명해 줍니다. $\mathit{L}$ 행렬은 모든 승수를 포함하며, 치환 행렬 $\mathit{P}$는 행을 상호 교환하는 역할을 합니다.

3×3 행렬을 만들고 LU 인수를 계산합니다.

A = [10 -7 0
     -3  2 6
      5 -1 5];

[L,U] = lu(A)

L = 3×3

    1.0000         0         0
   -0.3000   -0.0400    1.0000
    0.5000    1.0000         0

U = 3×3

   10.0000   -7.0000         0
         0    2.5000    5.0000
         0         0    6.2000

인수를 곱하여 A를 다시 만듭니다. 2-입력값 구문에서 lu는 반환되는 L이 실제로는 P'*L이 되도록 치환 행렬 P를 L 인수에 반영하므로 A = L*U가 됩니다.

L*U

ans = 3×3

    10    -7     0
    -3     2     6
     5    -1     5

출력값 3개를 지정하면 L에서 승수로부터 치환 행렬을 분리할 수 있습니다.

[L,U,P] = lu(A)

L = 3×3

    1.0000         0         0
    0.5000    1.0000         0
   -0.3000   -0.0400    1.0000

U = 3×3

   10.0000   -7.0000         0
         0    2.5000    5.0000
         0         0    6.2000

P = 3×3

     1     0     0
     0     0     1
     0     1     0

P'*L*U

ans = 3×3

    10    -7     0
    -3     2     6
     5    -1     5

LU 분해를 사용하여 선형 시스템 풀기

LU 분해를 수행하고 인수를 사용하여 문제를 단순화하여 선형 시스템을 풉니다. 이 결과를 백슬래시 연산자와 decomposition 객체를 사용하는 다른 접근 방식과 비교합니다.

5×5 마방진 행렬을 만들고 b의 모든 요소가 마방진의 합인 65와 같은 선형 시스템 $\mathrm{Ax}=\mathit{b}$를 풉니다. 이 행렬의 마방진의 합은 65이므로(모든 행과 열의 합이 65) x의 예상되는 해는 1로 구성된 벡터입니다.

A = magic(5);
b = 65*ones(5,1);
x = A\b

x = 5×1

    1.0000
    1.0000
    1.0000
    1.0000
    1.0000

일반 정사각 행렬에서 백슬래시 연산자는 LU 분해를 사용하여 선형 시스템의 해를 구합니다. LU 분해는 A를 삼각 행렬의 곱으로 표현하므로 삼각 행렬이 있는 선형 시스템은 대입 수식을 사용하여 쉽게 풀 수 있습니다.

백슬래시로 구한 답을 다시 만들려면 A의 LU 분해를 계산하십시오. 그런 다음 인수를 사용하여 다음 2개의 선형 시스템을 푸십시오.

y = L\(P*b);
x = U\y;

선형 시스템의 해를 구하기 전에 행렬 인수를 먼저 계산하는 이 접근 방식은 분해가 한 번만 발생하고 반복이 필요하지 않기 때문에 여러 개의 선형 시스템을 풀어야 할 때 성능이 높아질 수 있습니다.

[L,U,P] = lu(A)

L = 5×5

    1.0000         0         0         0         0
    0.7391    1.0000         0         0         0
    0.4783    0.7687    1.0000         0         0
    0.1739    0.2527    0.5164    1.0000         0
    0.4348    0.4839    0.7231    0.9231    1.0000

U = 5×5

   23.0000    5.0000    7.0000   14.0000   16.0000
         0   20.3043   -4.1739   -2.3478    3.1739
         0         0   24.8608   -2.8908   -1.0921
         0         0         0   19.6512   18.9793
         0         0         0         0  -22.2222

P = 5×5

     0     1     0     0     0
     1     0     0     0     0
     0     0     0     0     1
     0     0     1     0     0
     0     0     0     1     0

y = L\(P*b);
x = U\y

x = 5×1

    1.0000
    1.0000
    1.0000
    1.0000
    1.0000

decomposition 객체도 행렬 인수를 먼저 계산하는 접근 방식의 성능적인 이점을 얻으면서도 인수를 어떻게 사용하는지 알 필요가 없기 때문에 역시 특화된 분해를 사용하여 선형 시스템을 풀 때 유용합니다. decomposition 객체를 'lu' 유형과 함께 사용하여 동일한 결과를 다시 만듭니다.

dA = decomposition(A,'lu');
x = dA\b

x = 5×1

    1.0000
    1.0000
    1.0000
    1.0000
    1.0000

희소 행렬의 LU 분해

희소 행렬의 LU 분해를 계산하고 항등식 L*U = P*S*Q를 검증합니다.

버크민스터 풀러의 측지선 돔의 연결 그래프에 대한 60×60 희소 인접 행렬을 생성합니다.

S = bucky;

네 개의 출력값을 가진 희소 행렬 구문을 사용하여 S의 LU 분해를 계산하고 행과 열 치환 행렬을 반환합니다.

[L,U,P,Q] = lu(S);

S의 행과 열을 P*S*Q로 치환하고 이 결과를 삼각 인수를 곱한 결과(L*U)와 비교합니다. 두 차이에 대한 1-노름(Norm)이 반올림 오차 내에 있으므로, L*U = P*S*Q를 나타냅니다.

e = P*S*Q - L*U;
norm(e,1)

ans = 5.7732e-15

치환 벡터로 메모리 절약하기

행렬의 LU 분해를 계산합니다. 행 치환을 행렬이 아닌 벡터로 반환하여 메모리를 절약합니다.

1000×1000 확률 행렬을 만듭니다.

A = rand(1000);

행렬 P로 저장된 치환 정보를 사용하여 LU 분해를 계산합니다. 이 결과를 벡터 p로 저장된 치환 정보와 비교합니다. 행렬의 크기가 클수록 치환 벡터를 사용했을 때의 메모리 효율이 높아집니다.

[L1,U1,P] = lu(A);
[L2,U2,p] = lu(A,'vector');
whos P p

  Name         Size                Bytes  Class     Attributes

  P         1000x1000            8000000  double              
  p            1x1000               8000  double              

치환 벡터를 사용하면 이후의 연산에서의 실행 시간도 단축됩니다. 예를 들어, 앞에서 본 LU 분해를 사용하여 선형 시스템 $\mathrm{Ax}=\mathit{b}$를 구할 수 있습니다. 이때 치환 벡터로 구한 해와 치환 행렬로 구한 해는 (반올림 오차 내에서)동일하지만 치환 벡터를 사용할 때 시간이 더 적게 걸립니다.

희소 행렬 분해의 필인 줄이기

열 치환을 사용하여 희소 행렬의 LU 분해를 계산한 결과와 사용하지 않고 계산한 결과를 비교합니다.

실수 값의 479×479 희소 행렬인 west0479 행렬을 불러옵니다.

load west0479
A = west0479;

출력값 3개를 반환하는 lu를 호출하여 A의 LU 분해를 계산합니다. L 인수와 U 인수의 희소성 패턴을 보여주는 플롯을 생성합니다.

[L,U,P] = lu(A);
subplot(1,2,1)
spy(L)
title('L factor')
subplot(1,2,2)
spy(U)
title('U factor')

이번에는 출력값 4개를 반환하는 lu를 사용하여 A의 LU 분해를 계산합니다. 이때 lu는 A의 열을 치환하여 인수에서 0이 아닌 값의 개수를 줄입니다. 이 결과로 나오는 인수는 열 치환을 사용하지 않은 경우에 비해 희소성이 훨씬 높습니다.

[L,U,P,Q] = lu(A);
subplot(1,2,1)
spy(L)
title('L factor')
subplot(1,2,2)
spy(U)
title('U factor')

입력 인수

A — 입력 행렬

행렬

입력 행렬입니다. A는 비희소 또는 희소 행렬일 수 있고 수 있고 정사각 행렬이나 직사각 행렬일 수 있습니다.

데이터형: single | double
복소수 지원 여부: 예

S — 희소 입력 행렬

희소 행렬

희소 입력 행렬입니다. S는 정사각 행렬이나 직사각 행렬일 수 있습니다.

데이터형: double
복소수 지원 여부: 예

thresh — 희소 행렬의 피벗 연산 임계값

스칼라 | 요소를 2개 가진 벡터

희소 행렬의 피벗 연산 임계값으로, 스칼라 또는 요소를 2개 가진 벡터로 지정됩니다. 유효한 값은 구간 [0 1] 내에 있는 값입니다. thresh를 지정하는 방법은 lu를 호출할 때 지정된 출력값의 개수에 따라 다음과 같이 달라집니다.

• 출력값이 3개 이하인 경우 thresh는 스칼라여야 하고 디폴트 값은 1.0입니다.

• 출력값이 4개 이상인 경우 thresh는 스칼라 또는 요소를 2개 가진 벡터일 수 있습니다. 디폴트 값은 [0.1 0.001]입니다. thresh를 스칼라로 지정하면 벡터의 첫 번째 값만 대체합니다.

개략적으로 말하자면 이 입력값을 사용하여 정확도와 총 실행 시간 간의 상호 절충 관계를 조정할 수 있습니다. thresh 값이 작을수록 LU 인수의 희소성이 더 커지게 되는 경향이 있지만, 해는 부정확해질 수 있습니다. 값이 커지면 항상 그런 것은 아니지만 더 정확한 해를 구할 수 있으며, 대개 전체 작업 및 메모리 사용량이 증가하게 됩니다.

lu는 우선 출력 인수의 개수를 기준으로, 다음으로는 분해되는 행렬의 속성을 기준으로 피벗 연산 전략을 선택합니다. 모든 경우를 통틀어, 임계값을 1.0으로 설정하면 부분 피벗 연산이 선택되고, 임계값을 0으로 설정하면 결과로 나오는 행렬의 희소성만을 기준으로 피벗 연산이 선택됩니다. L의 모든 값은 1/min(thresh) 이하의 절댓값을 가집니다.

• 출력 인수가 3개 이하인 경우 — 알고리즘은 다음 수식이 충족되면 대각선 피벗을 선택합니다.

  A(j,j) >= thresh * max(abs(A(j:m,j)))

  충족되지 않으면 최대 절댓값 요소를 포함하는 행을 선택합니다.

• 대칭 피벗 연산 전략 — S가 거의 대부분 대칭 구조를 이루며 주로 0이 아닌 대각선 요소로 이루어진 정사각 희소 행렬이라면 lu는 대칭 피벗 연산 전략을 사용합니다. 이 전략의 경우, 알고리즘은 다음 부등식이 충족되면 대각선 피벗 j를 선택합니다.

  A(i,j) >= thresh(2) * max(abs(A(j:m,j)))

  대각선 요소가 이 테스트를 통과하지 못하면 lu는 다음 부등식을 충족하는 희소성이 가장 큰 행 i를 선택합니다.

  A(i,j) >= thresh(1) * max(abs(A(j:m,j)))

• 비대칭 피벗 연산 전략 — S가 대칭 피벗 연산 전략의 요구 사항을 충족하지 못하면 lu는 비대칭 전략을 사용합니다. 이 경우 lu는 다음 부등식을 충족하는 희소성이 가장 큰 행 i를 선택합니다.

  A(i,j) >= thresh(1) * max(abs(A(j:m,j)))

  thresh(1)의 값이 1.0이면 일반적인 부분 피벗 연산이 사용됩니다. L의 항목은 1/thresh(1) 이하의 절댓값을 가집니다. 비대칭 전략을 사용하는 경우 thresh 입력 벡터의 두 번째 요소는 사용되지 않습니다.

참고

드물지만, 부정확한 행렬 분해의 결과로 P*S*Q ≠ L*U가 될 수 있습니다. 이 경우, thresh를 최대 1.0(일반 부분 피벗 연산)으로 높여 다시 시도해 보십시오.

outputForm — 치환 출력값의 형태

'matrix' (디폴트 값) | 'vector'

치환 출력값의 형태로, 'matrix' 또는 'vector'로 지정됩니다. 이 플래그는 lu가 행 치환 P와 열 치환 Q를 치환 행렬과 치환 벡터 중 어느 것으로 반환할지를 제어합니다.

P와 Q가 행렬인 경우 다음 항등식을 충족합니다.

• 출력값 3개 — P는 P*A = L*U를 충족합니다.

• 출력값 4개 — P와 Q는 P*S*Q = L*U를 충족합니다.

• 출력값 5개 — P, Q, D는 P*(D\S)*Q = L*U를 충족합니다.

P와 Q가 벡터이면 다음 항등식을 충족합니다.

• 출력값 3개 — P는 A(P,:) = L*U를 충족합니다.

• 출력값 4개 — P와 Q는 S(P,Q) = L*U를 충족합니다.

• 출력값 5개 — P, Q, D는 D(:,P)\S(:,Q) = L*U를 충족합니다.

예: [L,U,P] = lu(A,'vector')

출력 인수

L — 하부 삼각 인수

행렬

하부 삼각 인수로, 행렬로 반환됩니다. L의 형태는 행 치환 P가 별도의 출력값으로 반환되는지 여부에 따라 다음과 같이 달라집니다.

• 세 번째 출력값 P가 지정된 경우 L은 단위 하부 삼각 행렬(즉, 주대각선 요소가 1인 하부 삼각 행렬)로 반환됩니다.

• 세 번째 출력값 P가 지정되지 않은 경우 L은 단위 하부 삼각 행렬의 행 치환으로 반환됩니다. 즉, 이것은 출력값이 3개인 경우에서 반환된 출력값 P와 L의 곱 P'*L입니다.

U — 상부 삼각 인수

행렬

상부 삼각 인수로, 상부 삼각 행렬로 반환됩니다.

P — 행 치환

벡터 | 행렬

행 치환으로, 치환 행렬로 반환되거나 'vector' 옵션이 지정된 경우 치환 벡터로 반환됩니다. 이 출력값을 사용하여 계산의 수치적 안정성을 개선할 수 있습니다.

이 출력값이 충족하는 항등식에 대한 설명은 outputForm을 참조하십시오.

Q — 열 치환

벡터 | 행렬

열 치환으로, 치환 행렬로 반환되거나 'vector' 옵션이 지정된 경우 치환 벡터로 반환됩니다. 이 출력값을 사용하여 희소 행렬의 인수에서 필인(0이 아닌 요소의 개수)을 줄일 수 있습니다.

이 출력값이 충족하는 항등식에 대한 설명은 outputForm을 참조하십시오.

D — 행 스케일링

대각 행렬

행 스케일링으로, 대각 행렬로 반환됩니다. D는 P*(D\S)*Q = L*U가 되도록 S의 값을 스케일링하는 데 사용됩니다. 항상 그렇지는 않지만 일반적으로, 행 스케일링을 수행하면 희소성이 더 커지고 더욱 안정적으로 행렬 분해를 수행할 수 있게 됩니다.

알고리즘

LU 분해는 가우스 소거법의 변형을 사용하여 계산됩니다. 해의 정확도는 원래 행렬의 조건수 cond(A)에 따라 달라집니다. 행렬의 조건수가 크면(즉, 유사 특이 행렬이면) 계산된 행렬 분해는 정확하지 않을 수 있습니다.

LU 분해는 inv를 사용하여 역을 구하거나 det를 사용하여 행렬식을 구하는 데 있어 중요한 단계입니다. 또한 선형 방정식의 해를 구하거나 연산자 \ 및 /를 사용하여 행렬 나눗셈을 계산하는 데 있어서도 기본적인 연산입니다. 이는 lu의 수치적 제한 사항이 이러한 종속 함수에도 존재함을 의미합니다.

참고 문헌

[1] Gilbert, John R., and Tim Peierls. “Sparse Partial Pivoting in Time Proportional to Arithmetic Operations.” SIAM Journal on Scientific and Statistical Computing 9, no. 5 (September 1988): 862–874. https://doi.org/10.1137/0909058.

[2] Anderson, E., ed. LAPACK Users’ Guide. 3rd ed. Software, Environments, Tools. Philadelphia: Society for Industrial and Applied Mathematics, 1999. https://doi.org/10.1137/1.9780898719604.

[3] Davis, Timothy A. "Algorithm 832: UMFPACK V4.3 – an unsymmetric-pattern multifrontal method." ACM Transactions on Mathematical Software 30, no. 2 (June 2004): 196–199. https://doi.org/10.1145/992200.992206.

확장 기능

C/C++ 코드 생성

MATLAB® Coder™를 사용하여 C 코드나 C++ 코드를 생성할 수 있습니다.

사용법 관련 참고 및 제한 사항:

• 코드 생성 시 이 함수에 대해 희소 행렬 입력값은 지원되지 않습니다.

GPU 코드 생성

GPU Coder™를 사용하여 NVIDIA® GPU용 CUDA® 코드를 생성할 수 있습니다.

사용법 관련 참고 및 제한 사항:

• 코드 생성 시 이 함수에 대해 희소 행렬 입력값은 지원되지 않습니다.

스레드 기반 환경

MATLAB®의 backgroundPool을 사용해 백그라운드에서 코드를 실행하거나 Parallel Computing Toolbox™의 ThreadPool을 사용해 코드 실행 속도를 높일 수 있습니다.

이 함수는 스레드 기반 환경을 완전히 지원합니다. 자세한 내용은 스레드 기반 환경에서 MATLAB 함수 실행하기 항목을 참조하십시오.

GPU 배열

Parallel Computing Toolbox™를 사용해 GPU(그래픽스 처리 장치)에서 실행하여 코드 실행 속도를 높일 수 있습니다.

사용법 관련 참고 및 제한 사항:

• A는 비희소 행렬이어야 합니다.

자세한 내용은 GPU에서 MATLAB 함수 실행하기 (Parallel Computing Toolbox) 항목을 참조하십시오.

분산 배열

Parallel Computing Toolbox™를 사용하여 대규모 배열을 클러스터의 결합된 메모리에 걸쳐 분할할 수 있습니다.

사용법 관련 참고 및 제한 사항:

• A는 비희소 행렬이어야 합니다.

자세한 내용은 분산 배열을 사용하여 MATLAB 함수 실행 (Parallel Computing Toolbox) 항목을 참조하십시오.

버전 내역

R2006a 이전에 개발됨

참고 항목

cond | det | inv | ilu | qr | rref | mldivide | decomposition

도움말 항목

• 행렬 분해

×

예제 열기

이 예제의 수정된 버전이 있습니다. 사용자가 편집한 내용을 반영하여 이 예제를 여시겠습니까?

아니요, 수정된 버전을 덮어씁니다. 예