Method and apparatus for computing roots of a polynomial equation with interval coefficients

摘要

One embodiment of the present invention provides a system for finding the roots of a polynomial or a quadratic equation with interval coefficients. The system operates by receiving a representation of a polynomial equation, which can be a quadratic equation of the form F(x)=Ax²+Bx+C=0, wherein A=[A_L, A_U], B=[B_L, B_U] and C=[C_L, C_U] are interval coefficients. Next, the system computes intervals containing roots of the functions F₁(x), F₂(x), F₃(x) and F₄(x), wherein F₁(x)=A_Lx²+B_Lx+C_L, F₂(x)=A_Ux²+B_Ux+C_U, F₃(x)=A_Lx²+B_Ux+C_L and F₄(x)=A_Ux²+B_Lx+C_U. The system then places the computed intervals into a list, L, and orders the computed intervals in L by their left endpoints, so that for a each entry, S_i=[S_1L, S_1U], S_{1L≦S1+1,L}. Next, the system establishes interval roots for F(x) from the interval entries in list L. In one embodiment of the present invention, establishing interval roots from the list L involves: establishing one interval root, [S_1,L, S_2U], if L contains two entries, S₁ and S₂; establishing two interval roots, [S_1,L, S_2U], and [S_3L, S_4U], if L contains four entries, S₁, S₂, S₃ and S₄; and establishing three interval roots, [−∞, S_2U], [S_3L, S_4U] and [S_5L,+∞], if L contains six entries, S₁, S₂, S₃, S₄, S₅ and S₆.