Tato bakalářská práce se zabývá problematikou řešení lineárních aproximačních úloh ve smyslu tzv. úplných nejmenších čtverců (TLS, z anlického total least squares). V úvodu se seznámíme s velmi důležitým nástrojem, kterým je singulární rozklad (SVD, z anglického singular value decomposition). Dále v práci popíšeme možné přístupy k řešení lineárních aproximačních úloh. Nejprve stručně zopakujeme běžně známý přístup přeformulování úlohy na tzv. (klasický) problém nejmenších čtverců, neboli lineární regresi. V kontrastu k tomu zavedeme úplný problém nejmenších čtverců, neboli tzv. ortogonální regresi. Dokážeme, že ne vždy má lineární aproximační úloha řešení ve smyslu TLS. Tento důkaz provedeme pomocí ortogonální tranformace původní úlohy, tj. změny báze souřadného systému, ve kterém je úloha zformulovaná, na blokově diagonální tvar. Tato transformace povede přímo k definici tzv. core problému. Zmíníme, že core problém lze zapsat ve dvou typických tvarech, pomocí SVD tvaru a pomocí bidiagonálního tvaru. V závěrečné části popíšeme software vytvořený v prostředí Matlab, který dokáže generovat pseudonáhodné lineární aproximační úlohy předepsaných rozměrů obsahující core problém předepsaných vlastností. Smyslem tohoto softwaru je vytvoření databáze úloh pro statistické testy. To však již není součástí této práce.
Anotace v angličtině
This bachelor thesis deals with solving linear approximation problems in the sense of the so-called total least squares (TLS). In the beginning we introduce one of the most important tools, the singular value decomposition (SVD).
Then we briefly describe possible approaches to solving such problem. First approach is the commonly known (ordinary) least squares formulation (or problem) also know as linear regression. We are particularly interested in the second approach, the total least squares formulation (or problem) also know as orthogonal regression. We show that the linear approximation problem may not have a solution in the sense TLS. This can be show using orthogonal transformations of the original problem, i.e., by changing coordinate systems in which the problem is formulated, so that the transformed problem has a block diagonal form. This transformation leads directly to the definition of the so-called core problem. We mention that the core problem can be written in two typical forms, in the SVD form and in the bidiagonal form. In the final section, we describe a software tool that we developed in Matlab, which can generate pseudo-random linear approximation problems with given dimensions and containing a core problem with prescribed properties. The aim of this tool is to assemble a database of such problems, which will be used for futher statistcal testing. This, however, is not part of this thesis.
Klíčová slova
singulární rozklad (SVD), (klasický) problém nejmenších čtverců (LS), úplný problém nejmenších čtverců (TLS), ortogonální regrese, ortogonální transformace, core problém, SVD tvar core problému, bidiagonální tvar core problému
Klíčová slova v angličtině
singular value decomposition (SVD), (ordinary) least squares problem (LS), total least squares problem (TLS), orthogonal regression, orthogonal transformation, core problem, SVD form of a core problem, bidiagonal form of a core problem
Rozsah průvodní práce
49 s.
Jazyk
CZ
Anotace
Tato bakalářská práce se zabývá problematikou řešení lineárních aproximačních úloh ve smyslu tzv. úplných nejmenších čtverců (TLS, z anlického total least squares). V úvodu se seznámíme s velmi důležitým nástrojem, kterým je singulární rozklad (SVD, z anglického singular value decomposition). Dále v práci popíšeme možné přístupy k řešení lineárních aproximačních úloh. Nejprve stručně zopakujeme běžně známý přístup přeformulování úlohy na tzv. (klasický) problém nejmenších čtverců, neboli lineární regresi. V kontrastu k tomu zavedeme úplný problém nejmenších čtverců, neboli tzv. ortogonální regresi. Dokážeme, že ne vždy má lineární aproximační úloha řešení ve smyslu TLS. Tento důkaz provedeme pomocí ortogonální tranformace původní úlohy, tj. změny báze souřadného systému, ve kterém je úloha zformulovaná, na blokově diagonální tvar. Tato transformace povede přímo k definici tzv. core problému. Zmíníme, že core problém lze zapsat ve dvou typických tvarech, pomocí SVD tvaru a pomocí bidiagonálního tvaru. V závěrečné části popíšeme software vytvořený v prostředí Matlab, který dokáže generovat pseudonáhodné lineární aproximační úlohy předepsaných rozměrů obsahující core problém předepsaných vlastností. Smyslem tohoto softwaru je vytvoření databáze úloh pro statistické testy. To však již není součástí této práce.
Anotace v angličtině
This bachelor thesis deals with solving linear approximation problems in the sense of the so-called total least squares (TLS). In the beginning we introduce one of the most important tools, the singular value decomposition (SVD).
Then we briefly describe possible approaches to solving such problem. First approach is the commonly known (ordinary) least squares formulation (or problem) also know as linear regression. We are particularly interested in the second approach, the total least squares formulation (or problem) also know as orthogonal regression. We show that the linear approximation problem may not have a solution in the sense TLS. This can be show using orthogonal transformations of the original problem, i.e., by changing coordinate systems in which the problem is formulated, so that the transformed problem has a block diagonal form. This transformation leads directly to the definition of the so-called core problem. We mention that the core problem can be written in two typical forms, in the SVD form and in the bidiagonal form. In the final section, we describe a software tool that we developed in Matlab, which can generate pseudo-random linear approximation problems with given dimensions and containing a core problem with prescribed properties. The aim of this tool is to assemble a database of such problems, which will be used for futher statistcal testing. This, however, is not part of this thesis.
Klíčová slova
singulární rozklad (SVD), (klasický) problém nejmenších čtverců (LS), úplný problém nejmenších čtverců (TLS), ortogonální regrese, ortogonální transformace, core problém, SVD tvar core problému, bidiagonální tvar core problému
Klíčová slova v angličtině
singular value decomposition (SVD), (ordinary) least squares problem (LS), total least squares problem (TLS), orthogonal regression, orthogonal transformation, core problem, SVD form of a core problem, bidiagonal form of a core problem
Zásady pro vypracování
Uvažujme lineární aproximační úlohu Ax aproximuje b, kde A je matice typu
m-krát-n, b je vektor délky m. Předpokládejme, že pravá strana b neleží
v oboru hodnot matice R(A) (v opačném případě existuje řešení v klasickém
smyslu), ale není ani ortogonální na R(A) (v opačném případě nemá smysl
pokoušet se aproximovat pravou stranu b lineární kombinací sloupců matice A).
Takovou aproximační úlohu řešíme zpravidla tak, že hledáme nějaký vektor x,
který minimalizuje předem zvolený funkcionál. Klasickým přístupem je
minimalizace normy rezidua, t. j. vektoru r=b-Ax, která, při použití eukleidovské normy, vede na standardní problém nejmenších čtverců ((ordinary) least squares, (O)LS). Takový přístup však pracuje s a-priorním předpokladem, že matici A známe naprosto přesně, zatímco vektor b obsahuje chyby (aproximované právě reziduem). Tento a-priorní předpoklad je odstraněn přechodem k úplnému problému nejmenších čtverců (total least squares, TLS). Nevýhodou TLS problému je, že, narozdíl od LS, nemusí mít řešení pro libovolnou dvojici (A,b), a to ani v případě, kdy má matice A plnou sloupcovou hodnost, viz [1]. Vhodným nástrojem pro studium řešitelnosti TLS je tzv. core problém, viz [3], který umožňuje snadno formulovat nutnou a postačující podmínku řešitelnosti.
Cílem práce bude zejména vytvoření softwaru (v MATLABu), který umožní snadné a
rychlé generování aproximačních úloh obsahujících netriviální core problém
předem daných rozměrů a vhodných parametrů (např. s předem danou distribucí
singulárních čísel). Smyslem práce je připravit vhodné nástroje a data pro
statistickou analýzu úloh s netriviálním core problémem.
Požadavky: Základní znalosti z lineární algebry, základní orientace v MATLABu,
základní znalost anglického jazyka a základy práce v LaTeXu.
Zásady pro vypracování teoretické části: Seznámit se s pokročilejšími partiemi
lineární algebry (zejm. SVD, TLS, core problém). V praktické části naprogramovat
software, který bude automaticky generovat aproximační problémy s netriviálním,
předem daným core problémem. Práce bude vypracovaná v LaTeXu.
Zásady pro vypracování
Uvažujme lineární aproximační úlohu Ax aproximuje b, kde A je matice typu
m-krát-n, b je vektor délky m. Předpokládejme, že pravá strana b neleží
v oboru hodnot matice R(A) (v opačném případě existuje řešení v klasickém
smyslu), ale není ani ortogonální na R(A) (v opačném případě nemá smysl
pokoušet se aproximovat pravou stranu b lineární kombinací sloupců matice A).
Takovou aproximační úlohu řešíme zpravidla tak, že hledáme nějaký vektor x,
který minimalizuje předem zvolený funkcionál. Klasickým přístupem je
minimalizace normy rezidua, t. j. vektoru r=b-Ax, která, při použití eukleidovské normy, vede na standardní problém nejmenších čtverců ((ordinary) least squares, (O)LS). Takový přístup však pracuje s a-priorním předpokladem, že matici A známe naprosto přesně, zatímco vektor b obsahuje chyby (aproximované právě reziduem). Tento a-priorní předpoklad je odstraněn přechodem k úplnému problému nejmenších čtverců (total least squares, TLS). Nevýhodou TLS problému je, že, narozdíl od LS, nemusí mít řešení pro libovolnou dvojici (A,b), a to ani v případě, kdy má matice A plnou sloupcovou hodnost, viz [1]. Vhodným nástrojem pro studium řešitelnosti TLS je tzv. core problém, viz [3], který umožňuje snadno formulovat nutnou a postačující podmínku řešitelnosti.
Cílem práce bude zejména vytvoření softwaru (v MATLABu), který umožní snadné a
rychlé generování aproximačních úloh obsahujících netriviální core problém
předem daných rozměrů a vhodných parametrů (např. s předem danou distribucí
singulárních čísel). Smyslem práce je připravit vhodné nástroje a data pro
statistickou analýzu úloh s netriviálním core problémem.
Požadavky: Základní znalosti z lineární algebry, základní orientace v MATLABu,
základní znalost anglického jazyka a základy práce v LaTeXu.
Zásady pro vypracování teoretické části: Seznámit se s pokročilejšími partiemi
lineární algebry (zejm. SVD, TLS, core problém). V praktické části naprogramovat
software, který bude automaticky generovat aproximační problémy s netriviálním,
předem daným core problémem. Práce bude vypracovaná v LaTeXu.
Seznam doporučené literatury
[1] G. H. Golub, C. F. Van Loan:
An analysis of the total least squares problem,
SIAM J. Num. Anal., 17 (1980), pp. 883--893.
[2] G. H. Golub, C. F. Van Loan:
Matrix Computations, fourth ed.
The Johns Hopkins University Press, Baltimore and London, 2012.
[3] C. C. Paige, Z. Strakoš:
Core problem in linear algebraic systems,
SIAM J. Matrix Anal. Appl., 27 (2006), pp. 861--875.
[4] S. Van Huffel, J. Vandewalle:
The Total Least Squares Problem: Computational Aspects and Analysis,
SIAM Publications, Philadelphia, PA, 1991.
[5] S. Van Huffel, ed.:
Recent Advances in Total Least Squares Techniques and Errors-in-Variables Modeling, Proceedings of the Second Int. Workshop on TLS and EIV,
Philadelphia, SIAM Publications, 1997.
[6] S. Van Huffel, P. Lemmerling, eds.:
Total Least Squares and Errors-in-Variables Modeling: Analysis, Algorithms and Applications,
Dordrecht, Kluwer Academic Publishers, 2002.
Seznam doporučené literatury
[1] G. H. Golub, C. F. Van Loan:
An analysis of the total least squares problem,
SIAM J. Num. Anal., 17 (1980), pp. 883--893.
[2] G. H. Golub, C. F. Van Loan:
Matrix Computations, fourth ed.
The Johns Hopkins University Press, Baltimore and London, 2012.
[3] C. C. Paige, Z. Strakoš:
Core problem in linear algebraic systems,
SIAM J. Matrix Anal. Appl., 27 (2006), pp. 861--875.
[4] S. Van Huffel, J. Vandewalle:
The Total Least Squares Problem: Computational Aspects and Analysis,
SIAM Publications, Philadelphia, PA, 1991.
[5] S. Van Huffel, ed.:
Recent Advances in Total Least Squares Techniques and Errors-in-Variables Modeling, Proceedings of the Second Int. Workshop on TLS and EIV,
Philadelphia, SIAM Publications, 1997.
[6] S. Van Huffel, P. Lemmerling, eds.:
Total Least Squares and Errors-in-Variables Modeling: Analysis, Algorithms and Applications,
Dordrecht, Kluwer Academic Publishers, 2002.
Přílohy volně vložené
1 CD
Přílohy vázané v práci
-
Převzato z knihovny
Ano
Plný text práce
Přílohy
Posudek(y) oponenta
Hodnocení vedoucího
Záznam průběhu obhajoby
Průběh obhajoby je zveřejněn pouze přihlášenému uživateli.