수치 선형대수학

응용 선형대수라고도 하는 수치 선형대수는 연속수학에서 질문에 대한 대략적인 답을 효율적이고 정확하게 제공하는 컴퓨터 알고리즘을 만들기 위해 매트릭스 연산을 어떻게 사용할 수 있는지에 대한 연구다. 수치해석의 하위 분야로, 선형대수의 일종이다. 컴퓨터는 부동소수점 산수를 사용하며 비합리적인 데이터를 정확히 나타낼 수 없기 때문에 컴퓨터 알고리즘을 데이터 행렬에 적용하면 때때로 컴퓨터에 저장된 숫자와 그것이 근사치인 실제 숫자의 차이를 증가시킬 수 있다. 수치 선형대수학은 벡터와 행렬의 속성을 이용하여 컴퓨터가 도입한 오류를 최소화하는 컴퓨터 알고리즘을 개발하며, 알고리즘이 가능한 한 효율적이 되도록 하는 것에도 신경을 쓴다.

수치 선형대수는 유한정밀컴퓨터를 이용해 연속수학의 문제를 푸는 것을 목표로 하므로 자연과학과 사회과학에 대한 응용은 연속수학의 응용만큼이나 방대하다. 그것은 종종 영상과 신호 처리, 통신, 컴퓨터 금융, 재료 과학 시뮬레이션, 구조 생물학, 데이터 마이닝, 생물 정보학, 유동적 역학 등과 같은 공학 및 컴퓨터 과학 문제의 근본적인 부분이다. 매트릭스 방법은 특히 유한 차이 방법, 유한 요소 방법, 미분 방정식의 모델링에 사용된다. 수치 선형대수의 광범위한 적용에 주목하면서, 로이드 N. 트레페텐과 데이비드 바우, III는 비교적 작은 분야임에도 불구하고 "미적분, 미분방정식처럼 수학적 과학의 기본"^[1]^{: x}이라고 주장한다.^[2] 행렬과 벡터의 많은 특성들이 기능과 연산자에도 적용되기 때문에 수치 선형대수학은 실용적인 알고리즘을 특별히 강조하는 기능분석 유형으로도 볼 수 있다.^[1]^{: ix}

수치 선형대수의 일반적인 문제에는 단수 값 분해, QR 인자화, LU 인자화 또는 아이겐데 구성과 같은 행렬 분해물을 얻는 것이 포함된다. 이 매개변수는 방정식의 선형 시스템 해결, 고유값 찾기 또는 최소 제곱 최적화와 같은 일반적인 선형 대수적 문제에 답하기 위해 사용될 수 있다.이온. 유한정밀 컴퓨터의 실제 데이터에 적용할 때 오류를 발생시키지 않는 알고리즘을 개발하는 수치 선형대수의 중심 관심사는 종종 직접적 방법보다는 반복적 방법에 의해 달성된다.

역사

수치 선형대수는 존 폰 노이만, 앨런 튜링, 제임스 H와 같은 컴퓨터 선구자들에 의해 개발되었다. 윌킨슨, 앨스턴 스콧 하우스홀더, 조지 포사이스, 하인즈 루티샤이저는 탄도 문제, 부분 미분 방정식의 시스템에 대한 해결책과 같은 연속 수학의 문제에 가장 초기의 컴퓨터를 적용하기 위해서입니다.^[2] 실제 데이터에 알고리즘을 적용할 때 컴퓨터 오류를 최소화하려는 첫 번째 심각한 시도는 1947년 존 폰 노이만과 허먼 골드스틴의 작품이다.^[3] 이 분야는 기술이 매우 큰 고밀도 매트릭스의 복잡한 문제를 연구자들이 해결할 수 있게 하면서 성장했고, 병렬 컴퓨팅과 같은 기술이 과학적인 문제에 대한 실질적인 접근법을 만들면서 일부 수치 알고리즘이 두드러지게 성장했다.^[2]

매트릭스 분해

분할 행렬

적용된 선형대수의 많은 문제에서 행렬의 관점을 열 벡터의 결합으로 채택하는 것이 유용하다. 예를 들어, x를 $A^{-1}$ 로 $A^{-1}$ A $A^{-1}$ - $A^{-1}$ b의 산물로 이해하는 것보다 $x=A^{-1}b$ 선형 시스템 x $x=A^{-1}b$ = $x=A^{-1}b$ - 1 $x=A^{-1}b$ ${\$ $A^{-1$ $}$ 을 해결할 때, x를 A의 열에 의해 형성된 기초에서 b의 선형 팽창 계수의 벡터로 생각하는 것이 도움이 된다.^[1]^{: 8} 행렬을 기둥의 결합으로 생각하는 것도 매트릭스 알고리즘의 목적을 위한 실용적인 접근법이다. 이는 매트릭스 알고리즘이 종종 두 개의 중첩된 루프를 포함하기 때문인데 하나는 매트릭스 A의 열에, 또 하나는 A의 행에 있기 때문이다. 예를 들어, 행렬 $A^{m\times n}$ $A^{m\times n}$ $A^{m\times n}$ $A^{m\times n}$ ${\$ A $^{m\times n}$ 과 $A^{m\times n}$ (와) 벡터 $x^{n\times 1}$ $x^{n\times 1}$ $x^{n\times 1}$ {\ $displaystyle$ x^{ $n\time:1}}$ 과 $x^{n\times 1}$ $y^{m\times 1}$ $y^{m\times 1}$ $y^{m\times 1}$ 1 ${\$ 의 경우 칼럼 분할 원근법을 사용하여 Ax + y를 계산한다 $y^{m\times 1}$

을 위해 j = 1:n   을 위해 i = 1:m     y(i) = A(i,j)x(j) + y(i)   종지부를 찍다 종지부를 찍다

단수 값 분해

매트릭스 $A^{m\times n}$ $A^{m\times n}$ $A^{m\times n}$ n ${\$ A $^{m\times n}$ 의 단수 값 $A=U\Sigma V^{\ast }$ 는 A $A=U\Sigma V^{\ast }$ = $A=U\Sigma V^{\ast }$ $A=U\Sigma V^{\ast }$ V $A=U\Sigma V^{\ast }$ ${\$ V $^{\ast }$ 이며 $A^{m\times n}$ , 여기서 $A=U\Sigma V^{\ast }$ $\Sigma$ 와 V는 단일하며, , ${\displaystystyle \Sigma}$ 은 $\Sigma$ 대각이다. $\Sigma$ $\Sigma$ 의 대각선 항목을 A의 단수 값이라고 한다 $\Sigma$ . 단수값은 $AA^{\ast }$ $∗{\$ 의 고유값의 제곱근이기 때문에 단수값 분해와 고유값 분해 사이에는 밀접한 관계가 있다 $AA^{\ast }$ 이것은 단수 값 분해를 계산하는 대부분의 방법이 고유값 방법과 유사하다는 것을 의미한다.^[1]^{: 36} 아마도 가장 일반적인 방법은 하우스홀더 절차를 포함한다.^[1]^{: 253}

QR 인자화

매트릭스 $A^{m\times n}$ $A^{m\times n}$ $A^{m\times n}$ n ${\$ n $}$ 의 $A^{m\times n}$ $Q^{m\times m}$ QR 인자화는 매트릭스 $Q^{m\times m}$ $Q^{m\times m}$ $Q^{m\times m}$ ${\$ $Q$ $^{m\time$ m $},$ 매트릭스 $R^{m\times n}$ $R^{m\times n}$ × $R^{m\times n}$ ${\$ R $^{m\timesn},$ 여기서 Q는 직교하고 R은 상위 삼각형이다.^[1]^{: 50}^[4]^{: 223} QR 인자화를 계산하기 위한 두 가지 주요 알고리즘은 그람-슈미트 프로세스와 하우스홀더 변환이다. QR 인자화는 선형 최소 제곱 문제, 고유값 문제(반복 QR 알고리즘을 통해)를 해결하기 위해 자주 사용된다.

LU 인자화

An LU factorization of a matrix A consists of a lower triangular matrix L and an upper triangular matrix M so that A = LU. The matrix U is found by an upper triangularization procedure which involves left-multiplying A by a series of matrices $M_{1},\ldots ,M_{n-1}$ to form the product $M_{n-1}\cdots M_{1}A=U$ $M_{n-1}\cdots M_{1}A=U$ $M_{n-1}\cdots M_{1}A=U$ $M_{n-1}\cdots M_{1}A=U$ $M_{n-1}\cdots M_{1}A=U$ = U $M_{n-1}\cdots M_{1}A=U$ 따라서 $L=M_{1}^{-1}\cdots M_{n-1}^{-1}$ 하게 L $L=M_{1}^{-1}\cdots M_{n-1}^{-1}$ = M $L=M_{1}^{-1}\cdots M_{n-1}^{-1}$ - $L=M_{1}^{-1}\cdots M_{n-1}^{-1}$ $L=M_{1}^{-1}\cdots M_{n-1}^{-1}$ M $L=M_{1}^{-1}\cdots M_{n-1}^{-1}$ - 1 $L=M_{1}^{-1}\cdots M_{n-1}^{-1}$ - $L=M_{1}^{-1}\cdots M_{n-1}^{-1}$ ${\$ ^[1]^{: 147}^[4]^{: 96}

고유값 분해

The eigenvalue decomposition of a matrix $A^{m\times m}$ is $A=X\Lambda X^{-1}$ , where the columns of X are the eigenvectors of A, and $\Lambda$ is a diagonal matrix the diagonal entries of which are the corresponding eigenvalues of A.^[1]^{: 33} 임의 행렬의 고유값 분해를 찾는 직접적인 방법은 없다. 유한한 시간 안에 임의 다항식의 정확한 뿌리를 찾는 프로그램을 쓸 수 없기 때문에, 어떤 일반 고유값 해결사라도 반드시 반복적이어야 한다.^[1]^{: 192}

Algorithms

Gaussian elimination

From the numerical linear algebra perspective, Gaussian elimination is a procedure for factoring a matrix A into its LU factorization, which Gaussian elimination accomplishes by left-multiplying A by a succession of matrices $L_{m-1}\cdots L_{2}L_{1}A=U$ until U is upper triangular and L is lower triangular, where $L\equiv L_{1}^{-1}L_{2}^{-1}\cdots L_{m-1}^{-1}$ .^[1]^{: 148} Naive programs for Gaussian elimination are notoriously highly unstable, and produce huge errors when applied to matrices with many significant digits.^[2] The simplest solution is to introduce pivoting, which produces a modified Gaussian elimination algorithm that is stable.^[1]^{: 151}

Solutions of linear systems

Numerical linear algebra characteristically approaches matrices as a concatenation of columns vectors. In order to solve the linear system $x=A^{-1}b$ , the traditional algebraic approach is to understand x as the product of $A^{-1}$ with b. Numerical linear algebra instead interprets x as the vector of coefficients of the linear expansion of b in the basis formed by the columns of A.^[1]^{: 8}

행렬 A의 특성과 벡터 x와 b의 특성에 따라 선형 문제를 해결하기 위해 여러 가지 다른 분해물을 사용할 수 있으며, 이는 한 인자화를 다른 요소들보다 훨씬 쉽게 얻을 수 있게 할 수 있다. A = QR이 A의 QR 인수인자인 경우, $Rx=Q^{\ast }b$ 하게 $Rx=Q^{\ast }b$ x $Rx=Q^{\ast }b$ = $Rx=Q^{\ast }b$ $Rx=Q^{\ast }b$ $Rx=Q^{\ast }b$ ${\displaystyle Rx=Q^{\ast }b$ . 이것은 매트릭스 인자화로서 계산하기 쉽다.^[1]^{: 54} If $A=X\Lambda X^{-1}$ is an eigendecomposition A, and we seek to find b so that b = Ax, with $b^{\prime }=X^{-1}b$ and $x^{\prime }=X^{-1}x$ , then we have ${\displaystyle b^{\prime }=\Lambda x^{\$ $prime$ $b^{\prime }=\Lambda x^{\prime }$ ^[1]^{: 33} 행렬의 단수값이 고유값의 제곱근이기 때문에 단수값 분해를 이용한 선형계통에 대한 해법과 밀접한 관계가 있다. 그리고 A = LU가 A의 LU 인자화라면, Ax = b는 삼각 행렬 Ly = b, Ux = y를 사용하여 해결할 수 있다.^[1]^{: 147}^[4]^{: 99}

최소 제곱 최적화

매트릭스 분해는 회귀 문제에서처럼 r을 최소화하려는 선형 시스템 r = b - Ax를 해결하는 여러 방법을 제안한다. QR 알고리즘은 먼저 y = ${\widehat {R}}x={\widehat {Q}}^{\ast }b$ 를 정의한 다음 ${\widehat {R}}x={\widehat {Q}}^{\ast }b$ 의 감소된 QR 인자화를 계산하고 R ${\widehat {R}}x={\widehat {Q}}^{\ast }b$ x = ${\widehat {R}}x={\widehat {Q}}^{\ast }b$ ^ ${\widehat {R}}x={\widehat {Q}}^{\ast }b$ ${\widehat {R}}x={\widehat {Q}}^{\ast }b$ ${\displaystyle{R}x={\widehat{Q}^{Q}{\widehat }}}$ 을(를) 얻기 위해 재배열하여 이 문제를 해결한다 ${\widehat {R}}x={\widehat {Q}}^{\ast }b$ 이 위쪽 삼각형 체계는 b에 대해 해결할 수 있다. 또한 SVD는 선형 최소 제곱을 얻기 위한 알고리즘을 제안한다. By computing the reduced SVD decomposition $A={\widehat {U}}{\widehat {\Sigma }}V^{\ast }$ and then computing the vector ${\widehat {U}}^{\ast }b$ , we reduce the least squares problem to a simple diagonal system.^[1]^{: 84} 최소 사각형 솔루션이 QR과 SVD 인자에 의해 생산될 수 있다는 것은 최소 사각형 문제를 해결하기 위한 고전적인 정규 방정식 방법 외에 Gram-Schmidt 알고리즘과 Householder 방법을 포함하는 방법으로도 이러한 문제를 해결할 수 있다는 것을 의미한다.

조건화 및 안정성

문제가 함수 $f:X\to Y$ : $f:X\to Y$ → $f:X\to Y$ Y {\ $displaystyle f:X\to Y}$ 임을 허용한다. 여기서 X는 데이터의 표준 벡터 공간이고 Y는 용액의 표준 벡터 공간이다 $f:X\to Y$ 일부 데이터 지점 $x\in X$ $x\in X$ $x\in X$ ${\displaystyle x\in$ X $}$ 에 대해 $x\in X$ x의 작은 동요가 f(x)의 값에서 큰 변화를 일으키면 문제는 조건이 좋지 않다고 한다. 우리는 문제가 얼마나 잘 해결되었는지 나타내는 조건 번호를 정의함으로써 이것을 정량화할 수 있다.

{\widehat {\\cappa }}=\lim _{\no 0}\sup_{\\no_\\\leq\\\}{\fract f\}{\\\\no_x\}}}.

불안정성은 부동 소수점 산술에 의존하는 컴퓨터 알고리즘이 문제에 대한 정확한 수학적 해법과는 극적으로 다른 결과를 내는 경향이다. 행렬이 많은 수의 유의한 숫자의 실제 데이터를 포함하는 경우 방정식의 선형 시스템 또는 최소 제곱 최적화와 같은 문제를 해결하기 위한 많은 알고리즘은 매우 부정확한 결과를 산출할 수 있다. 조건이 좋지 않은 문제에 대한 안정적인 알고리즘을 만드는 것은 수치 선형대수학에서 중심적인 관심사다. 한 예로, 주택 보유자 삼각화의 안정성으로 인해 선형 시스템을 위한 특히 강력한 솔루션 방법이 되는 반면, 최소 제곱 문제를 해결하기 위한 정규 방정식 방법이 불안정하다는 것은 단수 값 분해법을 사용하는 것과 같은 행렬 분해 방법을 선호하는 이유가 된다. 일부 매트릭스 분해 방법은 불안정할 수 있지만, 이를 안정되게 만드는 직접적인 수정을 가지고 있다. 한 예는 불안정한 그램-슈미트인데, 이것은 안정적인 변형 그램-슈미트를 생산하기 위해 쉽게 변경될 수 있다.^[1]^{: 140} 수치 선형대수의 또 다른 고전적 문제는 가우스 제거가 불안정하지만 선회 도입과 함께 안정화 된다는 발견이다.

반복적 방법

반복 알고리즘이 수치 선형대수의 중요한 부분이라는 두 가지 이유가 있다. 첫째로, 많은 중요한 수학적 문제들은 직접적인 해결책이 없다; 임의 매트릭스의 고유값과 고유 벡터를 찾기 위해서, 우리는 반복적인 접근법만을 채택할 수 있다. 둘째, 임의 $m\times m$ $m\times m$ $m\times m$ $m\time m$ 행렬에 $m\times m$ 대한 비기준 알고리즘에는 $O(m^{3})$ ( $O(m^{3})$ m $O(m^{3})$ ) ${\displaystyle$ O $(m^{3}})$ 시간이 필요하며 $O(m^{3})$ , 행렬에 $m^{2}$ 2 ${\$ m $^{2}}개$ 의 숫자만 $m^{2}$ 포함된다는 점을 감안하면 놀랄 만큼 높은 바닥이다. 반복적 접근법은 이 시간을 줄이기 위해 일부 행렬의 몇 가지 특징을 이용할 수 있다. 예를 들어, 행렬이 희박한 경우, 반복 알고리즘은 고도로 구조화된 행렬이 주어진 중복 단계라 하더라도 직접적 접근방식이 반드시 따라야 할 많은 단계를 건너뛸 수 있다.

수치 선형대수학에서 많은 반복적 방법의 핵심은 저차원 Krylov 하위 공간에 대한 행렬의 투영으로, 저차원 공간에서 시작하여 연속적으로 더 높은 디멘시오로 이동하는 유사한 행렬의 등가 특성을 반복적으로 계산하여 고차원 행렬의 특징을 근사하게 할 수 있다.ns. A가 대칭이고 선형 문제 Ax = b를 해결하고자 할 때, 고전적 반복적 접근법은 결합 구배 방법이다. A가 대칭적이지 않은 경우, 선형 문제에 대한 반복적 해결책의 예는 일반화된 최소 잔차 방법과 CNGN이다. A가 대칭이면 고유값과 고유벡터 문제를 해결하기 위해 Lanczos 알고리즘을 사용할 수 있고, A가 비대칭이면 Arnoldi 반복을 사용할 수 있다.

소프트웨어

몇몇 프로그래밍 언어는 수치 선형 대수 최적화 기법을 사용하며 수치 선형 대수 알고리즘을 구현하도록 설계되어 있다. 이 언어들은 MATLAB, Analytica, Mapatica를 포함한다. 수치 선형대수를 위해 명시적으로 설계되지 않은 다른 프로그래밍 언어에는 수치 선형대수 루틴과 최적화를 제공하는 라이브러리가 있다; C와 Fortran은 기본 선형대수 서브프로그램과 LAPACK 같은 패키지를 가지고 있고, python은 라이브러리 NumPy, Perl은 Perl 데이터 언어를 가지고 있다. R의 많은 숫자 선형 대수 명령어는 LAPACK과 같은 보다 근본적인 라이브러리에 의존한다.^[5] 숫자 라이브러리 목록에서 더 많은 라이브러리를 찾을 수 있다.

참조

^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k ^l ^m ⁿ ^o ^p ^q Trefethen, Lloyd; Bau III, David (1997). Numerical Linear Algebra (1st ed.). Philadelphia: SIAM. ISBN 978-0-89871-361-9.
^ ^a ^b ^c ^d Golub, Gene H. "A History of Modern Numerical Linear Algebra" (PDF). University of Chicago Statistics Department. Retrieved February 17, 2019.
^ von Neumann, John; Goldstine, Herman H. (1947). "Numerical inverting of matrices of high order" (PDF). Bulletin of the American Mathematical Society. 53 (11): 1021–1099. doi:10.1090/s0002-9904-1947-08909-6. S2CID 16174165. Archived from the original (PDF) on 2019-02-18. Retrieved February 17, 2019.
^ ^a ^b ^c Golub, Gene H.; Van Loan, Charles F. (1996). Matrix Computations (3rd ed.). Baltimore: The Johns Hopkins University Press. ISBN 0-8018-5413-X.
^ Rickert, Joseph (August 29, 2013). "R and Linear Algebra". R-bloggers. Retrieved February 17, 2019.

추가 읽기

Dongarra, Jack; Hammarling, Sven (1990). "Evolution of Numerical Software for Dense Linear Algebra". In Cox, M. G.; Hammarling, S. (eds.). Reliable Numerical Computation. Oxford: Clarendon Press. pp. 297–327. ISBN 0-19-853564-3.

외부 링크

웹 상에서 숫자 대수용으로 자유롭게 사용할 수 있는 소프트웨어로, 테네시 대학의 잭 동가라와 하템 라티에프(Hatem Ltaief)가 작곡함
NAG 수치 선형 대수 루틴 라이브러리
Twitter의 수치 선형대수군(영국 리서치그룹)
트위터에서 siagla (산업 및 응용수학을 위한 사회의 수치 선형대수에 대한 활동 그룹)
IMT2000 3GPP - 응용 및 수치 선형대수에 관한 연구

[tb397-1] ^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k ^l ^m ⁿ ^o ^p ^q Trefethen, Lloyd; Bau III, David (1997). Numerical Linear Algebra (1st ed.). Philadelphia: SIAM. ISBN 978-0-89871-361-9.

[golubhist-2] Golub, Gene H. "A History of Modern Numerical Linear Algebra" (PDF). University of Chicago Statistics Department. Retrieved February 17, 2019.

[3] von Neumann, John; Goldstine, Herman H. (1947). "Numerical inverting of matrices of high order" (PDF). Bulletin of the American Mathematical Society. 53 (11): 1021–1099. doi:10.1090/s0002-9904-1947-08909-6. S2CID 16174165. Archived from the original (PDF) on 2019-02-18. Retrieved February 17, 2019.

[gvl96-4] Golub, Gene H.; Van Loan, Charles F. (1996). Matrix Computations (3rd ed.). Baltimore: The Johns Hopkins University Press. ISBN 0-8018-5413-X.

[5] Rickert, Joseph (August 29, 2013). "R and Linear Algebra". R-bloggers. Retrieved February 17, 2019.

[1]

[2]

[3]

[4]

[5]

v t 수치 선형대수학
주요개념	부동소수점 수치안정성
문제	선형 방정식 체계 매트릭스 분해 행렬 곱하기(알고리즘) 행렬 분할 희소성 문제
하드웨어	CPU 캐시 TLB 캐시-관심 알고리즘 심드 다중 처리
소프트웨어	매트랩 기본 선형 대수 하위 프로그램(BLAS) 라팩 전문 라이브러리 범용 소프트웨어

Search