첨가 슈바르츠 방법

Additive Schwarz method

수학에서 헤르만 슈바르츠의 이름을 딴 첨가제 슈바르츠 방법은 작은 영역의 경계값 문제로 나누어 결과를 추가함으로써 대략적인 부분 미분방정식에 대한 경계값 문제를 해결한다.

개요

부분 미분 방정식(PDE)은 모든 과학에서 현상을 모형화하는 데 사용된다. 설명을 위해 물리적 문제와 그에 수반되는 경계 값 문제(BVP)를 예로 제시한다. 비록 독자가 표기법에 익숙하지 않더라도, 그 목적은 단지 BVP가 어떤 모습인지 적을 때 보여주기 위한 것이다.

(모델 문제) 정사각형 금속판의 열 분포는 왼쪽 가장자리가 1도로 유지되고 다른 가장자리가 0도로 유지되며, 장기간 놓아두면 다음과 같은 경계 값 문제가 충족된다.
fxx(x,y) + fyy(x,y) = 0
f(0,y) = 1; f(x,0) = f(x,1) = f(1,y) = 0
여기서 f는 알 수 없는 함수로서 f와xx f는yy 각각 x와 y에 관한 두 번째 부분파생상품을 나타낸다.

여기서 도메인은 제곱 [0,1] × [0,1]이다.

이 특별한 문제는 서류상으로 정확히 해결할 수 있기 때문에 컴퓨터가 필요 없다. 그러나 이것은 예외적인 사례여서 대부분의 BVP는 정확히 해결될 수 없다. 유일한 가능성은 대략적인 해결책을 찾기 위해 컴퓨터를 사용하는 것이다.

컴퓨터 문제 해결

일반적인 방법은 정사각형[0,1] × [0,1]의 일정한 간격으로 f를 표본을 추출하는 것이다. 예를 들어 x = 0.1, 0.2, ..., 0.8, 0.9에서 x 방향으로 8개의 표본을 추출하고 y 방향으로 8개의 표본을 유사한 좌표로 추출할 수 있다. 그리고 나서 우리는 (0.2,0.8)와 (0.6,0.6)와 같은 곳에서 64개의 사각형 샘플을 갖게 될 것이다. 컴퓨터 프로그램의 목표는 그 64개 지점에서 f의 값을 계산하는 것인데, 이것은 광장의 추상적인 기능을 찾는 것보다 쉬워 보인다.

예를 들어 사각형의 64점 만으로는xx f(0.5,0.5) knowing f를 계산할 수 없는 어려움도 있다. 이를 극복하기 위해 유한요소법이나 유한차이를 참고하여 파생상품의 수학적 근사치를 사용한다. 우리는 이러한 어려움을 무시하고 문제의 다른 측면에 집중한다.

선형 문제 해결

우리가 이 문제를 해결하기 위해 어떤 방법을 선택하든, 우리는 방정식의 큰 선형 시스템을 해결해야 할 것이다. 독자들은 고등학교 때 방정식의 선형 시스템을 떠올릴 수 있다. 그들은 다음과 같이 보인다.

2a + 5b = 12(*)
6a − 3b = −3

이것은 2개의 미상 (a와 b)에 2개의 방정식으로 이루어진 체계다. 만약 우리가 제안된 방식으로 위의 BVP를 풀면, 우리는 64개의 미지의 방정식들을 풀 필요가 있을 것이다. 이것은 현대의 컴퓨터에게는 어려운 문제가 아니지만, 우리가 더 많은 수의 샘플을 사용한다면, 현대의 컴퓨터도 BVP를 매우 효율적으로 해결할 수 없다.

도메인 분해

그래서 도메인 분해 방법이 나왔어 도메인 [0,1] × [0,1]을 두 개의 하위 도메인[0,0.5] × [0,1]과 [0.5,1] × [0,1] × [0,1]으로 나누면 각각 샘플 포인트의 절반만 된다. 그래서 우리는 각 서브 도메인에서 모델 문제의 버전을 해결하려고 노력할 수 있지만, 이번에는 각 서브 도메인마다 32개의 샘플 포인트만 가지고 있다. 마지막으로, 각 서브도메인에 대한 해답이 주어지면, [0,1] × [0,1]에서 원래의 문제의 해답을 얻기 위해 그것들을 조정해 볼 수 있다.

문제의 크기

선형계통의 관점에서, 우리는 64개의 미지의 방정식 시스템을 32개의 미지의 방정식 두 개의 계통으로 나누려고 하고 있다. 이것은 다음과 같은 이유로 분명한 이득이 될 것이다. 시스템(*)을 돌아보면 6가지 중요한 정보가 있음을 알 수 있다. 그것들은 a와 b의 계수(1번째 줄에 2.5, 2번째 줄에 6, 3), 그리고 오른손 쪽 (12,-3으로 쓴다)이다. 한편, 1 방정식의 2개의 "계"를 알 수 없는 1개의 방정식으로 취한다면, 다음과 같이 보일 수 있다.

시스템 1: 2a = 12
시스템 2: -3b = -3

우리는 이 시스템이 단지 4개의 중요한 정보만을 가지고 있다는 것을 안다. 이것은 컴퓨터 프로그램이 하나의 2×2 시스템을 푸는 것보다 두 개의 1×1 시스템을 푸는 것이 더 쉬울 것이라는 것을 의미한다. 왜냐하면 1×1 시스템의 쌍이 단일 2×2 시스템보다 더 단순하기 때문이다. 64×64와 32×32 시스템은 여기서 설명하기에는 너무 큰 반면, 우리는 유추하여 64×64 시스템은 4160개의 정보를 가지고 있는 반면, 32×32 시스템은 각각 1056개, 즉 64×64 시스템의 약 4분의 1을 가지고 있다고 말할 수 있다.

도메인 분해 알고리즘

불행하게도 기술적 이유로 64점(선형 방정식의 64×64계통)의 격자를 32점(선형 방정식의 32×32계통 2개)의 격자로 나누어 64×64계통에 대한 답을 얻는 것은 일반적으로 불가능하다. 대신 다음과 같은 알고리즘이 실제로 일어나는 것이다.

1) 64×64 계통의 대략적인 용액부터 시작한다.
2) 64×64 시스템에서 32×32 시스템 2개를 만들어 대략적인 용액을 개선한다.
3) 32×32 시스템 2개를 푼다.
4) 32×32 용액 2개를 "함께" 넣어 64×64 시스템의 대략적인 용액을 개선한다.
5) 아직 해법이 그리 좋지 않으면 2부터 반복한다.

이것이 기지 64×64 시스템을 해결하는 것보다 나을 수 있는 두 가지 방법이 있다. 첫째, 알고리즘의 반복 횟수가 적을 경우, 32×32 시스템 두 개를 푸는 것이 64×64 시스템을 푸는 것보다 더 효율적일 수 있다. 둘째, 32×32 시스템 두 개를 같은 컴퓨터에서 해결할 필요가 없으므로, 이 알고리즘을 병렬로 실행하여 여러 컴퓨터의 힘을 이용할 수 있다.

사실 64×64 시스템 대신 32×32 시스템 두 개를 (병렬주의를 사용하지 않고) 단일 컴퓨터에서 해결하는 것은 효율적이지 않을 것 같다. 하지만 세 개 이상의 서브 도메인을 사용하면 그림이 바뀔 수 있다. 예를 들어, 우리는 4개의 16×16 문제를 사용할 수 있고, 도메인 분해 알고리즘이 몇 번 반복해도 64×64 하나의 문제를 해결하는 것보다 더 나을 가능성이 있다.

기술적 예

여기서 우리는 독자가 부분 미분 방정식에 익숙하다고 가정한다.

우리는 부분 미분 방정식을 풀 것이다.

uxx + uyy = f(**)

우리는 무한대에 경계를 부과한다.

도메인 R²를 두 개의 겹치는 하위1 도메인 H = (- ∞,1] × R과 H2 = [0,+ ∞) × R로 분해한다. 각 하위 도메인에서 다음 형식의 BVP를 해결할 것이다.

u( j )xx + u( j )yy = f in Hj
u( j )(xj,y) = g(y)

여기서 x1 = 1 및 x2 = 0이며 무한대에서 다른 경계 조건과 같이 경계를 취한다. 위 문제의 해결책( j ) u를 S(f,g)로 나타낸다. S는 이선형이라는 점에 유의한다.

슈바르츠 알고리즘은 다음과 같이 진행된다.

  1. 각각 하위 도메인1 H와 H에2 있는 PDE의( 1 )0 u와 u의( 2 )0 대략적인 솔루션으로 시작하십시오. k를 1로 초기화한다.
  2. u( j )k + 1 = S(f,u(3 − j)k(xj))를 j = 1.2로 계산한다.
  3. k를 1씩 증가시키고 충분한 정밀도가 달성될 때까지 2를 반복한다.

참고 항목

참조

  • 배리 스미스, Petter Björstad, William Gropp, 도메인 분해, Elliptic 부분 미분 방정식의 병렬 다단계 방법, Cambridge University Press 1996
  • Andrea Toselli와 Olof Widlund, 도메인 분해 방법 - 알고리즘과 이론, 계산 수학에서의 스프링어 시리즈, 2004. 34, Vol.

외부 링크