방정식의 해 구하기

비선형방정식(non linear equation)

선형이 아닌 방정식. 2차 이상의 방정식을 예시로 들 수 있다.

 우리가 배워온 역학적, 물리적인 여러 방정식들은 편의를 위해 여러 가정을 거쳐 선형 방정식 혹은 간단한 비선형 방정식으로 나타냈지만 현실에서는 다양한 변수가 존재하기 때문에 굉장히 복잡한 비선형 방정식인 경우가 대다수이다.

 따라서 이러한 비선형방정식의 풀이법에 대해서 지금까지도 많은 풀이법이 생겨나며 발전되고 있는데, 그 몇 가지를 오늘 알아보자.

우선 f(x)=0 꼴의 변수가 하나인 함수에 대하여 알아보고, 이를 발전시켜 f(x1, x2...)=0와 같은 다변수 함수까지 확장시켜 보자.

 

Bisection Method

가장 먼저 다룰 방법은 Bisection method이다. 가장 간단한 알고리즘을 가지고 있다. 아래 그림을 보며 직관적으로 이해해보자.

1. 임의의 두 점 a,b를 잡는다

2. 그 중점으로 m(=(a+b)/2)을 잡는다.

3. f(m)이 허용 오차 범위에 들어가는지 확인한다. 오차 범위 안이라면, 그때의 m이 방정식의 해이다.

4. 오차 범위 밖이라면, 다음과 같은 방식으로 a와 b 중 하나를 m으로 옮긴다

f(a) f(m)>0 일 때, a가 m이 된다. 0보다 작다면 b가 m이 된다.

5. 새로운 a,b를 통해 2번 과정부터 다시 실시한다.

 

정말 쉬운 방법이지만, 일정하게 정복해나가는 방식이기에 상당히 느리다. 이를 보완하기 위해 아래와 같은 방법이 고안되었다.

False Position(or Falsi method)

Bisection method와 같은 알고리즘을 사용하지만, 이 방법에서는 a와 b의 중점 m을 사용하는 방식이 아닌 f(a)와 f(b)를 이은 직선의 x절편을 사용한다. 두 점을 지나는 직선의 방정식을 사용하거나 하여 x절편의 위치를 구하면 아래와 같다.

 

하지만 여전히 존재하는 문제점이 하나 있다. 항상 f(a)f(b)>0인 상황이라면 제대로 된 계산이 불가능하여 오류가 발생하는데(y=x^2+1과 같은 예시를 들 수 있다), 이를 해결하기 위하여 아래와 같은 방식이 도입되었다.

Newton-Rapson Method

이번엔 a,b가 아닌 하나의 점 x1에서부터 출발한다. 그 접선의 방정식을 활용하는데, 알고리즘은 아래와 같다.

1. (x1,f(x1))에서의 접선의 방정식을 긋고, 그 x절편을 x2라고 한다.

2. f(x2)가오차범위 이내인지 확인한다. 오차범위 안이라면 해를 찾았으니 종료한다.

3. 오차범위 밖이라면, (x2, f(x2))에서 접선의 방정식을 긋고, x절편을 x3이라고 한다.

이를 계속 반복하면 된다. 접선의 방정식에서의 x절편을 찾는 식은 아래와 같다.

에러를 xk - x(k+1)이라고 설정하고 테일러 급수를 통해 위 식을 전개하다 보면, 우리는 에러가 이차함수에 비례하여 감소한다는 것을 알 수 있다. 위 두 가지 방법보다 이 뉴턴-랩슨 방법이 훨씬 빠르다는 의미이다.

하지만 이런 뉴턴-랩슨 방법 또한 몇몇 문제점을 안고 있다. 두 가지만 설명하자면, 첫째로 미분이 굉장히 복잡한 방정식일 시 오히려 계산이 더 길어질 수 있다는 점이다. 이는 미분 대신 그 근사치를 사용하는 아래의 Secant method를 통해 어느 정도 보완할 수 있다.

 두번째로, 특정 모양의 방정식에 대해 해를 구할 수 없다는 문제점을 가지고 있다. 아래의 세 가지 형태의 방정식을 살펴보자.

 

1. Local minima/maxima, asymptotes

첫째로, 대상 함수가 local minima 혹은 maxima를 가지고 있을 때 뉴턴 랩슨법은 한계를 맞는다. 간단히 설명하면, 함수가 잘 흘러가다가 급격하게 오목한 구간 혹은 볼록한 구간이 있을 경우를 의미하는데 이 경우 값이 계속하여 진동하게 된다.

2. Asymptotes(점근선)

대상 함수가 1/x 그래프와 유사하게 곡선을 그리며 진행되는 경우, 계산값은 점근선을 그리며 계속 뻗어나가게 된다.

3. Overshoot

함수가 아래 모양을 따르면, 계산값은 발산하거나 수렴하게 된다.

 0<s<1/2일 경우 발산 , 1/2<s<1일 경우 수렴한다.

Secant Method

앞서 말했듯이 뉴턴랩슨법은 미분 계산이 복잡할 경우 속도가 현저히 떨어진다는 단점이 존재한다. 이를 보완하여 미분값 대신 그 근사치를 사용하여 계산하는 방법인 Secant method가 생겨났다.

이 값을 통해 뉴턴랩슨법의 식을 다시 정리하면, 아래와 같다.

식에서 볼 수 있듯이 secant method는 과거의(k-1번째) 값도 필요로 하기 때문에, 첫번째와 두번째 값까지는 직접 계산하여 넣어주어야 한다는 단점이 존재한다.

 

 

다변수함수

위의 Newton-Rapson법과 Secant 법을 발전시켜 다변수 함수에 대해서도 해를 구해볼 수 있다. 이를 위해서는 다변수 함수를 미분하는 과정이 필수적인데, 이를 위해 Jacobian Matrix를 활용할 수 있다.

야코 비안 혹은 자코비안으로 많이 불리는 이 행렬은, 치환 적분과 비슷하게 어떤 변수들을 필요한 알맞은 변수로 바꾸어주는 과정에 등장한다. 간단히 x(u,v)와 y(u,v)의 경우에 대해 살펴보면 자코비안 행렬은 다음과 같은 식으로 나타낼 수 있다. 약자로 J를 사용한다.

 

Newton-Rapson Method

이제 아래의 두 연립 비선형 방정식을 보자.

이 두 방정식을 열 벡터화하고, 타일러 급수를 거치면 아래와 같은 식으로 바꿀 수 있다.

이를 다시 표현하면 아래와 같다.

원래의 식과 비교해보면, 분모의 도함수가 Jacobian 역행렬이 된 것을 볼 수 있다. 행렬이기 때문에 분모에 들어가는 대신 역행렬을 취한 것이다.

 

Secant Method

Secant Method의 식 또한 다변수함수에 대하여 확장시킬 수 있다. 원래의 식을 다시 기억해보자.

이를 확장시키면 아래와 같다.