브로이덴의 방법

수치적 분석에서 브로이든의 방법은 k 변수에 뿌리를 찾기 위한 준뉴턴 방식이다. 원래 1965년에 C. G. Broyden이 묘사한 것이다.^[1]

뉴턴의 f(x) = 0을 푸는 방법은 매 반복마다 자코비안 행렬인 J를 사용한다. 그러나 이 자코비안을 계산하는 것은 어렵고 비용이 많이 드는 작업이다. 브로이든의 방법의 이면에 있는 아이디어는 첫 번째 반복에서만 자코비안 전체를 계산하고 다른 반복에서 1위 업데이트를 하는 것이다.

1979년 게이는 브로이든의 방법이 크기 n × n의 선형 시스템에 적용될 때, 2 n 단계로 종료되지만,^[2] 모든 준 뉴턴 방법과 마찬가지로 비선형 시스템에 수렴하지 않을 수 있다는 것을 증명했다.

방법 설명

단일 변수 방정식 해결

secant 방법에서는 x에서_n 첫 번째 파생상품 f′을 유한차 근사치로 대체한다.

${\displaystyle f'(x_{n})\simeq {\f(x_{n}-f(x_{n-1})}{x_{n-1},}$

뉴턴의 방법과 유사하게 진행하십시오.

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n}){f^{\prime }(x_{n})}}}$

여기서 n은 반복 지수다.

비선형 방정식 시스템 해결

k 비선형 방정식의 시스템 고려

${\displaystyle \mathbf {f}(\mathbf {x} )=\mathbf {0},}$

여기서 f는 벡터 x의 벡터 값 함수:

${\displaystyle \mathbf {x} =(x_{1},x_{2},x_{3},\dotsc ,x_{k}),}$

${\displaystyle \mathbf {f} (\mathbf {x} )={\big (}f_{1}(x_{1},x_{2},\dotsc ,x_{k}),f_{2}(x_{1},x_{2},\dotsc ,x_{k}),\dotsc ,f_{k}(x_{1},x_{2},\dotsc ,x_{k}){\big )}.}$

그런 문제들에 대해 브로이든은 1차원 뉴턴의 방법을 일반화하여 그 파생물을 제이콥스 J로 대체한다. Jacobian 행렬은 유한차 근사치의 제2차 방정식에 기초하여 반복적으로 결정된다.

${\displaystyle \mathbf {J} _{n}(\mathbf {x} _{n-1}) _{n-\mathbf {f}(\mathbf {x} _{n}-\mathbf {f}, _{n-1}),}$

여기서 n은 반복 지수다. 명확하게 하기 위해 다음을 정의해 봅시다.

${\displaystyle \mathbf {f} _{n}=\mathbf {f}(\mathbf {x} _{n}),}$

${\displaystyle \Delta \mathbf {x} _{n}=\mathbf {x} _{n}-\mathbf {x} _{n-1}}$

${\displaystyle \Delta \mathbf {f} _{n}=\mathbf {f} _{n}-\mathbf {f} _{n-1}}$

상술한 것을 로 다시 쓸 수 있도록.

${\displaystyle \mathbf {J} _{n}\Delta \mathbf {x} _{n}\simeq \Delta \mathbf {f} _{n}.}$

위의 방정식은 k가 1보다 클 때 충분히 결정되지 않는다. Broyden은 Jacobian 매트릭스_n−1 J의 현재 추정치를 사용하고_n−1 J:에 대한 최소한의 수정인 2차 방정식에 대한 해결책을 취함으로써 이를 개선할 것을 제안한다.

${\displaystyle \mathbf {J} _{n}=\mathbf {J} _{n-1}+{\frac {\Delta \mathbf {f} _{n}-\mathbf {J} _{n-1}\Delta \mathbf {x} _{n}}{\ \Delta \mathbf {x} _{n}\ ^{2}}}\Delta \mathbf {x} _{n}^{\mathrm {T} }.}$

이로써 다음과 같은 프로베니우스 규범이 최소화된다.

${\displaystyle \mathbf {J} _{n}-\mathbf {J} _{n-1}\{\rm {F}.}$

그런 다음 뉴턴 방향으로 진행할 수 있다.

${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\mathbf {J} _{n}^{-1}\mathbf {f} (\mathbf {x} _{n})}$

브로이든은 또한 Jacobian 매트릭스의 역행렬을 직접 업데이트하기 위해 셔먼-모리슨 공식을 사용할 것을 제안했다.

${\displaystyle \mathbf {J} _{n}^{-1}=\mathbf {J} _{n-1}^{-1}+{\frac {\Delta \mathbf {x} _{n}-\mathbf {J} _{n-1}^{-1}\Delta \mathbf {f} _{n}}{\Delta \mathbf {x} _{n}^{\mathrm {T} }\mathbf {J} _{n-1}^{-1}\Delta \mathbf {f} _{n}}}\Delta \mathbf {x} _{n}^{\mathrm {T} }\mathbf {J} _{n-1}^{-1}.}$

이 첫 번째 방법은 일반적으로 "좋은 브로이든의 방법"으로 알려져 있다.

J에_n−1 대해 약간 다른 수정을 사용함으로써 유사한 기술을 도출할 수 있다. 이것은^[3] 소위 "나쁜 브로이든의 방법"이라는 두 번째 방법을 산출한다.

${\displaystyle \mathbf {J} _{n}^{-1}=\mathbf {J} _{n-1}^{-1}+{\frac {\Delta \mathbf {x} _{n}-\mathbf {J} _{n-1}^{-1}\Delta \mathbf {f} _{n}}{\ \Delta \mathbf {f} _{n}\ ^{2}}}\Delta \mathbf {f} _{n}^{\mathrm {T} }.}$

이것은 다른 프로베니우스 규범을 최소화한다.

${\displaystyle \mathbf {J} _{n}^{-1}-\mathbf {J} _{n-1}^{-1}\{\rm {F}.}$

첫 번째 파생상품(다중 차원으로 나감)의 근원을 찾아 최대 또는 최소의 것을 추구하는 최적화에서는 그 밖의 많은 준뉴턴 제도들이 제안되어 왔다. 그라데이션의 야코비안은 헤시안이라고 불리며 대칭으로 업데이트에 제약을 더한다.

브로이든 반의 다른 멤버들

브로이든은 두 가지 방법뿐 아니라 모든 종류의 방법을 정의했다. 이 반의 다른 멤버들은 다른 작가들에 의해 추가되었다.

• 다비던-플레처-파월 업데이트는 브로이든이 정의한 두 멤버 이전에 발행되는 이 클래스의 유일한 멤버다.^[4]
• 슈베르트 또는 희박한 브로이든 알고리즘 - 희박한 자코비안 행렬의 수정.^[5]
• Klement(2014년) – 많은 방정식 시스템을 해결하기 위해 더 적은 반복을 사용한다.^[6][7]

참고 항목

• 세컨트법
• 뉴턴의 방법
• 준뉴턴법
• 뉴턴의 최적화 방법
• 다비던-플레처-파월 공식
• 브로이든-플레처-골드파브-샨노(BFGS) 방식

참조

추가 읽기

• Dennis, J. E.; Schnabel, Robert B. (1983). Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Englewood Cliffs: Prentice Hall. pp. 168–193. ISBN 0-13-627216-9.
• Fletcher, R. (1987). Practical Methods of Optimization (Second ed.). New York: John Wiley & Sons. pp. 44–79. ISBN 0-471-91547-5.

외부 링크

• 간단한 기본 설명: 맹목적인 궁수의 이야기