방정식 해 찾기 - 고정점 반복법

하나의 변수 $x$를 가진 방정식의 해를 구하고 싶습니다. ($f(x) = 0$) 방정식의 해를 구하는 방법은 여러 가지가 있습니다만 이번 포스트에서 알아볼 방법은 고정점 반복법이라는 알고리즘입니다. 고정점 반복법의 시작은 $f(x) = 0$을 $g(x)=x$의 형태로 두고 $y=x$와 $y=g(x)$의 연립방정식을 반복을 통해 푸는 방법으로  특정 조건 하에서 사용할 수 있습니다.

그렇다면 $f(x) = 0$으로부터 $g(x) = x$ 형태로 둔다는 것은 무엇일까요? 예를 들어 $f(x)=x-cos(x)$일 경우, $g(x)$는 $x=g(x)=cos(x)$로 둠으로써 $y=x$와 $y=cos(x)$의 교차점을 찾으면 $f(x)=x-cos(x)=0$의 해를 구할 수 있겠죠. 만약 $f(x)=x^3+cos(x)$일 경우에는 양변에 $x$를 더해 $x+f(x)=x+x^3+cos(x)=g(x)$의 형태로 만들 수 있겠죠. 이 경우에는 $y=x$와 $y=x+x^3+cos(x)$의 교차점이 해가 되겠죠. 이러한 방법이 가능한 이유는 $f(x)=0$에서 $x=x+f(x)$이고 $x+f(x)=g(x)$라 할 때, $f(x)=0$의 해가 $r$이라면 $r=g(r)$이 성립하기 때문입니다. 따라서 $y=x$와 $y=g(x)$의 교차점이 $r$이 되고 이를 고정점 (fixed point) 라고 합니다.

고정점 반복법의 시작은 임의의 점 $x_0$에서 시작해서 $x_1=g(x_0)$, $x_2=g(x_1)$ 식으로 $r$에 접근하는 방석으로 이루어집니다. 이 과정을 반복하게 되면 다음과 같습니다. ($s_n\in (x_n, r)$로 두 번쨰 수식은 평균값 정리로 유도됩니다.)

$e_{i+1}=|x_{i+1}-r|=|g(x_i)-g(r)|$

$=|g'(s_n)(x_n-r)|=|g'(s_n)(x_n-r)|=|g'(s_n)|e_{i}$

위의 수식을 보면 $i+1$ 번째에서의 고정점과의 거리 $e_{i+1}$는 $i$ 번째에서의 고정점과의 거리 $e_i$에서 $r$과 $x_i$ 사이에 있는 값의 미분값이 곱채진 것을 볼 수 있습니다. 즉, $|g'(s_n)|$의 값이 1보다 작다면, 이 과정을 반복하했을 때 고정점 $r$에 점점 가까워지게 되곘죠. 당연히 $|g'(s_n)|$의 값이 1보다 크면 수렴하지 않고 발산하게 됩니다.

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=mykepzzang&logNo=220080754808

 

파이썬 구현

def D(f, h=1e-6):  # first derivative of f
    return lambda x, f=f, h=h: (f(x + h) - f(x - h)) / 2 / h
    
def solve_fixed_point(f, x, ap=1e-6, rp=1e-4, ns=100):
    def g(x):
        return f(x) + x  # f(x)=0 <=> g(x)=x

    Dg = D(g)
    for k in range(ns):
        if abs(Dg(x)) >= 1:
            raise ArithmeticError("error D(g)(x)>=1")
        (x_old, x) = (x, g(x))
        if k > 2 and norm(x_old - x) < max(ap, norm(x) * rp):
            return x
    raise ArithmeticError("no convergence")

 

참조

• https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=mykepzzang&logNo=220080754808
• https://blog.naver.com/jang_hwan_im/221241743842