/ Forside / Karriere / Uddannelse / Højere uddannelser / Nyhedsindlæg
Login
Glemt dit kodeord?
Brugernavn

Kodeord


Reklame
Top 10 brugere
Højere uddannelser
#NavnPoint
Nordsted1 1588
erling_l 1224
ans 1150
dova 895
gert_h 800
molokyle 661
berpox 610
creamygirl 610
3773 570
10  jomfruane 570
Minimum for kvadratisk form ??
Fra : Joe


Dato : 07-04-05 18:27

Hejsa

Jeg sidder og forsøger at løse følgende:

Jeg skal finde minimum for funktionen f(x) hvor

f(x)=xAx'

hvor x er en 1xN matrix med variablerne [x1,x2,...,xN]
og A er en symmetrisk, konstant NxN matrix

x' er x transponeret

Udtrykket er en kvadratisk form og jeg har ledt lidt i lærebøgerne, men kan
ikke rigtig finde ud af hvilke(n) metode(r) man bruger til at
løse sådan en krabat...

Det må være noget med at jeg skal differentiere f(x) med hensyn til hver
enkelt variabel i x....Så får jeg et ligningssystem med N ligninger hvor
hver ligning skal give 0.

Men differentiation af matrix-udtryk er ikke lige min stærke side.....

Et par hints og lidt hjælp ville være glimrende

Tak på forhånd...






 
 
Jens Axel Søgaard (07-04-2005)
Kommentar
Fra : Jens Axel Søgaard


Dato : 07-04-05 20:41

Joe wrote:

> Hejsa
>
> Jeg sidder og forsøger at løse følgende:
>
> Jeg skal finde minimum for funktionen f(x) hvor
>
> f(x)=xAx'
>
> hvor x er en 1xN matrix med variablerne [x1,x2,...,xN]
> og A er en symmetrisk, konstant NxN matrix
>
> x' er x transponeret
>
> Udtrykket er en kvadratisk form og jeg har ledt lidt i lærebøgerne, men kan
> ikke rigtig finde ud af hvilke(n) metode(r) man bruger til at
> løse sådan en krabat...

Har du Fraleigh og Beauregard? Kig på "7.1 Diagonalization of
Quadratic Forms" og "7.3 Applications to Extrema".

Fidusen er at en symmetrisk matrix A med reelle indgange
kan diagolineres af en matrix C så C^-1 A C = D, hvor D
er en diagonal-matrix D=[l_1, ..., l_n]' , hvor l_i'erne
er egenværdierne for matricen A. Benytter man substitutionen
x = Ct, får man:

x' A x = t' D t = l_1 t_1^2 + ... + l_n t_n^2

og det sidste polynomium er det noget nemmere at finde ekstrema
for end det oprindelige.

--
Jens Axel Søgaard


Joe (07-04-2005)
Kommentar
Fra : Joe


Dato : 07-04-05 21:00

Tak ska du ha




Carsten Svaneborg (07-04-2005)
Kommentar
Fra : Carsten Svaneborg


Dato : 07-04-05 20:43

Joe wrote:
> Jeg skal finde minimum for funktionen f(x) hvor
> f(x)=xAx' og A er en symmetrisk, konstant NxN matrix

Diagonaliser matricen A. xAx' er så lig yBy'
hvor B er en diagonal matrix, og du kan få y fra x ved
at anvende en koordinat transformation.

I dette koordinatsystem er f(y)=a1*y1²+a2*y2²+..

Spørgsmålet er så fortegn af egenværdierne a1,..,aN

Og når du har disse i y koordinatsystemet kan du
transformerer tilbage til x.

--
Mvh. Carsten Svaneborg
http://gauss.ffii.org

Joe (08-04-2005)
Kommentar
Fra : Joe


Dato : 08-04-05 14:17


>
> Og når du har disse i y koordinatsystemet kan du
> transformerer tilbage til x.
>


Men giver det ikke en triviel løsning i de fleste tilfælde....altså
nul-vektoren? Jeg har sikkert overset noget...

Hvis jeg differentierer f(y) mht til de N variable der indgår i y så får jeg
N ligninger som ser sådan her ud:

df/yi=2*a1*yi = 0

Den giver jo kun 0 for yi =0




Carsten Troelsgaard (08-04-2005)
Kommentar
Fra : Carsten Troelsgaard


Dato : 08-04-05 23:08


"Joe" <JoeNOSPAM@yahoo.com> skrev i en meddelelse
news:42556d6f$0$67264$157c6196@dreader2.cybercity.dk...
> Hejsa
>
> Jeg sidder og forsøger at løse følgende:
>
> Jeg skal finde minimum for funktionen f(x) hvor
>
> f(x)=xAx'
>
> hvor x er en 1xN matrix med variablerne [x1,x2,...,xN]
> og A er en symmetrisk, konstant NxN matrix
>
> x' er x transponeret
>
> Udtrykket er en kvadratisk form og jeg har ledt lidt i lærebøgerne, men
> kan ikke rigtig finde ud af hvilke(n) metode(r) man bruger til at
> løse sådan en krabat...
>
> Det må være noget med at jeg skal differentiere f(x) med hensyn til hver
> enkelt variabel i x....Så får jeg et ligningssystem med N ligninger hvor
> hver ligning skal give 0.
>
> Men differentiation af matrix-udtryk er ikke lige min stærke side.....
>
> Et par hints og lidt hjælp ville være glimrende

Jeg er tilpas ukendt med matrix og vektor-matematik, så mit svar kan være
lige vild som vejledende. Har du overvejet at kigge på grad div og curl?

http://www.robots.ox.ac.uk/~ian/Teaching/Vectors/lecturenotes5-6.pdf

Carsten



Joe (09-04-2005)
Kommentar
Fra : Joe


Dato : 09-04-05 12:48

hejsa...

jeg ræsonnerede mig frem til følgende...

at finde et minimum for den kvadratiske form er det samme som at skulle
finde den vektor x som står vinkelret på samtlige rækkevektorer (eller
søjlevektorer) i den symmetriske matrice A.

den trivielle løsning er selvfølgelig 0-vektoren...

I de tilfælde hvor A's søjle/rækkevektorer ikke udspænder hele det rum de
ligger i, så vil det være muligt at finde en basisvektor x som står
vinkelret på samtlige søjle/rækkevektorer i A....Denne vektor minimerer den
kvadratiske form!

Nogen kommentarer?







Joe (09-04-2005)
Kommentar
Fra : Joe


Dato : 09-04-05 13:02

Jeg glemte at sige, at det selvfølgelig ikke er sikkert at det er et
minimum,....

I de tilfælde hvor A's række/søjlevektorer ikke udspænder hele det rum de
ligger i, vil det være muligt at finde en basisvektor x som er vinkelret på
samtlige A's række/søjlevektorer. Antallet af løsninger svarer til
n-rank(A). Løsningen er enten et minimum eller maksimum for den kvadratiske
form.





Per Vognsen (09-04-2005)
Kommentar
Fra : Per Vognsen


Dato : 09-04-05 20:41

Joe wrote:
> hejsa...
>
> jeg ræsonnerede mig frem til følgende...
>
> at finde et minimum for den kvadratiske form er det samme som at
skulle
> finde den vektor x som står vinkelret på samtlige rækkevektorer
(eller
> søjlevektorer) i den symmetriske matrice A.

Nemlig. Hvis du f.eks. har den kvadratiske form

f(x,y) = ax^2 + by^2 + 2cxy

så er gradienten grad f(x,y,z) = (2ax + 2cy, 2by + 2cx). En eventuel
optimeringsvektor skal søges i løsningsmængden for grad f = 0. Vi
kan udtrykke indgangene i gradienten som prikprodukterne (2a,2c).(x,y)
og (2b,2c).(x,y). Som du korrekt bemærker så er (2a,2c) og (2b,2c)
søjlevektorerne i koefficientmatricen for f. Så optimeringsvektorerne
udgør ortogonalkomplementet af koefficientmatricens søjlerum!

> Nogen kommentarer?

Jeg kunne sige noget mere om kvadratiske formers geometri hvis du har
løst. Det er et dejligt konkret emne som kan bruge en masse lineær
algebra. Mange sætninger som nu anses for at tilhøre den lineære
algebra blev opdaget i sammenhæng med kvadratiske former. Et berømt
eksempel er Sylvesters inertisætning ("Sylvester's Law of Inertia").
Det er en sætning som næsten aldrig behandles i indledende kurser men
det er en smuk sætning og fører til en meget simpel klassifiering af
kvadratiske former.


Søg
Reklame
Statistik
Spørgsmål : 177558
Tips : 31968
Nyheder : 719565
Indlæg : 6408929
Brugere : 218888

Månedens bedste
Årets bedste
Sidste års bedste