A brief note on Numerical Solution of Equations . Read it before a test. Try each question at the end before you open its answer.
Locating and bisecting Change of sign: a continuous f f f with f ( a ) f ( b ) < 0 f(a)f(b) < 0 f ( a ) f ( b ) < 0 has a root in ( a , b ) (a, b) ( a , b ) . Traps: a break in the graph, a touching root, two roots close together. To d d d places: test the ends of the rounding interval. Bisection width: b − a 2 n \dfrac{b - a}{2^n} 2 n b − a after n n n steps. Iteration Fixed point: g ( α ) = α g(\alpha) = \alpha g ( α ) = α ; iterate x n + 1 = g ( x n ) x_{n+1} = g(x_n) x n + 1 = g ( x n ) . Errors: e n + 1 ≈ g ′ ( α ) e n e_{n+1} \approx g'(\alpha)\,e_n e n + 1 ≈ g ′ ( α ) e n , linear speed. Rule: converges when ∣ g ′ ( α ) ∣ < 1 |g'(\alpha)| < 1 ∣ g ′ ( α ) ∣ < 1 . Shapes: staircase for g ′ > 0 g' > 0 g ′ > 0 , cobweb for g ′ < 0 g' < 0 g ′ < 0 . Newton's method Step: x n + 1 = x n − f ( x n ) f ′ ( x n ) x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)} x n + 1 = x n − f ′ ( x n ) f ( x n ) . Square root: x n + 1 = 1 2 ( x n + N x n ) x_{n+1} = \tfrac{1}{2}\left(x_n + \tfrac{N}{x_n}\right) x n + 1 = 2 1 ( x n + x n N ) . Speed: e n + 1 ≈ C e n 2 e_{n+1} \approx C e_n^2 e n + 1 ≈ C e n 2 at a simple root. Failures: flat tangents, cycles, x 3 \sqrt[3]{x} 3 x , slow at repeated roots. A worked example Find 6 \sqrt{6} 6 by Newton's method from x 0 = 2 x_0 = 2 x 0 = 2 .
First step. x 1 = 1 2 ( 2 + 3 ) = 2.5 x_1 = \tfrac{1}{2}(2 + 3) = 2.5 x 1 = 2 1 ( 2 + 3 ) = 2.5 . Second step. x 2 = 1 2 ( 2.5 + 2.4 ) = 2.45 x_2 = \tfrac{1}{2}(2.5 + 2.4) = 2.45 x 2 = 2 1 ( 2.5 + 2.4 ) = 2.45 . Check. 2.45 2 = 6.0025 2.45^2 = 6.0025 2.4 5 2 = 6.0025 , already close to 6 6 6 . Practice with new numbers
A program to try The program finds the root of x = cos x x = \cos x x = cos x in two ways, by iteration and by Newton's method, and counts the steps of each.
Read it first. Then run it. Which method needs fewer steps?
1. Change tol to 1e-14. How do the two counts change?
Mistakes to avoid A sign change across a break proves nothing. The slope at x 0 x_0 x 0 does not decide convergence; the slope at α \alpha α does. Dividing by f f f instead of f ′ f' f ′ in Newton's step. Degrees in place of radians. Check yourself Show that x 3 + x − 1 = 0 x^3 + x - 1 = 0 x 3 + x − 1 = 0 has a root in ( 0 , 1 ) (0, 1) ( 0 , 1 ) . Stuck? Show a hint Show the answerHow many bisection steps take the width of [ 0 , 1 ] [0, 1] [ 0 , 1 ] below 0.01 0.01 0.01 ? Stuck? Show a hint Show the answerDoes x n + 1 = 2 cos x n x_{n+1} = 2\cos x_n x n + 1 = 2 cos x n converge to its fixed point near 1.03 1.03 1.03 ? Stuck? Show a hint Show the answerWrite Newton's step for x 3 = 4 x^3 = 4 x 3 = 4 . Stuck? Show a hint Show the answerWhy is Newton's method slow at a double root? Stuck? Show a hint Show the answerSources OpenStax, Calculus Volume 1 , Section 4.9, Newton's Method.