04-10 - Newton's Method
Phase: 4 | Subject: 04-10 Prerequisites: 04-08-optimization.md (derivatives, finding roots) Next subject: 05-01-antiderivatives.md
Learning Objectives
By the end of this subject, you will be able to:
- Understand Newton's method as an iterative root-finding algorithm
- Apply the iteration formula
- Choose appropriate initial guesses
- Analyse convergence and divergence
Core Content
What is Newton's Method?
Newton's method (also called Newton-Raphson) is an iterative algorithm for finding approximate roots of equations f(x) = 0.
Idea: Start with a guess x₀. Draw the tangent at (x₀, f(x₀)). Where the tangent hits the x-axis is a better guess x₁. Repeat.
Formula:
$x_{n+1} = x_n - f(x_n) / f'(x_n)
$
⚠️ THIS IS CRITICAL — Newton's method is used constantly in numerical computing: training neural networks (it's the idea behind second-order optimisers), solving equations in physics engines, and finding maximum likelihood estimates in statistics. The concept of iterative improvement via local linear approximation also generalises to Newton's method in higher dimensions.
The Algorithm
- Choose initial guess x₀
- Compute x₁ = x₀ - f(x₀)/f'(x₀)
- Compute x₂ = x₁ - f(x₁)/f'(x₁)
- Repeat until |x_{n+1} - x_n| < tolerance
Choosing Initial Guess
- Pick x₀ near the root (check graph of f(x))
- Avoid points where f'(x) = 0 (tangent is horizontal, division by zero)
- If f(x₀) and f''(x₀) have the same sign, Newton's converges
Convergence
Newton's method converges QUADRATICALLY when it works — the number of correct digits roughly doubles each iteration.
Divergence can occur if: - Initial guess is far from root - f'(x) is very small near root - The iteration enters a cycle
Key Terms
- 04 10 Newtons Method
- Choosing Initial Guess
- Convergence
- Correct: A)
- Correct: B)
- Correct: C)
- Example 1: Find √2
- Example 2: Solve cos(x) = x
- Example 3: Cube root
- The Algorithm
- What is Newton's Method?
Worked Examples
Example 1: Find √2
Solve x² - 2 = 0. f(x) = x² - 2, f'(x) = 2x.
Start with x₀ = 1: x₁ = 1 - (1 - 2)/2 = 1 + 0.5 = 1.5 x₂ = 1.5 - (2.25 - 2)/3 = 1.5 - 0.25/3 = 1.5 - 0.0833 = 1.4167 x₃ = 1.4167 - (2.0069 - 2)/2.8334 ≈ 1.4167 - 0.0024 = 1.4142
√2 ≈ 1.4142. Converged in 3 iterations!
Example 2: Solve cos(x) = x
f(x) = cos(x) - x, f'(x) = -sin(x) - 1.
Start with x₀ = 1: x₁ = 1 - (cos(1) - 1)/(-sin(1) - 1) = 1 - (0.5403 - 1)/(-0.8415 - 1) = 1 - (-0.4597)/(-1.8415) = 1 - 0.2496 = 0.7504
x₂ = 0.7504 - (cos(0.7504) - 0.7504)/(-sin(0.7504) - 1) ≈ 0.7504 - (0.7317 - 0.7504)/(-0.6816 - 1) ≈ 0.7504 - (-0.0187)/(-1.6816) ≈ 0.7504 - 0.0111 = 0.7393
The root is approximately 0.7391 (the Dottie number).
Example 3: Cube root
Solve x³ - 7 = 0 with x₀ = 2 (find ∛7).
f(x) = x³ - 7, f'(x) = 3x². x₁ = 2 - (8 - 7)/12 = 2 - 1/12 ≈ 1.9167 x₂ = 1.9167 - (7.0417 - 7)/(3 · 3.6736) ≈ 1.9167 - 0.00379 ≈ 1.9129
∛7 ≈ 1.9129. Actual: 1.9129... Correct to 4 decimal places in 2 iterations.
Quiz
Q1: What does the concept of Choosing Initial Guess primarily refer to in this subject?
A) A computational error related to Choosing Initial Guess B) A historical anecdote about Choosing Initial Guess C) A visual representation of Choosing Initial Guess D) The definition and application of Choosing Initial Guess
Correct: D)
- If you chose A: This is incorrect. Choosing Initial Guess is defined as: the definition and application of choosing initial guess. The other options describe different aspects that are not the primary focus.
- If you chose B: This is incorrect. Choosing Initial Guess is defined as: the definition and application of choosing initial guess. The other options describe different aspects that are not the primary focus.
- If you chose C: This is incorrect. Choosing Initial Guess is defined as: the definition and application of choosing initial guess. The other options describe different aspects that are not the primary focus.
- If you chose D: Choosing Initial Guess is defined as: the definition and application of choosing initial guess. The other options describe different aspects that are not the primary focus. Correct!
Q2: What is the primary purpose of Convergence?
A) It replaces all other methods in this domain B) It is primarily a historical notation system C) It is used to convergence in mathematical analysis D) It is used only in advanced research contexts
Correct: C)
- If you chose A: This is incorrect. Convergence serves the purpose described in the correct answer. The other options misrepresent its role.
- If you chose B: This is incorrect. Convergence serves the purpose described in the correct answer. The other options misrepresent its role.
- If you chose C: Convergence serves the purpose described in the correct answer. The other options misrepresent its role. Correct!
- If you chose D: This is incorrect. Convergence serves the purpose described in the correct answer. The other options misrepresent its role.
Q3: Which statement about The Algorithm is TRUE?
A) The Algorithm is not related to this subject B) The Algorithm is mentioned only as a historical footnote C) The Algorithm is a fundamental concept covered in this subject D) The Algorithm is an advanced topic beyond this subject's scope
Correct: C)
- If you chose A: This is incorrect. The Algorithm is a fundamental concept covered in this subject. This subject covers The Algorithm as part of its core content.
- If you chose B: This is incorrect. The Algorithm is a fundamental concept covered in this subject. This subject covers The Algorithm as part of its core content.
- If you chose C: The Algorithm is a fundamental concept covered in this subject. This subject covers The Algorithm as part of its core content. Correct!
- If you chose D: This is incorrect. The Algorithm is a fundamental concept covered in this subject. This subject covers The Algorithm as part of its core content.
Q4: Based on the worked examples in this subject, what is the correct result?
A) A different result from a common mistake B) The inverse of the correct answer C) An unrelated numerical value D) 2.25 - (5.0625-5)/4.
Correct: D)
- If you chose A: This is incorrect. The worked examples show that the result is 2.25 - (5.0625-5)/4.. The other options represent common errors.
- If you chose B: This is incorrect. The worked examples show that the result is 2.25 - (5.0625-5)/4.. The other options represent common errors.
- If you chose C: This is incorrect. The worked examples show that the result is 2.25 - (5.0625-5)/4.. The other options represent common errors.
- If you chose D: The worked examples show that the result is 2.25 - (5.0625-5)/4.. The other options represent common errors. Correct!
Q5: How are The Algorithm and What Is Newton'S Method? related?
A) The Algorithm is a special case of What Is Newton'S Method? B) The Algorithm and What Is Newton'S Method? are closely related concepts C) The Algorithm is the inverse of What Is Newton'S Method? D) The Algorithm and What Is Newton'S Method? are completely unrelated topics
Correct: B)
- If you chose A: This is incorrect. Both The Algorithm and What Is Newton'S Method? are covered in this subject as interconnected topics.
- If you chose B: Both The Algorithm and What Is Newton'S Method? are covered in this subject as interconnected topics. Correct!
- If you chose C: This is incorrect. Both The Algorithm and What Is Newton'S Method? are covered in this subject as interconnected topics.
- If you chose D: This is incorrect. Both The Algorithm and What Is Newton'S Method? are covered in this subject as interconnected topics.
Q6: What is a common pitfall when working with Example 1: Find √2?
A) Example 1: Find √2 is always computed the same way in all contexts B) The main error with Example 1: Find √2 is using it when it is not needed C) Example 1: Find √2 has no common misconceptions D) A common mistake is confusing Example 1: Find √2 with a similar concept
Correct: D)
- If you chose A: This is incorrect. Students often confuse Example 1: Find √2 with similar-sounding or related concepts. Pay attention to the precise definitions.
- If you chose B: This is incorrect. Students often confuse Example 1: Find √2 with similar-sounding or related concepts. Pay attention to the precise definitions.
- If you chose C: This is incorrect. Students often confuse Example 1: Find √2 with similar-sounding or related concepts. Pay attention to the precise definitions.
- If you chose D: Students often confuse Example 1: Find √2 with similar-sounding or related concepts. Pay attention to the precise definitions. Correct!
Q7: When should you apply Example 2: Solve Cos(X) = X?
A) Avoid Example 2: Solve Cos(X) = X unless explicitly instructed B) Apply Example 2: Solve Cos(X) = X to solve problems in this subject's domain C) Example 2: Solve Cos(X) = X is not practically useful D) Use Example 2: Solve Cos(X) = X only in pure mathematics contexts
Correct: B)
- If you chose A: This is incorrect. Example 2: Solve Cos(X) = X is a practical tool used throughout this subject to solve relevant problems.
- If you chose B: Example 2: Solve Cos(X) = X is a practical tool used throughout this subject to solve relevant problems. Correct!
- If you chose C: This is incorrect. Example 2: Solve Cos(X) = X is a practical tool used throughout this subject to solve relevant problems.
- If you chose D: This is incorrect. Example 2: Solve Cos(X) = X is a practical tool used throughout this subject to solve relevant problems.
Practice Problems
-
Use Newton's method to find √5 (start with x₀ = 2) Answer: f(x) = x² - 5, f'(x) = 2x. x₁ = 2 - (4-5)/4 = 2.25. x₂ = 2.25 - (5.0625-5)/4.5 ≈ 2.2361.
-
Solve x³ - 2 = 0 with x₀ = 1 Answer: f(x) = x³ - 2, f'(x) = 3x². x₁ = 1 - (1-2)/3 = 1.333. x₂ = 1.333 - (2.370-2)/5.333 ≈ 1.263.
-
Why might Newton's method fail for f(x) = x³ - x with x₀ = 1/√3? Answer: f'(x) = 3x² - 1. At x₀ = 1/√3: f'(1/√3) = 1 - 1 = 0. Newton's formula divides by f'(x₀) = 0, causing failure. The tangent is horizontal at this point.
-
Use Newton's method with x₀ = 1 to find a root of f(x) = x³ + x - 1. Answer: f'(x) = 3x² + 1. x₁ = 1 - (1 + 1 - 1)/(3 + 1) = 1 - 1/4 = 0.75. x₂ = 0.75 - (0.4219 + 0.75 - 1)/(1.6875 + 1) = 0.75 - 0.1719/2.6875 ≈ 0.6860.
-
Explain why Newton's method with x₀ = 0 for f(x) = x^(1/3) fails to converge. Answer: At x = 0, f'(0) is undefined (vertical tangent). Even starting nearby, the derivative is very large, causing the iteration to overshoot wildly. Newton's method requires f'(x₀) ≠ 0 and preferably moderate slope.
Summary
Key takeaways:
- Newton's method: x_{n+1} = x_n - f(x_n)/f'(x_n)
- Iterative: each step uses tangent line to improve guess
- Quadratic convergence when it works
- Choose x₀ near the root, avoid f'(x) = 0
Pitfalls
- Choosing an initial guess where f'(x₀) = 0. The formula divides by f'(x_n), so a horizontal tangent at the starting point immediately breaks the method. Always check f'(x₀) ≠ 0 before iterating.
- Expecting convergence from a poor initial guess. Newton's method converges quadratically when close to the root, but can diverge wildly if x₀ is too far away. Sketch the function or try a few nearby guesses.
- Confusing the sign in the iteration formula. It's x_{n+1} = x_n - f(x_n)/f'(x_n), NOT x_n + f(x_n)/f'(x_n). The minus sign moves the guess toward the x-axis intercept of the tangent line; a plus sign moves away from it.
- Not recognising cyclic or divergent behaviour. If iterates bounce between values or grow without bound, Newton's has failed. Try a better initial guess or a different method.
- Applying Newton's method when an exact solution exists. For equations like x² - 4 = 0, factoring gives x = ±2 directly. Newton's method is for equations that cannot be solved algebraically — don't use it unnecessarily.
Next Steps
Next up: 05-01-antiderivatives.md