System af lineære ligninger - System of linear equations

I matematik er et system med lineære ligninger (eller lineært system ) en samling af en eller flere lineære ligninger, der involverer det samme sæt variabler . For eksempel,

${\ displaystyle {\ begin {alignat} {7} 3x && \;+\; && 2y && \;-\; && z && \; = \; && 1 & \\ 2x && \;-\; && 2y && \;+\; && 4z && \; = \ ; &&-2 & \\-x && \;+\; && {\ tfrac {1} {2}} y && \;-\; && z && \; = \; && 0 & \ end {alignat}}}$

er et system med tre ligninger i de tre variabler x , y , z . En løsning på et lineært system er en tildeling af værdier til variablerne, således at alle ligningerne samtidig opfyldes. En løsning på ovenstående system er givet af

${\ displaystyle {\ begin {alignat} {2} x & \, = \, & 1 \\ y & \, = \, &-2 \\ z & \, = \, &-2 \ end {alignat}}}$

da det gør alle tre ligninger gyldige. Ordet "system" angiver, at ligningerne skal overvejes samlet, snarere end individuelt.

I matematik er teorien om lineære systemer grundlaget og en grundlæggende del af lineær algebra , et emne, der bruges i de fleste dele af moderne matematik. Computational algoritmer til at finde løsningerne er en vigtig del af numerisk lineær algebra , og spille en fremtrædende rolle i teknik , fysik , kemi , datalogi , og økonomi . Et system med ikke-lineære ligninger kan ofte tilnærmes af et lineært system (se linearisering ), en nyttig teknik, når man laver en matematisk model eller computersimulering af et relativt komplekst system .

Meget ofte er koefficienterne for ligningerne reelle eller komplekse tal, og løsningerne søges i det samme antal tal, men teorien og algoritmerne gælder for koefficienter og løsninger inden for ethvert felt . For opløsninger i en integreret domæne ligesom ringen af hele tal , eller i andre algebraiske strukturer , andre teorier er blevet udviklet, se Lineær ligning over en ring . Integer lineær programmering er en samling metoder til at finde den "bedste" heltal løsning (når der er mange). Gröbner -grundteori giver algoritmer, når koefficienter og ukendte er polynomer . Også tropisk geometri er et eksempel på lineær algebra i en mere eksotisk struktur.

Elementære eksempler

Trivialt eksempel

Systemet med en ligning i en ukendt

${\ displaystyle 2x = 4}$

har løsningen

${\ displaystyle x = 2.}$

Imidlertid anses et lineært system normalt for at have mindst to ligninger.

Enkelt ikke -privat eksempel

Den enkleste form for utriveligt lineært system involverer to ligninger og to variabler:

${\ displaystyle {\ begin {alignat} {5} 2x && \;+\; && 3y && \; = \; && 6 & \\ 4x && \;+\; && 9y && \; = \; && 15 &. \ end {alignat}}}$

En metode til løsning af et sådant system er som følger. Løs først den øverste ligning med hensyn til : ${\ displaystyle x}$${\ displaystyle y}$

${\ displaystyle x = 3-{\ frac {3} {2}} y.}$

Nu erstatte dette udtryk for x ind i bunden ligning:

${\ displaystyle 4 \ left (3-{\ frac {3} {2}} y \ right)+9y = 15.}$

Dette resulterer i en enkelt ligning, der kun involverer variablen . Løsning giver , og erstatter dette tilbage i ligningen for udbytter . Denne metode generaliserer til systemer med yderligere variabler (se "eliminering af variabler" nedenfor eller artiklen om elementær algebra .) ${\ displaystyle y}$${\ displaystyle y = 1}$${\ displaystyle x}$${\ displaystyle x = 3/2}$

Generel form

Et generelt system med m lineære ligninger med n ukendte kan skrives som

${\ displaystyle {\ begin {align} a_ {11} x_ {1}+a_ {12} x_ {2}+\ cdots+a_ {1n} x_ {n} & = b_ {1} \\ a_ {21} x_ {1}+a_ {22} x_ {2}+\ cdots+a_ {2n} x_ {n} & = b_ {2} \\ & \ \ \ vdots \\ a_ {m1} x_ {1}+a_ {m2} x_ {2} +\ cdots +a_ {mn} x_ {n} & = b_ {m}, \ end {align}}}$

hvor er de ukendte, er systemets koefficienter og er de konstante vilkår. ${\ displaystyle x_ {1}, x_ {2}, \ ldots, x_ {n}}$${\ displaystyle a_ {11}, a_ {12}, \ ldots, a_ {mn}}$${\ displaystyle b_ {1}, b_ {2}, \ ldots, b_ {m}}$

Ofte er koefficienterne og ukendte reelle eller komplekse tal , men heltal og rationelle tal ses også, ligesom polynomer og elementer i en abstrakt algebraisk struktur .

Vektorligning

En yderst nyttig opfattelse er, at hver ukendt er en vægt for en søjlevektor i en lineær kombination .

${\ displaystyle x_ {1} {\ begin {bmatrix} a_ {11} \\ a_ {21} \\\ vdots \\ a_ {m1} \ end {bmatrix}}+x_ {2} {\ begin {bmatrix} a_ {12} \\ a_ {22} \\\ vdots \\ a_ {m2} \ end {bmatrix}} +\ cdots +x_ {n} {\ begin {bmatrix} a_ {1n} \\ a_ {2n} \\\ vdots \\ a_ {mn} \ end {bmatrix}} = {\ begin {bmatrix} b_ {1} \\ b_ {2} \\\ vdots \\ b_ {m} \ end {bmatrix}}}$

Dette gør det muligt at bringe hele sproget og teorien om vektorrum (eller mere generelt moduler ) i spil. For eksempel kaldes samlingen af ​​alle mulige lineære kombinationer af vektorerne på venstre side deres spændvidde , og ligningerne har en løsning lige når den højre vektor er inden for dette spænd. Hvis hver vektor inden for dette spændvidde har præcis ét udtryk som en lineær kombination af de givne venstrevektorer, så er enhver løsning unik. Under alle omstændigheder har spændet et grundlag for lineært uafhængige vektorer, der garanterer præcis et udtryk; og antallet af vektorer i dette grundlag (dets dimension ) kan ikke være større end m eller n , men det kan være mindre. Dette er vigtigt, fordi hvis vi har m uafhængige vektorer, er en løsning garanteret uanset højre side og ellers ikke garanteret.

Matrixligning

Vektorligningen svarer til en matrixligning af formen

${\ displaystyle A \ mathbf {x} = \ mathbf {b}}$

hvor A er en m × n matrix, x er en kolonnevektor med n poster, og b er en kolonnevektor med m poster.

${\ displaystyle A = {\ begin {bmatrix} a_ {11} & a_ {12} & \ cdots & a_ {1n} \\ a_ {21} & a_ {22} & \ cdots & a_ {2n} \\\ vdots & \ vdots & \ ddots & \ vdots \\ a_ {m1} & a_ {m2} & \ cdots & a_ {mn} \ end {bmatrix}}, \ quad \ mathbf {x} = {\ begin {bmatrix} x_ {1} \\ x_ {2} \\\ vdots \\ x_ {n} \ end {bmatrix}}, \ quad \ mathbf {b} = {\ begin {bmatrix} b_ {1} \\ b_ {2} \\\ vdots \ \ b_ {m} \ end {bmatrix}}}$

Antallet af vektorer i et grundlag for spændvidde udtrykkes nu som matrixens rang .

Løsningssæt

En løsning af et lineært system er en tildeling af værdier til variablerne x ₁ , x ₂ , ..., x _n, således at hver af ligningerne er opfyldt. Det sæt af alle mulige løsninger kaldes løsning sæt .

Et lineært system kan opføre sig på en af ​​tre mulige måder:

1. Systemet har uendeligt mange løsninger .
2. Systemet har en unik løsning .
3. Systemet har ingen løsning .

Geometrisk fortolkning

For et system, der involverer to variabler ( x og y ), bestemmer hver lineær ligning en linje på xy - planet . Fordi en løsning til et lineært system skal opfylde alle ligningerne, er løsningssættet skæringspunktet mellem disse linjer og er derfor enten en linje, et enkelt punkt eller det tomme sæt .

For tre variabler bestemmer hver lineær ligning et plan i det tredimensionelle rum , og løsningssættet er skæringspunktet mellem disse planer. Således kan løsningssættet være et plan, en linje, et enkelt punkt eller det tomme sæt. For eksempel, da tre parallelle planer ikke har et fælles punkt, er løsningen af ​​deres ligninger tom; løsningssættet af ligningerne for tre planer, der skærer hinanden på et punkt, er et enkelt punkt; hvis tre planer passerer gennem to punkter, har deres ligninger mindst to fælles løsninger; faktisk er løsningssættet uendeligt og består i, at hele linjen passerer gennem disse punkter.

For n variabler bestemmer hver lineær ligning et hyperplan i n -dimensionelt rum . Løsningen er skæringspunktet mellem disse hyperplaner og er en flad , som kan have en hvilken som helst dimension lavere end n .

Generel adfærd

Generelt bestemmes et lineært systems adfærd af forholdet mellem antallet af ligninger og antallet af ukendte. Her betyder "generelt", at der kan forekomme en anden adfærd for specifikke værdier for ligningskoefficienterne.

• Generelt har et system med færre ligninger end ukendte uendeligt mange løsninger, men det har muligvis ingen løsning. Et sådant system er kendt som et underbestemt system .
• Generelt har et system med samme antal ligninger og ukendte en enkelt unik løsning.
• Generelt har et system med flere ligninger end ukendte ingen løsning. Et sådant system er også kendt som et overbestemt system .

I det første tilfælde er dimensionen af løsningssættet generelt lig med n - m , hvor n er antallet af variabler og m er antallet af ligninger.

De følgende billeder illustrerer denne trikotomi i tilfælde af to variabler:

En ligning	To ligninger	Tre ligninger

Det første system har uendeligt mange løsninger, nemlig alle punkterne på den blå linje. Det andet system har en enkelt unik løsning, nemlig skæringspunktet mellem de to linjer. Det tredje system har ingen løsninger, da de tre linjer ikke har noget fælles punkt.

Det skal huskes, at ovenstående billeder kun viser det mest almindelige tilfælde (det generelle tilfælde). Det er muligt, at et system med to ligninger og to ukendte ikke har nogen løsning (hvis de to linjer er parallelle), eller at et system med tre ligninger og to ukendte kan løses (hvis de tre linjer skærer hinanden på et enkelt punkt).

Et system af lineære ligninger opfører sig anderledes end det generelle tilfælde, hvis ligningerne er lineært afhængige , eller hvis det er inkonsekvent og ikke har flere ligninger end ukendte.

Ejendomme

Uafhængighed

Ligningerne for et lineært system er uafhængige, hvis ingen af ​​ligningerne kan udledes algebraisk fra de andre. Når ligningerne er uafhængige, indeholder hver ligning nye oplysninger om variablerne, og fjernelse af en af ​​ligningerne øger størrelsen på løsningssættet. For lineære ligninger er logisk uafhængighed det samme som lineær uafhængighed .

For eksempel ligningerne

${\ displaystyle 3x+2y = 6 \; \; \; \; {\ text {og}} \; \; \; \; 6x+4y = 12}$

ikke er uafhængige - de er den samme ligning, når de skaleres med en faktor to, og de ville producere identiske grafer. Dette er et eksempel på ækvivalens i et system af lineære ligninger.

For et mere kompliceret eksempel, ligningerne

${\ displaystyle {\ begin {alignat} {5} x && \;-\; && 2y && \; = \; &&-1 & \\ 3x && \;+\; && 5y && \; = \; && 8 & \\ 4x && \;+\; && 3y && \; = \; && 7 & \ end {alignat}}}$

ikke er uafhængige, fordi den tredje ligning er summen af ​​de to andre. Faktisk kan enhver af disse ligninger udledes af de to andre, og en hvilken som helst af ligningerne kan fjernes uden at påvirke løsningssættet. Graferne for disse ligninger er tre linjer, der skærer hinanden på et enkelt punkt.

Konsistens

Et lineært system er inkonsekvent, hvis det ikke har nogen løsning, og ellers siges det at være konsekvent . Når systemet er inkonsekvent, er det muligt at udlede en modsætning fra ligningerne, der altid kan omskrives som sætningen 0 = 1 .

For eksempel ligningerne

${\ displaystyle 3x+2y = 6 \; \; \; \; {\ text {og}} \; \; \; \; 3x+2y = 12}$

er inkonsekvente. Faktisk ved at trække den første ligning fra den anden og multiplicere begge sider af resultatet med 1/6, får vi 0 = 1 . Graferne for disse ligninger på xy -planet er et par parallelle linjer.

Det er muligt for tre lineære ligninger at være inkonsekvente, selvom to af dem er konsistente sammen. For eksempel ligningerne

${\ displaystyle {\ begin {alignat} {7} x && \;+\; && y && \; = \; && 1 & \\ 2x && \;+\; && y && \; = \; && 1 & \\ 3x && \;+\; && 2y && \ ; = \; && 3 & \ end {alignat}}}$

er inkonsekvente. Ved at lægge de to første ligninger sammen giver 3 x + 2 y = 2 , som kan trækkes fra den tredje ligning for at give 0 = 1 . To af disse ligninger har en fælles løsning. Det samme fænomen kan forekomme for et vilkårligt antal ligninger.

Generelt opstår der uoverensstemmelser, hvis ligningens venstre side i et system er lineært afhængige, og de konstante udtryk ikke tilfredsstiller afhængighedsforholdet. Et ligningssystem, hvis venstre side er lineært uafhængige, er altid konsekvent.

Sagt på en anden måde, ifølge Rouché – Capelli -sætningen , er ethvert ligningssystem (overbestemt eller på anden måde) inkonsekvent, hvis rangen af den forstørrede matrix er større end koefficientmatrixens rang . Hvis rækken af ​​disse to matricer på den anden side er ens, skal systemet have mindst en løsning. Løsningen er unik, hvis og kun hvis rangen er lig med antallet af variabler. Ellers har den generelle løsning k frie parametre, hvor k er forskellen mellem antallet af variabler og rangen; derfor er der i et sådant tilfælde en uendelighed af løsninger. Rangen af ​​et ligningssystem (dvs. rangen af ​​den udvidede matrix) kan aldrig være højere end [antallet af variabler] + 1, hvilket betyder, at et system med et vilkårligt antal ligninger altid kan reduceres til et system, der har en antal uafhængige ligninger , der højst er lig med [antallet af variabler] + 1.

Ækvivalens

To lineære systemer, der bruger det samme sæt variabler, er ækvivalente, hvis hver af ligningerne i det andet system kan udledes algebraisk fra ligningerne i det første system og omvendt. To systemer er ækvivalente, hvis begge er inkonsekvente, eller hver ligning for hver af dem er en lineær kombination af ligningerne for den anden. Det følger heraf, at to lineære systemer er ækvivalente, hvis og kun hvis de har det samme løsningssæt.

Løsning af et lineært system

Der er flere algoritmer til løsning af et system af lineære ligninger.

Beskrivelse af løsningen

Når løsningssættet er begrænset, reduceres det til et enkelt element. I dette tilfælde er den unikke løsning beskrevet af en sekvens af ligninger, hvis venstre side er navnene på de ukendte og højre side er f.eks . De tilsvarende værdier . Når en ordre på de ukendte er blevet rettet, for eksempel den alfabetiske rækkefølge, kan løsningen beskrives som en vektor af værdier, ligesom for det foregående eksempel. ${\ displaystyle (x = 3, \; y = -2, \; z = 6)}$${\ displaystyle (3, \,-2, \, 6)}$

For at beskrive et sæt med et uendeligt antal løsninger, betegnes nogle af variablerne typisk som frie (eller uafhængige eller som parametre ), hvilket betyder, at de får lov til at tage enhver værdi, mens de resterende variabler er afhængige af værdierne for gratis variabler.

Overvej f.eks. Følgende system:

${\ displaystyle {\ begin {alignat} {7} x && \;+\; && 3y && \;-\; && 2z && \; = \; && 5 & \\ 3x && \;+\; && 5y && \;+\; && 6z && \; = \ ; && 7 & \ end {alignat}}}$

Løsningen til dette system kan beskrives ved følgende ligninger:

${\ displaystyle x = -7z-1 \; \; \; \; {\ tekst {og}} \; \; \; \; y = 3z+2 {\ tekst {.}}}$

Her er z den frie variabel, mens x og y er afhængige af z . Ethvert punkt i løsningssættet kan opnås ved først at vælge en værdi for z og derefter beregne de tilsvarende værdier for x og y .

Hver ledige variabel giver løsningsrummet en frihedsgrad , hvis antal er lig med dimensionen af løsningssættet. For eksempel er løsningssættet for ovenstående ligning en linje, da et punkt i løsningssættet kan vælges ved at angive værdien af ​​parameteren z . En uendelig løsning af højere orden kan beskrive et plan eller et højere dimensionelt sæt.

Forskellige valg for de gratis variabler kan føre til forskellige beskrivelser af det samme løsningssæt. For eksempel kan løsningen på ovenstående ligninger alternativt beskrives som følger:

${\ displaystyle y =-{\ frac {3} {7}} x+{\ frac {11} {7}} \; \; \; \; {\ tekst {og}} \; \; \; \; z =-{\ frac {1} {7}} x-{\ frac {1} {7}} {\ tekst {.}}}$

Her er x den frie variabel, og y og z er afhængige.

Eliminering af variabler

Den enkleste metode til at løse et system af lineære ligninger er at gentagne gange eliminere variabler. Denne metode kan beskrives som følger:

1. I den første ligning skal du løse en af ​​variablerne med hensyn til de andre.
2. Erstat dette udtryk i de resterende ligninger. Dette giver et ligningssystem med en færre ligning og en færre ukendt.
3. Gentag, indtil systemet reduceres til en enkelt lineær ligning.
4. Løs denne ligning, og erstat derefter tilbage, indtil hele løsningen er fundet.

Overvej f.eks. Følgende system:

${\ displaystyle {\ begin {alignat} {7} x && \;+\; && 3y && \;-\; && 2z && \; = \; && 5 & \\ 3x && \;+\; && 5y && \;+\; && 6z && \; = \ ; && 7 & \\ 2x && \;+\; && 4y && \;+\; && 3z && \; = \; && 8 & \ end {alignat}}}$

At løse den første ligning for x giver x = 5 + 2 z - 3 y , og tilslutter denne til den anden og tredje ligningsudbytte

${\ displaystyle {\ begin {alignat} {5} -4y && \;+\; && 12z && \; = \; &&-8 & \\-2y && \;+\; && 7z && \; = \; &&-2 & \ end {alignat }}}$

At løse den første af disse ligninger for y giver y = 2 + 3 z , og tilslutning af denne til den anden ligning giver z = 2 . Vi har nu:

${\ displaystyle {\ begin {alignat} {7} x && \; = \; && 5 && \;+\; && 2z && \;-\; && 3y & \\ y && \; = \; && 2 && \;+\; && 3z &&&&& \\ z && \ ; = \; && 2 &&&&&&&&&& end {alignat}}}$

Ved at erstatte z = 2 i den anden ligning får y = 8 , og substitution af z = 2 og y = 8 i den første ligning giver x = −15 . Derfor er løsningssættet det enkelte punkt ( x , y , z ) = (−15, 8, 2) .

Reduktion af rækker

I rækkereduktion (også kendt som Gaussisk eliminering ) er det lineære system repræsenteret som en forstærket matrix :

${\ displaystyle \ left [{\ begin {array} {rrr | r} 1 & 3 & -2 & 5 \\ 3 & 5 & 6 & 7 \\ 2 & 4 & 3 & 8 \ end {array}} \ right] {\ text {.}}}$

Denne matrix ændres derefter ved hjælp af elementære rækkeoperationer, indtil den når form for reduceret rækkeekselon . Der er tre typer elementære rækkeoperationer:

Type 1 : Skift positionerne på to rækker.

Type 2 : Multiplicer en række med en nul -skalar .

Type 3 : Føj til en række et skalær multiplum af en anden.

Fordi disse operationer er reversible, repræsenterer den udvidede matrix, der produceres, altid et lineært system, der svarer til originalen.

Der er flere specifikke algoritmer til række-reducere en forstørret matrix, hvoraf den enkleste er Gauss-eliminering og Gauss-Jordan-eliminering . Den følgende beregning viser eliminering af Gauss -Jordan, der er anvendt på matrixen ovenfor:

${\ displaystyle {\ begin {align} \ left [{\ begin {array} {rrr | r} 1 & 3 & -2 & 5 \\ 3 & 5 & 6 & 7 \\ 2 & 4 & 3 & 8 \ end {array}} \ højre] & \ sim \ venstre [{\ begin {array} {rrr | r} 1 & 3 & -2 & 5 \\ 0 & -4 & 12 & -8 \\ 2 & 4 & 3 & 8 \ end {array}} \ højre] \ sim \ venstre [{\ begin {array} {rrr | r} 1 & 3 & -2 & 5 \ \ 0 & -4 & 12 & -8 \\ 0 & -2 & 7 & -2 \ slut {array}} \ højre] \ sim \ venstre [{\ begin {array} {rrr | r} 1 & 3 & -2 & 5 \\ 0 & 1 & -3 & 2 \\ 0 &- 2 & 7 & -2 \ end {array}} \ højre] \\ & \ sim \ venstre [{\ begin {array} {rrr | r} 1 & 3 & -2 & 5 \\ 0 & 1 & -3 & 2 \\ 0 & 0 & 1 & 2 \ end {array}} \ højre ] \ sim \ venstre [{\ begin {array} {rrr | r} 1 & 3 & -2 & 5 \\ 0 & 1 & 0 & 8 \\ 0 & 0 & 1 & 2 \ slut {array}} \ højre] \ sim \ venstre [{\ begin {array} {rrr | r } 1 & 3 & 0 & 9 \\ 0 & 1 & 0 & 8 \\ 0 & 0 & 1 & 2 \ end {array}} \ højre] \ sim \ venstre [{\ begin {array} {rrr | r} 1 & 0 & 0 & -15 \\ 0 & 1 & 0 & 8 \\ 0 & 0 & 1 & 2 \ end {array}} \ højre ]. \ end {align}}}$

Den sidste matrix er i form af reduceret række -echelon og repræsenterer systemet x = −15 , y = 8 , z = 2 . En sammenligning med eksemplet i det foregående afsnit om den algebraiske eliminering af variabler viser, at disse to metoder faktisk er de samme; forskellen ligger i, hvordan beregningerne skrives ned.

Cramers regel

Cramers regel er en eksplicit formel for løsningen af ​​et system af lineære ligninger, med hver variabel givet af en kvotient af to determinanter . For eksempel løsningen på systemet

${\ displaystyle {\ begin {alignat} {7} x & \;+& \; 3y & \;-& \; 2z & \; = & \; 5 \\ 3x & \;+& \; 5y & \;+& \; 6z & \; = & \; 7 \\ 2x & \;+& \; 4y & \;+& \; 3z & \; = & \; 8 \ end {alignat}}}$

er givet af

${\ displaystyle x = {\ frac {\, {\ begin {vmatrix} 5 & 3 & -2 \\ 7 & 5 & 6 \\ 8 & 4 & 3 \ end {vmatrix}} \,} {\, {\ begin {vmatrix} 1 & 3 & -2 \\ 3 & 5 & 6 \\ 2 & 4 & 3 \ end {vmatrix}} \,}}, \; \; \; \; y = {\ frac {\, {\ begin {vmatrix} 1 & 5 & -2 \\ 3 & 7 & 6 \\ 2 & 8 & 3 \ end {vmatrix} } \,} {\, {\ begin {vmatrix} 1 & 3 & -2 \\ 3 & 5 & 6 \\ 2 & 4 & 3 \ end {vmatrix}} \,}}, \; \; \; \; z = {\ frac {\, { \ begin {vmatrix} 1 & 3 & 5 \\ 3 & 5 & 7 \\ 2 & 4 & 8 \ end {vmatrix}} \,} {\, {\ begin {vmatrix} 1 & 3 & -2 \\ 3 & 5 & 6 \\ 2 & 4 & 3 \ end {vmatrix}} \,}}. }$

For hver variabel er nævneren determinanten for matricen af ​​koefficienter , mens tælleren er determinanten for en matrix, hvor en kolonne er blevet erstattet af vektoren med konstante termer.

Selvom Cramers regel teoretisk er vigtig, har den ringe praktisk værdi for store matricer, da beregningen af ​​store determinanter er noget besværlig. (Faktisk beregnes store determinanter nemmest ved hjælp af radreduktion.) Desuden har Cramers regel meget dårlige numeriske egenskaber, hvilket gør den uegnet til at løse selv små systemer pålideligt, medmindre operationerne udføres i rationel aritmetik med ubegrænset præcision.

Matrix løsning

Hvis ligningssystemet udtrykkes i matrixformen , kan hele løsningssættet også udtrykkes i matrixform. Hvis matrixen A er firkantet (har m rækker og n = m kolonner) og har fuld rang (alle m rækker er uafhængige), så har systemet en unik løsning givet af ${\ displaystyle A \ mathbf {x} = \ mathbf {b}}$

${\ displaystyle \ mathbf {x} = A^{-1} \ mathbf {b}}$

hvor er den inverse af A . Mere generelt, uanset om m = n eller ej og uanset rang A , er alle løsninger (hvis der findes) givet ved hjælp af Moore-Penrose pseudoinverse af A , angivet som følger: ${\ displaystyle A^{-1}}$${\ displaystyle A^{+}}$

${\ displaystyle \ mathbf {x} = A^{+} \ mathbf {b}+\ venstre (IA^{+} A \ højre) \ mathbf {w}}$

hvor er en vektor med frie parametre, der spænder over alle mulige n × 1 vektorer. En nødvendig og tilstrækkelig betingelse for, at en eller flere løsninger findes, er, at den potentielle løsning, der opnås ved hjælp af tilfredsstiller - det vil sige, at Hvis denne betingelse ikke holder, er ligningssystemet inkonsekvent og har ingen løsning. Hvis betingelsen holder, er systemet konsekvent, og der findes mindst én løsning. For eksempel, i det ovennævnte tilfælde, hvor A er kvadratisk og af fuld rang, simpelthen lig med og den generelle løsningsligning forenkler til ${\ displaystyle \ mathbf {w}}$${\ displaystyle \ mathbf {w} = \ mathbf {0}}$${\ displaystyle A \ mathbf {x} = \ mathbf {b}}$${\ displaystyle AA^{+} \ mathbf {b} = \ mathbf {b}.}$${\ displaystyle A^{+}}$${\ displaystyle A^{-1}}$

${\ displaystyle \ mathbf {x} = A^{-1} \ mathbf {b} +\ venstre (IA^{-1} A \ højre) \ mathbf {w} = A^{-1} \ mathbf {b } +\ venstre (II \ højre) \ mathbf {w} = A^{-1} \ mathbf {b}}$

som tidligere nævnt, hvor er helt droppet ud af opløsningen og kun efterladt en enkelt løsning. I andre tilfælde er der imidlertid rester, og derfor giver en uendelighed af potentielle værdier for den frie parametervektor en uendelighed af løsninger af ligningen. ${\ displaystyle \ mathbf {w}}$${\ displaystyle \ mathbf {w}}$${\ displaystyle \ mathbf {w}}$

Andre metoder

Mens systemer med tre eller fire ligninger let kan løses i hånden (se Cracovian ), bruges computere ofte til større systemer. Standardalgoritmen til løsning af et system af lineære ligninger er baseret på gaussisk eliminering med nogle ændringer. For det første er det vigtigt at undgå division med små tal, hvilket kan føre til unøjagtige resultater. Dette kan gøres ved omorganisering af ligningerne, hvis det er nødvendigt, en proces kendt som drejning . For det andet betyder algoritmen ikke ligefrem gøre Gauss elimination, men det beregner LU nedbrydning af matricen A . Dette er for det meste et organisatorisk værktøj, men det er meget hurtigere, hvis man skal løse flere systemer med den samme matrix A, men forskellige vektorer b .

Hvis matrixen A har en særlig struktur, kan denne udnyttes til at opnå hurtigere eller mere præcise algoritmer. For eksempel kan systemer med en symmetrisk positiv bestemt matrix løses dobbelt så hurtigt med Cholesky -nedbrydningen . Levinson -rekursion er en hurtig metode til Toeplitz -matricer . Der findes også særlige metoder til matricer med mange nulelementer (såkaldte sparsomme matricer ), som ofte vises i applikationer.

En helt anden tilgang er ofte taget til meget store systemer, som ellers ville tage for meget tid eller hukommelse. Ideen er at starte med en indledende tilnærmelse til løsningen (som slet ikke behøver at være præcis) og ændre denne tilnærmelse i flere trin for at bringe den tættere på den sande løsning. Når tilnærmelsen er tilstrækkelig præcis, anses dette for at være løsningen på systemet. Dette fører til klassen af iterative metoder . For nogle sparsomme matricer forbedrer indførelsen af ​​tilfældighed hastigheden af ​​de iterative metoder.

Der er også en kvantealgoritme til lineære ligningssystemer .

Homogene systemer

Et system med lineære ligninger er homogent, hvis alle de konstante termer er nul:

${\ displaystyle {\ begin {alignat} {7} a_ {11} x_ {1} && \;+\; && a_ {12} x_ {2} && \;+\ cdots+\; && a_ {1n} x_ {n } && \; = \; &&& 0 \\ a_ {21} x_ {1} && \;+\; && a_ {22} x_ {2} && \;+\ cdots+\; && a_ {2n} x_ {n} && \; = \; &&& 0 \\ &&&&&&&&&& vdots \; \ &&& \\ a_ {m1} x_ {1} && \;+\; && a_ {m2} x_ {2} && \;+\ cdots+\; && a_ { mn} x_ {n} && \; = \; &&& 0. \\\ ende {alignat}}}$

Et homogent system svarer til en matrixligning af formen

${\ displaystyle A \ mathbf {x} = \ mathbf {0}}$

hvor A er en m × n matrix, x er en kolonnevektor med n poster, og 0 er nulvektoren med m poster.

Homogent løsningssæt

Hvert homogent system har mindst en løsning, kendt som nul (eller triviel ) løsning, som opnås ved at tildele værdien nul til hver af variablerne. Hvis systemet har en ikke-ental matrix ( det ( A ) ≠ 0 ), er det også den eneste løsning. Hvis systemet har en ental matrix, er der et løsningssæt med et uendeligt antal løsninger. Dette løsningssæt har følgende yderligere egenskaber:

1. Hvis u og v er to vektorer, der repræsenterer løsninger til et homogent system, så er vektorsummen u + v også en løsning til systemet.
2. Hvis u er en vektor, der repræsenterer en løsning til et homogent system, og r er en hvilken som helst skalar , så er r u også en løsning til systemet.

Disse er nøjagtigt de egenskaber, der kræves for, at løsningssættet er et lineært underrum af R ⁿ . Især opløsningen indstillet til et homogent system er den samme som nul plads af den tilsvarende matrix A . Numeriske løsninger til et homogent system kan findes med en enkeltværdi -dekomponering .

Forhold til ikke -homogene systemer

Der er et tæt forhold mellem løsningerne til et lineært system og løsningerne til det tilsvarende homogene system:

${\ displaystyle A \ mathbf {x} = \ mathbf {b} \ qquad {\ text {og}} \ qquad A \ mathbf {x} = \ mathbf {0}.}$

Specifikt, hvis p er en specifik løsning til det lineære system A x = b , kan hele løsningssættet beskrives som

${\ displaystyle \ left \ {\ mathbf {p} +\ mathbf {v}: \ mathbf {v} {\ text {er enhver løsning til}} A \ mathbf {x} = \ mathbf {0} \ right \} .}$

Geometrisk siger dette, at løsningssættet for A x = b er en oversættelse af løsningssættet for A x = 0 . Nærmere bestemt kan fladen til det første system opnås ved at oversætte det lineære underrum for det homogene system med vektoren p .

Denne begrundelse gælder kun, hvis systemet A x = b har mindst én løsning. Dette sker, hvis og kun hvis vektoren b løgne i billedet af den lineære transformation A .

Se også

Noter

Referencer

• Anton, Howard (1987), Elementary Linear Algebra (5. udgave), New York: Wiley , ISBN 0-471-84819-0
• Beauregard, Raymond A .; Fraleigh, John B. (1973), Et første kursus i lineær algebra: med valgfri introduktion til grupper, ringe og felter , Boston: Houghton Mifflin Company , ISBN 0-395-14017-X
• Burden, Richard L .; Faires, J. Douglas (1993), Numerical Analysis (5. udgave), Boston: Prindle, Weber og Schmidt , ISBN 0-534-93219-3
• Golub, Gene H .; Van Loan, Charles F. (1996), Matrix Computations (3. udgave), Baltimore: Johns Hopkins University Press , ISBN 0-8018-5414-8
• Harper, Charlie (1976), Introduction to Mathematical Physics , New Jersey: Prentice-Hall , ISBN 0-13-487538-9

Yderligere læsning

• Axler, Sheldon Jay (1997), Linear Algebra Done Right (2. udgave), Springer-Verlag, ISBN 0-387-98259-0
• Lay, David C. (22. august 2005), Lineær algebra og dens applikationer (3. udgave), Addison Wesley, ISBN 978-0-321-28713-7
• Meyer, Carl D. (15. februar 2001), Matrix Analysis and Applied Linear Algebra , Society for Industrial and Applied Mathematics (SIAM), ISBN 978-0-89871-454-8, arkiveret fra originalen den 1. marts 2001
• Poole, David (2006), Linear Algebra: A Modern Introduction (2. udgave), Brooks/Cole, ISBN 0-534-99845-3
• Anton, Howard (2005), Elementary Linear Algebra (Applications Version) (9. udgave), Wiley International
• Leon, Steven J. (2006), Linear Algebra With Applications (7. udgave), Pearson Prentice Hall
• Strang, Gilbert (2005), Lineær algebra og dens anvendelser

eksterne links

• Medier relateret til System of linear equations på Wikimedia Commons