velikost textu

Interval linear and nonlinear systems

Upozornění: Informace získané z popisných dat či souborů uložených v Repozitáři závěrečných prací nemohou být použity k výdělečným účelům nebo vydávány za studijní, vědeckou nebo jinou tvůrčí činnost jiné osoby než autora.
Název:
Interval linear and nonlinear systems
Název v češtině:
Intervalové lineární a nelineární systémy
Typ:
Disertační práce
Autor:
Mgr. Jaroslav Horáček
Školitel:
Mgr. Milan Hladík, Ph.D.
Oponenti:
Jürgen Garloff
Ing. Stefan Ratschan, Ph.D.
Id práce:
113671
Fakulta:
Matematicko-fyzikální fakulta (MFF)
Pracoviště:
Katedra aplikované matematiky (32-KAM)
Program studia:
Informatika (P1801)
Obor studia:
Diskrétní modely a algoritmy (4I4)
Přidělovaný titul:
Ph.D.
Datum obhajoby:
6. 6. 2019
Výsledek obhajoby:
Prospěl/a
Jazyk práce:
Angličtina
Klíčová slova:
intervalová matice, intervalový lineární systém, intervalová lineární algebra, splňování omezujících podmínek, intervalová regrese, intervalový determinant, výpočetní složitost
Klíčová slova v angličtině:
interval matrix, interval linear system, interval linear algebra, constraint satisfaction problem, interval regression, interval determinant, computational complexity
Abstrakt:
Nejprve představíme základní aspekty intervalové analýzy, role intervalů a jejich aplikace. Poté popíšeme různé třídy intervalových matic a popíšeme je- jich vztahy. Tato látka představuje základ pro jednotící téma celé práce – řešení intervalových lineárních soustav. Představíme a porovnáme několik metod pro řešení čtvercových a přeurčených intervalových soustav. Pro čtvercové soustavy představíme novou shaving me- todu, pro přeurčené soustavy představíme nové schéma podčtverců. Diskutujeme detekci neřešitelnosti a řešitelnosti soustav a porovnáme několik polynomiálních podmínek. Dokážeme, že dvě nejsilnější podmínky jsou ekvivalentní za určitého předpokladu. Řešení intervalových lineárních soustav je poté použito řešení ostat- ních problémů v této práci. Zabýváme se výpočtem obálky determinantu intervalových matic. Dokážeme NP-těžkost relativní i absolutní aproximace. Navrhneme novou metodu založenou na řešení čtvercových intervalových soustav a Kramerově pravidlu. Charakterizu- jeme rozličné třídy matic, u kterých lze spočítat meze determinantu v polynomi- álním čase. Řešení soustav rovnic je též použito k výpočtu lineární a nelineární regrese pomocí nejmenších čtverců. Ta je poté aplikována na reálná medicínská data z analýzy plicních funkcí. Výsledky produkují několik potenciálně klinicky významných hypotéz. Součástí aplikace je popis nového algoritmu pro hledání dechů. V souvislosti s nelineárními systémy ukážeme způsob, jak linearizovat problém splňování omezujících podmínek na intervalovém boxu a převést ho na soustavu reálných nerovnic. Tento přístup je zobecněním starší práce, kterou pro- vedli Araya, Trombettoni a Neveu. Na konci adresujeme výpočetní složitost vybraných intervalových problémů a popíšeme jejich polynomiálně řešitelné podúlohy. Popíšeme též vlastní intervalový toolbox LIME pro Octave a jeho intervalový balík, který implementuje většinu testovaných metod v této práci.
Abstract v angličtině:
First, basic aspects of interval analysis, roles of intervals and their applications are addressed. Then, various classes of interval matrices are described and their relations are depicted. This material forms a prelude to the unifying theme of the rest of the work – solving interval linear systems. Several methods for enclosing the solution set of square and overdetermined interval linear systems are covered and compared. For square systems the new shaving method is introduced, for overdetermined systems the new subsquares approach is introduced. Detecting unsolvability and solvability of such systems is discussed and several polynomial conditions are compared. Two strongest condi- tions are proved to be equivalent under certain assumption. Solving of interval linear systems is used to approach other problems in the rest of the work. Computing enclosures of determinants of interval matrices is addressed. NP- hardness of both relative and absolute approximation is proved. New method based on solving square interval linear systems and Cramer’s rule is designed. Various classes of matrices with polynomially computable bounds on determinant are characterized. Solving of interval linear systems is also used to compute the least squares linear and nonlinear interval regression. It is then applied to real medical pulmonary testing data producing several potentially clinically significant hypotheses. A part of the application is a description of the new breath detection algorithm. Regarding nonlinear systems an approach to linearizing a constraint satisfaction on an interval box problem into a system of real inequalities is shown. Such an approach is a generalization of the previous work by Araya, Trombettoni and Neveu. The features of this approach are discussed. At the end computational complexity of selected interval problems is add- ressed and their feasible subclasses are captured. The interval toolbox LIME for Octave and its interval package, which implements most of the tested methods, is introduced.
Dokumenty
Stáhnout Dokument Autor Typ Velikost
Stáhnout Text práce Mgr. Jaroslav Horáček 5.71 MB
Stáhnout Abstrakt v českém jazyce Mgr. Jaroslav Horáček 40 kB
Stáhnout Abstrakt anglicky Mgr. Jaroslav Horáček 39 kB
Stáhnout Posudek vedoucího Mgr. Milan Hladík, Ph.D. 122 kB
Stáhnout Posudek oponenta Jürgen Garloff 149 kB
Stáhnout Posudek oponenta Ing. Stefan Ratschan, Ph.D. 69 kB
Stáhnout Záznam o průběhu obhajoby prof. RNDr. Jaroslav Nešetřil, DrSc. 153 kB