Numerical certification: Difference between revisions

Revision as of 13:49, 1 March 2019

Revision as of 15:54, 1 March 2019

Line 31:

=== Interval Newton ===

The fixed points of the Newton operator [[Newton's method]] for a square system of functions <math>F:\mathbb{C}^n\rightarrow\mathbb{C}^n</math> correspond to the roots of <math>f</math>. In more generality, suppose thatSuppose <math>G:\mathbb{C}^n\rightarrow\mathbb{C}^n</math> is a function whose fixed points correspond to the roots of <math>F</math>. IntervalFor Newton {{citation needed|reason=don't have time to figure out how to reference a book right now|November 9example, 2018}}, Krawczyk {{citation needed|reason=don't have time to figure out how to reference a book right now|November 9, 2018}}, and related methods use such functions to establish the existenceNewton andoperator uniquenesshas ofthis rootsproperty. within aSuppose regionthat <math>I</math> usingis topologicala methods:region, then,

# 1 If <math>G</math> maps a region <math>I</math> into itself, i.e., <math>G(I)\subseteq I</math>, then by [[Brouwer fixed-point theorem]], <math>G</math> has at least one fixed point in <math>I</math>, and, hence <math>F</math> has at least one root in <math>I</math>.

# 2 If <math>FG</math> is a [[contraction mappingcontractive]] in a region containing <math>I</math>, then there is at most one root of <math>F</math> in <math>I</math>.

These properties can often be established using interval arithmetic. For example, the [[Interval_arithmetic#Interval_Newton_method|interval Newton operator]] replaces <math>x</math> with the region <math>I</math> containing <math>x</math>. For example, the interval Newton operator is

# 2 If <math>F</math> is a [[contraction mapping]] in a region <math>I</math>, then there is at most one root of <math>F</math> in <math>I</math>.

<math display="block">N(I)=m(I)+D(I)^{-1}\cdot(I-m(I)),</math>

where <math>m(I)</math> is a point (often the [[center of mass]]) of <math>I</math> and <math>D(I)^{-1}</math> is an interval over-approximation to the set inverses of derivatives for <math>x\in I</math>. Then, one can show that if <math>x</math> is a fixed point of

Interval Newton {{citation needed|reason=don't have time to figure out how to reference a book right now|November 9, 2018}}, Krawczyk {{citation needed|reason=don't have time to figure out how to reference a book right now|November 9, 2018}}, and related methods use such functions to establish the existence and uniqueness of roots within a region <math>I</math> using topological methods:

The basic form of Newton's method replaces the input in the iterator with an interval approximation. In other words