ChapterZero

Contractivity

Given a C^1 function , what kind of bounds can you put on the size of an interval F(I) where I=[a,b] ? The fact that you can give a meaningful answer to this question is what allows for exact real arithmetic, because it allows you to perform exact operations on a number without knowing every digit of the number. That is, if we represent each number $x = [0.x_1x_2\ldots…]$ as a stream of digits, we can figure out how many digits of we need to determine the first digits of $y = [y_1y_2\ldots] = F(x)$ .

To answer the question, note that

$\displaystyle |F(I)| = \sup_{x,y \in I} |F(y) - F(x)| \leq \sup_{z \in I} |F^\prime(z)|\sup_{x,y \in I} |y-x| = \sup_{z \in I} |F^\prime(z)| |I|$

We call the quantity $\sup_{z\in I} |F^\prime(z)|$ the contractivity of over , and denote it by $\text{con}^I F$ .

There is a clear correspondence between representing numbers as a sequence of digits and as nested intervals: $x=[0.x_1x_2\ldots]$ iff $x \in [0.x_1x_2\ldots x_n, 0.x_1x_2\ldots x_n + 10^{-n}]$ for all . Therefore each number has a clearly defined head of digits for each integer , and the length of the corresponding interval is $10^{1-m}$ . So, to get the first digits of y=F(x) , we need to ensure

$|F([x_1x_2\ldots x_n])| < 10^{1-m}.$

Using $\text{con}^{[0,1]} F |[x_1x_2\ldots x_n]| = \text{con}^{[0,1]} F 10^{1-n}$ as an upper bound, we see that
$n > \log_{10} \text{con}^{[0,1]} F + m$ is a sufficient condition.

This entry was posted on Tuesday, December 27th, 2005 at 2:05 am and is filed under Mathematics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Contractivity

Leave a Reply