Content deleted Content added
MichaelBurr (talk | contribs) |
MichaelBurr (talk | contribs) →Interval Newton Method: Wrote section on interval Newton. |
||
Line 39:
====Interval Newton Method====
In the univariate case, Newton's method can be directly generalized to certify a root over an interval. For an interval <math>J</math>, let <math>m(J)</math> be the midpoint of <math>J</math>. Then, the interval Newton operator applied to <math>J</math> is
:<math>IN(J)=m(J)-F(m(J))/F'(J).</math>
In practice, any interval containing <math>F'(J)</math> can be used in this computation. If <math>x</math> is a root of <math>F</math>, then by the [[mean value theorem]], there is some <math>c\in J</math> such that <math>F(m(J))-F'(c)(m(J)-x)=F(x)=0</math>. In other words, <math>F(m(J))=F'(c)(m(J)-x)</math>. Since <math>F'(J)</math> contains the inverse of <math>F</math> at all points of <math>J</math>, it follows that <math>m(J)-x\in F(m(J))/F'(J)</math>. Therefore, <math>x=m(J)-(m(J)-x)\in IN(J)</math>.
Furthermore, if <math>0\not\in F'(J)</math>, then either <math>m(J)</math> is a root of <math>F</math> and <math>IN(J)=\{m(J)\}</math> or <math>m(J)\not\in IN(J)</math>. Therefore, <math>J\cap N(J)</math> is at most half the width of <math>J</math>. Therefore, if there is some root of <math>F</math> in <math>J</math>, the iterative procedure of replacing <math>J</math> by <math>J\cap IN(J)</math> will converge to this root. If, on the other hand, there is no root of <math>F</math> in <math>J</math>, this iterative procedure will eventually produce an empty interval, a witness to the nonexistence of roots.
See [[Interval_arithmetic#Interval_Newton_method|interval Newton method]] for higher dimensional analogues of this approach.
====Krawczyck Method====
| |||