IMG_0155.PNG

# Lecture 18: October 26, 2023 ## Topics ### 1. Newton's Method * Example for solving $x^2 = c$ * General Case * When does it work? * When does it fail? * Basin of Attraction ### 2. Solving $f(x) = 0$ #### Newton's method Want to solve $f(x) = 0$. Start with a guess $x_0$. T...

# Lecture 18: October 26, 2023 ## Topics ### 1. Newton's Method * Example for solving $x^2 = c$ * General Case * When does it work? * When does it fail? * Basin of Attraction ### 2. Solving $f(x) = 0$ #### Newton's method Want to solve $f(x) = 0$. Start with a guess $x_0$. Take the tangent line at $x_0$: $y - f(x_0) = f'(x_0)(x - x_0)$ $y = f'(x_0)(x - x_0) + f(x_0)$ Find where the tangent line crosses the x-axis, i.e., when $y=0$ $0 = f'(x_0)(x - x_0) + f(x_0)$ $-f(x_0) = f'(x_0)(x - x_0)$ $-\frac{f(x_0)}{f'(x_0)} = x - x_0$ $x = x_0 - \frac{f(x_0)}{f'(x_0)}$ Let $x_1 = x$, then $x_1 = x_0 - \frac{f(x_0)}{f'(x_0)}$ In general: $x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$ * Keep iterating until $|x_{n+1} - x_n|$ is small ### Example: Solve $x^2 = c$, i.e., solve $f(x) = x^2 - c = 0$ $f'(x) = 2x$ $x_{n+1} = x_n - \frac{x_n^2 - c}{2x_n} = x_n - \frac{x_n}{2} + \frac{c}{2x_n} = \frac{x_n}{2} + \frac{c}{2x_n} = \frac{1}{2}(x_n + \frac{c}{x_n})$ $x_{n+1} = \frac{1}{2}(x_n + \frac{c}{x_n})$ e.g., $c = 2, x_0 = 1$ $x_1 = \frac{1}{2}(1 + \frac{2}{1}) = \frac{3}{2} = 1.5$ $x_2 = \frac{1}{2}(\frac{3}{2} + \frac{2}{\frac{3}{2}}) = \frac{1}{2}(\frac{3}{2} + \frac{4}{3}) = \frac{1}{2}(\frac{9 + 8}{6}) = \frac{17}{12} \approx 1.4167$ $x_3 = \frac{1}{2}(\frac{17}{12} + \frac{2}{\frac{17}{12}}) = \frac{1}{2}(\frac{17}{12} + \frac{24}{17}) = \frac{1}{2}(\frac{289 + 288}{204}) = \frac{577}{408} \approx 1.4142$ $\sqrt{2} \approx 1.4142$ ### When does Newton's method work? * If you have a good initial guess, it works really well. * It often doubles the number of digits each time. * There are good theorems which say that it converges quickly if $|x_0 - x^*|$ is small enough, where $x^*$ is the solution. ### When can Newton's method Fail? e.g. $f(x) = x^{1/3}$ $f'(x) = \frac{1}{3}x^{-2/3}$ $x_{n+1} = x_n - \frac{x_n^{1/3}}{\frac{1}{3}x_n^{-2/3}} = x_n - 3x_n = -2x_n$ So $x_{n+1} = -2x_n$ This will not converge unless $x_0 = 0$. ### Basin of Attraction Consider $f(z) = z^3 - 1 = 0, z \in \mathbb{C}$ The solutions are $z = 1, e^{2\pi i/3}, e^{4\pi i/3}$ If we use Newton's method, the initial guess $z_0$ will determine which of the three solutions we converge to. The set of initial guesses that converge to a particular solution is called the basin of attraction for that solution.