3.1 Some Basic Algorithm

Definition 3.1.1 [Algorithm & Input & Output Data]

Algorithm이란 것은 operation(연산) 또는 논리적 계산 및 산술이 순서적으로 놓여 있는 것을 의미한다. 이는 어떠한 문제를 해결하기 위한 과정을 의미하기도 한다. 이러한 과정에서 이 문제를 해결하기 위하여 투입되는 정보(Data)를 Input Data라고 하고, 이러한 과정을 거쳐서 Algorithm을 거쳐 나온 정보를 Output Data라고 한다.

손쉬운 접근을 위하여 Vector라든지 Matrix의 기본적인 연산들을 생각해보고 이러한 수학적인 연산들을 어떻게 이용할 수 있을지에 대하여 생각해 보도록 하자. 이렇게 고려한 Algorithm은 모두 임의의 명령줄로 쓰여질텐데 이러한 명령어를 pseudo code라고 한다. (1973년 Stewart소개)

3.1.1. Computing the Norm of a Vector

이라고 하자. 을 계산하는 방법을 생각해보자.

Algorithm 3.1.1 [2-Norm]

Input Data : , , , Step 1 : 를 구하자. Step 2 : 모든 값에 대하여 를 구하자. Step 3 : Output Data : 위의 내용을 바탕으로 Pseudo Code를 작성해보자. For to do

위의 Algorithm중에서 고려해야 할 점은 인 경우가 나오지 않도록 해야 한다는 점이다. 이러한 알고리즘에 의거하면 우리는 바로 이를 언어로 코딩할 수 있다.

Algorithm 3.1.1 [2-Norm Source]

[Code : SecondNorm.java] [결과]

자바의 특성을 이용한다면 위의 Class를 이용하여 바로 2-Norm을 구할 수 있는 Applet을 개발할 수 있다.

이를 더 응용하여 10차원 vector에 대한 p-norm을 구하는 Applet을 제작해 보자.

Algorithm 3.1.1 [2-Norm Source]

[Code : Norm.java] - Main Engine부분 [Code : PNorm.java] - Applet 및 UI(User Interface)부분

3.1.2. Computing the Inner Product of Two Vectors

위와 같은 방법으로 Algorithm을 생각하고 이를 이용하여 실제로 계산할 수 있는 프로그램을 생각해 볼 수 있다. 이번에는 Inner Product를 생각해 보자. (참고로 inner product는 이다.)

Algorithm 3.1.2 [Inner Product]

Input Data : , , , , Step 1 : 를 먼저 구하자. Step 2 : 을 구하자. Output Data : 위의 내용을 바탕으로 Pseudo Code를 작성해보자. For do [Code : InnerProduct.java] [결과]

마찬가지로, 이 또한 Applet으로 바로 우리가 만들어 볼 수도 있다.

3.1.3. Solution of an Upper Triangular Matrix

우리가 를 upper triangular matrix라고 생각을 해 보자. 이 경우, 우리는 라는 형태의 Linear System을 다음과 같이 생각할 수 있다.

여기서 들은 matrix 의 원소들이고, 와 는 각각 와 vector의 원소들이다. 이것을 구하기 위해서는 부터 해를 구하는 것이 아니라, 부터 해를 구하는 것이 바람직해 보인다. 따라서 해를 구할 때 일반적으로 생각하는 방향과 거꾸로 구하게 된다. 이렇게 해를 구하는 방법을 backward substitution(책에서는 back substitution)이라고 한다.

Algorithm 3.1.3 [Back Substitution]

Input Data : , 값들, 값들. Step 1 : Step 2 : (단 이 경우는 계속 그 이전값의 정보를 저장하고 있어야 한다.) Output Data : 들 위의 내용을 바탕으로 Pseudo Code를 작성해보자. For to do [Code : BackSub.java] [결과]

3.1.4. Computing the Inverse of an Upper Triangular Matrix

일반적으로 임의의 행렬의 역행렬을 찾는 일은 를 만족하는 행렬을 찾는 일이다. 일반적인 행렬에 대해서 이를 구하는 것은 지금의 단계로는 생각하기 어려운 편이다. 그러나 가 Upper Triangular Matrix라면, 위에 나온 3.1.3의 방법을 이용하여 좀 더 손쉽게 구할 수 있는 방법을 제시할 수 있다.

를 행렬의 각 column vector에 대하여 생각해보자. 의 column vector를 라고 하면, 가 된다. (는 standard basis) 이 문제는 바로 위의 3.1.3에서 다루었던 Upper Triangular Matrix의 대표적인 예제이므로, 이를 이용하여 계산하면 된다. 여기서는 Back Substitution의 문제가 있으므로, 결과값을 임의대로 라고 하고 이 index를 거꾸로 생각하도록 하겠다.

그러면 들을 생각해 보자.

: 이라면 이고 나머지 값은 모두 0이다.

: 이므로, ,

모두를 이런 식으로 생각해 본다면,

: 이므로, , 인 식이 된다.

이제 이를 이용하여 Pseudo Code를 작성해 보도록 하자.

Algorithm 3.1.4 [Upper Triangular Matrix Inversion]

For do 1. 2.  ()

위의 Algorithm을 이해를 쉽게 하기 위하여 실제코드를 작성하는 것보다, 아래의 예제를 보기로 하자.

Example 3.1.1

일 경우 에 관하여 계산해 보면 된다. ; ; ; 따라서

Pseudo Code에서 실질적인 Programming Code로 만드는 일은 그다지 어려운 일이 아니다. 단 여기서 주의할 점은 의 값이 값에 맞추어서 같이 돌아가야 한다는 점이다.

3.1.5. Gaussian Elimination for Solving

우리는 아래와 같이 개의 미지수를 가지는 차 연립방정식(n-dimensional linear system)이 있다고 가정하자.

이것을 Matrix의 형태로 나타내면 의 형태가 될 것이다. 이러한 문제를 접근하는 가장 고전적이고, 잘 알려진 방법은 Gaussian Elimination이란 방법이 있다. 이 방법은 오랫동안 많은 분야에 활용되어 왔고, 그 속도나 해법이 빠르고 명확하고 또한 매우 쉬워서 행렬을 이용한 선형연립방정식을 푸는 방법으로 많이 쓰인다.

여기서는 간단히 그 방법중 가장 기본적인 scheme만을 소개하고 더 많은 아이디어들에 대해서는 4장과 5장에 걸쳐서 소개하도록 한다. 일단 기본적인 방법을 사용하기 위해서는 다음의 Step을 사용한다.

먼저 각 행연산(Row Operation)을 이용하여 Upper Triangular Matrix로 행렬을 정리한다. : Reduction Process
Upper Triangular Matrix를 Back Substitution을 통해서 를 최종적으로 구한다. : Back Substitution

우선 Reduction Process를 고려해 보자.

Step 1 : 1번 row에 의 값을 이용하여 다른 row의 값을 모두 소거한다. 이를 위하여 각 row에 다음과 같은 값을 계산해준다.



이 값들을 곱하여 각 row에 곱해주면 그 row의 첫 번재 항의 값은 0이 된다. 이렇게 만들어 주는 값을 우리는 multiplier라 부르고 ()인 값이 된다.

Step 2 : 그러면 이 값들을 이용하여 vector 의 값을 다음과 같이 계산해 볼 수 있다.

(번째)

행렬의 각각의 원소도 다음과 같이 표현할 수 있다.

(번째)

이러한 과정을 이용하여 다음과 같은 Pseudo Code와 Algorithm을 생각해 볼 수 있다.

Pseudo Code : 일단 번의 과정을 거치게 된다. () 각각의 에 대하여 multiplier를 계산하도록 하자. 위에서 구한 내용을 가지고, , 을 계산한다.

Algorithm 3.1.5 [Basic Gaussian Elimination]

For do For do (당연히 ) For do

Remarks

Basic Gaussian Elemination Algorithm은 행의 치환을 생각하지 않은 Algorithm이다. 이에 우리가 생각하는 일반적인 Gaussian Algorithm과는 결과상에서 많은 차이를 보여준다. 우리가 일반적으로 알고 있는 Gaussian Elimination은 행의 치환을 생각하는 Gaussian Elimination with pivoting을 의미한다. 또한, 이 Algorithm은 Full rank matrix에만 적용되는 단점을 가지고 있다. 을 가지고 잇기 때문에, 당연히 파생되는 문제이다. 이를 해결하기 위해서는 row의 interchange가 중요한 요소로 부각된다.

개발중

기반 C 소스 : gec.txt 기반 View : PPrj.zip 개발용은 위의 algorithm을 쓰지 않고, Gaussian Elimination with complete pivoting을 사용한다.

 

 3.2 Definitions and Concepts of Stability

 일반적으로 Algorithm에 의하여 생성되는 그 결과값의 정확도에 따라서 그 Algorithm을 두 가지로 나눠 부른다.

stable algorithm : 정확한 결과를 항시 출력해 주는 algorithm
unstable algorithm : 어떤 경우에 대해서는 정확하지 않은 결과를 출력해 주는 algorithm

그러면 정확한 결과인지 아닌지를 판단하기 위해서는 그 결과의 error가 어떻게 나타나느냐가 중요한 문제일 것이다. 이러한 문제를 고려하는 것이 rounded error analysis라고 하며, 이러한 error는 backward error와 forward error의 두 가지가 있다.

일반적인 우리가 생각하는 거의 모든 연산들을 생각하면 Forward Stale한 Algorithm을 쓴다. 이러한 algorithm은 그 오차에 더 관심을 두며, 그  오차를 forward error라 하며, 이러한 error를 줄이는 데 그 목적을 둔다.

이론적으로 그 결론을 우리가 정확히 계산할 수 없을 경우를 의미하며 대부분의 수치해석적 결과들이 이에 해당한다. 이런 경우 그 error의 분석은 원래 문제에 적용했을 때만 구할 수 있고, 그 결과를 backward error라고 한다. 또한 본 내용에서는 앞으로 stable하다는 표현은 모두 backward stable로 표현하도록 하겠다.

이러한 개념을 선형연립방정식에 응용하면 다음과 같은 이야기를 할 수 있다.

그러면 위에서 소개한 작다("small")의 개념은 어떻게 측정할 수 있는가? 측정의 방법은 여러 가지가 있을 수 있다. 단, 행렬에서는 아래와 같이 Norm을 위주로 측정하느냐, Entry들을 중심으로 측정하느냐의 방법만이 남아 있을 것이다.

이러한 개념을 이용하여 algorithm의 stability를 생각해 보도록 하자.

위의 chapter 11의 p.601에 위의 유도과정을 볼 수 있다.

특히, Example 3.2.1과 같이 임의의 Matrix들에 대해서만 stable한 경우를 stable algorithm for a class of matrices라고 이야기하기도 한다.

 3.3 Conditioning of the Problem and Perturbation Analysis

 임의의 algorithm에 원래의 값에 약간의 변형을 가하는 일은 아주 흥미로운 문제이다. 이러한 원본의 값에 약간의 변형을 가하여 그 결과가 어떤지 유추하는 작업을 perturbation analysis라고 한다.

3.4 Conditioning of the Problem, Stability of the Algorithm and Accuracy of the Solution

 일반적으로 앞에서 소개한 Conditioned Problem과 Stability와는 밀접한 관계를 가진다. 단, 그 관점은 약간 다르다. Stability는 정확히 구한 값에 대해 근접하는 문제가 있다는 것을 확인해 줄 수 있으며, Conditioned Problem은 원래의 문제와 그 근접한 문제가 거의 비슷하다는 것을 보여줄 수 있다. 따라서 우리가 임의의 문제를 해결하기 위해서는 먼저 Algorithm의 Stability를 검증한 후, 그 결과값을 Conditioned Problem을 체크하여 Well-Conditioned Problem이 되는 지 체크하는 것이 중요한 문제가 된다.

일반적인 행렬연산에서는 Condition Number는 다음과 같이 성립한다.

 3.5 The Wilkinson Polynomial

ill-Conditioned가 발생할 수 있는 경우 중 의 형태로 생긴 polynomial을 Wilkinson polynomial이라 하고, 이러한 polynomial의 condition number를 구하면 이는 다음과 같이 나타난다.

일반적으로 이러한 Polynomial에 ill-conditioned problem은 방정식의 해를 구하는 문제에서 끝나지 않고, Characteristic polynomial을 통한 eigenvalue의 computation에도 영향을 미칠 수 있다.

 3.6 An Ill-Conditioned Linear System Problem

대표적인 예제는 다음과 같다.

위의 행렬을 Hilbert matrix라고 하고 이 행렬을 이용한 Linear System 는 의 perturbation에 많은 영향을 받는다.

3.7 Examples of Ill-Conditioned Eigenvalue Problem

아래의 행렬을 생각해 보자.

 

이 행렬은 Wilkinson bidiagonal matrix라 하며 이런 경우 일반적인 characteristic polynomial을 이용하여 eigenvalue를 구할 경우, 심각한 ill-conditioned problem을 초래할 수 있다. (물론 QR-iteration을 통한 현존하는 방법으로도 마찬가지의 문제가 발생할 수 있다.)

특히 Eigenvalue의 문제는 그 내부의 연산의 복잡도에 의하여 실제로 구해진 값과의 condition problem이 발생할 수 있다. 이를 일반적으로 를 right eigenvector, 를 left eigenvector라고 하면,

의 condition number가 발생하게 된다. 이를 통하여 더 많은 condition problem을 유발하는 행렬을 찾아볼 수 있다.

 3.8 Strong, Weak, and Mild Stability

 

일반적으로 stable한 algorithm에 대해서도, 우리는 그 algorithm이 임의의 matrix들의 class에 대해서 stable한 경우가 있을 수 있고, 다른 class에 대해서는 stability가 약간 불안해질 수 있다. 이런 경우를 우리는 strongly stability와 weakly stability로 나눈다.

strongly stable를 만족하는 matrix class의 모든 matrix들은 모두 well-conditioned를 만족하는 상태이다.

만일 well-conditioned상태의 matrix들마저도 weakly stable하지 않다면, 우리는 그 algorithm은 stable하지 않다고 한다.

그리고 stable하나, weakly stable이라고 하기에는 ill-conditioned에 대해서도 많은 문제가 발생하지 않으면서도, 일부의 ill-conditioned를 해결하지 못하는 일반적인 algorithm을 mild stable algorithm이라고 한다.