Lecture 9: Hermite interpolation availableAssignment 3 availableLecture 8 onlineLecture 7 onlineSchedule now available in "Admin"Problem class exercises now onlineLecture 6 onlineQuiz 1 solutions onlineLectures 2-3 exercises have solutions!Lecture 1 exercises have solutions!
Lecture 5: Chapter 2: Solving nonlinear equations in 1d II
Warning
These lecture notes are mainly a record of what we discussed in class. They should not be used as a replacement for attending lectures or reading books. Please let me know if you find any errors or have any questions about the material.
TipHypothesis
You can use the Hypothesis commenting system available on the right side panel (you can login with your U/Google account). This allows you annotate the notes (private) and leave comments or reply to other people’s comments (public).
Note
I encourage you to download the lecture notes and play around with the Julia code.
This chapter will be mainly based on Chapter 1 of An Introduction to Numerical Analysis by Süli and Mayers (2003). These notes are mainly a record of what we discussed and are not a substitute for attending the lectures and reading books! If anything is unclear/wrong, let me know and I will update the notes.
Considered the simple iteration \(x_{n+1} = g(x_n)\),
Lemma: if simple iteration converges, then it converges to a fixed point,
Example: \(g(x) = \log(2x+1)\) on \([1,2]\) and saw that the simple iteration converged to \(\xi \approx 1.26\),
Example: \(h(x) = \frac{e^x-1}{2}\) converged to \(0\),
We saw (numerically) that \(x_{n+1} = g(x_n)\) converges linearly,
Defined: contraction; showed it \(|g'| \leq L < 1\) then \(g\) is a contraction,
Contraction mapping theorem: if \(g: [a,b]\to[a,b]\) is a contraction then there exists a unique fixed point \(\xi = g(\xi) \in [a,b]\). Moreover, the iteration \(x_{n+1} = g(x_n)\) converges to \(\xi\) at least linearly with asymptotic error constant \(\mu := |g'(\xi)|\).
We showed that \(g(x) = \log(2x+1)\) is a contraction with constant \(L=\tfrac23\).
Exercise 5.1
Suppose \(g : [a,b] \to [a,b]\) is a contraction with constant \(L < 1\) and consider the simple iteration \(x_{n+1} = g(x_n)\). Let \(\xi \in [a,b]\) be the unique fixed point of \(g\) in \([a,b]\).
Show that \(|x_1 - \xi| \leq \frac1{1-L} |x_1 - x_2|\),
Hence, write down a lower bound on the number of iterations \(n\) to ensure \(|x_{n+1} - \xi|\leq \varepsilon\).
Recall that \(|x_{n+1} - \xi| \leq L |x_{n} - \xi|\). In particular, we have \(|x_1 - \xi| \leq |x_1 - x_2| + |x_2 - \xi| \leq |x_1 - x_2| + L|x_1-\xi|\) and thus \(|x_1 - \xi| \leq \frac1{1-L} |x_1 - x_2|\). As a result, we have
\[\begin{align}
n \geq \frac{ \log \frac{|x_1-x_2|}{\epsilon(1-L)} }{\log\frac1L}.
\end{align}\]
This gives an upper bound on the number of iterations needed in order to be within some fixed tolerance.
Let’s back to the function \(g(x) = \log(2x+1)\). For an error of \(\epsilon = 10^{-10}\), we require around \(54\) iterations. Actually, \(40\) will do (but we have an upper bound):
Definition 5.1\(\xi\) is a stable fixed point of \(g\) if the iteration \(x_{n+1} = g(x_n)\) converges to \(\xi\) for all \(x_1\) sufficiently close to \(\xi\). \(\xi\) is an unstable fixed point of \(g\) if for all \(\delta > 0\) there exists \(x_1 \in [\xi-\delta, \xi+\delta]\) for which \(x_{n+1} = g(x_n)\) does not converge to \(\xi\).
Example 5.1 We have seen that \(\xi = 1.26...\) is a stable fixed point of \(g(x) = \log( 2x + 1 )\) and we saw (numerically) that \(\xi \approx 1.26...\) is an unstable fixed point of \(h(x) = \frac{e^x-1}{2}\).
Theorem 5.1 Suppose \(h'\) is continuous with \(|h'(x)| > L > 1\) for all \(x \in I\) where \(I\) is an interval containing \(\xi = h(\xi)\). For \(x_{1}\in I \setminus \{\xi\}\), define \(x_{n+1} = h(x_n)\). Then, there exists \(N\) such that \(x_N \not\in I\).
Proof. Let \(I = [\xi-\delta,\xi+\delta]\) be such that \(|h'| > L\) on \(I\). If \(x_n \in I\) then there exists \(\eta \in I\) such that
Similarly, if \(x_{n+1} \in I\), then \(|x_{n+2} - \xi| > L^2|x_{n} - \xi|\). Since \(L> 1\) (and so \(L^n\to\infty\) as \(n\to\infty\)), there exists \(N\) such that \(x_{n+N} \not\in I\).
If one can additionally prove that no \(x\not\in I\) maps to \(\xi\), then the sequence \((x_n)\) does not converge to \(\xi\).
Example 5.2\(\xi = 1.26...\) is an unstable fixed point of \(h(x) = \frac{e^x -1}{2}\). In fact, for \(x_1 > \xi\), \(x_{n+1}= h(x_n)\) diverges to infinity.
\(\zeta = 0\) is a stable fixed point of \(h\). For \(x_1 < \xi\), \(x_{n+1}= h(x_n)\) converges to \(0\).
5.2 Relaxation
Recall that we have \(f:[a,b]\to\mathbb R\) and we want to find roots \(\xi\) (i.e. such that \(f(\xi)=0\)),
Define \(x_{n+1} = x_{n} - \lambda f(x_{n})\)
Code
functionrelaxation( f, λ, x1; N=100, tol=1e-10) x = [x1] r =0.;for n ∈2:Npush!( x, x[n-1] -λ*f(x[n-1]) ) r =abs(f(x[end]));if (r < tol)return xendend@warn"max interations with |f| = $r";return xend
relaxation (generic function with 1 method)
Example 5.3 (Kepler’s equation) Consider Kepler’s equation:
┌ Warning: max interations with |f| = 0.0012486749578126677
└ @ Main In[3]:11[ Info: Saved animation to c:\Users\jack6\Math5485-Fall-2026\Math5485\images\Relaxed.gif
Play around with \(\lambda\), how does this affect the plot on the right?
Theorem 5.2 (Convergence: Relaxation) Suppose that \(f: [a,b]\to\mathbb R\) is continuously differentiable with \(f(\xi) = 0\), \(f'(\xi) \not= 0\). Then, there exists \(\delta, \lambda> 0\) such that \(x_{n+1} = x_n - \lambda f(x_n)\) converges at least linearly to \(\xi\) for all \(x_1 \in I_\delta := [\xi-\delta,\xi+\delta]\). The asymptotic error constant (for \(\alpha =1\)) is given by \(\left| 1 - \lambda f'(\xi) \right|\).
Therefore, for \(\epsilon \not= 1\), we have \(f(2\pi) = 0 \not= f'(2\pi)\) and so we can apply Theorem 5.2. Relaxation converges linearly with asymptotic error constant \(\mu := \left| 1 - \lambda f'(2\pi) \right| = \left| 1 - \lambda (1-\epsilon) \right|\).
In the above example, we chose \(\epsilon = 0.9\) and so the asymptotic error constant is \(\left| 1 - 0.1\lambda \right|\). This is in good agreement with what we see numerically:
Proof. Relaxation is a simple iteration with \(g(x) = x - \lambda f(x)\). We wish to apply the contraction mapping theorem and thus it is sufficient to check \(|g'(\xi)| \leq L < 1\).
Suppose that \(f'(\xi) > 0\) (the proof is very similar in the other case). Since \(f'\) is continuous, there exists \(\delta> 0\) such that
\[\begin{align*}
m := \frac12 f'(\xi) \leq f'(x) \leq M := \max_{y\in [a,b]} f'(y).
\end{align*}\]
As a result, we have \(1 - \lambda M \leq 1 - \lambda f'(x) \leq 1 - \lambda m\). Choosing \(L = 1 - \lambda m = \lambda M - 1\) gives \(\lambda = \frac{2}{M+m}\) and thus
[ Info: Saved animation to c:\Users\jack6\Math5485-Fall-2026\Math5485\images\Newton.gif
Theorem 5.3 (Convergence: Newton) Suppose \(f: [a,b] \to \mathbb R\) is twice continuously differentiable with \(f(\xi) = 0\) and \(f'(\xi) \not= 0\) for some \(\xi \in [a,b]\). Further suppose that
\[\begin{align}
\left|\frac{f''(x)}{f'(y)}\right| \leq A
\end{align}\]
for all \(x,y \in [a,b]\). Then, the Newton iteration \(x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}\) converges at least quadratically to \(\xi\) for all \(x_1 \in [a,b]\) such that \(|x_1 - \xi| \leq A^{-1}\). The asymptotic error constant \(\mu\) is \(\frac12 \left|\frac{f''(\xi)}{f'(\xi)}\right|\).
If \(|x_1 - \xi| \leq A^{-1}\) then, we have \(|x_2 - \xi| \leq A |x_1 - \xi|^2 \leq A A^{-1} |x_1 - \xi| \leq A^{-1}\). Proceeding iteratively, we obtain \(|x_{n} - \xi| \leq A^{-1}\). As a result, we have \(\left| x_{n+1} - \xi \right| \leq \frac12 |x_n - \xi|\) and so \((x_n) \to \xi\). Finally, we have
Therefore, for \(\epsilon \not= 1\), we can apply the above theorem. Newton therefore converges at least quadratically with asymptotic error constant \(\mu = \frac12 \left| \frac{f''(2\pi )}{f'(2\pi)} \right| = 0\). As a result, we would expect Newton iteration to converge super-quadratically in this case:
In fact, in this case the convergence is cubic with asymptotic error constant \(\mu = \frac13 \left| \frac{f'''(\xi)}{f'(\xi)} \right| = \frac13 \frac{\epsilon}{1-\epsilon}\) (Exercise: why?).
Code
println( "theoretical value of μ (for α=3) = ", (1/3) * ( ϵ/ (1-ϵ) ) )
theoretical value of μ (for α=3) = 3.0000000000000004
[ Info: Saved animation to c:\Users\jack6\Math5485-Fall-2026\Math5485\images\Secant.gif
Theorem 5.4 (Convergence: Secant) Suppose \(f: [a,b] \to \mathbb R\) is continuously differentiable with \(f(\xi) = 0\) and \(f'(\xi) \not= 0\) for some \(\xi \in [a,b]\). Then, the Secant iteration \(x_{n+1} = x_n - \frac{f(x_n)}{f[x_n,x_{n-1}]}\) converges at least linearly to \(\xi\) for all \(x_1,x_2\) sufficiently close to \(\xi\).
Remark 5.1. In fact, order of convergence \(\alpha = \frac{1 + \sqrt{5}}{2}\) in this case, with \(\mu = \left| \frac{f''(\xi)}{2 f'(\xi)} \right|^{\alpha/(1 + \alpha)}\).
Possible presentation topic: order of convergence of the secant method. Why is \(\alpha = \frac{1 + \sqrt{5}}{2}\) (the golden ratio)? Where do the Fibonacci numbers come in? Verify \(\alpha\) and \(\mu\) numerically.
Example 5.6 Let’s try and approximate \(\sqrt{2}\) again:
Code
# g(x) = x^2 - 2 is already defined a = (1/2)*(1+sqrt(5));mu = ( 2/(2*2*sqrt(2)) )^(a/(1+a));orderOfConvergence( secant( g, 1. ,2. ), sqrt(2); α=a )println("theoretical values of (α, μ) = (", a, ", " , mu, ")" )
Proof. Again, we may apply Taylor’s remainder theorem: there exists \(\eta_n\) between \(x_n\) and \(x_{n-1}\) such that \(f[x_n, x_{n-1}] = f'(\eta_n)\) and \(\theta_n\) between \(x_n\) and \(\xi\) such that \(f(x_n) = f'(\xi)(x_n - \xi)\). As a result, we have
for all \(x \in I\). If \(x_n, x_{n-1} \in I\) then \(\eta_n, \theta_n \in I\) and so we have \(\frac23 < 1 - \frac{f'(\theta_n)}{ f'(\eta_n) } < \frac25\) and thus \(x_{n+1} \in I\) with
That is, the sequence converges at least linearly. Moreover, by (1), we have \(|x_{n+1}-\xi|/|x_n - \xi| \to 0\) as \(n\to\infty\).
Definition 5.2 (Efficiency index) The efficiency index is \(E := \alpha^{1/\theta}\) where \(\theta\) is the number of function evaluations at each step of the iteration. This measures the order of the method per function evaluation
Note
Newton when \(f'(\xi), f''(\xi) \not= 0\), we have \(E = 2^{1/2} \approx 1.41...\) since the order of convergence is \(2\) and we need to evaluate \(f\) and \(f'\) at \(x_n\).
Secant when \(f'(\xi) \not= 0\), we have \(E = \left[\frac12\big( 1 + \sqrt{5} \big)\right]^{1/1} \approx 1.618...\) since the order of convergence is \(\frac12\big( 1 + \sqrt{5} \big)\) and we only require one function evaluation per iteration.
TipTO-DO
Assignment 2: Due in a week!
Exercises throughout the notes,
(Sign-up to office hours if you like)
5.5 Extra exercises
Exercise 5.4 (Faster than linear convergence)
Suppose that \(g\) is twice continuously differentiable with \(g(\xi) = \xi\) and \(g'(\xi) = 0\).
✍️ Show that there exists \(\delta > 0\) such that \(x_{n+1} = g(x_n)\) converges to \(\xi\) for all \(x_1 \in [\xi - \delta, \xi + \delta]\).
(whenever \(x_n \not= \xi\) for all \(n\)). What is the order of convergence when \(g''(\xi) \not= 0\)?
Exercise 5.5 (Newton)
Newton’s method\(x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}\) is the simple iteration with \(g(x) := x - \frac{f(x)}{f'(x)}\).
✍️ Suppose that \(f\) is three times continuously differentiable with \(f(\xi) = 0\) and \(f'(\xi) \not= 0\). Show that \(g'(\xi) = 0\) and \(g''(\xi) = \frac{f''(\xi)}{f'(\xi)}\). What does this tell you about Newton’s method?
Taylor’s theorem.
Exercise 5.6 (Division without dividing)
Fix \(a > 0\).
✍️ Show that Newton’s method applied to \(f(x) := \frac1x - a\) is given by \(x_{n+1} = x_n(2 - a x_n)\).
✍️ Define \(e_n := 1 - a x_n\) and show that \(e_{n+1} = e_n^2\). Hence, find all \(x_1\) for which \((x_n) \to \frac1a\).
✍️ Show that \(\left| x_{n+1} - \frac1a \right| = a \left| x_n - \frac1a \right|^2\). What are the order of convergence and the asymptotic error constant? Compare with the asymptotic error constant \(\mu = \frac12 \left| \frac{f''(\xi)}{f'(\xi)} \right|\) from lectures.
💻 Take \(a = 7\). Verify your answers to (ii) and (iii) numerically using \(x_1 = 0.1, 0.28\), and \(0.3\).
We have \(f(x) = \frac1x - a\) and \(f'(x) = -\frac1{x^2}\) and so Newton is
\[\begin{align}
e_{n+1} &= 1 - a x_{n+1} \nonumber\\
&= 1 - a x_n (2 - ax_n) \nonumber\\
&= 1 - 2 a x_n + (ax_n)^2 \nonumber\\
&= (1 - a x_n)^2 = e_n^2.
\end{align}\]
We have \(x_n \to \frac1a\) if and only if \(e_n \to 0\). Since \(e_{n+1} = e_n^2 = e_1^{2^n}\), we have \(e_n \to 0\) for all \(x_1\) with \(|e_n| = |1 - a x_1| < 1\). That is, if \(0 < x_1 < 2/a\).
We have
\[\begin{align}
|x_{n+1} - \frac1a| &= \frac{1}{a} | 1 - a x_{n+1} | \nonumber\\
&= \frac1a e_{n+1} \nonumber\\
&= \frac1a |1 - a x_n|^2 \nonumber\\
&= a |x_n - \frac1a|^2.
\end{align}\]
Therefore, the order of convergence is \(\alpha = 2\) with asymptotic error constant \(\mu = a\). Here, we are applying Newton’s method to \(f(x) = \frac1x - a\) and so \(f'(x) = -\frac1{x^2}\), \(f''(x) = \frac2{x^3}\), and \(\frac12 \big|\frac{f''(1/a)}{f'(1/a)}\big| = \frac12 \frac2{a^{-3}} (a^{-2}) = a\) (which agrees with the above).
Süli, Endre, and David F. Mayers. 2003. An Introduction to Numerical Analysis. Cambridge, England: Cambridge University Press. https://doi.org/10.1017/CBO9780511801181.
