켤레 구배법

주어진 선형 시스템과 관련된 2차 함수를 최소화하기 위한 최적의 단계 크기(녹색) 및 켤레 벡터(빨간색)와의 경사 하강 수렴 비교.공역 구배는 정확한 산술로 가정할 때, 대부분의 n단계에서 수렴한다. 여기서 n은 시스템의 행렬 크기이다(여기서 n = 2).

수학에서, 켤레 경사법은 선형 방정식의 특정 시스템, 즉 행렬이 양의 유한인 시스템의 수치 해법을 위한 알고리즘이다.공역 구배법은 종종 반복 알고리즘으로 구현되며, 직접 구현이나 촐레스키 분해와 같은 다른 직접 방법에 의해 처리되기에는 너무 큰 스파스 시스템에 적용된다.대형 스파스 시스템은 편미분 방정식이나 최적화 문제를 수치적으로 풀 때 종종 발생합니다.

공역 구배법은 에너지 최소화와 같은 제약 없는 최적화 문제를 해결하기 위해서도 사용할 수 있다.이것은 일반적으로 ^[3]Z4에서 프로그래밍하고 광범위하게 ^[4][5]연구한 Magnus Hestenes와 Eduard Stiefel에 ^[1][2]기인한다.

쌍공역 구배법은 비대칭 행렬에 대한 일반화를 제공한다.다양한 비선형 공역 구배 방법은 비선형 최적화 문제의 최소화를 추구한다.

공역 구배를 통해 해결된 문제에 대한 설명

선형 방정식의 시스템을 풀려고 합니다.

$\displaystyle \mathbf {A} \mathbf {x} = \mathbf {b}$

벡터 x{\displaystyle \mathbf{)} 들어}이 알려진 n×n{\displaystyle n\times의 스녀}행렬 A{\displaystyle \mathbf{A}}은 대칭(즉, AT)A),positive-definite(Rn에 i.e. xTAx>0모든 0이 아니벡터에){\displaystyle \mathbf{x}}), 그리고 진정한 것, 그리고 b{\displaystyle \mathbf{b}.}나는라고도 알려져 있습니다.이 시스템의 고유한 솔루션을 x$displaystyle \mathbf {x} _$로 $나타냅니다{\displaystyle {\mathbf{}}_{}}$.

직접적 방법으로서의 도출

공역 구배법은 최적화를 위한 공역 방향 방법의 전문화 및 고유값 문제에 대한 Arnoldi/Lanczos 반복의 변화를 포함한 여러 다른 관점에서 도출할 수 있다.접근법의 차이에도 불구하고, 이러한 도출은 공통의 주제인 잔차의 직교성과 검색 방향의 활용성을 입증한다.이 두 가지 특성은 이 방법의 잘 알려진 간결한 공식을 개발하는 데 중요하다.

0이 아닌 2개의 벡터 u와 v는 켤레라고 합니다(A$${\$displaystyle \mathbf {A$에 $대하여{\displaystyle \mathbf{}}$).

${\displaystyle \mathbf {u}^{\mathsf {T}}\mathbf {A} \mathbf {v} = 0 .}$

$(\$는 대칭이고 양의 정의이므로 왼쪽은 내적을 정의합니다.

$\displaystyle \mathbf {u}^{\mathbf {T}}\mathbf {A}=\mathbf {u},\mathbf {v} \rangle _{\mathbf {A} =\mathbf {A} \mathbf},\mathbf {u}$

두 벡터는 이 내부곱에 대해 직교하는 경우에만 켤레이다.켤레는 대칭 관계입니다.$u{\displaystyle \mathbf{}}${\$displaystyle \mathbf {u}$가 v$${\$displaystyle \mathbf {v$$}}$에 $켤레$이면 v ${\${u$\}$는$u${\$displaystyle \mathbf${u}에 $켤레$입니다.

${\displaystyle P=\{\mathbf {p}_{1},\displays,\mathbf {p}_{n}\}$

는 A$(\$$$$\mathbf {A$에 $대해{\displaystyle \mathbf{}}$ 서로$$공역하는 $n개$의 $벡터{\displaystyle }$ 집합입니다.$즉{\displaystyle {\mathbf{}}_{}^{}}$, ${\displaystyle {\mathsf{}}_{}^{}}$ T ${\displaystyle A_{}^{}\mathbf{}}$ ${\displaystyle p{\mathbf{}}_{}}$ ${\displaystyle {}_{}}$ $= 0$(\$displaystyle \mathbf {p} _{i}^{\mathbf {T}\mathbf {p} _j0$$)$입니다${\displaystyle .}$$다음$으로 P$(\displaystyle$ P$)$는 ${\displaystyle {}^{}}$ n$(\$의 기저를 형성하며, A ${\displaystyle \mathbf{x}}$ ${\displaystyle =}$ ${\displaystyle b\mathbf{}}$= \$displaystyle \mathbf {Ax}$= \$mathbf {b}$의 $해{\displaystyle \mathbf{}}$ $x{\displaystyle {\mathbf{}}_{}}$ ${\$ {$displaystyle \mathbf$ {$x}$를 다음과 같이 나타낼 수 있습니다.

${\displaystyle \mathbf {x} _{*}=\sum _{i=1}^{n}\alpha _{i}\rightarrow \mathbf {A} \mathbf {x}_{*}=\sum _{i=1}^{n}\alpha _mathbf {p} \mathbf {p} \mathbf {p} \mathbf {p}}$

${\displaystyle {\mathsf{}}_{}^{}}$ T$${\$displaystyle \mathbf {p} _{k}^{\mathsf {T}}$ 수율에$$ $의한{\displaystyle {\mathbf{}}_{}^{}}$ 좌승수

${{displaystyle \mathbf {p}_{k}^{\mathbf {t}=\mathbf {p}^{k}{\mathbf {T}{\mathbf {A}_{*}=\sum _{i=1}^{n}\alpha {p}_mathb}_mathbf}_mathb} {p}_mathb} {p}bf {p} _{k}\right\rangle _{\mathbf {A}}}$

그래서

${\displaystyle \alpha _{k}=parcfrac {k},\mathbf {b} \rangle }{\mathbf {p}_{k},\mathbf {p}\rangle _{\mathbf {A}}}}.}$

이것은 방정식 Ax = b를 풀기 위한 다음 방법을^[4] 제공합니다$:$ n {\$displaystyle$ n$}$ 공역$$ $방향$의 시퀀스를 찾은 다음 $계수{\displaystyle {}_{}}$ ${\displaystyle {\alpha }_{}}$k {\$displaystyle \alpha$ _${k$

반복적인 방법으로서

공역 $벡터{\displaystyle {\mathbf{}}_{}}$ ${\displaystyle {}_{}}$ k$(\$를 신중하게 선택하면 모든 벡터 p k(\$displaystyle \mathbf {x}$ _$\{*\})$의 $근사치$를$$얻을 필요가 없기 때문에 공역 구배법을 반복법으로 간주하고 싶다.또한 n이 너무 커서 직접 방법이 너무 오래 걸리는 시스템을 대략적으로 해결할 수 있습니다.

x x₀ x에 대한_∗ 초기 추측을 나타냅니다(일반성을 잃지 않고 x = 0으로₀ 가정할 수 있습니다. 그렇지 않으면 시스템을 Az = b - Ax로₀ 간주할 수 있습니다).x부터₀ 솔루션을 검색하고 반복할 때마다 솔루션_∗ x에 가까운지 여부를 나타내는 메트릭이 필요합니다.이 메트릭은 솔루션_∗ x가 다음 2차 함수의 고유한 최소화라는 사실에서 비롯된다.

${\displaystyle f(\mathbf {x})=tfrac {1}{x}^{\mathbf {T}}\mathbf {A}\mathbf {x}^{\mathbf {b},\qad \mathbf {x}\mathbf {x} \mathbf {x}}$

독특한 최소화의 존재는 2차 도함수의 헤시안 행렬이 대칭 정의이기 때문에 명백하다.

$\displaystyle \mathbf {H}(f(\mathbf {x}))=\mathbf {A} ',}$

그리고 미니마이저(Df(x)=0 사용)가 초기 문제를 해결한다는 것은 첫 번째 도함수에서 명백하다.

$\displaystyle \mathbf {x} = \mathbf {A} \mathbf {x} - \mathbf {b} , . }$

이것은 첫 번째 기저₀ 벡터 p를₀ x = x에서 f의 구배 음수로 삼는 것을 암시한다.f의 구배는 Ax - b와 같다.초기 추측₀ x부터 시작하여 p = b - Ax를₀ 취합니다₀.베이스의 다른 벡터들은 구배와 결합될 것이고, 따라서 공역 구배법이라는 이름이 붙을 것이다.p는 알고리즘의 이 초기 단계에서 제공되는 잔차이기도 합니다₀.

r을 k번째 단계에서 잔차라고 합니다_k.

${\displaystyle \mathbf {r} _{k}=\mathbf {b} -\mathbf {Ax} _{k}.}$

위에서 관찰한 바와 같이 $k$ \$displaystyle$ \$mathbf {r}$ _${k}$는 ${\displaystyle {}_{}}$ k$${\$displaystyle \mathbf {x} _{k$에서$$f {$style$ f$}$의 음의 구배이므로 구배 강하법은 r 방향으로_k 이동해야 한다.단, 여기서는 ${\displaystyle {}_{}}$ p$$k$(\displaystyle$ \$mathbf$ {$p}_{$k$$})는 서로 공역해야 합니다.이를 강제하는 실용적인 방법은 현재 및 모든 이전 검색 방향에서 다음 검색 방향을 작성하도록 요구하는 것입니다.켤레 제약조건은 직교 정규형 제약조건이므로 알고리즘은 그램-슈미트 직교 정규화의 예로 볼 수 있다.그러면 다음과 같은 표현이 나옵니다.

${\displaystyle \mathbf {p} _{k}=\mathbf {r}-\sum _{i}{\mathbf {p}_{i}{\mathbf {t}_mathbf {r}_{k}}_mathbf {p}{i}}{i}{mathbf}{i}{mathbf {p}}{i}}}{i}}}}{mathbf}}}{mathbf}{mathbf}}}{mathbf}{i}}$

(컨버전스에 대한 켤레 제약의 영향에 대해서는 기사 맨 위의 그림을 참조하십시오).이 방향에 따라 다음 최적 위치는 다음과 같이 지정됩니다.

$\displaystyle \mathbf {x} _{k+1}=\mathbf {x} _{k} +\alpha _{k} \mathbf {p} _{k}$

와 함께

${\displaystyle \alpha _{k}={mathbf {p}^{\mathbf {T}}{\mathbf {p}_{k}}{\mathbf {p}_{k}}}{\mathbf {p} {p}}{\mathbf {p}}=frac {p}$

여기서 마지막 등식은 r ${\displaystyle {}_{}}$\$displaystyle \mathbf {r} _{k}$의 정의에서 나옵니다.${\displaystyle {\alpha }_{}}$ k$(\$ \$alpha _{$})의 $식은{\displaystyle {}_{}}$ x를 f로_k+1 대체하고 이를 최소화하면 도출할 수 있다.

${\displaystyle {displaystyle {mathbf {x} _{k+1}&=f(\mathbf {x} _{k} +\alpha _{k}\mathbf {p} _{k})=:g'(\alpha _{k} &\overset {k}!}{=}0\matharrow \alpha _{k}=mathbfrac {{k}^{\mathsf {T}}{\mathbf {b} -\mathbf {Ax}_{k}}}{\mathbf {p}_{k}\mathbf {T}\mathb} {F}\end { aligned}}$

결과 알고리즘

위의 알고리즘은 켤레 구배법에 대한 가장 간단한 설명을 제공한다.보아하니, 전술한 알고리즘은 이전의 모든 검색 방향과 잔차 벡터의 저장과 많은 행렬-벡터의 곱셈을 필요로 하므로 계산 비용이 많이 들 수 있다.그러나 알고리즘의 상세한 분석 결과 ${\displaystyle {}_{}}$ i ${\$는 r ${\displaystyle {}_{}^{}}$$${{${\displaystyle {displaystyle}_{}^{}{\mathbf{}}_{}}$ $\$${\displaystyle {}_{}}$${r} _{j$ $0$ {$displaystyle \mathbf {r}$ _${i}^{\mathsf {T}}}$=${0j$}$$에 $대해{\displaystyle {\mathbf{}}_{}}$ 직교합니다.}은$($는$)$ p $j$와 $직교$합니다$($${\displaystyle {}_{}^{}}$, ${\displaystyle {\mathsf{}}_{}^{}}$ T$$${\displaystyle {}_{}}$ ${\displaystyle p{\mathbf{}}_{}}$j $=$ $0$ { displaystyle \$mathbf {p} _{i}^{\mathbf$ {T$}} \mathbf {A} _{$$j}$ ） 。이는 알고리즘이 진행됨에 따라 $\$ ${\displaystyle {}_{}}$ $r{\displaystyle {\mathbf{}}_{}}$ ${\$ _${i}}$가 동일한 Krylov 서브스페이스에 걸쳐 있다고 볼 수 있습니다.${\displaystyle {}_{}}$서 r i$(\$는 표준 내적에 대한 직교 기저, ${\displaystyle {}_{}}$i(\$displaystyle \mathbf {$$p}$ _${i})$는 A$(\displaystyle$ \$mathbf${A}$$$})$에 $의해{\displaystyle \mathbf{}}$ 유도되는 내적에 대한 직교 기저이다. $따라서$ x$(\$displaystyle \$mathbf$ {x$})$_${k}}$은(는) Krylov 서브스페이스에 x$(\displaystyle\mathbf${x$})$를 투영한 것으로 간주할 수 있습니다.

Ax = b를 풀기 위한 알고리즘은 아래에 자세히 설명되어 있습니다. $여기$서 A$(\$는 실제 대칭의 양의 제곱 행렬입니다.입력 $벡터{\displaystyle {\mathbf{}}_{}}$ ${\displaystyle {\mathrm{}}_{}}$ 0$(\$은 대략적인 초기 해이거나 0일 수 있습니다.이것은 위에서 설명한 정확한 절차의 다른 공식입니다.

${\displaystyle{\begin{정렬}&, \mathbf{r}_{0}:=\mathbf{b}-\mathbf{도끼를}_{0}\\&,{\hbox{만약}}}{r}_{0}{\text{충분히 그때 다시 작다}\mathbf,{)}_{0}{\text{서 얻은 결과}}\\& \mathbf \mathbf _{0}:=\mathbf{r}_{0}\\&, k:=0\\&,{\text{반복}}\\&,\qquad \alpha _{k}:={\frac{\mathbf{r}_{k}^{\mathsf{T}}\mathbf{p}. {r}_{k}}{\mathbf{p}_{K}^{\mathsf{T}};{Ap}_{k}}}\\& \mathbf \qquad \mathbf{)}_{k+1}:=\mathbf{)}_{k}+\alpha _{k}\mathbf{p}_{k}\\&, \qquad \mathbf{r}_{k+1}:=\mathbf{r}_{k}-\alpha _{k}\mathbf{Ap}_{k}\\&, \qquad{\hbox{만약}}\mathbf{r}_{k+1}{\text{충분히 그 출구 루프 작다}}\\&, \qquad\beta _{k}:={\frac{\mathbf{r}_{k+1}^{\mathsf{T}}년.mathbf{r}_{k+1}{\mathbf {r}_{k}^{\mathsf {T}}\mathbf {r}_{k}}\&\qquad \mathbf {p}_{k+1}+\mathbf {p}_{k}_{k}\qqq}_mathbf {p}_{p}_{k+1}_{k}_k}_k}_k}_{k}_k}_k}_k}_k}_k}_k+quadd_k}_k=$

이것은 가장 일반적으로 사용되는 알고리즘입니다.β에 대한_k 동일한 공식이 Fletcher-Reves 비선형 켤레 경사법에도 사용된다.

재기동

${\displaystyle {\mathrm{}}_{}}$ 1$({$은 x$$({$displaystyle \mathbf {x} _{0$에 적용된 경사 하강법에 의해 계산된다.β ${\displaystyle k_{}}$ $=$ $({displaystyle \mathbf$${x} _{k}=$$0})$을 설정하면 $마찬가지$로 x${\displaystyle {}_{}}$ + $({$ {x} _k+$1})$가 계산된다.${\displaystyle {}_{}}$ k$(\displaystyle$ \$mathbf {x} _{$k$\})$ 즉, 켤레 그라데이션 ^[4]반복의 재기동의 간단한 구현으로 사용할 수 있습니다.재기동은 컨버전스를 늦출 수 있지만, 예를 들어 반올림 오류로 인해 켤레 그라데이션 방식이 잘못 동작할 경우 안정성을 향상시킬 수 있습니다.

명시적 잔차 계산

$공식{\displaystyle {\mathbf{}}_{}}$ ${\displaystyle {}_{}}$k + ${\displaystyle {}_{}{}_{}}$: ${\displaystyle =}$ ${\displaystyle {}_{}}$ + ${\displaystyle {\alpha }_{}}$ k ${\displaystyle {}_{}{\mathbf{}}_{}}$ \ $displaystyle$ \$mathbf { x } _$ {$k$ + \ $alpha$_ { $k$} + \ $mathbf$ {$p$}$_${ k$$ } 、 $r{\displaystyle {\mathbf{}}_{}}$ ${\displaystyle {}_{}}$ :$=$ ${\displaystyle {\mathbf{A}}_{}}$ \ $displaystyle$\ $mathbf${ $r$} _ {$k$ } :\ $mathb f }$ :\ $mathbf$ } }${\displaystyle {\mathbf{k}}_{}}$ p ${\displaystyle {}_{}}$\$displaystyle \mathbf {r} _{k+1}$ :$=$$\mathbf {r} _$${$${\displaystyle k\mathbf{}}$$}$ \$mathbf {$${\displaystyle {\mathbf{Ap}}_{}}$$} 및$${\displaystyle {}_{}}k{\displaystyle {\mathbf{}}_{}}$ + ${\displaystyle 1_{}}${$displaystyle \mathbf {r}$ ${k+1$} :\$mathbf$ {$r}$ - ${mathbf}$${\displaystyle {벡터}_{}}$ $A{\displaystyle {\mathbf{}}_{}}$ ${\displaystyle {\mathbf{p}}_{}}$ ${\displaystyle {}_{}}$ ${\$ \$mathbf {Ap}$ _${k$}는$$ 이미 α k$$\$displaystyle \alpha$ _${k$을(를) $평가$하기 위해 계산되었기 때문에 A$${\$displaystyle \mathbf {A$$}}}$의 $추가{\displaystyle \mathbf{}}$ 곱셈을 피하기 위해 알고리즘에서 전자를 사용합니다.후자는 명시적 $계산{\displaystyle {\mathbf{}}_{}}$ ${\displaystyle {}_{}}$ k${\displaystyle {}_{}}$+${\displaystyle 1_{}}$ : $=$ - ${\displaystyle {\mathbf{A}}_{}}$ ${\displaystyle {}_{}}$k +$$ {\$displaystyle \mathbf {r} _{k+1$}:=\$mathbf {b}$ -$\mathbf${Ax}$_{k+1}$을 반올림 오차 누적의 대상이 되는 재귀에 의한 암묵적 계산으로 대체함으로써 더 정확할 수 있으며, 따라서 때때로 평가를 ^[6]권장한다.

잔류물의 노름은 일반적으로 정지 기준에 사용됩니다.명시적 $잔차{\displaystyle {\mathbf{}}_{}}$ ${\displaystyle {}_{}}$k +${\displaystyle 1_{}}$ : $=$ - A ${\displaystyle {\mathbf{x}}_{}}$ +$$ {\$displaystyle \mathbf {r} _{k+1$}:=\$mathbf {b}$ -$\mathbf${Ax}$_{k+1}}$의 노름은 정확한 산술과 수렴이 자연스럽게 정체되는 반올림 오차에서 보장된 정확도 수준을 제공한다.반면 암묵적 $잔차{\displaystyle {\mathbf{}}_{}}$ ${\displaystyle {}_{}}$k +${\displaystyle 1_{}}$ : $=$ ${\displaystyle {}_{}{}_{}}$ - ${\displaystyle {\alpha }_{}}$ ${\displaystyle {}_{}{\mathbf{}}_{}}$ ${\displaystyle {\mathbf{A}}_{}}$ ${\displaystyle {}_{}}$ k$$\ $displaystyle \mathbf {r}$ _${k+1$} :=\$mathbf {r} _{k}-\alpha$_{$k}\mathbf {Ap}$ _${k}$는 반올림 오차 수준보다 훨씬 낮은 진폭에서 계속 작아지는 것으로 알려져 있으므로 수렴을 결정할 수 없다.

알파 및 베타 계산

알고리즘에서_k ${\displaystyle {\mathrm{\alpha }}_{}}$는$$r${\displaystyle {}_{}}$k + 1$({displaystyle \mathbf {r} _{$k$$+1$})$이 r $k {\displaystyle \mathbf {r}$ _{k$\})$와 직교하도록 선택됩니다.분모는 에서 단순화된다.

${\displaystyle \alpha _{k}={mathbf {r}{\mathbf {r}_{k}}{\mathbf {T}}{\mathbf {A}\mathbf {p}_{k}}=frac {k}{mathbf {r}$

${\displaystyle {}_{}}$ k${\displaystyle {}_{}}$+ ${\displaystyle 1_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$k +${\displaystyle {}_{}{}_{}}$ - ${\displaystyle {}_{}{\mathbf{}}_{}}$ k p ${\displaystyle {}_{}}$k {$displaystyle$\$mathbf { r } =$ \ $mathbf { p }$- \ $mathbf$ { p } _ { k + 1$$} - \ $mathbf { p$}$$。β는 p_k ${\displaystyle {}_{}}$+ $({$이 ${\displaystyle {}_{}}$ k$${{$displaystyle \mathbf {p} _{k$에 $해당$하도록 선택된다. 처음에 β는_k

${\displaystyle \mathbf {r}=-{\frac {mathbf {r}^{\mathbf {T}} {\mathbf {p} {{k}} {\mathbf {p} _{k}}} {\mathbf {A}} {mathbf {p}} {p}} {k} {k}}}$

사용.

$\displaystyle \mathbf {r} _{k+1}=\mathbf {r} _{k} - \alpha _{k} \mathbf {A} \mathbf {p} _{k}$

그리고 동등하게

$({displaystyle \mathbf {A} \mathbf {p} _{k}=mathbf {r} {\alpha _{k}} {{k}-\mathbf {r} _{k+1}),})$

β의_k 분자는 다음과 같이 고쳐 쓴다.

${{displaystyle \mathbf {r}_{k+1}^{\mathsf {T}}\mathbf {A}\mathbf {p}_{k}=mathbf {r}{\mathbf {t}{k+1}{\mathbf}_mathbf} {k}$

${\displaystyle {}_{}}$+ $(\$과 r $(\$ _${k})$는 설계상 직교하기 $때문$입니다.분모는 다음과 같이 고쳐 씁니다.

$\displaystyle \mathbf {p} _{k}^{\mathsf {T}\mathbf {A} \mathbf {p} =(\mathbf {r} _{k-1} \mathbf {p} _{k-1}^{k-1} \mathbf {T} \mathbf {F})$

검색 방향_k p가 공역이고 잔차가 직교임을 다시 사용합니다.이는 α를_k 소거한 후 알고리즘의 β를 제공한다.

MATLAB/GNU 옥타브 코드 예시

함수 x = consegrad(A, b, x) r = b - A * x; p = r; rsold = r' * r; i = 1 : length (b) Ap = A * p ; alpha = rsold / (p' * Ap ) ;x = x + alpha * p ; r ; alpha * r ; new r' r'

수치 예시

다음과 같은 선형 시스템 Ax = b를 고려하십시오.

${\displaystyle \mathbf {A} \mathbf {x} = beginb { bmatrix } 4 & 1 \ \ \ \ 1 & 3 \ end { bmatrix } { \ bmatrix } = beginbb { bmatrix }$

우리는 첫 번째 추측부터 시작해서 켤레 그라데이션 방법의 두 단계를 수행할 것이다.

${\displaystyle \mathbf {x} _{0}=syslog {bmatrix}2\\1\end {bmatrix}}$

시스템에 대한 대략적인 해결책을 찾기 위해.

솔루션

참고로 정확한 해결책은

${\displaystyle \mathbf {x} = syslog {bmatrix} {\frac {1} {11} \ \ {\frac {7} {bmatrix} \ end {bmatrix} \ about { bmatrix} \ {\ {\ 0 . 0 . 6364 \ end { bmatrix }$

첫 번째 단계는 x와 관련된₀ 잔류 벡터₀ r을 계산하는 것입니다.이 잔차는 공식 r₀ = b₀ - Ax에서 계산되며, 이 경우 다음과 같다.

$\displaystyle \mathbf {r} _{0}=param {bmatrix}1\\\end {bmatrix}4&1\\end {bmatrix}{\param {bmatrix}2\1\end {bmatrix}=param {bmatrix}1\end {bmatrix}}$

이것이 첫 번째 반복이기 때문에, 우리는 우리의 초기 검색₀ 방향 p로 잔존₀ 벡터 r을 사용할 것이다; p를 선택하는_k 방법은 더 많은 반복으로 바뀔 것이다.

우리는 이제 관계를 사용하여 스칼라α를₀ 계산한다.

${\displaystyle \alpha_{0}={\frac{\mathbf{r}_{0}^{\mathsf{T}}}{\mathbf{p}_{0}^{\mathsf{T}}{Ap}_{0}}}={\frac{{\begin{bmatrix}-8& \mathbf, -3\end{bmatrix}}{\begin{bmatrix}-8\\-3\end{bmatrix}}}{{\begin{bmatrix}-8&, -3\end{bmatrix}}{\begin{bmatrix}4&, 1\\1&, 3\end{bmatrix}}{\begin{bmatrix}-8\\-3\end{bmatrix}}}}){\frac{{r}_{0}\mathbf.73}{331}}=0.2205}$

이제 공식을 사용하여 x를 계산할₁ 수 있습니다.

$\displaystyle \mathbf {x} _{1}=\mathbf {x} _{0} +\alpha _{0} \mathbf {p} _{0} = scap{bmatrix}2 \ \ \ \ \ 1 \ end { bmatrix } + { \ frac { 731 } { \ bmatrix } - 8 \ matrix }2356\\0.3384\end {bmatrix}.}$

이 결과는 첫 번째 반복을 완료하고, 그 결과는 시스템에 대한 "개선된" 근사 솔루션 x입니다₁. 이제 다음 공식을 사용하여 다음 잔차 벡터₁ r을 계산할 수 있습니다.

$\displaystyle \mathbf {r} _{1}=\mathbf {r} _{0}-\alpha _{0}\mathbf {A}\mathbf {p}_{0}=mathbf {p}_{0}-{\end {bmatrix}-{331}-{b}\1}\matrix}}$

이 과정의 다음 단계는 최종적으로 다음 검색₁ 방향 p를 결정하는 데 사용될 스칼라₀ β를 계산하는 것이다.

$\displaystyle \mathbf {r} = specfrac {{1}^{\mathbf {r} {{0} {\mathsf {T}} {\mathbf {r} {0} = specfrac {r} {{matbrix} 092&092.$

이제, 이 스칼라₀ β를 사용하여, 우리는 관계를 사용하여 다음 검색 방향₁ p를 계산할 수 있다.

${\displaystyle \mathbf {p} _{1}=\mathbf {r} _{0}\mathbf {p} _{0}=matrix {bmatrix} - 0.2810 \ 0.7492 \ end {bmatrix} + 0.0088 display {bmatrix} - 8 \ 3 \ bmatrix = { matrix }}$

이제 α에 사용된 것과 동일한 방법으로 새로₀ 획득한₁ p를 사용하여 스칼라₁ α를 계산한다.

${\displaystyle \alpha_{1}={\frac{\mathbf{r}_{1}^{\mathsf{T}}}{\mathbf{p}_{1}^{\mathsf{T}}{Ap}_{1}}}={\frac{{\begin{bmatrix}-0.2810& \mathbf, 0.7492\end{bmatrix}}{\begin{bmatrix}-0.2810\\0.7492\end{bmatrix}}}{{\begin{bmatrix}-0.3511&, 0.7229\end{bmatrix}}{\begin{bmatrix}4&, 1\\1&, 3\end{bmatrix}}{\begin{bmatrix}-0.3{r}_{1}\mathbf.511\\0.7229\end{bmatrix}}}}=0.4122.}$

마지막으로 x를 찾을₁ 때와 같은 방법으로 x를 찾을₂ 수 있습니다.

$\displaystyle \mathbf {x} _{2}=\mathbf {x} _{1}+\alpha _{1}\mathbf {p} _{1}=mathbmatrix}0.2356\\0.3384\end{bmatrix}+0.4122cap{bmatrix}-0.3511\\0.7229\end{bmatrix}=cap{bmatrix} 0.0909\0.6364\end{bmatrix}}.}$

결과 x는₂ x와₀ x보다 시스템₁ 솔루션에 "더 나은" 근사치입니다. 이 예에서 제한값 대신 정확한 산술을 사용한다면 이론적으로 정확한 해는 n = 2회 반복(n은 시스템의 순서) 후에 도달했을 것입니다.

컨버전스 속성

공역 구배법은 이론적으로 직접적인 방법으로 볼 수 있는데, 반올림 오차가 없을 경우 행렬 크기보다 크지 않은 유한한 횟수 반복 후에 정확한 해를 생성하기 때문이다.실제로, 공역 구배법은 심지어 작은 섭동에 관해서도 불안정하기 때문에, 정확한 해법은 결코 얻어지지 않는다. 예를 들어, 대부분의 방향은 크릴로프 서브스페이스를 생성하는 퇴행성 특성 때문에 실제로 공역하지 않는다.

반복 방법으로서 켤레 경사법은 (에너지 노름에서) 단조롭게 x $(\$k$$$})$의 $정확$한 해법을 개선하며, (문제 크기에 비해) 비교적 적은 반복 횟수 후에 필요한 공차에 도달할 수 있다.개선은 일반적으로 선형이며 속도는 시스템 $A$의 ${\displaystyle \mathrm{조건}}$ 번호${\displaystyle }number{\displaystyle }$ (${\displaystyle }$A$$) \ $displaystyle$ \$kappa ( A$ ) :${\displaystyle <img\; alt="A"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3"\; style="vertical-align:\; -0.338ex;\; width:1.743ex;\; height:2.176ex;">(}$ ( ${\displaystyle A}$) \ $displaystyle$\ $kappa$( A $)$가 클수록 ^[7]개선 속도가 느려집니다.

${\displaystyle (}$ ( ${\displaystyle A}$) { $displaystyle \kappa$( A )$$} , , 、 $a{\displaystyle }$ a a $a{\displaystyle \mathbf{}}$ a ${\displaystyle \mathbf{a}}$ 、 ${\displaystyle 0}$\ $displaystyle${ $Ax }$ - \ $mathbf${ $b =$0$（$ $Ax$-${\displaystyle b\mathbf{}}$ ）${\displaystyle {}^{}=}$ \ $displaystyle$\$mathbf { B$^$1$}로 대체하기 위해 일반적으로 프리 컨디셔닝이 사용됩니다.$e \kappa (\mathbf {M}^{-1}\mathbf {A})}$가${\displaystyle }is{\displaystyle }$ (${\displaystyle A\mathbf{}}$) \ $displaystyle \kappa$( \$mathbf {A}$ $)$보다 작습니다.아래를 참조해 주십시오.

수렴 정리

다항식의 부분 집합을 다음과 같이 정의합니다.

$\displaystyle \Pi _{k}^*:=\left\lbrace \p\in \Pi _{k}\:\p(0)=1\right\rbrace \,}$

여기서 ${\displaystyle {\delta }_{}}$k {$displaystyle \Pi$ _${k}$는 최대 $차수{\displaystyle }$k {$style$ k$\}$의 다항식 집합입니다.

$({\displaystyle {}_{}}$ ${\displaystyle {{}_{}}_{}}$ )$$ \ $displaystyle \left(\mathbf {x} _{k}\$right$)$로 합니다.$_{k}$는 정확한 $솔루션{\displaystyle {\mathbf{}}_{}}$ x$displaystyle \mathbf$${x}$ $_$의 반복 근사치이며, ${\displaystyle {}_{}}$e ${\displaystyle {\mathbf{}}_{}}$ : $=$ ${\displaystyle {\mathbf{}}_{}}$ k - ${\displaystyle {}_{}}${\(\$displaystyle$ \$mathbf {e} _{k} _{k$ )로 정의됩니다.수렴의 환율은 다음과 같습니다.

${\displaystyle{\begin{정렬}\left\\mathbf{e}_{k}\right\ _{\mathbf{A}}&=\min _{p\in \Pi_{k}^{*}}p(\mathbf{A})\mathbf{e}_{0}\right\ _{\mathbf{A}}\\& \left\, \leq \min _{p\in \Pi_{k}^{*}}_{\lambda\in \sigma(\mathbf{A})}p(\lambda))\left\\mathbf{e}_{0}\right\ _{\mathbf{A}}\\& \,\max, \leq 2\left({\frac{{\sqrt{\kapp.a(\mathbf{A}}}-1}{{\sqrt {kappa (\mathbf {A}}}}+1}}\오른쪽}^{k}\\left\\mathbf {e}_{0}\right\_{\mathbf {A}},\end{aligned}}$

$여기$서 ${\displaystyle (}$ ( ${\displaystyle A\mathbf{}}$) { $displaystyle \sigma$( \$mathbf {A$${\displaystyle \}}$ )는$$ 스펙트럼을 나타내고 ${\displaystyle \kappa \mathbf{}}$( A )$${ $displaystyle \kappa$ ( $\mathbf {A})}$는 조건 번호를 나타냅니다.

$주의{\displaystyle }$: ${\displaystyle (}$ ( ${\displaystyle A\mathbf{}}$) \ $displaystyle$\$kappa$( \ $mathbf${ $A$} )이$$ ${\$ \ $displaystyle$\ $infty$}인 경우의 중요한 제한은 다음과 같습니다.

$(\displaystyle {{\sqrt {\mathbf {A}}) {{\sqrt {kappa(\mathbf {A}}}}+1}}\약 1-{\frac {2}{\sqrt {Kappa(\mathbf {A}}}})\quad {\mathbf {\kappa}\cad}\crt {\capa(\mathbf {\mathbf {\crt})\crt} {\cr} {\cr}\c}$

${\displaystyle \frac{이\mathbf{}}{}}$ 한계는${\displaystyle -}$ 1 - ${\displaystyle \frac{2}{}}$ ${\displaystyle \frac{(}{}}$ (${\displaystyle \frac{}{}}$A$$) \ $displaystyle$\$approx$1-${\frac${2}{\$kappa$(\$mathbf${A$\}\})$로 스케일링되는 야코비 또는 가우스-세이델의 반복 방법과 비교하여 더 빠른 수렴 속도를 보여준다.

수렴정리에 반올림오차는 없다고 가정하지만, 수렴한계는 Anne Greenbaum에 의해 이론적으로^[5] 설명되었듯이 실제로 유효하다.

실용적인 컨버전스

무작위로 초기화된 경우, 첫 번째 반복 단계가 가장 빠른 경우가 많은데, 이는 오류가 처음에 더 작은 유효 조건 번호를 반영하는 Krylov 하위 공간 내에서 제거되기 때문이다.수렴의 두 번째 단계는 일반적으로${\displaystyle \sqrt{}}\delta {\displaystyle \sqrt{}}$ ($A$$$ {{$sqrt {kappa (\mathbf {A$$}}}}$로 묶인 이론적 수렴에 의해 잘 정의되지만 $A$의 스펙트럼 분포와 ^[5]오차의 스펙트럼 분포에 따라 초선형일 수 있다.마지막 단계에서는 달성 가능한 최소 정밀도에 도달하여 수렴 또는 방법이 분산되기 시작할 수 있다.큰 크기의 행렬을 위한 2배 정밀도의 부동소수점 형식의 전형적인 과학 컴퓨팅 어플리케이션에서, 켤레 구배법은 첫 번째 또는 두 번째 단계 동안 반복을 종료하는 공차를 가진 정지 기준을 사용한다.

사전 조건 공역 구배법

대부분의 경우, 공역 구배법의 빠른 수렴을 보장하기 위해 사전 조절이 필요하다.전제조건부 켤레 그라데이션 방법은 다음 형식을 ^[9]취합니다.

$\displaystyle \mathbf {r} _{0}:=\mathbf {b} -\mathbf {Ax} _{0}$

$\displaystyle \mathbf {z} _{0}:=\mathbf {M}^{-1}\mathbf {r} _{0}$

${\displaystyle \mathbf {p} _{0}:=\mathbf {z} _{0}$

${\displaystyle k:=0,}$

따라하다

${\displaystyle \alpha _{k} : = snfrac {mathbf {r} {{k}} {\mathbf {z} _{k}} {\mathbf {p} _{\mathsf {T}}} {{\mathbf {Ap}}}}}$

${\displaystyle \mathbf {x} _{k+1}:=\mathbf {x} _{k} +\alpha _{k} \mathbf {p} _{k}$

${\displaystyle \mathbf {r} _{k+1}:=\mathbf {r} _{k} -\alpha _{k} \mathbf {Ap} _{k}$

r이 충분히 작으면 출구_k+1 루프가 종료됩니다.

${\displaystyle \mathbf {z} _{k+1}:=\mathbf {M}^{-1}\mathbf {r} _{k+1}$

${\displaystyle \mathbf {r} _{k+1} = prac {\mathbf {T} {\mathbf {r} _{k+1}} {\mathbf {r}^{\mathsf {T} {z}} {mathbf {k}}}}$

${\displaystyle \mathbf {p} _{k+1} :=\mathbf {z} _{k+1}+\display _{k} \mathbf {p} _{k}$

${\displaystyle k:=k+1,}$

종료 반복

결과는_k+1 x 입니다.

위의 공식은 시스템에^[10] 사전 조건 없이 공역 구배법을 적용하는 것과 같다.

${\displaystyle \mathbf {E} ^{-1}\mathbf {A} (\mathbf {E} =\mathbf {x} ^{-1}\mathbf {b})$

어디에

${\displaystyle \mathbf {EE}^{\mathsf {T}}=\mathbf {M},\qquad \mathbf {x}=\mathbf {E}^{\mathbf {X}}}}$

전제 조건 행렬 M은 대칭적인 양의 정의여야 하며 고정적이어야 한다. 즉, 반복에서 반복으로 변경할 수 없다.전제조건에 관한 이러한 전제조건 중 하나를 위반했을 경우, 전제조건의 공역구배법의 동작을 예측할 수 없게 되는 경우가 있습니다.

일반적으로 사용되는 전제조건의 예는 불완전한 콜레스키 인수분해입니다.^[11]

유연한 사전 조건 공역 구배법

수치적으로 어려운 애플리케이션에서는 정교한 전제조건이 사용되며, 이는 가변적인 전제조건, 반복간 변경으로 이어질 수 있습니다.전제조건이 모든 반복에서 대칭적인 양의 정의일지라도, 그것이 변경될 수 있다는 사실은 위의 인수를 무효화하며, 실제 테스트에서는 위에 제시된 알고리즘의 수렴이 현저하게 느려집니다.Polak-Ribiere 공식 사용

${\displaystyle _{k}:=frac {mathbf {r}^{k+1} {T}}\left(\mathbf {z})_{k+1}-\mathbf {z}_{k}\right}{\mathbf {k} {k}} {k} {mathbf} {k}$

플레처-리브스 공식 대신

${\displaystyle \mathbf {r} _{k+1} = prac {\mathbf {T} {\mathbf {r} _{k+1}} {\mathbf {r}^{\mathsf {T} {z}} {mathbf {k}}}}$

이 ^[12]경우 컨버전스를 극적으로 개선할 수 있습니다.이 버전의 사전 조건 공역 구배법은 가변 사전 조건을 허용하기 때문에 플렉시블이라고^[13] 할 수 있습니다.플렉시블 버전은 프리컨디셔너가 Symmetric Positive Finite(SPD; 대칭 포지티브 확정)가 아닌 경우에도 견고한 것으로 나타납니다^[14].

유연한 버전을 구현하려면 추가 벡터를 저장해야 합니다.고정 SPD 전제 조건의 $경우{\displaystyle {\mathbf{}}_{}^{}}$, ${\displaystyle {}_{}^{}}$k + ${\displaystyle {\mathsf{}}_{}^{}}$ ${\displaystyle T_{}^{}{\mathbf{}}_{}}$ ${\displaystyle {}_{}}$ k $=$, {\$displaystyle \mathbf {r} {{k+1}^{\mathsf$ {T}}\$mathbf {z}$ _{k}=$0,}$이므로 β에 대한_k 두 공식은 모두 정확한 산술에서 동등하다. 즉, 반올림 오류는 없다.

Polak-Ribiere 공식을 사용한 방법의 더 나은 수렴 거동에 대한 수학적 설명은 이 경우 방법이 국소적으로 최적이며, 특히 국소적으로 가장 가파른 하강 방법보다 ^[15]더 느리게 수렴되지 않는다는 것이다.

국소적으로 최적의 가장 가파른 강하 방법 대비

원본 및 사전 조건 공역 경사 방법 모두에서 라인 검색, 가장 가파른 하강 방법을 사용하여 국소적으로 ${\displaystyle {최적화}_{}}$하기 위해 ${\displaystyle \mathrm{\beta }}$ k ${\displaystyle {}_{}}$ $=$0$(\displaystyle$ \$discript$ _${k$:=$0$$})$만 설정하면 된다.이 치환에 의해 벡터 p는 벡터 z와 항상 같기 때문에 벡터 p를 저장할 필요가 없다.따라서, 이러한 가장 가파른 강하 방법의 모든 반복은 공역 구배 방법에 비해 다소 저렴하다.단, (높은) 변수 또는 비 SPD 프리컨디셔너를 사용하지 않는 한 후자의 컨버전스는 고속입니다.상기를 참조해 주십시오.

이중 적분기를 위한 최적의 피드백 컨트롤러로서의 켤레 경사법

공역 구배법은 또한 최적 ^[16]제어 이론을 사용하여 도출될 수 있다.이 접근법에서 켤레 경사법은 최적의 피드백 제어기로 분류된다.

$${\displaystyle u=k(x,v):=-\display_{a}\displayla f(x)-\display_{b}v}$$

$$\displaystyle\dot {x}=v,\display\dot {v}=u}$$

수량 ${\displaystyle a_{}}$ a$$\ $displaystyle$\ $gamma$_ { $a$} 및$$ ${\displaystyle b_{}}$b \ $displaystyle$\$gamma$_ { $b$}는$$ 가변 피드백 ^[16]이득입니다.

정규 방정식의 켤레 경사

공역 구배법은 임의의 n-by-m 행렬에 적용할 수 있는데, AA는 임의의^T A에 대해 대칭적인 양의-반 유한 행렬이기^T 때문이다^T.결과는 정규 방정식(CGNR)의 켤레 구배입니다.

AAx^T = Ab^T

반복 방법으로서, AA를 명시적으로 메모리에 형성할^T 필요는 없고, 행렬-벡터를 실행하고 행렬-벡터 곱셈을 전치하는 것만이 필요하다.따라서 CGNR은 A가 스파스 매트릭스일 때 특히 유용합니다.이는 이러한 연산이 보통 매우 효율적이기 때문입니다.그러나 정규 방정식을 형성하는 단점은 조건 번호 θ(AA^T)가 θ²(A)와 같기 때문에 CGNR의 수렴 속도가 느릴 수 있고 근사 용액의 품질이 반올림 오차에 민감할 수 있다는 것이다.CGNR 방법을 사용할 때 좋은 전제 조건을 찾는 것이 종종 중요한 부분입니다.

몇 가지 알고리즘(예: CGLS, LSQR)이 제안되었다).LSQR 알고리즘은 A가 컨디션이 나쁜 경우, 즉 A의 컨디션 번호가 큰 경우에 최고의 수치 안정성을 갖는 것으로 알려져 있습니다.

복소 에르미트 행렬의 켤레 경사법

복소수 행렬 A와 벡터 b가 주어졌을 때, A가 에르미트(즉, A-양수$)$인 복소수 벡터 x에 $대한{\displaystyle \mathbf{}}$ ${\displaystyle 선형\mathbf{}}$ $방정식$ ${\displaystyle A\mathbf{}}$x$=$ b \$displaystyle$ \$mathbf {$x$}$ =\$mathbf$ {b$$$} }$의 시스템을 푸는 데까지 확장할 수 있다.는 MATLAB/GNU 옥타브 스타일을 사용한 켤레 전치입니다.사소한 수정은 단순히 모든 곳의 실제 전치 대신 켤레 전치 대신하는 것이다.켤레 전치가 실제 값 벡터 및 행렬에서 실제 전치 형식으로 바뀌기 때문에 이 치환은 역호환성이 있습니다.따라서 MATLAB/GNU 옥타브에서 제공된 예제 코드는 수정이 필요하지 않은 복잡한 에르미트 행렬에 대해 이미 작동합니다.

「 」를 참조해 주세요.

레퍼런스

추가 정보

• Atkinson, Kendell A. (1988). "Section 8.9". An introduction to numerical analysis (2nd ed.). John Wiley and Sons. ISBN 978-0-471-50023-0.
• Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 978-0-486-43227-4.
• Golub, Gene H.; Van Loan, Charles F. (2013). "Chapter 11". Matrix Computations (4th ed.). Johns Hopkins University Press. ISBN 978-1-4214-0794-4.
• Saad, Yousef (2003-04-01). "Chapter 6". Iterative methods for sparse linear systems (2nd ed.). SIAM. ISBN 978-0-89871-534-7.

외부 링크