Česky | English Sign in

Our Events - SIAM SC Seminar - Other Events

Peter Franek - Verification of zeros of continuous functions that are known only approximately

Date: 09/12/2015 14:00
Place: Seminární místnost KNM
The problem of deciding whether a system of nonlinear equations is solvable is algorithmically undecidable in general. Numerical software is only capable of yielding incomplete, although effective, results. I will describe some tools for formal verification of the (non-)existence of solutions in systems of equations.

I will define the concept of robustness: a system of n equation, written compactly f(x)=0, has an r-robust solution, if for any continuous g, ||g-f||‹ r, the system g(x)=0 has a solution. Robustness of the (non-)existence of a solution is an important property in case when only approximations of the equations in question are known.  I will present recent results on algorithmic (un-)decidability of the existence of r-robust solutions, including experimental results of the first software implementation. I will also present further invariants of solution sets (except the already mentioned nonemptyness) that persist if we perturb the system.
The methods used in these algorithm come from the field of computational topology.