interval halving converges linearly

Theorem 1.

The interval halving algorithm converges linearly.

Proof.

To see that interval halving (or bisection) converges linearly we use the alternative definition of linear convergence that says that $|x_{i+1}-x_{i}|<c|x_{i}-x_{i-1}|$ for some constant $1>c>0$ .

In the case of interval halving, $|x_{i+1}-x_{i}|$ is the length of the interval we should search for the solution in and has $x_{i+2}$ as its midpoint. We have then that this interval has half the length of the previous interval which means, $\\mathit{length}_{i+1}=\\frac{1}{2}\\mathit{length}_{i}$ . Thus $c=1/2$ and we have exact linear convergence.∎

单词	IntervalHalvingConvergesLinearly
释义	interval halving converges linearly Theorem 1. The interval halving algorithm converges linearly. Proof. To see that interval halving (or bisection) converges linearly we use the alternative definition of linear convergence that says that $\|x_{i+1}-x_{i}\|<c\|x_{i}-x_{i-1}\|$ for some constant $1>c>0$ . In the case of interval halving, $\|x_{i+1}-x_{i}\|$ is the length of the interval we should search for the solution in and has $x_{i+2}$ as its midpoint. We have then that this interval has half the length of the previous interval which means, $\\mathit{length}_{i+1}=\\frac{1}{2}\\mathit{length}_{i}$ . Thus $c=1/2$ and we have exact linear convergence.∎
随便看	stationary increment StationaryPoint stationary point StationaryProcess stationary process StationarySet stationary set Statistic statistic StatisticalModel statistical model StatisticsOnPlanetMath statistics on PlanetMath SteinbergGroup Steinberg group SteinersTheorem SteinerSystem Steiner system Steiner’s theorem SteinitzTheorem Steinitz theorem SteinManifold Stein manifold StephenWilliamHawking Stephen William Hawking