Verifying topological indices for higher-order rank deficiencies.

*(English)*Zbl 1005.65049Summary: It has been known how to use computational fixed point theorems to verify existence and uniqueness of a true solution to a system of nonlinear equations within a small region about an approximate solution. This can, be done in \(O(n^3)\) operations, where \(n\) is the number of equations and unknowns. However, these standard techniques are only valid if the Jacobi matrix for the system is nonsingular at the solution.

In previous work and a dissertation (of Dian), we have shown, both theoretically and practically, that existence and multiplicity can be verified in a complex setting, and in the real setting for odd multiplicity, when the rank defect of the Jacobi matrix at an isolated solution is 1. Here, after reviewing work to date, we discuss the case of higher rank defect. In particular, it appears that \(p\)-dimensional searches are required if the rank defect is \(p\), and that the work increases exponentially in \(p\).

In previous work and a dissertation (of Dian), we have shown, both theoretically and practically, that existence and multiplicity can be verified in a complex setting, and in the real setting for odd multiplicity, when the rank defect of the Jacobi matrix at an isolated solution is 1. Here, after reviewing work to date, we discuss the case of higher rank defect. In particular, it appears that \(p\)-dimensional searches are required if the rank defect is \(p\), and that the work increases exponentially in \(p\).

##### MSC:

65H10 | Numerical computation of solutions to systems of equations |

65G30 | Interval and finite arithmetic |

65G20 | Algorithms with automatic result verification |

##### Keywords:

result verification; interval arithmetic; topological indices; higher-order rank deficiencies; computational fixed point theorems; system of nonlinear equations
PDF
BibTeX
XML
Cite

\textit{R. B. Kearfott} and \textit{J. Dian}, J. Complexity 18, No. 2, 589--611 (2002; Zbl 1005.65049)

Full Text:
DOI

##### References:

[1] | Aberth, O, Computation of topological degree using interval arithmetic, and applications, Math. comp., 62, 171-178, (1994) · Zbl 0798.55002 |

[2] | Alefeld, G; Herzberger, J, Introduction to interval computations, (1983), Academic Press New York |

[3] | G. Bohlender, Bibliography on enclosure methods and related topics, 1996, . · Zbl 0784.65039 |

[4] | Dian, J, Existence verification of higher degree singular zeros of nonlinear systems, (2000), University of Louisiana at Lafayette |

[5] | J. Dian, and, R. B. Kearfott, Existence verification for singular zeros of real nonlinear systems, 2001, . · Zbl 1025.65030 |

[6] | Govaerts, W, Computation of singularities in large nonlinear systems, SIAM J. numer. anal., 34, 867-880, (1997) · Zbl 0874.65041 |

[7] | Govaerts, W; Kuznetsov, Yu.A; Sijnave, B, Numerical methods for the generalized Hopf bifurcation, SIAM J. numer. anal., 38, 329-346, (2000) · Zbl 0968.65109 |

[8] | Griewank, A; Reddien, G.W, Characterization and computation of generalized turning points, SIAM J. numer. anal., 21, 176-185, (1984) · Zbl 0536.65031 |

[9] | Griewank, A, On solving nonlinear equations with simple singularities or nearly singular solutions, SIAM rev., 27, 537-564, (1985) · Zbl 0598.65026 |

[10] | Hansen, E.R, Global optimization using interval analysis, (1992), Dekker New York · Zbl 0756.65035 |

[11] | Jürgens, H; Peitgen, H.-O; Saupe, D, Topological perturbations in the numerical nonlinear eigenvalue and bifurcation problems, Analysis and computation of fixed points, (1980), Academic Press New York, p. 139-181 |

[12] | Kearfott, R.B, An efficient degree-computation method for a generalized method of bisection, Numer. math., 32, 109-127, (1979) · Zbl 0386.65016 |

[13] | Kearfott, R.B, Algorithm 763: : A Fortran 90 module for an interval data type, ACM trans. math. software, 22, 385-392, (1996) · Zbl 0884.65041 |

[14] | Kearfott, R.B, Interval computations—introduction, uses, and resources, Euromath bull., 2, 95-112, (1996) |

[15] | Kearfott, R.B, Rigorous global search: continuous problems, (1996), Kluwer Academic Dordrecht · Zbl 0876.90082 |

[16] | R. B. Kearfott, and, J. Dian, Existence verification for higher-degree singular zeros of complex nonlinear systems, 2000, . · Zbl 0986.65054 |

[17] | Kearfott, R.B; Dian, J; Neumaier, A, Existence verification for singular zeros of complex nonlinear systems, SIAM, J. numer. anal., 38, 360-379, (2000) · Zbl 0986.65054 |

[18] | V. Kreinovich, Interval computations web page, 2001;, . |

[19] | Kreinovich, V; Lakeyev, A; Rohn, J; Kahl, P, Computational complexity and feasibility of data processing and interval computations, (1998), Kluwer Academic Dordrecht · Zbl 0945.68077 |

[20] | Neumaier, A, Interval methods for systems of equations, (1990), Cambridge Univ. Press Cambridge · Zbl 0706.15009 |

[21] | Ratschek, H; Rohne, J, New computer methods for global optimization, (1988), Wiley New York · Zbl 0648.65049 |

[22] | Sikorski, K.A, Optimal solution of nonlinear equations, (2001), Oxford Univ. Press New York |

[23] | Sommese, A.J; Verschelde, J; Wampler, C.W, Numerical decomposition of the solution sets of polynomial systems into irreducible components, SIAM J. numer. anal., 38, 2022-2046, (2000) · Zbl 1002.65060 |

[24] | Stenger, F, An algorithm for the topological degree of a mapping in \(R\)^n, Numer. math., 25, 23-38, (1976) |

[25] | Stevenson, D, Floating-point working group, microprocessor standards, subcommittee, IEEE standard for binary floating point arithmetic, Technical report, (1985), IEEE |

[26] | G. W. Walster, et al., Forte Fortran/HPC: interval arithmetic, 2000;, http://www.sun.com/forte/fortran/interval/. |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.