sequence | Beni Bogoşel's blog

Iterative algorithms – Convergence rates

April 13, 2024 beni22sof Leave a comment

In optimization and any other iterative numerical algorithms, we are interested in having convergence estimates for all algorithms. We are not only interested in showing that the error goes to ${0}$ , although that is essential, but also at what speed the error goes to ${0}$ . An algorithm which converges quicker is a better choice in all cases!

Generally, there are two points of view for convergence: convergence in terms of ${1/n}$ where ${n}$ is the number of iterations or having a comparison between the error at iteration ${n+1}$ and the error at the iteration ${n}$ . I will take the latter point of view below.

To fix the ideas, denote ${e_n}$ the error estimate for ${|x_n-x^*|}$ , where ${x_n}$ is the current iterate and ${x^*}$ is the solution to the problem.

We have the following standard classification:

linear convergence: there exists ${q \in (0,1)}$ such that ${r_{i+1} \leq q r_i}$
${\star}$ the constant ${q \in (0,1)}$ is called the convergence ratio ${\star}$ it is easy to show that ${r_i \leq q^i r_0}$ , so in particular ${r_i \rightarrow 0}$ .
sublinear convergence: ${r_i \rightarrow 0}$ but is not linearly converging
superlinear convergence: ${r_i\rightarrow 0}$ with any positive convergence ratio
${\star}$ sufficient condition: ${\lim\limits_{i\rightarrow \infty} (r_{i+1}/{r_i}) =0}$
{convergence of order ${p>1}$ }: there exists ${C>0}$ such that for ${i}$ large enough $\displaystyle r_{i+1} \leq Cr_i^p$
${\star}$ ${p}$ is called the order of convergence
${\star}$ the case ${p=2}$ has a special name: quadratic convergence

To underline the significant difference between linear and superlinear convergence consider the following examples: Let ${\gamma \in (0,1)}$ . Then:

${(\gamma^n)}$ converges linearly to zero, but not superlinearly
${(\gamma^{n^2})}$ converges superlinearly to zero, but not quadratically
${(\gamma^{2^n})}$ converges to zero quadratically

Quadratic convergence is much faster than linear convergence.

Among optimization algorithm, the simpler ones are usually linearly convergent (bracketing algorithms: trisection, Golden search, Bisection algorithm, gradient descent). Algorithms involving higher order information or approximation are generally superlinear (Secant method, Newton, BFGS or LBFGS in higher dimensions etc.).

There is a huge difference between linear convergence and super-linear convergence. If a faster algorithm is available using it is surely useful!

Categories: Algorithms, Analysis, Calculus of Variations, Numerical Analysis, Optimization Tags: algorithm, convergence, optimization, sequence, speed

Sum of floors of multiples of the Golden Ratio

July 25, 2020 beni22sof 1 comment

Propose an algorithm for computing

$\displaystyle S_n = \sum_{i=1}^n \lfloor i\varphi \rfloor$

for ${n=10^{16}}$ , where ${\varphi= \frac{\sqrt{5}+1}{2}}$ is the golden ratio. The sum ${S_n}$ is the sum of the first ${n}$ terms in the so called lower Wythoff sequence.

Solution: Computing a floor function and a multiplication is not complicated, therefore proposing a ${O(n)}$ algorithm for computing ${S_n}$ is trivial. However, such an algorithm is not viable for ${n = 10^{16}}$ .

The path to a much more efficient algorithm goes through the notion of Beatty sequence. For a positive irrational number ${r>1}$ the associated Beatty sequence is ${(\lfloor nr\rfloor)_{n\geq 1}}$ . This notion becomes interesting when noting the following fact. If ${s>1}$ is defined by ${1/r+1/s=1}$ then the Beatty sequences ${(\lfloor nr\rfloor)_{n\geq 1}}$ and ${(\lfloor ns\rfloor)_{n\geq 1}}$ cover all the positive integers. The latter sequence is called the associated complementary Beatty sequence. Two proofs of this fact can be found in the Wikipedia link above.

It is obvious now that ${S_n}$ is just the partial sum of the Beatty sequence associated to ${\varphi}$ . Now let’s see what is the complementary sequence. A brief computation shows that the associated ${s}$ is given by ${s=\varphi+1}$ , which shows that the terms which are not of the form ${\lfloor i\varphi\rfloor}$ are not far from it. In order to see how this can give an efficient algorithm, let’s follow the instructions below:

denote by ${N = \lfloor n\varphi \rfloor}$ , the largest term in ${S_n}$ .
looking at all the integers up to ${N}$ , in view of the result regarding the Beatty sequences, they are either of the form ${\lfloor i\varphi \rfloor}$ or of the form ${\lfloor j(\varphi+1) \rfloor}$ (in the associated complementary sequence).
denote by ${J}$ the largest integer such that ${\lfloor j(\varphi+1) \rfloor< N}$ , which is given by ${J = \lfloor (N+1)/(\varphi+1)\rfloor}$ . Then, it is not difficult to see that ${S_n}$ is the difference between the sum of all positive integers up to ${N}$ and ${S_J+1+...+J}$ .
In the end we obtain
$\displaystyle S_n = N(N+1)/2 - S_J-J(J+1)/2.$
by convention, state that ${S_0=0}$ or ${S_1=1}$ .

The last item above shows that a recursive algorithm can be implemented in order to compute ${S_n}$ . Moreover, since the computation of ${S_n}$ is reduced to the computation of ${S_J}$ where ${J = \lfloor (\lfloor n\varphi\rfloor+1)/(\varphi+1)\rfloor\leq n \frac{\varphi}{\varphi+1}+\frac{1}{\varphi+1}}$ , the algorithm will converge very fast, since the sequence of upper bounds for ${J}$ converges exponentially to zero. Therefore, the algorithm obtained will have complexity ${O(\log n)}$ and will work for extremely large values of ${n}$ , provided the language you are using can handle the expected precision.

The algorithm for computing ${S_n}$ shown above can be used, for example, in computing sums related to elements in the Wythoff table, which can be expressed using Fibonacci numbers and terms in ${S_n}$ .

Other values of ${r}$ , like for example ${r=\sqrt{2}}$ (with ${s=2+\sqrt{2}}$ ) lead to other types of sums for which the same type of algorithm can be applied. It is likely that even cases where ${s}$ is not explicitly related to ${r}$ through an integer may be handled through a similar procedure (to be confirmed).

Categories: Algebra, Algorithms, Problem Solving, puzzles, Uncategorized Tags: algorithm, beatty, fibonacci, project euler, sequence, wythoff

Compute recurrent sequences fast

July 9, 2020 beni22sof 1 comment

In many programming questions the computation of a recurrent sequence might be necessary. One of the famous such sequences is the Fibonacci sequence defined by ${F_0=F_1=1}$ and

$\displaystyle F_{n+1}=F_n+F_{n-1},\ n \geq 1.$

Writing a code which computes ${F_n}$ for given ${n}$ is a no-brainer, but the complexity may vary much depending on the implementation. As it turns out, not everyone has the right reflexes when writing such a code. In the following I write some algorithmic variants and discuss their speed and complexity. In the end I’ll say a few words on how to compute quickly the ${n}$ -th sequence of any recurrence relation with fixed coefficients and fixed order.

First, remember that it is possible to have an exact formula:

$\displaystyle F_n = a\lambda_1^n+b\lambda_2^n$

where ${\lambda_i}$ are solutions of ${\lambda^2=\lambda+1}$ and ${a}$ and ${b}$ are found from ${F_0}$ and ${F_1}$ . Note that ${\lambda}$ are irrational, so when looking for an exact formula you might need to be careful for large ${n}$ . This could give you a ${O(\log n)}$ algorithm. The formula is explicit, but you need to compute two exponentials so it’s not really free. Moreover, this shows that values of ${F_n}$ grow exponentially fast so you’ll quickly overflow if you’re not working in arbitrary precision. Moreover, if you need to compute ${F_n (\mod p)}$ for really large ${n}$ , this might not be the simplest approach, since you’re working with irrationals.

1. Recursion. The simplest way to code the computation of ${F_n}$ is using a recursive function. Create a function fibonacci which depending on the value of ${n}$ returns ${1}$ if ${n \leq 2}$ or returns fibonacci( ${n-1}$ )+fibonacci( ${n-2}$ ). I remember using coding this when I was a beginner, thinking it was a nice idea… It turns out, however, that this approach has exponential complexity. If you’re not convinced, implement this and try to compute ${F_{10}, F_{20}}$ , etc. You’ll quickly see the exponential cost we’re talking about.

In order to see why, it is enough to note that when computing ${F_n}$ the algorithms needs to compute ${F_j}$ for all ${j <n}$ . Then for each ${F_j}$ one also needs to compute ${F_{j'}}$ for all ${j'<j}$ , etc. The only way this can be efficient if one stores the values already computed. This is called recursion with memoization, and should always be used when coding recursive tasks when there is a risk of computing the same value multiple times. However, the memoization has an ${O(n)}$ memory cost.

2. Iterative sequence. The second approach is more efficient. You only need two variables, ${A}$ and ${B}$ which store ${F_n}$ and ${F_{n-1}}$ . Then at each iteration, store ${F_{n}}$ in a temporary variable, change ${A}$ into ${F_{n}+F_{n-1}}$ and store the value of ${F_n}$ in ${B}$ . It is obvious that this approach costs ${O(n)}$ in execution time and ${O(1)}$ in memory. If you need to store all values of ${F_j}$ , ${j<n}$ you will also have ${O(n)}$ memory cost. As always, when doing this you can go up to ${n\approx 10^9}$ in reasonable computing time (even higher, depending on your hardware, or programming language). However, reaching ${n=10^{16}}$ is generally out of the question.

3. Matrix exponentiation. One interesing approach, which is really fast is rewriting the second order recurrence as a first order matrix recurrence:

$\displaystyle \begin{pmatrix} F_{n+1}\\ F_n \end{pmatrix} = \begin{pmatrix} 1& 1 \\ 1& 0 \end{pmatrix} \begin{pmatrix} F_{n}\\ F_{n-1} \end{pmatrix}$

This implies that ${\begin{pmatrix} F_{n+1}\\ F_n \end{pmatrix} = A^n \begin{pmatrix} F_{1}\\ F_0 \end{pmatrix}}$ where ${A = \begin{pmatrix} 1& 1 \\ 1& 0 \end{pmatrix}}$ . Therefore, in order to compute ${F_n}$ only a matrix exponential is needed. Using exponentiation by squaring this can be done in ${O(\log n)}$ time. At the end you will obtain an (exact) integer result or a result modulo whatever integer ${p}$ you want. So this is the way to go if you need to compute ${F_n}$ for extremely large ${n}$ .

Please note that you can generalize this to recurrences of the form

$\displaystyle x_{n+k+1} = a_{k}x_{n+k} + ... + a_1 x_1.$

It suffices to see that

$\displaystyle \begin{pmatrix} x_{n+k+1}\\ x_{n+k} \\ ... \\ x_{n+1} \end{pmatrix} = \begin{pmatrix} a_{k} & a_{k-1} & ... & a_2 & a_1 \\ 1 & 0 & ... & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & ... & 1& 0 \end{pmatrix} \begin{pmatrix} x_{n+k}\\ x_{n+k-1} \\ ... \\ x_{n} \end{pmatrix}$

so in the end you just need to compute the exponential of a bigger matrix. The complexity stays the same!

What to remember from this post?

Don’t use recursion (without memoization) when computing recurrent sequences. You won’t get very far and you’ll waste your ressources!
You can compute the ${n}$ -th value in recurrent sequences with constant coefficients with a ${O(\log n)}$ complexity using matrix exponentiation. This works well even for huge ${n}$ when working modulo a fixed integer ${p}$ .

Categories: Algebra, Algorithms, Programming Tags: algorithm, programming, sequence

Putnam 2018 – Problem B4

February 8, 2019 beni22sof Leave a comment

B4. Given a real number ${a}$ , we define a sequence by ${x_0=1}$ , ${x_1=x_2=a}$ and ${x_{n+1} = 2x_nx_{n-1}-x_{n-2}}$ for ${n \geq 2}$ . Prove that if ${x_n =0 }$ for some ${n}$ , then the sequence is periodic.

Putnam 2018, Problem B4

Solution: The path to the solution for this problem is really interesting. The first question that pops in mind when seeing the problem is: How do I prove that a sequence is periodic?. It’s not obvious from the given recurrence relation that this should happen, and what’s with the condition ${x_n = 0}$ ?

SEEMOUS 2014

March 18, 2014 beni22sof Leave a comment

Problem 1. Let ${n}$ be a nonzero natural number and ${f:\Bbb{R} \rightarrow \Bbb{R}\setminus \{0\}}$ be a function such that ${f(2014)=1-f(2013)}$ . Let ${x_1,..,x_n}$ be distinct real numbers. If

$\displaystyle \left| \begin{matrix} 1+f(x_1)& f(x_2)&f(x_3) & \cdots & f(x_n) \\ f(x_1) & 1+f(x_2) & f(x_3) & \cdots & f(x_n)\\ f(x_1) & f(x_2) &1+f(x_3) & \cdots & f(x_n) \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ f(x_1)& f(x_2) & f(x_3) & \cdots & 1+f(x_n) \end{matrix} \right|=0$

prove that ${f}$ is not continuous.

Problem 2. Consider the sequence ${(x_n)}$ given by

$\displaystyle x_1=2,\ \ x_{n+1}= \frac{x_n+1+\sqrt{x_n^2+2x_n+5}}{2},\ n \geq 2.$

Prove that the sequence ${y_n = \displaystyle \sum_{k=1}^n \frac{1}{x_k^2-1} ,\ n \geq 1}$ is convergent and find its limit.

Problem 3. Let ${A \in \mathcal{M}_n (\Bbb{C})}$ and ${a \in \Bbb{C},\ a \neq 0}$ such that ${A-A^* =2aI_n}$ , where ${A^* = (\overline A)^t}$ and ${\overline A}$ is the conjugate matrix of ${A}$ .

(a) Show that ${|\det(A)| \geq |a|^n}$ .

(b) Show that if ${|\det(A)|=|a|^n}$ then ${A=aI_n}$ .

Problem 4. a) Prove that $\lim_{n \rightarrow \infty} n \int_0^n \frac{\arctan(x/n)}{x(x^2+1)}dx=\frac{\pi}{2}$ .

b) Find the limit $\lim_{n \rightarrow \infty} n\left(n \int_0^n \frac{\arctan(x/n)}{x(x^2+1)}dx-\frac{\pi}{2} \right)$

Categories: Algebra, Analysis, Linear Algebra, Olympiad Tags: Algebra, continuity, integral, limit, matrix, SEEMOUS, sequence

Agregation 2013 – Analysis – Part 3

June 19, 2013 beni22sof Leave a comment

Part III: Muntz spaces and the Clarkson-Edros Theorem

Recall that for every ${\lambda \in \Bbb{N}}$ we define ${nu_\lambda(t)=t^\lambda,\ t \in [0,1]}$ and that ${\Lambda=(\lambda_n)_{n \in \Bbb{N}}}$ is a strictly increasing sequence of positive integers.

1. Suppose that ${\lambda_0=0}$ and $\sum_{n \geq 1}\frac{1}{\lambda_n} =\infty$ . Let ${k \in \Bbb{N}\setminus \Lambda}$ . Define ${Q_0=\nu_k}$ and by recurrence for ${n \in \Bbb{N}}$ define ${Q_{n+1}}$ by

$\displaystyle Q_{n+1}(x)=(\lambda_{n+1}x^{\lambda_{n+1}}\int_x^1 Q_n(t)t^{-1-\lambda_{n+1}}dt.$

(a) Calculate ${Q_1}$ and prove that ${\|Q_1\|_\infty \leq \displaystyle \left|1-\frac{k}{\lambda_1}\right|.}$

(b) Prove that for every ${n \geq 1}$ ${Q_n-\nu_k}$ is a linear combination of ${\nu_{\lambda_1},\nu_{\lambda_2},..,\nu_{\lambda_n}}$ .

(c) Prove that for every ${n \geq 1}$ we have ${\displaystyle\|Q_n\|_\infty \leq \prod_{i=1}^n \left|1-\frac{k}{\lambda_j}\right|}$ .

(d) Deduce that ${\nu_k \in \overline{M_\Lambda}}$ .

(e) Conclude that ${C([0,1])=\overline{M_\Lambda}}$ .

From here on suppose that ${\lambda_0}$ is arbitrary and the series $\sum_{n \geq 1}\frac{1}{\lambda_n}$ converges. For ${p \in \Bbb{N}}$ denote ${\rho_p(\Lambda)=\sum_{\lambda_n>p} \frac{1}{\lambda_n}}$ . For ${s \in \Bbb{N}}$ denote ${N_s(\Lambda)}$ the cardinal of the set ${\{n \in \Bbb{N} | \lambda_n\leq s\}}$ .

Nice characterization of convergence

October 6, 2011 beni22sof Leave a comment

Suppose $X$ is a topological space, and consider the sequence $(x_n)$ with the following property:

every subsequence $(x_{n_k})$ has a subsequence converging to $x$ .

Then $x_n \to x$ .

Increasing sequence of real numbers

April 17, 2010 beni22sof Leave a comment

Define the sequence $(a_n)_n$ in the following way: $a_0$ is a positive integer and
$a_{n+1}=\begin{cases} \frac{a_n}{5} & 5 | a_n \\ \lfloor \sqrt{5}a_n\rfloor & 5\nmid a_n \end{cases}$
Prove that from a certain moment, the sequence is increasing.

Categories: Olympiad, Problem Solving Tags: sequence

Interesting sequence

April 16, 2010 beni22sof Leave a comment

Consider $x_1,x_2,...$ an infinite sequence such that $\displaystyle | x_i-x_j| \geq \frac{1}{i+j}$ for any $i,j$ positive integers. Prove that if $x_n \in [0,c]$ for all $n$ , then $c \geq 1$ .
IMO Shortlist 2002

Categories: Analysis, IMO, Inequalities, Olympiad, Problem Solving Tags: sequence

Property of a Sequence

September 9, 2009 beni22sof 2 comments

We have bounded a sequence $(x_n)$ of real numbers such that $\lim\limits_{n\to \infty} (x_{n+1}-x_n)=0$ . Prove that the set of accumulation points of such a sequence is a closed interval.
Read more…

Categories: Analysis, Geometry, Problem Solving Tags: interval, limit, sequence

Beni Bogoşel's blog

Archive

Iterative algorithms – Convergence rates

Sum of floors of multiples of the Golden Ratio

Compute recurrent sequences fast

Putnam 2018 – Problem B4

SEEMOUS 2014

Agregation 2013 – Analysis – Part 3

Nice characterization of convergence

Increasing sequence of real numbers

Interesting sequence

Property of a Sequence

Beni Bogoşel

Blog Stats

Today’s Visitors

Stay connected

Blogroll

Archive

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Beni Bogoşel

Blog Stats

Today’s Visitors

Stay connected

Blogroll