Conditioning
Find r r r f ( r ) = 0 f(r) = 0 f ( r ) = 0 f f f f ~ ( x ) = f ( x ) + ϵ \tilde{f}(x) = f(x) + \epsilon f ~ ( x ) = f ( x ) + ϵ r ~ = r + δ \tilde{r} = r + \delta r ~ = r + δ δ ≈ − ϵ / f ′ ( r ) \delta \approx -\epsilon / f'(r) δ ≈ − ϵ / f ′ ( r )
κ r = ∣ f ′ ( r ) ∣ − 1 \kappa_r = |f'(r)|^{-1} κ r = ∣ f ′ ( r ) ∣ − 1 The residual is f ( r ~ ) f(\tilde{r}) f ( r ~ ) ∣ f ′ ( r ) ∣ |f'(r)| ∣ f ′ ( r ) ∣ f ( r ~ ) ≈ 0 f(\tilde{r}) \approx 0 f ( r ~ ) ≈ 0 r ~ \tilde{r} r ~ r r r
r r r f ′ ( r ) ≠ 0 f'(r) \neq 0 f ′ ( r ) = 0 m m m f ( r ) = f ′ ( r ) = ⋯ = f ( m − 1 ) ( r ) = 0 f(r) = f'(r) = \cdots = f^{(m-1)}(r) = 0 f ( r ) = f ′ ( r ) = ⋯ = f ( m − 1 ) ( r ) = 0 f ( m ) ( r ) ≠ 0 f^{(m)}(r) \neq 0 f ( m ) ( r ) = 0 κ r = ∞ \kappa_r = \infty κ r = ∞
Fixed Point Iteration
Rewrite f ( x ) = 0 f(x) = 0 f ( x ) = 0 g ( x ) = x g(x) = x g ( x ) = x g ( x ) = x − f ( x ) g(x) = x - f(x) g ( x ) = x − f ( x ) y = g ( x ) y = g(x) y = g ( x ) y = x y = x y = x x k + 1 = g ( x k ) x_{k+1} = g(x_k) x k + 1 = g ( x k ) ϵ k = x k − r \epsilon_k = x_k - r ϵ k = x k − r g ( r ) = r g(r) = r g ( r ) = r
ϵ k + 1 + r = g ( ϵ k + r ) = g ( r ) + g ′ ( r ) ϵ k + 1 2 g ′ ′ ( r ) ϵ k 2 + ⋯ ⟹ ϵ k + 1 = g ′ ( r ) ϵ k + O ( ϵ k 2 ) \epsilon_{k+1} + r = g(\epsilon_k + r) = g(r) + g'(r)\epsilon_k + \frac{1}{2}g''(r)\epsilon_k^2 + \cdots \implies \epsilon_{k+1} = g'(r)\epsilon_k + O(\epsilon_k^2) ϵ k + 1 + r = g ( ϵ k + r ) = g ( r ) + g ′ ( r ) ϵ k + 2 1 g ′′ ( r ) ϵ k 2 + ⋯ ⟹ ϵ k + 1 = g ′ ( r ) ϵ k + O ( ϵ k 2 ) So if ∣ g ′ ( r ) ∣ > 1 |g'(r)| > 1 ∣ g ′ ( r ) ∣ > 1 σ = ∣ g ′ ( r ) ∣ < 1 \sigma = |g'(r)| < 1 σ = ∣ g ′ ( r ) ∣ < 1 ∣ ϵ k ∣ ≈ C σ k |\epsilon_k| \approx C\sigma^k ∣ ϵ k ∣ ≈ C σ k log ∣ ϵ k ∣ ≈ k log σ + log C \log |\epsilon_k| \approx k \log \sigma + \log C log ∣ ϵ k ∣ ≈ k log σ + log C
lim k → ∞ ∣ x k + 1 − r ∣ ∣ x k − r ∣ = σ \lim_{k \to \infty} \frac{|x_{k+1} - r|}{|x_k - r|} = \sigma k → ∞ lim ∣ x k − r ∣ ∣ x k + 1 − r ∣ = σ i.e. linear convergence.
Newton's Method
x k + 1 = x k − f ( x k ) f ′ ( x k ) x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)} x k + 1 = x k − f ′ ( x k ) f ( x k ) With ϵ k = r − x k \epsilon_k = r - x_k ϵ k = r − x k f ( r ) = 0 f(r) = 0 f ( r ) = 0 f ′ ( r ) ≠ 0 f'(r) \neq 0 f ′ ( r ) = 0
ϵ k + 1 = ϵ k + f ( r − ϵ k ) f ′ ( r − ϵ k ) = ϵ k + f ( r ) − ϵ k f ′ ( r ) + 1 2 ϵ k 2 f ′ ′ ( r ) + O ( ϵ k 3 ) f ′ ( r ) − ϵ k f ′ ′ ( r ) + O ( ϵ k 2 ) \epsilon_{k+1} = \epsilon_k + \frac{f(r - \epsilon_k)}{f'(r - \epsilon_k)} = \epsilon_k + \frac{f(r) - \epsilon_k f'(r) + \frac{1}{2}\epsilon_k^2 f''(r) + O(\epsilon_k^3)}{f'(r) - \epsilon_k f''(r) + O(\epsilon_k^2)} ϵ k + 1 = ϵ k + f ′ ( r − ϵ k ) f ( r − ϵ k ) = ϵ k + f ′ ( r ) − ϵ k f ′′ ( r ) + O ( ϵ k 2 ) f ( r ) − ϵ k f ′ ( r ) + 2 1 ϵ k 2 f ′′ ( r ) + O ( ϵ k 3 ) = ϵ k − ϵ k [ 1 − 1 2 f ′ ′ ( r ) f ′ ( r ) ϵ k + O ( ϵ k 2 ) ] ⋅ [ 1 − f ′ ′ ( r ) f ′ ( r ) ϵ k + O ( ϵ k 2 ) ] − 1 = \epsilon_k - \epsilon_k \Big[ 1 - \frac{1}{2}\frac{f''(r)}{f'(r)}\epsilon_k + O(\epsilon_k^2) \Big] \cdot \Big[ 1 - \frac{f''(r)}{f'(r)}\epsilon_k + O(\epsilon_k^2) \Big]^{-1} = ϵ k − ϵ k [ 1 − 2 1 f ′ ( r ) f ′′ ( r ) ϵ k + O ( ϵ k 2 ) ] ⋅ [ 1 − f ′ ( r ) f ′′ ( r ) ϵ k + O ( ϵ k 2 ) ] − 1 Using ( 1 + z ) − 1 = 1 − z + O ( z 2 ) (1 + z)^{-1} = 1 - z + O(z^2) ( 1 + z ) − 1 = 1 − z + O ( z 2 ) ∣ z ∣ < 1 |z| < 1 ∣ z ∣ < 1
= ϵ k − ϵ k [ 1 − 1 2 f ′ ′ ( r ) f ′ ( r ) ϵ k + O ( ϵ k 2 ) ] [ 1 + f ′ ′ ( r ) f ′ ( r ) ϵ k + O ( ϵ k 2 ) ] = − 1 2 f ′ ′ ( r ) f ′ ( r ) ϵ k 2 + O ( ϵ k 3 ) = \epsilon_k - \epsilon_k \Big[ 1 - \frac{1}{2}\frac{f''(r)}{f'(r)}\epsilon_k + O(\epsilon_k^2) \Big] \Big[ 1 + \frac{f''(r)}{f'(r)}\epsilon_k + O(\epsilon_k^2) \Big] = -\frac{1}{2}\frac{f''(r)}{f'(r)}\epsilon_k^2 + O(\epsilon_k^3) = ϵ k − ϵ k [ 1 − 2 1 f ′ ( r ) f ′′ ( r ) ϵ k + O ( ϵ k 2 ) ] [ 1 + f ′ ( r ) f ′′ ( r ) ϵ k + O ( ϵ k 2 ) ] = − 2 1 f ′ ( r ) f ′′ ( r ) ϵ k 2 + O ( ϵ k 3 ) so the convergence is quadratic, lim k → ∞ ∣ x k + 1 − r ∣ ∣ x k − r ∣ 2 \lim_{k \to \infty} \frac{|x_{k+1} - r|}{|x_k - r|^2} lim k → ∞ ∣ x k − r ∣ 2 ∣ x k + 1 − r ∣
Secant Method
Instead of the tangent, use the secant through the last two points,
g ( x ) = f ( x k ) + f ( x k ) − f ( x k − 1 ) x k − x k − 1 ( x − x k ) g(x) = f(x_k) + \frac{f(x_k) - f(x_{k-1})}{x_k - x_{k-1}}(x - x_k) g ( x ) = f ( x k ) + x k − x k − 1 f ( x k ) − f ( x k − 1 ) ( x − x k ) and solve g ( x ) = 0 g(x) = 0 g ( x ) = 0 x k + 1 x_{k+1} x k + 1
x k + 1 = x k − f ( x k ) ( x k − x k − 1 ) f ( x k ) − f ( x k − 1 ) , k = 1 , 2 , … x_{k+1} = x_k - \frac{f(x_k)(x_k - x_{k-1})}{f(x_k) - f(x_{k-1})}, \qquad k = 1, 2, \ldots x k + 1 = x k − f ( x k ) − f ( x k − 1 ) f ( x k ) ( x k − x k − 1 ) , k = 1 , 2 , … With ϵ k = r − x k \epsilon_k = r - x_k ϵ k = r − x k ϵ k + 1 ≈ − 1 2 f ′ ′ ( r ) f ′ ( r ) ϵ k ϵ k − 1 \epsilon_{k+1} \approx -\frac{1}{2}\frac{f''(r)}{f'(r)}\epsilon_k \epsilon_{k-1} ϵ k + 1 ≈ − 2 1 f ′ ( r ) f ′′ ( r ) ϵ k ϵ k − 1 ∣ ϵ k + 1 ∣ ≈ C ∣ ϵ k ∣ a |\epsilon_{k+1}| \approx C|\epsilon_k|^a ∣ ϵ k + 1 ∣ ≈ C ∣ ϵ k ∣ a ∣ ϵ k ∣ ≈ C ∣ ϵ k − 1 ∣ a |\epsilon_k| \approx C|\epsilon_{k-1}|^a ∣ ϵ k ∣ ≈ C ∣ ϵ k − 1 ∣ a ∣ ϵ k − 1 ∣ a 2 ≈ C ∣ ϵ k − 1 ∣ a + 1 |\epsilon_{k-1}|^{a^2} \approx C|\epsilon_{k-1}|^{a+1} ∣ ϵ k − 1 ∣ a 2 ≈ C ∣ ϵ k − 1 ∣ a + 1
a 2 = a + 1 , a = 1 + 5 2 ≈ 1.62 a^2 = a + 1, \qquad a = \frac{1 + \sqrt{5}}{2} \approx 1.62 a 2 = a + 1 , a = 2 1 + 5 ≈ 1.62 the golden ratio: superlinear convergence, 1 < a < 2 1 < a < 2 1 < a < 2
Newton gets order 2 for two function evaluations (f f f f ′ f' f ′ ϵ 2 = ( ϵ 2 ) 2 \epsilon^2 = (\epsilon^{\sqrt{2}})^{\sqrt{2}} ϵ 2 = ( ϵ 2 ) 2 2 ≈ 1.41 \sqrt{2} \approx 1.41 2 ≈ 1.41 1.62 1.62 1.62