How to derive formulas for sequences that converge to a specific value using simple functions

Question

If I have some value $L\in \mathbb{R}$ such that a sequence $a_n$ $$\lim_{n\rightarrow\infty}{a_n}=L$$ If I state the properties of the sequence such as monotonically increasing or decreasing is it possible to find the terms in the sequence in the form $a_{n+1}=A(a_n)$ where $A$ is a function that requires only simple functions, where simple means exactly calculable over a finite proccess. We can express this as a guess $$|L-x_n|<\epsilon$$ And we want to rearrange it to be $$|L-A(x_n)|<B(\epsilon)$$ And $A(x_n)$ is a better approximation if $B(\epsilon) < \epsilon$. However, we also want $A(x_n) > x_n$ since we want it to be monotonically increasing. For example, if I want to find $$\log_2(b)$$ We can first express it as $$|\log_2(b)-x|<\epsilon$$ But how can I express it as $$|L-A(x_n)|<B(\epsilon)$$ where B is composed of only simple functions (i.e. exactly calcuable) and using the property that $A(x_n) > x_n$

Answer 1

The archetypal method to evaluate "specific values" defined by transcendental functions is the Taylor series.

The approximations are polynomials with terms computed as $\dfrac{f^{(n)}(x_0)}{n!}(x-x_0)^n$, where $x$ is the value of the argument for which you want to evaluate the function, and $x_0$ a value at which the computation of these derivatives is easy. When $x$ lies in the radius of convergence of the series, you do obtain better and better approximations (except maybe for the first terms).

E.g. to obtain $\ln\dfrac32$, you use $x_0=1$, and the successive approximations are

$$\frac12,\frac12-\frac1{2\cdot2^2},\frac12-\frac1{2\cdot2^2}+\frac1{3\cdot2^3},\frac12-\frac1{2\cdot2^2}+\frac1{3\cdot2^3}-\frac1{4\cdot2^4},\cdots$$

The errors are $0.094534892,-0.030465108,0.011201559,-0.004423441,\cdots$ They are roughly halved with every new term. Notice that the computation only involves fractions.

---

I am not aware of a general theory to construct similar sequences using other polynomials than Taylor's, or other expressions than polynomials, except for the continuous fraction approach.

Answer 2

I'm sorry that I don't have a complete answer for you, but I'll attempt to help in two ways: (i) by rephrasing the question and (ii) by providing a widget that you can use to experiment with various choices of $A$ and see if inspiration strikes you.

(i) Here is my interpretation of the problem:

You want fixed point iterative method (i.e., $x_{n+1}=A(x_n)$), subject to the additional constraint that the sequence is increasing (i.e., $A(x_n) \geq x_n$). Essentially, you want a fixed point iterative method that starts with a guess $x_0 < L$ and then never overshoots.

This seems like a tall order. There exist numerous iterative methods, but I don't know of any offhand that will give the monotonicity property you want. Bisection method might give you monotonicity, but isn't of the form you asked for.

For instance, to solve the equation $f(x)=0$, Newton's method asks us to iterate $$ x_{n+1} = A(x_n) $$ where $$ A(x) = x - \frac{f(x)}{f'(x)}. $$ We want to solve $x = \log_2(b)$. Squaring both sides, this is equivalent to $2^x = b$, so $2^x-b = 0$ and thus we can try $f(x)=2^x-b$ in Newton's method. So, $$ A(x) = x - \frac{f(x)}{f'(x)} = x - \frac{2^x-b}{\ln(2)2^x} $$ However, as one can check (I did, it took more time than I'd like to admit), this function $A$ has the property that if $y \leq \log_2(b)$ then $y \leq \log_2(b) \leq A(y)$. So, approximation from below cannot be achieved with this $A$ (note: if you want your sequence $(x_n)$ to be monotonically increasing and converge to $\log_2(b)$, then it is a necessary condition that $x_n \leq \log_2(b)$ for every $n$).

(ii) You (or anyone) can use the following R code to test various A

#
# you want to solve for the true value of a function "true" at a point "b",
# we you want to do this by iterating a function # A
#

true <- function(b) log(b,2)                  # the true value to test against
A <- function(x,b) x - (2^x-b)/(log(2)*2^x)   # Newton's method for computing log_2(b)        

Iterate <- function( f, b=3, N=8, initial=NULL ) {
    if (is.null(initial)) initial <- 0.3     # small enough to be \leq \log_2(b)
    n <- 1:N
    a <- rep( initial, N )
    for (j in 2:N) { a[j] <- f(a[j-1],b) }
    plot( n, a, las=1 )
    abline( h=true(b), lty=3 )
    a
}

Iterate(A)
#

Edit: to run that code online, you might be able to use https://rweb.webapps.cla.umn.edu/Rweb/Rweb.general.html the author of whom once taught a class I took at the U of M.

Sorry for not answering your question completely, but I hope this was at least helpful.