Lineær algebra og diskret matematikk : matematikk for ingeniører 8256233095 [PDF]

Zitiervorschau

Haugland - Stray - Ubøe

Lineær algebra og diskret matematikk MATEMATIKK FOR INGENIØRER

NB Rana Depotbiblioteket

®NKI Forlaget

© NKI Forlaget 1997 1. utgave 1. opplag 1997

Utgiver: NKI Forlaget, Hans Burums vei 30 Postboks 111, 1341 Bekkestua Tlf.: sentralbord 67 58 88 00 ordrekontor 67 58 89 00 Telefaks: 67 58 19 02 Illustrasjoner: Petter Heier Omslag: Wanda design as Sats: Frode Holen Trykk: GCSM as

Det må ikke kopieres fra denne boka i strid med åndsverkloven eller med avtaler om kopiering inngått med KOPINOR, interesseorgan for rettighetshavere til åndsverk. Kopiering i strid med lov eller avtale kan føre til erstatningsansvar og inndragning, og kan straffes med bøter eller fengsel. ISBN 82-562-3309-5

Forord Lineær algebra har med årene utviklet seg fra å være et eksklusivt mate­ matisk emne til å ta sin plass i brukerkurs i teknologiske og økonomiske fag. Denne læreboka i lineær algebra og diskret matematikk retter seg mot rammeplanene og undervisningsbehovet som gjelder teknologiske fag, men boka kan også danne grunnlaget for et mer matematisk orientert kurs i lineær algebra.

Boka starter med et kort innføringskapittel, der hensikten er å poengtere ulike sider ved lineær matematikk på en enkel måte. I det neste kapitlet utvikles vektorregningen i planet og rommet. Det legges vekt på geometriske begreper som projeksjon og rotasjon. Projeksjoner og rotasjoner er eksempler på lineære transformasjoner. Slike blir behandlet allment ved hjelp av matriser. Matrisealgebra nyttes og i likningsteorien og blir ellers anvendt på differensiallikninger. Lineære likningssystemer blir behandlet ved hjelp av gausseliminering. Teorien for lineære likningssystemer blir utviklet videre etter hvert som nye begreper kommer til. Det gjelder både determinantbegrepet og emner som lineær uavhengighet, basis og dimensjon. På samme måte som vi beskriver geometriske vektorer ved hjelp av koordinater, bruker vi matriser til å beskrive lineære transformasjoner.

Andre bruksområder for matriseteorien omfatter egenverdiproblemer, diagonalisering og kjeglesnitt, systemer av differensiallikninger og minste kvadraters metode.

Den siste delen av boka, diskret matematikk, er først og fremst tatt med for å dekke behovet som rammeplanene for ingeniørutdanningen legger opp til. Emner som behandles er mengdelære, logikk, kombinatorikk og bevis ved matematisk induksjon. En kort innføring i komplekse tall er tatt med som et tillegg bakerst i boka. Til slutt noen ord om bevis og matematisk stringens: Vi har gitt de fleste setningene i boka et fullstendig bevis. I en teknologisk utdanning vil det sikkert være naturlig å sløyfe en del av bevisene, og det må være opp til lærerne og studentene i fellesskap å gjøre det. Et eksempel er teorien om determinanter, der bevisene både kan virke innfløkte og særegne i forhold til de matematiske metodene ellers i boka. I andre deler av teorien spiller bevisene en mer sentral rolle, siden de ofte er konstruktive i den forstand at de definerer viktige algoritmer.

Vi påtar oss ikke å peke ut de bevisene som «enhver leser må studere», men vi minner om at i matematikken er et godt bevis også en god forklaring. Forfatterne, april 1997

Innhold 1 Lineære metoder og problemer Innledning 9 1-1 Lineær optimering 10 1-2 Et eksempel på produksjonsplanlegging 1-3 Matriser 14 Oppgaver 22

13

2 Vektorer, plan og linjer Innledning 25 2-1 Vektorer i planet og rommet 26 2-2 Koordinatisering 28 2-3 Prikkproduktet og projeksjoner 32 2-4 Likningsframstilling for et plan 36 2-5 Likninger og parameterframstilling for en rett linje 37 2-6 Projeksjoner på linjer og plan 39 2-7 Vektorproduktet 42 Oppgaver 44

3 Matrisealgebra Innledning 47 3-1 Matrisealgebra 48 3-2 Noen eksempler på lineære transformasjoner 58 3-3 Lineære transformasjoner beskrevet ved matriser 62 Oppgaver 67

4 Lineære likningssystemer Innledning 71 4-1 Allmenne lineære systemer 73 4-2 Gausseliminering 76 4-3 Gauss-Jordan-algoritmen 87 4-4 Vektorlikninger 91 Oppgaver 94

5 Determinanter Innledning 97 5-1 Determinanten til 2 x 2- og 3 x 3-matriser 98 5-2 Determinanten til en allmenn n x «-matrise 101 5-3 Regneregler for determinanter 104 5-4 Determinanter og lineære likningssystemer 116 5-5 Bevis til utvalgte setninger 118 Oppgaver 125

6 Vektorer i IR" Innledning 127 6-1 «-dimensjonale vektorer 128 6-2 Basiser for IR" og underrom i IR” 133 6-3 Radrom, søylerom og rang til en matrise 138 6-4 Nullrom og nullitet 141 6-5 Ortogonalitet i IR" 143 6-6 Lineære likningssystemer (oppsummering) 147 Oppgaver 149

7 Egenverdier og diagonalisering Innledning 153 7-1 Egenverdier 154 7-2 Diagonalisering 158 7-3 Egenverdiregning og differenslikninger Oppgaver 164

161

8 Overgangsmatriser og skifte av koordinater Innledning 167 8-1 Overgangsmatriser 168 8-2 Koordinatisering av lineære transformasjoner Oppgaver 175

173

9 Viktige klasser av matriser Innledning 179 9-1 Ortogonale matriser 180 9-2 Symmetriske matriser 182 9-3 Likedannete (similære) matriser Oppgaver 190

186

10 Bruk av matriser Innledning 193 10-1 Kjeglesnitt og symmetriske matriser 194 10-2 Tilnærming med en lineær funksjon 197 10-3 Det allmenne tilnærmingsproblemet 201 10-4 Diagonalisering og systemer av differensiallikninger Oppgaver 213

11 Mengdelære Innledning 217 11-1 Mengdelære 218 11-2 Operasjoner på mengder 219 11-3 Mengdealgebra og De Morgans lover 11-4 Venndiagrammer 222 Oppgaver 224

221

12 Matematisk logikk Innledning 227 12-1 Utsagnslogikk 228 12-2 Induksjonsbevis 239 Oppgaver 242

13 Kombinatorikk Innledning 245 13-1 Multiplikasjonsprinsippet 246 13-2 Fakultetuttrykk og Stirlings formel 13-3 Utvalg fra en mengde 250 Oppgaver 256

248

T Komplekse tall Innledning 259 T-l Kompleks addisjon og multiplikasjon T-2 Det komplekse planet 263 T-3 Polynomlikninger 266 Oppgaver 269

Stikkordregister

271

260

205

1 Lineære metoder og problemer Innledning I teknologi og vitenskap er det ikke alltid den mest kompliserte matema­ tikken som har størst nytteverdi. Ofte kan enkle ideer og teknikker spille en hovedrolle, til og med når vi skal løse svært kompliserte problemer.

Et slikt eksempel er lineær algebra. Dette feltet har fått stadig større praktisk betydning, ikke minst fordi det er lett å lage dataprogrammer som kan regne med lineære matematiske funksjoner. Dermed kan vi få en datamaskin til å gjøre regnearbeidet. Mange praktiske problemer i ingeniørfag, økonomi, statistikk osv fører til lineære likninger og ulik­ heter. Det er den delen av matematikken som blant annet handler om lineære likninger og ulikheter, vi kaller lineær algebra.

10

LINEÆRE METODER OG PROBLEMER

Dette kapitlet gir ikke noen sammenhengende innføring i lineær algebra. Kapitlet er ment som en liten forrett: Vi ønsker å vise noen typiske eksempler på hva vi kan bruke lineær algebra til. Vi skal også nevne begrepet matematisk modell. Den systematiske framstillingen av lineær algebra som matematisk disiplin starter i kapittel 2.

1-1 Lineær optimering Lineær optimering går ut på å finne maksimum (eller minimum) av en lineær funksjon når variablene er avgrenset til et område som er definert av et sett med lineære ulikheter. La oss vente litt med å definere begrepene lineær funksjon og lineær ulikhet. I stedet tar vi for oss en konkret situasjon, der vi får et maksimeringsproblem med to variabler.

Men aller først minner vi om at: y — ax + b

(1-1)

er den allmenne likningen for en rett linje i et plant, rettvinklet koordinatsystem. La (x, 71) være et punkt som ligger under linja. Da er 71 < y, der y er som i likning (1.1). Det vil si at 71 < ax + b, men den siste ulikheten kan vi også skrive slik: — ax + 71 < b.

Nå kan vi gjøre en oppsummering: • La 7 = ax 4- b være likningen for en rett linje, og la (x, 7) være et fritt valgt punkt i xy-planet. Da kan vi avgjøre om punktet ligger over, på eller under linja ved å bruke disse reglene'.

(1.2)

punktet ligger over linja dersom

(1.3)

punktet ligger på linja dersom

(1.4)

punktet ligger under linja dersom

— ax + 7 > b — ax + 7 = b — ax 4- 7 < b

Nå er vi forberedt på å regne eksempel 1-1.

EKSEMPEL 1-1 (1.5)

Finn den største verdien til uttrykket:

F(x,7) = 15 000x4-7507

når x og 7 skal oppfylle ulikhetene:

(1-6)

10x 4- 7 < 200

(1-7)

250x + 57 < 2500

(1.8)

0 < x og 0 < 7

Løsning Dette problemet kan vi løse grafisk. Vi starter med å finne ut hvor punktet (x, 7) kan ligge når alle ulikhetene (1.6)-(1.8) skal være oppfylt.

LINEÆRE METODER OG PROBLEMER

11

1 På grunn av ulikheten (1.6) og reglene (1.2) og (1.3) må (x, j/) ligge under linja y = — 10.x + 200. 2 På grunn av ulikheten (1.7) og reglene (1.2) og (1.3) må (x, 7) ligge under linja y = —50x + 500. 3 På grunn av de to ulikhetene (1.8) må (x, j>) ligge i første kvadrant.

Det grå området på figur 1-1 viser hvilke punkter (x, v) som oppfyller ulikhetene (1.6)-(1.8).

Figur 1-1 Det grå området på figuren består av de punktene som oppfyller alle ulikhetene (1.6)-(1.8)

Vi går tilbake til funksjonen som vi skal maksimere (se likning (1.5)). La Å være den linja som har likningen:

(1-9)

15 000x + 750^ = D

der D er en konstant. Vi har tegnet linja L på figur 1-1 for D « 450000. Hvis vi tenker oss at D minker mot null, svarer det til at vi parallellforskyver L mot origoen. Linja treffer da det grå området for første gang i punktet P, som er skjæringspunktet mellom linjene: (1.10)

10x + y — 200

(111)

250x + 5y = 2500

Vi løser dette likningssystemet og finner at P har koordinatene x = 7 og y = 130. Punktet P ligger derfor på den linja som har likningen:

(1.12)

15000* + 750y = 200 500

12

LINEÆRE METODER OG PROBLEMER

Resonnementet med å parallellforskyve L viser at hvis en linje L\ har likningen:

(1-13)

15 000x + 750y = Z>i

og skjærer det grå området på figur 1-1, må 0 < D\ < 200 500.

Vi kan dermed slutte at summen 15 000% + 750y får sin største verdi når x — 7 og y = 130, og at denne verdien er 200 500.

Et allment optimeringsproblem Et mer allment optimeringsproblem av samme type som ovenfor ville være å finne maksimumsverdien til uttrykket: (1-14)

G(x, y) = Cj%+ C2y

der Ci og C2 er kjente tall, og der variablene x og y varierer i et område som er avgrenset av en mangekant. Med samme slags geometrisk resonnement som i eksempel 1-1 kan vi vise at summen Cix + C2y får sin største verdi i et av hjørnene på mangekanten. Ved å sammenlikne verdiene til C\x + C2y når x og y er koordinatene til de ulike hjørnene, kan vi finne ut hvilket hjørne som gir uttrykket den største verdien.

Her er tre spørsmål som du bør tenke over:

1 Sett at du skal minimere uttrykket Cix + C2y i stedet for å maksimere det. Gå ut fra at du har vist at summen C\x + C2y har sitt maksimum i et hjørne på mangekanten. Gi to ulike forklaringer på at også minimumsverdien oppstår i et av hjørnene på mangekanten. 2 Kan uttrykket C]X + C2y få samme ekstremverdi i to ulike hjørner på mangekanten? Hva er i så fall vilkåret for at det skal skje? 3 Kan uttrykket C\x + C2y få samme ekstremverdi i flere enn to ulike hjørner på mangekanten? Hva er i så fall vilkåret for at det skal skje?

Vi sier at en funksjon (x, y) dersom funksjonen har formen:

(1.15)

/(x,

y) av to variabler x og y er lineær

/(x,y) = Cix + C2j;

der Ci og C2 er konstanter. Som en konklusjon kan vi nå oppsummere dette innledende avsnittet i en setning:

SETNING 1-1 La (x, y) /(x, y) være en lineær funksjon som er definert i et plant område. Gå ut fra at defmisjonsområdet er en mangekant. a) Da får f sin største verdi i et av mangekantens hjørner. Videre er pkt a likeverdig med pkt b: b) Funksjonen f får sin minste verdi i et av mangekantens hjørner.

LINEÆRE METODER OG PROBLEMER

13

Strengt tatt har vi bare vist at pkt a i setningen foran er riktig. Men dersom du svarte riktig på spørsmål 1 foran likning (1.15), kan du selv forklare at hele setningen er korrekt. Lineære funksjoner med to eller flere variabler støter vi på i mange praktiske problemer. I neste avsnitt skal vi drøfte en slik situasjon.

1-2 Et eksempel på produksj onsplanlegging Vi går ut fra at en gårdbruker disponerer 200 mål dyrkbar mark. Han skal drive med korn- eller melkeproduksjon, eller en kombinasjon.

Vi gjør følgende forutsetninger: 1 Årsfortjenesten per ku er 15 000 kr. 2 For å fore en ku i ett år trengs det 10 mål jord.

3 Kornproduksjon gir en årlig fortjeneste på 750 kr/mål.

4 En ku legger beslag på 250 timer av bondens arbeidstid i året, mens kornproduksjon krever 5 timer per mål i løpet av et år. 5 Bonden ønsker ikke å arbeide mer enn 2500 timer i året.

La x være antall kyr som brukes i melkeproduksjonen, mens y er antall mål som går med til kornproduksjon. Resten av jorda bruker bonden til å dekke kyrnes behov for gras. Gårdbrukeren ønsker å velge x og y slik at han får maksimal fortjeneste.

Du bør nå vise at forutsetningene vi har gjort, formulert med ulikheter der x og y inngår, nettopp leder til et maksimeringsproblem av samme type som i eksempel 1-1 (se side 10).

Forutsetningene 1-5 og den matematiske formuleringen av dem i avsnitt 1-1 illustrerer et viktig begrep: matematisk modellbygging. Ovenfor utviklet vi en matematisk modell for å oppnå størst mulig fortjeneste på gårdsdrift. Om dette er en god modell i et konkret tilfelle, avhenger av om forutsetningene som vi gjorde, passer til den situasjonen vi ønsker å studere. I mer kompliserte situasjoner får vi lineære funksjoner med flere variabler X], X2, xj,..., x„. Den grafiske metoden som vi brukte i avsnitt 1-1, kan vi ikke bruke hvis den lineære funksjonen som vi skal maksimere eller minimere, har flere enn to variabler. Idéer fra lineær algebra erstatter den todimensjonale grafikken, og den vanligste løsningsmetoden kalles simpleksmetoden. Metoden spiller en viktig rolle i produksjonsplanlegging, utforming av kommunikasjonsnett­ verk, transportsystemer osv. Simpleksmetoden er en algoritme som «leter» seg fram til et «optimalt hjørne» i en «-dimensjonal mangekant. I så måte er den en videreføring av det vi gjorde i eksempel 1-1.

14

LINEÆRE METODER OG PROBLEMER

(Ordet simpleks er et fellesord for mangekant, uavhengig av dimensjonstallet. En plan mangekant er en todimensjonal simpleks. En fasettslipt diamant er et eksempel på en tredimensjonal simpleks. Merk at hver fasett på diamanten er en todimensjonal simpleks! Det er typisk: Overflata på en «-dimensjonal simpleks er satt sammen av fasetter, og hver fasett er en (« - 1)-dimensjonal simpleks. Hvilke fasetter har en plan mangekant?)

Utviklingen av moderne datamaskiner har gjort at vi kan gjennomføre omfattende utregninger med simpleksmetoden.

Lineær optimering med

n

variabler

Det lineære optimeringsproblemet med n variabler kan vi formulere mate­ matisk slik: Finn maksimum av funksjonen:

(1.16)

£(xi, x2,.. •, xn) = Cix1 + C2x2 + ... + Cnxn

når disse vilkårene skal gjelde: Cl\nxn < b\ a22x2 + ... + a2nxn < b2

«11^1 + «12^2 + • • • +

«21*1 +

(1-17)

dn\X\ + an2%2 + • • • + ^nn^n < bn Her er Cj (1 < j < ri) og ay (1 < i < m og 1 < j < ri) kjente tall, mens x\,..., xn kan være antall produserte enheter av n forskjellige vareslag i en bedrift.

1-3 Matriser Vi skal avslutte dette kapitlet med å se litt på matriser. En allmenn m x nmatrise kan vi skrive som et rektangulært tallskjema:

(1-18)

A=

«il

«12

•

«21

«22

•

«2m

«ml

«m2

•

«mn _

•

«In

med m horisontale rader og n vertikale søyler. Vi skal her bare ta for oss 2 x 2-matriser, altså matriser på formen:

(119)

«11

«12

«21

«22

Tallene a\\, a\2, a2\ og a22 kaller vi matrisens elementer. I dette kapitlet skal vi forutsette at alle elementene i en matrise er reelle tall. Vi merker oss at elementet ay står i rad nummer i og i søyle nummer j i begge skjemaene (1.18) og (1.19).

LINEÆRE METODER OG PROBLEMER

15

A multiplisere en matrise med et tall Siden elementene i en matrise A er reelle tall, kan vi multiplisere A med et reelt tall t ved å multiplisere hvert matriseelement med t. Dermed får vi en regel for å multiplisere en matrise med et tall:

td\i ta^\

(1.20)

tCl\2 ta^2

DEFINISJON 1-1 Dersom A er en matrise, og dersom t er et reelt tall, multipliserer vi matrisen med tallet ved å multipisere hvert ele­ ment i matrisen med t.

Både matematikere og fysikere bruker ofte ordet skalar om et reelt tall, og de sier at en skalar - altså et tall - kan virke på eller operere på en matrise. Det matematikeren eller fysikeren da mener, er at hun multipliserer matrisen med tallet, slik definisjon 1-1 foreskriver.

A addere matriser Hvis både A og B er 2 x 2-matriser, der:

(1.21)

£11

Z>12

Z?21

^22

og A er som i likning (1.19), definerer vi summen A + B slik:

(1-22)

A + B= a“

«12 «22

+

£11 ^21

b\2

«11 + ^11

«12 + £12

^22

«21 + £21

«22 + £22

Dermed har vi denne definisjonen for addisjon med matriser: DEFINISJON 1-2 Dersom A og B er to matriser med like mange rader og like mange søyler, adderer vi A og B ved å addere sam­ svarende elementer.

Vi merker oss at etter definisjon 1-2 har det ikke noen mening å addere matriser som har ulikt antall rader og/eller ulikt antall søyler.

EKSEMPEL 1-2 La A, B og C være matrisene: (1-23)

8 0

og la t — 1 /4. Regn ut:

a) produktet tA b) summen B + C

16

og

C=

5 2

16

LINEÆRE METODER OG PROBLEMER

Løsning a) Vi bruker definisjon 1-1 og får: 4 16

8 0

(1-24)

2 0

1 4

b) Summen B + C får vi ved å bruke definisjon 1-2: (1-25)

Ii

4 8

5 2

C

5 1

A multiplisere matriser med hverandre Vi trenger enda en regneoperasjon med matriser: å multiplisere dem med hverandre. Vi skriver AB for produktet av to matriser A og B, og definerer det slik: «ii

(1-26)