Visualizing Newton-Raphson

Specific Domains Optimization (Mathematical)
1

I’ve been studying the Newton-Raphson algorithm and coded up a simple example to show some of its shortcomings with particular functions. I’m posting here simply to share with the community and, as always, I welcome feedback!

First is the case where we choose a good starting point and the algorithm quickly converges to find the root:

Newton-Raphson1

Next is a case where the algorithm doesn’t converge and it just oscillates around:

Newton-Raphson2

Finally, this starting point eventually converges, but only after taking a long strange trip down the curve (that was for you, deadheads :wink:):

Newton-Raphson3

And here’s the simple code to generate these visuals:

using ForwardDiff
using Plots

f(x) = 0.05x^3 - 1.2x + 5
range = -8.0:0.01:8

x = -3
xᵢ = []
yᵢ = []

for i in 1:11
    if i == 1
        push!(xᵢ, x)
        push!(yᵢ, f(x))
    else
        global x = x - (f(x) / ForwardDiff.derivative(f, x))
        push!(xᵢ, x)
        push!(yᵢ, f(x))
    end
end

anim = @animate for i in 1:length(xᵢ)
    p = plot(
        range,
        f.(range),
        legend=false,
        title="Iteration $(i-1), x = $(round(xᵢ[i], digits=2)), y = $(round(yᵢ[i], digits=2))",
        framestyle=:origin
    )
    scatter!([xᵢ[i]], [yᵢ[i]])
end

gif(anim, "Newton-Raphson3.gif", fps=0.5)
2 Likes
2

Thanks!

Another nice thing to try is to use the Interact package to have an interactive version of the plot. It’s also nice to plot the tangent line so that you can visualize the Newton step.

I put together an IJulia notebook that does both of these things to illustrate the Newton method: https://github.com/mitmath/1806/blob/master/lectures/Multidimensional-Newton.ipynb (note that you’ll have to download it and run it in order to see the interactive plot — nbviewer doesn’t show this). This notebook was pre Julia 1.0, however, so it will need a few tweaks to run now.

4 Likes
3

I put together an IJulia notebook that does both of these things to illustrate the Newton method: https://github.com/mitmath/1806/blob/master/lectures/Multidimensional-Newton.ipynb (note that you’ll have to download it and run it in order to see the interactive plot — nbviewer doesn’t show this). This notebook was pre Julia 1.0, however, so it will need a few tweaks to run now.

This looks fantastic, thanks for sharing!!

4

My package Fatou.jl also allows you to visualize the convergence of Newton Raphson iterations, as well as other fixed point iterations.

2 Likes