반복법

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 선형 시스템
- 2.1. 정적 반복법 (Stationary Iterative Methods)
  - 2.1.1. 예시
- 2.2. 크릴로프 부분 공간 방법 (Krylov Subspace Methods)
3. 비선형 방정식
4. 고유값 문제
- 4.1. 멱승법 (Power Iteration)
- 4.2. 야코비 방법 (Jacobi Method)
5. 부동점 반복법 (Fixed-Point Iteration)
6. 알고리즘
7. 역사
참조

1. 개요

반복법은 연립 일차 방정식, 비선형 방정식, 고유값 문제 등 다양한 수학적 문제를 해결하기 위해 사용되는 알고리즘이다. 선형 시스템의 경우, 정상 반복법과 크릴로프 부분 공간 방법이 주요하며, 야코비 방법, 가우스-자이델 방법, 켤레 기울기 방법 등이 대표적인 예시이다. 비선형 방정식에서는 뉴턴 방법, 할리 방법과 같은 방법이 활용되며, 부동점 반복법은 방정식의 해를 찾는 데 사용되는 또 다른 접근 방식이다. 반복법은 자맘시드 알 카시, 카를 프리드리히 가우스 등의 연구를 통해 발전해 왔으며, 1950년대 이후 이론이 확립되고 1970년대에 편미분 방정식 해결에 효과적임이 밝혀졌다.

더 읽어볼만한 페이지

반복법 - 이산화
이산화는 연속적인 미분 방정식을 수치 해석에 적합하게 변환하거나, 연속 시간 모델을 이산 시간 모델로 변환하거나, 연속형 변수를 이산형 변수로 변환하는 과정을 의미한다.
수치해석학 - 수학적 최적화
수학적 최적화는 주어진 집합에서 실수 또는 정수 변수를 갖는 함수의 최댓값이나 최솟값을 찾는 문제로, 변수 종류, 제약 조건, 목적 함수 개수에 따라 다양한 분야로 나뉘며 여러 학문 분야에서 활용된다.
수치해석학 - 선형대수학
선형대수학은 벡터, 벡터 공간, 행렬 등의 개념으로 선형 방정식과 선형 변환을 연구하는 수학 분야로, 선형성을 활용해 행렬로 표현 및 계산하며, 연립일차방정식 해법, 고유값/고유벡터를 통한 행렬 분석, 벡터 공간의 기저와 차원 등을 다루고 물리학, 공학, 컴퓨터 과학 등 다양한 분야에 응용된다.

반복법
개요
종류	수치해석 알고리즘
분야	수학, 컴퓨터 과학
목적	해의 근사값 계산
특징	초기 추측값에서 반복적으로 해를 개선
상세 정보
설명	반복적인 과정을 통해 해를 구하는 알고리즘
활용	선형 시스템, 비선형 방정식, 최적화 문제 등
장점	직접적인 방법보다 계산 비용이 저렴할 수 있음
단점	수렴하지 않거나 수렴 속도가 느릴 수 있음
관련 개념
직접법	해를 직접 계산하는 방법
수렴	반복 과정이 해에 가까워지는 것
발산	반복 과정이 해에서 멀어지는 것
종류 (예시)
선형 시스템	야코비 방법 가우스-자이델 방법 SOR (Successive Over-Relaxation) 방법) 켤레 기울기법
비선형 방정식	뉴턴-랩슨 방법 할선법 브렌트 방법

2. 선형 시스템

선형 방정식계에서 반복법은 해를 구하는 데 사용된다. 반복법의 두 가지 주요 부류는 정적 반복법과 크릴로프 부분 공간 방법이 있다.

주어진 함수 ''f''에 대해, ''f''(''x'') = 0을 만족하는 값 ''x''를 구하는 일반적인 알고리즘은 다음과 같다.

# 초기값 ''x''₀ ∈ '''R'''^''n''를 정하고, ''i'' = 0으로 한다.

# 점화식 $x_{i+1}=g(x_i)$ 에 의해 ''x''_{''i'' + 1}를 구한다. 여기서 ''g''는 ''f''로부터 결정되는 함수이다.

# 적절한 판단 기준 $r(x_i, x_{i+1})\leq \epsilon \quad ( \epsilon > 0)$ 이 성립하면(이를 수렴이라고 표현한다) 중단하고, ''x_i''를 해로 한다. 그렇지 않으면 ''i'' → ''i'' + 1로 하고, 스텝 2로 돌아간다. 일반적으로, 판단 기준에는 $r(x_i, x_{i+1}) = |x_{i+1}- x_i|$ 등이 채택된다.

2. 1. 정적 반복법 (Stationary Iterative Methods)

정적 반복법은 원래 연산자를 근사하는 연산자를 사용하여 연립 일차 방정식을 푸는 방법이다. 이 방법은 결과의 오차 측정(잔차)을 기반으로 "수정 방정식"을 형성하여 반복적으로 해를 구한다. 이러한 방법은 유도, 구현 및 분석이 간단하지만, 수렴은 제한된 종류의 행렬에 대해서만 보장된다.^[1]

'''반복법'''은 다음과 같이 정의된다.

:

\mathbf{x}^{k+1} := \Psi (  \mathbf{x}^k ) \,, \quad k\geq0

정확한 해

\mathbf{x}^*

를 갖는 주어진 선형 시스템

A\mathbf x= \mathbf b

에 대한 ''오차''는 다음과 같다.

:

\mathbf{e}^k := \mathbf{x}^k - \mathbf{x}^* \,, \quad k\geq0\,.

반복법이 선형이면 행렬

C \in \R^{n\times n}

가 존재하여

:

\mathbf{e}^{k+1} = C  \mathbf{e}^k   \quad \forall \, k\geq0

이 행렬을 ''반복 행렬''이라고 한다.

주어진 반복 행렬

C

를 갖는 반복법이 수렴한다는 것은 다음이 성립하는 경우이다.

:

\lim_{k\rightarrow \infty} C^k=0\,.

중요한 정리에 따르면, 주어진 반복법과 해당 반복 행렬

C

에 대해 이 방법이 수렴하려면 해당 스펙트럼 반경

\rho(C)

이 1보다 작아야 한다.

:

\rho(C) < 1 \,.

기본적인 반복법은 행렬

A

를 분할하여 작동한다.

:

A = M - N

여기서 행렬

M

은 쉽게 가역할 수 있어야 한다.

이제 반복법은 다음과 같이 정의된다.

:

M \mathbf{x}^{k+1} = N \mathbf{x}^k + b \,, \quad k\geq0\,.

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

:

C = I - M^{-1}A = M^{-1}N\,.

정적 반복법에 나타나는 근사 연산자는 GMRES와 같은 크릴로프 부분 공간 방법에 통합될 수도 있다. 또는, 전처리된 크릴로프 방법을 정상 반복법의 가속으로 간주할 수 있다. 전처리자의 구성은 광범위한 연구 분야이다.

2. 1. 1. 예시

연립 일차 방정식을 푸는 고정 반복법의 예시는 행렬

A

를 다음과 같이 분할하는 방법을 사용한다.^[1]

:

A = D+L+U\,,\quad D := \text{diag}( (a_{ii})_i)

여기서

D

는

A

의 대각 성분만 포함하며,

L

은

A

의 엄격한 하부 삼각 부분이다.^[1] 마찬가지로,

U

는

A

의 엄격한 상부 삼각 부분이다.^[1]

리처드슨 방법: $M:=\frac{1}{\omega} I \quad (\omega \neq 0)$
야코비 방법: $M:=D$
감쇠 야코비 방법: $M:=\frac{1}{\omega}D \quad (\omega \neq 0)$
가우스-자이델 방법: $M:=D+L$
연속적인 과잉 완화 방법 (SOR): $M:=\frac{1}{\omega}D+L \quad (\omega \neq 0)$
대칭 연속 과잉 완화 (SSOR): $M := \frac{1}{\omega (2-\omega)} (D+\omega L) D^{-1} (D+\omega U)$

\quad (\omega \not \in \{0,2\})

선형 고정 반복법은 완화 방법이라고도 한다.^[1]

2. 2. 크릴로프 부분 공간 방법 (Krylov Subspace Methods)

크릴로프 부분 공간 방법^[2]은 초기 잔차에 행렬 거듭제곱을 차례로 곱한 수열의 기저 ('''크릴로프 수열''')를 형성하여 작동한다. 그런 다음 해에 대한 근사값은 형성된 부분 공간에서 잔차를 최소화하여 구한다.

이러한 방법의 대표적인 예로는 시스템 행렬

A

가 대칭 양의 정부호라고 가정하는 켤레 기울기 방법 (CG)이 있다. 대칭(그리고 아마도 부정부호)

A

의 경우에는 최소 잔차 방법 (MINRES)을 사용한다. 비대칭 행렬의 경우에는 일반화 최소 잔차 방법 (GMRES) 및 쌍대 켤레 기울기 방법 (BiCG)과 같은 방법이 있다.

이 방법들은 기저를 형성하므로, 시스템 크기 ''N''번의 반복 내에 수렴한다. 그러나 반올림 오차가 발생하면 이 명제는 성립하지 않으며, 실제로 ''N''이 매우 클 수 있고, 반복 과정은 이미 훨씬 전에 충분한 정확도에 도달한다. 이러한 방법의 분석은 연산자의 스펙트럼의 복잡한 함수에 따라 달라지므로 어렵다.

정상 반복법에 나타나는 근사 연산자는 GMRES와 같은 크릴로프 부분 공간 방법에 통합될 수도 있다(또는, 전처리된 크릴로프 방법을 정상 반복법의 가속으로 간주할 수 있다). 여기에서 원래 연산자를 조건이 더 좋은 연산자로 변환한다. 전처리자의 구성은 광범위한 연구 분야이다.

3. 비선형 방정식

비선형 방정식의 근을 찾는 데 사용되는 반복법은 주어진 함수 ''f''에 대해 ''f''(''x'') = 0을 만족하는 값 ''x''를 구하는 방법이다. 일반적인 알고리즘은 다음과 같다.

1. 초기값 ''x''₀을 정하고, ''i'' = 0으로 한다.

2. 점화식 ''x''_{''i'' + 1} = ''g''(''x''_i)를 이용하여 ''x''_{''i'' + 1}을 구한다. 여기서 ''g''는 ''f''로부터 결정되는 함수이다.

3. 적절한 판단 기준 ''r''(''x''_i, ''x''_{''i'' + 1}) ≤ ε (ε > 0)이 성립하면 (이를 수렴이라고 한다) 중단하고, ''x''_i를 해로 한다. 그렇지 않으면 ''i''를 ''i'' + 1로 하고, 2단계로 돌아간다. 일반적으로 판단 기준에는 ''r''(''x''_i, ''x''_{''i'' + 1}) = |''x''_{''i'' + 1} - ''x''_i| 등이 사용된다.

이러한 반복법의 예시로는 뉴턴 방법, 할리 방법 등이 있다.

3. 1. 뉴턴 방법 (Newton's Method)

뉴턴 방법은 함수의 영점을 찾는 방법 중 하나이다. 미분 값을 이용하여 빠르게 수렴하는 특징을 가지고 있다.^[6]

함수 ''f''가 매끄러운 함수일 때, ''f''의 영점을 구하기 위한 함수 ''g''를 다음과 같이 정의할 수 있다.

:

g(x) = x - \frac{f(x)}{f'(x)}

이 방법은 수렴할 경우 2차 수렴(Quadratic convergence^영어)을 보인다.^[6] 즉, 근을

a

,

\Delta x_i \triangleq x_i - a

로 두고, 다음과 같이 표현할 수 있다.

:

\Delta x_{i+1} =  \frac{f^{\prime\prime} (a)}{2 f^\prime (a)} (\Delta x_{i})^2 + O[\Delta x_{i}]^3

3. 2. 할리 방법 (Halley's Method)

Halley's method^영어에서는

:

g(x)=x-\frac{f(x)}{f'(x)-\frac{f''(x)f(x)}{2f'(x)}}

를 취한다. 이는 수렴하는 경우 3차 수렴이 된다. 즉,

:

\Delta x_{i+1} =  \frac{3 (f^{\prime\prime})^2 - 2 f^\prime f^{\prime\prime\prime}}{12 (f^\prime)^2} (\Delta x_{i})^3 + O[\Delta x_{i}]^4

3. 3. 기타 방법

이분법
듀란-카너법^[6]
브렌트법
구간 뉴턴법^[9]

4. 고유값 문제

행렬의 고유값을 구하는 데 사용되는 반복법에는 다음이 있다.

멱승법은 가장 큰 고유값과 해당 고유 벡터를 찾는 데 사용된다.^[6]
야코비 방법은 대칭 행렬의 고유값을 구하는 데 사용된다.^[6]^[7]

4. 1. 멱승법 (Power Iteration)

고유값 문제에 대한 멱승법은 가장 큰 고유값과 해당 고유 벡터를 찾는 데 사용된다.^[6]

4. 2. 야코비 방법 (Jacobi Method)

야코비 방법은 대칭 행렬의 고유값을 구하는 데 사용된다.^[6]^[7]

5. 부동점 반복법 (Fixed-Point Iteration)

방정식이 ''f''(''x'') = ''x'' 형태로 표현될 수 있고, 해 '''x'''가 함수 ''f''의 매력적인 고정점이라면, 끌개에 있는 점 ''x''₁에서 시작하여 ''x''를 대입하고, ''n'' ≥ 1에 대해 ''x''_''n''+1 = ''f''(''x''_''n'')으로 설정하면 수열 {''x''_''n''}_{''n'' ≥ 1}은 해 '''x'''로 수렴한다. 여기서 ''x''_''n''는 ''x''의 ''n''번째 근사치 또는 반복이며, ''x''_''n''+1은 ''x''의 다음 또는 ''n'' + 1번째 반복이다. 함수 ''f''가 연속 미분 가능하다면, 수렴을 위한 충분 조건은 도함수의 스펙트럼 반경이 고정점 근방에서 1보다 엄격하게 작다는 것이다. 이 조건이 고정점에서 충족되면 충분히 작은 근방(끌개)이 존재해야 한다.

일반화된 '''부동점 반복법'''^[6]^[10] 또는 '''l점 반복법'''은 다음과 같이 표현된다.

: $x_{i+1} = g(x_i, x_{i-1}, \ldots ,x_{i-l+1}),\qquad l\geq 1$

뉴턴법은 l=1인 경우이고, 할선법은 l=2인 경우이다. '''반복 함수''' g는 f(α)=0을 만족하는 참 해 α에 대해 다음을 만족한다.

: $g(\alpha, \alpha,\ldots,\alpha)=\alpha$

따라서 α는 g의 '''부동점'''(Fixed point^영어)이라고 불린다.^[6]^[9]

l=1인 경우, 이 반복법의 수렴성에 대한 충분 조건으로 다음의 '''부동점 정리'''가 성립한다. 부동점 반복법

: $x_{i+1} = g(x_i)$

은 반복 함수 g가 다음 조건을 만족할 때 유일한 부동점 α에 수렴한다.

# g(x)는 구간 I = [a, b]에서 연속이다.

# 모든 x ∈ I에 대해 g(x) ∈ I이다.

# 모든 x, y ∈ I, x ≠ y에 대해 다음을 만족하는 상수 L (0 ≦ L < 1)이 존재한다.

#:: $|g(x)-g(y)|$

부동점 정리의 조건이 성립한다면, 적절한 초기값 x₀ ∈ I을 선택하여 반복 계산을 수행하면, x_i는 구간 I 내에 유일하게 존재하는 부동점 α에 수렴함을 보일 수 있다.^[6]^[9]

6. 알고리즘

반복법의 일반적인 알고리즘은 다음과 같다.

# 초기값 ''x''₀^한국어를 정한다. ''i'' = 0으로 한다.

# 점화식에 의해 ''x''_{''i'' + 1} = g(''x''_i)^한국어를 구한다. 여기서 ''g''는 ''f''로부터 결정되는 함수이다.

# 적절한 판단 기준 r(''x''_i, ''x''_''i''+1) ≤ ε (ε > 0)^한국어이 성립하면 (수렴이라고 표현한다) 중단하고, ''x_i''^한국어를 해로 한다. 그렇지 않으면 ''i'' → ''i'' + 1로 하고, 2단계로 돌아간다. 일반적으로, 판단 기준에는 r(''x''_i, ''x''_''i''+1) = |''x''_''i''+1- ''x''_i|^한국어 등이 채택된다.

위의 알고리즘에서, ''i'' +1^한국어번째 근사해 ''x''_''i''+1^한국어는 바로 앞의 근사해 ''x''_''i''^한국어만의 함수이지만, 이것을 일반화한 '''부동점 반복법'''^[6]^[10] 또는 '''''l''^한국어점 반복법'''은 :''x''_''i''+1 = g(''x''_i, ''x''_''i''-1, … ,''x''_''i''-l''+1), l ≥ 1^한국어의 형태로 나타낸다. 뉴턴법은 ''l'' 이고, 할선법은 ''l'' 인 경우이다. '''반복 함수''' ''g''^한국어는 ''f'' (α) 을 만족하는 참 해 α^한국어에 대해 :g(α, α,…,α)=α^한국어를 만족한다. 이로부터 α^한국어는 ''g''^한국어의 '''부동점''' (Fixed point|픽스드 포인트^영어)이라고 불린다^[6]^[9]。

7. 역사

자맘시드 알 카시는 그의 저서 《현과 사인에 관한 논문》에서 1°의 사인과 π|파이^영어를 고정밀도로 계산하기 위해 반복법을 사용했다.

가우스는 선형 시스템을 풀기 위한 초기 반복법을 그의 제자에게 보낸 편지에서 제시했다. 그는 잔차가 가장 큰 구성 요소를 반복적으로 풀어 4x4 방정식 시스템을 해결하는 방법을 제안했다.

1950년대부터 D.M. 영의 연구로 정지 반복법 이론이 확립되었다. 켤레 기울기 방법 또한 같은 시기에 코르넬리우스 란초스, 마그누스 헤스테네스, 에두아르트 슈티펠에 의해 독립적으로 개발되었지만, 당시에는 그 본질과 적용 가능성이 제대로 이해되지 못했다. 1970년대에 이르러서야 공액 기반 방법이 편미분 방정식, 특히 타원형 방정식에 매우 효과적이라는 것이 밝혀졌다.

참조

_[1] 논문 Recycling Krylov subspaces for CFD applications and a new hybrid recycling solver
_[2] 서적 Krylov Solvers for Linear Algebraic Systems: Krylov Solvers Elsevier
_[3] 웹사이트 Babylonian mathematics https://mathshistory[...] 2000-12-01
_[4] 서적 Fixed-point theorems for compact convex sets Mahlon M day 1960-11-02
_[5] 문서 矢部2006、126頁
_[6] 서적 数値解析入門サイエンス社 2003-06
_[7] 서적 数値解析第2版共立出版
_[8] 서적 共役勾配法 1977
_[9] 서적 精度保証付き数値計算の基礎コロナ社
_[10] 서적 Cで学ぶ数値計算アルゴリズム共立出版

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com