가우스 - 자이 델의 방법은 임의로 선택 정밀도 선형 대수 방정식의 시스템으로 근사해를 찾기위한 반복적 인 절차이다. 이 방법은 대각선에 0이 아닌 요소가있는 정사각형 행렬에 적용되며 행렬이 대각선으로 우세한 경우 수렴이 보장됩니다.
그것은 칼 프리드리히 가우스 (1777-1855)에 의해 만들어졌으며, 그는 1823 년에 그의 학생 중 한 명에게 개인 시연을하였습니다. 나중에 1874 년에 Philipp Ludwig von Seidel (1821-1896)에 의해 공식적으로 출판되었으므로 그 이름은 두 수학자의.
그림 1. Gauss-Seidel 방법은 방정식 시스템의 해를 얻기 위해 빠르게 수렴합니다. 출처 : F. Zapata.
방법을 완전히 이해하려면 각 행의 대각선 요소의 절대 값이 동일한 행의 다른 요소의 절대 값의 합보다 크거나 같을 때 행렬이 대각선으로 우세하다는 것을 알아야합니다.
수학적으로 다음과 같이 표현됩니다.
간단한 케이스를 사용한 설명
Gauss-Seidel 방법의 구성을 설명하기 위해 X와 Y의 값이 아래 표시된 2 × 2 선형 방정식 시스템에서 찾을 수있는 간단한 경우를 사용합니다.
5X + 2Y = 1
X-4Y = 0
따라야 할 단계
1- 우선 수렴이 안전한지 확인해야합니다. 첫 번째 행에서 첫 번째 계수가 첫 번째 행의 다른 계수보다 더 높은 절대 값을 갖기 때문에 실제로 대각선으로 우세한 시스템이라는 것이 즉시 관찰됩니다.
-5->-2-
마찬가지로 두 번째 행의 두 번째 계수도 대각선으로 우세합니다.
--4->-1-
2- 변수 X 및 Y가 지워집니다.
X = (1-2Y) / 5
Y = X / 4
3- "seed"라고하는 임의의 초기 값이 배치됩니다. Xo = 1, I = 2.
4- 반복이 시작됩니다. 첫 번째 근사 X1, Y1을 얻기 위해 시드는 2 단계의 첫 번째 방정식에서 대체되고 결과는 2 단계의 두 번째 방정식으로 대체됩니다.
X1 = (1-2 I) / 5 = (1-2 × 2) / 5 = -3/5
Y1 = X1 / 4 = (-3/5) / 4 = -3/20
5- 우리는 방정식 시스템의 해의 두 번째 근사치를 얻기 위해 비슷한 방식으로 진행합니다.
X2 = (1-2 Y1) / 5 = (1-2x (-3/20)) / 5 = 13/50
Y2 = X2 / 4 = (13/50) / 4 = 13/200
6- 세 번째 반복 :
X3 = (1-2 Y2) / 5 = (1-2 (13/200)) / 5 = 87/500
Y3 = X3 / 4 = (87/500) / 4 = 87/2000
7- 네 번째 반복,이 예시 사례의 마지막 반복 :
X4 = (1-2 Y3) / 5 = (1-2 (87/2000)) / 5 = 913/5000
Y4 = X4 / 4 = (913/5000) / 4 = 913/20000
이 값은 다른 해결 방법에서 찾은 솔루션과 아주 잘 일치합니다. 독자는 온라인 수학 프로그램의 도움으로 빠르게 확인할 수 있습니다.
방법 분석
알 수 있듯이 Gauss-Seidel 방법에서는 동일한 단계에서 이전 변수에 대해 얻은 근사값을 다음 변수로 대체해야합니다. 이것은 각 단계에서 이전 단계의 근사치를 요구하는 Jacobi와 같은 다른 반복 방법과 구별됩니다.
Gauss-Seidel 방법은 병렬 절차가 아니지만 Gauss-Jordan 방법은 병렬 절차가 아닙니다. 또한 Gauss-Seidel 방법이 Jordan 방법보다 적은 단계에서 더 빠른 수렴을 갖는 이유이기도합니다.
대각선으로 우세한 행렬 조건의 경우 항상 만족되는 것은 아닙니다. 그러나 대부분의 경우 단순히 원래 시스템에서 행을 교체하는 것만으로도 조건이 충족됩니다. 또한이 방법은 대각선 우위 조건이 충족되지 않더라도 거의 항상 수렴합니다.
Gauss-Seidel 방법을 네 번 반복하여 얻은 이전 결과는 십진수 형식으로 작성할 수 있습니다.
X4 = 0.1826
Y4 = 0.04565
제안 된 방정식 시스템에 대한 정확한 솔루션은 다음과 같습니다.
X = 2/11 = 0.1818
Y = 1/22 = 0.04545.
따라서 단 4 번의 반복으로 1000 분의 1 정밀도 (0.001)의 결과를 얻습니다.
그림 1은 연속적인 반복이 어떻게 정확한 솔루션으로 빠르게 수렴되는지 보여줍니다.
응용
Gauss-Seidel 방법은 2 × 2 선형 방정식 시스템에만 제한되지 않습니다. 이전 절차를 일반화하여 다음과 같은 행렬로 표현되는 n 개의 미지수를 갖는 n 개의 방정식으로 구성된 선형 시스템을 풀 수 있습니다.
A X = b
여기서 A는 nxn 행렬이고 X 는 계산할 n 변수의 벡터 n 구성 요소입니다. 및 B는 독립적 인 용어들의 값을 포함하는 벡터이다.
변수 Xi가 계산되기를 원하는 nxn 시스템에 대한 예시 사례에서 적용되는 반복 순서를 일반화하기 위해 다음 공식이 적용됩니다.
이 방정식에서 :
-k는 반복 k에서 얻은 값의 인덱스입니다.
-k + 1은 다음에있는 새 값을 나타냅니다.
최종 반복 횟수는 반복 k + 1에서 얻은 값이 정확히 원하는 정밀도 인 양 ε만큼 이전에 얻은 값과 다를 때 결정됩니다.
Gauss-Seidel 방법의 예
-예 1
계수 A의 행렬, 독립 항의 벡터 b , 반복 횟수 (i ter) 및 초기 값 또는 "시드"가 주어지면 방정식 nxn의 선형 시스템 의 근사 솔루션 X 의 벡터를 계산할 수있는 일반 알고리즘을 작성합니다. "벡터 X의 .
해결책
알고리즘은 두 개의 "종료"사이클로 구성됩니다. 하나는 반복 횟수에 대한 것이고 다른 하나는 변수 수에 대한 것입니다. 다음과 같습니다.
k ∊의 경우
나는 ∊
X = (1 / A) * (b - Σ J = 1 N (A * X) + A * X)
-예 2
Windows 및 Android에서 사용할 수있는 무료로 사용할 수있는 무료 수학 소프트웨어 SMath Studio에서 응용 프로그램을 통해 이전 알고리즘의 작동을 확인합니다. Gauss-Seidel 방법을 설명하는 데 도움이 된 2 × 2 행렬의 경우를 예로 들어 보겠습니다.
해결책
그림 2. SMath Studio 소프트웨어를 사용하는 2 x 2 예제의 연립 방정식 솔루션. 출처 : F. Zapata.
-예 3
대각선의 계수가 우세한 (즉, 계수의 절대 값보다 절대 값이 더 큰) 방식으로 이전에 정렬 된 다음 3 × 3 방정식 시스템에 대해 Gauss-Seidel 알고리즘을 적용합니다. 같은 행) :
9 X1 + 2 X2-X3 = -2
7 X1 + 8 X2 + 5 X3 = 3
3 X1 + 4 X2-10 X3 = 6
null 벡터를 시드로 사용하고 5 회 반복을 고려합니다. 결과에 대해 설명합니다.
해결책
그림 3. SMath Studio를 사용한 풀이 예제 3의 연립 방정식 솔루션. 출처 : F. Zapata.
5 회 대신 10 회 반복하는 동일한 시스템에 대해 다음 결과가 얻어집니다. X1 = -0.485; X2 = 1.0123; X3 = -0.3406
이는 다섯 번의 반복으로 소수점 이하 세 자리의 정밀도를 얻기에 충분하며 방법이 신속하게 해에 수렴된다는 것을 알려줍니다.
-예제 4
위에 주어진 Gauss-Seidel 알고리즘을 사용하여 아래 주어진 4 × 4 연립 방정식에 대한 해를 찾으십시오.
10 x1-x2 + 2 x3 + 0 x4 = 6
-1 x1 + 11 x2-1 x3 + 3 x4 = 25
2 x1-1 x2 + 10 x3-1 x4 = -11
0 x1 + 3 x2-1 x3 + 8 x4 = 15
메서드를 시작하려면 다음 시드를 사용하십시오.
x1 = 0, x2 = 0, x3 = 0 및 x4 = 0
10 회 반복을 고려하고 반복 횟수 11과 비교하여 결과의 오류를 추정합니다.
해결책
그림 4. SMath Studio를 사용하여 풀이 예 4의 연립 방정식 솔루션. 출처 : F. Zapata.
다음 반복 (숫자 11)과 비교할 때 결과는 동일합니다. 두 반복 사이의 가장 큰 차이는 2 × 10 -8 정도 이며, 이는 표시된 솔루션의 정밀도가 소수점 이하 7 자리 이상임을 의미합니다.
참고 문헌
- 반복적 솔루션 방법. 가우스-자이 델. 출처 : cimat.mx
- 수치 적 방법. 가우스-자이 델. 출처 : test.cua.uam.mx
- 수치 : Gauss-Seidel 방법. 출처 : aprendeenlinea.udea.edu.co
- Wikipedia. Gauss-Seidel 방법. 출처 : ko. wikipedia.com
- Wikipedia. Gauss-Seidel 방법. 출처 : es.wikipedia.com