Next: 4.9.1 Formulation of the Up: 4. Nonlinear Polynomial Solvers Previous: 4.8.5 Implementation of rounded Contents Index

4.9 Interval Projected Polyhedron algorithm

Maekawa [246] and Maekawa and Patrikalakis [254,255] extended the PP algorithm to operate in rounded interval arithmetic (RIA) in order to solve a nonlinear polynomial system robustly, which we refer to as Interval Projected Polyhedron (IPP) algorithm. Rounded interval arithmetic operations can be implemented effectively in object-oriented languages such as C++ as we discussed in Sect. 4.8. Other than overloading the arithmetic operations, we need to pay attention in intersecting each convex hull with the horizontal axis (see Sect. 4.4). The computed parametric values result in interval numbers $u_{low} = [u_a, u_b]$ and $u_{up} = [u_c, u_d]$ . We simply replace them by $u_{low} = [u_a, u_a]$ and $u_{up} = [u_d, u_d]$ to keep the parameter as real numbers or in other words degenerate interval numbers.

We illustrated the effectiveness of the IPP algorithm using the single polynomial equation that we used in Example 4.6.2. The output of this computation is listed in Table 4.5. If we compare the bounding boxes of Tables 4.1 and 4.5 for each iteration, we can easily recognize that the bounding boxes of the RIA are always conservative with respect to the FPA. Also at iteration 9, FPA loses the root 0.7 due to floating point error, while RIA finds it.

**Table 4.5:** (x-0.1)(x-0.6)(x-0.7)=0 solved by IPP algorithm (adapted from [255])
Iter	Bounding Box (RIA)	Message
1	[0, 1]
2	[0.076363636363635, 0.856000000000001]
3	[0.0981877322393447, 0.770083868324001]
4	[0.0999880766853675, 0.723874047810262]	Binary Sub.
5	[0.402239977003124, 0.704479954527489]
6	[0.550441290533286, 0.700214508664294]
7	[0.591018492648947, 0.700000534482208]
8	[0.599458794784611, 0.700000000003333]	Binary Sub.
9	[0.649998841568894, 0.7]	Root Found
10	[0.599997683137788, 0.649998841568895]	Root Found
11	[0.0999999994787598, 0.402239977003124]	Root Found

Subsections

Next: 4.9.1 Formulation of the Up: 4. Nonlinear Polynomial Solvers Previous: 4.8.5 Implementation of rounded Contents Index

December 2009