---

Nogen her der er skrappe til matematik?

Jeg har brug for at løse otte ligninger med otte ubekendte.

Givet fire u,v koordinater (u0,v0 etc.) og fire x,y koordinator kan man
opstille følgende otte ligninger:

u0 = (Ax0 + By0 + C) / (Gx0 + Hy0 + 1)
v0 = (Dx0 + Ey0 + F) / (Gx0 + Hy0 + 1)

u1 = (Ax1 + By1 + C) / (Gx1 + Hy1 + 1)
v1 = (Dx1 + Ey1 + F) / (Gx1 + Hy1 + 1)

u2 = (Ax2 + By2 + C) / (Gx2 + Hy2 + 1)
v2 = (Dx2 + Ey2 + F) / (Gx2 + Hy2 + 1)

u3 = (Ax3 + By3 + C) / (Gx3 + Hy3 + 1)
v3 = (Dx3 + Ey3 + F) / (Gx3 + Hy3 + 1)

Opgaven går ud på, når vi kender fire par af hhvs. x,y og u,v at finde
værdierne af A, B, C, D, E, F, G og H.

For de nysgerrige kan jeg oplyse at det drejer sig om en
perspektivistisk transformation, hvor man kender de fire oprindelige
punkter og de fire nye punkter.

Det skulle vistnok kunne løses v.h.a. Cramer. Nogen der har et bud?

--
M.v.h.
Olav

---

Olav M.J. Christiansen <omjc@intete-kontor.dk> wrote:

> Jeg har brug for at løse otte ligninger med otte ubekendte.

Burde kunne løses i Excel. Matematisk programmering.
--
Per Erik Rønne

---

"Per Rønne" <per@ronne.invalid> skrev i en meddelelse
news:1fsuos0.oqonnb5u3qznN%per@ronne.invalid...
[klip]
> Burde kunne løses i Excel. Matematisk programmering.
[klip]

Hmmm... er det noget du excellerer i? Nå, spøg til side. Jeg har faktisk
brug for en generel løsning, da det skal indgå i et program.

--
M.v.h.
Olav

---

Olav M.J. Christiansen <omjc@intete-kontor.dk> wrote:

> "Per Rønne" <per@ronne.invalid> skrev i en meddelelse
> news:1fsuos0.oqonnb5u3qznN%per@ronne.invalid...
> [klip]
> > Burde kunne løses i Excel. Matematisk programmering.
> [klip]
>
> Hmmm... er det noget du excellerer i? Nå, spøg til side. Jeg har faktisk
> brug for en generel løsning, da det skal indgå i et program.

Så har du jo fået stikordet af mig. »Matematisk programmering«. Havde
der været tale om 8 lineært uafhængige lineære ligninger havde det været
»Lineær Programmering«, og løsningen havde været simplexalgoritmen.

Nu drejer det sig om det generelle »matematisk programmering. Søg i
google, eventuelt senere på et forskingsbibliotek.

--
Per Erik Rønne

---

Olav M.J. Christiansen skrev:

> Nå, spøg til side. Jeg har faktisk brug for en generel løsning,
> da det skal indgå i et program.

Sidst jeg havde matematik, løste man den slags ligninger v.hj.af
determinanter/vektorer, og det var vældig meget lettere end at
isolere en af variablene ad gangen - og samtidig får man netop en
generel løsning af ligningssystemet.

Desværre er det så lang tid siden, at jeg ikke engang kan huske
formen for et ligningssystem med to ligninger og to ubekendte,
men mon ikke andre her kan være behjælpelige?


// Klaus

--
><>    unselfish actions pay back better

---

"Klaus Alexander Seistrup" <spam@magnetic-ink.dk> skrev i en meddelelse
news:10381a33-78c0-4361-8a1a-9d656d6c239e@news.szn.dk...
[snip]
> Sidst jeg havde matematik, løste man den
> slags ligninger v.hj.af determinanter/vektorer
[snip]

Jeg tror næsten du tænker på Cramers sætning. Den siger at løsningen til

ax + by = e
cx + dy = f

er givet ved

x = (ed - fb) / (ad - cb)
y = (af - ce) / (ad - cb)

(det kan også skrives med matricer)

--
M.v.h.
Olav

---

Olav M.J. Christiansen skrev:

>> Sidst jeg havde matematik, løste man den
>> slags ligninger v.hj.af determinanter/vektorer
>
> Jeg tror næsten du tænker på Cramers sætning. Den siger at
> løsningen til
>
> ax + by = e
> cx + dy = f
>
> er givet ved
>
> x = (ed - fb) / (ad - cb)
> y = (af - ce) / (ad - cb)
>
> (det kan også skrives med matricer)

Jep, det er lige præcis dén metode - jeg vidste bare ikke at det
hed Cramers sætning.


// Klaus

--
><>    unselfish actions pay back better

---

Scripsit "Olav M.J. Christiansen" <omjc@intete-kontor.dk>

> Givet fire u,v koordinater (u0,v0 etc.) og fire x,y koordinator kan man
> opstille følgende otte ligninger:

> u0 = (Ax0 + By0 + C) / (Gx0 + Hy0 + 1)
> v0 = (Dx0 + Ey0 + F) / (Gx0 + Hy0 + 1)

Gang nævnerne over på den anden side af ligningen. Så har du et
lineært ligningssystem med A, B, ..., H som ubekendte. Det kan så
løses med standardmetoder. Gauss-eliminering er, hvis den er
fornuftigt skrevet (så den vælger den numeriske største koefficient at
eliminere med i stedet for bare den første den bedste som er
forskellig fra 0), nok mere håndterbar end Cramers regel.
8×8-determinanter er ikke rare.

Se bort fra Per Rønnes anbefaling af lineær programmering. Han har
misforstået enten problemet eller den løsning han foreslår. (Lineær
programmering handler om at finde et ekstremum for en lineær funktion
defineret på et hyper-polyeder i R^n).

--
Henning Makholm "... a specialist in the breakaway
oxidation phenomena of certain nuclear reactors."

---

"Henning Makholm" <henning@makholm.net> skrev i en meddelelse
news:yahr88jpkqe.fsf@pc-043.diku.dk...

> Gang nævnerne over på den anden side af ligningen.

Tak. Det vil jeg forsøge.

> 8×8-determinanter er ikke rare.

Nej, men jeg har på et tidligere tidspunkt løst noget der mindede om
dette v.h.a. Cramer. Dengang var det dog 'kun' seks ligninger med seks
ubekendte, men jeg fik ligningerne reduceret tilstrækkelig til at de
kunne løses v.h.a. Cramer (bl.a. kunne de opfattes som tre ligninger med
tre ubekendte).

> Se bort fra Per Rønnes anbefaling af lineær
> programmering. Han har misforstået enten
> problemet eller den løsning han foreslår. (Lineær
> programmering handler om at finde et ekstremum
> for en lineær funktion defineret på et
> hyper-polyeder i R^n).

Det var også ca. hvad der stod i min matematiske opslagsbog, så jeg
forstod heller ikke hvad han mente.

--
M.v.h.
Olav

---

Henning Makholm <henning@makholm.net> wrote:

> Se bort fra Per Rønnes anbefaling af lineær programmering. Han har
> misforstået enten problemet eller den løsning han foreslår. (Lineær
> programmering handler om at finde et ekstremum for en lineær funktion
> defineret på et hyper-polyeder i R^n).

Jeg har misforstået problemet. Læste ikke indlægget godt nok igennem.

Jeg har kendt til LP siden folkeskolen, og har på 2. del af datalogi
lavet et undervisningsprogram i simplex-algoritmen.
--
Per Erik Rønne

---

"Olav M.J. Christiansen" <omjc@intete-kontor.dk> wrote:

> Jeg har brug for at løse otte ligninger med otte ubekendte.
>
> Opgaven går ud på, når vi kender fire par af hhvs. x,y og u,v at finde
> værdierne af A, B, C, D, E, F, G og H.
>
> For de nysgerrige kan jeg oplyse at det drejer sig om en
> perspektivistisk transformation, hvor man kender de fire oprindelige
> punkter og de fire nye punkter.

Et bud kunne være Newton-Raphson's metode, som jeg selv har erfaring med i
forbindelse med kamerakalibrering. Her var der dog tale om N kendte
korrespondancer mellem 3-D rumkoordinater og 2-D billedkoordinater, mens der
kun var 6 ukendte parametre (3 rotationsparametre og 3
translationsparametre), men princippet burde være det samme. Den
væsentligste ulempe ved metoden er nok, at den kræver et kvalificeret
start-gæt på løsningen.

Mvh,
Kristian

---

"Olav M.J. Christiansen" <omjc@intete-kontor.dk> skrev i en meddelelse
news:3e8c5027$0$32027$edfadb0f@dread12.news.tele.dk...
[snip]
> Jeg har brug for at løse otte ligninger
> med otte ubekendte.
[snip]

Hmmm.... jeg tror jeg har en rettelse til ligningerne.

Teorien bag har jeg bl.a. fundet på denne side:
http://tinyurl.com/8sz5

Der står der at:

"For a projective transformation: [up vp wp] = [x y w] T, where

u = up / wp
v = vp / wp.

T is a 3-by-3 matrix, where all nine elements can be different.

T = [ A D G
B E H
C F I]

The above matrix equation is equivalent to these two expressions:

u = (Ax + By + C) / (Gx + Hy + 1)
v = (Dx + Ey + F) / (Gx + Hy + 1)"

Er det ikke forkert? Det sidste 1-tal skulle vel have været et I?

--
M.v.h.
Olav

---

"Olav M.J. Christiansen" <omjc@intete-kontor.dk> skrev i en meddelelse
news:3e8d49e7$0$32017$edfadb0f@dread12.news.tele.dk...
[snip]
> Er det ikke forkert? Det sidste
>1-tal skulle vel have været et I?
[snip]

Jeg kan iøvrigt (hvis ovenstående er korrekt) ved et simpelt kunstgreb
reducere problemet yderligere.

Ved at antage at x0,y0 og u0,v0 er nul (kræver kun en simpel flytning
før og efter transformationen), så kan jeg reducere problemet til
følgende:

u1 = (Ax1 + By1) / (Gx1 + Hy1 + I)
v1 = (Dx1 + Ey1) / (Gx1 + Hy1 + I)

u2 = (Ax2 + By2) / (Gx2 + Hy2 + I)
v2 = (Dx2 + Ey2) / (Gx2 + Hy2 + I)

u3 = (Ax3 + By3) / (Gx3 + Hy3 + I)
v3 = (Dx3 + Ey3) / (Gx3 + Hy3 + I)

(idet C og F begge bliver 0)

Nu har jeg seks ligninger med syv ubekendte. Kan det løses?

--
M.v.h.
Olav

---

"Olav M.J. Christiansen" <omjc@intete-kontor.dk> skrev i en meddelelse
news:3e8c5027$0$32027$edfadb0f@dread12.news.tele.dk...
[snip]
> Jeg har brug for at løse otte ligninger
> med otte ubekendte.
[snip]

Til information: Jeg fik nogle gode svar på mine spørgsmål i
comp.graphics.algorithms (som jeg iøvrigt tidligere har brugt).

Hvis andre har tilsvarende problemer er det en god ng at kigge i.

--
M.v.h.
Olav

---

Jeg har ingen højere matematisk uddannelse, men jeg kender en del til Excel,
så hvis det drejer sig om en numerisk løsning, så mener jeg at have et
forslag. Sig til hvis du er interesseret i en xls fil der viser en løsning
af et lineært ligningssystem med otte ligninger og otte ubekendte.

Hans Knudsen


"Olav M.J. Christiansen" <omjc@intete-kontor.dk> skrev i en meddelelse
news:3e8ea074$0$31996$edfadb0f@dread12.news.tele.dk...
> "Olav M.J. Christiansen" <omjc@intete-kontor.dk> skrev i en meddelelse
> news:3e8c5027$0$32027$edfadb0f@dread12.news.tele.dk...
> [snip]
> > Jeg har brug for at løse otte ligninger
> > med otte ubekendte.
> [snip]
>
> Til information: Jeg fik nogle gode svar på mine spørgsmål i
> comp.graphics.algorithms (som jeg iøvrigt tidligere har brugt).
>
> Hvis andre har tilsvarende problemer er det en god ng at kigge i.
>
> --
> M.v.h.
> Olav
>
>

---

"Hans Knudsen" <hans.knudsen__REMOVE__@mail.tele.dk> skrev i en
meddelelse news:3e8ea697$0$10381$edfadb0f@dread11.news.tele.dk...
[snip]
> Sig til hvis du er interesseret i en xls fil der
> viser en løsning af et lineært ligningssystem
> med otte ligninger og otte ubekendte.
[snip]

Tak for tilbudet, men jeg skal bruge en generel algoritme der kan
implementeres i et programmeringssprog (f.eks. Pascal eller C). Som sagt
har jeg allerede fået en del input andetsteds fra, så jeg tror jeg har
hvad jeg skal bruge nu.

--
M.v.h.
Olav