수치해석을 이용한 근 찾기 Rootfinding with the Use of Numerical Analysis

(1)

한빛미디어 Engineering Numerical Analysis Learning by MATLAB 1^/43

CHAPTER 07

수치해석을 이용한 근 찾기

Rootfinding with the Use of Numerical Analysis

방성완

중앙대학교 전자전기공학부

2012. 12. 31

(2)

7.2

뉴턴법

7.1

이분법

7.3

할선법

가위치법

7.4

근 찾기 방법 비교

7.5

(3)

학습목표

구간의 중앙값을 이용하는 이분법으로 근을 찾을 수 있다.

함수의 1차 도함수를 이용하는 뉴턴법으로 근을 찾을 수 있다.

뉴턴법을 기초로 한 할선법을 이용하여, 1차 도함수를 계산하지 않고 근을 찾을 수 있다.

구간의 끝점들을 연결시킨 직선과 직선의 절편의 위치를

이용하는 가위치법으로 근을 찾을 수 있다.

(4)

7.1 이분법

7.1 이분법

함수의 근

 어떤 함수 f(x)에 대해서 조건 f(x) = 0을 만족하는 숫자 x가 근(roots)

 x축과 그래프가 만나는 점

 1차부터 4자까지의 다항식은 다음의 근의 공식으로 계산

 더 큰 문제 해결을 위한 중간 단계로 자주 사용

 5차 이상의 다항식에는 존재하지 않음

 비선형 방정식의 근을 찾기는 어려움

 수치해석에서는 근삿값과 관련된 오차 해석을 이용하여 찾음

(5)

7.1 이분법

7.1 이분법

반복법(Iterative method)

 f(x) = 0이 되는 x를 구할 때 기초로 사용

 반복적으로 구한 근삿값을 거듭 이용하여 더욱 정확한 값을 계산

이분법(Bisection method)

 반복법을 활용한 가장 간단한 방법

 범위가 정해져 있는 구간을 항상 반으로 나누어 검색하는 증분법의 변형

 구간의 중앙값을 이용하여 함수값을 계산



함수 f(x)가 구간 [a, b]에서 연속적이고, 근

a

가 존재

 실제 근

a

, 근사적 근

 허용 오차

e

,

e

> 0

(6)

7.1 이분법

7.1 이분법

 구간에서 함수의 부호가 (+)에서 (-)로 혹은 (-)에서 (+)로 바뀌면 근이 존재

 구간 [a, b]를 이등분하여 부호가 바뀌면 이분법을 계속 반복

 함수 f(x)가 0이 되는 정확한 근을 찾게 됨

 함수의 부호가 더 이상 바뀌지 않는 일 때 이분법을 중단

이분법을 이용하여 근을 찾는 단계적 계산 과정

(7)

7.1 이분법

7.1 이분법

sign은 양의 부호 혹은 음의 부호를 표시

(8)

7.1 이분법

7.1 이분법

 실제 근

a

와 근사적 근 c_i에 대한 절대 오차

 초기 구간 [a₁, b₁], 연속적 구간 [a_i, b_i], 중앙값

 귀납적 방법으로 일반화시킨 식 (7.3)

 이분법의 가장 큰 장점은 항상 실제 근에 수렴

 항상 경계 오차를 만족하고 반복 실행할 때마다 반씩 줄어듬

 이분법의 단점은 근을 찾아가는 실행 속도가 느림

 함수 f(x)가 근

a

에 대해서 연속적 미분이 가능한 경우, 실행 속도가 더욱 느림

(9)

7.1 이분법

7.1 이분법

예제

7-1

이분법의 기초 개념 이해하기

A와 B 두 사람이 카드놀이를 하고 있다. A가 1~100까지 번호가 정해진 카드

100장에서 1장을 뽑고, B가 뽑힌 카드의 번호를 맞추는 놀이다. 이때 B는 A에게 자신이 선택한 번호가 카드의 번호보다 큰 숫자인지 혹은 작은 숫자인지를 물을 수 있다.

이분법을 사용하여 이 문제를 풀 경우 최대 몇 번 이내에 정확히 번호를 맞출 수 있겠는가?

Tip !

 최대 횟수를 구하는 수치적 표현은 2ⁿ ≤ 카드의 총 갯수

(10)

7.1 이분법

7.1 이분법

예제

7-2

이분법을 이용한 비선형방정식의 근 찾기

다음 비선형방정식이 주어졌다. 편의를 위해서 모든 결과는 소수점 네 자리까지 나타내라.

(a) 구간 [0, 1]에서 양의 근이 하나 존재함을 보여라.

(b) 이분법을 네 번 반복하여 각각의 근 를 계산하라. 참고로 주어진 함수 f(x)의 정확한 양의 근은

a

= 0.6180이다.

(c) 절대 오차의 값이 10^-6보다 작은 범위 내에 존재하는 경우, 필요한 반복 횟수 n을 구하라.

Tip !

 (c)의 풀이는 식 (7.4)를 직접 이용

(11)

7.1 이분법

7.1 이분법

MATLAB

7-1

매트랩을 이용한 이분법 실행

매트랩을 이용하여 [예제 7-2(b)]의 결과를 구하라. 편의를 위해서 모든 결과는 소수점 네 자리까지 나타내라.

Tip !

 부록에서 제공하는 사용자정의함수 bisect 함수를 현재 사용중인 매트랩의 작업 공간에 저장한 이후에 사용

(12)

function root=bisect(a0,b0,ep,max_iterate,index_f)

if a0 >= b0

disp('a0 < b0 is not true. Stop!') return

end

format short a = a0; b = b0;

fa = f(a,index_f); fb = f(b,index_f);

if sign(fa)*sign(fb) > 0

disp('f(a0) and f(b0) are of the same sign. Stop!') return

end

c = (a+b)/2;

it_count = 0;

while b-c > ep & it_count < max_iterate it_count = it_count + 1;

fc = f(c,index_f);

iteration = [it_count a b c fc b-c]

if sign(fb)*sign(fc) <= 0 a = c;

fa = fc;

else b = c;

fb = fc;

end

c = (a+b)/2;

pause end

format short root = c format short error_bound = b-c format short it_count

%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function value = f(x,index)

% function to define equation for rootfinding problem.

switch index case 1

value = x.^3 +2*x.^2 - 1;

case 2

value = x.^3+x-7;

end

bisect.m

(13)

7.2 뉴턴법

7.2 뉴턴법

뉴턴법(Newton method)

 비선형방정식의 근을 결정할 때 자주 사용하는 방법

 개발자인 뉴턴과 랩슨(Raphson)의 이름을 합쳐서 뉴턴-랩슨법이라고도 부름

[그림 7-2] 설명

 근

a

는 y = f(x) 그래프가 x축과 교차하는 점을 찾음

 근을 찾기 위한 문제 f(x) = 0을 쉽게 찾기 힘든 경우

 근

a

의 근처에서 함수 f(x)를 근사시킴

 선형 다항식 p₁(x)를 구하여 p₁(x) = 0을 계산

 구간 [a, b]에서 함수 f(x)가 미분 가능하고 함수의 해도 포함하고 있다고 가정

(14)

7.2 뉴턴법

7.2 뉴턴법

[그림 7-2] 뉴턴법의 기하학적 표시

(15)

7.2 뉴턴법

7.2 뉴턴법

 미분을 이용한 접선으로 수렴해 가는 방법을 사용하여 처음 해로 x₀를 추정

 x₀가 실제 근에 가까운 값일수록 더 빠르게 수렴

 x₀가 실제 근에 가까운 값이 아니어도 구간 내에 있으면 최종 해는 구함

 미분으로 x₀에서 접선을 구하고 이 접선을 이용하여 x₁을 구함

 x₁은 x₀보다 좀 더

a

에 근접

 같은 방법을 반복하면 실제 근

a

에 수렴함

x

₁

에 대한 뉴턴법 공식 찾기

 좌표 (x₀, f(x₀))은 곡선 그래프 y = f(x)와 선형 다항식 p₁(x)가 교차하는 접촉점

 방정식 y = p₁(x)

(16)

7.2 뉴턴법

7.2 뉴턴법

 근 x₁을 찾기 위해서 p₁(x₁) = 0으로 놓고 식 (7.5) 다시 쓰기

 식 (7.6) 정리

 이때

 x₁을 초기 가정값으로 놓고 근 x₂를 찾은 식

 x₁이 x₀보다 실제 근

a

에 더 근접

 같은 과정을 n번 반복 실행하면 점점 정확한 실제 근

a

를 찾게 됨

(17)

7.2 뉴턴법

7.2 뉴턴법

 추정하려는 근 x₀, x₁, x₂, ··· 에 대한 뉴턴법의 일반형

구간 [1, 2]에서 함수 f(x) = e

^x

– x

³

에 대한 정확한 근을 근사

 함수 f(x)의 1차 도함수 f ‘(x) = e^x – 3x²를 식 (7.9)에 대입

 구간의 중앙값 1.5를 초기 가정값 x₀으로 지정하여 식 (7.9)에 대입

 x

₀은 구간 내의 어떤 값을 선택해도 무관

 정리하여 다시 쓴 식 (7.9)

(18)

7.2 뉴턴법

7.2 뉴턴법

 반복 계산된 추정하려는 근 x₁, x₂, x₃의 결과

 세 번 반복한 x₃의 값이 실제 근과 같은 값, 더 이상 반복 계산은 불필요

 유효숫자의 자릿수가 증가하면 더 많은 반복이 필요

(19)

7.2 뉴턴법

7.2 뉴턴법

예제

7-3

뉴턴법을 이용한 비선형방정식의 근 찾기

다음 비선형방정식이 구간 [0, 1]에서 양의 근이 하나 존재한다. 뉴턴법을 이용하여 반복해서 나타나는 근들을 계산하라. 편의를 위해서 모든 결과는 소수점 네 자리까지 나타내라.

Tip !

 추정하는 초기값 x₀는 주어진 구간의 중앙값 0.5로 지정

 함수 f(x)의 1차 도함수를 구함

 뉴턴법의 반복 계산에 필요한 수식

그래프 x=-4:0.1:5;

y=x.^3+2*x.^2-1;

plot(x,y) hold

y2=zeros(1,91);

plot(x,y2)

(20)

7.2 뉴턴법

7.2 뉴턴법

MATLAB

7-2

매트랩을 이용한 뉴턴법 실행

매트랩을 이용하여 [예제 7-3]의 결과를 구하라. 편의를 위해서 모든 결과는 소수점 네 자리까지 나타내라.

Tip !

 부록에서 제공하는 사용자정의함수 newton 함수를 현재 사용중인 매트랩의 작업 공간에 저장한 이후에 사용

(21)

한빛미디어 Engineering Numerical Analysis Learning by MATLAB 21^/43 function root = newton(x0,error_bd,max_iterate,index_f)

format short error = 1;

it_count = 0;

while abs(error) > error_bd & it_count <= max_iterate fx = f(x0,index_f);

dfx = deriv_f(x0,index_f);

if dfx == 0

disp('The derivative is zero. Stop') return

end

x1 = x0 - fx/dfx;

error = x1 - x0;

iteration = [it_count x0 fx dfx error]

x0 = x1;

it_count = it_count + 1;

end

if it_count > max_iterate

disp('The number of iterates calculated exceeded') disp('max_iterate. An accurate root was not') disp('calculated.')

else

format short root = x1 end

function value = f(x,index) switch index

case 1

value = x.^3 +2*x.^2 -1;

case 2

value = x.^3+x-7;

end

function value = deriv_f(x,index) switch index

case 1

value = 3 * x.^2 + 4*x ; case 2

value = 3*x.^2+1;

end

newton.m

(22)

한빛미디어 Engineering Numerical Analysis Learning by MATLAB 22

7.2 뉴턴법

7.2 뉴턴법

 뉴턴법의 가장 큰 장점은 실제 근에 빠른 속도로 수렴

 4~5번의 반복 실행으로 10^-6 정도의 작은 오차 범위를 갖는 근을 구함

 뉴턴법의 단점은 기술적으로 완전히 수렴되지 못함

 또 다른 단점은 함수 f(x)의 1차 도함수 f ’(x)의 계산도 반드시 필요

 근사시키는 함수 f(x)가 미분 가능한지를 먼저 확인

(23)

7.3 할선법

7.3 할선법

할선법(Secant method)

 뉴턴법을 기초로 이용

 뉴턴법과는 다르게 1차 도함수 f ‘(x)의 계산이 필요없는 유용한 방법

 뉴턴법처럼 실제 근에 완전하게 수렴하지는 않음

 함수 f(x)의 곡선 그래프와 교차하는 접촉점을 이용하여 직선을 그림

 실제 근

a

에 근접하는 두 개의 초기점 x₀와 x₁을 추정

 세 번째 추정점 x₂는 좀 더 실제 근

a

에 근접

(24)

7.3 할선법

7.3 할선법

[그림 7-4]와 [그림 7-5] 설명

 두 개의 접촉점 (x₀, f(x₀))와 (x₁, f(x₁))을 연결하여 생성되는 선이 할선(secant line)

 이 할선이 y = f(x)의 그래프를 근사

 [그림 7-4]에서 실제 근은 추정하는 값들 사이에 위치

 추정하는 각각의 값이 서로 반대

 초기의 두 점 x₀와 x₁을 내삽하여 x₂를 구함

[그림 7-5]에서 실제 근은 추정하는 값들 바깥에 위치

 실제 근을 중심으로 추정하는 각각의 값이 서로 같은 방향

 초기의 두 점 x₀와 x₁을 외삽하여 x₂를 구함

(25)

7.3 할선법

7.3 할선법

[그림 7-4] 할선법의 기하학적 표시 그림 : x₁ <

a

< x₀

(26)

7.3 할선법

7.3 할선법

[그림 7-5] 할선법의 기하학적 표시 그림 :

a

< x₁ < x₀

(27)

7.3 할선법

7.3 할선법

 주어진 선형 다항식

 초기 추정한 두 개의 점 x₀와 x₁에서 함수 f(x)가 교차

 식 (7.10)으로 그린 직선은 새롭게 추정하는 근 x₂도 통과

 식 (7.11)을 이용하여 식 (7.10)의 계수 a₀와 a₁

(28)

7.3 할선법

7.3 할선법

 식 (7.13)과 식 (7.14)를 식 (7.12)에 대입

 식 (7.11)의 상태를 확인하기 위해서 식 (7.15)에 x = x₀와 x = x₁을 각각 대입

 식 (7.15)를 p₁(x₂) = 0으로 놓고 근 x₂를 계산

 식 (7.17)을 식 (7.9)와 비교하면 다음의 수식은 뉴턴법의 근사치라고 부름

(29)

7.3 할선법

7.3 할선법

구간 [1, 2]에서 함수 f(x) = e

^x

– x

³

에 대한 정확한 근을 근사

 첫번째 추정할 수 있는 근은 x₂

 초기 가정값 x₀은 상한값 2를 x₁은 하한값 1을 이용

 새롭게 계산되는 근들

(30)

7.3 할선법

7.3 할선법

예제

7-4

할선법을 이용한 비선형방정식의 근 찾기

다음 비선형방정식이 구간 [0, 1]에서 양의 근이 하나 존재한다. 할선법을 이용하여 반복해서 나타나는 근들을 계산하라. 편의를 위해서 모든 결과는 소수점 네 자리까지 나타내라.

Tip !

 초기 두 개의 점은 x₀ = 1과 x₁ = 0

(31)

7.3 할선법

7.3 할선법

MATLAB

7-3

매트랩을 이용한 할선법 실행

매트랩을 이용하여 [예제 7-4]의 결과를 구하라. 모든 결과는 매트랩 출력 명령어 format long을 이용하여 표시하라.

Tip !

 부록에서 제공하는 사용자정의함수 secant 함수를 현재 사용중인 매트랩의 작업 공간에 저장한 이후에 사용

(32)

function root = secant(x0,x1,error_bd,max_iterate,index_f) format short

error = 1;

fx0 = f(x0,index_f);

it_count = 0;

iteration = [it_count x0 fx0]

while abs(error) > error_bd & it_count <= max_iterate it_count = it_count + 1;

fx1 = f(x1,index_f);

if fx1 - fx0 == 0

disp('f(x1) = f(x0); Division by zero; Stop') return

end

x2 = x1 - fx1*(x1-x0)/(fx1-fx0);

error = x2 - x1;

iteration = [it_count x1 fx1 error]

x0 = x1;

x1 = x2;

fx0 = fx1;

end

if it_count > max_iterate

disp('The number of iterates calculated exceeded') disp('max_iterate. An accurate root was not') disp('calculated.')

else

format short root = x2 end

function value = f(x,index) switch index

case 1

value = x.^3 +2*x.^2 -1;

case 2

value = x.^3+x-7;

end

secant.m

(33)

7.3 할선법

7.3 할선법

 할선법은 이분법보다 더 빠르게 실제 근에 수렴하는 장점이 있음

 할선법의 단점은 이분법과는 다르게 기술적으로 완전히 수렴되지 못함

 할선법은 뉴턴법과는 다르게 f ‘(x)의 계산은 불필요

 할선법도 뉴턴법처럼 대개의 경우만 수렴

(34)

7.4 가위치법

7.4 가위치법

가위치법(Regula falsi method : False-position method)

 이분법을 수정한 형태

 구간의 폭을 반복적으로 좁히면서 정확한 근은 구하지 않음

 새롭게 설정되는 구간의 끝 점들을 직선으로 연결

 절편의 위치를 결정하여 다음 근들을 추정

 함수 f(x)가 주어진 구간 내에서 근을 포함

 반복적으로 미리 결정된 근의 값을 수행

(35)

7.4 가위치법

7.4 가위치법

[그림 7-7] 설명

 좌표점 (a, f(a))와 (b, f(b))을 통과하는 직선방정식

 m은 직선방정식의 기울기 표시

 f(x) = 0일 때 새롭게 추정되는 근 x

 직선방정식의 절편

(36)

7.4 가위치법

7.4 가위치법

[그림 7-7] 가위치법의 기하학적 표시 그림

(37)

7.4 가위치법

7.4 가위치법

구간 [a, b]에서 의 근을 찾기 위한 가위치법 알고리즘

(38)

7.4 가위치법

7.4 가위치법

구간 [a, b]에서 의 근을 찾기 위한 가위치법 알고리즘

(39)

7.4 가위치법

7.4 가위치법

구간 [1, 2]에서 함수 f(x) = x

³

+ x – 7에 대한 x

₀

, x

₁

, x

₂

를 추정

 구간의 왼쪽 끝점 1을 a₀로 놓고 오른쪽 끝점 2를 b₀로 지정

 식 (7.22)와 식 (7.23)에 n = 0, n = 1, n = 2를 대입

 계산 과정은 선택적으로 ②와 ③ 둘 중 하나를 이용



 n = 0에 대하여 f (a₀ = 1) = -5와 f (b₀ = 2) = 3

(40)

7.4 가위치법

7.4 가위치법

 다음 단계를 반복 수행하기 위한 a₁과 b₁

 n = 1에 대하여 f (a₁ = 1.625) = -1.0840와 f (b₁ = 2) = 3

 다음 단계를 반복 수행하기 위한 a₂와 b₂

(41)

7.4 가위치법

7.4 가위치법

 n = 2에 대하여 f (a₂ = 1.7245) = -0.1467와 f (b₂ = 2) = 3

 세 번째 반복으로 구한 기울기와 근사시킨 근

 같은 방법으로 양쪽 끝점들을 계속 이용하여 반복 실행

 실제 근

a

= 1.7392에 가깝게 접근

(42)

7.4 가위치법

7.4 가위치법

예제

7-5

가위치법을 이용한 비선형방정식의 근 찾기

다음 비선형방정식이 구간 [0, 1]에서 양의 근 하나가 존재한다. 가위치법을 이용하여 반복해서 나타나는 근들을 계산하라. 편의를 위해서 모든 결과는 소수점 네 자리까지 나타내고 실제 근과 동일한 값이 나올 때까지 반복 계산을 실행하라.

Tip !

 주어진 구간의 왼쪽 끝점 0을 a₀, 오른쪽 끝점 1를 b₀로 지정

(43)

7.4 가위치법

7.4 가위치법

MATLAB

7-4

매트랩을 이용한 가위치법 실행

매트랩을 이용하여 [예제 7-5]의 결과를 구하라. 모든 결과는 매트랩 출력 명령어 format long을 이용하여 표시하라.

Tip !

 부록에서 제공하는 사용자정의함수 regula 함수를 현재 사용중인 매트랩의 작업 공간에 저장한 이후에 사용

(44)

7.4 가위치법

7.4 가위치법

 가위치법은 이분법과 다르게 주어진 구간에 대한 구간법 이용이 불확실

 가위치법은 할선법과 동일한 방법으로 근삿값 추정

 가위치법은 이분법보다 신속하게 근을 찾음

 이분법보다 계산은 복잡

 가위치법은 끝점 두 개가 필요하고 항상 실제 근에 수렴

(45)

7.5 근 찾기 방법 비교

7.5 근 찾기 방법 비교

[표 7-4] 근 찾기 방법의 비교표

(46)