Lecture 4: Chapter 2: Solving nonlinear equations in 1d
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.
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).
I encourage you to download the lecture notes and play around with the Julia code.
Notes for this lecture have not been updated since we met (stay tuned for updates)
This lecture is based on Chapter 1 of [Fundamentals of Numerical Computation by Driscoll, Braun] which is avaliable online (opens in a new tab)
Last time: conditioning, stability;
Start of Chapter 2: roots (zeros), intermediate value theorem and change of sign theorem, example \(f(x) = e^x - 2x - 1\) on \([1,2]\), fixed points, Brouwer’s fixed point theorem.
Since \(f\) is continuous and we have \(f(1) = e - 3 < 0 < e^2 - 5 = f(2)\) and so we can apply change of sign theorem to \(f\) on the interval \([1,2]\): there exists \(\xi \in [1,2]\) with \(f(\xi) = 0\).
Here’s a picture:
f(x) = exp(x) - 2*x - 1
g(x) = log( 2*x + 1 )
h(x) = (exp(x) - 1)/2
id(x) = x
@show (f(1), f(2))
plot( f, 1, 2, label=L"y = f(x)" )
hline!([0], label=L"y = 0", linestyle=:dash)
scatter!([1 2], [f(1) f(2)] , label=[L"f(1)" L"f(2)"]) (f(1), f(2)) = (-0.2817181715409549, 2.3890560989306504)
Rearranging \(f(x) = 0\) gives \(g(x) = x\) and \(h(x) = x\).
Since \(g\) is increasing we have \(1 < \log3 = g(1) \leq g(x) \leq g(2) = \log5 < 2\) for all \(x \in [1,2]\). We can therefore apply Brouwer’s fixed point theorem to conclude there exists \(\xi \in [1,2]\) such that \(g(\xi) = \xi\).
On the other hand \(h(1) = \frac{e-1}{2} < 1\) (and \(g(2) > 2\)) and so \(h\) does not map \([1,2]\) onto \([1,2]\) and we cannot apply Brouwer’s fixed point theorem to \(h\).
Here’s a picture:
@show (g(1), g(2));
@show (h(1), h(2));
plot( [g, id, h], 1, 2,
label=[L"g" L"x" L"h"], lw=2,
color=["red" "black" "green"], linestyle=[:solid :dash :solid] )
hline!( [1,2], linestyle=:dash, primary=false, color="black" )(g(1), g(2)) = (1.0986122886681098, 1.6094379124341003)
(h(1), h(2)) = (0.8591409142295225, 3.194528049465325)
Suppose we want to find fixed points of a continuous function \(g:[a,b] \to [a,b]\). The simple iteration is defined by
\[ \begin{align} x_1 &\in [a,b] \nonumber\\ % x_{n+1} &:= g(x_n). \end{align} \tag{4.1}\]
We implement this here:
function simple_iteration(g, x1; N=100, tol=1e-10, flag=false)
x = Vector{Float64}(undef, N)
x[1] = x1
for n ∈ 2:N
x[n] = g(x[n-1])
if !isfinite(x[n])
return x[1:n], false
end
# compute relative error
rel_err = abs(x[n] - x[n-1]) / max(abs(x[n]), 1e-12)
if rel_err < tol
return x[1:n], true
end
end
if flag
@warn "Fixed-point iteration did not converge within $N iterations."
end
return x, false
endsimple_iteration (generic function with 1 method)Lemma 4.1 Suppose that \((x_{n}) \to \xi\) then \(\xi\) is a fixed point of \(g\).
Proof. Since \((x_{n+1}) \to \xi\), we have \(\xi = \lim_{n\to \infty} g(x_n) = g(\xi)\) by continuity of \(g\).
Example 4.1 Returning to Exercise 3.5 and Exercise 3.6 where \(f(x) = e^x - 2x - 1\). Recall that finding roots of \(f\) in \([1,2]\) is equivalent to finding fixed points of \(g\) and \(h\) as defined in (3.1).
Let’s see if the iterative methods \(x_{n+1} = g(x_n)\) and \(y_{n+1} = h(y_n)\) converge for \(x_1 = y_1 = 1\):
x, _ = simple_iteration( g, 1; N=20 )
y, _ = simple_iteration( h, 1; N=20 );
@show (x[end], y[end]);
plot( [g, h] , -0.25, 2;
label=[ L"y = g(x)" L"y = h(x)"], color=[:red :blue])
scatter!( x, g.(x);
label=L"x_{n+1} = g(x_n)", color=:red)
scatter!( y, h.(y);
label=L"y_{n+1} = h(y_n)", color=:blue)
vline!( [1, 2];
linestyle=:dash, color=:black, primary=false)(x[end], y[end]) = (1.2564242398858796, 1.374528751196813e-5)
Here, we see that \(x_n \to \xi \approx 1.255 \in [1,2]\) but \(y_{n} \to \widetilde{\xi} \approx 0\) so the formulations \(g(x) = x\) and \(h(x) = x\) are equivalent, but they lead to different numerical methods.
Animations:
# code-fold: true
function animate_simple( g, x1; N=10, label="g")
x, _ = simple_iteration( g, x1; N=20 )
plot( [id, g] , min(-0.25,x[1]-1e-3), max(2,x[1]+1e-3),
label=[ L"x" L"%$label"], title=L"\textrm{simple~iteration~} x_1 = %$x1 \textrm{~and~} x_{n+1} = %$label(x_{n})",
color=["black" "red"], linestyle=[:dash :solid])
anim = @animate for n ∈ 2:2(length(x)-1)
if (n%2 == 0)
k = Int(n/2)
plot!( [x[k], x[k]], [x[k], x[k+1]],
primary=false, color=:black, lw=2)
else
k = Int((n+1)/2)
plot!( [x[k-1], x[k]], [x[k],x[k]],
primary=false, color=:black, lw=2)
end
end
return anim
endanimate_simple (generic function with 1 method)anim = animate_simple( g, 1e-3; N=20, label="g")
gif(anim, "../images/stable.gif", fps = 3)[ Info: Saved animation to c:\Users\jack6\Math5485-Fall-2026\Math5485\images\stable.gif
anim = animate_simple( h, x[end]+1e-2; N=10, label="h")
gif(anim, "../images/unstable.gif", fps = 3)[ Info: Saved animation to c:\Users\jack6\Math5485-Fall-2026\Math5485\images\unstable.gif
In fact, \((\xi, \tilde{\xi})\) approximate the two real roots of \(f\):
@show ( f(1), f(2) )
plot( f, -1, 2; label = L"y = f(x)" )
plot!( x->0; label = L"y = 0", linestyle=:dot )
scatter!( [x[end], y[end]], [0, 0]; primary=false )(f(1), f(2)) = (-0.2817181715409549, 2.3890560989306504)
Definition 4.1 (Order of convergence) Let \(x_n \to \xi\). Suppose that there exist \(\alpha\geq1\) and \(\mu \geq 0\) such that
\[\begin{align} \lim_{n\to\infty} \frac{\left|x_{n+1} - \xi\right|}{\left|x_n - \xi\right|^\alpha} = \mu \end{align}\]
In the case where (i) \(\alpha = 1, \mu \in (0,1)\) or (ii) \(\alpha>1, \mu> 0\), we say
Example 4.2 Let’s go back to our example: \(f(x) = e^x - 2x - 1\). We have defined \(g(x) = \log( 2x + 1 )\) and we are trying to solve the fixed point problem \(g(x) = x\).
(This is mathematically equivalent to \(f(x) = 0\).)
We have seen (numerically) that \(x_{n+1} = g(x_n)\) with \(x_1\) converges to \(\xi = g(\xi) \approx 1.26\). What is the order of convergence? What is the asymptotic error constant? Asymptotic rate of convergence?
(It turns out that \(\xi = g(\xi) \approx 1.256\) can be written in terms of the LambertW function.)
using LambertW
ξ = -( 1/2 + lambertw(-(1/2) * exp(-1/2), -1) )
println("ξ = $ξ")ξ = 1.2564312086261695μₙ = @. abs( ( x[2:end] - ξ )/(x[1:end-1] - ξ ) )19-element Vector{Float64}:
0.6154434977067526
0.5965577179668249
0.5851632047756364
0.5784563522754123
0.5745645700825062
0.5723246633711306
0.5710414920687147
0.5703083577906018
0.5698901195281622
0.569651729099643
0.569515916456726
0.5694385647462568
0.5693945163234355
0.569369434946979
0.569355154232495
0.5693470233879584
0.5693423940983908
0.5693397584481151
0.5693382578603982μ, ρ = μₙ[end], -log10( μₙ[end] )
println("μ = $μ")
println("ρ = $ρ")μ = 0.5693382578603982
ρ = 0.2446296318929979Since μₙ appears to converge to \(\mu \in (0,1)\), we have \(x_n \to \xi\) linearly with asymptotic error constant \(\mu\approx 0.569\) and asymptotic rate of convergence \(\rho \approx 0.245\).
We will prove that \(x_{n+1} = g(x_n)\) converges linearly and show that \(\mu = |g'(\xi)|\). Our computed value of \(\mu\) (after \(20\) iterations) is close to this theoretical value:
g′ = x -> 2/( 2*x + 1);
@show g′( ξ );g′(ξ) = 0.569336274081677Definition 4.2 We say \(g : [a,b] \to \mathbb R\) is a contraction if there exists an \(L \in [0,1)\) such that \(|g(x) - g(y)| \leq L|x-y|\) for all \(x\in[a,b]\).
Suppose \(g :[a,b] \to \mathbb R\) is continuously differentiable with \(|g'(x)| \leq L < 1\) for all \(x \in [a,b]\). Show that \(g\) is a contraction with constant \(L\).
Theorem 4.1 (Contraction Mapping Theorem (Banach fixed point theorem)) Suppose \(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\) for all \(x_1 \in [a,b]\)
Proof. By Brouwer’s fixed point theorem (\(g:[a,b] \to [a,b]\) is continuous), there exists a fixed point \(\xi \in [a,b]\). If \(\zeta\) is another fixed point, then there exists \(L \in (0,1)\) such that
\[\begin{align} |\xi - \zeta| &= |g(\xi) - g(\zeta)| \nonumber\\ % &\leq L |\xi - \zeta| \end{align}\]
Here, we used the fact that \(\xi, \zeta\) are fixed points of \(g\) and that \(g\) is a contraction. That is, \(0 \leq (1-L) |\xi - \zeta| \leq 0\) and so \(\xi = \zeta\). i.e. \(\xi\) is unique.
Defining \(x_{n+1} = g(x_n)\) for \(x_1 \in [a,b]\), we have
\[\begin{align} |x_{n+1} - \xi| &= |g(x_n) - g(\xi)| \nonumber\\ % &\leq L |x_{n} - \xi| \nonumber\\ % &\leq L^n |x_1 - \xi|. \end{align}\]
Since \(L \in (0,1)\), we have \(L^n \to 0\) as \(n \to \infty\) and thus \((x_n) \to \xi\).
Take the simple iteration \(x_{n+1} = g(x_n)\) for some contraction \(g : [a,b] \to [a,b]\). Show that \((x_n)\) converges to the fixed point of \(g\) in \([a,b]\) at least linearly with asymptotic error constant \(\mu = |g'(\xi)|\).
Show that \(g(x) = \log( 2x + 1)\) is a contraction on \([1,2]\) with \(L = \frac23\). Hence conclude that \(x_{n+1} := g(x_n)\) converges for all \(x_1 \in [1,2]\).
Assignment 2, Fall 2025, [25 pts]. Fix \(a, x_1 > 0\) and define the iteration \(x_{n+1} = \frac{1}{2}\big( x_n + \frac{a}{x_n} \big)\).
Exercise 4.5 (Lambert W function)
Assignment 3, Fall 2025. The Lambert W function (also called the product-log function) \(W : [0,\infty) \to [0,\infty)\) satisfies \(W(a) e^{W(a)} = a\). Define \(\Omega := W(1)\).
\[\begin{align} g(x) = e^{-x}, \qquad h(x) = \log \left|\frac{1}{x}\right| \end{align}\]
Exercise 4.6 (Simple iteration)
Midterm, Fall 2025, Optional section, 30 pts. Define \(g(x) = 1 + \frac{1}{1 + x}\) and \(I := [1,2]\).