|
| 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.
| |
|
|