반복법

계산수학에서 반복법은 초기값을 사용하여 문제의 종류에 대한 근사해결을 개선하는 일련의 순서를 생성하는 수학적 절차로, 여기서 n번째 근사해법은 앞의 근사해법에서 도출된다.종료기준을 포함한 반복방법의 특정 실장은 반복방법의 알고리즘이다.대응하는 시퀀스가 소정의 초기 근사치에 대해서 수렴하는 경우는, 반복 방법을 수렴법이라고 부릅니다.반복 방법의 수학적으로 엄격한 수렴 분석이 보통 수행되지만, 휴리스틱 기반의 반복 방법 또한 일반적이다.

이와는 대조적으로, 직접 방법은 유한한 일련의 연산에 의해 문제를 해결하려고 시도한다.반올림 오류가 없는 경우, 직접 방법은 정확한 해법을 전달할 것이다(예를 들어, 가우스 제거를 통해 $방정식{\displaystyle }$ ${\displaystyle A\mathbf{}}$ x $=$ \ $displaystyle$ A$\mathbf {x}$ =\$mathbf {b} }$의 선형 시스템을 푸는 것).비선형 방정식에 대한 유일한 선택지는 반복 방법인 경우가 많습니다.그러나 반복적인 방법은 많은 변수를 수반하는 선형 문제(때로는 수백만 개 정도)에도 유용하며, 직접 방법은 최고의 컴퓨팅 ^[1]능력을 사용하더라도 엄청나게 비용이 많이 들 수 있습니다(경우에 따라서는 불가능하기도 합니다.

매력적인 고정점

방정식을 f(x) = x의 형태로 만들 수 있고, 용액 x가 함수 f의 매력적인 고정점일 경우, x의 흡인성 분지에 있는₁ 점 x에서 시작하여 n ≤ 1에 대해 x = f(x_n)로 하면_n+1, 시퀀스_{n n ≥ 1}{x}는 솔루션 x로 수렴한다.x의 여기 xn은 몇번째인지도 모를 정도의 근사 또는 반복과인데 대안으로, 괄호 안에 위 첨자 종종 숫자상의 방법에 사용된다의 xn+1이나 n+다음 1반복,는 다른 의미를 가진 첨자에 관여하지 않겠다고.(예를 들어, x(n+1))f(x(n)).만약 함수 f연속 미분 가능은, 융합을 위한 충분 조건이다.도함수의 스펙트럼 반경이 고정점 근방에서 1로 엄격하게 제한된다.이 조건이 고정점에서 유지되면 충분히 작은 근린(인력의 분지)이 존재해야 합니다.

선형 시스템

선형 방정식 시스템의 경우, 반복 방법의 두 가지 주요 클래스는 고정 반복 방법과 보다 일반적인 크릴로프 부분 공간 방법이다.

고정 반복 방법

서론

정상 반복법은 원래 시스템에 근사한 연산자와 선형 시스템을 풀고 결과(잔차)의 오차 측정에 기초하여 이 과정을 반복하는 "수정 방정식"을 형성한다.이러한 방법들은 도출, 구현 및 분석이 간단하지만, 수렴은 제한된 클래스의 행렬에 대해서만 보장됩니다.

정의.

반복 방법은 다음과 같이 정의됩니다.

$\displaystyle \mathbf {x}^{k+1}:=Psi(\mathbf {x}^{k}),\display k\geq 0}$

또한 정확한 $솔루션{\displaystyle {\mathbf{}}^{}}$ x$$${\displaystyle \mu \mathbf{}}$ {$displaystyle$ \$mathbf {x}$=$\mathbf {b} }$의 경우, A$$ ${\displaystyle =}$ b$${displaystyle $\mathbf {x}$^{*}}}의$$ 오류는 다음과 같습니다.

$\displaystyle \mathbf {e}^{k}=\mathbf {x}-\mathbf {x}^{*},\displaystyle k\geq 0,}$

$행렬{\displaystyle }$ C${\displaystyle {\mathbb{}}^{}}$ ${\displaystyle {}^{}}$n ×$$ \ $displaystyle$ C$\in \mathbb {R}^{n\times$ n$}$이 존재하는 경우 반복 방법을 선형이라고 한다.

$\displaystyle \mathbf {e} ^{k+1}=C\mathbf {e} ^{k}\display \forall \,k\geq 0}$

이 행렬을 반복 행렬이라고 합니다.주어진 $반복행렬{\displaystyle }$ C$(\displaystyle$ C$)$를 갖는 반복방법은 다음 조건이 충족될 경우 수렴(convergent)이라고 한다.

${\displaystyle \lim _{k\rightarrow \infty}C^{k}=0,}$

중요한 정리에 따르면 특정 반복 방법과 반복 $행렬{\displaystyle }$ C$(\displaystyle$ C$)$에 대해 스펙트럼 반지름$C)\$displaystyle $\rho$(C$)$가 단일성보다 작을 경우에만 수렴한다.

${\displaystyle\rho(C)<1,}$

기본 반복 방식은 $매트릭스{\displaystyle }$A(\$displaystyle$ A$)$를 다음과 같이 분할하여 동작합니다.

${\displaystyle A=M-N}$

$행렬 M$은 쉽게 반전될 수 있습니다.반복 방법은 다음과 같이 정의됩니다.

${\displaystyle M\mathbf {x} ^{k+1}=N\mathbf {x} ^{k}+b,\display k\geq 0,}$

이것으로부터 반복행렬은 다음과 같이 주어진다.

${\displaystyle C=I-M^{-1}A=M^{-1}N}$

예

고정 반복 방법의 기본적인 예에서는 다음과 같은 $행렬{\displaystyle }$A의 분할(\$displaystyle$ A$)$을 사용합니다.

${\displaystyle A=D+L+U,\quad D:=text{diag}((a_{ii})_{i})}$

$여기$서 D$(\displaystyle$ D$)$는 A$(\displaystyle$ A$)$의 대각선 $부분$일 뿐이고 L(\$displaystyle$$$L$)$은 A(\$displaystyle$ A$)$의 엄밀한 하부 삼각형 부분이며 U$(\displaystyle$ U$)$는 $A{\displaystyle }$$(\displaystyle$ A$)$의$$$엄밀$한 상부 삼각형 부분입니다.

• Richardson 메서드:${\displaystyle }M{\displaystyle }$ : ${\displaystyle =}$ ${\displaystyle 1\frac{\mathrm{}}{}}$ ${\displaystyle \omega I}$ ( ${\displaystyle \mathrm{\omega }}$0$$) { $displaystyle$ M : =$flac {$1$}$ {\ $obega } I$ \ $quad$( \$obega$ \ $neq$0 ) }
• Jacobi $방식{\displaystyle :}$ M : $=$ ${\displaystyle D}$ { $displaystyle$ M : $=$D }
• 감쇠 자코비 $메서드{\displaystyle :}$ ${\displaystyle M\frac{\mathrm{}}{}}$ : ${\displaystyle =}$ ${\displaystyle 1}$ ${\displaystyle \mu }$D ( ${\displaystyle )}$ ${\displaystyle 0}$) { $displaystyle$ M : =$fr frac${1} {\$obega$}}$D\quad$( \$obega$ \ $neq$ 0$)$ }
• 가우스-세이델 방식:${\displaystyle }M{\displaystyle }$ : ${\displaystyle =D}$ +$$ { $displaystyle$ M : $= D$ + $L$}
• 연속과잉법(SOR):${\displaystyle }M{\displaystyle }$ : ${\displaystyle =}$ ${\displaystyle 1\frac{\mathrm{}}{}}$ ${\displaystyle d}$D +${\displaystyle L}$ ( ${\displaystyle \omega 0}$ 0$$) { $displaystyle$ M : =$fr frac${$1$} {\$obega$}}$D$ +$L$ \ $quad$( \$obega$ \ $neq$ 0 $)$
• 대칭적 연속과잉($SSOR{\displaystyle ):}$ ${\displaystyle M\frac{\mathrm{}}{}}$ : ${\displaystyle =}$ ${\displaystyle \frac{1\mathrm{\mu }}{}}$ ${\displaystyle \frac{(}{}2}$ -${\displaystyle \frac{}{}\mu }$ ${\displaystyle \frac{}{}}$( D + ${\displaystyle )}$ ${\displaystyle {}^{}}$) ${\displaystyle {\mathrm{D}}^{}}$- 1 (${\displaystyle }$D + ${\displaystyle )}$U ) (${\displaystyle 0}${ ${\displaystyle 0}$ , 2$}$ ) { $display style$ M : =$frac${1} {\$ope (2-\ope)}}}$ ($D+1-Omega)$

선형 고정 반복 방법을 완화 방법이라고도 합니다.

크릴로프 부분공간법

크릴로프 부분 공간 방법은 연속 행렬 거듭제곱의 시퀀스에 초기 잔차(크릴로프 시퀀스)를 곱한 기초를 형성함으로써 작동한다.그런 다음 형성된 부분 공간에 걸쳐 잔차를 최소화하여 솔루션에 대한 근사치를 형성합니다.이 클래스의 프로토타입 방법은 시스템 $행렬{\displaystyle }$ A$(\display style$ A$)$가 대칭 정의 정의라고 가정하는 켤레 경사법(CG)이다.대칭(및 아마도 무기한)의 경우 {\$displaystyle$ A$}$은(는) 최소 잔류법(MINRES)으로 작동합니다.비대칭행렬의 경우 일반화 최소잔차법(GMRES) 및 쌍공역구배법(BiCG) 등의 방법이 도출되었다.

크릴로프 부분공간법의 수렴

이 방법들은 기본이 되기 때문에 N회 반복으로 수렴되는 것이 명백합니다.여기서 N은 시스템사이즈입니다.그러나 반올림 오류가 있는 경우 이 문장은 유지되지 않습니다. 더욱이 실제로 N은 매우 클 수 있으며 반복 프로세스는 이미 훨씬 전에 충분한 정확도에 도달합니다.이러한 방법의 분석은 운영자의 스펙트럼의 복잡한 기능에 따라 어렵다.

프리컨디셔너

정지 반복 방법에 나타나는 근사 연산자는 GMRES와 같은 크릴로프 부분 공간 방법에도 통합될 수 있으며(또는 사전 조건화된 크릴로프 방법은 정지 반복 방법의 가속으로 간주될 수 있음), 여기에서 원래의 연산자가 추정상 더 나은 조건의 연산자로 변환되는 것이 된다.전제조건의 건설은 대규모 연구 영역이다.

역사

아마도 선형 시스템을 푸는 첫 번째 반복적인 방법은 가우스의 제자에게 보낸 편지에 나타나 있을 것이다.그는 잔차가 가장 큰^{[citation needed]} 성분을 반복적으로 풀어서 4x4 방정식을 풀자고 제안했다.

고정 반복 방법의 이론은 1950년대부터 D.M. Young의 연구로 확고히 확립되었다.공역 구배법도 1950년대에 발명되어 코넬리우스 란초스, 마그누스 헤스테네스, 에두아르트 스티펠이 독자적으로 개발하였으나, 그 성격과 적용 가능성은 당시에는 오해되었다.1970년대에야 공역 기반 방법이 편미분 방정식, 특히 타원형에 매우 잘 작동한다는 것을 깨달았다.

「 」를 참조해 주세요.

• 폐쇄형식
• 반복적인 개선
• 비선형 최소 제곱
• 수치 분석
• 루트 검색 알고리즘

레퍼런스

외부 링크

• 선형 시스템 솔루션용 템플릿
• Y. Sad:희박한 선형 시스템을 위한 반복적 방법, 제1판, PWS 1996