Matematikk.net - Brukerbidrag [nb]

Matriser

2011-10-01T12:17:57Z

Svinepels:

Innen matematikk og innen særlig [[lineær algebra]], er en '''matrise''' en rektangulær tabell med tall eller mer generelle uttrykk. Innholdet i matriser kalles for elementer. For eksempel inneholder matrisen under seks elementer. 

<tex> \begin{bmatrix} 4 & -3 & 0 \\ 2\pi & 0.3 & 7 \end{bmatrix}</tex>
 

Man har definert regler for å legge sammen, trekke fra hverandre og multiplisere matriser. I tillegg er det mulig å multiplisere en matrise med en skalar, som ofte betegner et reelt eller komplekst tall. Disse operasjonene stiller visse krav til størrelsen på matrisene som er involvert. Med størrelsen på en matrise mener man antall rader og kolonner. Matrisen over har størrelse 2 × 3. Man betegner ofte matriser med store bokstaver, som ''A'', ''B'' og ''M''. Når man ønsker å presisere størrelsen til en matrise, kan man skrive <tex>A = [a_{i,j}]_{m \times n}</tex> der matrisen har størrelse ''m'' × ''n''.

Man kan få bruk for matriser i så og si hvert eneste eneste område innen naturvitenskap og teknologi. Innen numerikk har det blitt svært aktuelt å finne algoritmer som gjør at datamaskiner kan utføre ulike matriseoperasjoner på en mest effektiv måte, noe som er essensielt når man behandler store matriser med kanskje flere millioner elementer.

==Matriseoperasjoner==
En generell matrise ''A'' med størrelse ''m'' × ''n'' ser slik ut: 

<tex> A = \begin{bmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & & \vdots \\ a_{1,m} & a_{2,m} & \cdots & a_{m,n} \end{bmatrix} </tex> 

===Likhet===
For at to matriser skal være ''like'', må de ha samme størrelse, og elementet i en hvilken som helst rad og kolonne i den første matrisen skal være likt elementet i eksakt samme rad og kolonne i den andre matrisen. Vi kan formulere det matematisk slik: Hvis matrisen <tex>A=[a_{i,j}]</tex> og matrisen <tex>B=[b_{i,j}]</tex> er like og begge har størrelse ''m'' × ''n'', må vi ha ''a''''i'',''j'' = ''b''''i'',''j'' for alle ''i'' og ''j'' med 1 ≤ ''i'' ≤ ''m'' og 1 ≤ ''j'' ≤ ''n''.

===Addisjon===
For at addisjon mellom to matriser skal være definert, må de ha samme størrelse. Lar vi <tex>A=[a_{i,j}]</tex> og <tex>B=[b_{i,j}]</tex> begge være ''m'' × ''n'' -matriser, definerer vi ''A'' + ''B'' som en ny matrise hvor elementet i rad ''i'' og kolonne ''j'' er gitt ved <tex>a_{i,j} + b_{i,j}</tex>. Under følger et eksempel: 

<tex> A = \begin{bmatrix} 2 & 0 \\ -1 & 4 \end{bmatrix} \;\;\; B = \begin{bmatrix} 1 & 1 \\ 2 & -2 \end{bmatrix} \;\;\; A+B = \begin{bmatrix} 3 & 1 \\ 1 & 2 \end{bmatrix}</tex> 

===Multiplikasjon med en skalar===
I lineær algebra omtaler man reelle eller komplekse tall som skalarer. Hvis <tex>A=[a_{i,j}]</tex> er en matrise av størrelse ''m'' × ''n'' og ''c'' er en skalar, er matrisen ''cA'' definert som en ny matrise av størrelse ''m'' × ''n'' der elementet i rad nr. ''i'' og kolonne nr. ''j'' er gitt ved ''ca''''i'',''j''. Man multipliserer med andre ord alle elementene i matrisen ''A'' med skalaren ''c''. Et eksempel:

<tex>A= \begin{bmatrix} 1 & 0 & -3 \\ 0 & 5 & \frac{2}{5} \end{bmatrix} \;\;\; 2A = \begin{bmatrix} 2 & 0 & -6 \\ 0 & 10 & \frac{4}{5} \end{bmatrix} </tex>

Når det gjelder differansen mellom to matrise ''A'' og ''B'', defineres den som matrisen ''A'' + (-''B'') der -''B'' er matrisen ''B'' multiplisert med skalaren -1.

==Matriser som lineære transformasjoner==
- En matrise representer en avbildning mellom to vektorrom med respekt til gitte basiser.

[[Category:matrise]][[Category:ped]]
[[kategori:lex]]

Divisjonsalgoritmen

2011-10-01T11:22:28Z

Svinepels: /* Entydighet */

I aritmetikk og tallteori er '''divisjonsalgoritmen''' et fundamentalt teorem knyttet til [[divisjon]] blant heltallene. Det finnes flere metoder for å finne kvotienten og resten i en divisjon, men begrepet divisjonsalgoritmen refererer til det formelle utsagnet som understreker eksistensen og entydigheten til disse to tallene, til tross for at ordet algoritme inngår i navnet. Teoremet opptrer som en ingrediens i mange andre resultater i tallteori, for eksempel i den euklidske algoritmen, som brukes til å finne største felles divisor mellom to heltall.

==Formelt utsagn==
Divisjonsalgoritmen sier at for to heltall ''a'' og ''b'' > 0, så eksisterer det unike heltall ''q'' og ''r'' slik at

<tex>a=qr+b \;\;\; \textrm{der} \;\;\; 0 \leq r < b</tex>

Tallet ''a'' kalles for dividenden, ''b'' kalles for divisoren, ''q'' kalles for kvotienten og ''r'' kalles for resten. Det er vanlig å betegne kvotienten med ''q'' = ''a'' div ''b'' og resten med ''r'' = ''a'' mod ''b''.

==Eksempler==
* Hvis ''a'' = 14 og ''b'' = 6, da er kvotienten 2 og resten 2 siden <tex>14=2 \cdot 6 + 2</tex>.
* Hvis dividenden er 35 og divisoren er 7, så er ''q'' = 5 og ''r'' = 0 siden <tex>35 = 5 \cdot 7 + 0</tex>. Når resten er 0, sier vi at ''b'' ''deler'' ''a''.

==Bevis==
Beviset for divisjonsalgoritmen er basert på ''velordningsprinsippet'', som sier at dersom en ikke-tom mengde inneholder kun ikke-negative heltall, ja da må mengden inneholde et ''minste'' element. Vi deler beviset inn i to deler: Bevis for at ''q'' og ''r'' eksisterer, og bevis for at de er unike.

===Eksistens===
La ''a'' og ''b'' > 0 være vilkårlige heltall. Betrakt mengden

<tex>S = \{ a-xb \, | \, x \in \mathbb{Z} \: \textrm{og} \: a-xb \geq 0 \}</tex>

Vi skal først vise at ''S'' ikke er tom, uansett hvilke heltall ''a'' og ''b'' måtte være. Da må vi demonstrere en heltallsverdi for ''x'' slik at ''a'' - ''xb'' ≥ 0. Observer at siden ''b'' > 0, altså ''b'' ≥ 1, må |''a''|b ≥ |''a''| og ''a'' + |''a''|b ≥ ''a'' + |''a''|. Lar vi da ''x'' = -|''a''|, får vi at

<tex>a-xb = a-(-|a|)b = a+|a|b \geq a+|a| \geq 0</tex>

Altså ligger ''a'' - ''xb'' i ''S'' hvis ''x'' = -|''a''|. Dermed er mengden ikke-tom og inneholder kun ikke-negative heltall. Ifølge velordningsprinsippet følger det at ''S'' må inneholde et ''minste'' element, som vi kaller ''r''. Siden ''r'' er i ''S'', må det etter definisjonen av ''S'' finnes et heltall ''q'' som tilfredsstiller ''r'' = ''a'' - ''qb'', der ''r'' ≥ 0. Flytter vi ''qb'' over likhetstegnet, får vi

<tex>a = qb+r \;\; \textrm{der} \;\; r \geq 0</tex>

Nå gjenstår det å vise at ''r'' < ''b''. La oss anta det motsatte, nemlig at ''r'' ≥ ''b''. Betrakt så tallet

<tex>a-(q+1)b=(a-qb)-b=r-b \geq 0 \;\; \Leftrightarrow \;\; r \geq b </tex>

Antakelsen vår om at ''r'' ≥ ''b'' impliserer altså at det finnes et heltall ''a'' - (''q'' + 1)''b'' ≥ 0. Se på formen til tallet, det må per definisjon være med i ''S''. Men ''a'' - (''q'' + 1)''b'' = ''r'' - ''b'' < ''r'', noe som er umulig siden vi har valgt ''r'' til å være det minste elementet i ''S''. Vi må derfor forkaste antakelsen vår om at ''r'' ≥ ''b'', og følgelig er ''r'' < ''b''.

Vi har altså at for to vilkårlige heltall ''a'' og ''b'' > 0, så eksisterer det heltall ''q'' og ''r'' slik at

<tex>a=qb+r \;\; \textrm{der} \;\; 0 \leq r < b</tex>

Nå gjenstår det å vise at ''q'' og ''r'' er unike.

===Entydighet===
Anta at ''a'' har to representasjoner: ''a'' = ''qb'' + ''r'' = ''q'b'' + ''r' '', hvor 0 ≤ ''r'' < ''b'' og 0 ≤ ''r' '' < ''b''. Dette gir

<tex>r-r' = q'b-qb = b(q'-q) </tex>

Tar vi absoluttverdien av begge sider, får vi

<tex>|r-r'| = |b(q'-q)|=b|q'-q|</tex>

Legg merke til at vi kunne fjerne absoluttverditegnene rundt ''b'', siden vi har antatt at ''b'' > 0. Vi vet at 0 ≤ ''r' '' < ''b'', som gir -''b'' < -''r' '' ≤ 0. Legger vi denne ulikheten sammen med 0 ≤ ''r'' < ''b'', får vi

<tex> -b+0 < -r'+ r < 0 + b \;\; \Rightarrow \;\; -b < r'-r 

Ser vi nå på de tidligere uttrykkene våre, får vi |''r' '' - ''r''| = ''b''|''q'' - ''q' ''| < ''b''. Vi kan i siste ulikhet dele med ''b'' på begge sider. Siden ''b'' > 0, slipper vi å bekymre oss for å måtte snu ulikheten. Siden absoluttverdien av et uttrykk alltid er ikke-negativ, får vi nå

<tex>0 \leq |q'-q|<1 </tex>

Altså er eneste mulighet at |''q' '' - ''q''| = 0, som gir ''q' '' = ''q''. Men da må

<tex> |r-r'| = b \cdot 0 = 0 \;\; \Rightarrow \;\; r'=r </tex>

Altså har antakelsen vår om at det eksisterer en annen kvotient og en annen rest med de samme egenskapene som tallene ''q'' og ''r'' vi fant i første del av beviset, ført til konklusjonen om at disse andre kvotientene og restene er akkurat de samme. Dette bekrefter entydigheten til ''q'' og ''r'', og beviset er ferdig.

Divisjonsalgoritmen

2011-10-01T11:22:12Z

Svinepels: /* Entydighet */

I aritmetikk og tallteori er '''divisjonsalgoritmen''' et fundamentalt teorem knyttet til [[divisjon]] blant heltallene. Det finnes flere metoder for å finne kvotienten og resten i en divisjon, men begrepet divisjonsalgoritmen refererer til det formelle utsagnet som understreker eksistensen og entydigheten til disse to tallene, til tross for at ordet algoritme inngår i navnet. Teoremet opptrer som en ingrediens i mange andre resultater i tallteori, for eksempel i den euklidske algoritmen, som brukes til å finne største felles divisor mellom to heltall.

==Formelt utsagn==
Divisjonsalgoritmen sier at for to heltall ''a'' og ''b'' > 0, så eksisterer det unike heltall ''q'' og ''r'' slik at

<tex>a=qr+b \;\;\; \textrm{der} \;\;\; 0 \leq r < b</tex>

Tallet ''a'' kalles for dividenden, ''b'' kalles for divisoren, ''q'' kalles for kvotienten og ''r'' kalles for resten. Det er vanlig å betegne kvotienten med ''q'' = ''a'' div ''b'' og resten med ''r'' = ''a'' mod ''b''.

==Eksempler==
* Hvis ''a'' = 14 og ''b'' = 6, da er kvotienten 2 og resten 2 siden <tex>14=2 \cdot 6 + 2</tex>.
* Hvis dividenden er 35 og divisoren er 7, så er ''q'' = 5 og ''r'' = 0 siden <tex>35 = 5 \cdot 7 + 0</tex>. Når resten er 0, sier vi at ''b'' ''deler'' ''a''.

==Bevis==
Beviset for divisjonsalgoritmen er basert på ''velordningsprinsippet'', som sier at dersom en ikke-tom mengde inneholder kun ikke-negative heltall, ja da må mengden inneholde et ''minste'' element. Vi deler beviset inn i to deler: Bevis for at ''q'' og ''r'' eksisterer, og bevis for at de er unike.

===Eksistens===
La ''a'' og ''b'' > 0 være vilkårlige heltall. Betrakt mengden

<tex>S = \{ a-xb \, | \, x \in \mathbb{Z} \: \textrm{og} \: a-xb \geq 0 \}</tex>

Vi skal først vise at ''S'' ikke er tom, uansett hvilke heltall ''a'' og ''b'' måtte være. Da må vi demonstrere en heltallsverdi for ''x'' slik at ''a'' - ''xb'' ≥ 0. Observer at siden ''b'' > 0, altså ''b'' ≥ 1, må |''a''|b ≥ |''a''| og ''a'' + |''a''|b ≥ ''a'' + |''a''|. Lar vi da ''x'' = -|''a''|, får vi at

<tex>a-xb = a-(-|a|)b = a+|a|b \geq a+|a| \geq 0</tex>

Altså ligger ''a'' - ''xb'' i ''S'' hvis ''x'' = -|''a''|. Dermed er mengden ikke-tom og inneholder kun ikke-negative heltall. Ifølge velordningsprinsippet følger det at ''S'' må inneholde et ''minste'' element, som vi kaller ''r''. Siden ''r'' er i ''S'', må det etter definisjonen av ''S'' finnes et heltall ''q'' som tilfredsstiller ''r'' = ''a'' - ''qb'', der ''r'' ≥ 0. Flytter vi ''qb'' over likhetstegnet, får vi

<tex>a = qb+r \;\; \textrm{der} \;\; r \geq 0</tex>

Nå gjenstår det å vise at ''r'' < ''b''. La oss anta det motsatte, nemlig at ''r'' ≥ ''b''. Betrakt så tallet

<tex>a-(q+1)b=(a-qb)-b=r-b \geq 0 \;\; \Leftrightarrow \;\; r \geq b </tex>

Antakelsen vår om at ''r'' ≥ ''b'' impliserer altså at det finnes et heltall ''a'' - (''q'' + 1)''b'' ≥ 0. Se på formen til tallet, det må per definisjon være med i ''S''. Men ''a'' - (''q'' + 1)''b'' = ''r'' - ''b'' < ''r'', noe som er umulig siden vi har valgt ''r'' til å være det minste elementet i ''S''. Vi må derfor forkaste antakelsen vår om at ''r'' ≥ ''b'', og følgelig er ''r'' < ''b''.

Vi har altså at for to vilkårlige heltall ''a'' og ''b'' > 0, så eksisterer det heltall ''q'' og ''r'' slik at

<tex>a=qb+r \;\; \textrm{der} \;\; 0 \leq r < b</tex>

Nå gjenstår det å vise at ''q'' og ''r'' er unike.

===Entydighet===
Anta at ''a'' har to representasjoner: ''a'' = ''qb'' + ''r'' = ''q'b'' + ''r' '', hvor 0 ≤ ''r'' < ''b'' og 0 ≤ ''r' '' < ''b''. Dette gir

<tex>r-r' = q'b-qb = b(q'-q) </tex>

Tar vi absoluttverdien av begge sider, får vi

<tex>|r-r'| = |b(q'-q)|=b|q'-q|</tex>

Legg merke til at vi kunne fjerne absoluttverditegnene rundt ''b'', siden vi har antatt at ''b'' > 0. Vi vet at 0 ≤ ''r' '' < ''b'', som gir -''b'' < -''r' '' ≤ 0. Legger vi denne ulikheten sammen med 0 ≤ ''r'' < ''b'', får vi

<tex> -b+0 < -r'+ r < 0 + b \;\; \Rightarrow \;\; -b < r'-r 

Ser vi nå på de tidligere uttrykkene våre, får vi |''r' '' - ''r''| = ''b''|''q'' - ''q' ''| < ''b''. Vi kan i siste ulikhet dele med ''b'' på begge sider. Siden ''b'' > 0, slipper vi å bekymre oss for å måtte snu ulikheten. Siden absoluttverdien av et uttrykk alltid er ikke-negativ, får vi nå

<tex>0 \leq |q'-q|<1 </tex>

Altså er eneste mulighet at |''q' '' - ''q''| = 0, som gir ''q' '' = ''q''. Men da må

<tex> |r-r'| = b \cdot 0 = 0 \;\; \Rightarrow \;\; r'=r </tex>

Altså har antakelsen vår om at det eksisterer en annen kvotient og en annen rest med de samme egenskapene som tallene ''q'' og ''r'' vi fant i første del av beviset, ført til konklusjonen om at disse andre kvotientene og restene er akkurat de samme. Dette bevise entydigheten til ''q'' og ''r'', og beviset er ferdig.

Divisjonsalgoritmen

2011-10-01T11:19:40Z

Svinepels: /* Eksistens */

I aritmetikk og tallteori er '''divisjonsalgoritmen''' et fundamentalt teorem knyttet til [[divisjon]] blant heltallene. Det finnes flere metoder for å finne kvotienten og resten i en divisjon, men begrepet divisjonsalgoritmen refererer til det formelle utsagnet som understreker eksistensen og entydigheten til disse to tallene, til tross for at ordet algoritme inngår i navnet. Teoremet opptrer som en ingrediens i mange andre resultater i tallteori, for eksempel i den euklidske algoritmen, som brukes til å finne største felles divisor mellom to heltall.

==Formelt utsagn==
Divisjonsalgoritmen sier at for to heltall ''a'' og ''b'' > 0, så eksisterer det unike heltall ''q'' og ''r'' slik at

<tex>a=qr+b \;\;\; \textrm{der} \;\;\; 0 \leq r < b</tex>

Tallet ''a'' kalles for dividenden, ''b'' kalles for divisoren, ''q'' kalles for kvotienten og ''r'' kalles for resten. Det er vanlig å betegne kvotienten med ''q'' = ''a'' div ''b'' og resten med ''r'' = ''a'' mod ''b''.

==Eksempler==
* Hvis ''a'' = 14 og ''b'' = 6, da er kvotienten 2 og resten 2 siden <tex>14=2 \cdot 6 + 2</tex>.
* Hvis dividenden er 35 og divisoren er 7, så er ''q'' = 5 og ''r'' = 0 siden <tex>35 = 5 \cdot 7 + 0</tex>. Når resten er 0, sier vi at ''b'' ''deler'' ''a''.

==Bevis==
Beviset for divisjonsalgoritmen er basert på ''velordningsprinsippet'', som sier at dersom en ikke-tom mengde inneholder kun ikke-negative heltall, ja da må mengden inneholde et ''minste'' element. Vi deler beviset inn i to deler: Bevis for at ''q'' og ''r'' eksisterer, og bevis for at de er unike.

===Eksistens===
La ''a'' og ''b'' > 0 være vilkårlige heltall. Betrakt mengden

<tex>S = \{ a-xb \, | \, x \in \mathbb{Z} \: \textrm{og} \: a-xb \geq 0 \}</tex>

Vi skal først vise at ''S'' ikke er tom, uansett hvilke heltall ''a'' og ''b'' måtte være. Da må vi demonstrere en heltallsverdi for ''x'' slik at ''a'' - ''xb'' ≥ 0. Observer at siden ''b'' > 0, altså ''b'' ≥ 1, må |''a''|b ≥ |''a''| og ''a'' + |''a''|b ≥ ''a'' + |''a''|. Lar vi da ''x'' = -|''a''|, får vi at

<tex>a-xb = a-(-|a|)b = a+|a|b \geq a+|a| \geq 0</tex>

Altså ligger ''a'' - ''xb'' i ''S'' hvis ''x'' = -|''a''|. Dermed er mengden ikke-tom og inneholder kun ikke-negative heltall. Ifølge velordningsprinsippet følger det at ''S'' må inneholde et ''minste'' element, som vi kaller ''r''. Siden ''r'' er i ''S'', må det etter definisjonen av ''S'' finnes et heltall ''q'' som tilfredsstiller ''r'' = ''a'' - ''qb'', der ''r'' ≥ 0. Flytter vi ''qb'' over likhetstegnet, får vi

<tex>a = qb+r \;\; \textrm{der} \;\; r \geq 0</tex>

Nå gjenstår det å vise at ''r'' < ''b''. La oss anta det motsatte, nemlig at ''r'' ≥ ''b''. Betrakt så tallet

<tex>a-(q+1)b=(a-qb)-b=r-b \geq 0 \;\; \Leftrightarrow \;\; r \geq b </tex>

Antakelsen vår om at ''r'' ≥ ''b'' impliserer altså at det finnes et heltall ''a'' - (''q'' + 1)''b'' ≥ 0. Se på formen til tallet, det må per definisjon være med i ''S''. Men ''a'' - (''q'' + 1)''b'' = ''r'' - ''b'' < ''r'', noe som er umulig siden vi har valgt ''r'' til å være det minste elementet i ''S''. Vi må derfor forkaste antakelsen vår om at ''r'' ≥ ''b'', og følgelig er ''r'' < ''b''.

Vi har altså at for to vilkårlige heltall ''a'' og ''b'' > 0, så eksisterer det heltall ''q'' og ''r'' slik at

<tex>a=qb+r \;\; \textrm{der} \;\; 0 \leq r < b</tex>

Nå gjenstår det å vise at ''q'' og ''r'' er unike.

===Entydighet===
Anta at ''a'' har to representasjoner: ''a'' = ''qb'' + ''r'' = ''q'b'' + ''r' '', hvor 0 ≤ ''r'' < ''b'' og 0 ≤ ''r' '' < ''b''. Dette gir

<tex>r-r' = q'b-qb = b(q'-q) </tex>

Tar vi absoluttverdien av begge sider, får vi

<tex>|r-r'| = |b(q'-q)|=b|q'-q|</tex>

Legg merke til at vi kunne fjerne absoluttverditegnene rundt ''b'', siden vi har antatt at ''b'' > 0. Vi vet at 0 ≤ ''r' '' < ''b'', som gir -''b'' < -''r' '' ≤ 0. Legger vi denne ulikheten sammen med 0 ≤ ''r'' < ''b'', får vi

<tex> -b+0 < -r'+ r < 0 + b \;\; \Rightarrow \;\; -b < r'-r 

Ser vi nå på de tidligere uttrykkene våre, får vi |''r' '' - ''r''| = ''b''|''q'' - ''q' ''| < ''b''. Vi kan i siste ulikhet dele med ''b'' på begge sider. Siden ''b'' > 0, slipper vi å bekymre oss for å måtte snu ulikheten. Siden absoluttverdien av et uttrykk alltid er ikke-negativ, får vi nå

<tex>0 \leq |q'-q|<1 </tex>

Altså er eneste mulighet at |''q' '' - ''q''| = 0, som gir ''q' '' = ''q''. Men da må

<tex> |r-r'| = b \cdot 0 = 0 \;\; \Rightarrow \;\; r'=r </tex>

Altså har antakelsen vår om at det eksistere en annen kvotient og en annen rest med de samme egenskapene som vår allerede eksisterende kvotient og rest, ført til konklusjonen om at disse kvotientene og restene er akkurat de samme. Dette bevise entydigheten til ''q'' og ''r'', og beviset er ferdig.

Geometriske rekker

2011-09-30T23:07:32Z

Svinepels:

==Geometrisk progresjon==

En geometrisk progresjon <tex>(a_n)_{n\in\mathbb{N}}</tex> er en tallfølge der hvert tall er et konstant multippel av det forrige, dvs <tex>\frac{a_{n+1}}{a_n}=k</tex>.

Slike tallfølger kan skrives på formen <tex>a_n=a_1k^{n-1}</tex>

[http://www.matematikk.net/ressurser/oppgaver/kari/vis_oppgaver.php?q=9FB%2B9FC%2B9FD%2B9FE%2B9FF%7Ctimer_off%7Cshow_all%7Cnq%5B5%5D%7Ccat%5B35%5D%7Cdiff%5B0%5D%26quser_submit_step3 Test deg selv]

==Geometrisk rekke==

En geometrisk rekke er summen av elementene i en geometrisk progresjon.

For geometriske rekker <tex>a_n=a_1k^{n-1}</tex> er <tex>S_n=\sum_{i=1}^n a_i=a_1\frac{k^n-1}{k-1}</tex>

===Bevis for summeformel===
Betrakt tallet <tex>(k-1)(1+k+k^2+k^3+ \ldots +k^n)</tex>. Ganger vi ut parentesene, får vi <tex>(k+k^2+k^3+ \ldots + k^{n+1})-(1+k+k^2+k^3+ \ldots + k^n) = k^{n+1}-1</tex>. Men dersom

<tex>(k-1)(1+k+k^2+ \ldots + k^n) = k^{n+1}-1</tex>

kan vi dele med faktoren <tex>(k-1)</tex> på begge sider og få

<tex>\sum_{i=0}^{n}k^i = 1+k+k^2+ \ldots + k^n = \frac{k^{n+1}-1}{k-1} </tex>

Multipliserer vi så med <tex>a_1</tex> på begge sider, vil vi oppnå summeformelen, og beviset er ferdig.

==Uendelige geometriske rekker==

Dersom <tex>-1<k<1</tex> i en geometrisk tallfølge <tex>a_n=a_1k^{n-1}</tex> sier vi at den konvergerer. Det vil si at summen av uendelig mange etterfølgende elementer i følgen har en endelig verdi.

I slike tilfeller er <tex>\lim_{n\to\infty}S_n=\lim_{n\to\infty}\sum_{i=1}^n a_i=\frac{a_1}{1-k}</tex>

----
[[R2 Hovedside|Tilbake til R2 Hovedside]]

[[Kategori:Algebra]]
[[Kategori:R2]]
[[Kategori:S2]]
[[Kategori:Ped]]

Bruker:Svinepels

2011-09-30T22:57:00Z

Svinepels: Ny side: Intet svin uten pels.

Intet svin uten pels.

Divisjonsalgoritmen

2011-09-30T22:47:04Z

Svinepels: Ny side: I aritmetikk og tallteori er '''divisjonsalgoritmen''' et fundamentalt teorem knyttet til divisjon blant heltallene. Det finnes flere metoder for å finne kvotienten og resten i en divi...

I aritmetikk og tallteori er '''divisjonsalgoritmen''' et fundamentalt teorem knyttet til [[divisjon]] blant heltallene. Det finnes flere metoder for å finne kvotienten og resten i en divisjon, men begrepet divisjonsalgoritmen refererer til det formelle utsagnet som understreker eksistensen og entydigheten til disse to tallene, til tross for at ordet algoritme inngår i navnet. Teoremet opptrer som en ingrediens i mange andre resultater i tallteori, for eksempel i den euklidske algoritmen, som brukes til å finne største felles divisor mellom to heltall.

==Formelt utsagn==
Divisjonsalgoritmen sier at for to heltall ''a'' og ''b'' > 0, så eksisterer det unike heltall ''q'' og ''r'' slik at

<tex>a=qr+b \;\;\; \textrm{der} \;\;\; 0 \leq r < b</tex>

Tallet ''a'' kalles for dividenden, ''b'' kalles for divisoren, ''q'' kalles for kvotienten og ''r'' kalles for resten. Det er vanlig å betegne kvotienten med ''q'' = ''a'' div ''b'' og resten med ''r'' = ''a'' mod ''b''.

==Eksempler==
* Hvis ''a'' = 14 og ''b'' = 6, da er kvotienten 2 og resten 2 siden <tex>14=2 \cdot 6 + 2</tex>.
* Hvis dividenden er 35 og divisoren er 7, så er ''q'' = 5 og ''r'' = 0 siden <tex>35 = 5 \cdot 7 + 0</tex>. Når resten er 0, sier vi at ''b'' ''deler'' ''a''.

==Bevis==
Beviset for divisjonsalgoritmen er basert på ''velordningsprinsippet'', som sier at dersom en ikke-tom mengde inneholder kun ikke-negative heltall, ja da må mengden inneholde et ''minste'' element. Vi deler beviset inn i to deler: Bevis for at ''q'' og ''r'' eksisterer, og bevis for at de er unike.

===Eksistens===
La ''a'' og ''b'' > 0 være vilkårlige heltall. Betrakt mengden

<tex>S = \{ a-xb \, | \, x \in \mathbb{Z} \: \textrm{og} \: a-xb \geq 0 \}</tex>

Vi skal først vise at ''S'' ikke er tom, uansett hvilke heltall ''a'' og ''b'' måtte være. Da må vi demonstrere en heltallsverdi for ''x'' slik at ''a'' - ''xb'' ≥ 0. Observer at siden ''b'' > 0, altså ''b'' ≥ 1, må |''a''|b ≥ |''a''| og ''a'' + |''a''|b ≥ ''a'' + |''a''|. Lar vi da ''x'' = -|''a''|, får vi at

<tex>a-xb = a-(-|a|)b = a+|a|b \geq a+|a| \geq 0</tex>

Altså ligger ''a'' - ''xb'' i ''S'' hvis ''x'' = -|''a''|. Dermed er mengden ikke-tom og inneholder kun ikke-negative heltall. Ifølge velordningsprinsippet følger det at ''S'' må inneholde et ''minste'' element, som vi kaller ''r''. Siden ''r'' er i ''S'', må det etter definisjonen av ''S'' finnes et heltall ''q'' som tilfredsstiller ''r'' = ''a'' - ''qb'', der ''r'' ≥ 0. Flytter vi ''qb'' over likhetstegnet, får vi

<tex>a = qb+r \;\; \textrm{der} \;\; r \geq 0</tex>

Nå gjenstår det å vise at ''r'' < ''b''. La oss anta det motsatte, nemlig at 'r'' ≥ ''b''. Betrakt så tallet

<tex>a-(q+1)b=(a-qb)-b=r-b \geq 0 \;\; \Leftrightarrow \;\; r \geq b </tex>

Antakelsen vår om at ''r'' ≥ ''b'' impliserer altså at det finnes et heltall ''a'' - (''q'' + 1)''b'' ≥ 0. Se på formen til tallet, det må per definisjon være med i ''S''. Men ''a'' - (''q'' + 1)''b'' = ''r'' - ''b'' < ''r'', noe som er umulig siden vi har valgt ''r'' til å være det minste elementet i ''S''. Vi må derfor forkaste antakelsen vår om at ''r'' ≥ ''b'', og følgelig er ''r'' < ''b''.

Vi har altså at for to vilkårlige heltall ''a'' og ''b'' > 0, så eksisterer det heltall ''q'' og ''r'' slik at

<tex>a=qb+r \;\; \textrm{der} \;\; 0 \leq r < b</tex>

Nå gjenstår det å vise at ''q'' og ''r'' er unike.

===Entydighet===
Anta at ''a'' har to representasjoner: ''a'' = ''qb'' + ''r'' = ''q'b'' + ''r' '', hvor 0 ≤ ''r'' < ''b'' og 0 ≤ ''r' '' < ''b''. Dette gir

<tex>r-r' = q'b-qb = b(q'-q) </tex>

Tar vi absoluttverdien av begge sider, får vi

<tex>|r-r'| = |b(q'-q)|=b|q'-q|</tex>

Legg merke til at vi kunne fjerne absoluttverditegnene rundt ''b'', siden vi har antatt at ''b'' > 0. Vi vet at 0 ≤ ''r' '' < ''b'', som gir -''b'' < -''r' '' ≤ 0. Legger vi denne ulikheten sammen med 0 ≤ ''r'' < ''b'', får vi

<tex> -b+0 < -r'+ r < 0 + b \;\; \Rightarrow \;\; -b < r'-r 

Ser vi nå på de tidligere uttrykkene våre, får vi |''r' '' - ''r''| = ''b''|''q'' - ''q' ''| < ''b''. Vi kan i siste ulikhet dele med ''b'' på begge sider. Siden ''b'' > 0, slipper vi å bekymre oss for å måtte snu ulikheten. Siden absoluttverdien av et uttrykk alltid er ikke-negativ, får vi nå

<tex>0 \leq |q'-q|<1 </tex>

Altså er eneste mulighet at |''q' '' - ''q''| = 0, som gir ''q' '' = ''q''. Men da må

<tex> |r-r'| = b \cdot 0 = 0 \;\; \Rightarrow \;\; r'=r </tex>

Altså har antakelsen vår om at det eksistere en annen kvotient og en annen rest med de samme egenskapene som vår allerede eksisterende kvotient og rest, ført til konklusjonen om at disse kvotientene og restene er akkurat de samme. Dette bevise entydigheten til ''q'' og ''r'', og beviset er ferdig.

Tallfølger

2011-09-25T21:12:04Z

Svinepels:

En tallfølge er en ordnet liste med tall hvor hvert tall er assosiert med et positivt heltall <tex>n</tex>. Når vi skriver ut elementene etter stigende <tex>n</tex> får vi en følge. Man kan betrakte en tallfølge som en funksjon fra de positive heltallene <tex>\mathbb{Z}^+</tex> til de reelle tallene, <tex>\mathbb{R}</tex>, eventuelt til de komplekse tallene <tex>\mathbb{C}</tex>.

En følge kan være uendelig lang eller ha et endelig antall elementer.

<blockquote style="padding: 1em; border: 3px dotted red;">

'''Eksempel'''

:1,2,3,4,5
Dette er en endelig følge med 5 elementer.

----

:2,4,6,8,...
Dette er en uendelig lang følge. De tre prikkene til sist kjennetegner dette.

----

:1,3,5,...,9
Denne følgen er endelig, men med mindre det er spesifisert vet vi ikke hvor mange elementer følgen består av.

</blockquote>

==Eksplisitte uttrykk==

Følger kan uttrykkes som funksjoner <tex>a_n</tex> (sammenlign med <tex>f(x)</tex>), der <tex>n</tex> er et positivt heltall.

<blockquote style="padding: 1em; border: 3px dotted red;">

'''Eksempel'''

:<tex>a_n=n\,,\,n\in[3,7]</tex>
Skriver vi ut denne følgen, får vi
:3,4,5,6,7

----

:<tex>a_n=n^2</tex>
Ettersom definisjonsmengden til <tex>n</tex> ikke er spesifisert, kan vi gå ut ifra at følgen omfatter alle <tex>n\in\mathbb{N}</tex>. Skriver vi ut følgen får vi da
:1,4,9,16,25,...

</blockquote>

==Rekursive uttrykk==

Det er også mulig å definere følger ved å relatere de forskjellige leddene med hverandre. Da får vi ligninger på formen

<tex>f(a_n,a_{n-1},...,a_1,a_0,n)=0</tex>

Hvis vi sammen med et slikt uttrykk har informasjon om ett av leddene, er følgen entydig bestemt.

Dette kalles et rekursivt uttrykk og vises best gjennom noen eksempler:

<blockquote style="padding: 1em; border: 3px dotted red;">

'''Eksempel'''

:<tex>a_n=a_{n-1}+n\,,\,a_0=0</tex>
Ettersom ingen opplysninger og definisjonsmengden til <tex>n</tex> er gitt, kan vi gå ut ifra at følgen dekker alle positive heltallige <tex>n</tex>. Skriver vi ut følgen og starter fra <tex>n=0</tex>, får vi
:0,1,3,6,10,15,...
I denne følgen er hvert ledd <tex>a_n</tex> summen av de <tex>n</tex> første heltallene. Dette ser vi også fra det rekursive uttrykket ved at hvert i hvert ledd legges det neste heltallet til summen av de forrige.

----

Følger trenger ikke være bestemt av én funksjon. Forskjellige funksjoner kan bestemme leddene i forskjellige deler av følgen.

:<tex>a_n=\left{\begin{matrix} 0 & \text{if} & n=0 \\ 1 & \text{if} & n=1 \\ a_{n-1}+a_{n-2} & \text{if} & n>1 \end{matrix}</tex>
Hvis vi skriver ut denne følgen og starter fra <tex>n=0</tex>, får vi
:0,1,1,2,3,5,8,13,21,34,55,89,144...
Denne følgen kalles ''Fibonaccifølgen'' og har mange interessante geometriske og tallteoretiske egenskaper. Blant annet vil forholdet mellom to påfølgende tall gå mot Det gylne snitt når <tex>n</tex> går mot uendelig.
</blockquote>

== Konvergens ==

Vi sier at en følge <tex>(a_n)_{n\in\mathbb{N}}</tex> konvergerer mot et element <tex>a</tex> dersom <tex>\lim_{n\to\infty}a_n=a</tex>. En aritmetisk følge vil derfor ikke konvergere siden den vokser ubegrenset.

<blockquote style="padding: 1em; border: 3px dotted red;">

'''Eksempel'''
: Følgen definert ved <tex> f_n=\frac{1}{n}</tex> konvergerer mot <tex>0</tex> når <tex>n\to\infty</tex> siden <tex>\lim_{n\to\infty}\frac{1}{n}=0</tex>
----
: Følgen definert ved <tex>g_n=\cos(\frac{1}{n})</tex> vil konvergere mot <tex>1</tex> når <tex>n\to\infty</tex> siden argumentet går mot <tex>0</tex> og <tex>\cos(0)=1</tex>.
</blockquote>

----
[[R2 Hovedside|Tilbake til R2 Hovedside]]

[[Kategori:Algebra]]
[[Kategori:R2]]
[[Kategori:S2]]
[[Kategori:Ped]]