Home  
  Teaching  
  Research  
  Misc  
Milan Hladík
Teaching

Ročníkové projekty a bakalářské práce

Projekty a práce tématicky především z oblasti lineární algebry, intervalové analýzy a optimalizace. U projektů preferuji pokračování do bakalářské práce.

Některá témata jsou v SISu. Další navrhovaná témata jsou dole (můžete přijít i s vlastním tématem), jedná se zejména o problémy z intervalového počítání, proto jsem sepsal pár základních informací a odkazů o intervalovém počítání. Může se také hodit pár užitečných odkazů.

  • Mocnění intervalových matic [zabráno]
  • Určit přesný rozsah hodnot druhé mocniny intervalové matice [A]2 je jednoduché, ale pro třetí mocninu je to už výpočetně složité - NP-těžké. Pro vyšší mocniny pak prakticky musíme rozsahy složek aproximovat. Cílem projektu je prozkoumat různé způsoby spočítání obálky hodnot k-té mocniny intervalové matice. Nabízí se standardní mocnění intervalovou aritmetikou nebo využití spektrálního rozkladu, případně další způsoby. Součástí řešení by mělo být odvození různých způsobů řešení, implementace matod a jejich numerické porovnání různých přístupů. Programovací jazyk: Matlab/Octave + Intlab.

    Odkazy:

    1. H.S. Ahn, K.L. Moore and Y.Q. Chen. Iterative Learning Control. Robustness and Monotonic Convergence for Interval Systems. Springer, 2007.
    2. Z. Haiyan, A note about power-boundedness of interval matrices. J. Comput. Appl. Math. 31(2), 1990.
    3. M. Hladík, D. Daney, and E. P. Tsigaridas. Bounds on Real Eigenvalues and Singular Values of Interval Matrices. SIAM J. Matrix Anal. Appl. 31(4):2116-2129, 2010.
    4. O. Kosheleva, V. Kreinovich, G. Mayer, and H.T. Nguyen. Computing the cube of an interval matrix is NP-Hard. In Proceedings of the 2005 ACM symposium on Applied computing (SAC '05), Lorie M. Liebrock (Ed.). ACM, New York, NY, USA.

  • Utažení pivota pro parametrické lineární soustavy rovnic
  • Utažení pivota je způsob jak zefektivnit (z hlediska výsledné obálky množiny řešení) metody na řešení soustav intervalových lineárních rovnic, a to konkrétně Gaussovy eliminace pro obecnou soustavu a Choleského rozklad pro soustavu s positivně definitní maticí. Cílem projektu je rozšířit tento způsob na intervalové soustavy s lineárními závislostmi. Součástí by mělo být i numerické porovnání s jinými metodami řešení. Programovací jazyk: Matlab/Octave + Intlab.

    Odkazy:

    1. J. Garloff. Pivot tightening for direct methods for solving symmetric positive definite systems of linear interval equations. Comput. 94(2-4):97-107, 2012.
    2. J. Garloff. Interval Gaussian elimination with pivot tightening. SIAM J. Matrix Anal. Appl. 30(4):1761-1772, 2009.
    3. M. Hladík. Enclosures for the solution set of parametric interval linear systems. Int. J. Appl. Math. Comput. Sci., 22(3):561–574, 2012.

  • Předpodmínění a regularita symetrických intervalových matic
  • Předpodmínění se často používá pro řešení intervalových (i neintervalových) soustav rovnic. Různá předpodmiňovací matice samozřejmě vede k různým výsledkům. Cílem projektu je prozkoumat různé způsoby předpodmínění symetrické intervalové matice pro účely testování regularity. Dále, použít výsledky pro těsné odhady vlastních čísel symetrických intervalových matic. Součástí by mělo být i numerické porovnání různých přístupů. Programovací jazyk: Matlab/Octave + Intlab.

    Odkazy:

    1. M. Hladík, D. Daney, and E. P. Tsigaridas. A filtering method for the interval eigenvalue problem. Appl. Math. Comput. 217(12):5236-5242, 2011.
    2. M. Hladík, D. Daney, and E. P. Tsigaridas. Bounds on Real Eigenvalues and Singular Values of Interval Matrices. SIAM J. Matrix Anal. Appl. 31(4):2116-2129, 2010.
    3. M. Hladík. Optimal Preconditioning for the Interval Parametric Gauss–Seidel Method. SCAN 2015, Wuerzburg, Germany.
    4. Arnold Neumaier. Interval methods for systems of equations. Cambridge University Press, 1990.

  • Obraz boxu při bilineárním a kvadratickém zobrazení
  • Obraz intervalového boxu při bilineárním a kvadratickém zobrazení se dá snadno odhadnout vyhodnocením intervalovou aritmetikou, ale výsledek může být značně nadhodnocen. Cílem této práce je vylepšit tyto základní odhady použitím algebraických maticových dekompozic, linearizací používaných v optimalizaci, heuristik a jiných technik. Součástí by měla být implementace a numerické porovnání metod. Programovací jazyk: Matlab/Octave + Intlab.

    Odkazy:

    1. C. A. Floudas. Deterministic Global Optimization. Theory, Methods and Applications, Kluwer, 2000.
    2. Arnold Neumaier. Interval methods for systems of equations. Cambridge University Press, 1990.
    3. S. M. Rump. Verification methods: Rigorous results using floating-point arithmetic. Acta Numer., 19:287-­449, 2010.

  • Grafické znázornění komplexních vlastních čísel intervalové matice
  • Problém spočívá ve vykreslení množiny všech komplexních čísel všech matic, které se od zadané matice A liší v každé složce nanejvýš o nějaké δij. Tato množina není jednoduše popsatelná, a proto se musí aproximovat. Například metody založené na principu branch & bound aproximují množinu s libovolnou přesností. Cílem projektu je navrhnout a implementovat metodu, která vykreslí tyto množiny s předem danou přesností. Programovací jazyk: Matlab/Octave + Intlab.

    Odkazy:

    1. E. Garajová: Intervalový solver nelineárních podmínek, 2014.
    2. M. Hladík. Bounds on eigenvalues of real and complex interval matrices. Appl. Math. Comput., 219(10):5584–5591, 2013.
    3. M. Hladík, D. Daney, and E.P. Tsigaridas. A filtering method for the interval eigenvalue problem. Appl. Math. Comput., 217(12):5236–5242, 2011.
    4. J. Rohn. Checking properties of interval matrices. Technical Report 686, Institute of Computer Science, Academy of Sciences of the Czech Republic, 1996.
    5. J. Rohn. A handbook of results on interval linear problems. Technical Report 1163, Institute of Computer Science, Academy of Sciences of the Czech Republic, 2012.

  • Lokalizace vlastních čísel intervalových matic [zabráno]
  • Zde nás zajímá množina všech komplexních čísel všech matic, které se od zadané matice A liší v každé složce nanejvýš o nějaké δij. Cílem práce je zapouzdřit tuto množinu pomocí jednoduchých odhadů založených na Gerschgorinových discích, Cassiniho oválech a dalších pokročilých technik. Konkrétně, jedná se o adaptaci výše zmíněných metod na intervalové matice, porovnání metod a jejich implementace. Programovací část (jazyk Matlab/Octave + Intlab) zahrnuje i vizualizaci odhadů.

    Odkazy:

    1. H.-B. Li, T.-Z. Huang, and H. Li On some subclasses of P-matrices. Numer. Linear Algebra Appl., 14: 391–405, 2007.
    2. M. Hladík. Bounds on eigenvalues of real and complex interval matrices. Appl. Math. Comput., 219(10):5584–5591, 2013.
    3. M. Hladík, D. Daney, and E.P. Tsigaridas. A filtering method for the interval eigenvalue problem. Appl. Math. Comput., 217(12):5236–5242, 2011.
    4. J.M. Peña. On an alternative to Gerschgorin circles and ovals of Cassini. Numer. Math., 95(2): 337-­345 , 2003.
    5. J. Rohn. A handbook of results on interval linear problems. Technical Report 1163, Institute of Computer Science, Academy of Sciences of the Czech Republic, 2012.

  • Vyhodnocení polynomu s intervalovými koeficienty [zabráno]
  • Pro daný polynom s intervalovými koeficienty chceme najít co nejtěsnější obálku funkčních hodnot pro dané body. Kromě přímého použití intervalové aritmetiky (pomocí Hornerova schematu) existují i jiné metody, například pomocí tzv. Bernsteinových polynomů. Cílem práce je implementace zmíněných metod a jejich porovnání, případně vylepšení. Programovací jazyk: Matlab/Octave + Intlab.

    Odkazy:

    1. J. Garloff and A. P. Smith. Preface. Special Issue on the Use of Bernstein Polynomials in Reliable Computing: A Centennial Anniversary. Reliable Computing 17, 2012.
    2. V. Stahl. Interval methods for bounding the range of polynomials and solving systems of nonlinear equations. Dissertation, Johannes Kepler University Linz, Austria, 1995.

  • Speciální soustavy s parametrickými závislostmi koeficientů při navrhování příhradových konstrukcí [zabráno]
  • Soustavy rovnic, které vznikají při navrhování příhradových konstrukcí, mají specifickou strukturu. Pokud máme zohlednit určitou míru nepřesnosti vstupních dat, vede to na problém řešení speciálních lineárních soustav rovnic s parametry. Jako řešení hledáme intervalové zapouzdření všech možných řešení soustavy pro všechny přípustné hodnoty parametrů. Cílem práce by bylo porovnat, a případně vylepšit, různé alternativní metody se základní metodou Neumaiera a Pownuka. Pokusíme se získat reálná data, aby porovnání bylo co nejvěrohodnější. Programovací jazyk: Matlab + Intlab.

    Odkazy:

    1. A. Neumaier and A. Pownuk. Linear Systems with Large Uncertainties, with Applications to Truss Structures. Reliable Computing 13:149-172, 2007.



    Diplomové práce

    Tématicky především z oblasti lineární algebry, intervalové analýzy a optimalizace. Některá témata jsou v SISu. Další navrhovaná témata (můžete přijít i s vlastním tématem):

  • Verifikace v lineárním programování [zabráno]
  • Používání floating-point aritmetiky vede k zaokrouhlovacím chybám a v důsledku toho mohou solvery na lineární programování dávat chybné výsledky. Verifikační metody jsou postupy, které dokážou potvrdit optimalitu vypočítaného řešení (resp. optimální báze) vhledem k dané přesnosti. Cílem práce by bylo zmapovat verifikaci v lineárním programování, porovnat a případně navrhnout vylepšení. Předpokládá se i implementace ve vhodném prostředí - nejspíše v Matlabu s použitím Intlabu.

    Odkazy:

    1. Christian Jansson. Rigorous Lower and Upper Bounds in Linear Programming, SIAM J. Optim. 14(3): 914-935, 2004.
    2. Arnold Neumaier and Oleg Shcherbina. Safe bounds in linear and mixed-integer linear programming, Math. Program., Ser. A, 99(2):283-296, 2004.
    3. Siegfried M. Rump. Verification methods: Rigorous results using floating-point arithmetic, Acta Numerica 19: 287-449, 2010.
    4. Jiří Rohn. VERSOFT: Verification software in MATLAB / INTLAB, version 10, 2009.
    5. Christian Keil and Christian Jansson. Computational Experience with Rigorous Error Bounds for the Netlib Linear Programming Library , Reliab. Comput. 12(4): 303-321, 2006.
    6. Christian Keil. Lurupa - Rigorous Error Bounds in Linear Programming, Dagstuhl Seminar Proceedings 05391, 2006.

  • Intervalová maticová norma
  • Jsou známy různé způsoby jak rozšířit maticové normy na intervalové matice. Cílem této práce by bylo porovnat různé normy mezi sebou, jak moc je těsná ekvivalence mezi nimi, zjistit jejich vlasnosti (konsistence, výpočetní složitost atp.). Zajímavým rozšířením by bylo zobecnění norem tak, aby měly intervalovou hodnotou.

    Odkazy:

    1. R. Farhadsefat, J. Rohn and T. Lotfi. Norms of interval matrices. Technical Report No. 1122, Institute of Computer Science, Academy of Sciences of the Czech Republic, Prague 2011.
    2. Behnam Hashemi and Hanieh Tavakolipour. A non-induced interval matrix norm. Reliable Computing 18, 144-146, 2013.
    3. Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University, 1985.

  • Exponenciála s intervalovou maticí
  • Exponent s maticí je definován přirozeně pomocí Taylorovy řady jako matice eA=∑k=0Ak/k!. Cílem je určit co nejlepší dolní a horní odhady na prvky eA pokud prvky matice A perturbujeme v rámci předem daných intervalů. Motivace tohoto problému pochází v mikro-robotiky, vzniká při hledání robustního řešení v teorii řízení robota.

    Odkazy:

    1. Micky Rakotondrabe, homepage.
    2. Alexandre Goldsztejn. On the Exponentiation of Interval Matrices, arXiv, 2009.
    3. M. Althoff, O. Stursberg, and M. Buss. Reachability analysis of linear systems with uncertain parameters and inputs. In Proc. of the 46th IEEE Conference on Decision and Control, 726-732, 2007.
    4. E.P. Oppenheimer and A.N. Michel. Application of Interval Analysis Techniques to Linear Systems. II. The Interval Matrix Exponential Function. IEEE Trans. Circuits Syst., 35(10):1230-1242, 1988.

  • Porovnání metod intervalového lineárního programování
  • Úlohou intervalového lineárního programování rozumíme množinu úloh lineárního programování, v nichž parametry nabývají hodnot z daných intervalů. Jedním z cílů tohoto problému je najít extrémní meze, ve kterých se nabývají optimální hodnoty jednotlivých lineárních programů. To lze řešit různými metodami, např. dekompozicí na exponenciálně mnoho lineárních programů, metodami globální optimalizace či nehladké nekonvexní optimalizace. Cílem práce je implementace a porovnání základních metod s využitím vhodných dolních a horních odhadů na meze optimálních hodnot. Programovací jazyk: Matlab/Octave + Intlab.

    Odkazy:

    1. E. Hansen and G.W. Walster. Global optimization using interval analysis. 2nd ed., Marcel Dekker, 2004.
    2. M. Hladík. Interval linear programming: A survey. In Zoltán Ádám Mann, editor, Linear Programming - New Frontiers in Theory and Applications, pp. 85–120, Nova Science Publishers, New York, 2012.
    3. M. Hladík. On approximation of the best case optimal value in interval linear programming. Optim. Lett., 8(7):1985–1997, 2014.
    4. M. Hladík. Weak and strong solvability of interval linear systems of equations and inequalities. Linear Algebra Appl., 438(11):4156–4165, 2013.



    Další užitečné odkazy