Gauss-dokumentáció-TeXworks

\documentclass[oneside,11pt,a4paper]{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{indentfirst}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{url}
\usepackage{algorithmic}
\usepackage{algorithm}
\usepackage{mathtools}
\usepackage{bbm}

\newtheorem{szoveg}{ }

\DeclareMathOperator{\diag}{diag}

%Számhalmazok jelölése%
\newcommand{\IR}{\mathbb{R}}
\newcommand{\IN}{\mathbb{N}}

\title{Gauss-elimináció\\ \vspace{10mm} \large Dokumentáció a programcsomagok numerikus módszekeben\\ kurzus beadandóhoz}
\author{Készítette: Farkas István (FASSAAI.ELTE)}
\date{ 2012 Április 3}

\begin{document}
\maketitle
\clearpage
\renewcommand*\contentsname{Tartalom}
\tableofcontents

\newpage
\section{Feladat}

\subsection{Feladat leírás}
Gauss-elimináció LER részleges főelemkiválasztással.\\
Készítsen olyan függvényt, amely adott A mátrix és b vektor esetén a
Gauss-elimináció módszerét követve kiszámítja az Ax = b lineáris egyenletrendszer megoldását. Mutassa közben az alakuló mátrixo(ka)t, a sorok
cseréjét.

\subsection{A feladat megoldására használt szoftver}
A feladat megoldására a Matlab szoftvert használjuk. A szoftver numerikus számítások elvégzésére lett kifejlesztve, így könnyű benne mátrixműveleteket végrehajtani (mint például sorcsere) és algorimusokat implementálni.

\section{Gauss-elimináció}

\subsection{Az alapfeladat}
Egy n ismeretlenes egyenletrendszer általános alakja
\begin{equation}
    a_{11}x_1 + a_{12}x_2 + ... + a_{1n}x_n = b_1
\end{equation}
\begin{equation}
    a_{21}x_1 + a_{22}x_2 + ... + a_{2n}x_n = b_2\\
\end{equation}
\begin{equation}
\vdots
\end{equation}
\begin{equation}
    a_{n1}x_1 + a_{n2}x_2 + ... + a_{nn}x_n = b_n
\end{equation}
\par

Feladatunk, hogy kiszámoljuk az egyenletrendszer ismeretlenjeit. Erre az egyik legkézenfekvőbb eszköz a Gauss-elimináció. Ha az egyenletrendszer együtthatóit beírjuk egy A $\in$ $\IR^{n \times n}$ -es mártixba, és az  egyenletrendszer bal oldali konstansait beírjuk egy b $\in$  $\IR^n$ -es vektorba akkor a feladat a következőképpen is megfogalmazható:\par
Keressük azt az x $\in$  $\IR^n$ vektort amire teljesül az \\
\begin{equation}
Ax = b
\end{equation}
ahol A $\in$ $\IR^{n \times n}$ invertálható mátrix, det(A) $\neq$ 0 és b $\in$  $\IR^n$. \par
A Gauss-elimináció során ebből a mátrixból fogunk kiindulni. Első lépésként az A mártrix mellé írjuk a b vektort, így egy n$\times$n+1 es mártixot kapunk. Az algoritmus két fő részre osztható:
\begin{szoveg}
 az n$\times$n es mátrixból felsőháromszög mátrixot csinálunk
\end{szoveg}
\begin{szoveg}
rekurzív visszahelyettesítésel megkapjuk az n+1 oszlopban az eredményvektort
\end{szoveg}

\subsection{Részleges főelemkiválasztás}
Az algoritmus során, mikor a mátrixot ekvivalens áttalakításokkal felsőháromszög mátrixá alakítjuk, folymatosan osztanunk kell az éppen aktuális mátrix diagonális elemével. Azonban ha ez az elem nulla a Gauss-elimináció megakad. Hogy ezt a problémát kiküszöböljük, az algoritmusba beteszünk egy ellenőrzést az aktuális elem vizsgálatára. Ha a k. diagonális elem nulla akkor megkeressük az akutális oszlop legnagyobb elemét abszolút értékben, és azt a sort amelyikben ez az elem van, kicseréljük a k. sorral. Ezt az eljárást nevezzük részleges főelemkiválsztásnak.

\section{A program}
A program adott A mátrix és b vektor esetén a Gauss-elimináció módszerét követve kiszámítja az Ax = b lineáris egyenletrendszer megoldását, részleges főelemkiválasztással. A programot gauss nevű fájlba mentjük és .m kiterjesztéssel látjuk el. A program hívását az x=gauss(A,b) paranccsal tehetjük meg. Ekkor az eredmény az x vektorba fog bekerülni.

\subsection{Bemenő, kimenő adatok}
Bemenő paraméterek:\\
Egy n$\times$n -es mátrix (A), egy n méretű vektor (b)\\

Kimenő adatok:\\
Egy n méretű vektor, a lineáris egyenletrendszer megoldása (x)

\newpage
\subsection{Programkód}
A program kódja a következő:\\
\begin{verbatim}
function x = gauss(A,b)

n=length(A);
A=[A,b]
for k=1:n-1
  for i=k+1:n
    for j=k+1:n+1
      if ( A(k,k) == 0 )
        [maximum, ind] = max(abs(A(k:n,k)));
        if ( maximum == 0 )
          disp('A mátrix determinánsa nulla')
          return;
        end
           akt = A(ind,1:n+1);
           A(ind,1:n+1) = A(k,1:n+1);
           A(k,1:n+1) = akt;
          disp('A mátrix sorcsere utan:')
          disp(A)
       end
        A(i,j) = A(i,j) -  ( (A(i,k) / A(k,k)) * A(k,j) );
    end
    A(i,k)=0;
  end
  disp('A matrix elimináció után:')
  disp(A)
end
x=zeros(n,1);
x(n,1) = A(n,n+1) / A(n,n);
temp=0;
for k=n-1:-1:1
  for j=k+1:n
    temp = temp + A(k,j) * x(j,1);
  end
    x(k,1) = (A(k,n+1) - temp) / A(k,k);
    temp=0;
end
\end{verbatim}

\section{Teszteredmények}
\subsection{Egy általános teszteset}
A program a
$$
\left[\begin{array}{ccc|c}
 0 & 7 & -8  & 3\\
 2 & 4 & -5 & 1\\
 -4 & -6 & 5 & 9\\
\end{array}\right]
$$

bemenetre első lépésként sorcserét csinál, felcseréli az első sort a harmadikkal.

$$
\left[\begin{array}{ccc|c}
 -4 & -6 & 5  & 9\\
 2 & 4 & -5 & 1\\
 0 & 7 & -8 & 3\\
\end{array}\right]
$$

Második lépésként eliminálja ez első oszlopot,

$$
\left[\begin{array}{ccc|c}
 -4 & -6 & 5  & 9\\
 0 & 1 & -2.5 & 5.5\\
 0 & 7 & -8 & 3\\
\end{array}\right]
$$

majd a második oszlopot.

$$
\left[\begin{array}{ccc|c}
 -4 & -6 & 5  & 9\\
 0 & 1 & -2.5 & 5.5\\
 0 & 0 & 9.5 & 35.5\\
\end{array}\right]
$$

A program a végén kiírja az eredményvektort.

$$
\left[\begin{array}{c}
 -1.1579\\
 -3.8421 \\
 -3.7368 \\
\end{array}\right]
$$

Ha olyan mátrixot adunk meg bemenetnek aminek a determinánsa nulla, akkor a "Mátrix determinánsa nulla" üzenetet kapjuk. Ekkor a gauss elimináció nem végrehajtható a mátrixon.

\subsection{A program futásidejének tesztelése}
Hogy megvizsgáljuk a program futásidejét, készítünk egy teszt\_script.m nevű scriptet. A scriptet egy n $\in$ $\IN$ bemenő konstansal hívjuk meg. A program k$\times$k k $\in$ (1...n) méretű mártixokat generál és tölt fel véletlenszerű számokkal, valamint k $\in$ (1...n) méretű vektorokat készít az egyenletrendszerhez, szintén véletlen számokkal feltöltve. Minden egyes Ax = b egyenletrendszerre meghívja a gauss\_teszt.m  programot, ami annyiban tér el az eredeti gauss.m programtól, hogy itt mellőzünk mindenféle képernyőre íratást, az ugyanis torzítana a teszt eredményén.
A teszt\_script.m kimenete egy grafikon, ahol az x tengelyen a mátrixok mérete, y tengelyen pedig a Gauss-elimináció végrehajtásának idelye van.
A teszt\_script.m kódja:
\begin{verbatim}
function test_script(n)
tocok = zeros(1,n);
kak = (1:n);
for k=1:n,
  A = rand(k,k);
  b = rand(k,1);
  tic;
  gauss_test(A,b);
  tocok(k) = toc;
end

plot(kak, tocok, 'r*')
\end{verbatim}

100 darab mátrixra meghívva a következő grafikont kapjuk.\\\\
\includegraphics[origin = c, width=300pt, height=300pt]{kep.png}

\newpage
\section{Hivatkozások}

\renewcommand*\refname{}
\begin{thebibliography}{9}

\bibitem{book1}
\textbf{Freud, R.,}
\textit{Lineáris algebra},
ELTE Eötvös Kiadó, Budapest, 2004.

\bibitem{book2}
\textbf{Gergó, L.,}
\textit{Numerikus módszerek},
ELTE Eötvös Kiadó, Budapest, 2010 október.

\bibitem{electronic}
\textbf{Krebsz, A., Bozsik, J.,} Numerikus Módszerek Példatár,
{\tt http://numanal.inf.elte.hu/$\sim$krebsz/prog\_inf\_bsc\_c.htm}

\end{thebibliography}

\end{document}