MATHHX A
3.9 Beviser til kvadratisk programmering
-
Bevis
Påstanden bevises nemt vha. Pythagoras. Lad \(P\) være et punkt på cirklen:
Vi bruger Pythagoras på den røde trekanten på tegningen og får det ønskede resultat:
\[(x-x_0)^2+(y-y_0)^2=r^2\]
Men nu tænker du nok: ”Benjamin: Hvad nu hvis punktet ligger et andet sted på cirklen?”. Vi kunne f.eks. have:
Hvilket giver
\[(x_0-x)^2+(y-y_0)^2=r^2\]
Vi kan se at der er byttet om på \(x\) og \(x_0\) i forhold til den ligning vi gerne ville frem til. Men det er ligemeget om der står \(x-x_0\) eller \(x_0-x\) i parentesen i cirklens ligning. Det giver det samme, fordi det bliver sat i anden. Vi har hermed bevist at cirklens ligning er bestemt ved:
\[(x-x_0)^2+(y-y_0)^2=r^2\]
-
Sætning 3.8.3
Lad \(f(x,y)=ax^2+bx+cy^2+dy+e\).
Hvis \(a\neq 0\), \(d\neq 0\) og \(c=0\), så er niveaukurven \(N(t)\) en parabel for alle værdier af \(t\). Ændres \(t\) vil parablen parallelforskydes i lodret regning. Der gælder:-
• Hvis \(d\) er positiv vil en højere værdi for \(t\) forskyde parablen op.
-
• Hvis \(d\) er negativ vil en højere værdi for \(t\) forskyde parablen ned.
-
• Hvis \(a\) og \(d\) har samme fortegn er der tale om en konkav parabel, ellers er den konveks.
-
-
Bevis
Niveaukurven \(N(t)\) er givet ved.\[f(x,y)=t.\]
Vi indsætter forskriften.
\[ax^2+bx+cy^2+dy+e=t.\]
Da \(c=0\) går \(cy^2\)-ledet ud:
\[ax^2+bx+dy+e=t.\]
Vi vil gerne vise at vi kan skrive det på form som en parabel. Så vi isolerer \(y\). Vi trækker \(ax^2\), \(bx\) og \(e\) fra på begge sider.
\[dy=t-ax^2-bx-e,\]
og dividerer med \(d\):
\[y=\frac {t-ax^2-bx-e}{d}.\]
Vi deler brøken op og omarrangerer leddene
\[y=\frac {-ax^2}{d}+\frac {-bx}{d}+\frac {t-e}{d},\]
hvorefter vi sætter \(x^2\) og \(x\) ned bagved brøkerne.
\[y=\frac {-a}{d}x^2+\frac {-b}{d}x+\frac {t-e}{d}\]
Vi kan se at udtrykket nu har form som en parabel, så \(N(t)\) er altså en parabel. Vi kan se at det eneste led som indeholder \(t\) er konstantleddet \(\frac {t-e}{d}\). Dvs. en ændring i \(t\) vil betyde end lodret parallelforskydning af parablen. Hvis \(d\) er positiv vil konstantleddet vokse når \(t\) vælges større, hvilket igen betyder at parablen forskydes op. Hvis \(d\) er negativ vil konstantleddet aftage da nævnerne i brøken bliver negativ, så når brøkens tæller vokser, så vil hele brøken blive mindre. Altså vil en negativ \(d\)-værdi betyde at parablen forskydes ned når \(t\) vælges større.
Vi kan se at koefficienten til \(x^2\) er \(\frac {-a}{d}\). Hvis \(a\) og \(d\) har samme fortegn vil brøken være negativ og parablen dermed konkav. Hvis \(a\) og \(d\) har forskelligt fortegn vil brøken være positiv og parablen vil dermed være konveks.
Vi vil nu bevise en sætning som ikke er så interessant i sig selv, men som skal bruges i de efterfølgende beviser. Derfor er den kaldt en ”hjælpesætning”.
-
\[f(x,y)=ax^2+bx+cy^2+dy+e.\]
Vi faktoriserer:
\[f(x,y)=a\left (x^2+\frac {b}{a}x\right )+c\left (y^2+\frac {d}{c}y\right )+e,\]
og vi vil nu kvadratkompletterer det der står i parenteserne. Da halvdelen af \(\frac {b}{a}\) er \(\frac {b}{2a}\) får vi:
\[f(x,y)=a\left (\left (x+\frac {b}{2a}\right )^2-\left (\frac {b}{2a}\right )^2\right )+c\left (\left (y+\frac {d}{2c}\right )^2-\left (\frac {d}{2c}\right )^2\right )+e.\]
Vi reducerer
\[f(x,y)=a\left (\left (x+\frac {b}{2a}\right )^2-\frac {b^2}{4a^2}\right ) + c\left (\left (y+\frac {d}{2c}\right )^2-\frac {d^2}{4c^2}\right )+e,\]
ganger parenteserne ud
\[f(x,y)=a\left (x+\frac {b}{2a}\right )^2-a\frac {b^2}{4a^2} + c\left (y+\frac {d}{2c}\right )^2-c\frac {d^2}{4c^2}+e,\]
reducerer igen
\[f(x,y)=a\left (x+\frac {b}{2a}\right )^2-\frac {b^2}{4a} + c\left (y+\frac {d}{2c}\right )^2-\frac {d^2}{4c}+e,\]
og bytter nu om på rækkefølgen:
\[f(x,y)=a\left (x+\frac {b}{2a}\right )^2 + c\left (y+\frac {d}{2c}\right )^2+e-\frac {b^2}{4a}-\frac {d^2}{4c}.\]
Vi ser at \(f\) har formen:
\[f(x,y)=a(x-x_0)^2 + c(y-y_0)^2+m,\]
hvor
\[\text {$x_0=-\frac {b}{2a}$,\quad $y_0=-\frac {d}{2c}$\quad og\quad $m=e-\frac {b^2}{4a}-\frac {d^2}{4c}$}.\]
-
Sætning 3.8.1
Lad \(f(x,y)=ax^2+bx+cy^2+dy+e\), og antag at \(a\) og \(c\) har samme fortegn (som ikke er nul selvfølgelig). Da har \(f\) frit ekstremum i punktet\[C=\left (-\frac {b}{2a},-\frac {d}{2c}\right )\]
med ekstremumsværdi
\[m=e-\frac {b^2}{4a}-\frac {d^2}{4c}.\]
Hvis \(a\) og \(c\) er positive er det frie ekstremum et minimum ellers er det et maksimum.
-
Bevis
Først omskrives \(f(x,y)\) ifølge sætning 3.9.1. Vi har altså:\[f(x,y)=a(x-x_0)^2 + c(y-y_0)^2+m,\]
hvor
\[\text {$x_0=-\frac {b}{2a}$,\quad $y_0=-\frac {d}{2c}$\quad og\quad $m=e-\frac {b^2}{4a}-\frac {d^2}{4c}$}.\]
Antag først at \(a>0\) og \(c>0\).
Vi vi nu undersøge, hvad der sker når vi variere \(x\) og \(y\). Hvad sker der med funktionsværdien? Vi bemærker at \(m\) er en konstant og derfor forbliver det samme, når \(x\) og \(y\) ændrer sig. Så det er kun de to første led, der varierer, når vi ændre \(x\) og \(y\). Vi ved at \((x-x_0)^2\) og \((y-y_0)^2\) ikke kan blive mindre end nul, da de har form som noget i anden. Vi har altså:\[f(x,y)=\underbrace {a}_{+}\cdot \underbrace {(x-x_0)^2}_{+\text { eller } 0} + \underbrace {c}_{+}\cdot \underbrace {(y-y_0)^2}_{+\text { eller } 0}+\underbrace {m}_{?},\]
hvilket må betyde at:
\[f(x,y)=\underbrace {a(x-x_0)^2}_{+\text { eller } 0} + \underbrace {c(y-y_0)^2}_{+\text { eller } 0}+\underbrace {m}_{?}.\]
Vi kan se at de to første led altid er positive eller nul, så vi får den mindste funktionsværdi når de begge to er nul (\(m\) er en konstant, så den vil være det samme uanset hvad \(x\) og \(y\) er). De to første led er nul når \(x=x_0\) og \(y=y_0\). Den tilhørende funktionsværdi bliver:
\[f(x_0,y_0)=a(x_0-x_0)^2 + c(y_0-y_0)^2+m=0+0+m=m \]
Altså har funktionen minimum i \((x_0,y_0)\) og vi ser samtidigt, at minimumsværdien er \(m\).
Antag nu at \(a<0\) og \(c<0\). Se næste øvelse.
Øvelse 3.9.1
-
a) Gør ovenstående bevis færdigt. Det fungerer tilsvarende som når \(a>0\) og \(c>0\).
Løsning 3.9.1
-
a) Vis mig det.
-
Sætning 3.8.2
Lad \(f(x,y)=ax^2+bx+cy^2+dy+e\) og antag at \(f\) har frit ekstremum \(m\).Hvis \(a>0\), \(c>0\) og \(t>m\) så er er niveaukurven \(N(t)\) en ellipse. Vælges en højere værdi for \(t\) fås en større ellipse. Alle niveaukurverne har samme centrum.
Hvis \(a<0\), \(c<0\) og \(t<m\) så er er niveaukurven \(N(t)\) en ellipse. Vælges en højere værdi for \(t\) fås en mindre ellipse. Alle niveaukurverne har samme centrum.
Hvis \(a=c\) i en af de to ovennævnte situationer, så er niveaukurverne tilmed cirkler.
-
Bevis
Antag først at \(a>0\), \(c>0\) og \(t>m\):Niveaukurven \(N(t)\) er givet ved.
\[f(x,y)=t.\]
Forskriften for \(f\) kan ifølge sætning 3.9.1 skrives som:
\[a(x-x_0)^2 + c(y-y_0)^2+m=t.\]
Vi trækker \(m\) fra på begge sider
\[a(x-x_0)^2 + c(y-y_0)^2=t-m.\]
Vi deler nu med \(t-m\). Det kan vi gøre fordi vi ved at \(t>m\) og dermed kan \(t-m\) ikke være nul.
\[\frac {a(x-x_0)^2}{t-m} + \frac {c(y-y_0)^2}{t-m}=1.\]
Vi forkorter den første brøk med \(a\) og den anden med \(c\). Det kan vi gøre fordi ved ved at \(a\) og \(c\) ikke er nul (vi har antaget at de er større end nul):
\[\frac {(x-x_0)^2}{\frac {t-m}{a}} + \frac {(y-y_0)^2}{\frac {t-m}{c}}=1.\]
Da \(t>m\) er \(t-m>0\) og da også \(a>0\) og \(c>0\) er brøkerne \(\frac {t-m}{a}\) og \(\frac {t-m}{c} \) også positive. De kan derfor skrives som kvadratrødder i anden:
\[\frac {(x-x_0)^2}{ \left (\sqrt {\frac {t-m}{a}}\right )^2} + \frac {(y-y_0)^2}{\left (\sqrt {\frac {t-m}{c}}\right )^2}=1.\]
Og der har vi den. Ellipsens ligning. Niveaukurven \(N(t)\) er altså en ellipse med centrum i \((x_0,y_0)=\left (-\frac {b}{2a},-\frac {d}{2c}\right )=C,\) vandret halvakse \(\sqrt {\frac {t-m}{a}}\) og lodret halvakse \(\sqrt {\frac {t-m}{c}}\).
Når der vælges en højere værdi af \(t\) bliver \(t-m\) større, og dermed bliver halvakserne \(\sqrt {\frac {t-m}{a}}\) og \(\sqrt {\frac {t-m}{c}}\) også større. Ud fra udtrykkene for halvaksene ses også at halvakserne bliver ens hvis \(a=c\) og vi har allerede set (se øvelse 3.7.6) at en ellipse med ens halvakser er en cirkel.
Antag nu at \(a<0\), \(c<0\) og \(t<m\): Se næste øvelse.
Øvelse 3.9.2
-
a) Gør ovenstående bevis færdigt. Det fungerer tilsvarende som når \(a>0\) og \(c>0\).
Løsning 3.9.2
-
a) Vis mig det.