---

Hvis jeg har tre ligninger for tre variable og jeg vil minimere dem, så kan
man definere en 3x3 jacobi matrix og bruge den til minimering. Man kunne
også bare skrive en funktion som summen af "fejlen" i de tre ligninger
(eller summen af fejlen i anden potens) og beregne gradienten for den ene
funktion og bruge den til at minimere med.

Hvad er egentlig forskellen på de to indgangsvinkler?

---

Lad os kigge på en ligning i en dimension:

f(x)=0.

De forskellige numeriske metoder vil opføre sig forskelligt tæt på
en vendetangent, f'(x)=0, der opfylder

f''(x)f(x) + (f'(x))^2 > 0

I metode 2 definerer du en fejl på følgende form

fejl(x) = (f(x))^2

De lokale minima for denne funktion opfylder

f''(x)f(x) + (f'(x))^2 > 0
f(x)f'(x) = 0

Med andre ord kan fejl(x) have et lokal minimum der opfylder

f''(x)f(x) + (f'(x))^2 > 0
f'(x)=0
f(x) != 0 (!= betyder ikke lig med)

Derfor kan metode 2 konvergere mod et punkt der ikke opfylder f(x) = 0.


Hvis du derimod anvender Newton Raphson (metode 1), så kan du løbe
ind i andre problemer. Skridtlængden i Newton Raphson er givet ved

x(n+1) - x(n) = f(x(n))/f'(x(n))

Hvis du indsætter vendetangentligningen f'(x)=0, er det let at se at
en vendetangent kan resultere i et meget langt Newton Raphson-skridt.
Så vidt jeg ved findes der smarte metoder til and undgå for lange
Newton Raphson-skridt, men jeg ved ikke meget om dem.

En tredje mulighed er alt løse følgende differentialligning

dx(t)/dt = f(x(t)) /f'(x(t))

Så vidt jeg husker vil denne differentialligning vil også konvergere
mod min vendetangent.

Alle tre metoder kan generaliseres til funktioner af mange variable.
Så vidt jeg ved er Newton Raphson normal hurtigst (især hvis man
bruger et trick til at tilnærme Jacobimatricen). Der står mere om det
hele i kapitel 9 i numerical recipies.

http://www.library.cornell.edu/nr/cbookcpdf.html

---

Jeg forstår ikke helt hvad du argumenterer for. Du siger at metode 2. kan
konvergere mod et punkt hvor f(x)!=0 og jeg læser din formulering som at du
mener det er skidt. Det er jo bare ikke sikkert at der findes noget punkt
for f(x)=0, så det er da en nødvendighed at den kan udsøge disse punkter.

>Hvis du derimod anvender Newton Raphson (metode 1), så kan du løbe
>ind i andre problemer. Skridtlængden i Newton Raphson er givet ved

Hvis man definerer en funktion som summen af kvadratet af fejlene og triller
ned mod gradienten, så vil de fleste itterative metoder vel have samme
problem...?

>Alle tre metoder kan generaliseres til funktioner af mange variable.
>Så vidt jeg ved er Newton Raphson normal hurtigst (især hvis man
>bruger et trick til at tilnærme Jacobimatricen).

Hvorfor vil du tilnærme Jacobimatricen? Den er vel konstant for hele
forløbet.

>Der står mere om det
>hele i kapitel 9 i numerical recipies.
>http://www.library.cornell.edu/nr/cbookcpdf.html

Jeg tager et kig.

Egentlig ville jeg bare prøve at forstå forskellen på at bruge Jacobi hvor
de tre ligninger (fejlene) hver har en gradient og på at bruge en enkelt
ligning hvor man har en samlet gradient. Jeg kan stadig ikek rigtig se
forskellen.

hvis vi har et meget simpelt eksempel med tre ligninger og godt nok kun een
ubekendt.
e1 = (2-2x)^2
e2 = (3-3x)^2
e3 = (4-4x)^2

og en generel ligning e = e1^2+e2^2+e3^2

så har man en Jacobi for de tre ligninger på
[8x-8 , 18x-18 , 32x-32]^T

og en enkelt gradient (simpel hældning her) for e på 58x-58

Begge kan bruges til at finde minimum som er x=1. Metoderne til at gøre det
er forskellige, men min pointe er (mener jeg da) at den Jacobimatrice reelt
bare er den generelle fejl delt ud i tre led. Hvad er forskellen egentlig og
hvorfor bruge den ene metode istedet for den anden.

---

Jakob Nielsen wrote:
> Egentlig ville jeg bare prøve at forstå forskellen på at bruge Jacobi hvor
> de tre ligninger (fejlene) hver har en gradient og på at bruge en enkelt
> ligning hvor man har en samlet gradient. Jeg kan stadig ikek rigtig se
> forskellen.

Hvordan det skulle virke at bruge Jacobi-matricen for de tre
ligninger/funktioner? Det giver jo én steepest-descent retning for hver
funktion, så hvilken retning skulle man vælge? Man kan ikke lægge en 3x3
matrix til en 3d vektor.

> hvis vi har et meget simpelt eksempel med tre ligninger og godt nok kun een
> ubekendt.
> e1 = (2-2x)^2
> e2 = (3-3x)^2
> e3 = (4-4x)^2

Det er ikke et godt eksempel. I det typiske tilfælde har man lige så
mange (ikke-ækvivalente) ligninger som ubekendte.

--
Jonas Møller Larsen

---

> Hvordan det skulle virke at bruge Jacobi-matricen for de tre
> ligninger/funktioner? Det giver jo én steepest-descent retning for hver
> funktion, så hvilken retning skulle man vælge? Man kan ikke lægge en 3x3
> matrix til en 3d vektor.

Jeg tror ikke helt jeg forstår hvad du mener med det. Newtons metode til
itterativ løsning af et system af ikke lineære ligninger bruger
Jacobimatricen til at nærme sig løsningen.

Ellers er jeg enig. Jacobimatricen er jo netop heldningen for hver ligning
og det er også roden til mit spørgsmål om hvad forskellen på at løse een
ligning og at løse hele systemet opdelt er.

> Det er ikke et godt eksempel. I det typiske tilfælde har man lige så mange
> (ikke-ækvivalente) ligninger som ubekendte.

Det er jeg klar over. Som jeg også skrev "hvis vi har et meget simpelt
eksempel med tre ligninger og godt nok kun een
ubekendt."

---

Jakob Nielsen wrote:
>>Hvordan det skulle virke at bruge Jacobi-matricen for de tre
>>ligninger/funktioner? Det giver jo én steepest-descent retning for hver
>>funktion, så hvilken retning skulle man vælge? Man kan ikke lægge en 3x3
>>matrix til en 3d vektor.
>
> Jeg tror ikke helt jeg forstår hvad du mener med det. Newtons metode til
> itterativ løsning af et system af ikke lineære ligninger bruger
> Jacobimatricen til at nærme sig løsningen.

Okay, jeg tror jeg forstår nu. Du har (i fx to dimensioner) ligningssystemet

f(x,y) = 0
g(x,y) = 0.

Dette kan man så forsøge at løse 1) med Newtons metode, eller 2) ved at
minimere f(x,y)² + g(x,y)². Hvad er forskellen mellem de to metoder?

Tja, det er forskellige metoder. Newtons metode konvergerer nok
hurtigere end steepest descent, som ikke udnytter informationen om, at
værdien af minimummet er nul. Til gengæld er det så nødvendigt at
invertere en matrix for hver iteration i Newtons metode.

--
Jonas Møller Larsen

---

> Okay, jeg tror jeg forstår nu. Du har (i fx to dimensioner)
> ligningssystemet
>
> f(x,y) = 0
> g(x,y) = 0.
>
> Dette kan man så forsøge at løse 1) med Newtons metode, eller 2) ved at
> minimere f(x,y)² + g(x,y)². Hvad er forskellen mellem de to metoder?

Præcis

> Tja, det er forskellige metoder. Newtons metode konvergerer nok hurtigere
> end steepest descent, som ikke udnytter informationen om, at værdien af
> minimummet er nul. Til gengæld er det så nødvendigt at invertere en matrix
> for hver iteration i Newtons metode.

Vi er bare ude i at det er forskellige metoder med hver deres svagheder? Der
er intet markant anderledes i dem?
I de systemer jeg leger med er det nu ikke givet at minimum er nul. Der er
måleunøjagtigheder som gør at man må stille sig til tåls med et minimum
selvom det ikke er 0. Det er en art ultralydsgps hvor fire lydgivere på
kendte positioner udsender pulser hvert andet sekund (alle fire samtidigt)
med forskellige frekvenser. Ved at opstille et ligningssystem med deres
positioner og forskydningen i modtagelsestidspunktet kan jeg beregne
positionen for modtageren. Der er bare unøjagtigheder som gør at der ikke
nødvendigvis findes en position med en fejl på nul.

---

Jakob Nielsen wrote:
> Vi er bare ude i at det er forskellige metoder med hver deres svagheder? Der
> er intet markant anderledes i dem?

Så længe ligningssystemet har netop én løsning, tror jeg ikke der er den
store forskel. Hvis systemet er underdetermineret (færre ligninger end
ubekendte, uendeligt mange løsninger), vil Newtons metode nok fejle pga.
en singulær Jacobi-matrix, mens minimere-fejlen-metoden vil konvergere
mod en af de mange løsninger. Hvis ligningssystemet har flere ligninger
end ubekendte (dvs er inkonsistent/overdetermineret), virker Newtons
metode ikke, men det giver det mening at forsøge at minimere fejlen.

> Det er en art ultralydsgps hvor fire lydgivere på
> kendte positioner udsender pulser hvert andet sekund (alle fire samtidigt)
> med forskellige frekvenser. Ved at opstille et ligningssystem med deres
> positioner og forskydningen i modtagelsestidspunktet kan jeg beregne
> positionen for modtageren. Der er bare unøjagtigheder som gør at der ikke
> nødvendigvis findes en position med en fejl på nul.

Det lyder umiddelbart som om, du har tre ligninger med tre ubekendte
(positionen). Og at det altid er muligt at finde mindst én eksakt
løsning? I hvert flad ville jeg kun bruge Newtons algoritme, hvis der er
præcist en løsning.

--
Jonas Møller Larsen

---

Jonas Møller Larsen wrote:
> Det lyder umiddelbart som om, du har tre ligninger med tre ubekendte
> (positionen). Og at det altid er muligt at finde mindst én eksakt
> løsning?

Medmindre modtageren ikke er synkroniseret med senderen, idet der i
dette tilfælde er en ekstra ubekendt, nemlig modtagerens tid.

Med venlig hilsen Preben

---

Preben Bohn wrote:
> Jonas Møller Larsen wrote:
>> Det lyder umiddelbart som om, du har tre ligninger med tre ubekendte
>> (positionen). Og at det altid er muligt at finde mindst én eksakt
>> løsning?
>
> Medmindre modtageren ikke er synkroniseret med senderen, idet der i
> dette tilfælde er en ekstra ubekendt, nemlig modtagerens tid.

Men der er også en ekstra lydsender (fire i alt), som jeg går ud fra
bruges til at eliminere den fjerde ubekendte fra regnskabet (som i GPS),
sådan at man står tilbage med tre ligninger med tre ubekendte.

--
Jonas Møller Larsen

---

> Men der er også en ekstra lydsender (fire i alt), som jeg går ud fra
> bruges til at eliminere den fjerde ubekendte fra regnskabet (som i GPS),
> sådan at man står tilbage med tre ligninger med tre ubekendte.

Princippet er at lydgiverne er synkroniserede, men modtageren er på sin egen
tid og reelt bare har et stopur.
Jeg behøvede som sådan ikke fire lydgivere da jeg kun bestemmer positionen i
planet, men grndlæggende set sker der det at modtageren starter stopuret når
den hører et signal. Den ved, når den har modtaget alle fire signaler, hvor
meget afstanden mellem lydgiverene varierer og kan beskrive afstanden til de
tre udtrykt ved den første plus et offset.
Da der kommer signal hvert andet sekund, så kan man leve med en forsinkelse
på op mod et sekund og det er jo ca 320 m hvilket er meget mere end
nødvendigt.
Dette er hvis modtageren bliver tændt midt i det hele og måske starter midt
i en impulsperiode.

Jeg vil fortsætte med Newton og Jacobi så. Takker for svarene.

---

Jakob Nielsen wrote:
> Jeg behøvede som sådan ikke fire lydgivere da jeg kun bestemmer positionen i
> planet, men grndlæggende set sker der det at modtageren starter stopuret når
> den hører et signal. Den ved, når den har modtaget alle fire signaler, hvor
> meget afstanden mellem lydgiverene varierer og kan beskrive afstanden til de
> tre udtrykt ved den første plus et offset.

Det lyder meget som om, problemet i virkeligheden er overdetermineret,
og at du har tre ligninger med to ubekendte. Hvis ikke, hvad er da den
tredje ubekendte? (Newtons metode kræver som sagt, at der er lige så
mange ligninger som ubekendte.)

--
Jonas Møller Larsen

---

> Det lyder meget som om, problemet i virkeligheden er overdetermineret, og
> at du har tre ligninger med to ubekendte. Hvis ikke, hvad er da den tredje
> ubekendte? (Newtons metode kræver som sagt, at der er lige så mange
> ligninger som ubekendte.)

Det er ganske rigtigt for mange ligninger til de to ubekendte, men som med
det gængse gps-system, så er der unøjagtigheder og man kan ikke regne med at
få DEN rigtige løsning. Ved at have flere målinger kan man finde den løsning
som for alle målinger passer bedst. Hvis eksempelvis et af fire signaler er
meget ukorrekt (temperatur, vind, støj, blokerende objekter) så vil de tre
resterende stadig pege på den korrekte position.

---

"Jakob Nielsen" <jni@mail.no> writes:

> > Dette kan man så forsøge at løse 1) med Newtons metode, eller 2) ved at
> > minimere f(x,y)² + g(x,y)². Hvad er forskellen mellem de to metoder?
>
> Præcis
>
> > Tja, det er forskellige metoder.

Det ene (Newton) er vel en numerisk metode, mens den anden ikke
definere en metode til minimeringen, kun hvad problemet der skal
løses er?

Der findes mange optimeringsmetoder, så hvilken skal der sammenlignes
med?

På den anden side kan Newton fx. ved indførelse af Lagrange
multipliers benyttes til optimering.

--
Brian (remove the sport for mail)
http://www.et.web.mek.dtu.dk/Staff/be/be.html

---

Brian Elmegaard wrote:
>>>Tja, det er forskellige metoder.
>
> Det ene (Newton) er vel en numerisk metode, mens den anden ikke
> definere en metode til minimeringen, kun hvad problemet der skal
> løses er?

Ja, enig. Jeg nævnte steepest descent (altså, tag et skridt i retningen
modsat gradienten) som en metode til minimering, men det er heller ikke
én bestemt metode, før man specificerer, hvilken skridtlængde der
bruges. Tilsvarende kunne man sige, at Newtons metode ikke er én bestemt
metode, før man specificerer, hvordan 1/f'(x) = J(x)^-1 beregnes,
hvilket er ikke-trivielt i højere end én dimension.

--
Jonas Møller Larsen