```{r first_example, fig.align= "center", fig.width = 10, fig.height = 10, echo = FALSE, cache = FALSE} a <- c(0,-1,0,1)/6 #a <- c(1,-2,0,1)/6 x <- seq (-2, 2, length = 1000) y <- ecubic (a, x) plot (x, y$fx, xlim = c(-2,2), ylim = c(-1,1), type = "l", col = "RED", ylab = "y", lwd = 2) lines (x, y$gx, col = "BLUE", lwd = 2) lines (x, y$hx, col = "GREEN", lwd = 2) abline(h=0) abline(v=1) abline(v=-1) abline(v=0) abline(v=sqrt(3)/3) abline(v=-sqrt(3)/3) ```

We will look for a local minimum in the interval $[-2,2]$, stating with initial value 1. Note that $f''(x)=x$ and thus $K_0=B=2$. At $x_\infty=\frac13\sqrt{3}$ we have $\rho(x_\infty)=1-\frac16\sqrt{3}$, i.e. approximately `r 1-sqrt(3)/6`. We report the results of the final iteration. ```{r first_analysis_1, echo = FALSE, size = "tiny"} h <- myIterator(xinit = 1.0, f = cubicUQ, eps = 1e-6, itmax = 100, verbose = FALSE, final = TRUE, a = a, up = 2, lw = -2, sharp = FALSE) ``` If we look for a local minimum in the interval $[0,1]$ instead of $[-2,2]$, we get much faster convergence, because the upper bound is now much closer to the solution. ```{r first_analysis_2, echo = FALSE, size = "tiny"} h <- myIterator(xinit = 0.5, f = cubicUQ, eps = 1e-6, itmax = 100, verbose = FALSE, final = TRUE, a = a, up = 1, lw = 0, sharp = FALSE) ``` If we start at a value to the left of $-\frac13\sqrt{3}$ and look for a minimum in $[-2,2]$ then the algorithm converges to the boundary at $-2$. ```{r first_analysis_3, echo = FALSE, size = "tiny"} h <- myIterator(xinit = -1.5, f = cubicUQ, eps = 1e-6, itmax = 100, verbose = FALSE, final = TRUE, a = a, up = 2, lw = -2, sharp = FALSE) ``` Note that alteratively we could have used $$ K_0^+:=\max_{L\leq x\leq U} |f''(x)| $$ in our majorization fuctions. Since $f''$ is linear we see that $|f''|$ is convex, and thus $K_0^+=\max(|f''(L)|,|f''(U)|$. Using $K_0^+$ gives a majorization which is generally less precise, but uses majorization functions that are always convex quadratics. Also note that if there is a strict local minimum in $\mathcal{I}$ then $K_0>0$, although we can still have $K_0

If we are close to a strict local minimum $x$ we have $f'(x)\approx 0$ and $f''(x)>0$. Thus the quadratic will have one root approximately zero and one root approximately equal to $f''(x)$, and the iteration is basically a Newton iteration. Thus, at least for cubics, sublevel majorization has quadratic convergence. We illustrate this by analyzing our small example with sublevel majorization, starting from $x=1$ and $x=\frac12$. ```{r third_analysis_1, echo = FALSE, size = "tiny"} h <- myIterator(xinit = 1, f = cubicSublevel, eps = 1e-6, itmax = 100, verbose = TRUE, final = FALSE, a = a) ``` ```{r third_analysis_2, echo = FALSE, size = "tiny"} h <- myIterator(xinit = .5, f = cubicSublevel, eps = 1e-6, itmax = 100, verbose = TRUE, final = FALSE, a = a) ``` If $\mathcal{I}=[L,U]$ then our analysis must be modified slightly. We want inequality $\eqref{E:sharp}$ on the intersection of the sublevel interval and $[L,U]$. If the sublevel interval is in $[L,U]$ our previous analysis applies. Because we always have $y\in[L,U]$ the other possible intervals are $[y,U]$ if $y\leq U\leq y-2f'(y)/K$ and $[L,y]$ if $y-2f'(y)/K\leq L\leq y$. #Appendix: Code ##auxilary.R ```{r file_auxilary, code = readLines("auxilary.R")} ``` ##iterate.R ```{r file_auxilary, code = readLines("iterate.R")} ``` ##sublevel.R ```{r file_auxilary, code = readLines("sublevel.R")} ``` #References