가우스-자이델법

수치 선형 대수학에서, 가우스-자이델 방법(Liebmann 방법 또는 연속 변위 방법)은 선형 방정식의 체계를 푸는 데 사용되는 반복적인 방법이다.독일 수학자 카를 프리드리히 가우스와 필리프 루트비히 폰 자이델의 이름을 따서 지어졌으며 야코비 방법과 유사하다.대각선에 0이 아닌 요소가 있는 모든 행렬에 적용할 수 있지만, 수렴은 행렬이 엄격히 대각선 ^[1]우세이거나 대칭 및 양의 유한인 경우에만 보장됩니다.그것은 1823년 ^[2]가우스가 그의 제자 게링에게 보낸 사적인 편지에서만 언급되었다.1874년 이전에는 세이델에 ^[3]의해 출판되지 않았다.

묘사

가우스-세이델 방법은 x가 불분명한 n개의 선형 방정식의 제곱계를 풀기 위한 반복 기법이다.

A\mathbf {x} =\mathbf {b} .

이것은 반복에 의해 정의됩니다.

L_{*}\mathbf {x}^{(k+1)}=\mathbf {b} -U\mathbf {x}^{(k)},

$\mathbf {x} ^{(k)}$ 서 $\mathbf {x} ^{(k)}$ x ( $\mathbf {x} ^{(k)}$ ) $\mathbf {x} ^{(k)}$ { $displaystyle$ $\$ $mathbf$ $\mathbf {x} ,\,\mathbf {x} ^{(k+1)}$ { $x$ } ^{ ( $\mathbf {x} ^{(k)}$ $k$ ) } $\mathbf {x}$ $、$ x ( $\mathbf {x} ,\,\mathbf {x} ^{(k+1)}$ $+$ $)$ 의 $\mathbf {x} ^{(k)}$ $\mathbf {x} ,\,\mathbf {x} ^{(k+1)}$ $\mathbf {x} ,\,\mathbf {x} ^{(k+1)}$ 근사치 또는 반복치이며, 행렬은 $\mathbf {x}$ x ( k + 1)의 다음 또는 k + 1 $반복치입니다.$ laystyle $L_{*}$ 및 완전히 위쪽 삼각 구성 $요소$ U(\ $displaystyle$ U $)$ 즉 $U$ , $A=L_{*}+U$ $A=L_{*}+U$ $A=L_{*}+U$ + $A=L_{*}+U$ (\ $displaystyle$ A = $L_{*}$ + $U$ ^[4]입니다.

자세한 내용은 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{)}={\begin{bmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\end{bmatrix}},\qquad\mathbf{b}={\begin{bmatrix}b_{1}\\b_{2}\\\vdo &.이익 \\b_{n}\end{bmatrix}}.

그런 다음 A를 아래쪽 삼각형 성분과 엄밀하게 위쪽 삼각형 성분으로 분해하면 다음과 같이 계산됩니다.

A=L_{*}+U\qquad{\text{어디}}\qquad L_{*}={\begin{bmatrix}a_{11}&, 0&, \cdots &, 0\\a_{21}&, a_{22}&, \cdots, 0\\\vdots &, \vdots &, \ddots &, \vdots \\a_{n1}&, a_{n2}&, \cdots &, a_{nn}\end{bmatrix}},\quad U={\begin{bmatrix}0&, a_{12}&, \cdots &, a_{1n}\\0&, 0&, \cdots &, a_{2n}\\\vdots &, \v &.다츠&\ddots, \vdots \\0&, 0&, \cdots &, 0\end{bmatrix}}&.

선형 방정식 시스템은 다음과 같이 다시 작성할 수 있습니다.

L_{*}\mathbf {x} =\mathbf {b} - U\mathbf {x}

이제 가우스-세이델 방법은 x에 대한 이 식의 왼쪽을 오른쪽에 있는 x에 대한 이전 값을 사용하여 해결합니다.분석적으로, 이것은 다음과 같이 쓸 수 있다.

\displaystyle \mathbf {x}^{(k+1)}=L_{*}^{-1}\left(\mathbf {b} -U\mathbf {x}^{(k)}\오른쪽).}

단, L ${\(\$ 의 삼각형을 이용하여 x의 요소를^(k+1) 순차적으로 계산할 수 있습니다.

({displaystyle x_{i}^{(k+1)}=paramfrac {1}{a_{i}-\sum _{j=1}^{i-1}a_{ij}x_{j}^{(k+1)^{j=i+1}-\sum _{ij}^{j}^{j}{k}^{dism}^{{dism}}}}}}{{i}}}}}{displaystyflft(k})

^[5]

이 절차는 일반적으로 반복에 의한 변화가 충분히 작은 잔차 등 일부 공차 미만이 될 때까지 계속됩니다.

논의

가우스-세이델 방법의 요소별 공식은 야코비 방법의 공식과 매우 유사하다.

x의^(k+1) 계산은 이미 계산된 x의 요소와^(k+1) k+1 반복에서 계산되지 않은 x의^(k) 요소만 사용합니다.즉, Jacobi 방법과는 달리 요소가 계산될 때 덮어쓸 수 있으므로 하나의 스토리지 벡터만 필요하므로 매우 큰 문제에 유리할 수 있습니다.

그러나, 야코비 방법과는 달리, 각 요소에 대한 계산은 일반적으로 병렬로 구현하기가 훨씬 더 어렵다. 왜냐하면 그것들은 매우 긴 임계 경로를 가질 수 있고, 따라서 희박한 행렬에 대해 가장 실현가능하기 때문이다.또한 각 반복에서의 값은 원래 방정식의 순서에 따라 달라집니다.

가우스-자이델은 θ $\omega =1$ $(\$ \Omega $=1$ 인 SOR(연속 과다섭취)와 동일하다.

컨버전스

가우스-세이델 방법의 수렴 특성은 행렬 A에 따라 달라진다.즉, 이 절차는 다음과 같은 경우에 수렴하는 것으로 알려져 있다.

A는 대칭적인 양의 ^[6]정의 또는
A는 엄격하거나 축소할 수 없을 정도로 ^[7]대각선으로 우세하다.

가우스-세이델 방법은 이러한 조건이 충족되지 않더라도 수렴될 수 있습니다.

알고리즘.

이 알고리즘에서는 요소를 계산할 때 덮어쓸 수 있으므로 하나의 스토리지 벡터만 필요하며 벡터 인덱스는 생략됩니다.알고리즘은 다음과 같습니다.

입력:A,b    출력: "Choose initial uspet"을 선택하여 컨버전스가 될 때까지 솔루션을 반복합니다. i 1에서 1까지 n                   하다σ ← 0위해서 j 1에서 1까지 n              하다한다면 j≠i                                        그 후 ← σ + a secondend_ij_j ifend ( )j     -loop_i) ← (b_i - δ) / aend_ii (i-loop) 컨버전스가 종료되었는지 확인합니다(표준).

예

매트릭스 버전의 예

$A\mathbf {x} =\mathbf {b}$ x $=$ {\ $displaystyle$ A $\mathbf {x}$ =\ $mathbf {b} }$ 로 $A\mathbf {x} =\mathbf {b}$ 표시된 선형 시스템은 다음과 같다.

A={\begin{bmatrix}16&3\\7&-11\\\end{bmatrix}}

A={\begin{bmatrix}16&3\\7&-11\\\end{bmatrix}}

[

A={\begin{bmatrix}16&3\\7&-11\\\end{bmatrix}}

A={\begin{bmatrix}16&3\\7&-11\\\end{bmatrix}}

7 -

]{

displaystyle

A =

bgin

{

bmatrix }16&3\7&-11\end {bmatrix}}

b={\begin{bmatrix}11\\13\end{bmatrix}}.

b={\begin{bmatrix}11\\13\end{bmatrix}}.

b={\begin{bmatrix}11\\13\end{bmatrix}}.

{ 11

13

{

displaystyle

b

= bmatrix}11\13\end {bmatrix}.

}

우리는 그 방정식을 사용하고 싶다.

\displaystyle \mathbf {x}^{(k+1)}=L_{*}^{-1}(\mathbf {b} -U\mathbf {x}^{(k)})}

형태로

\displaystyle \mathbf {x}^{(k+1)}=T\mathbf {x}^{(k)}+C}

여기서:

T=-L_{*}^{-1}U

=

-

T=-L_{*}^{-1}U

T=-L_{*}^{-1}U

-

T=-L_{*}^{-1}U

U {\

displaystyle

T=-

L_{*}^{-1} U

C=L_{*}^{-1}\mathbf {b} .

C

C=L_{*}^{-1}\mathbf {b} .

C=L_{*}^{-1}\mathbf {b} .

C=L_{*}^{-1}\mathbf {b} .

- 1

C=L_{*}^{-1}\mathbf {b} .

. {\

displaystyle

C

=L_{*}^{-1}\mathbf {b}

.}

A $A_{}^{}$ $displaystyle$ $A_{}^{})$ 를 $A_{}^{}$ 하위 삼각 $L_{*}^{}$ L $L_{*}^{}$ ${{*}^}$ 과 $L_{*}^{}$ (와) 상위 삼각 $U_{}^{}$ U $U_{}^{}$ 의 합으로 $A_{}^{}$ 해야 합니다.

L_{*}={\begin{bmatrix}16&0\\7&-11\\\end{bmatrix}}

L_{*}={\begin{bmatrix}16&0\\7&-11\\\end{bmatrix}}

[

L_{*}={\begin{bmatrix}16&0\\7&-11\\\end{bmatrix}}

L_{*}={\begin{bmatrix}16&0\\7&-11\\\end{bmatrix}}

7 -

11

]{

displaystyle

L _ { * } =

begin

{

bmatrix

}

16 &

0

\ \ \ \ \ \ \ \

end

{ bmatrix

L_{*}={\begin{bmatrix}16&0\\7&-11\\\end{bmatrix}}

}

U={\begin{bmatrix}0&3\\0&0\end{bmatrix}}.

U={\begin{bmatrix}0&3\\0&0\end{bmatrix}}.

U={\begin{bmatrix}0&3\\0&0\end{bmatrix}}.

[

U={\begin{bmatrix}0&3\\0&0\end{bmatrix}}.

3

U={\begin{bmatrix}0&3\\0&0\end{bmatrix}}.

. {

displaystyle

U =

begin

{

bmatrix

}

0 }

}

$L$ $L_{*}^{}$ {\ （ { $display$ style L _ { * $L_{*}^{}$ }^{ }}의 역수는 다음과 $L_{*}^{}$ 같습니다.

L_{*}^{-1}={\begin{bmatrix}16&0\\7&-11\end{bmatrix}}^{-1}={\begin{bmatrix}0.0625&0.0000\\0.0398&-0.0909\\\end{bmatrix}}

L_{*}^{-1}={\begin{bmatrix}16&0\\7&-11\end{bmatrix}}^{-1}={\begin{bmatrix}0.0625&0.0000\\0.0398&-0.0909\\\end{bmatrix}}

- 1

L_{*}^{-1}={\begin{bmatrix}16&0\\7&-11\end{bmatrix}}^{-1}={\begin{bmatrix}0.0625&0.0000\\0.0398&-0.0909\\\end{bmatrix}}

[

L_{*}^{-1}={\begin{bmatrix}16&0\\7&-11\end{bmatrix}}^{-1}={\begin{bmatrix}0.0625&0.0000\\0.0398&-0.0909\\\end{bmatrix}}

0

L_{*}^{-1}={\begin{bmatrix}16&0\\7&-11\end{bmatrix}}^{-1}={\begin{bmatrix}0.0625&0.0000\\0.0398&-0.0909\\\end{bmatrix}}

-

L_{*}^{-1}={\begin{bmatrix}16&0\\7&-11\end{bmatrix}}^{-1}={\begin{bmatrix}0.0625&0.0000\\0.0398&-0.0909\\\end{bmatrix}}

-

L_{*}^{-1}={\begin{bmatrix}16&0\\7&-11\end{bmatrix}}^{-1}={\begin{bmatrix}0.0625&0.0000\\0.0398&-0.0909\\\end{bmatrix}}

=

[

L_{*}^{-1}={\begin{bmatrix}16&0\\7&-11\end{bmatrix}}^{-1}={\begin{bmatrix}0.0625&0.0000\\0.0398&-0.0909\\\end{bmatrix}}

.

L_{*}^{-1}={\begin{bmatrix}16&0\\7&-11\end{bmatrix}}^{-1}={\begin{bmatrix}0.0625&0.0000\\0.0398&-0.0909\\\end{bmatrix}}

0.

L_{*}^{-1}={\begin{bmatrix}16&0\\7&-11\end{bmatrix}}^{-1}={\begin{bmatrix}0.0625&0.0000\\0.0398&-0.0909\\\end{bmatrix}}

0.

L_{*}^{-1}={\begin{bmatrix}16&0\\7&-11\end{bmatrix}}^{-1}={\begin{bmatrix}0.0625&0.0000\\0.0398&-0.0909\\\end{bmatrix}}

]{

L_

{*}^{bmatrix}16&0\7&

11

\end{bmatrix}^{-

1}=

bginbatrix025&025&025

. 06. 06.

이제 다음을 찾을 수 있습니다.

({displaystyle T=-{\begin{bmatrix} 0.0625&0.0000\\0.0398&-0.0909\end{bmatrix}\times {bmatrix}\times {bmatrix}\time {bmatrix}\times {bmatrix}0.000&0.09\times)

({displaystyle C=bgin{bmatrix} 0.0625&0.0000\\0.0398&-0.0909\end{bmatrix}}\times {bmatrix}11\13\end{bmatrix}=bgin{bmatrix}0).6875\\-0.7439\end {bmatrix}.}

이것으로 T $displaystyle T_{}^}}$ 와 $T_{}^{}$ C $displaystyle C_{}^{})$ 를 $C_{}^{}$ $T_{}^{}$ 할 수 있으며, 이를 $\mathbf {x}$ 하여 벡터 x $({\$ 를 반복적으로 $\mathbf {x}$ 얻을 수 있습니다.

먼저 x $\mathbf {x} ^{(0)}$ ( $\mathbf {x} ^{(0)}$ ) $\mathbf {x} ^{(0)}$ \ $displaystyle$ \ $mathbf$ { $x$ } ^ { ( 0 $\mathbf {x} ^{(0)}$ ) $\mathbf {x} ^{(0)}$ }를 $\mathbf {x} ^{(0)}$ 해야 합니다.추측이 정확할수록 알고리즘의 실행이 빨라집니다.

다음과 같이 가정합니다.

x^{(0)}=param {bmatrix} 1.0\\1.0\end {bmatrix}.

그런 다음 다음을 계산할 수 있습니다.

(\displaystyle x^{(1)}=bmatrix 0.000&-0.1193\end {bmatrix}\times {bmatrix} 1.0\end {bmatrix}+{\times {bmatrix} 0).6875\\-0.7443\end{bmatrix}=param{bmatrix}0.199\-0.8636\end{bmatrix}}.}

({displaystyle x^{(2)}=param{bmatrix}0.000&-0.1193\end{bmatrix}\times {bmatrix}\times {bmatrix}+{bmatrix}0).6875\\-0.7443\end{bmatrix}=param{bmatrix}0.8494\\-0.6413\end{bmatrix}}.}

(\displaystyle x^{(3)}=bmatrix 0.000&-0.1193\end {bmatrix}\times {bmatrix}\times {bmatrix}\times {bmatrix}+{bmatrix}0\times6875\\-0.7443\end{bmatrix}=param{bmatrix}0.8077\-0.6678\end {bmatrix}.}

x^{(4)}=bmatrix 0.000&-0.1193\end {bmatrix}\times {bmatrix}\times {bmatrix}0.times8077\-0.6678\end{bmatrix}+{\caps{bmatrix}0.6875\\-0.7443\end{bmatrix}=param{bmatrix}0.8127\\-0.6646\end{bmatrix}}.

(\displaystyle x^{(5)}=param{bmatrix}0.000&-0.1193\end{bmatrix}\times {bmatrix}\times {bmatrix}+{bmatrix}0).6875\\-0.7443\end{bmatrix}=param{bmatrix}0.8121\-0.6650\end{bmatrix}}.}

(\displaystyle x^{(6)}=param{bmatrix}0.000&-0.1193\end{bmatrix}\times {bmatrix}+{\param{bmatrix}0).6875\\-0.7443\end{bmatrix}=param{bmatrix}0.8122\-0.6650\end{bmatrix}}.}

({displaystyle x^{(7)}=bmatrix 0.000&-0.1193\end {bmatrix}\times {bmatrix}\times {bmatrix}+{\times {bmatrix}0.000&-0.1193\end {bmatrix}).6875\\-0.7443\end{bmatrix}=param{bmatrix}0.8122\-0.6650\end{bmatrix}}.}

예상대로 알고리즘은 정확한 솔루션으로 수렴됩니다.

\mathbf {x} =A^{-1}\mathbf {b} \ about {\sec{bmatrix} 0.8122\\ - 0.6650\end{bmatrix}}.

사실 행렬 A는 대각선 방향으로 엄격히 우세합니다(그러나 양의 유한은 아닙니다).

매트릭스 버전의 다른 예

$A\mathbf {x} =\mathbf {b}$ x $=$ {\ $displaystyle$ A $\mathbf {x}$ =\ $mathbf {b} }$ 로 $A\mathbf {x} =\mathbf {b}$ 표시된 또 다른 선형 시스템은 다음과 같다.

A={\begin{bmatrix}2&3\\5&7\\\end{bmatrix}}

A={\begin{bmatrix}2&3\\5&7\\\end{bmatrix}}

[

A={\begin{bmatrix}2&3\\5&7\\\end{bmatrix}}

A={\begin{bmatrix}2&3\\5&7\\\end{bmatrix}}

A={\begin{bmatrix}2&3\\5&7\\\end{bmatrix}}

7

]({

displaystyle

A =

bgin

{

bmatrix }

b={\begin{bmatrix}11\\13\\\end{bmatrix}}.

&

3

\ \ 5 &

7

\ \ \ \ \ \

end

{ bmatrix

A={\begin{bmatrix}2&3\\5&7\\\end{bmatrix}}

} ) 및 b

b={\begin{bmatrix}11\\13\\\end{bmatrix}}.

[

b={\begin{bmatrix}11\\13\\\end{bmatrix}}.

].

{

displaystyle

b=

bmatrix

}

11

\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }

}

우리는 그 방정식을 사용하고 싶다.

\displaystyle \mathbf {x}^{(k+1)}=L_{*}^{-1}(\mathbf {b} -U\mathbf {x}^{(k)})}

형태로

\displaystyle \mathbf {x}^{(k+1)}=T\mathbf {x}^{(k)}+C}

여기서:

T=-L_{*}^{-1}U

=

-

T=-L_{*}^{-1}U

T=-L_{*}^{-1}U

-

T=-L_{*}^{-1}U

U {\

displaystyle

T=-

L_{*}^{-1} U

C=L_{*}^{-1}\mathbf {b} .

C

C=L_{*}^{-1}\mathbf {b} .

C=L_{*}^{-1}\mathbf {b} .

C=L_{*}^{-1}\mathbf {b} .

- 1

C=L_{*}^{-1}\mathbf {b} .

. {\

displaystyle

C

=L_{*}^{-1}\mathbf {b}

.}

A $A_{}^{}$ $displaystyle$ $A_{}^{})$ 를 $A_{}^{}$ 하위 삼각 $L_{*}^{}$ L $L_{*}^{}$ ${{*}^}$ 과 $L_{*}^{}$ (와) 상위 삼각 $U_{}^{}$ U $U_{}^{}$ 의 합으로 $A_{}^{}$ 해야 합니다.

L_{*}={\begin{bmatrix}2&0\\5&7\\\end{bmatrix}}

L_{*}={\begin{bmatrix}2&0\\5&7\\\end{bmatrix}}

[

L_{*}={\begin{bmatrix}2&0\\5&7\\\end{bmatrix}}

L_{*}={\begin{bmatrix}2&0\\5&7\\\end{bmatrix}}

L_{*}={\begin{bmatrix}2&0\\5&7\\\end{bmatrix}}

7

]({

displaystyle

L _ { * } =

begin

{

bmatrix

}

2 & 0

\ \ \ \ \ \

end

{ bmatrix

L_{*}={\begin{bmatrix}2&0\\5&7\\\end{bmatrix}}

} )

U={\begin{bmatrix}0&3\\0&0\\\end{bmatrix}}.

U

U={\begin{bmatrix}0&3\\0&0\\\end{bmatrix}}.

[

U={\begin{bmatrix}0&3\\0&0\\\end{bmatrix}}.

3

U={\begin{bmatrix}0&3\\0&0\\\end{bmatrix}}.

. {

displaystyle

U =

begin

{

bmatrix } 0

&

3

\

0

. 0 \ \ \ \ \

batrix

} }

}

$L$ $L_{*}^{}$ {\ （ { $display$ style L _ { * $L_{*}^{}$ }^{ }}의 역수는 다음과 $L_{*}^{}$ 같습니다.

L_{*}^{-1}={\begin{bmatrix}2&0\\5&7\\\end{bmatrix}}^{-1}={\begin{bmatrix}0.500&0.000\\-0.357&0.143\\\end{bmatrix}}

L_{*}^{-1}={\begin{bmatrix}2&0\\5&7\\\end{bmatrix}}^{-1}={\begin{bmatrix}0.500&0.000\\-0.357&0.143\\\end{bmatrix}}

- 1

L_{*}^{-1}={\begin{bmatrix}2&0\\5&7\\\end{bmatrix}}^{-1}={\begin{bmatrix}0.500&0.000\\-0.357&0.143\\\end{bmatrix}}

[

L_{*}^{-1}={\begin{bmatrix}2&0\\5&7\\\end{bmatrix}}^{-1}={\begin{bmatrix}0.500&0.000\\-0.357&0.143\\\end{bmatrix}}

L_{*}^{-1}={\begin{bmatrix}2&0\\5&7\\\end{bmatrix}}^{-1}={\begin{bmatrix}0.500&0.000\\-0.357&0.143\\\end{bmatrix}}

5

L_{*}^{-1}={\begin{bmatrix}2&0\\5&7\\\end{bmatrix}}^{-1}={\begin{bmatrix}0.500&0.000\\-0.357&0.143\\\end{bmatrix}}

-

L_{*}^{-1}={\begin{bmatrix}2&0\\5&7\\\end{bmatrix}}^{-1}={\begin{bmatrix}0.500&0.000\\-0.357&0.143\\\end{bmatrix}}

L_{*}^{-1}={\begin{bmatrix}2&0\\5&7\\\end{bmatrix}}^{-1}={\begin{bmatrix}0.500&0.000\\-0.357&0.143\\\end{bmatrix}}

[

L_{*}^{-1}={\begin{bmatrix}2&0\\5&7\\\end{bmatrix}}^{-1}={\begin{bmatrix}0.500&0.000\\-0.357&0.143\\\end{bmatrix}}

.

L_{*}^{-1}={\begin{bmatrix}2&0\\5&7\\\end{bmatrix}}^{-1}={\begin{bmatrix}0.500&0.000\\-0.357&0.143\\\end{bmatrix}}

.

L_{*}^{-1}={\begin{bmatrix}2&0\\5&7\\\end{bmatrix}}^{-1}={\begin{bmatrix}0.500&0.000\\-0.357&0.143\\\end{bmatrix}}

L_{*}^{-1}={\begin{bmatrix}2&0\\5&7\\\end{bmatrix}}^{-1}={\begin{bmatrix}0.500&0.000\\-0.357&0.143\\\end{bmatrix}}

0.

L_{*}^{-1}={\begin{bmatrix}2&0\\5&7\\\end{bmatrix}}^{-1}={\begin{bmatrix}0.500&0.000\\-0.357&0.143\\\end{bmatrix}}

0 .

displaystyle

_ { * }^{ - 1

L_{*}^{-1}={\begin{bmatrix}2&0\\5&7\\\end{bmatrix}}^{-1}={\begin{bmatrix}0.500&0.000\\-0.357&0.143\\\end{bmatrix}}

=

begin

{

bmatrix

}

2

&

0

\

5

&

7

\ \ \ \ \ \

end begin

{

matrix

} 0 . 500

\ 35 .

0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0

이제 다음을 찾을 수 있습니다.

({displaystyle T=-{\begin{bmatrix}0.500&0.000\\-0.357&0.143\\end{bmatrix}\times {bmatrix}0&3\end{bmatrix}=times{bmatrix}0.000&1.000&0.500&0.100&\end.000\times).

({displaystyle C=bgin{bmatrix}0.500&0.000\-0.357&0.143\\end{bmatrix}}\times {bmatrix}\times {bmatrix}=times {bmatrix}5.500\\\-2.071\\end{bmatrix}\\\\\\\end{bmatrix}\\\\\\\\\times.}

이것으로 T $displaystyle T_{}^}}$ 와 $T_{}^{}$ C $displaystyle C_{}^{})$ 를 $C_{}^{}$ $T_{}^{}$ 할 수 있으며, 이를 $\mathbf {x}$ 하여 벡터 x $({\$ 를 반복적으로 $\mathbf {x}$ 얻을 수 있습니다.

먼저 x $\mathbf {x} ^{(0)}$ ( $\mathbf {x} ^{(0)}$ ) $\mathbf {x} ^{(0)}$ \ $displaystyle$ \ $mathbf$ { $x$ } ^ { ( 0 $\mathbf {x} ^{(0)}$ ) $\mathbf {x} ^{(0)}$ }를 $\mathbf {x} ^{(0)}$ 해야 합니다.추측이 정확할수록 알고리즘의 실행이 빨라집니다.

다음과 같이 가정합니다.

x^{(0)}=control {bmatrix}1.1\2.3\\\end{bmatrix}.

그런 다음 다음을 계산할 수 있습니다.

\displaystyle x^{(1)}=param {bmatrix}0&-1.500\\0&1.071\\end {bmatrix}\times\param {bmatrix}1.1\\2.3\\end{bmatrix}+{\caps{bmatrix}5.500\-2.071\\end{bmatrix}=caps{bmatrix}2.050\0.393\\end{bmatrix}.}

{displaystyle x^{(2)}=bmatrix 0&-1.500\\0&1.071\\end{bmatrix}\times {bmatrix} 2.050\\0.393\\end{bmatrix}+{\disp{bmatrix}5.500\\-2.071\\end{bmatrix}=disp{bmatrix}4.disp\-1.651\\\end{bmatrix}}.}

x^{(3)}=\cdots .,

수렴을 테스트하면 알고리즘이 분산된다는 것을 알 수 있습니다.사실 행렬 A는 대각선 우세도 아니고 양의 유한도 아니다.그 후, 정확한 솔루션으로의 컨버전스

\mathbf {x} =A^{-1}\mathbf {b} =sys{bmatrix}-38\\29\end{bmatrix}

는 보증되지 않으며, 이 경우 발생하지 않습니다.

방정식 버전의 예

여기서_n x는 이러한 방정식과 시작점₀ x의 벡터라고 가정합니다.첫 번째 방정식에서 $x_{n+1},x_{n+2},\dots ,x_{n}.$ 는 x₁ $x_{n+1},x_{n+2},\dots ,x_{n}.$ + $x_{n+1},x_{n+2},\dots ,x_{n}.$ , x $x_{n+1},x_{n+2},\dots ,x_{n}.$ + $x_{n+1},x_{n+2},\dots ,x_{n}.$ x $x_{n+1},x_{n+2},\dots ,x_{n}.$ . $x_{n+1},x_{n+2},\dots ,x_{n}.$ { $display x_{n+1}, x_{n+2},\dots,x_{n}$ 로 $x_{n+1},x_{n+2},\dots ,x_{n}.$ 해결됩니다.다음 방정식은 xs의 이전 값으로 대체됩니다.

명확히 하기 위해 예를 들어보자.

{array}{rrl}10x_{1}&-x_{2}&=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 {array}

$x_{1},x_{2},x_{3}$ 1, $x_{1},x_{2},x_{3}$ , $x_{1},x_{2},x_{3}$ 3 $({$ 및 $x_{1},x_{2},x_{3}$ $x_{4}$ 4 $({$ 에 $x_{4}$ $x_{1},x_{2},x_{3}$ 해결 방법은 다음과 같습니다.

{signed}x_{1}&=x_{2}/5+3/5,\x_{2}&=x_{1}/11+x_{3}/11-3x_{4}/11+25/11,\x_{3}=-x_{1/5+x}/2}\end { aligned}

초기 근사치로 ( $0, 0, 0, 0)$ 을 선택한 다음 첫 번째 근사해를 다음에 나타냅니다.

{displaystyle {signed}x_{1}&=3/5=0.6,\x_{2}&=(3/5)/10/11/11=2.3272,\x_{3}&=-5+(1.32)/10/10/{2}&=0-22/25/55.\end { aligned}

구한 근사치를 사용하여 원하는 정확도에 도달할 때까지 반복 절차를 반복합니다.다음은 4회 반복한 후의 대략적인 해결 방법입니다.

{\displaystyle {lll} {lll} x_{1} & x _ { 4} \ \ hline 0 . 6 & 2 . 32727 & 0 . 887864 \ 1 . 03018 & 2.03694 & 1.01446 & 984 \ 1 . 001 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 3272727 27 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 .

시스템의 정확한 솔루션은 $(1,$ 2 $, -1, 1)$ 입니다.

Python 및 NumPy 사용 예시

다음 수치 절차는 솔루션 벡터를 생성하기 위해 단순하게 반복합니다.

수입품 수치 ~하듯이 np  반복_제한 = 1000  # 매트릭스 초기화 A = np.배열([[10., -1., 2., 0.],               [-1., 11., -1., 3.],               [2., -1., 10., -1.],               [0., 3., -1., 8.]]) # RHS 벡터 초기화 b = np.배열([6.0, 25.0, -11.0, 15.0])  인쇄물("방정식 체계:") 위해서 i 에 범위(A.모양.[0]):     배를 젓다 = ["{0:3g}*x{1}".포맷(A[i, j], j + 1) 위해서 j 에 범위(A.모양.[1])]     인쇄물("[{0}] = [{1:3g}]".포맷(" + ".합류하다(배를 젓다), b[i]))  x = np.0과 같은(b) 위해서 카운트 에 범위(1, 반복_제한):     x_new = np.0과 같은(x)     인쇄물(「반복합니다.{0}:{1}".포맷(카운트, x))     위해서 i 에 범위(A.모양.[0]):         s1 = np.점(A[i, :i], x_new[:i])         s2 = np.점(A[i, i + 1 :], x[i + 1 :])         x_new[i] = (b[i] - s1 - s2) / A[i, i]     한다면 np.모두 닫다(x, x_new, 반응하다=1e-8):         브레이크.     x = x_new  인쇄물("솔루션:{0}".포맷(x)) 에러 = np.점(A, x) - b 인쇄물("오류:{0}".포맷(에러))

출력을 생성합니다.

방정식 체계: [ 10 * x 1 + - 1 * x 2 + 2 * x 3 + 0 * x 4 ]= [ 6 ] [ -1*x1 + 11*x2 + -1*x3 + 3*x4] = [25] [2*x1 + -1*x2 + 10*x3 + -1*x4] = [-11] [ 0 * x 1 + 3 * x 2 + -1 * x 3 + 8 * x 4 ]= [ 15 ] 반복 1: [0. 0. 0. 0. 0] 반복 2: [0.6 2.327273 - 0.987273 0.87886364] 반복 3: [1.030182 2.03693802 -1.0144562 0.98434122] 반복 4: [1.00658504 2.00355502 -1.00252738 0.99835095] 반복 5: [1.00086098 2.00029825 - 1.00030728 0.99984975] 반복 6: [1.00009128 2.002134 - 1.00003115 0.9999881] 반복 7: [ 1.00000836 2.00000117 - 1.00000275 0.9999922] 반복 8: [1.00000067 2.00000002 - 1.00000021 0.999996] 반복 9: [1.00000004 1.99999 - 1.00000001 1 ] 반복 10: [1. 2. -1. 1.] 해결책: [1. 2. -1. 1.] 오류: [2.06480930e-08-1.25551054e-08 3.61417563e-11 0.00000000e+00]

Matlab을 사용하여 방정식의 임의의 수를 푸는 프로그램

예제 다음 코드)i=1는 나는 거야.− ∑ j>(b나는, 나는 나는 j)j(k+1∑ j<>−)나는 나는 j)j(k)), 나는, j=1,2,…, n{\displaystyle x_{나는}^{(k+1)}={\frac{1}{a_{ii}}}\left(b_{나는}-\sum_{j<, 나는}a_{ij}x_{j}^{())}-\sum _{j>, 나는}a_{ij}x_{j}^{(k)}\right),\quad(k+1)는 공식을 이용한다. i,j=1,2,\ldo $ts ,n}$

함수 x = i = 1:j = 1:size(A,1) x(j) = (b(j) - sum(A(j,:)'에 대한 함수 x = gauss_seidel(A, b, x, iters)*x) + A(j,j)*x(j)/A(j,j), 엔드 엔드

「」를 참조해 주세요.

가우스 신념 전파
반복 방법.선형 시스템
Kaczmarz 방법('행 지향' 방법인 반면, Gauss-Seidel은 '열 지향' 방법).이 문서를 참조해 주세요.)
행렬 분할
리처드슨 반복

메모들

^ Sauer, Timothy (2006). Numerical Analysis (2nd ed.). Pearson Education, Inc. p. 109. ISBN 978-0-321-78367-7.
^ 가우스 1903, 페이지 279; 직접 링크
^ Seidel, Ludwig (1874). "Über ein Verfahren, die Gleichungen, auf welche die Methode der kleinsten Quadrate führt, sowie lineäre Gleichungen überhaupt, durch successive Annäherung aufzulösen" [On a process for solving by successive approximation the equations to which the method of least squares leads as well as linear equations generally]. Abhandlungen der Mathematisch-Physikalischen Klasse der Königlich Bayerischen Akademie der Wissenschaften (in German). 11 (3): 81–108.
^ 골럽앤반론 1996, 페이지 511.
^ Golub & Van Loan 1996, eqn (10.1.3)
^ Golub & Van Loan 1996, Thm 10.1.2.
^ Bagnara, Roberto (March 1995). "A Unified Proof for the Convergence of Jacobi and Gauss-Seidel Methods". SIAM Review. 37 (1): 93–97. doi:10.1137/1037008. JSTOR 2132758.

레퍼런스

를 클릭합니다Gauss, Carl Friedrich (1903), Werke (in German), vol. 9, Göttingen: Köninglichen Gesellschaft der Wissenschaften.
를 클릭합니다Golub, Gene H.; Van Loan, Charles F. (1996), Matrix Computations (3rd ed.), Baltimore: Johns Hopkins, ISBN 978-0-8018-5414-9.
Black, Noel & Moore, Shirley. "Gauss-Seidel Method". MathWorld.

이 문서에는 GFDL 라이선스의 CFD-Wiki에 관한 기사 Gauss-Seidel_method의 텍스트가 포함되어 있습니다.

외부 링크

"Seidel method", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
가우스-세이델(www.math-linux.com)
전체론적 수치법 연구소의 가우스-세이델
www.geocities.com의 Gauss Siedel 반복
가우스-자이델 방법
빅슨
매트랩 코드
C 코드 예시

[1] Sauer, Timothy (2006). Numerical Analysis (2nd ed.). Pearson Education, Inc. p. 109. ISBN 978-0-321-78367-7.

[2] 가우스 1903, 페이지 279; 직접 링크

[3] Seidel, Ludwig (1874). "Über ein Verfahren, die Gleichungen, auf welche die Methode der kleinsten Quadrate führt, sowie lineäre Gleichungen überhaupt, durch successive Annäherung aufzulösen" [On a process for solving by successive approximation the equations to which the method of least squares leads as well as linear equations generally]. Abhandlungen der Mathematisch-Physikalischen Klasse der Königlich Bayerischen Akademie der Wissenschaften (in German). 11 (3): 81–108.

[4] 골럽앤반론 1996, 페이지 511.

[5] Golub & Van Loan 1996, eqn (10.1.3)

[6] Golub & Van Loan 1996, Thm 10.1.2.

[7] Bagnara, Roberto (March 1995). "A Unified Proof for the Convergence of Jacobi and Gauss-Seidel Methods". SIAM Review. 37 (1): 93–97. doi:10.1137/1037008. JSTOR 2132758.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

v t 수치 선형 대수
주요 개념	부동 소수점 수치 안정성
문제	선형 방정식 체계 행렬 분해 행렬 곱셈(알고리즘) 행렬 분할 희박한 문제
하드웨어	CPU 캐시 TLB 캐시 오비어스 알고리즘 SIMD 멀티프로세서
소프트웨어	매트랩 기본 선형 대수 서브 프로그램(BLAS) 랩 전문 라이브러리 범용 소프트웨어

Search

가우스-자이델법

네임스페이스

더

목차

묘사

논의

컨버전스

알고리즘.

예

매트릭스 버전의 예

매트릭스 버전의 다른 예

방정식 버전의 예

Python 및 NumPy 사용 예시

Matlab을 사용하여 방정식의 임의의 수를 푸는 프로그램

「」를 참조해 주세요.

메모들

레퍼런스

외부 링크

Search

가우스-자이델법

묘사

논의

컨버전스

알고리즘.

예

매트릭스 버전의 예

매트릭스 버전의 다른 예

방정식 버전의 예

Python 및 NumPy 사용 예시

Matlab을 사용하여 방정식의 임의의 수를 푸는 프로그램

「 」를 참조해 주세요.

메모들

레퍼런스

외부 링크

「」를 참조해 주세요.