Погрешность предиката левый поворот — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{в разработке}} hello»)
 
Строка 1: Строка 1:
 
{{в разработке}}
 
{{в разработке}}
hello
+
Пусть две точки заданны абсолютно точно, а одна - точка внешнего касания двух окружностей <tex>(o_1(x1, y1), r_1)</tex> и <tex>(o_2(x2, y2), r_2).</tex>
 +
Обозначим точку касания как <tex>c.</tex> Тогда:
 +
 
 +
<tex>\overrightarrow{o_1c} = \frac{r_1}{r_1 + r_2} \cdot \overrightarrow{o_1o_2}, \\
 +
\overrightarrow{o_1o_2} = (x_2 - x_1, y_2 - y_1) \\
 +
c_x = \frac{r_1}{r_1 + r_2} \cdot (x_2 - x_1) + x_1 = \frac{r_1}{r_1 + r_2} \cdot x_2 + \frac{r_2}{r_1 + r_2} \cdot x_1\\
 +
c_y = \frac{r_1}{r_1 + r_2} \cdot (y_2 - y_1) + y_1 = \frac{r_1}{r_1 + r_2} \cdot y_2 + \frac{r_2}{r_1 + r_2} \cdot y_1</tex>
 +
 
 +
Обозначим
 +
 
 +
<tex> v = (b - a) \times (c - a) = \\
 +
= (b_x - a_x) (\frac{r_1}{r_1 + r_2} \cdot y_2 + \frac{r_2}{r_1 + r_2} \cdot y_1 - a_y) - \\
 +
- (b_y - a_y) (\frac{r_1}{r_1 + r_2} \cdot x_2 + \frac{r_2}{r_1 + r_2} \cdot x_1 - a_x) = \\</tex>
 +
 
 +
<tex dpi = 140> = \frac{(b_x - a_x) (r_1 y_2 + r_2 y_1 - a_y (r_1 + r_2)) - (b_y - a_y) (r_1 x_2 + r_2 x_1 - a_x (r_1 + r_2))}{r_1 + r_2}</tex>.
 +
 
 +
Так как <tex> r_1 + r_2 > 0, </tex> то мы можем оценивать знак выражения <tex>k = v \cdot (r_1 + r_2)</tex>
 +
 
 +
<tex>k = (b_x - a_x) (r_1 (y_2 - a_y) + r_2 (y_1 - a_y)) - (b_y - a_y) (r_1 (x_2 - a_x) + r_2 (x_1 - a_x)) = \\
 +
= (b_x - a_x) r_1 (y_2 - a_y) + (b_x - a_x) r_2 (y_1 - a_y) - \\
 +
- (b_y - a_y) r_1 (x_2 - a_x) - (b_y - a_y) r_2 (x_1 - a_x)</tex>
 +
 
 +
Теперь распишем это выражение в дабловой арифметике.
 +
Для сокращения обозначим произведение <tex>(1 + \delta_{p_1}) \cdot (1 + \delta_{p_2}) \cdot \ldots \cdot (1 + \delta_{p_n})</tex> за
 +
<tex>F(p_1, p_2, \ldots , p_n)</tex>
 +
 
 +
<tex>\tilde{k} = (b_x \ominus a_x) \otimes (r_1 \otimes (y_2 \ominus a_y) \oplus r_2 \otimes (y_1 \ominus a_y)) \ominus \\
 +
        \ominus (b_y \ominus a_y) \otimes (r_1 \otimes (x_2 \ominus a_x) \oplus r_2 \otimes (x_1 \ominus a_x)) = \\
 +
= [(b_x - a_x) (r_1 (y_2 - a_y)F(1, 2) + r_2 (y_1 - a_y)F(3, 4))F(5, 6, 7) - \\
 +
- (b_y - a_y) (r_1 (x_2 - a_x)F(8, 9) + r_2 (x_1 - a_x)F(10, 11))F(12, 13, 14)]F(15) = \\
 +
= (b_x - a_x) r_1 (y_2 - a_y)F(1, 2, 5, 6, 7, 15) + \\
 +
+ (b_x - a_x) r_2 (y_1 - a_y)F(3, 4, 5, 6, 7, 15) - \\
 +
- (b_y - a_y) r_1 (x_2 - a_x)F(8, 9, 12, 13, 14, 15) - \\
 +
- (b_y - a_y) r_2 (x_1 - a_x)F(10, 11, 12, 13, 14, 15)
 +
</tex>
 +
 
 +
 
 +
<tex> |\delta_i| \leq \varepsilon_m </tex>
 +
 
 +
Заметим, что <tex> k\approx \tilde{k} </tex>
 +
 
 +
Теперь оценим абсолютную погрешность <tex> \epsilon = |k - \tilde{k}|. </tex>
 +
 
 +
<tex> |k - \tilde{k}| = \\
 +
=|r_1(b_x - a_x)(y_2 - a_y) + \\
 +
+ r_2(b_x - a_x)(y_1 - a_y) - \\
 +
- r_1(b_y - a_y)(x_2 - a_x) - \\
 +
- r_2(b_y - a_y)(x_1 - a_x) - \\
 +
- r_1(b_x - a_x)(y_2 - a_y) \cdot F(1, 2, 5, 6, 7, 15) - \\
 +
- r_2(b_x - a_x)(y_1 - a_y) \cdot F(3, 4, 5, 6, 7, 15) + \\
 +
+ r_1(b_y - a_y)(x_2 - a_x) \cdot F(8, 9, 12, 13, 14, 15) + \\
 +
+ r_2(b_y - a_y)(x_1 - a_x) \cdot F(10, 11, 12, 13, 14, 15)| = \\
 +
= |r_1(b_x - a_x)(y_2 - a_y) \cdot (F(1, 2, 5, 6, 7, 15) - 1) - \\
 +
- r_2(b_x - a_x)(y_1 - a_y) \cdot (F(3, 4, 5, 6, 7, 15) - 1) + \\
 +
+ r_1(b_y - a_y)(x_2 - a_x) \cdot (F(8, 9, 12, 13, 14, 15) - 1) + \\
 +
+ r_2(b_y - a_y)(x_1 - a_x) \cdot (F(10, 11, 12, 13, 14, 15) - 1)| \leq \\
 +
\leq |r_1(b_x - a_x)(y_2 - a_y)| \cdot |(F(1, 2, 5, 6, 7, 15) - 1)| + \\
 +
+ |r_2(b_x - a_x)(y_1 - a_y)| \cdot |(F(3, 4, 5, 6, 7, 15) - 1)| + \\
 +
+ |r_1(b_y - a_y)(x_2 - a_x)| \cdot |(F(8, 9, 12, 13, 14, 15) - 1)| + \\
 +
+ |r_2(b_y - a_y)(x_1 - a_x)| \cdot |(F(10, 11, 12, 13, 14, 15) - 1)| = \\
 +
</tex>
 +
 
 +
 
 +
Пусть <tex> t = (|(b_x - a_x) (c_y - a_y)| + |(b_y - a_y) (c_x - a_x)|).</tex> Получаем, что
 +
 
 +
<tex> \epsilon = |v - \tilde{v}| \leq t \cdot (4 \varepsilon_m + 6 \varepsilon_m^2 + 4 \varepsilon_m^3 + \varepsilon_m^4). </tex>
 +
 
 +
<tex>\tilde {t} = (|(b_x - a_x) (c_y - a_y) (1 + \delta_1) (1 + \delta_2) (1 + \delta_3)| + \\
 +
+ |(b_y - a_y) (c_x - a_x) (1 + \delta_4) (1 + \delta_5) (1 + \delta_6)|) (1 + \delta_7) \geq \\
 +
\geq |(b_x - a_x) (c_y - a_y) (1 - \varepsilon_m)^3)|(1 - \varepsilon_m) + \\
 +
+ |(b_y - a_y) (c_x - a_x) (1 - \varepsilon_m)^3)|(1 - \varepsilon_m) = \\
 +
= |(b_x - a_x) (c_y - a_y)| (1 - \varepsilon_m)^4 + |(b_y - a_y) (c_x - a_x)| (1 - \varepsilon_m)^4 = \\
 +
= (|(b_x - a_x) (c_y - a_y)| + |(b_y - a_y) (c_x - a_x)|) (1 - \varepsilon_m)^4 = t \cdot (1 - \varepsilon_m)^4</tex>
 +
 
 +
Итого:
 +
 
 +
<tex> t \leq \tilde{t} \frac{1}{(1 - \varepsilon_m)^4} = \tilde{t} (1 + 4 \varepsilon_m + 10 \varepsilon_m^2 + 20 \varepsilon_m^3 + \cdots) </tex>
 +
 
 +
<tex> \epsilon = |v - \tilde{v}| \leq \tilde{\epsilon} \leq \tilde{t} (1 +  4 \varepsilon_m + 10 \varepsilon_m^2 + 20 \varepsilon_m^3 + \cdots) (4 \varepsilon_m + 6 \varepsilon_m^2 + 4 \varepsilon_m^3 + \varepsilon_m^4) </tex>

Версия 03:06, 30 января 2012

Эта статья находится в разработке!

Пусть две точки заданны абсолютно точно, а одна - точка внешнего касания двух окружностей [math](o_1(x1, y1), r_1)[/math] и [math](o_2(x2, y2), r_2).[/math] Обозначим точку касания как [math]c.[/math] Тогда:

[math]\overrightarrow{o_1c} = \frac{r_1}{r_1 + r_2} \cdot \overrightarrow{o_1o_2}, \\ \overrightarrow{o_1o_2} = (x_2 - x_1, y_2 - y_1) \\ c_x = \frac{r_1}{r_1 + r_2} \cdot (x_2 - x_1) + x_1 = \frac{r_1}{r_1 + r_2} \cdot x_2 + \frac{r_2}{r_1 + r_2} \cdot x_1\\ c_y = \frac{r_1}{r_1 + r_2} \cdot (y_2 - y_1) + y_1 = \frac{r_1}{r_1 + r_2} \cdot y_2 + \frac{r_2}{r_1 + r_2} \cdot y_1[/math]

Обозначим

[math] v = (b - a) \times (c - a) = \\ = (b_x - a_x) (\frac{r_1}{r_1 + r_2} \cdot y_2 + \frac{r_2}{r_1 + r_2} \cdot y_1 - a_y) - \\ - (b_y - a_y) (\frac{r_1}{r_1 + r_2} \cdot x_2 + \frac{r_2}{r_1 + r_2} \cdot x_1 - a_x) = \\[/math]

[math] = \frac{(b_x - a_x) (r_1 y_2 + r_2 y_1 - a_y (r_1 + r_2)) - (b_y - a_y) (r_1 x_2 + r_2 x_1 - a_x (r_1 + r_2))}{r_1 + r_2}[/math].

Так как [math] r_1 + r_2 \gt 0, [/math] то мы можем оценивать знак выражения [math]k = v \cdot (r_1 + r_2)[/math]

[math]k = (b_x - a_x) (r_1 (y_2 - a_y) + r_2 (y_1 - a_y)) - (b_y - a_y) (r_1 (x_2 - a_x) + r_2 (x_1 - a_x)) = \\ = (b_x - a_x) r_1 (y_2 - a_y) + (b_x - a_x) r_2 (y_1 - a_y) - \\ - (b_y - a_y) r_1 (x_2 - a_x) - (b_y - a_y) r_2 (x_1 - a_x)[/math]

Теперь распишем это выражение в дабловой арифметике. Для сокращения обозначим произведение [math](1 + \delta_{p_1}) \cdot (1 + \delta_{p_2}) \cdot \ldots \cdot (1 + \delta_{p_n})[/math] за [math]F(p_1, p_2, \ldots , p_n)[/math]

[math]\tilde{k} = (b_x \ominus a_x) \otimes (r_1 \otimes (y_2 \ominus a_y) \oplus r_2 \otimes (y_1 \ominus a_y)) \ominus \\ \ominus (b_y \ominus a_y) \otimes (r_1 \otimes (x_2 \ominus a_x) \oplus r_2 \otimes (x_1 \ominus a_x)) = \\ = [(b_x - a_x) (r_1 (y_2 - a_y)F(1, 2) + r_2 (y_1 - a_y)F(3, 4))F(5, 6, 7) - \\ - (b_y - a_y) (r_1 (x_2 - a_x)F(8, 9) + r_2 (x_1 - a_x)F(10, 11))F(12, 13, 14)]F(15) = \\ = (b_x - a_x) r_1 (y_2 - a_y)F(1, 2, 5, 6, 7, 15) + \\ + (b_x - a_x) r_2 (y_1 - a_y)F(3, 4, 5, 6, 7, 15) - \\ - (b_y - a_y) r_1 (x_2 - a_x)F(8, 9, 12, 13, 14, 15) - \\ - (b_y - a_y) r_2 (x_1 - a_x)F(10, 11, 12, 13, 14, 15) [/math]


[math] |\delta_i| \leq \varepsilon_m [/math]

Заметим, что [math] k\approx \tilde{k} [/math]

Теперь оценим абсолютную погрешность [math] \epsilon = |k - \tilde{k}|. [/math]

[math] |k - \tilde{k}| = \\ =|r_1(b_x - a_x)(y_2 - a_y) + \\ + r_2(b_x - a_x)(y_1 - a_y) - \\ - r_1(b_y - a_y)(x_2 - a_x) - \\ - r_2(b_y - a_y)(x_1 - a_x) - \\ - r_1(b_x - a_x)(y_2 - a_y) \cdot F(1, 2, 5, 6, 7, 15) - \\ - r_2(b_x - a_x)(y_1 - a_y) \cdot F(3, 4, 5, 6, 7, 15) + \\ + r_1(b_y - a_y)(x_2 - a_x) \cdot F(8, 9, 12, 13, 14, 15) + \\ + r_2(b_y - a_y)(x_1 - a_x) \cdot F(10, 11, 12, 13, 14, 15)| = \\ = |r_1(b_x - a_x)(y_2 - a_y) \cdot (F(1, 2, 5, 6, 7, 15) - 1) - \\ - r_2(b_x - a_x)(y_1 - a_y) \cdot (F(3, 4, 5, 6, 7, 15) - 1) + \\ + r_1(b_y - a_y)(x_2 - a_x) \cdot (F(8, 9, 12, 13, 14, 15) - 1) + \\ + r_2(b_y - a_y)(x_1 - a_x) \cdot (F(10, 11, 12, 13, 14, 15) - 1)| \leq \\ \leq |r_1(b_x - a_x)(y_2 - a_y)| \cdot |(F(1, 2, 5, 6, 7, 15) - 1)| + \\ + |r_2(b_x - a_x)(y_1 - a_y)| \cdot |(F(3, 4, 5, 6, 7, 15) - 1)| + \\ + |r_1(b_y - a_y)(x_2 - a_x)| \cdot |(F(8, 9, 12, 13, 14, 15) - 1)| + \\ + |r_2(b_y - a_y)(x_1 - a_x)| \cdot |(F(10, 11, 12, 13, 14, 15) - 1)| = \\ [/math]


Пусть [math] t = (|(b_x - a_x) (c_y - a_y)| + |(b_y - a_y) (c_x - a_x)|).[/math] Получаем, что

[math] \epsilon = |v - \tilde{v}| \leq t \cdot (4 \varepsilon_m + 6 \varepsilon_m^2 + 4 \varepsilon_m^3 + \varepsilon_m^4). [/math]

[math]\tilde {t} = (|(b_x - a_x) (c_y - a_y) (1 + \delta_1) (1 + \delta_2) (1 + \delta_3)| + \\ + |(b_y - a_y) (c_x - a_x) (1 + \delta_4) (1 + \delta_5) (1 + \delta_6)|) (1 + \delta_7) \geq \\ \geq |(b_x - a_x) (c_y - a_y) (1 - \varepsilon_m)^3)|(1 - \varepsilon_m) + \\ + |(b_y - a_y) (c_x - a_x) (1 - \varepsilon_m)^3)|(1 - \varepsilon_m) = \\ = |(b_x - a_x) (c_y - a_y)| (1 - \varepsilon_m)^4 + |(b_y - a_y) (c_x - a_x)| (1 - \varepsilon_m)^4 = \\ = (|(b_x - a_x) (c_y - a_y)| + |(b_y - a_y) (c_x - a_x)|) (1 - \varepsilon_m)^4 = t \cdot (1 - \varepsilon_m)^4[/math]

Итого:

[math] t \leq \tilde{t} \frac{1}{(1 - \varepsilon_m)^4} = \tilde{t} (1 + 4 \varepsilon_m + 10 \varepsilon_m^2 + 20 \varepsilon_m^3 + \cdots) [/math]

[math] \epsilon = |v - \tilde{v}| \leq \tilde{\epsilon} \leq \tilde{t} (1 + 4 \varepsilon_m + 10 \varepsilon_m^2 + 20 \varepsilon_m^3 + \cdots) (4 \varepsilon_m + 6 \varepsilon_m^2 + 4 \varepsilon_m^3 + \varepsilon_m^4) [/math]