야코비 방법

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

1. 개요
2. 기본 원리
3. 수렴 조건
4. 알고리즘
5. 장점 및 단점
- 5.1. 장점
- 5.2. 단점
6. 가중 야코비 방법 (Weighted Jacobi Method)
7. 예제
- 7.1. 예제 1
- 7.2. 예제 2
8. 고유값 문제 (야코비 대각화법)
참조

1. 개요

야코비 방법은 연립 일차 방정식의 해를 구하는 반복적인 수치 해석 방법이다. 행렬을 대각, 하삼각, 상삼각 행렬로 분리하여 반복식을 통해 해를 구하며, 병렬 계산에 적합하다는 장점이 있다. 수렴 조건은 반복 행렬의 스펙트럼 반경이 1보다 작을 때 보장되며, 행렬이 엄격하게 대각 지배 행렬이거나 기약 대각 지배 행렬일 경우 수렴이 보장된다. 또한, 가중 야코비 방법은 수렴 속도를 개선하기 위해 가중치를 도입한 방법이다. 야코비 방법은 실수 대칭 행렬의 고유값과 고유 벡터를 구하는 야코비 대각화법으로도 활용된다.

더 읽어볼만한 페이지

완화법 (반복법) - 가우스-자이델 방법
가우스-자이델 방법은 선형 연립 방정식의 해를 반복적으로 근사하는 수치 해석 방법으로, 이전 반복에서 계산된 값을 사용하여 변수를 업데이트하며, 야코비 방법보다 빠르게 수렴하지만 병렬 처리가 어렵고, 행렬이 대각 지배적이거나 대칭 양의 정부호 행렬일 때 수렴이 보장된다.
완화법 (반복법) - 축차가속완화법
축차과잉완화법(SOR)은 가우스-자이델 방법의 개선된 형태로, 행렬 분해와 완화 계수를 이용하여 선형 연립 방정식의 수렴 속도를 향상시키는 반복적인 방법입니다.
수치선형대수학 - 가우스 소거법
가우스 소거법은 연립 일차 방정식의 해를 구하기 위해 행렬을 사다리꼴로 변환하는 알고리즘이며, 기본 행 연산을 통해 전진 소거와 후퇴 대입 단계를 거쳐 해를 계산하고, 행렬식 계산 등 다양한 분야에 응용된다.
수치선형대수학 - LINPACK
LINPACK은 부동소수점 연산 성능을 평가하는 벤치마크 프로그램이자 FORTRAN 라이브러리로, 슈퍼컴퓨터 성능 측정 기준으로 사용되는 HPLinpack 벤치마크의 기반이 되었으며, TOP500 목록에서 고성능 컴퓨터 순위를 결정하는 데 기여한다.

야코비 방법
개요
종류	반복법
분야	수치해석학
목적	선형 방정식 시스템 해 구하기
창시자	카를 구스타프 야코프 야코비
설명
정의	야코비 방법은 선형 방정식 시스템을 푸는 데 사용되는 반복적인 알고리즘이다. 대각 행렬이 지배적인 행렬에 대한 선형 방정식 시스템을 결정하기 위한 것이다.
반복 공식	x^(k+1)_i = (b_i - Σ(j≠i) a_ij x^(k)_j) / a_ii, 여기서 i = 1, 2, ..., n
다른 이름	야코비 반복법, 치환법
절차
초기 추정	해에 대한 초기 추정값 x^(0)을 선택한다.
반복	수렴할 때까지 다음 공식을 사용하여 x^(k+1)을 계산한다: x^(k+1)_i = (b_i - Σ(j≠i) a_ij x^(k)_j) / a_ii, 여기서 i = 1, 2, ..., n
수렴 판정	\|\|x^(k+1) - x^(k)\|\| < tolerance 또는 최대 반복 횟수에 도달하면 반복을 중단한다.
결과	최종 추정값 x^(k+1)은 선형 방정식 시스템의 해이다.
장단점
장점	구현이 간단하고 각 반복 계산이 단순하다.
단점	수렴 속도가 느릴 수 있으며, 모든 행렬에 대해 수렴이 보장되지 않는다. 특히 대각 지배 조건이 충족되지 않으면 발산할 수 있다.
수렴 조건
필요 조건	야코비 방법은 계수 행렬이 대각 지배 행렬일 때 수렴이 보장된다. 즉, 각 행에서 대각 성분의 절댓값이 나머지 성분들의 절댓값의 합보다 크다.
충분 조건	계수 행렬이 대칭 양정치 행렬이면 야코비 방법은 수렴한다.
활용
응용 분야	전산 유체 역학 구조 해석 회로망 분석
예제
선형 방정식 시스템	5x_1 - 2x_2 + 3x_3 = -1 -3x_1 + 9x_2 + x_3 = 2 2x_1 - x_2 - 7x_3 = 3
초기 추정값	x^(0) = (0, 0, 0)
반복 결과	x^(1) = (-0.2, 0.222, -0.429) x^(2) = (0.056, 0.317, -0.319) x^(3) = (-0.065, 0.336, -0.412)
해	x ≈ (-0.07, 0.34, -0.41)
참고 문헌
관련 서적	Richard L. Burden, J. Douglas Faires, 수치해석학, 제9판, Cengage Learning, 2011 Gene H. Golub, Charles F. Van Loan, 행렬 계산, 제3판, Johns Hopkins University Press, 1996
관련 항목
관련 항목	가우스-자이델 방법 반복법 수치해석학

2. 기본 원리

야코비 방법은 주어진 연립 일차 방정식을 다음과 같은 형태로 나타낸다.

: $A\mathbf x = \mathbf b$

여기서 ''A''는 ''n'' × ''n'' 정사각행렬, x는 미지수 벡터, b는 상수 벡터이다. ''A'', x, b는 다음과 같다.

: $A=\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\a_{n1} & a_{n2} & \cdots & a_{nn} \end{bmatrix}, \qquad \mathbf{x} = \begin{bmatrix} x_{1} \\ x_2 \\ \vdots \\ x_n \end{bmatrix} , \qquad \mathbf{b} = \begin{bmatrix} b_{1} \\ b_2 \\ \vdots \\ b_n \end{bmatrix}.$

행렬 ''A''를 대각행렬 ''D'', 하삼각행렬 ''L'', 상삼각행렬 ''U''의 합으로 행렬 분리한다.

: $A=D+L+U \qquad \text{where} \qquad D = \begin{bmatrix} a_{11} & 0 & \cdots & 0 \\ 0 & a_{22} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\0 & 0 & \cdots & a_{nn} \end{bmatrix} \text{ and } L+U = \begin{bmatrix} 0 & a_{12} & \cdots & a_{1n} \\ a_{21} & 0 & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & 0 \end{bmatrix}.$

이를 통해 원래 방정식을 다음과 같이 변형할 수 있다.

: $\mathbf{x}^{(k+1)} = D^{-1} (\mathbf{b} - (L+U) \mathbf{x}^{(k)}),$

여기서 $\mathbf{x}^{(k)}$ 는 ''k''번째 반복에서의 근사해 벡터이다. 위 식을 원소별로 표현하면 다음과 같다.

: $x^{(k+1)}_i = \frac{1}{a_{ii}} \left(b_i -\sum_{j\ne i}a_{ij}x^{(k)}_j\right),\quad i=1,2,\ldots,n.$

초기 추측값 $\mathbf{x}^{(0)}$ (보통 영벡터)로부터 시작하여 위 반복식을 수렴할 때까지 반복한다. $x_i^{(k+1)}$ 의 계산은 자기 자신을 제외한 '''x'''^(''k'')를 필요로 한다. 가우스-자이델 방법과 달리 $x_i^{(k)}$ 를 $x_i^{(k+1)}$ 로 덮어 쓰지 않으므로, ''n''의 두 배의 저장 공간을 필요로 한다.

3원 연립 일차 방정식의 경우,

$\left( \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{array} \right) \left( \begin{array}{c} x_1 \\ x_2 \\ x_3 \end{array} \right) = \left( \begin{array}{c} b_1 \\ b_2 \\ b_3 \end{array} \right)$

에서 k번째 반복에서 x를 구하는 식은 다음과 같다.

$x_1^{(k+1)} = (b_1 - a_{12} x_2^{(k)} - a_{13} x_3^{(k)}) / a_{11}$

$x_2^{(k+1)} = (b_2 - a_{21} x_1^{(k)} - a_{23} x_3^{(k)}) / a_{22}$

$x_3^{(k+1)} = (b_3 - a_{31} x_1^{(k)} - a_{32} x_2^{(k)}) / a_{33}$

야코비 방법은 병렬 계산이 가능하다는 장점이 있다.

3. 수렴 조건

표준적인 수렴 조건(모든 반복 방법에 대해)은 반복 행렬의 스펙트럼 반경이 1보다 작을 때이다.

: $\rho(D^{-1}(L+U)) < 1.$

이 방법이 수렴하기 위한 충분 조건은 행렬 ''A''가 엄격하게 또는 기약 대각 지배 행렬이어야 한다는 것이다. 엄격한 행 대각 지배는 각 행에 대해 대각 성분의 절댓값이 다른 성분들의 절댓값의 합보다 크다는 것을 의미한다.

: $\left | a_{ii} \right | > \sum_{j \ne i} {\left | a_{ij} \right |}.$

야코비 방법은 이러한 조건이 충족되지 않아도 때때로 수렴한다.

야코비 방법은 모든 대칭 양의 정부호 행렬에 대해 수렴하지 않을 수도 있다. 예를 들어 다음과 같다.

: $A =\begin{pmatrix}29 & 2 & 1\\2 & 6 & 1\\1 & 1 & \frac{1}{5}\end{pmatrix}\quad \Rightarrow \quadD^{-1} (L+U) =\begin{pmatrix}0 & \frac{2}{29} & \frac{1}{29}\\\frac{1}{3} & 0 & \frac{1}{6}\\5 & 5 & 0\end{pmatrix}\quad \Rightarrow \quad\rho(D^{-1}(L+U)) \approx 1.0661 \,.$

하지만, 시스템 행렬 $A$ 가 대칭 양의 정부호 유형인 경우 수렴성을 보일 수 있다.

$C = C_\omega = I - \omega D^{-1}A$ 를 반복 행렬이라고 하자.

그러면 다음 조건에서 수렴이 보장된다.

: $\rho(C_\omega) < 1\quad \Longleftrightarrow \quad0 < \omega < \frac{2}{\lambda_\text{max} (D^{-1}A)} \,,$

여기서 $\lambda_\text{max}$ 는 최대 고유값이다.

스펙트럼 반경은 다음과 같이 특정 $\omega = \omega_\text{opt}$ 선택에 대해 최소화될 수 있다.

: $\min_\omega \rho (C_\omega) = \rho (C_{\omega_\text{opt}}) = 1-\frac{2}{\kappa(D^{-1}A)+1}\quad \text{for} \quad\omega_\text{opt} := \frac{2}{\lambda_\text{min}(D^{-1}A)+\lambda_\text{max}(D^{-1}A)} \,,$

여기서 $\kappa$ 는 행렬 조건수이다.

4. 알고리즘

야코비 방법의 알고리즘은 다음과 같다.

반복 계산을 통해 해를 구하는 과정은 아래 의사 코드로 나타낼 수 있다.

```

k = 0

while 수렴에 도달하지 않음 do

for i := 1 step until n do

σ = 0

for j := 1 step until n do

if j ≠ i then

σ = σ + a_ijx_j^(k)

end if

end for

x_i^(k+1) = (b_i - σ) / a_ii

end for

k 증가

end while

```

3원 연립 일차 방정식, 즉

:math:`\left( \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{array} \right) \left( \begin{array}{c} x_1 \\ x_2 \\ x_3 \end{array} \right) = \left( \begin{array}{c} b_1 \\ b_2 \\ b_3 \end{array} \right)`

을 푸는 것을 생각한다. ''k''번째 반복에서 얻어진 x₁의 값을 x₁^(k)로 쓴다. 초깃값 x⁽⁰⁾는 적당한 값(예: 영벡터)이어도 상관없다.

:math:`x_1^{(k+1)} = (b_1 - a_{12} x_2^{(k)} - a_{13} x_3^{(k)}) / a_{11}`

:math:`x_2^{(k+1)} = (b_2 - a_{21} x_1^{(k)} - a_{23} x_3^{(k)}) / a_{22}`

:math:`x_3^{(k+1)} = (b_3 - a_{31} x_1^{(k)} - a_{32} x_2^{(k)}) / a_{33}`

위 식을 반복하면 해를 구할 수 있다.

야코비 방법은 직렬 계산에서는 가우스-자이델 방법보다 느리지만, 각 식이 다른 식에 의존하지 않고 병렬성이 있기 때문에 병렬 계산에서도 사용된다.

5. 장점 및 단점

야코비 방법은 알고리즘이 간단하고 구현하기 쉬우며, 각 반복 단계의 계산이 독립적이므로 병렬 처리에 적합하다. 따라서 대규모 희소 행렬 시스템에서 효과적이다. 하지만, 가우스-자이델 방법 등 다른 반복법에 비해 수렴 속도가 느릴 수 있고, 수렴 조건이 엄격하여 모든 경우에 적용 가능하지 않다는 단점이 있다.

$x_i^{(k+1)}$ 계산에는 자기 자신을 제외한 '''x'''^(''k'')가 필요하다. 가우스-자이델 방법과 달리 $x_i^{(k)}$ 를 $x_i^{(k+1)}$ 로 덮어 쓰지 않기 때문에, ''n''의 두 배의 저장 공간이 필요하다.

5. 1. 장점

야코비 방법은 알고리즘이 간단하고 구현하기 쉬우며, 각 반복 단계의 계산이 독립적이므로 병렬 처리에 적합하다. 따라서 대규모 희소 행렬 시스템에서 효과적이다. 가우스-자이델 방법과 달리 각 식이 다른 식에 의존하지 않아 병렬성이 있다는 장점이 있지만, 직렬 계산에서는 가우스-자이델 방법보다 느리다.

5. 2. 단점

가우스-자이델 방법 등 다른 반복법에 비해 수렴 속도가 느릴 수 있고, 수렴 조건이 엄격하여 모든 경우에 적용 가능하지 않다는 단점이 있다.

x_i^{(k+1)}

계산에는 자기 자신을 제외한 '''x'''^(''k'')가 필요하다. 가우스-자이델 방법과 달리

x_i^{(k)}

를

x_i^{(k+1)}

로 덮어 쓰지 않기 때문에, ''n''의 두 배의 저장 공간이 필요하다.

직렬 계산에서는 가우스-자이델 방법보다 느리지만, 각 식이 다른 식에 의존하지 않고 병렬성이 있어 병렬 계산에 사용될 수 있다.

6. 가중 야코비 방법 (Weighted Jacobi Method)

가중 야코비 방법은 매개변수 $\omega$ 를 사용하여 반복을 계산하는 방법으로, 다음 식으로 표현된다.^[1]

: $\mathbf{x}^{(k+1)} = \omega D^{-1} (\mathbf{b} - (L+U) \mathbf{x}^{(k)}) + \left(1-\omega\right)\mathbf{x}^{(k)}$

여기서 $\omega = 2/3$ 는 일반적으로 사용되는 값이다.^[1]

관계식 $L + U = A - D$ 를 이용하면, 위 식은 다음과 같이 표현할 수도 있다.

: $\mathbf{x}^{(k+1)} = \omega D^{-1} \mathbf{b} + \left( I - \omega D^{-1} A \right) \mathbf{x}^{(k)}$

7. 예제

다음은 야코비 방법을 설명하기 위한 예제이다.

'''예제 1'''

다음 선형 시스템을 야코비 방법으로 풀어보자.

: $Ax=b$ 형태의 선형 시스템과 초기 추정치 $x^{(0)}$ 은 다음과 같다.

: $A=\begin{bmatrix}2 & 1 \\5 & 7 \\\end{bmatrix},\ b=\begin{bmatrix}11 \\13 \\\end{bmatrix}\quad \text{and} \quad x^{(0)} =\begin{bmatrix}1 \\1 \\\end{bmatrix} .$

방정식 $x^{(k+1)}=D^{-1}(b - (L+U)x^{(k)})$ 를 사용하여 $x$ 를 추정한다. 이 식을 $D^{-1}(b - (L+U)x^{(k)}) = Tx^{(k)} + C$ 로 다시 쓸 수 있는데, 여기서 $T=-D^{-1}(L+U)$ 이고 $C = D^{-1}b$ 이다. 주어진 값을 이용하면 다음과 같다.

$D^{-1}=\begin{bmatrix}1/2 & 0 \\0 & 1/7 \\\end{bmatrix},\ L=\begin{bmatrix}0 & 0 \\5 & 0 \\\end{bmatrix}\quad \text{and} \quad U =\begin{bmatrix}0 & 1 \\0 & 0 \\\end{bmatrix} .$

$T=-D^{-1}(L+U)$ 는 다음과 같이 계산된다.

$T=\begin{bmatrix}1/2 & 0 \\0 & 1/7 \\\end{bmatrix}\left\{\begin{bmatrix}0 & 0 \\$

5 & 0 \\

\end{bmatrix}+\begin{bmatrix}0 & -1 \\0 & 0 \\\end{bmatrix}\right\}=\begin{bmatrix}0 & -1/2 \\

5/7 & 0 \\

\end{bmatrix} .

또한,

C

는 다음과 같이 계산된다.

C =\begin{bmatrix}1/2 & 0 \\0 & 1/7 \\\end{bmatrix}\begin{bmatrix}11 \\13 \\\end{bmatrix}=\begin{bmatrix}11/2 \\13/7 \\\end{bmatrix}.

T

와

C

를 계산하여

x

를

x^{(1)}= Tx^{(0)}+C

로 추정하면 다음과 같다.

x^{(1)}=\begin{bmatrix}0 & -1/2 \\

5/7 & 0 \\

\end{bmatrix}\begin{bmatrix}1 \\1 \\\end{bmatrix}+\begin{bmatrix}11/2 \\13/7 \\\end{bmatrix}=\begin{bmatrix}5.0 \\8/7 \\\end{bmatrix}\approx\begin{bmatrix}5 \\1.143 \\\end{bmatrix} .

다음 반복을 수행하면 다음과 같다.

x^{(2)}=\begin{bmatrix}0 & -1/2 \\

5/7 & 0 \\

\end{bmatrix}\begin{bmatrix}5.0 \\8/7 \\\end{bmatrix}+\begin{bmatrix}11/2 \\13/7 \\\end{bmatrix}=\begin{bmatrix}69/14 \\

12/7 \\

\end{bmatrix}\approx\begin{bmatrix}4.929 \\

1.714 \\

\end{bmatrix} .

이 과정을

\|Ax^{(n)} - b\|

가 충분히 작아질 때까지 반복한다. 25번 반복 후의 해는 다음과 같다.

:

x=\begin{bmatrix}7.111\\

3.222

\end{bmatrix}.

'''예제 2'''

다음과 같은 선형 시스템이 주어졌다고 가정해 보자.

:

\begin{align}10x_1 -   x_2 +  2x_3 & = 6, \\

x_1 + 11x_2 - x_3 + 3x_4 & = 25, \\

2x_1- x_2+ 10x_3 - x_4 & = -11, \\3x_2 - x_3 + 8x_4 & = 15.\end{align}

(0, 0, 0, 0)을 초기 근사값으로 선택하면, 첫 번째 근사해는 다음과 같다.

:

\begin{align}x_1 & = (6 + 0 - (2 * 0)) / 10 = 0.6, \\x_2 & = (25 + 0 + 0 - (3 * 0)) / 11 = 25/11 = 2.2727, \\x_3 & = (-11 - (2 * 0) + 0 + 0) / 10 = -1.1,\\x_4 & = (15 - (3 * 0) + 0) / 8 = 1.875.\end{align}

얻어진 근사값을 사용하여, 원하는 정확도에 도달할 때까지 반복 절차를 반복한다. 다음은 5번의 반복 후의 근사해이다.

$x_1$	$x_2$	$x_3$	$x_4$
0.6	2.27272	-1.1	1.875
1.04727	1.7159	-0.80522	0.88522
0.93263	2.05330	-1.0493	1.13088
1.01519	1.95369	-0.9681	0.97384
0.98899	2.0114	-1.0102	1.02135

시스템의 정확한 해는 (1, 2, -1, 1)이다.

7. 1. 예제 1

다음 선형 시스템을 야코비 방법으로 풀어보자.

:

Ax=b

형태의 선형 시스템과 초기 추정치

x^{(0)}

은 다음과 같다.

:

A=\begin{bmatrix}2 & 1 \\5 & 7 \\\end{bmatrix},\ b=\begin{bmatrix}11 \\13 \\\end{bmatrix}\quad \text{and} \quad x^{(0)} =\begin{bmatrix}1 \\1 \\\end{bmatrix} .

방정식

x^{(k+1)}=D^{-1}(b - (L+U)x^{(k)})

를 사용하여

x

를 추정한다. 이 식을

D^{-1}(b - (L+U)x^{(k)}) = Tx^{(k)} + C

로 다시 쓸 수 있는데, 여기서

T=-D^{-1}(L+U)

이고

C = D^{-1}b

이다. 주어진 값을 이용하면 다음과 같다.

D^{-1}=\begin{bmatrix}1/2 & 0 \\0 & 1/7 \\\end{bmatrix},\ L=\begin{bmatrix}0 & 0 \\5 & 0 \\\end{bmatrix}\quad \text{and}  \quad U =\begin{bmatrix}0 & 1 \\0 & 0 \\\end{bmatrix} .

T=-D^{-1}(L+U)

는 다음과 같이 계산된다.

T=\begin{bmatrix}1/2 & 0 \\0 & 1/7 \\\end{bmatrix}\left\{\begin{bmatrix}0 & 0 \\

5 & 0 \\

\end{bmatrix}+\begin{bmatrix}0 & -1 \\0 & 0 \\\end{bmatrix}\right\}=\begin{bmatrix}0 & -1/2 \\

5/7 & 0 \\

\end{bmatrix} .

또한,

C

는 다음과 같이 계산된다.

C =\begin{bmatrix}1/2 & 0 \\0 & 1/7 \\\end{bmatrix}\begin{bmatrix}11 \\13 \\\end{bmatrix}=\begin{bmatrix}11/2 \\13/7 \\\end{bmatrix}.

T

와

C

를 계산하여

x

를

x^{(1)}= Tx^{(0)}+C

로 추정하면 다음과 같다.

x^{(1)}=\begin{bmatrix}0 & -1/2 \\

5/7 & 0 \\

\end{bmatrix}\begin{bmatrix}1 \\1 \\\end{bmatrix}+\begin{bmatrix}11/2 \\13/7 \\\end{bmatrix}=\begin{bmatrix}5.0 \\8/7 \\\end{bmatrix}\approx\begin{bmatrix}5 \\1.143 \\\end{bmatrix} .

다음 반복을 수행하면 다음과 같다.

x^{(2)}=\begin{bmatrix}0 & -1/2 \\

5/7 & 0 \\

\end{bmatrix}\begin{bmatrix}5.0 \\8/7 \\\end{bmatrix}+\begin{bmatrix}11/2 \\13/7 \\\end{bmatrix}=\begin{bmatrix}69/14 \\

12/7 \\

\end{bmatrix}\approx\begin{bmatrix}4.929 \\

1.714 \\

\end{bmatrix} .

이 과정을

\|Ax^{(n)} - b\|

가 충분히 작아질 때까지 반복한다. 25번 반복 후의 해는 다음과 같다.

:

x=\begin{bmatrix}7.111\\

3.222

\end{bmatrix}.

7. 2. 예제 2

다음과 같은 선형 시스템이 주어졌다고 가정해 보자.

:

\begin{align}10x_1 -   x_2 +  2x_3 & = 6, \\

x_1 + 11x_2 - x_3 + 3x_4 & = 25, \\

2x_1- x_2+ 10x_3 - x_4 & = -11, \\3x_2 - x_3 + 8x_4 & = 15.\end{align}

(0, 0, 0, 0)을 초기 근사값으로 선택하면, 첫 번째 근사해는 다음과 같다.

:

\begin{align}x_1 & = (6 + 0 - (2 * 0)) / 10 = 0.6, \\x_2 & = (25 + 0 + 0 - (3 * 0)) / 11 = 25/11 = 2.2727, \\x_3 & = (-11 - (2 * 0) + 0 + 0) / 10 = -1.1,\\x_4 & = (15 - (3 * 0) + 0) / 8 = 1.875.\end{align}

얻어진 근사값을 사용하여, 원하는 정확도에 도달할 때까지 반복 절차를 반복한다. 다음은 5번의 반복 후의 근사해이다.

$x_1$	$x_2$	$x_3$	$x_4$
0.6	2.27272	-1.1	1.875
1.04727	1.7159	-0.80522	0.88522
0.93263	2.05330	-1.0493	1.13088
1.01519	1.95369	-0.9681	0.97384
0.98899	2.0114	-1.0102	1.02135

시스템의 정확한 해는 (1, 2, -1, 1)이다.

8. 고유값 문제 (야코비 대각화법)

야코비 방법은 실수 대칭 행렬의 고유값 및 고유 벡터를 구하는 데에도 사용될 수 있다. 혼동을 피하기 위해 야코비 대각화법이라고도 한다.

$n$ 차의 실수 대칭 행렬 $A$ 에 대해 $G(p, q, \theta)$ 에 의한 닮음 변환, 즉 기븐스 회전을 실행함으로써 비대각 요소 $a_{ij}(i \ne j)$ 의 최댓값 $a_{pq}$ 가 0이 되도록 한다.

: $B=G^TAG$

이것에 의해 행렬 $B$ 의 각 요소는 다음과 같이 된다. 단, $i,j \ne p,q$ 이다.

: $\begin{cases} b_{pp} = a_{pp}\cos^2\theta + a_{qq}\sin^2\theta - 2a_{pq}\sin\theta\cos\theta ,\\b_{qq} = a_{pp}\sin^2\theta + a_{qq}\cos^2\theta + 2a_{pq}\sin\theta\cos\theta ,\\b_{pq} = b_{qp} = \frac{1}{2}(a_{pp}-a_{qq})\sin2\theta + a_{pq}\cos2\theta ,\\b_{ij} = a_{ij} ,\\b_{pj} = a_{pj}\cos\theta - a_{qj}\sin\theta ,\\b_{qj} = a_{pj}\sin\theta + a_{qj}\cos\theta ,\\b_{ip} = a_{ip}\cos\theta - a_{iq}\sin\theta ,\\b_{iq} = a_{ip}\sin\theta + a_{iq}\cos\theta\end{cases}$

여기서, $a_{pq} \ne 0$ 일 때 $b_{pq}=0$ 이 되는 $\theta$ 는 위 식으로부터

: $\tan 2\theta = \frac{-2a_{pq}}{(a_{pp}-a_{qq})}$

에서 구할 수 있음을 알 수 있다.

기븐스 회전을 모든 비대각 요소가 거의 0이 될 때까지 반복하면, 실수 대칭 행렬 $A$ 가 대각화된 형태가 되므로, 그 대각 요소가 $A$ 의 고유값이 된다. 또한, $A$ 가 k회 변환된 행렬을 $A_{k}$ , k번째 기븐스 회전을 나타내는 직교 행렬을 $G_{k}$ 라고 하면,

: $A_k = G_k^T A_{k-1} G_k = U_k^TAU_k$

:여기서, $U_k = G_1 G_2 G_3 \cdots G_{k-1} G_k$

가 된다. $A_{k}$ 의 모든 비대각 요소가 거의 0이 되었을 때, $U_{k}$ 는 고유 벡터를 늘어놓은 행렬이 된다.

기븐스 회전의 반복 과정에서, 한 번은 0이 된 요소가 그 후의 변환에 의해 0이 되지 않는 경우도 있지만, 변환의 반복에 의해 비대각 항은 0에 가까워진다.

야코비 대각화법은 실수 대칭(또는 복소 에르미트) 행렬에 주로 사용되지만, 비대칭 행렬에 대한 야코비 방법도 연구되었다. 그러나 QR법이 등장한 후에는 비대칭 행렬의 경우 QR법이 주로 사용된다.

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

문의하기 : help@durumis.com