-
Notifications
You must be signed in to change notification settings - Fork 1
/
slides.html
378 lines (302 loc) · 11.2 KB
/
slides.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
<!DOCTYPE html>
<html lang="" xml:lang="">
<head>
<title>Draw fractals from root finding iteration in R</title>
<meta charset="utf-8" />
<meta name="author" content="Keren Xu" />
<link href="libs/remark-css-0.0.1/default.css" rel="stylesheet" />
<link href="libs/remark-css-0.0.1/rladies.css" rel="stylesheet" />
<link href="libs/remark-css-0.0.1/rladies-fonts.css" rel="stylesheet" />
</head>
<body>
<textarea id="source">
class: center, middle, inverse, title-slide
# Draw fractals from root finding iteration in R
## LA R users group: April Meeting
### Keren Xu
### PhD student in Epidemiology at USC
### 2020/04/23
---
# Overview
### 1. Root-finding Algorithm
### 2. Newton’s Method
### 3. Secant Method
### 4. Fractals
### 5. Getting Started - Creating your fractals
---
# Root-finding Algorithm
`\(f(a) = 0\)`
`\(f(x) = g(x)\)` ➡️ `\(h(x) = f(x) – g(x)\)`
.center[
<img src="root_def.png" width="50%" height="50%" />
]
---
background-image: url(https://upload.wikimedia.org/wikipedia/commons/3/39/GodfreyKneller-IsaacNewton-1689.jpg)
background-position: 95% 10%
background-size: 20%
# Newton’s Method
Our curent "guess" for a: `\(x_0\)` ➡️ `\(f'(x_0) = \frac{f(x_0) - y}{x_0 - x}\)`
➡️ `\(f'(x_0) = \frac{f(x_0) - 0}{x_0 - x_1}\)` ➡️ `\(x_1= x_0 - \frac{f(x_0)}{f'(x_0)}\)` ➡️ `\(x_2= x_1 - \frac{f(x_1)}{f'(x_1)}\)`
.center[
<img src="newton_method.png" width="60%" height="60%" />
]
---
# Newton’s Method
.center[
]
---
# Newton’s Method
<b>
### In general:
<b>
## `\(x_{n+1}= x_n - \frac{f(x_n)}{f'(x_n)}\)`
---
# Newton’s Method
### Computational example:
### Find roots for `\(x^3-1\)`
```r
F1 <- function(x){
return(c(x^3-1, 3*(x^2)))
}
```
---
# Newton’s Method
### Computational example:
```r
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))
}
```
---
background-image: url(https://upload.wikimedia.org/wikipedia/commons/thumb/0/06/CIRCLE_LINES.svg/594px-CIRCLE_LINES.svg.png)
background-position: 95% 8%
background-size: 20%
# Secant Method
- Do not need to compute a derivative
- Need to provide two initial guesses
<br>
<img src="https://upload.wikimedia.org/wikipedia/commons/9/92/Secant_method.svg" width="60%" height="60%" />
---
background-image: url(https://upload.wikimedia.org/wikipedia/commons/thumb/0/06/CIRCLE_LINES.svg/594px-CIRCLE_LINES.svg.png)
background-position: 95% 8%
background-size: 20%
# Secant Method
Two initial "guesses" `\(x_0\)` and `\(x_1\)`, assuming `\(x_0\)` is the older one
➡️ `\(\frac{y-f(x_1)}{x-x_1} = \frac{f(x_0) - f(x_1)}{x_0 - x_1}\)`
➡️ so `\(x_2\)` can be found from `\(\frac{0-f(x_1)}{x_2-x_1} = \frac{f(x_0) - f(x_1)}{x_0 - x_1}\)` ➡️ `\(x_2 = x_1 - f(x_1)\frac{x_0 - x_1}{f(x_0) - f(x_1)}\)`
<img src="https://upload.wikimedia.org/wikipedia/commons/9/92/Secant_method.svg" width="60%" height="60%" />
---
# Secant Method
<b>
### In general:
<b>
## `\(x_{n+1} = x_n - f(x_n)\frac{x_n - x_{n-1}}{f(x_n) - f(x_{n-1})}\)`
---
# Secant Method
### Computational example:
```r
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))
}
```
---
# Fractals
### Root finding functions can also be applied to find roots for **complex functions**, which are functions of **complex numbers**.
<img src="https://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Complex_number_illustration.svg/1024px-Complex_number_illustration.svg.png" width="50%" height="50%" />
---
# Fractals
### Each root has a **basin of attraction** in the complex plane, which is a set of all **initial guesses** that cause the method to converge to that particular root.
### These sets can be mapped into images. The boundaries of the basins of attraction are called **fractals**.
<img src="https://upload.wikimedia.org/wikipedia/commons/a/a4/Mandelbrot_sequence_new.gif" width="50%" height="50%" />
---
# Fractals
## Julia set
<img src="https://upload.wikimedia.org/wikipedia/commons/thumb/d/d9/Julia_set%2C_plotted_with_Matplotlib.svg/1920px-Julia_set%2C_plotted_with_Matplotlib.svg.png" width="50%" height="50%" />
---
# Fractals
## Mandelbrot set
<img src="https://upload.wikimedia.org/wikipedia/commons/thumb/2/21/Mandel_zoom_00_mandelbrot_set.jpg/1920px-Mandel_zoom_00_mandelbrot_set.jpg" width="50%" height="50%" />
---
# Fractals
## Burning ship fractals
<img src="https://upload.wikimedia.org/wikipedia/commons/9/9a/Burning_Ship_Fractal_Zoom-out_64.gif" width="50%" height="50%" />
---
# Fractals
## Newton's fractals
<img src="https://upload.wikimedia.org/wikipedia/commons/9/9b/FRACT008.png" width="50%" height="50%" />
---
# Summary
### 1. Root-finding algorithm: `\(h(x) = f(x) – g(x) = 0\)` 📐
### 2. Most common: Newton’s Method and Secant method 🍎
### 3. Complex numbers and fractals 👩🎨
---
# Get Started - Creating your fractals
<br><br><br>
.center[
]
---
# Recommended readings
- Introduction to scientific programming and simulation using r, by Andrew P. Robinson, Owen Jones, and Robert Maillardet [[link](http://www.tf.uns.ac.rs/~omorr/radovan_omorjan_003_prII/r-examples/spuRs/spuRs-2ed.pdf)]
- Newton fractal wiki page [[link](https://en.wikipedia.org/wiki/Newton_fractal)]
---
class: center, middle,inverse
# Thanks for attending!
😄
### Keep in touch [twitter @kerenxuepi](https://twitter.com/kerenxuepi)
<br><br><br>
Slides created via **RLadies** **xaringan** slide theme
</textarea>
<style data-target="print-only">@media screen {.remark-slide-container{display:block;}.remark-slide-scaler{box-shadow:none;}}</style>
<script src="https://remarkjs.com/downloads/remark-latest.min.js"></script>
<script>var slideshow = remark.create({
"highlightStyle": "github",
"highlightLines": true,
"countIncrementalSlides": false
});
if (window.HTMLWidgets) slideshow.on('afterShowSlide', function (slide) {
window.dispatchEvent(new Event('resize'));
});
(function(d) {
var s = d.createElement("style"), r = d.querySelector(".remark-slide-scaler");
if (!r) return;
s.type = "text/css"; s.innerHTML = "@page {size: " + r.style.width + " " + r.style.height +"; }";
d.head.appendChild(s);
})(document);
(function(d) {
var el = d.getElementsByClassName("remark-slides-area");
if (!el) return;
var slide, slides = slideshow.getSlides(), els = el[0].children;
for (var i = 1; i < slides.length; i++) {
slide = slides[i];
if (slide.properties.continued === "true" || slide.properties.count === "false") {
els[i - 1].className += ' has-continuation';
}
}
var s = d.createElement("style");
s.type = "text/css"; s.innerHTML = "@media print { .has-continuation { display: none; } }";
d.head.appendChild(s);
})(document);
// delete the temporary CSS (for displaying all slides initially) when the user
// starts to view slides
(function() {
var deleted = false;
slideshow.on('beforeShowSlide', function(slide) {
if (deleted) return;
var sheets = document.styleSheets, node;
for (var i = 0; i < sheets.length; i++) {
node = sheets[i].ownerNode;
if (node.dataset["target"] !== "print-only") continue;
node.parentNode.removeChild(node);
}
deleted = true;
});
})();
(function() {
"use strict"
// Replace <script> tags in slides area to make them executable
var scripts = document.querySelectorAll(
'.remark-slides-area .remark-slide-container script'
);
if (!scripts.length) return;
for (var i = 0; i < scripts.length; i++) {
var s = document.createElement('script');
var code = document.createTextNode(scripts[i].textContent);
s.appendChild(code);
var scriptAttrs = scripts[i].attributes;
for (var j = 0; j < scriptAttrs.length; j++) {
s.setAttribute(scriptAttrs[j].name, scriptAttrs[j].value);
}
scripts[i].parentElement.replaceChild(s, scripts[i]);
}
})();
(function() {
var links = document.getElementsByTagName('a');
for (var i = 0; i < links.length; i++) {
if (/^(https?:)?\/\//.test(links[i].getAttribute('href'))) {
links[i].target = '_blank';
}
}
})();
// adds .remark-code-has-line-highlighted class to <pre> parent elements
// of code chunks containing highlighted lines with class .remark-code-line-highlighted
(function(d) {
const hlines = d.querySelectorAll('.remark-code-line-highlighted');
const preParents = [];
const findPreParent = function(line, p = 0) {
if (p > 1) return null; // traverse up no further than grandparent
const el = line.parentElement;
return el.tagName === "PRE" ? el : findPreParent(el, ++p);
};
for (let line of hlines) {
let pre = findPreParent(line);
if (pre && !preParents.includes(pre)) preParents.push(pre);
}
preParents.forEach(p => p.classList.add("remark-code-has-line-highlighted"));
})(document);</script>
<script>
slideshow._releaseMath = function(el) {
var i, text, code, codes = el.getElementsByTagName('code');
for (i = 0; i < codes.length;) {
code = codes[i];
if (code.parentNode.tagName !== 'PRE' && code.childElementCount === 0) {
text = code.textContent;
if (/^\\\((.|\s)+\\\)$/.test(text) || /^\\\[(.|\s)+\\\]$/.test(text) ||
/^\$\$(.|\s)+\$\$$/.test(text) ||
/^\\begin\{([^}]+)\}(.|\s)+\\end\{[^}]+\}$/.test(text)) {
code.outerHTML = code.innerHTML; // remove <code></code>
continue;
}
}
i++;
}
};
slideshow._releaseMath(document);
</script>
<!-- dynamically load mathjax for compatibility with self-contained -->
<script>
(function () {
var script = document.createElement('script');
script.type = 'text/javascript';
script.src = 'https://mathjax.rstudio.com/latest/MathJax.js?config=TeX-MML-AM_CHTML';
if (location.protocol !== 'file:' && /^https?:/.test(script.src))
script.src = script.src.replace(/^https?:/, '');
document.getElementsByTagName('head')[0].appendChild(script);
})();
</script>
</body>
</html>