할선법은 함수 f의 영점을 찾는 수치 해석적인 반복 방법이다. 초기값 두 개를 사용하여 다음 점화식에 따라 반복하며, 함수의 2번 연속 미분 가능 및 특정 조건 만족 시 황금비에 가까운 수렴 속도를 보인다. 뉴턴법보다 수렴 속도는 느리지만, 도함수 계산이 필요 없어 계산 비용 효율적일 수 있다. 할선법은 뉴턴법의 차분 근사로 볼 수 있으며, 여러 차원으로 일반화한 브로이덴 방법도 존재한다.
더 읽어볼만한 페이지
근 찾기 알고리즘 - 뉴턴 방법 뉴턴 방법은 미분 가능한 함수의 근을 찾기 위해 초기 추측값에서 시작하여 접선의 x절편을 다음 추측값으로 반복 설정하여 해를 근사하는 수치해석 알고리즘이다.
근 찾기 알고리즘 - 유리근 정리 유리근 정리는 유일 인수 분해 정역 위에서 정의된 다항식환의 다항식이 분수체 원소를 근으로 가질 때, 분자는 상수항을 나누고 분모는 최고차항을 나눈다는 정리로, 일계수 다항식이면 그 근은 환의 원소가 된다.
수치해석학 - 수학적 최적화 수학적 최적화는 주어진 집합에서 실수 또는 정수 변수를 갖는 함수의 최댓값이나 최솟값을 찾는 문제로, 변수 종류, 제약 조건, 목적 함수 개수에 따라 다양한 분야로 나뉘며 여러 학문 분야에서 활용된다.
수치해석학 - 선형대수학 선형대수학은 벡터, 벡터 공간, 행렬 등의 개념으로 선형 방정식과 선형 변환을 연구하는 수학 분야로, 선형성을 활용해 행렬로 표현 및 계산하며, 연립일차방정식 해법, 고유값/고유벡터를 통한 행렬 분석, 벡터 공간의 기저와 차원 등을 다루고 물리학, 공학, 컴퓨터 과학 등 다양한 분야에 응용된다.
여기서 은 n번째 근의 추정값, 과 는 각각 이전 단계의 추정값들이다. 초기값 와 이 주어지면, 위의 점화식에 따라 , , ... 를 계산하여 근의 추정값을 얻는다.
허용 오차를 ε이라고 할 때, 할선법은 다음 조건 중 하나를 만족하면 정지한다.[5]
:
\leq \epsilon
2. 1. 방법의 유도
할선법은 함수 f의 영점을 찾기 위한 반복적인 수치 해석 방법이다. 초기값 와 에서 시작하여, 점 와 를 지나는 할선을 그린다. 이 할선의 방정식은 기울기-절편 형태로 다음과 같이 표현할 수 있다.[5]
:
이 선형 함수의 근, 즉 을 만족하는 의 값은 다음과 같다.[5]
:
이 값을 로 사용하고, 와 대신 과 를 사용하여 위 과정을 반복한다. , 등을 계산하여 충분히 높은 정밀도 수준 (과 사이의 충분히 작은 차이)에 도달할 때까지 반복한다.[5]
:
할선법에 의한 반복 과정. 할선의 절편이 다음 값에 해당한다.
일반적으로 다음과 같이 표현할 수 있다.[5]
:
3. 수렴성
할선법의 반복 ${\displaystyle x_{n}}$은 초기값 ${\displaystyle x_{0}}$과 ${\displaystyle x_{1}}$이 근에 충분히 가깝고 ${\displaystyle f}$가 잘 동작하는 경우 ${\displaystyle f}$의 근으로 수렴한다. ${\displaystyle f}$가 두 번 연속 미분 가능하고 문제의 근이 단순근(중복도 1)일 때, 수렴 차수는 황금비 ${\displaystyle \varphi =(1+{\sqrt {5}})/2\approx 1.618}$이다.[2] 이 수렴은 초선형이지만 이차 수렴보다는 느리다.
초기값이 근에 충분히 가깝지 않거나 ${\displaystyle f}$가 잘 동작하지 않으면 할선법이 전혀 수렴하지 않을 수도 있다. "충분히 가깝다"에 대한 일반적인 정의는 없지만, 수렴 기준은 초기값 사이의 간격에서 함수의 "울퉁불퉁함"과 관련이 있다. 예를 들어, ${\displaystyle f}$가 해당 간격에서 미분 가능하고 간격 내에 ${\displaystyle f'=0}$인 점이 있는 경우 알고리즘이 수렴하지 않을 수 있다.
함수 ${\displaystyle f}$가 2번 연속 미분 가능하고 ${\displaystyle f'(x_{*})\neq 0}$이며, ${\displaystyle f''(x_{*})\neq 0}$라면 수열 ${\displaystyle x_{k}}$는 ${\displaystyle x_{*}}$에 수렴하며, 그 수렴 속도는 황금비 ${\displaystyle \varphi =(1+{\sqrt {5}})/2\asymp 1.6}$이다.[5]
4. 다른 근 찾기 방법과의 비교
이분법과 달리 할선법은 근이 연속적인 반복에서 묶여 있을 필요가 없으므로 항상 수렴하지는 않는다. 가위치법(또는 regula falsila)은 할선법과 같은 공식을 사용하지만, 할선법처럼 xn-1과 xn-2에 공식을 적용하는 대신, xn-1과 f(xk)와 f(xn-1)이 다른 부호를 갖는 마지막 반복 xk에 적용한다. 따라서 가위치법은 항상 수렴하지만, 수렴 차수는 선형이다. 할선법의 초선형 수렴 차수를 유지하면서도 수렴성을 보장하는 방법으로는 ITP 방법이나 Illinois 방법 등이 있다.
4. 1. 뉴턴법과의 관계
할선법은 뉴턴법의 공식에서 미분값을 다음과 같은 유한 차분 근사로 대체한 것으로 볼 수 있다.[2]
:
따라서 할선법은 도함수가 근사값으로 대체되는 방법으로 해석될 수 있으며, 준 뉴턴법의 일종이다.
뉴턴법에 의한 반복의 모습. 접선의 절편이 다음 값에 대응한다.
뉴턴법과 할선법을 비교하면, 뉴턴법이 더 빠르게 수렴한다 (2차 vs 황금비 ''φ'' ≈ 1.6).[2] 그러나 뉴턴법은 매 단계에서 함수 f와 그 도함수 f'의 값을 모두 구해야 하는 반면, 할선법은 함수 f의 값만 계산하면 된다. 따라서 함수 f의 계산 비용이 도함수의 계산 비용보다 훨씬 크거나, 도함수를 구하기 어려운 경우에는 할선법이 뉴턴법보다 더 효율적일 수 있다. 예를 들어, f를 평가하는 데 도함수를 평가하는 것만큼 시간이 걸리고 다른 모든 비용을 무시한다고 가정하면, 뉴턴법의 한 단계와 동일한 비용으로 할선법의 두 단계를 수행할 수 있다. 이때 할선법은 오차의 로그를 ''φ''2 ≈ 2.6만큼 감소시키고, 뉴턴법은 오차의 로그를 2만큼 감소시키므로 할선법이 더 빠르다. 더 높은 차원에서, 뉴턴법에 필요한 모든 편도함수, 즉 야코비 행렬은 함수 자체보다 계산하는 데 훨씬 더 많은 비용이 들 수 있다. 그러나 도함수 또는 도함수들의 평가를 위한 병렬 처리를 고려한다면, 뉴턴법이 전체적으로 더 많은 계산 연산을 소요하더라도 실제 계산 시간은 더 빠를 수 있다.
단순히 차분 근사한 뉴턴법과 비교하면, 할선법은 수렴까지의 반복 횟수는 늘지만, 1회 반복당 함수 평가 횟수는 적다. 따라서 총 연산량에 대한 함수 평가 비용의 비율이 큰 경우에는 수렴까지의 계산 시간을 단축할 수도 있다.
위 코드에서 적절한 중단 기준을 설정하는 것이 중요하다. 그렇지 않으면, 부동 소수점 숫자의 제한된 정밀도로 인해 알고리즘이 너무 많은 반복을 실행하여 부정확한 결과를 반환할 수 있다.[3]
참조
[1]
간행물
Origin and evolution of the secant method in one dimension
https://www.jstor.or[...]
2013
[2]
웹인용
Order of Convergence
https://math.librete[...]
2024-10-03
[3]
웹사이트
MATLAB TUTORIAL for the First Course. Part 1.3: Secant Methods
https://www.cfm.brow[...] [4]
서적
Cで学ぶ数値計算アルゴリズム
共立出版
[5]
문서
Secant method
SpringerEOM
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
