---

Jeg har et overbestemt ligningssystem som ikke har nogen løsning for f(..)=0
jeg skal minimere funktionen og bruger newtons metode til at itterere mig
frem til punktet hvor gradienten er O.
Det giver ikke nødvendigvis en absolut korrekt løsning, så jeg tænkte på
hvorfor man ikke simpelthend løser ligningerne for gradienten.

et eksempel f(x,y)=2x^2+y^2
gradienten er så [4x , 2y]^T
et ekstremum har gradient=O, så kan jeg ikke bare sige at jeg skal finde
løsningerne for
4x=0 og 2y=0, hvilket giver mig x=0 og y=0

I mit virkelige eksempel er der uendeligt mange løsninger på hver af
ligningerne i gradienten, men man bør vel kunne udsøge de løsninger som er
fælles for alle, eller som er nær et godt gæt på ekstremum. Tager jeg fejl?

f(x,y)=2xy+x
gradient = [2y+1 , 2x]^T
2y+1=0 og 2x=0 => y=-½ x=0

---

Hmm.. jeg er ikke sikker på at jeg forstår dig rigtigt

Man kan bruge Newtons metode til at finde et punkt (x,y) der opfylder
grad f(x,y)=0. hvis jeg forstår dig rigtigt, så er dit problem at der
findes mange punkter (x,y) der opfylder grad f(x,y)=0, selvom de ikke
er minima. Det betyder at Newtons metode ofte konvergerer mod et
sadelpunkt. (Er det korrekt?)

I din post foreslår du at du kan bruge noget matematik til at omskrive
ligningssystemet grad f(x,y) =0. I princippet kan det ikke skade at
omskrive ligningerne, men det løser ikke problemet.

Hvis jeg har forstået problemet rigtigt, så vil jeg foreslå dig at
bruge en metode der er konstrueret til at finde minima. Det simpleste
er at løse følgende differentialligning numerisk

dx(t)/dt = -df(x,y)/dx
dy(t)/dt = -df(x,y)/dy

Du kan bruge denne metode til at finde et punkt der ligger tæt på
minimummet. Derefter kan du bruge Newtons metode til at finpudse
resultatet.

Den ovenstående metode er ikke særligt hurtig. Du kan finde hurtigere
metoder ved at kigge i Numerical recipies:

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

Niels

---

>Man kan bruge Newtons metode til at finde et punkt (x,y) der opfylder
>grad f(x,y)=0. hvis jeg forstår dig rigtigt, så er dit problem at der
>findes mange punkter (x,y) der opfylder grad f(x,y)=0, selvom de ikke
>er minima. Det betyder at Newtons metode ofte konvergerer mod et
>sadelpunkt. (Er det korrekt?)


Nej, det er ikke det der er problemet. Det jeg tænker på er at newton vel
principielt skal køre uendeligt længe for at finde den eksakte løsning. Det
er hvis vi ser bort fra maskinunøjagtighed.
Jeg tænkte så om ikke man bare kunne regne på gradienten og finde den
eksakte løsning på den måde. For hver ligningen i gradienten (to hvis to
variabler) kan der være flere løsninger og man finder så de fælles, og evt
også kun de der er nær et oprindeligt godt gæt på gradient=O.

---

Scripsit "J Kissinger" <kiss@mail.dk>

> Nej, det er ikke det der er problemet. Det jeg tænker på er at newton vel
> principielt skal køre uendeligt længe for at finde den eksakte løsning.

Sådan er det med numeriske metoder - man får aldrig eksakte løsninger.

> Jeg tænkte så om ikke man bare kunne regne på gradienten og finde den
> eksakte løsning på den måde.

Hvis du _kan_ finde nulpunkter for gradienten eksakt, behøver du
naturligvis ikke iterere dig frem til dem. De numeriske
løsningsmetoder bruger man når udtrykket er så kompliceret at man ikke
bare kan løse det.

--
Henning Makholm "Check the sprog."

---

"J Kissinger" <kiss@mail.dk> writes:

Flytter lige lidt rundt på dit:

> Jeg har et overbestemt ligningssystem som ikke har nogen løsning for f(..)=0

> et eksempel f(x,y)=2x^2+y^2

En ligning og to ubekendte er underbestemt.

> jeg skal minimere funktionen og bruger newtons metode til at itterere mig
> frem til punktet hvor gradienten er O.

Er opgaven at finde minimum?

> Det giver ikke nødvendigvis en absolut korrekt løsning,

Af hvad?

> gradienten er så [4x , 2y]^T
> et ekstremum har gradient=O, så kan jeg ikke bare sige at jeg skal finde
> løsningerne for
> 4x=0 og 2y=0, hvilket giver mig x=0 og y=0

Du kan ikke slutte at hvis f(x,y) er minimal for (x0,y0), så er
(x0,y0) også en af løsningerne til problemet f(x,y)=0

Men jeg misforstår dig måske?

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

---

> En ligning og to ubekendte er underbestemt.

Det er korrekt, og det var en dum formulering.
Skulle være.. jeg har en overbestemt ligning, og den giver anledning til
nogle overvejelser. et eksempel...

>> Det giver ikke nødvendigvis en absolut korrekt løsning,
> Af hvad?

Ja, du fanger alle de ringe formuleringer. Det jeg ville sige er at der ikke
nødvendigvis findes noget nulpunkt.


> Du kan ikke slutte at hvis f(x,y) er minimal for (x0,y0), så er
> (x0,y0) også en af løsningerne til problemet f(x,y)=0

Nej, det er det jeg mener med at der ikke er nogen løsning/nulpunkter.
Det jeg kan slutte er dog at hvis f(x0,y0) er minimal, så er f'(x0,y0)=O,
hvis altså der ingen grænser er for parametrene x og y.

> Men jeg misforstår dig måske?

Ja, men det kan du dårligt bebrejdes

---

"J Kissinger" <kiss@mail.dk> writes:

> Det jeg kan slutte er dog at hvis f(x0,y0) er minimal, så er f'(x0,y0)=O,
> hvis altså der ingen grænser er for parametrene x og y.

Ja, det tror jeg ikke nogen kan være uenige med dig i. Var det det der
var spørgsmålet/oplysningen i dit første indlæg?

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

---

> Ja, det tror jeg ikke nogen kan være uenige med dig i. Var det det der
> var spørgsmålet/oplysningen i dit første indlæg?

Spørgsmålet var dog ikke _så_ uklart. Andre kunne trods alt forstå det.
Det gik på om man ikke istedetfor at itterere mod et minimum kunne lave en
direkte og absolut løsning for gradient=O.
Det har Henning svaret fint på, så der er egentlig ikke flere spørgsmål lige
nu.
Jeg kan kun beklage at jeg fik formuleret mig lidt uklart.