Newton's Method: An iterative algorithm for finding successively better approximations to the roots (or zeros) of a real-valued function.
- Start: Choose an initial guess \(x_0\)
- Compute: \(f(x_n)\) and \(f'(x_n)\)
- Update: Apply formula \(x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}\)
- Repeat: Until convergence or maximum iterations
To find \(\sqrt{2}\), solve \(f(x) = x^2 - 2 = 0\)
Derivative: \(f'(x) = 2x\)
Formula: \(x_{n+1} = x_n - \frac{x_n^2 - 2}{2x_n} = \frac{x_n^2 + 2}{2x_n}\)
For \(\sqrt{2}\), let \(f(x) = x^2 - 2\), so we want \(f(x) = 0\)
Derivative: \(f'(x) = 2x\)
\(x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} = x_n - \frac{x_n^2 - 2}{2x_n}\)
\(x_{n+1} = \frac{2x_n^2 - x_n^2 + 2}{2x_n} = \frac{x_n^2 + 2}{2x_n}\)
\(x_0 = 1\)
\(x_1 = \frac{1^2 + 2}{2(1)} = \frac{3}{2} = 1.5\)
\(x_1 = 1.5\)
\(x_2 = \frac{(1.5)^2 + 2}{2(1.5)} = \frac{2.25 + 2}{3} = \frac{4.25}{3} = 1.4167\)
\(x_2 = 1.4167\)
\(x_3 = \frac{(1.4167)^2 + 2}{2(1.4167)} = \frac{2.0069 + 2}{2.8334} = \frac{4.0069}{2.8334} = 1.4142\)
\(x_0 = 1.0000\), \(x_1 = 1.5000\), \(x_2 = 1.4167\), \(x_3 = 1.4142\)
True value: \(\sqrt{2} = 1.41421356...\)
• Newton's Formula: \(x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}\)
• Convergence: Quadratic convergence near the root
• Derivative Calculation: Proper differentiation is crucial
To find \(\sqrt[3]{5}\), solve \(f(x) = x^3 - 5 = 0\)
Derivative: \(f'(x) = 3x^2\)
For \(\sqrt[3]{5}\), let \(f(x) = x^3 - 5\), so we want \(f(x) = 0\)
Derivative: \(f'(x) = 3x^2\)
\(x_{n+1} = x_n - \frac{x_n^3 - 5}{3x_n^2} = \frac{3x_n^3 - x_n^3 + 5}{3x_n^2} = \frac{2x_n^3 + 5}{3x_n^2}\)
\(x_0 = 2\)
\(x_1 = \frac{2(2)^3 + 5}{3(2)^2} = \frac{16 + 5}{12} = \frac{21}{12} = 1.75\)
\(x_1 = 1.75\)
\(x_2 = \frac{2(1.75)^3 + 5}{3(1.75)^2} = \frac{2(5.3594) + 5}{3(3.0625)} = \frac{10.7188 + 5}{9.1875} = \frac{15.7188}{9.1875} = 1.710\)
\(x_0 = 2.000\), \(x_1 = 1.750\), \(x_2 = 1.710\)
True value: \(\sqrt[3]{5} = 1.70997594...\)
• Power Rule: \(\frac{d}{dx}(x^n) = nx^{n-1}\)
• Cube Root Equation: Set \(x^3 - a = 0\) for \(\sqrt[3]{a}\)
• Algebraic Simplification: Combine terms carefully
Solve \(f(x) = \cos(x) - x = 0\)
Derivative: \(f'(x) = -\sin(x) - 1\)
We want to solve \(\cos(x) = x\), so \(f(x) = \cos(x) - x\)
Derivative: \(f'(x) = -\sin(x) - 1\)
\(x_{n+1} = x_n - \frac{\cos(x_n) - x_n}{-\sin(x_n) - 1} = x_n + \frac{\cos(x_n) - x_n}{\sin(x_n) + 1}\)
\(x_0 = 0.7\)
\(f(0.7) = \cos(0.7) - 0.7 = 0.7648 - 0.7 = 0.0648\)
\(f'(0.7) = -\sin(0.7) - 1 = -0.6442 - 1 = -1.6442\)
\(x_1 = 0.7 - \frac{0.0648}{-1.6442} = 0.7 + 0.0394 = 0.7394\)
\(x_1 = 0.7394\)
\(f(0.7394) = \cos(0.7394) - 0.7394 = 0.7391 - 0.7394 = -0.0003\)
\(f'(0.7394) = -\sin(0.7394) - 1 = -0.6736 - 1 = -1.6736\)
\(x_2 = 0.7394 - \frac{-0.0003}{-1.6736} = 0.7394 - 0.0002 = 0.7392\)
\(x_0 = 0.7000\), \(x_1 = 0.7394\), \(x_2 = 0.7392\)
This converges to the Dottie number ≈ 0.739085
• Trigonometric Derivatives: \(\frac{d}{dx}[\cos(x)] = -\sin(x)\)
• Numerical Precision: Track significant digits carefully
• Convergence Check: Monitor differences between iterations
Root/Zeros: Values where \(f(x) = 0\)
Tangent Line: Line touching curve at one point with slope \(f'(x)\)
Convergence: Sequence approaches exact solution
Quadratic Convergence: Error squared at each step when \(f'(root) \neq 0\)
Linear Convergence: When derivative is zero at root
• Continuity: \(f\) and \(f'\) must be continuous near root
• Non-zero derivative: \(f'(r) \neq 0\) at the root
• Initial proximity: Initial guess must be sufficiently close
• Function behavior: Function should be well-behaved
Rewrite as \(f(x) = x \ln(x) - 1 = 0\)
Using product rule: \(f'(x) = \ln(x) + 1\)
\(x \ln(x) = 1\) becomes \(f(x) = x \ln(x) - 1 = 0\)
Derivative: \(f'(x) = \ln(x) + x \cdot \frac{1}{x} = \ln(x) + 1\)
\(x_{n+1} = x_n - \frac{x_n \ln(x_n) - 1}{\ln(x_n) + 1}\)
\(x_0 = 2\)
\(f(2) = 2 \ln(2) - 1 = 2(0.6931) - 1 = 1.3863 - 1 = 0.3863\)
\(f'(2) = \ln(2) + 1 = 0.6931 + 1 = 1.6931\)
\(x_1 = 2 - \frac{0.3863}{1.6931} = 2 - 0.2282 = 1.7718\)
\(x_1 = 1.7718\)
\(f(1.7718) = 1.7718 \ln(1.7718) - 1 = 1.7718(0.5722) - 1 = 1.0139 - 1 = 0.0139\)
\(f'(1.7718) = \ln(1.7718) + 1 = 0.5722 + 1 = 1.5722\)
\(x_2 = 1.7718 - \frac{0.0139}{1.5722} = 1.7718 - 0.0088 = 1.7630\)
\(x_0 = 2.000\), \(x_1 = 1.772\), \(x_2 = 1.763\)
The exact solution is approximately 1.7632228343518967
• Product Rule: \(\frac{d}{dx}[uv] = u'v + uv'\)
• Logarithmic Derivative: \(\frac{d}{dx}[\ln(x)] = \frac{1}{x}\)
• Algebraic Manipulation: Simplify complex expressions
\(f(x) = x^{1/3}\), so we want \(f(x) = 0\) which means \(x = 0\)
Derivative: \(f'(x) = \frac{1}{3}x^{-2/3} = \frac{1}{3x^{2/3}}\)
\(f(x) = x^{1/3}\) has root at \(x = 0\)
Derivative: \(f'(x) = \frac{1}{3}x^{-2/3} = \frac{1}{3x^{2/3}}\)
\(x_{n+1} = x_n - \frac{x_n^{1/3}}{\frac{1}{3x_n^{2/3}}} = x_n - 3x_n^{1/3} \cdot x_n^{2/3} = x_n - 3x_n = -2x_n\)
\(x_0 = 1\)
\(x_1 = -2(1) = -2\)
\(x_1 = -2\)
\(x_2 = -2(-2) = 4\)
Each iteration: \(x_{n+1} = -2x_n\), so sequence is: \(1, -2, 4, -8, 16, ...\)
The method diverges exponentially!
The method fails because \(f'(0) = \infty\) (not defined), violating convergence conditions.
The function \(x^{1/3}\) is not differentiable at its root.
• Zero derivative: \(f'(r) = 0\) at root
• Undefined derivative: Function not differentiable at root
• Poor initial guess: Too far from actual root
• Oscillatory behavior: Function changes concavity rapidly
Newton's Method: Iterative algorithm for finding roots of \(f(x) = 0\)
Root: Value \(r\) where \(f(r) = 0\)
Tangent Line: Linear approximation of function at current point
- Problem setup: Write equation in form \(f(x) = 0\)
- Derivative calculation: Find \(f'(x)\) analytically
- Initial guess: Choose \(x_0\) reasonably close to expected root
- Iteration loop: Apply Newton's formula repeatedly
- Convergence check: Stop when desired accuracy reached
• Newton's formula: \(x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}\)
• Linearization: \(L(x) = f(a) + f'(a)(x-a)\)
• Error relation: \(|x_{n+1} - r| \approx C|x_n - r|^2\)
• Convergence condition: \(|f'(r)| > 0\) and \(x_0\) close enough
- First tangent line at \(x_0 = 2\)
- Second tangent line at \(x_1 = 1.5\)
- Third tangent line at \(x_2 = 1.4167\)
Geometric interpretation: Each iteration follows the tangent line to the x-axis.
- The tangent line at \((x_n, f(x_n))\) has slope \(f'(x_n)\)
- It intersects the x-axis at \(x_{n+1}\)
- This provides increasingly accurate approximations to the root