Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [rate-of-convergence]

The tag has no usage guidance.

1
vote
0answers
54 views

Does Aitken's $\Delta^2$ method asymptotically improve rate of convergence?

Denoting $y_n = x_n-\frac{(x_{n+1}-x_n)^2}{x_{n+2}-2x_{n+1} +x_n}$ when $x_n\rightarrow_{n\rightarrow\infty} a $ with $p$ convergence order. I showed that $\lim_{n\rightarrow\infty} |\frac {y_n-a}{...
1
vote
1answer
29 views

Probability- $L^2 \implies \max$ tail inequality

I wonder if anyone can give a hint about whether the following is correct or wrong. If given a probability measure $P$, $D \in L^2(P)$ is a function. Is it true that $$ \max_{1\leq i\leq n} D(X_i) = ...
1
vote
1answer
73 views

How fast does $\,\big(1+\frac 1n\big)^n$ converges to e?

How fast does the sequence $(1+1/n)^n$ converge to $\mathrm{e}$? Is the difference more like $\frac1n$ or more like $\mathrm{e}^{-n}$?
0
votes
1answer
45 views

Does $2\sum\frac{1}{(2k+1)3^{2k+1}}$ converge to $\ln 2$ linearly?

Based on the fact that $$\frac{1}{2}\ln\frac{1+x}{1-x}=\sum_{k=0}^\infty\frac{x^{2k+1}}{2k+1}$$ and evaluating at $x=-1/3$, we can conclude $$\ln 2=2\sum_{k=0}^\infty \frac{1}{(2k+1)3^{2k+1}}\,.$$ ...
0
votes
0answers
24 views

The multiplier between 0.0 to 1.0 that cause 2 points collapse the fastest

I don't know what kind this problem is. May be it is similar as finding energy loss coefficient k in every turn in a spring motion simulation that has the shortest time to become stable? I have two ...
0
votes
0answers
16 views

What is the rate of convergence of the argmins of a sequence of uniformly convergent strictly convex functions?

From Theorem 2.1 and 2.2 in Kanniappan (1983) "Uniform convergence of convex optimization problems", if a sequence of strictly convex functions $f_n$ uniformly converge to a strictly convex function $...
0
votes
0answers
21 views

Potentially new method for obtaining asymptotic distribution of M-estimators

Disclaimer. I'm not quite sure this is the best venue for this question, but I'll give it a try... So, in a comment to this MO post, it was said that one can use the comment right after Remark 7.3 in ...
0
votes
0answers
56 views

Approximating rate of convergence for ODE algorithms

I have a problem with approximating ROC for numerical algorithms for solving ODE's. It's known, that the global error for Euler's method is of order $O(h)$, and for 4th order Runge Kutta it's $O(h^4)$....
0
votes
0answers
18 views

Rate of convergence of Karhunen–Loève expansion of Wiener process

I read some wikipedia page about wiener process and find the formula to approximate the Wiener process using Karhunen–Loève theorem. $$ {\displaystyle W(t)={\sqrt {2}}\sum _{k=1}^{\infty }Z_{k}{\frac {...
1
vote
0answers
25 views

Numerical estimation of the rate of convergence of a sequence of random variables

Let $(\Omega,\mathcal{A},\mathbb{P})$ be a probability space and $(X_n)_{n\geq 1}$ be a sequence of real valued random variables defined on $\Omega$. Suppose that there exists a sequence $a_n \...
3
votes
1answer
40 views

Comparing the grow rate of two functions with discrete domain

Consider all the possible ways to put $\{0,1\}$ in $m\in \mathbb{N}$ places. E.g., if $m=3$, then the number of possibilities is $8$ $$ \begin{pmatrix} 1 & 1 & 1\\ 1 & 1 & 0\\ 1 & ...
3
votes
1answer
108 views

Quadratic convergence of a specific iteration (Steffensen's method)

DEFINITION (QUADRATIC CONVERGENCE) : Let $\left\{x_k\right\}$ be a sequence of real numbers and $\xi \in \mathbb{R}$. We say that $x_k \to \xi$ quadratically if and only if \begin{align*} &(i) \...
0
votes
1answer
48 views

Asymptotic rate of the largest order statistic.

Let $X_1, \cdots, X_n$ be i.i.d. random variables with distribution $P$. Let $g$ be a measurable function with $P g = 0$ and $P g^2 = 1$. Show that $\max_{1 \leq i \leq n}|g(X_i)| = o_p (\sqrt{n})$. ...
0
votes
1answer
36 views

Properties of norms of inverse Hessians near a solution

In theorem 3.5 of the book on Numerical Optimization by Jorge Nocedal and Stephen J Wright, Second edition, is given the proof for the quadratic convergence to the solution of a sequence of iterates ...
3
votes
2answers
125 views

Rate of weak convergence of sin(nx)

Since $\sin(n\cdot)$ converges weakly to zero, we know that $$ \lim_{n\rightarrow\infty} \int_a^b g(x)\sin(nx)\mathrm{d}x = \int_a^b g(x)\cdot 0\,\mathrm{d}x = 0 $$ holds for all $g\in L^2([a,b])$. ...
0
votes
0answers
134 views

If fixed-point iteration has linear convergence, how can Newton's Method have quadratic convergence?

Newton's Method for finding the roots of a function can be considered a type of fixed point iteration of $g(x) = x - \frac{f(x)}{f'(x)}$, since $f(k) = 0 \rightarrow g(k) = k$. But it is well-known ...
1
vote
1answer
13 views

Flow rate and proportion

I'm wondering if there is a short cut for calculating the time taken for 2taps to fill and another tap to empty a tank apart from the usual way. For e g. two taps take 20minutes to for fill ...
1
vote
1answer
45 views

is there a better way to prove it?

$\{x^k\}$ converge super linaerly to $x^*$ meant $ \ \ \lim_{k\to\infty}\frac{||x^{k+1} - x^*||}{||x^k - x^*||^p}=r$ and $\ \ 0<p<2$ and $\ \ $$r$ is constant. is It true that The value ...
2
votes
0answers
39 views

Convergence rate of $\operatorname E|\langle X,f_n\rangle|^p$

Suppose that $X$ is a random element with values in a separable Hilbert space $\mathbb H$ such that $\operatorname EX=0$ and $\operatorname E\|X\|^2<\infty$. Suppose that $f_1,f_2,\ldots$ form an ...
9
votes
0answers
193 views

Convergence of a linear recurrence equation

Let $T \colon \mathbb{C}^n \to \mathbb{C}^n$ be a linear operator. Let $\{u_k\} \subset \mathbb{C}^n$ and $\{v_k\} \subset \mathbb{C}^n$ be two sequences of vectors. Suppose the spectral radius of $T$ ...
2
votes
2answers
29 views

Speed of convergence of an integral (whose complete version gives the Mascheroni constant)

Consider the following integral: $$ I(k):= \int_k^{+\infty} \frac{e^{-1/x} \log(x)}{x^2} dx\\ =-\int_0^{1/k} e^{-t} \log t \, dt, $$ where $k>0$. It is known that $\lim_{k \to 0} I(k)=\gamma$, ...
1
vote
0answers
47 views

Rate of Convergence of Function F(x) = f(x)/f′(x) using Newtons Method

Derive a formula for Newton’s method for the function $F(x) = f(x)/f′(x)$, where $f(x)$ is a function with simple zeros that is three times continuously differentiable. Show that the convergence of ...
1
vote
1answer
44 views

Estimate convergence order of a sequence

For a given real sequence $\{a_k\} \subset \mathbb{R}^n$, suppose the sequence satisfies relation $| a_k - a_{k-1} | \le \frac 1 k$. We know this does not guarantee the sequence to be Cauchy. If we ...
1
vote
0answers
133 views

Big O analysis and order of convergence summarized

I want to confirm my understanding about rate of convergence and Big O analysis, where the argument inside of $O$ is a function of the error between $X_n$ and what it's converging to $L$. My ...
2
votes
1answer
70 views

Convergence rate if a sequence $\{x_k\}$ satisfies that $x_{k} - x_{k-1} \le \frac {1} {k^{p}}$ where $p >1$

Suppose $\{x_k\} \subseteq X$ where $X$ is a Banach space. $\{x_k\}$ satisfies \begin{align*} \|x_k - x_{k-1} \| \le \frac 1 {k^p}, \end{align*} where $1 < p < 2$. The sequence is clearly Cauchy ...
0
votes
1answer
84 views

Estimate convergence rate for recurrences $a_{k} \le \frac{k}{k+2} a_{k-1}$ and $b_{k} \le \frac{k+\alpha}{k+2} b_{k-1}$

Suppose a positive sequence satisfies the recurrence $$a_k \le \frac{k}{k+2} a_{k-1}$$ for $k \ge 2$. If we do the expansion, then \begin{align*} a_k \le \frac{k}{k+2} a_{k-1} \le \dots \le \frac{6}{(...
1
vote
0answers
80 views

Estimate rate of convergence for a sequence to a limit

Suppose we have a sequence $\{x_k\} \subset X$ with $X$ being a Banach space satisfying $$\| x_k - x_{k-1} \| \le \frac{1}{k^2} C,$$ where $C$ is some positive constant. The sequence clearly has a ...
2
votes
1answer
860 views

sublinear rate of convergence in mathematical optimization

In Wiki page, the sublinear convergence rate refers that for a sequence $\{x_k\}$ with limit $L$, \begin{align*} \limsup \frac{\|x_{k+1} - L\|} {\|x_k - L\|} = 1. \end{align*} In most convex ...
5
votes
0answers
125 views

Limit of a sequence given by recurrence relation and convergence rate

Suppose we have a sequence $\{a_n\}_{n=0}^{\infty}$ which is generated by \begin{align*} a_{n+1} - \left(q+ \frac{A} {n+1} \right) a_n - \frac B n a_{n-1} = C, \end{align*} for $n \ge 1$, where $q, A, ...
2
votes
1answer
30 views

Convergence and order

Let $f \in L^1(\mathbb{R}^n)$, and $B_m = \left\{x \in \mathbb{R}^n \ | \ |x|< \frac{1}{m}\right\}$. Then $\int_{B_m} |f| = O\left(\frac{1}{m^\delta}\right)$ as $m \to \infty$ for some $\delta >...
0
votes
1answer
341 views

Rate of Convergence of a sequence of functions

I know that the rate of convergence $\mu$ of a convergent sequence $(x_n)_{n\in\mathbb N} \to x$ in $\mathbb R$ is given by $$\mu = \lim_{n\to\infty}\frac{|x_{n+1} - x|}{|x_n - x|}.$$ But if I have a ...
1
vote
0answers
764 views

Convergence Analysis of Regula Falsi method

I was reading about the convergence analysis of the regula falsi method in the book A friendly introduction to numerical analysis by B. Bradie. I got stuck in the last step where $e_n=\lambda e_{n-1}$...
0
votes
0answers
64 views

Rate of convergence of the logistic map

Given the logistic map $x_{n+1} = r x_n(1-x_n)$, it is well-known that if $0 \le r\le 1$, then $\lim_{n\rightarrow\infty} x_n = 0$ regardless of the value of $x_0\in(0,1)$. What is the asymptotic ...
1
vote
1answer
31 views

Alternate Characterization of Rate of Convergence

Let $\{x_n\}$ be a sequence converging to $L$. According to Wikipedia, if there exists a $\mu\in(0,1)$ satisfying $$\lim_{k→∞}\frac{|x_{k+1}−L|}{|x_k−L|}=μ$$ then we say $\{x_n\}$ converges ...
0
votes
1answer
279 views

Determine the order of the rate of convergence for these values

Consider the recurrence relation $x_n=2(x_{n-1}+x_{n-2})$ and the general solution $z_n=\alpha(1+\sqrt{3})^n+\beta(1-\sqrt{3})^n$. For which values of $\alpha,\beta\in\mathbb{R}$ does the ...
5
votes
1answer
75 views

Rate of $L_1$ loss in estimating density on $[0,1]$

Let $f$ be a density on $[0,1]$ and let $X_1,X_2,\ldots$ be $\textit{iid}$ $f$-distributed. Also, let $f_n$ denote the kernel density estimator, i.e. $$f_n(x) = \frac{1}{nh_n} \sum_{i=1}^n K\left(\...
0
votes
2answers
287 views

Rate of convergence of exp(-n)

I am trying to determine the rate of convergence of the sequence $ e^{-n}$ (as $n \to \infty$). I know that I need to find a sequence $\beta_n$ that converges to 0, that is larger than $\alpha_n - \...
1
vote
1answer
181 views

Sub-linear convergence rate in convex optimization

I learned the definition of sublinear rate of convergence from wikipedia, but I am not quite sure how to use it in practice. Specifically, I am studying the proof for linear and sub-linear rate of ...
0
votes
1answer
159 views

Rate of convergence definition.

I am confused about the definition of the rate of convergence. The first definition I have seen at (1) says, If a sequence $x_1, x_2, . . . , x_n$ converges to a value $r$ and if there exist real ...
0
votes
1answer
232 views

Estimate number of iterations based on rate of convergence and asymptotic error constant

I'm trying to estimate the number of iterations required to reach a certain accuracy ( tol < $10^{-8}$), based only on the rate of convergence and asymptotic error constant, without actually ...
-1
votes
2answers
451 views

Rates of convergence numerical analysis

I have been leaning about fixed point iterations, and have been introduced to the notion of rates of convergence, in the quadratic, and linear case. Consider a fixed point iteration $x_{n+1} = g(x_n)$,...
1
vote
0answers
68 views

Local rate of convergence for fixed point iteration with unique statonary point implies global?

Suppose one has a fixed point iteration $$x_{n+1}=f(x_n)$$ which is known to converge to a unique stationary point $x^*$, regardless of the initial value $x_0$. Suppose further that it is known that ...
2
votes
1answer
46 views

How fast can $\Sigma_{n=1}^{\infty}a_nr^n$ blow up as $r \to 1$?

Suppose I know $a_n \to 0$ as $n \to \infty$. How fast can $\Sigma_{n=1}^{\infty}a_nr^n$ blow up as $r \to 1$? In particular, can I say $(1-r)\Sigma_{n=1}^{\infty}a_nr^n \to 0$? If so, how can I ...
1
vote
2answers
8k views

How to show that regula falsi has linear rate of convergence?

How can we prove that regula falsi method has linear rate of convergence? I know how to do so for the secant method but I am unable to derive it for regula falsi. Any help is much appreciated. ...
0
votes
2answers
48 views

How fast does $a_n\to 0$ if $\sum a_n=1$

Let $a_n\ge 0.$ If $\sum a_n$ converges, say to 1 (such as a probability mass function), then by the Divergence Test we have $\lim_n a_n=0. $ However, can we say how fast it converges? I was ...
3
votes
2answers
318 views

Faster Convergence for the Smaller Values of the Riemann Zeta Function [duplicate]

I have a C++ program that uses the equation $$\zeta(s)=\sum_{n=1}^\infty\frac{1}{n^s}$$ to calculate the Riemann zeta function. This equation converges fast for larger values, like 183, but ...
0
votes
0answers
23 views

Notation f(x)<=O(g(x))

In writing a paper, I am using the notation $\beta_n\le O(n^{-3 })$ to mean any sequence converging to zero as fast as or even faster that $1/n^3$. Is this a standard notation?, and has anyone seen ...
0
votes
2answers
131 views

Find the instantaneous rate of change at $ x=1$

As I have said on my previous question ,I have a quiz tomorrow! And I need to get ready , but this question in my quiz review has been a problem for me! So basically it asks the instantaneous rate of ...
0
votes
2answers
46 views

Do $e^{c/n}$ and $1+\frac{c}{n}$ have the same rate of convergence as n grows to infinity?

I am wondering whether the functions $e^{c/n}$ and $1+\frac{c}{n}$ converge to one at the same rate as $n$ grows to infinity? I was trying to establish this based on Wikipedia's definitions of ...
-1
votes
1answer
326 views

Rate of convergence vs number of iteration

Can anyone explain to me the difference between rate of convergence and number of iterations for a numerical algorithm? Is it correct to say rate of convergence measure how fast the sequence approach ...