제 2 장. 비선형 방정식의 해법 1. 방정식의 근 2. 방정식의 실근을 구하는 해법 3. 다항식의 복소수 근을 구하는 해법

2 1. 방정식의 근 f ( x ) = 0 을 만드는 x 값을 그 방정식의 근이라고 정의 방정식의 근  중간 값의 정리 함수 f(x) 가 닫힌 구간 [ a, b ] 에서 연속하고, f(a)· f(b) < 0 이면, f(x) =0 을 만족하는 근이 구간 [ a, b ] 에 적어도 하나 있다.

3 1. 방정식의 근 (cont.) 고차다항식이나 초월방정식과 같은 함수는 쉽게 근을 구할 수 없음 – 공식을 이용하여 해를 구할 수 없는 방정식의 근을 수치해법으로 구함 – 대입해야 할 임의의 숫자가 근에 빨리 수렴하는 방법을 찾아내어 원하는 근사값을 얻을 때 까지 대입을 반복

4 2. 실근을 구하는 해법 구간법 (Bracketing) – 함수는 근의 근방에서 부호가 변한다는 사실에 기초를 둠 – 근을 구하기 위하여 두 개의 초기 가정 값이 필요하기 때문에 구간법이라고 함 – 반복적으로 적용하여 근의 참값에 수렴하는 근의 추정 값을 구함

5 2. 실근을 구하는 해법 (cont.) 개구간법 (Open methods) – 한 개의 시작 값이나 구간 내에 근을 포함하지 않는 두 개의 시작 값에서부터 시작하는 방법 – 계산이 진행되면서 발산하거나 근에서 멀어지기도 함 – 수렴할 경우에는 수렴 속도가 빠르다

6 2.1 이분법 (Bisection Method) 구간 반감법 (Interval halving method) 구간을 항상 반으로 나누어 함수의 부호가 바뀌는 구간을 찾아내어 근을 구하는 방법 보다 정확한 값을 얻기 위해 반복

7 2.1 이분법 (Bisection Method) Example : x 2 – 4 = 0 의 근사해를 [0, 5] 에서 구하기 (1) f(x) = x 는 f(0) =  4 0 이므로 f(a)· f(b) < 0 이다. 따라서, [0, 5] 에 해가 존재한다 (2) c =2.5=x 1, f(c) = 2.25 >0 이므로 a=0, b=2.5 이다. 새로운 근사해 c =1.25= x 2 가 되고, f(c) =  <0 이므로 다시 a=1.25, b=2.5 가 된다. 새로운 근사해 c =1.875= x 3 가 되고, f(c) =  <0 이므로 다시 a=1.875, b=2.5 가 된다. (3) 여기에서 반복을 중지하면, 근사해는 c = ( )/2 = = x 4

8 2.1 이분법 (Bisection Method) Algorithm 1. Bisection Method  Input : a, b, e 1, e 2, MAX( 최대반복횟수 ), f(x)  Output : c for n = 1 to MAX length = (b-a)/2 ; approx = a + length ; If ( |f(approx)| < e 2 or length < e 1 ) stop If ( f(a) ·f(approx) < 0) b = approx ; else a = approx ; endfor

9 2.1 이분법 (cont.) 종료 판정 기준과 오차 추정 – 근사 상대 오차 ( i a ) 의 절대 값을 사용 | i a |  E S – 각 반복 단계에서 근사 근은 x r = ( x 1 + x u )/2 – 따라서, 참근의 존재 구간은 ( x u – x 1 )/2 =  x /2

이분법 (cont.) 최대 오차는 구간의 반을 넘지 못하고, 반복 횟수가 증가 될 때마다 오차는 두 배씩 줄어들게 됨 수렴 속도가 느리지만, 오차의 범위가 분명

이분법 (cont.) 반복 횟수의 추정 – 절대 오차를 만족하는 근을 구하기 위하여 필요한 반복 계산 횟수 – 각 반복 단계에서의 절대 오차 ( E a ) – 첫 반복 계산후의 오차

이분법 (cont.) 반복 계산이 수행될 때마다 구간이 반으로 줄어듬 오차와 반복 횟수 n 에 대한 일반식 초기 구간의 간격 (  x 0 ), 허용오차 E S 를 정해놓으면, 반복의 회수 추정 가능

가위치법 (Regular Falsi Method) 선형 보간법이라고도 하며, 이분법이 수렴속도가 느린 점을 개선한 방법 이분법의 결점 : 구간을 x l 와 x u 사이에서 항상 반으로 나누며, 함수 값 f ( x l ) 과 f ( x u ) 의 크기를 고려하지 않음

가위치법 (cont.) 가위치법은 f(x l ) 과 f(x u ) 를 직선으로 연결 시키는 것이다. 이 직선과 x 축이 만나는 교점이 새로운 추정 값

가위치법 (cont.) 초기 경계의 한 값이 고정되고 다른 값은 근에 수렴해 가는 방법이므로, 이분법의 오차보다 훨씬 빠르게 감소 Example : x 2 – 4 = 0 의 근사해를 [0, 5] 에서 구하기

가위치법 (cont.) 두 점 (x 1, f(x 1 )), (x 2, f(x 2 )) 을 지나는 직선의 방정식 P.39 : 가위치법 알고리즘 참조

가위치법 (cont.) 가위치법의 문제점 – 수렴 속도가 빠르다 해도 결론에 위배되는 특별한 경우가 존재 ( 곡선의 기울기에 좌우됨 ) – 근으로의 접근이 한쪽 방향으로 진행되기 때문 – 수정 가위치법 (x 2, f(x 2 )/2), ( x 3, f(x 3 )/2) 을 통과하는 직선이 x 축과 만나는 점 P.41 : 수정 가위치법 알고리즘

고정점 반복법 함수 f(x l ) = 0 을 재 배열함으로써 간단한 고정점 반복법을 유도할 수 있음 x 를 방정식의 좌측에 오게 하여, x = g ( x ) 의 형태로 만들면 이 식은 이전 계산 단계에서의 x 값에 대한 함수를 사용하여 새로운 x 값을 예측하는데 사용

고정점 반복법 (cont.) 고정점 반복법의 반복식 : x i+1 = g(x i ) 수렴 조건 (p.49 그림 2.6) –| g ' (x i ) | < 1 이면 반복 계산이 진행되면서 오차가 감소하고, 기울기가 양이면 오차도 양의 값이 되어 점진적으로 수렴하고, 음이면 오차는 진동 예제 ) f(x)=x 2  x  2 에 대한 가능한 반복식 –x = x 2  2  g’(x) =2x –x = sqrt(2+x)  g’(x) =1/2 sqrt(2+x) –x = 1+2/ x  g’(x) =  1/x 2 –x = (2+5x  x 2 )/4  g’(x) =5/4  x/2

Newton-Raphson 의 방법 x i 에서의 기울기는 이고, 다음과 같이 다시 쓸 수 있음 초기값 x 0 에 대응하는 점 (x 0, f(x 0 )) 에서 함수 f(x) 의 접선 방정식은 y=f ’(x 0 )(x- x 0 )+f(x 0 ) 이 직선이 x 축과 만나는 점 x 1 은

Newton-Raphson 의 방법 (cont.) 오차 추정 – 오차는 이전 단계에서의 오차의 제곱에 비례 장점 : 근의 근처에서 수렴 속도가 매우 빠르다 단점 : 0 에 가까운 기울기 ( f '(x) = 0 ) 를 가지게 되면, 해를 구할 수 없다

Birge-Vieta 의 방법 f '( x ) = 0 인 경우, 조립제법을 이용 다항식 f(x) 를 1 차식 ( x – x 1 ) 으로 나누어 그 몫을 f 1 ( x ) 라 하면

Birge-Vieta 의 방법 (cont.) f 1 ( x ) 를 다시 ( x – x 1 ) 로 나누고, 그 몫과 나머지를 f 2 ( x ), R 2 라고 하면,

Birge-Vieta 의 방법 (cont.) 따라서, Newton 의 반복식은 조립제법 공식의 유도 : p.46-47

할선법 (Secant Method) Newton 방법에서 발생할 수 있는 문제점은 도함수의 계산 두 개 초기값 x i 와 x i-1 이 필요 – 두 점에 대한 함수 값의 부호가 반대일 필요 없음 이므로 에 대입하면

할선법 (cont.) 할선법과 가위치법의 차이 – 할선법은 새로운 x i+1 값은 x i 값을 대치하고, x i 는 x i-1 을 대치하는 엄격한 순서에 의함 – 따라서, 할선법의 두 값이 근의 같은 편에 있을 수도 있으며, 특별한 경우 발산하기도

27 3. 복소수 근을 구하는 해법 다항식 에 대한 근을 찾는 방법 –n 차 방정식 에는 n 개의 근 ( 실근과 복소수 근 ) 이 존재 –n 이 홀수이면 최소한 한 개 이상의 실근이 존재 – 복소수 근이 존재하는 경우에는 a  bi 로 존재

28 3. 복소수 근을 구하는 해법 (cont.) 1.Newton-Raphson 법 2.Muller 법 3.Bairstow 법 4.Lin 의 방법 ( 조립 제법 )

Newton-Raphson 법 시작점의 값을 복소수로 정의해서 반복식에 대입 복소수 근이 존재하면 부호의 차이에 의한 구간의 정의가 불가능하기 때문에 구간법을 사용할 수 없음 개구간법 가운데에서는 일반적으로 Newton-Raphson 방법이 가장 좋다 종료 조건 : 근의 크기 ( ) 가 일정한 값에 수렴

Muller 의 방법 할선법의 연장으로서 인접해 있는 세점을 지나는 포물선 ( ) 을 구하고, 이 포물선이 x 축과 만나는 점을 다음 근사 점으로 취함 –x 축과 만나는 두 근은 근의 공식에 의해 –b 2  4ac 의 값에 따라 복소수 근이 구해짐

Muller 의 방법 f ( x ) = 0 에 가까운 점을 다음 근사 점으로 하여, 새로 계산된 점과 가까이에 있는 점을 사용하여 또 다시 포물선을 구한다 P.64 [ 예제 2.10] 참조 Newton 방법과 달리, 초기값이 실수라고 해도, 복소수 근을 구할 수 있다

Muller 의 방법 (cont.) 할선법 Muller 법 

Bairstow 의 방법 Bairstow 법은 조립제법을 사용하여 인수 ( ) 로 다항식을 나누는 것이 주된 과정 반복 과정은 오차 (  r,  s ) 가 허용오차 판정 기준인 E s 이하로 떨어지면 중지하고, 근의 공식을 사용하여 근을 구한다

Bairstow 의 방법 (cont.) 위의 식을 전개하여 계수를 비교하면, 조립제법 공식 나머지 R

Bairstow 의 방법 (cont.) f(x) 가 인수로 나누어 떨어진다면, b n 과 b n+1 을 ( r 0, s 0 ) 를 중심으로 Taylor 급수 전개하 고, (r  r 0 ) 와 (s  s 0 ) 값이 극히 작다고 가정하여, 2 차항 이상을 무시하면

36 이 식에서 을 구하려면, b n 과 b n+1 에 대한 편미분 값을 구해야 함 에 대한 연립방정식 3.3 Bairstow 의 방법 (cont.) 위와 같이 정의하고, r 1 과 s 1 이 근사값이라고 가정하여 식을 정리하면, ( 식 1)

Bairstow 의 방법 (cont.) 조립제법 식으로부터 b 와 c 의 값의 관계식을 정리하면, 위의 식을 r 과 s 에 대하여 편미분 해서, c 에 대해 정리 조립제법 공식

Bairstow 의 방법 (cont.) 위의 연립방정식을 풀면 결과를 ( 식 1) 에 대입해서, 새로운 값 r 1, s 1 을 구한다 p.67( 식 2.48) 참조

Bairstow 의 방법 (cont.) 계산을 반복하다가, 의 값이 거의 0 이 되는 시점에 반복을 중지 이때의 r 과 s 의 값을 가지고 근의 공식을 사용하여 근을 구한다 P.68 [ 예제 2.11] 참고

40 예제 2.11 풀이 ) 다항식 을 이용하여 인수분해. 즉, r 0 =  1 s 0 =  1 을 사용하여 조립제법 적용 r 0 =  1 s 0 =  1 a1a1 a 2 a 3 a 4 a 5 1          5.5    3.2 a 2 + rb 1 b n+1 bnbn cncn a 2 + rb 2 + sb 1

41 예제 2.11 (cont.) n = 4 이므로 –b 1 = 1, b 2 =  2.1, b 3 = 3.4, b 4 =  0.8, b 5 = 0.7 –c 1 = 1, c 2 =  3.1, c 3 = 5.5, c 4 =  3.2 – 따라서, r 1 =  =  0.89, s 1 =  1  0.06 =  1.06

42 예제 2.11 (cont.) r 1 =  0.89 s 1 =  1.06 a1a1 a 2 a 3 a 4 a 5 1          4.01    1.03 두번째 반복하면, r 2 =  0.89  =  0.9 s 2 =  1.06  =  1.1

43 예제 2.11 (cont.) 여기에서 반복을 중지하면, 에 대한 근의 공식 와