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.∎
随便看	LabeledGraph labeled graph LabelledDigraph labelled digraph LabelledStateTransitionSystem labelled state transition system LadderConnected ladder connected LagrangeInterpolationFormula Lagrange interpolation formula LagrangeMultiplierAppliedToTheLegendreTransform Lagrange multiplier applied to the Legendre transform LagrangeMultiplierMethod Lagrange multiplier method LagrangeMultiplierMethodProofOf Lagrange multiplier method, proof of LagrangeMultipliersOnBanachSpaces Lagrange multipliers on Banach spaces LagrangeMultipliersOnManifolds Lagrange multipliers on manifolds LagrangesFoursquareTheorem LagrangesIdentity LagrangesTheorem Lagrange’s four-square theorem Lagrange’s identity