Open methods

Open methods

6.1 simple fixed-point lteration 6.2 newton- Raphson

6.3 Secant Methods 6.4 Brent’s Method

6.5 MATLAB Function: Fzero 6.6 Polynomials

목차

• Recognizing the difference between bracketing and open methods for root location.

• Understanding the fixed-point iteration method and how you can evaluate its convergence

characteristics.

• Knowing how to solve a roots problem with the NewtonRaphson method and appreciating the

concept of quadratic convergence.

• Knowing how to implement both the secant and the modified secant methods.

• Knowing how to use MATLAB’s fzero function to estimate roots.

• Learning how to manipulate and determine the roots of polynomials with MATLAB.

학습 목표

6.1 simple fixed-point lteration

단일 고정점 반복법

) (x g

x 

0 )

( x 

f x _{i  1}  g ( x _i )

% 100

1 1











i

i i

a

x

x

근

x

산 오차

Ex) 6.1

고정점 반복법을 통해

f ( x )  e

^x  x

x e

x

f ( ) 

 x  e ^{ x} x i _{ 1}  e ^{ x}

초기값x=0 설정

i x_i (%) (%)

0 1 2 3 4 5 6 7 8 9 10

0.0000 1.0000 0.3679 0.6922 0.5005 0.6062 0.5454 0.5796 0.5601 0.5711

0.5649

100.000 171.828 46.854 38.309 17.447 11.157 5.903 3.481 1.931 1.109

100.000 76.322 35.135 22.050 11.755 6.894 3.835 2.199 1.239 0.705 0.399

0.763 0.460 0.628 0.533 0.586 0.556 0.573 0.564 0.569 0.566





/

t i 



근의 참값:

0.56714329

) (x g

0 x 

) (



f

x 

g ( x

)

Convergence possibility

(수렴가능성)

1 ) ( 

 x

g

1 ) ( 

 x

g

0 ) ( 



오차 감소

오차 증가

0 ) ( 

 x

g

오차 단조로움

오차가진동

) ( ) (

2 1

x g y

x y

x e

x

f









6.2 Newton-Raphson 법

1. 근에 대한 초기값 𝑥_𝑖 설정

2. (𝑥_𝑖,𝑓(𝑥_𝑖))에 접하는 접선 구하기 3. 접선과 x축이 만나는 점 찾기

개선된 추정값 공식으로 나타내기

1

0 ) ) (

(



 



i i

i

i

x x

x x f

f

) (

) (

1

i i i

i

f x

x x f

x

Raphson 공식

Ex) 6.2

x e

x

f ( ) 



Newton-Raphson 법을 사용하여 의 근을 추정하라.

초기 가정은 x₀ = 0

1 )

(   

 x e ^x

f

  1

 



 _i

i

x

i x

i

i

e

x x e

x

i x

(%)

0 1 2 3 4

0

0.500000000 0.566311003 0.567143165

0.567143290

100 11.8 0.147 0.0000220

< 10^-8



0 ) ) (

(

 

 



i i

i

i x x

x x f

f

( )

) (

1

i i i

i

f x

x x f

x

  

Ex) 6.3

Newton-Raphson 법을 사용하여 의 양근을 추정하라.

초기 가정은 x₀ = 0.5

f ( x )  x

 1

9 10

1

10

1

i i

i

x

x x

x

  

i x

0 1 2 3 4 40 41 42

0.5 51.65 46.485 41.8365 37.65285 1.002316 1.000024

1

99.032 11.111 11.111 11.111 2.130 0.229 0.002



수렴 속도가 매우 느리다.

Newton-Raphson법이 수렴되지 않는 경우

Newton-Raphson법을 위한 일반적인 수렴판정 기준 없다.

그니까 초기값을 최대한 정확히 잡아야함 근데 초기값 잘 잡아도 소용없는 경우도 있음

그러니까 수렴이 늦거나 발산을 인식할 수 있는 좋은 프로그램이 작성되어야 한다!

Ex) 6.4

항력계수가 0.25kg/m 일때 자유낙한 4초 후의 속도가 36m/s가 되는 번지점프하는 사람의 질량을 구하기 위해, M 파일 함수를 사용하라 (중력가속도 9.81m/ss)

𝑓 𝑚 = 𝑔𝑚

𝑐_𝑑 tanh 𝑔𝑐_𝑑

𝑚 𝑡 − 𝑣(𝑡)

Newton raphson 법을 적용하기 위해 도함수를 미지수 m에 대하여 구해야 한다.

𝑑𝑓(𝑚)

𝑑𝑚 = 1 2

𝑔

𝑚𝑐_𝑑 tanh 𝑔𝑐_𝑑

𝑚 𝑡 − 𝑔

2𝑚𝑡𝑠𝑒𝑐ℎ² 𝑔𝑐_𝑑 𝑚 𝑡

Newtraph 함수 .M파일로 저장

근 구하기

6.3 SECANT METHODS

할선법

도함수 계산을 줄이기 위해

i i

i i

i x x

x f x

x f

f 

 





 1

1) ( )

) (

( ( )

) (

1

i i i

i f x

x x f

x _   

할선법을위한 공식

) ( ) (

) )(

(

1 1 1

i i

i i

i i

i f x f x

x x

x x f

x 

 





 

) ( )

(

) )(

(

1 1 1

i i

i i

i i

i

f x f x

x x

x x f

x

 





 

두 초기값 사용

한 초기값 사용

i

i i

i

i x

x f x x x f

f 





 

 ( ) ( )

)

( ( )

) (

1

i i i

i f x

x x f

x _   

) ( ) (

) (

1

i i

i

i i i

i f x x f x

x f x x

x  

 

 

) ( )

(

) (

1

i i

i

i i

i

i

f x x f x

x f x x

x   

 





할선법 공식

Ex) 6.5

수정된 할선법으로 항력계수가 0.25 kg/m일 때 자유낙하 4초 후의 속도가 36

m/s가 되도록 번지점프 하는 사람의 질량을 구하라.

중력가속도 9.81 m/s2 질량의 초기가정 50 kg 변동량 10-6

%) 4 . 43

%;

1 . 38 (

39931 .

88

) 57938708 .

4 ( 579381118 .

4

) 57938708 .

4 )(

50 ( 50 10

579381118 .

4 ) (

00005

. 50

57938708 .

4 ) (

50

6 1

0 0

0 0

0 0

















 

























a t

x

x x

f x

x

x f x

) ( )

(

) (

1

i i

i

i i

i

i

f x x f x

x f x x

x   

 





%) 76 . 28

%;

1 . 13 (

08970 .

124

) 69220771 .

1 ( 692203516 .

1

) 69220771 .

1 )(

39931 .

88 ( 10

39931 .

88

692203516 .

1 ) (

39940

. 88

69220771 .

1 ) (

39931 .

88

6 2

1 1

1 1

1 1

















 

























a t

x

x x

f x

x

x f x

i x_i (%) (%)

0 1 2 3 4 5 6

50.0000 88.3993 124.0897 140.5417 142.7072 142.7376 142.7376

64.971 38.069 13.064 1.538 0.021 4.1  10^-6 3.4  10^-12

43.438 28.762 11.706 1.517 0.021 4.1  10^-6

a _t

6.4 Brent’s Method

• 구간법 + 개방법 => 혼합법 Brent !!

• 구간법

– 이분법

• 개방법

– 할선법

– 역2차 보간법

• 역 2차 보간법

x x

F(x) F(x)

근의 추정값! 근의 추정값!

• 할선법

• 세 점 (𝑥

𝑦

),(𝑥

𝑦

),(𝑥

𝑦

)이 존재

• 𝑔 𝑦 =

𝑖−2−𝑦_𝑖−1)(𝑦_𝑖−2−𝑦_𝑖)

𝑥

+

𝑖−1−𝑦_𝑖−2)(𝑦_𝑖−1−𝑦_𝑖)

𝑥

+

(𝑦−𝑦_𝑖−2)(𝑦−𝑦_𝑖−1) (𝑦_𝑖−𝑦_𝑖−2)(𝑦_𝑖−𝑦_𝑖−1)

𝑥

• 𝑥

=

(𝑦_𝑖−2−𝑦_𝑖−1)(𝑦_𝑖−2−𝑦_𝑖)

𝑥

+

(𝑦_𝑖−1−𝑦_𝑖−2)(𝑦_𝑖−1−𝑦_𝑖)

𝑥

+

𝑦_𝑖−2𝑦_𝑖−1

(𝑦_𝑖−𝑦_𝑖−2)(𝑦_𝑖−𝑦_𝑖−1)

𝑥

x y

y=f(x)

X=f(y)

X축과 교차하지 않아!!

• 예제6.6

• 점들[(1,2), (2,1), (4,5)]에 대해 먼저 y=f(x) 에 대한 2차 공식을 사용 하여 근이 복소수임을 보이고 x= g(y)에 대해 역 2차 보간법을 사용 하여 근의 추정값을 구하여라.

• f 𝑥 = ^{(𝑥−2)(𝑥−4)}

(1−2)(1−4)2 + ^{(𝑥−1)(𝑥−4)}

(2−1)(2−4)1 + ^{(𝑥−1)(𝑥−2)}

(4−1)(4−2)5

• f x = 𝑥² − 4𝑥 + 5

• x=2±𝑖

• g y = ^{(𝑦−1)(𝑦−5)}

(2−1)(2−5) 1 + ^{(𝑦−2)(𝑦−5)}

(1−2)(1−5) 2 + ^{(𝑦−2)(𝑦−1)}

(5−2)(5−1) 4

• 𝑥_𝑖+1 = ^(−1)(−5)

(2−1)(2−5)1 + ^(−2)(−5)

(1−2)(1−5)2 + ^(−2)(−1)

(5−2)(5−1)4 = 4

– 단, 세개의 y값이 서로 다르지 않을 때 역 2차 함수는 존재하지 않음.

Br ent

법 의

알 고

리 즘

6.5 MATLAB Function: Fzero

• Fzero 함수는 단일 방정식에서 실근을 구하도록 설계

– fzero (function, x0)

– 근을 포함하는 두 개의 가정값

• fzero (function, [x0 x1])

– (이때 x0,x1은 함수값의 부호를 서로 다르게 하는 가정값)

>> x= fzero( @(x) x^2-9, -4) x=

-3

>> x= fzero( @(x) x^2-9, 4) x=

3

>> x= fzero( @(x) x^2-9, 0) x=

-3

>> x= fzero( @(x) x^2-9, [0 4]) x=

3

>> x= fzero( @(x) x^2-9, [-4 4])

• Fzero 함수에 한 개의 초기 가정값이 전달

– 초기 가정값에서 부호 변화가 감지될 때까지 양과 음의 방향으로 점점 넓은 간격 을 취한다.

fzero 구문의 완전한 표현

[x, fx] = fzero (function, xo, options, p1, p2 , …)

optimset 함수의 구문

Options = optimset (‘par1’, val1, ‘par2’, val2, …)

display : ‘iter’로 지정되면, 모든 반복에 대한 자세한 기록 표시 tolx : x에 대한 종료 허용값을 지정하는 양수의 스칼라 값

• 예제 6.7

• 근을 구하는 문제를 optimset과 fzero로 풀어라.

– (양의 근을 초기값 0.5를 이용하여)

1 )

( x  x



f

6.6 Polynomials

• 이분법과 Newton-Raphson법은 고차 다항식의 근을 못 구함.

• 내장함수 roots

– roots 함수의 구문

• x = roots(c) x = 근을 나타내는 열벡터

c = 다항식의 계수를 나타내는 행벡터

roots의 역함수는 poly이며 근의 값이 들어가면 다항식의 계수 출력 – poly 함수의 구문

• c = poly (r) r = 근을 나타내는 열벡터

c = 다항식의 계수를 나타내는 행벡터

• 예제6.8

다항식은 세 개의 실근 0.5, -1.0, 2 ,한 쌍의 복소수 근 1±0.5i 를 가짐

>> a = [1 -3.5 2.75 2.125 -3.875 1.25];

>>polyval (a, 1) ans =

-0.2500

(x-0.5)(x+1) = x^2+0.5x-0.5

>>b = [1 .5 -.5]

b =

1.0000 0.5000 -0.5000

>>b = poly([0.5 -1]) b =

1.0000 0.5000 -0.5000

25 . 1 875

. 3 125

. 2 75

. 2 5

. 3 )

( x  x

 x

 x

 x

 x 

f

• >> [q,r] = deconv(a,b)

• q =

• 1.0000 -4.0000 5.2500 -2.5000

• r =

• 0 0 0 0 0 0

• >> x=roots(q)

• x =

• 2.0000

• 1.0000 + 0.5000i

• 1.0000 - 0.5000i

• >> a=conv(q,b)

• a =

• 1.0000 -3.5000 2.7500 2.1250 -3.8750 1.2500

25 . 1 875 . 3 125 . 2 75 . 2 5

. 3 )

( x  x

 x

 x

 x

 x  f

사용된 근 : 0.5, -1 사용x 근 : 2, 1±0.5i

• >> x=roots(a)

• x =

• 2.0000

• -1.0000

• 1.0000 + 0.5000i

• 1.0000 - 0.5000i

• 0.5000

• >> c=poly(x)

• c =

• 1.0000 -3.5000 2.7500 2.1250 -3.8750

1.2500