Zoom Talk Draw Fractals from Root Finding Iterations

A zoom talk about drawing fractals in R for the LA R Users April Meetup.

Github repo:

Slides: link

Samples codes:

Use NewtonRaphson root finding methods to draw fractals for complex functions.

Create function newtonraphson

# ftn is the name of a function that has two output including f(x) and f'(x)
# x0 is the starting point for the algorithm
# tol is a good stop condition when |f(x)| <= tol for the algorithm, the default here is 1e-9
# max.iter is a stop condition for the algorithm when n = max.itr

newtonraphson <- function(ftn, x0, tol = 1e-9, max.iter) {
  # initialize
  x <- x0
  fx <- ftn(x)
  iter <- 0

  # continue iterating until stopping conditions are met
  while ((abs(fx[1]) > tol) && (iter < max.iter)) {
    x <- x - fx[1] / fx[2]
    fx <- ftn(x)
    iter <- iter + 1
    # cat("At iteration", iter, "value of x is:", x, "\n")
  }

  # output depends on the success of the algorithm
  if (abs(fx[1]) > tol) {
    # cat("Algorithm failed to converge\n")
    return(data.frame(x0, root = NA, iter = NA))
  } else {
    # cat("Algorithm converged\n")
    return(data.frame(x0, root = x, iter))
  }
}

Draw graph for x^3-1

F1 <- function(x) {
  return(c(x^3 - 1, 3 * (x^2)))
}

# create complex numbers
x <- seq(-1, 1, length.out = 500)
y <- seq(-1, 1, length.out = 500)
z <- outer(x, 1i * y, "+")

# parallel processing using furrr
plan(multiprocess)

df <- z %>% future_map_dfr(~ newtonraphson(F1, ., 1e-9, 40), .progress = TRUE)

df$x <- Re(df$x0)
df$y <- Im(df$x0)

# color by iteration
df %>% ggplot(aes(x = x, y = y)) +
  geom_raster(aes(fill = iter), interpolate = TRUE) +
  scale_fill_gradientn(colors = brewer.pal(12, "Paired")) +
  theme_void() +
  theme(legend.position = "none")

df %>% ggplot(aes(x = x, y = y)) +
  geom_raster(aes(fill = iter), interpolate = TRUE) +
  scale_fill_gradientn(colors = carto.pal("multi.pal")) +
  theme_void() +
  theme(legend.position = "none")

df %>% ggplot(aes(x = x, y = y)) +
  geom_raster(aes(fill = iter), interpolate = TRUE) +
  scale_fill_gradientn(colors = carto.pal("turquoise.pal")) +
  theme_void() +
  theme(legend.position = "none")

df %>% ggplot(aes(x = x, y = y)) +
  geom_raster(aes(fill = iter), interpolate = TRUE) +
  scale_fill_gradientn(colors = wes_palette("BottleRocket2")) +
  theme_void() +
  theme(legend.position = "none")

df %>% ggplot(aes(x = x, y = y)) +
  geom_raster(aes(fill = iter), interpolate = TRUE) +
  scale_fill_gradientn(colors = wes_palette("Rushmore1")) +
  theme_void() +
  theme(legend.position = "none")

Sample codes for Secant method

secant <- function(ftn, x0, x1, tol = 1e-9, max.iter) {
  # initialize
  x_n0 <- x0
  x_n1 <- x1
  ftn_n0 <- ftn(x_n0)
  ftn_n1 <- ftn(x_n1)
  iter <- 0

  # continue iterating until stopping conditions are met
  while ((abs(ftn_n1) > tol) && (iter < max.iter)) {
    x_n2 <- x_n1 - ftn_n1 * (x_n1 - x_n0) / (ftn_n1 - ftn_n0)
    x_n0 <- x_n1
    ftn_n0 <- ftn(x_n0)
    x_n1 <- x_n2
    ftn_n1 <- ftn(x_n1)
    iter <- iter + 1
    # cat("At iteration", iter, "value of x is:", x_n1, "\n")
  }

  return(c(x_n1, iter))
}

Reuse

https://creativecommons.org/licenses/by/4.0/

Citation

BibTeX citation:

@online{xu2020,
  author = {Keren Xu},
  editor = {},
  title = {Zoom {Talk} {Draw} {Fractals} from {Root} {Finding}
    {Iterations}},
  date = {2020-04-23},
  url = {https://xukeren.github.io//posts/2020-04-23-draw-fractals-from-root-finding-iteration},
  langid = {en}
}

For attribution, please cite this work as:

Keren Xu. 2020. “Zoom Talk Draw Fractals from Root Finding Iterations.” April 23, 2020. https://xukeren.github.io//posts/2020-04-23-draw-fractals-from-root-finding-iteration.