๋ดํด๋ฒ์ด๋?
๋ดํด๋ฒ(๋ดํด-๋ฉ์จ๋ฒ์ด๋ผ๊ณ ๋ ํฉ๋๋ค)์ ๋ฐฉ์ ์์ ์์น์ ๊ทผ, ์ฆ \(f(x) = 0\)์ด ๋๋ \(x\) ๊ฐ์ ์ฐพ๋ ๊ฐ์ฅ ๋น ๋ฅด๊ณ ๋๋ฆฌ ์ฐ์ด๋ ๋ฐฉ๋ฒ ์ค ํ๋์ ๋๋ค. ์ด๊ธฐ ์ถ์ ๊ฐ์์ ์ถ๋ฐํด ๊ณก์ ์ ์ ์ ์ ๊ทธ๋ฆฌ๊ณ , ๊ทธ ์ ์ ์ด x์ถ๊ณผ ๋ง๋๋ ์ง์ ์ ๋ค์ ๋จ๊ณ์ ๋ ์ ํํ ์ถ์ ๊ฐ์ผ๋ก ์ผ๋ ๊ณผ์ ์ ๋ฐ๋ณตํฉ๋๋ค. ์กฐ๊ฑด์ด ์ ๋ง์ผ๋ฉด 2์ฐจ ์๋ ด(quadratic convergence)์ ๋ณด์ฌ, ๋จ๊ณ๋ง๋ค ์ ํํ ์๋ฆฟ์๊ฐ ๋๋ต ๋ ๋ฐฐ์ฉ ๋์ด๋ฉ๋๋ค.
๊ณ์ฐ๊ธฐ ์ฌ์ฉ๋ฒ
๋ณ์๋ก \(x\)๋ฅผ ์ฌ์ฉํ์ฌ ํจ์ \(f(x)\)๋ฅผ ์ ๋ ฅํ์ธ์. ์ด ๊ณ์ฐ๊ธฐ๋ ์๋ ๋ฏธ๋ถ์ ์ง์ํ์ง ์์ผ๋ฏ๋ก, ํด์์ ์ผ๋ก ์ง์ ๊ตฌํ ๋ํจ์ \(f'(x)\)๋ ํจ๊ป ์ ๋ ฅํด์ผ ํฉ๋๋ค. ์ด๊ธฐ ์ถ์ ๊ฐ \(x_0\)์ ์ต๋ ๋ฐ๋ณต ํ์๋ฅผ ์ ํ๋ฉด, ๊ณ์ฐ๊ธฐ๋ ๊ทผ์ฌ ๊ทผ, ๊ทธ ๊ทผ์์์ \(f\) ๊ฐ(0์ ๊ฐ๊น์ธ์๋ก ์๋ ด์ด ์ ๋ ๊ฒ์ ๋๋ค), ์ฌ์ฉ๋ ๋ฐ๋ณต ํ์, ๊ทธ๋ฆฌ๊ณ ๋จ๊ณ๋ณ ๊ณผ์ ์ ๋ณด์ฌ์ฃผ๋ ํ๋ฅผ ๋๋ ค์ค๋๋ค. ์ง์ํ๋ ๋ฌธ๋ฒ: ๊ฑฐ๋ญ์ ๊ณฑ์ + - * / ^, ๊ดํธ, ๊ทธ๋ฆฌ๊ณ sin, cos, tan, asin, acos, atan, exp, ln, log, sqrt, abs ํจ์์ ์์ pi, e์ ๋๋ค. ์ผ๊ฐํจ์๋ ๋ผ๋์ ๋จ์๋ฅผ ์ฌ์ฉํฉ๋๋ค.
๊ณต์ ํ์ด
๊ฐฑ์ ๊ท์น์ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
$$x_{n+1} = x_{n} - \frac{f(x_{n})}{f'(x_{n})}$$๋งค ๋ฐ๋ณต๋ง๋ค ํ์ฌ ์ง์ ์์ ํจ์ ๊ฐ๊ณผ ๊ธฐ์ธ๊ธฐ๋ฅผ ๊ณ์ฐํ๊ณ , ์ ์ ์ด x์ถ๊ณผ ๋ง๋๋ ์ง์ ์ชฝ์ผ๋ก ํ ๊ฑธ์ ์ด๋ํฉ๋๋ค. ์ด๋ ๋จ๊ณ์์๋ ๋ํจ์๊ฐ 0์ด๋ฉด ์ ์ ์ด ์ํ์ด ๋์ด, 0์ผ๋ก ๋๋๋ ์ค๋ฅ๊ฐ ๋ฐ์ํ๋ฉฐ ๋ฐฉ๋ฒ์ด ์คํจํฉ๋๋ค.
ํ์ด ์์
\(f(x) = x - \cos(x)\), ๋ํจ์ \(f'(x) = 1 + \sin(x)\), \(x_0 = 1\)์ ์ดํด๋ด ์๋ค. 1๋จ๊ณ์์ ๋ค์์ด ๋์ต๋๋ค.
$$x_1 = 1 - \frac{1 - \cos 1}{1 + \sin 1} = 0.75034$$2๋จ๊ณ์์๋ \(0.73912\), 3๋จ๊ณ์์๋ \(0.73909\)๊ฐ ๋๋ฉฐ, ๋ช ๋ฒ์ ๋ฐ๋ณต ์์ \(x = 0.7390851332151607\)๋ก ์์ ํ๋ฉ๋๋ค. ์ด๋ \(x = \cos x\)๋ฅผ ๋ง์กฑํ๋ ์ ๋ช ํ "๋ํฐ ์(Dottie number)"์ ๋๋ค. ์ด ์ง์ ์์ \(f(x)\)๋ ์ฌ์ค์ 0์ ๋๋ค.
์์ฃผ ๋ฌป๋ ์ง๋ฌธ
์ ๋ํจ์๋ฅผ ์ง์ ์ ๋ ฅํด์ผ ํ๋์? ์ด ๊ณ์ฐ๊ธฐ๋ ์์์ ๊ณ์ฐํ ์๋ ์์ง๋ง ๊ธฐํธ ๋ฏธ๋ถ(symbolic differentiation)์ ํ์ง ๋ชปํฉ๋๋ค. ๊ทธ๋์ \(f'(x)\)๋ฅผ ์ง์ ์ ๋ ฅํด์ผ ํฉ๋๋ค. ๋ํจ์๊ฐ ํ๋ฆฌ๋ฉด ์๋ชป๋ ๊ทผ์ด ๋์ค๊ฑฐ๋ ๋ฐ์ฐํ ์ ์์ต๋๋ค.
์ ์๋ ดํ์ง ์๋์? ๋ดํด๋ฒ์ ์ด๊ธฐ ์ถ์ ๊ฐ์ด ์ข์ง ์๊ฑฐ๋, ๋ณ๊ณก์ ๊ทผ์ฒ์ด๊ฑฐ๋, ์ค๊ทผ ์์ฒด๊ฐ ์กด์ฌํ์ง ์์ ๋ ๋ฐ์ฐํ๊ฑฐ๋ ์ง๋ํ ์ ์์ต๋๋ค. \(x_0\)๋ฅผ ๋ฐ๊พธ๊ฑฐ๋ ๋ฐ๋ณต ํ์ ํ๋๋ฅผ ๋๋ ค ๋ณด์ธ์.
๊ทผ์ด ์ฌ๋ฌ ๊ฐ์ผ ๋ ์ด๋ค ๊ทผ์ด ๋์ค๋์? ์ฐพ์์ง๋ ๊ทผ์ ์ด๊ธฐ ์ถ์ ๊ฐ \(x_0\)์ ๋ฐ๋ผ ๋ฌ๋ผ์ง๋๋ค. ์ํ๋ ๊ทผ์ ๊ฐ๊น์ด ๊ฐ์ ๊ณจ๋ผ ์ ๋ ฅํ์ธ์.