[Section 3.1 : Some Basic Algorithm]

    [Section 3.2 : Definitions and Concepts of Stability]

    [Section 3.3 : Conditioning of the Problem and Perturbation Analysis]

    [Section 3.4 : Conditioning of the Problem, Stability of the Algorithm and Accuracy of the Solution]

    [Section 3.5 : The Wilkinson Polynomial]

    [Section 3.6 : An Ill-Conditioned Linear System Problem]

    [Section 3.7 : Examples of Ill-Conditioned Eigenvalue Problem]

    [Section 3.8 : Strong, Weak, and Mild Stability]

square65_blue.gif 3.1 Some Basic Algorithm

     

    dia_bluve.gif Definition 3.1.1 [Algorithm & Input & Output Data]

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

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

bar05_solid1x1_blue.gif

    3.1.1. Computing the Norm of a Vector

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

    dia_bluve.gif Algorithm 3.1.1 [2-Norm]

    Input Data : , , ,

    Step 1 : 를 구하자.

    Step 2 : 모든 값에 대하여 를 구하자.

    Step 3 :

    Output Data :

    위의 내용을 바탕으로 Pseudo Code를 작성해보자.

      For to do

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

    dia_bluve.gif Algorithm 3.1.1 [2-Norm Source]

    [Code : SecondNorm.java]

    bar05_solid1x1_darkyellow.gif

    [결과]

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

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

    dia_bluve.gif Algorithm 3.1.1 [2-Norm Source]

    [Code : Norm.java] - Main Engine부분

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

    bar05_solid1x1_darkyellow.gif

bar05_solid1x1_green.gif

    3.1.2. Computing the Inner Product of Two Vectors

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

    dia_bluve.gif Algorithm 3.1.2 [Inner Product]

    Input Data : , , , ,

    Step 1 : 를 먼저 구하자.

    Step 2 : 을 구하자.

    Output Data :

    위의 내용을 바탕으로 Pseudo Code를 작성해보자.

      For do

    bar05_solid1x1_purple.gif

    [Code : InnerProduct.java]

    [결과]

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

bar05_solid1x1_red.gif

    3.1.3. Solution of an Upper Triangular Matrix

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

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

    dia_bluve.gif Algorithm 3.1.3 [Back Substitution]

    Input Data : , 값들, 값들.

    Step 1 :

    Step 2 : (단 이 경우는 계속 그 이전값의 정보를 저장하고 있어야 한다.)

    Output Data :

    위의 내용을 바탕으로 Pseudo Code를 작성해보자.

      For to do

    bar05_solid1x1_purple.gif

    [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를 작성해 보도록 하자.

    dia_bluve.gif Algorithm 3.1.4 [Upper Triangular Matrix Inversion]

    For do

      1.

      2.  ()

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

    dia_bluve.gif 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을 사용한다.

    1. 먼저 각 행연산(Row Operation)을 이용하여 Upper Triangular Matrix로 행렬을 정리한다. : Reduction Process
    2. 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 :

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

bar05_solid1x1_blue.gif

    dia_bluve.gif Algorithm 3.1.5 [Basic Gaussian Elimination]

    For do

      For do

        (당연히 )

        For do

bar05_solid1x1_darkyellow.gif

    dia_brown.gif Remarks

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

    bar05_solid1x1_green.gif

    dia_brown.gif 개발중

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

     

bar01_dot1x1_black.gif

square65_green.gif 3.2 Definitions and Concepts of Stability

     

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

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

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

dia_bluve.gif Definition 3.2.1 [Forward Stable]

forward stable algorithm은 어떠한 문제에 대하여 정확한 값을 알 때, 그 값에 근사하는 값을 구할 수 있는 algorithm을 이야기한다.

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

dia_bluve.gif Definition 3.2.2 [Backward Stable]

backward stable algorithm은 정확한 값은 모르더라도, 어떤 문제의 solution이라고 생각할 수 있는 값을 구하여 그 값이 그 문제를 해결할 수 있는 경우를 이야기한다.

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

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

dia_bluve.gif Definition 3.2.3 [Stablity of Linear System]

만일 가 stable한 algorithm을 가지고 있다면 그 결과는 (는 굉장히 작은 수)로 표현될 수 있다.

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

Normwise Error와 Entrywise Error

Normwise의 error와 entrywise error의 경우, 그 갯수부터 차이가 난다. normwise error의 경우, 1개에 불과하지만, entrywise error의 경우에는 행렬의 경우 가 존재하기 때문이다. 물론 algorithm에 따라서 entrywise로 측정할 경우, 더 정밀한 결과를 얻을 수 있겠지만, 횟수만큼의 대조를 해야 하기 때문에 전체적인 algorithm이 느려지게 된다. 그러나, 만일 normwise의 경우에는 정밀한 결과를 얻지는 못하겠지만, 그 수가 작은 경우, 어느 정도의 신뢰도를 가지는 결과를 생각하면서 대조하는데에는 그 속도가 더 빠르게 구현할 수 있을 것이다.

단, normwise의 경우, 그 오차가 커지면 entrywise의 관점에서 보면 그 오차는 너무 많이 증가하게 된다. 실제로 entrywise error가 0.000001이 차이나는 matrix의 경우 normwise의 경우 10.0499의 차이가 나는 경우가 있으므로, normwise error이 높을 때에는 이것이 실제로 error율이 높은지 낮은지를 판단하는 것은 불가능하다.

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

dia_bluve.gif Example 3.2.1

Stable Algorithm의 예제를 생각해 보자.

Algorithm 3.1.3의 back-substitution을 생각해 보자. 이를 [Chapter 11]의 내용을 이용하여 위의 선형연립방정식을 생각해 보자.

그러면 가 되었을 때, 의 모든 원소들인 를 만족한다.

이 값에서 는 상수이고, 는 굉장히 작은 값이므로, 는 매우 작은 행렬이 된다. 따라서 back-substitution은 stable한 algorithm이라 할 수 있다.

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

dia_bluve.gif Example 3.2.2

Unstable Algorithm의 예제를 생각해 보자.

Gussian Elimination without pivoting (Algorithm 3.1.5)를 위의 Example 3.2.1과 비슷하게 풀어보도록 하자.

인 경우,

이 경우 로 정의된다. 이 항의 값은 앞으로 증가할 가능성이 높으므로 이를 growth factor라고 부르고, 이러한 factor가 존재하게 할 수 있는 Algorithm을 unstable algorithm이라고 한다.

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

bar01_dot1x1_blue.gif

square65_orange.gif 3.3 Conditioning of the Problem and Perturbation Analysis

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

dia_bluve.gif Definition 3.3.1 [Conditioned]

만일 원래의 값(초기값)에 약간의 relatively error가 적은 값을 perturbation을 주었을 때 그 결과가 큰 차이를 나타내면 이러한 algorithm은 ill-conditioned 또는 badly-conditioned problem을 가지고 있다고 한다. 반대로 적은 perturbation을 주었을 때, 그리 많은 차이가 나지 않는 경우를 well-conditioned problem이라고 한다.

bar01_dot1x1_darkyellow.gif

square65_blue.gif 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

일부의 Numerical Analysis를 연구하는 학자들 사이에서는 Condition상태가 ill-conditioned인지, well-conditioned인지를 판단하는 방법중 하나로 Condition Number라는 것을 체크하고 있다. Condition Number는 입력된 초기 데이터에 약간의 perturbation을 취하여 그 결과값이 얼마의 relative error를 가지는지 체크하는 것을 통하여 구할 수 있다.

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

bar01_dot1x1_black.gif

square65_green.gif 3.5 The Wilkinson Polynomial

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

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

bar01_dot1x1_blue.gif

square65_orange.gif 3.6 An Ill-Conditioned Linear System Problem

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

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

bar01_dot1x1_darkyellow.gif

square65_blue.gif 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을 유발하는 행렬을 찾아볼 수 있다.

dia_bluve.gif Example 3.7.2

은 ill-conditioned를 유발시키는 행렬이다.

bar01_dot1x1_black.gif

square65_green.gif 3.8 Strong, Weak, and Mild Stability

     

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

dia_bluve.gif Definition 3.8.1 [Strongly Stability]

임의의 stable한 algorithm이 어떤 matrix의 class에 대해서 그 perturbation이 특이하게 아주 작게 나타난다면 그 algorithm은 그 matrix의 class에 대해서 strongly stable하다고 한다.

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

dia_bluve.gif Definition 3.8.2 [Weakly Stability]

어떠한 matrix의 class에 대해서도 위와 같이 well-conditioned상태인 것만을 stable하게 유지하는 algorithm을 weakly stable이라 한다.

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

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

bar01_dot1x1_blue.gif

Copyright © 2002, Made by SML(Sungkyunkwan Univ. Linear algebra Lab.), All rights reserved.