Изменения

Перейти к: навигация, поиск
м
rollbackEdits.php mass rollback
Предикат, определяющий взаимное расположение точек <tex>c_1</tex> и <tex>c_2</tex> по ординате, выглядит следующим образом:
<tex>K = (r_2 \cdot \sin \alpha + y_2) - (r_4 \cdot \sin \beta + y_4) = (r_2 \cdot frac{y_1 - y_2}{r_1 + r_2} + y_2) - (r_4 \frac{y_3 - y_4}{r_3 + r_4} + y_4)</tex> Т.к. <tex> r_1 + r_2 > 0, r_3 + r_4 > 0</tex>, то можно оценивать знак выражения <tex>T = K (r_1 + r_2) (r_3 + r_4)</tex> <tex>T = (r_2 (y_1 - y_2)+y_2 (r_1+r_2)) (r_3+r_4) - (r_4 (y_3-y_4)+y_4 (r_3+r_4)) (r_1+r_2) = \\= (y_1 r_2 + y_2 r_1)(r_3+r_4) - (y_3 r_4 + y_4 r_3)(r_1+r_2)</tex> Рассмотрим это выражение в дабловой арифметике. Обозначим за <tex>F(p_1, p_2, \ldots , p_n) = (1 + \delta_{p_1}) (1 + \delta_{p_2}) \ldots (1 + \delta_{p_n})</tex> <tex>\tilde{T} = (y_1 \otimes r_2 \oplus y_2 \otimes r_1)(r_3 \oplus r_4) \ominus (y_3 \otimes r_4 \oplus y_4 \otimes r_3)(r_1 \oplus r_2) =</tex> <tex>= [(y_1 r_2 F(1,2) + y_2 r_1 F(3,4))(r_3+r_4) F(5,6,7) - \\- (y_3 r_4 F(8,9) + y_4 r_3 F(10,11))(r_1+r_2) F(12,13,14)] F(15) =</tex> <tex>= y_1 r_2 (r_3+r_4)F(1,2,5,6,7,15)+ \\+ y_2 r_1 (r_3+r_4)F(3,4,5,6,7,15)- \\- y_3 r_4 (r_1 + r_2)F(8,9,12,13,14,15)-\\- y_4 r_3 (r_1+r_2)F(10,11,12,13,14,15)</tex> <tex>|\tilde{T} -T| = \\= |y_1 r_2 (r_3+r_4)(F(1,2,5,6,7,15)-1) + \\+ y_2 r_1 (r_3+r_4)(F(3,4,5,6,7,15)-1) - \\- y_3 r_4 (r_1+r_2)(F(8,9,12,13,14,15)-1) -\\- y_4 r_3 (r_1+r_2)(F(10,11,12,13,14,15)-1)| \leq \\\leq |y_1 r_2 (r_3+r_4)| \cdot |(F(1,2,5,6,7,15) - 1)| + \\+ |y_2 r_1 (r_3+r_4 )| \cdot |(F(3,4,5,6,7,15)-1)| + \frac{\+ |y_3 r_4 (r_1+r_2)| \cdot |(F(8,9,12,13,14,15)- 1)| +\\+ |y_4 r_3 (r_1+r_2)| \cdot |(F(10,11,12,13,14,15)-1)|</tex> Теперь раскрываем скобки во всех <tex>F</tex>. Пользуемся тем, что <tex>|\sum{p_i}| \leq \sum{|p_i|}</tex> и <tex> |\delta_i| \leq \varepsilon_m </tex>.Получаем следующее: <tex>|\tilde{T}-T| \leq \\\leq |y_1 r_2 (r_3+r_4)| \cdot (6\varepsilon_m + 15\varepsilon_m^2 + 20\varepsilon_m^3 + 15\varepsilon_m^4 + 6\varepsilon_m^5 + \varepsilon_m^6) + \\+ |y_2 r_1 (r_3 + r_4)| \cdot (6\varepsilon_m + 15\varepsilon_m^2 + 20\varepsilon_m^3 + 15\varepsilon_m^4 + 6\varepsilon_m^5 + \varepsilon_m^6) + \\+ |y_3 r_4 (r_1+r_2)| \cdot (6\varepsilon_m + 15\varepsilon_m^2 + 20\varepsilon_m^3 + 15\varepsilon_m^4 + 6\varepsilon_m^5 + \varepsilon_m^6) +\\+ |y_4 r_3 (r_1+r_2)| \cdot (6\varepsilon_m + 15\varepsilon_m^2 + 20\varepsilon_m^3 + 15\varepsilon_m^4 + 6\varepsilon_m^5 + \varepsilon_m^6) = \\= (|y_1 r_2 (r_3+r_4)|+|y_2 r_1 (r_3+r_4)|+|y_3 r_4 (r_1+r_2)|+|y_4 r_3 (r_1+r_2)|) \cdot \\\cdot (6\varepsilon_m + 15\varepsilon_m^2 + 20\varepsilon_m^3 + 15\varepsilon_m^4 + 6\varepsilon_m^5 + \varepsilon_m^6)</tex> Обозначим <tex>T' = |y_1 r_2 (r_3+r_4)|+|y_2 r_1 (r_3+r_4)|+|y_3 r_4 (r_1+r_2)|+|y_4 r_3 (r_1+r_2)|</tex> Тогда <tex>|\tilde{T} -T| \leq T' \cdot (6\varepsilon_m + 15\varepsilon_m^2 + 20\varepsilon_m^3 + 15\varepsilon_m^4 + 6\varepsilon_m^5 + y_4\varepsilon_m^6)</tex> <tex>T' \leq \tilde{T'} \frac{1}{(1 - \varepsilon_m)^6} = \tilde{T'} (1 + 6 \varepsilon_m + 21 \varepsilon_m^2 + 56 \varepsilon_m^3 + \ldots)</tex> <tex>|\tilde{T} - T| \leq \tilde{\epsilon} \leq \tilde{T'} (1 + 6 \varepsilon_m + 21 \varepsilon_m^2 + \ldots) (6 \varepsilon_m + 15 \varepsilon_m^2 + 20 \varepsilon_m^3 + \ldots)</tex>
[[Категория: Вычислительная геометрия]]
1632
правки

Навигация