\documentclass[a4paper,dvips,12pt]{article} % Dokumenttype \usepackage[latin1]{inputenc} % Inputtype (platformafhængig) \usepackage[danish]{babel} % Ordombrydningssprog \usepackage[T1]{fontenc} % Fonts der kan bruges i dokumentet \hyphenation{} % Orddelingsregler % MATEMATIK OG GRAFIK ------------------------------------------------------------------------------------------------------------------------------------% \usepackage{amsmath,amssymb} % Matematisk pakke \usepackage[pdftex]{color,graphicx} % PDF med farvet grafik \usepackage[pdftex]{graphicx} % PDF med grafik \usepackage{maplestd2e} % Til at kunne implementere Maple-kode \usepackage{braket} % Til at kunne lave | i variabel størrelse (\middle|) \renewcommand{\theequation}{\arabic{subsection}.\arabic{equation}} % Gendefiner kommandoen der laver equation numre \usepackage{color} % Til at kunne lave farvet output % LAYOUT ------------------------------------------------------------------------------------------------------------------------------------% \usepackage{fancyhdr} % Til sidehoved og sidefod \pagestyle{fancy} % Layout af sidehoved og sidefod \fancyhead{} % Renser alle head-felter \fancyhead[L]{\ECFTallPaul Lineær Algebra ugeopgave 3} % Udskriver i venstre side øverst \fancyhead[R]{\ECFTallPaul Opgave \thesubsection} % Udskriver i højre side øverst \headheight 14.5pt % Højden af headerfeltet \fancyfoot{} % Renser alle foot-felter \fancyfoot[C]{\ECFTallPaul \rule{40pt}{0.2pt} \thepage{} \rule{40pt}{0.2pt}} % Udskriver i midten nederst \renewcommand{\headrulewidth}{0.2pt} % Tykkelse på øverste linie \renewcommand{\footrulewidth}{0.0pt} % Tykkelse på nederste linie \usepackage{enumerate} % Til at kunne lave nummererede items \usepackage{subfigure} % Til at kunne lave figurer side om side \usepackage{emerald} % Skrifttyper speficik for forsiden til afleveringen \usepackage{pifont} % Til at kunne typesætte tal med ring om \usepackage{yhmath} % START PÅ DOKUMENT MED FORSIDE ------------------------------------------------------------------------------------------------------------------------------------% \begin{document} % Starter dokumentet efter preamble \pagestyle{empty} % Sidehoved og sidefod for forsiden \input{forside.tex} % Input af forsiden, der ligger i forside.tex % START PÅ AFLEVERINGSOPGAVEN SELV ------------------------------------------------------------------------------------------------------------------------------------% \newpage % Ny side efter forsiden er indsat \pagestyle{fancy} % Sidehoved og sidefod for resten af dokumentet \setcounter{page}{2} % Resten af afleveringen har sidenummer 2 og frem \section*{Lin.Alg. Ugeopgave 3} \setcounter{section}{3} % reset tælleren til at nummerere sections (ugeopgavenummer) \subsection{Determinanter} Jeg er givet en $n \times n$ matrix $F_n$ for $n \in \mathbb{N}$ på formen \begin{equation} F_n = \left[ \begin{array}{ccc} & & -1 \\ & \adots & \\ -1 & \\ \end{array} \right] \label{a:hovedmatrix} \end{equation} Denne skal jeg arbejde videre med i de to delopgaver a og b som følger. \subsubsection*{Delopgave a} Jeg skal ved hjælp af Maple udregne determinanten til $F_n$ givet i \eqref{a:hovedmatrix} for værdierne $n \in \left\{ 1,...,20 \right\}$, og derefter opstille en hypotese om hvordan disse afhænger af $n$. Jeg starter ud med at definere min matrix i Maple som en funktion $F(n)$ -- med hvilken jeg mener $F_n$ med samme $n$ selvfølgelig. Derefter viser jeg et lille eksempel for lige at kontrollere at sekvensen faktisk fungerer: \input{mapleexports/3.1a1.tex} \vspace{10pt} \noindent Det jeg gør med sekvensen er faktisk bare at sige at for alle $(i,j)$ indgange i en $n \times n$ matrix hvor $i=n-k+1$ og $j=k$ skal værdien i matricen være $f_{ij} = -1$. Derudover sørger {\verb+Matrix+}-kommandoen selv for at indsætte nuller. Jeg kan gøre dette da jeg ved at alle indgangene $f_{ij}$ i diagonalen for $F_n$ fra højre hjørne og ned i venstre hjørne har værdier $i$ og $j$ så $i+j =n+1$. Nu kan jeg så ved hjælp af en simpel sekvens finde determinanterne af $F_n$ for $n=[1;20]$: \input{mapleexports/3.1a2.tex} \vspace{10pt} \noindent Og jeg kan altså se et mønster i mine determinanter. Først får jeg to $-1$-taller, derefter to $1$-taller, og så forfra igen. Min hypotese er altså at determinanterne af $F_n$ altid vil være enten $-1$ eller $1$, og at de bliver ved med at følge rækken \begin{equation} -1,-1,1,1,-1,-1,1,1,... \label{a:raekke} \end{equation} som er givet ved gaffelfunktionen \begin{equation} det(F_n) = \left\{ \begin{array}{ll} (-1)^{\frac{n}{2}} \cdot (-1)^n & \quad , n \text{ lige} \\ (-1)^{\frac{n-1}{2}} \cdot (-1)^n & \quad , n \text{ ulige} \end{array} \right. \label{a:raekke2} \end{equation} for alle $n \in \mathbb{N}$. \subsubsection*{Delopgave b} Jeg skal nu ved hjælp af matematiske argumenter vise at sammenhængen jeg fandt i delopgave a til at være \eqref{a:raekke2} nu også er sand. Det er logisk nok at determinanten for $n=1$ er $-1$, og determinanten for $n=2$ er også nemt fundet ved \begin{equation*} \det{\left[ \begin{array}{cc} 0 & -1 \\ -1 & 0 \end{array} \right]} = 0 \cdot 0 - (-1) \cdot (-1) = -1 \text{.} \end{equation*} Hvis jeg fra nu af går over til at argumentere ud fra definitionen af determinanten kan jeg også se på hvordan determinanten videre vil udvikle sig for værdier af $n \geq 3$. Jeg starter altså ud med at bruge kofaktormetoden til at finde et udtryk. Definitionen på en determinant til en vilkårlig $n \times n$ matrix $A$ er defineret ved: \begin{equation} \det{(A)} \equiv \sum_{i=1}^{n}{a_{i,1} A_{i,1}} \text{,} \label{b:determinantdef} \end{equation} hvor $A_{i,j}$ er den $(i,j)$'te kofaktor defineret ved \begin{equation} A_{i,j} \equiv (-1)^{i+j} \det{(M_{i,j}^A)} \text{,} \label{b:kofaktordef} \end{equation} hvor $M_{i,j}^A$ er $(n-1) \times (n-1)$ matricen taget fra $A$ ved at fjerne den $i$'te række og den $j$'te kolonne (søjle). Man kan i stedet for $1$-tallerne i \eqref{b:determinantdef} indsætte et vilkårligt tal $0 < t \leq n$, hvorfor man altså kan udvikle ud fra en vilkårlig søjle. I det følgende vil jeg holde mig til at bruge første søjle, hvorfor jeg altså bare lader 1-tallet stå. Det jeg her ser er at hvis jeg tager determinanten af en $n \times n$ matrix på formen $F_n$ vil jeg komme til at gange med nul med alle $f_{i,1}$ hvor $i \in [1;n-1]$, og for $i=n$ vil $f_{i,1} = -1$. Så første led i alle mine determinanter bliver $-1$. Med dette in mente har jeg altså udtrykket fra \eqref{b:determinantdef} til at være \begin{equation*} \det{(F_n)} = -1 \cdot F_{n,1} \text{,} \end{equation*} og nu kan jeg så bruge udtrykket for kofaktoren $F_{n,1}$ i \eqref{b:kofaktordef} og får \begin{equation} \det{(F_n)} = -1 \cdot (-1)^{n+1} \cdot \det{(M_{n,1}^{F_n})} \text{.} \label{b:udtrykfordeterminant} \end{equation} Jeg ser at udtrykket $M_{n,1}^{F_n}$ må være det samme som $F_{n-1}$ da jeg med kofaktoren fjerner den sidste række og den første søjle, hvorfor udtrykket i \eqref{b:udtrykfordeterminant} lig med følgende \begin{equation*} \det{(F_n)} = -1 \cdot (-1)^{n+1} \cdot \det{(F_{n-1})} \text{,} \end{equation*} som jeg udbygger ved at bruge det samme udtryk igen for at finde determinanten til $F_{n-1}$ og får \begin{align*} \det{(F_n)} &= -1 \cdot (-1)^{n+1} \cdot \det{(F_{n-1})} \\ &= -1 \cdot (-1)^{n+1} \cdot -1 \cdot (-1)^{n} \cdot \det{(F_{n-2})} \\ &= -1 \cdot (-1)^{n+1} \cdot -1 \cdot (-1)^{n} \cdot -1 \cdot (-1)^{n-1} \cdot \det{(F_{n-3})} \text{.} \end{align*} Denne kan jeg omskrive til produktet \begin{equation} \det{(F_n)} = \prod_{i=1}^{n}{(-1)(-1)^{n-i+2}} \text{,} \label{b:sammenhaengfordeterminant} \end{equation} som med Maple giver mig samme række som jeg får ved at finde determinanten af $F_n$. Jeg viser lige først hvordan jeg definerer funktionen, for derefter at vise udregningerne med denne i en sekvens for $n \in [1;20]$. \input{mapleexports/3.1b1.tex} \vspace{10pt} \noindent Og jeg ser altså at jeg får samme række som da jeg udregnede determinanten med {\verb+Determinant+}-kommandoen i delopgave a. Jeg har altså med \eqref{b:sammenhaengfordeterminant} vist min hypotese med et matematisk udtryk, at determinanterne for en række af matricer på formen for $F_n$ følger rækken vist i \eqref{a:raekke}. \\ \\ \noindent Jeg kunne også have valgt at bruge eliminationsmetoden til at finde et udtryk for determinanten, hvor jeg i stedet for at bruge definitionen ville have brugt argumenter for om der var et lige eller ulige antal rækker i $F_n$, for derefter at se på hvor mange rækker jeg skulle bytte rundt på for at jeg fik en trekantsmatrix (og på den måde bare kunne gange diagonalen sammen og skifte fortegn afhængigt af hvor mange rækkeoperationer jeg skulle lave på matricen). Denne metode vil jeg lige hurtigt vise, da denne er den der giver gaffelfunktionen som jeg fandt i \eqref{a:raekke2}, og ikke kun den rigtige række som jeg fandt med \eqref{b:sammenhaengfordeterminant}. Jeg ser at når jeg skal finde trekantsmatricen skal jeg for et ulige $n$ bruge samme rækkeoperationer af type I som jeg skal for $n-1$. Hvis mit $n$ og $n-1$ går op i 2 med et lige tal bliver fortegnet for produktet af determinanterne af mine elementarmatricer positivt, hvis det går op i 2 med et ulige tal bliver fortegnet negativt. Derudover skal jeg gange med diagonalen af min trappematrix, som må være $(-1)^n$. Samlet får jeg altså trappematricen i \eqref{a:raekke2}. Jeg kan lige vise dette for $n \leq 5$: \begin{align*} \det{(F_1)} &= -1 \\ \det{(F_2)} &= -1 \cdot \det{\left[\begin{array}{cc} -1&0\\ 0&-1 \end{array}\right]} = -1 \\ \det{(F_3)} &= -1 \cdot \det{\left[\begin{array}{ccc} -1&0&0\\ 0&-1&0\\ 0&0&-1 \end{array}\right]} = 1 \\ \det{(F_4)} &= -1 \cdot -1 \cdot \det{\left[\begin{array}{cccc} -1&0&0&0\\ 0&-1&0&0\\ 0&0&-1&0\\ 0&0&0&-1 \end{array}\right]} = 1 \\ \det{(F_5)} &= -1 \cdot -1 \cdot \det{\left[\begin{array}{ccccc} -1&0&0&0&0\\ 0&-1&0&0&0\\ 0&0&-1&0&0\\ 0&0&0&-1&0\\ 0&0&0&0&-1 \end{array}\right]} = -1 \end{align*} Det passer altså for min gaffelfunktion. \subsection*{Konklusion} Jeg fandt ud af at determinanten for en matrix på formen $F_n$ fulgte rækken \eqref{b:sammenhaengfordeterminant}, også givet som funktionen \eqref{a:raekke2}, samt at man kunne finde denne række både ved hjælp af eliminationsmetoden og kofaktormetoden. Metoden med kofaktoren er mest matematisk stringent, da denne går ud fra definitionen, men derimod er metoden med elimination nemmere at argumentere for. Sammenlagt er elimination derfor nok den nemmeste metode at bruge. \clearpage \setcounter{equation}{0} \subsection{Effektivitet for udregning af determinanter} \subsubsection*{Delopgave a} For at kunne argumentere for at jeg med kofaktormetoden altid for en $n \times n$ matrix (for $n \geq 2$) skal bruge mere end $n!$ multiplikationer eller divisioner vil jeg starte med at se på definitionen for determinanten. Denne er givet ved følgende for en vilkårlig $n \times n$ matrix $A$ : \begin{equation} \det{(A)} \equiv \sum_{i=1}^{n}{a_{i,1} A_{i,1}} \text{,} \label{2a:determinantdef} \end{equation} hvor $A_{i,j}$ er den $(i,j)$'te kofaktor defineret ved \begin{equation} A_{i,j} \equiv (-1)^{i+j} \det{(M_{i,j}^A)} \text{,} \label{2a:kofaktordef} \end{equation} hvor $M_{i,j}^A$ er $(n-1) \times (n-1)$ matricen taget fra $A$ ved at fjerne den $i$'te række og den $j$'te kolonne. Jeg vil lige bemærke at man i stedet for $1$-tallerne i \eqref{2a:determinantdef} kan indsætte et vilkårligt tal $0 < t \leq n$, hvorfor man altså kan udvikle ud fra en vilkårlig søjle, og ikke bare første søjle. Jeg holder mig dog bare i min udledning til første søjle for overskuelighedens skyld. Hvis jeg nu ser på en vilkårlig $n \times n$ matrix B og vil finde determinanten af denne, bruger jeg \eqref{2a:determinantdef} og finder at \begin{equation*} \det{(B)} = \sum_{i=1}^{n}{b_{i,1} B_{i,1}} \text{.} \end{equation*} Ved så at indsætte definitionen på kofaktoren $B_{i,1}$ fra \eqref{2a:kofaktordef} i ovenstående vil jeg få at \begin{equation*} \det{(B)} = \sum_{i=1}^{n}{b_{i,1} \cdot (-1)^{i+1} \det{(M_{i,1}^B)}} \text{,} \end{equation*} hvor $M_{i,j}^B$ er den $(n-1) \times (n-1)$ matrix der fås ved at fjerne række $i$ og søjle 1 i $B$. Jeg har her ovenfor allerede $n$ multiplikationer. Determinanten af undermatrixen $M_{i,j}^B$ er en dimension mindre end min matrix $B$, og udskriver jeg denne vil jeg få $n(n-1)$ multiplikationer mere inklusive en determinant af en under-undermatrix. Denne determinant vil så igen indeholde $(n-1)(n-2)$ multiplikationer. Jeg kan fortsætte på denne måde og få at antallet af multiplikationer for en $n \times n$ matrix $m_n$ er givet ved \begin{align*} m_n &= n + n m_{n-1} \\ &= n + n [(n-1) + (n-1) m_{n-2}] \\ &= n + n [(n-1) + (n-1)[(n-2)+ (n-2) m_{n-3}]] \text{,} \end{align*} som igen kan omskrives ved at gange ind i parenteserne efter at have udskrevet hele rækken (der for $n \in \mathbb{R}$ selvfølgelig kan være uendelig lang): \begin{equation*} m_n = n + n(n-1) + n(n-1)(n-2) + n(n-1)(n-2)(n-3) + \cdots + n! \text{,} \end{equation*} og det sidste led af rækken er altså $n!$, da definitionen på denne er givet ved \begin{equation*} n! = n(n-1)(n-2)(n-3)(n-4) \cdots 3 \cdot 2 \cdot 1 \text{.} \end{equation*} Jeg har altså med dette argumenteret for at man skal udføre over $n!$ multiplikationer for at udregne determinanten af en $n \times n$ matrix for $n \geq 2$ med kofaktormetoden. \subsubsection*{Delopgave b} Jeg skal i Maple udføre kommandoen fra opgavesedlen, som jeg nu først vil vise her med Maple-kode, for derefter at forklare yderligere: \input{mapleexports/3.2a1.tex} \begin{figure}[htb] \centering \includegraphics[width=0.9\textwidth]{mapleexports/3plot2d1.pdf} \label{fig:3.2b1} \end{figure} \noindent Kommandoen kan jeg dele op i flere dele for at forklare den. Først og fremmest er der en plotkommando der skal plotte de punkter der kommmer ud af en sekvens på formen {\verb+seq([x(n),y(n)],n=a..b)+}. Denne sekvens vil jeg gerne gå lidt mere i dybden med. Førstekoordinaten, $x(n)$, er givet ved et $n$, mens andenkoordinaten $y(n)$ er givet ved flere funktioner af $n$. Den yderste af funktionerne er {\verb+time+}, der udskriver hvor lang tid dennes kaldte kommando tager om at blive udregnet (dette er vel og mærke hvor lang tid CPU'en bruger på det). Udskriften af {\verb+time+} er $y(n)$-koordinaten i sekvensen. Inden i {\verb+time+} er kommandoen {\verb+Determinant+}, som Maple bruger for at finde determinanten til en funktion. Inden i {\verb+Determinant+} er så kommandoen {\verb+RandomMatrix+} der laver en tilfældig $n \times n$ matrix. I den sidste er det vigtigt at bemærke at det er dette $n$ der også er $x(n)$-koordinaten, og at det er dette $n$ som sekvensen ændrer for hver iteration. Det jeg til sidst får ud i min graf er altså punkter $(n,t)$ der viser hvor lang tid $t$ det tager for Maple af udregne determinanten af en $n \times n$ tilfældig matrix (egentlig er det også tiden Maple bruger på at udvælge den tilfældige matrix, men den tid er så kort i forhold til determinantudregningen at man ikke kan se den). \subsubsection*{Delopgave c} Jeg ser i delopgave a at hvis jeg skulle bruge kofaktormetoden blev antallet af multiplikationer meget hurtigt utrolig højt for voksende matricer. I delopgave b ser jeg hvor lang tid Maple bruger på at finde determinanten, og jeg ser at tiden det tager for udregningen (der er proportional med antallet af multiplikationer), over hovedet ikke flyver så hurtigt opad. For at sammenligne de to forskellige metoder, kofaktormetoden og den algoritme som Maple bruger, har jeg defineret et par funktioner i Maple og plottet disse sammen. Den første, $det(n)$, er den normale fakultetsfunktion (som et udtryk for hvor mange multiplikationer som jeg mindst skal udføre for at udregne determinanten med kofaktormetoden -- vist i delopgave a) ganget med en meget lille brøk, så den rent faktisk er mulig at se på mit plot (men så den stadig er illustrativ), mens den anden, $mapledet(n)$, er min egen approksimation af Maples udregningstider, et andengradspolynomium ganget med en lille brøk. Disse har jeg plottet sammen med mine data fra delopgave b der viser tiden rigtigt. Jeg får som følger (hvor jeg har defineret plottet med tiderne tidligere til at være $timeplot$): \input{mapleexports/3.2c1.tex} \begin{figure}[htb] \centering \includegraphics[width=0.9\textwidth]{mapleexports/3plot2d2.pdf} \label{fig:3.2c} \end{figure} \noindent Jeg ser altså at Maple tydeligvis \emph{ikke} bruger kofaktormetoden til at finde determinanter. Det kan simpelthen ikke lade sig gøre at udregne determinanten så hurtigt som Maple gør det med denne metode, og så er min røde linie i plottet endda et overslag over hvor mange multiplikationer man mindst skal udføre -- det egentlige antal er meget større. Jeg vil lige tilføje at man selvfølgelig ikke kan sammenligne de to grafer helt direkte, da grafen der opfører sig som et andengradspolynomie er et udtryk for hvor lang tid der bliver brugt på udregningerne, mens min graf $det(n)$ viser en fakultetsfunktion. Jeg kan dog sige at fakultetsfunktionen kun er multiplikationer, så denne må om noget stadig have et tidsforbrug der vokser som en fakultetsfunktion i Maple -- hvorfor min sammenligning alligevel kan bruges; det er tydeligt at {\verb+time+}-kommandoen på Maples udregninger ikke vokser som en fakultetsfunktion. \\ \\ \noindent Jeg skal til sidst forsøge at give et estimat af hvor mange multiplikationer/divisioner man kommer til at lave ved at bruge eliminationsmetoden til at finde determinanten. Når jeg gør dette vil jeg se på det værst mulige tilfælde, altså der hvor jeg har en matrix uden nuller i sine indgange. Når man skal bruge elimination til at finde determinanten for en matrix starter man med at udføre rækkeoperationer på matricen for at få den på trappeform. Dette kan man gøre udelukkende ved at bruge rækkeoperation III, der lægger et multiplum af en række til en anden række. Det antal multiplikationer og divisioner jeg skal udføre bliver altså det antal gange jeg skal gange indgange i rækker med et tal -- da jeg derefter jo bare adderer række til en anden. Hvis jeg har en $n \times n$ matrix skal jeg altså multiplicere første række med et tal for at kunne eliminere indgang $(2,1)$, derefter med et tal for at eliminere indgang $(3,1)$ osv. op til indgang $(n,1)$. Dette bliver $n (n-1)$ multiplikationer, da jeg skal gange hver indgang i første række $n-1$ gange. Derefter skal jeg så gange alle indgange (undtagen den første -- der nu er nul) i anden række med et tal for at eliminere alle indgange $(i>2,2)$. Dette giver mig endnu $(n-1)(n-2)$ multiplikationer. På denne måde kan jeg fortsætte til jeg har omskrevet matricen om til trappeform, hvilket vil være efter \begin{equation*} n (n-1) + (n-1)(n-2) + (n-2)(n-3) + \cdots + 3 \cdot 2 + 2 \cdot 1 \end{equation*} multiplikationer. Denne kan omskrives til summen \begin{equation*} \sum_{i=1}^{n}{(n-i+1)(n-i)} \text{,} \end{equation*} som igen kan omskrives til \begin{equation*} \sum_{i=1}^{n}{n^2 - 2ni +i^2 +n-i} \text{.} \end{equation*} Altså er elimination en metode der tager i størrelsesordenen $n^2$ multiplikationer, i modsætning til de langt over $n!$ multiplikationer der blev brugt ved kofaktormetoden. Sammenligner jeg dette ved hjælp af Maple i forhold til hvor mange multiplikationer man skal bruge med kofaktormetoden ser jeg: \input{mapleexports/3.2c2.tex} \vspace{10pt} \noindent Det er altså tydeligt at se hvordan den første, der viser eliminationsmetoden, bruger langt mindre multiplikationer end kofaktormetoden. \\ \\ Når Maple udregner determinanter kan man vælge hvilken metode den skal bruge, og jeg vil lige vise hvor stor forskel der er på de forskellige algoritmer. Jeg har ligesom i første delopgave brugt {\verb+time+}-kommandoen og nu i {\verb+Determinant+} sat et ekstra argument på, der fortæller hvilken metode der skal bruges. Grafen er vist på Figur 1. \begin{figure}[htb] \centering \includegraphics[width=0.9\textwidth]{mapleexports/3plot2d3.pdf} \label{fig:3.2timesammenligninger} \caption{Plot af tidsforbruget ved de forskellige metoder for at finde determinanter i Maple.} \end{figure} \noindent Specielt vil jeg gerne nævne den gule linie, der er kofaktormetoden (i Maple bare kaldt \emph{minor}), mens den lyseblå er \emph{multivar}, Gausselimination. Forskellen er tydelig, selv for $n \leq 20$. \subsection*{Konklusion} Jeg har redegjort for at der normalt skal udføres flere end $n!$ multiplikationer og divisioner for at finde determinanten for en $n\times n$ matrix ved kofaktormetoden, når $n \geq 2$. På samme måde har jeg givet et estimat af antallet af multiplikationer og divisioner der skal bruges for at finde determinanten med eliminationsmetoden. Derudover har jeg argumenteret for at Maple umuligt kan bruge kofaktormetoden når den udregner determinanter, og jeg har vist hvordan forskellige algoritmer i Maple tager forskellige tider for CPU'en at udregne determinanten. \end{document}