Matematické Fórum

miroun · 08. 02. 2014 18:22

Ahoj,
jedná se o součást hobby projektu počítačového vidění.
mám soustavu tří kvadratických rovnic se třemi neznámými $t_{0}, t_{1}, t_{2}\in (0;\infty)$ .
Ostatní písmenka jsou konstanty:
$a_{0}, a_{1}, a_{2}, b_{0}, b_{1}, b_{2}\in R$
$l, c_{0}, c_{1}, c_{2}\in (0;\infty)$

Tady je soustava rovnic:
$t_{0}^2(a_{0}^2+b_{0}^2+c_{0}^2)+t_{1}^2(a_{1}^2+b_{1}^2+c_{1}^2)-2t_{0}t_{1}(a_{0}a_{1}+b_{0}b_{1}+c_{0}c_{1})-l^2=0$
$t_{0}^2(a_{0}^2+b_{0}^2+c_{0}^2)+t_{2}^2(a_{2}^2+b_{2}^2+c_{2}^2)-2t_{0}t_{2}(a_{0}a_{2}+b_{0}b_{2}+c_{0}c_{2})-l^2=0$
$t_{1}^2(a_{1}^2+b_{1}^2+c_{1}^2)+t_{2}^2(a_{2}^2+b_{2}^2+c_{2}^2)-2t_{1}t_{2}(a_{1}a_{2}+b_{1}b_{2}+c_{1}c_{2})-l^2=0$

Potřebuji to celé upravit do tvaru
$t_{0}=...$
$t_{1}=...$
$t_{2}=...$
Kde každá neznámá bude vyjádřena jako funkce konstant (nikoliv ostatních neznámých). Pokud se nemýlím, tak by mělo být v definičním oboru (kladných čísel) jen jedno řešení.

Bohužel se mi vůbec nedaří upravit rovnice do tohoto tvaru. Zkoušel jsem rovnice sčítat, vyjádřit si jednu z proměnných a dosadit, řešit pomocí diskriminantu, různě upravovat, ale stále se točím v kruzích, vždycky se dostanu zase zpátky k původní soustavě rovnic. Prosím o pomoc zkušenější matematiky.

Pokud by někoho zajímalo co rovnice představuje, jde o výpočet souřadnic vrcholů rovnostranného trojuhelníku o straně $l$ v prostoru. Každý z vrcholů leží na jedné ze tří přímek procházejících počátkem soustavy souřadnic a daných vektorem $[a_{n},b_{n},c_{n}]$ . Vrchol trojuhelníku pak bude mít souřadnice $t_{n}.[a_{n},b_{n},c_{n}]$ .

Předem díky za pomoc
Miroun

jelena · 09. 02. 2014 00:27

Zdravím,

pokud jsem rozuměla dobře, tak jsi použil vzorce na výpočet vzdálenosti bodů (v prostoru). Trochu se mi nezdá, že jako neznámé vystupuji parametry, kterými bys zadával přímky procházející počátkem. Mám takový dojem, že jeden z vrcholu trojúhelníku by měl být zadán (tedy jedno $t$ se zadá), zbývající 2 se dopočtou z podmínky, že trojúhelník je rovnostranný. A ani tak to řešení nebude jedno. Jelikož 2. bod může být libovolně na kružnice o poloměru l od prvního a až 3. bod se "zachytí" do 2 možných pozic od prvních dvou.

Jiná možnost je zadávat střed kružnice opsané, který "zachytí" umístění trojúhelníku a umístění vrcholů může být libovolně na kružnici opsané (+podmínka délky strany).

Proč $c$ má být jen kladné? Má to nějaký důvod? Je možné, že celá úloha je míněná jinak - snad to okomentuj, prosím.

Ještě můžeš zkusit přepsat do přehlednějšího tvaru, že rozsáhlé závorky nahradíš jednou konstantou, např. $kx^2+my^2-2nxy-l^2=0$ a takové rovnice vložit do WA nějak tak (jen vzor vložení), ale zda to ubohý stroj zpracuje, to nevím.

miroun · 09. 02. 2014 01:21 — Editoval miroun (09. 02. 2014 03:11)

↑ jelena:
Díky za reakci. Pokusím se na všechno odpovědět:

pokud jsem rozuměla dobře, tak jsi použil vzorce na výpočet vzdálenosti bodů (v prostoru)

Ano.

Trochu se mi nezdá, že jako neznámé vystupuji parametry, kterými bys zadával přímky procházející počátkem

Přímky pocházející počátkem jsou dané konstantami $a_{n},b_{n},c_{n}$ , přesněji řečeno pomocí vektorů $[a_{n},b_{n},c_{n}]$ . Pokud si situaci zjednodušíme tím, že budou tyto vektory normované (jednotkové), potom neznámá $t_{n}$ znamená vzdálenost vrcholu trojúhelníku od počátku.

Mám takový dojem, že jeden z vrcholu trojúhelníku by měl být zadán

Bohužel ani jeden z vrcholů není zadán.

A ani tak to řešení nebude jedno

Zkoušel jsem to i fyzicky zkonstruovat ze špejlí a vystřiženého trojúhelníku a skutečně nemohu najít více než jedno řešení. Je možné, že budou mít rovnice více kořenú, ale mimo definiční obor.

Proč c má být jen kladné?

Vychází to z podstaty řešeného problému (počítačové vidění). Objekt se vždy nacházi v "poloprostoru" před kamerou, proto je vždy konstanta c>0.

Jiná možnost je zadávat střed kružnice opsané, který "zachytí" umístění trojúhelníku a umístění vrcholů může být libovolně na kružnici opsané (+podmínka délky strany).

Znám pouze vektory přímek a velikost trojúhelníku. Střed trojúhelníku (kružnice) by se opět musel vypočítat podobnou soustavou rovnic.

rovnice vložit do WA

Zkusil jsem:
solve m*d^2+n*g^2-2*d*g*p-h=0, m*d^2+o*f^2-2*d*f*q-h=0, n*g^2+o*f^2-2*g*f*r-h=0 with respect to d, g, f
Výsledek: Standard computation time exceeded...

jelena · 09. 02. 2014 10:22

↑ miroun:

děkuji, snad je mi to více jasné - tedy hledáme v prostoru takovou situaci, že vznikne nepravidelný čtyřstěn (základna rovnostranný trojúhelník, vrchol v počátku souřadnic).
Jelikož můžeme uvažovat podobnost, podaří se výpočet pomocných $t$ dle takové podmínky: $t_0$ zadáme (např. $t_0=1$ ) a najít zbývající $t$ , aby vzdálenost mezi body byla stejná. A tuto vzdálenost vyjádřit jako $l_0$ .
Potom najít poměr vzdálenosti $l/l_0$ a všechna t zvětšit v poměru.

Pořád ale mám dojem, že při některých počátečních volbách směrových vektorů úloha nebude řešitelná, ale jen dojem. Co kolegové? Děkuji.

mák · 09. 02. 2014 10:33

Zdravím,
při svém koníčku i v zaměstnání se často setkávám s tím, že většina rovnic nejde řešit algebraicky, ale pouze numericky. Někdy pomůže jiný pohled na problém a někdy ne. To možná bude tento případ.
Pro zajímavost jsem to zadal do Mathematicy a po přibližně dvaceti minutách vypsala výsledek. Myslím, že tam opravdu bylo více řešení jak jedno. Bohužel měla více rozumu jak já, když oznámila, výstup je příliš dlouhý pro zobrazení a tak zobrazila jenom část (strukturu) s vynechanými opakujícími, nebo příliš dlouhými části (jsou nahrazené další proměnou - po stisku tlačítka se zobrazí kompletní výstup).
Takže v tomto případě je numerické řešení opravdu mnohem jednodušší a asi i rychlejší.

jelena · 09. 02. 2014 12:54

↑ mák:

Zdravím,

v čem by mohl být jiný pohled, než analytická geometrie? Navrhuji podobnost, ale to cca do zpracování totéž. Dle mého návrhu už to Matematica zpracuje? Ještě můžeme zjednodušit značení, že v každé rovnici podělíme (závorkou) u prvního členu, tedy koeficient 1. členu je 1, poměry konstant přeznačíme atd. např. 1. rovnice pro $t_0=1$ dopadne tak:
$1+t_{1}^2k-2t_{1}n-m=0$

Děkuji.

miroun · 09. 02. 2014 13:52

Myslím, že budou dvě řešení, z toho ale jen jedno v definičním oboru. Druhé řešení bude obraz prvního řešení bodově souměrný podle počátku. Ještě jsem asi zapomněl zdůraznit, že vstupní vektory budou vždy různoběžné. Pokud by všechny vektory měly stejný směr, potom by žádné řešení nebylo. Pokud by pouze dva vektory měly stejný směr, potom by opět bylo jedno řešení v definičním oboru a jedno řešení mimo definiční obor.

↑ jelena:
Zajímavý nápad. Vznikne tedy stejná soustava, ale jedno $t$ bude známé a $l$ bude neznámé. Zkusím

↑ mák:

Pro zajímavost jsem to zadal do Mathematicy

Je možné že vzorec bude složitý a že tam bude více řešení pro různé podmínky. Pokud ještě máš výsledek, tak jej prosím pošli.

Takže v tomto případě je numerické řešení opravdu mnohem jednodušší a asi i rychlejší.

Rovnice se bude v programu počítat minimálně jednou v každém snímku, tedy minimálně cca 30x za sekundu na relativně pomalém cpu. Pokud správně chápu numerické řešení jako postupné hádání a zkoušení hodnot neznámých, byla by to až krajní varianta. Mnohem rychlejší by bylo mít v programu již upravený vzorec, kdy se jen sečtou/vynásobí/odmocní vstupní hodnoty.

Díky
Miroun

gadgetka

Zdravím vespolek, a co to upravit tímto stylem?
$t_{0}^2(a_{0}^2+b_{0}^2+c_{0}^2)+t_{1}^2(a_{1}^2+b_{1}^2+c_{1}^2)-2t_{0}t_{1}(a_{0}a_{1}+b_{0}b_{1}+c_{0}c_{1})-l^2=0$
$t_{0}^2(a_{0}^2+b_{0}^2+c_{0}^2)+t_{2}^2(a_{2}^2+b_{2}^2+c_{2}^2)-2t_{0}t_{2}(a_{0}a_{2}+b_{0}b_{2}+c_{0}c_{2})-l^2=0$
$t_{1}^2(a_{1}^2+b_{1}^2+c_{1}^2)+t_{2}^2(a_{2}^2+b_{2}^2+c_{2}^2)-2t_{1}t_{2}(a_{1}a_{2}+b_{1}b_{2}+c_{1}c_{2})-l^2=0$

$(k_0t_0+k_1t_1)^2-l^2=0$ ...

$(k_0t_0+k_1t_1-l)(k_0t_0+k_1t_1+l)=0$
$(k_0t_0+k_2t_2-l)(k_0t_0+k_2t_2+l)=0$
$(k_1t_1+k_2t_2-l)(k_1t_1+k_2t_2+l)=0$

... kde
$k_0=a_{0}^2+b_{0}^2+c^2_0$
$k_1=a_{1}^2+b_{1}^2+c^2_1$
$k_2=a_{2}^2+b_{2}^2+c^2_2$

... třeba by s tím šlo pak lépe pracovat... (nezkoušela jsem, jen tipuji) :)

Edit: Rovnou ten nápad škrtám, protože jednotlivé členy konstant nejsou v součinu, čili by to moje rozložení nebylo správné...

jelena · 09. 02. 2014 17:14

Nechala jsem $t_0=1$ a závorky jsem přeznačila za nové proměnné (s původním označením nesouvisí), $z$ je kvadrát délky pomocného podobného trojúhelníku. Snad v tom není nějaký překlep.

$a+bx^2-2dx-z=0$
$a+ky^2-2my-z=0$
$bx^2+ky^2-2uxy-z=0$

Z prvních 2 rovnic by šlo sestavit kořeny kvadratických rovnic pro x, y (ve vyjádření zůstane jen z) a dosadit do 3. rovnice. Tam by měla vzniknout rovnice jen s neznámou z, ale zda bude odvozovatelná, to jsem nezkoušela, jen narychlo. Vede to někam? Děkuji.

miroun · 09. 02. 2014 20:39 — Editoval miroun (09. 02. 2014 20:46)

↑ jelena:
Předpokládejme, že první i druhá rovnice má řešení. Potom lze vyjádřit
$x=\frac{d\pm \sqrt{d^2+b(z-a)}}{b}$
$y=\frac{m\pm \sqrt{m^2+k(z-a)}}{k}$
Po dosazení do třetí rovnice:
$\frac{(d\pm \sqrt{d^2+b(z-a)})^2}{b}+\frac{(m\pm \sqrt{m^2+k(z-a)})^2}{k}-2u\frac{d\pm \sqrt{d^2+b(z-a)}}{b}.\frac{m\pm \sqrt{m^2+k(z-a)}}{k}-z=0$
Já vím že to $\pm$ je prasárna, správně bych měl rozepsat 4 varianty.
Zkoušel jsem zadat do WA, ale pořád to píše Standard computation time exceeded. Ruční řešení nemůžu najít. Roznásobil jsem to, ale je to velmi dlouhé se spoustou různých odmocnin, které neumím odstranit.

díky
Miroun

miroun · 09. 02. 2014 21:09

Tak jsem ještě zkoušel konstruovat trojúhelník z papíru a ze špejlí a zjistil jsem, že úloha má opravdu vice než jedno řešení v definičním oboru. Myslím, že řešení budou 2 (+minimálně další 2 mimo def. obor).

mák · 11. 02. 2014 13:43

Počítám pouze s numerickým řešením jedné proměnné.
Z mé zkušenosti stačí na přesnost 12 platných míst tak 4 až 7 opakování. U tohoto nevím.
Taky záleží na prvopočátečním odhadu (někdy se dá použít Taylor pro automatický odhad).

↑ miroun:

Pokud ještě máš výsledek, tak jej prosím pošli.

Psal jsem, že je příliš veliký. Možná, kdyby byl menší, tak by mi stačila paměť RAM (8GB) a swapovací soubor (12GB) a šel by zobrazit celý, takle jsem po dosažení 16.5GB Mathematicu raději ukončil (neodpovídala, měla dost práce s kreslením odmocnin), abych si neudělal nějaký problém. Proto jsem také předpokládal, že numerické řešení bude výkonově i časově podstatně méně náročné.

miroun · 12. 02. 2014 04:41

Je zajímavé, že algebra (asi) nemá odpověď na tuto zdánlivě triviální geometrickou úlohu.

↑ mák:
Numerické řešení zřejmě opravdu bude jediná možnost. Pokud ale stačí jednotky iterací, pak to není problém. Počáteční odhad se bude brát z předchozích snímků, případně z dalších už vypočtených hodnot ve scéně. Mockrát díky za kompletní výpočet v odkazovaném souboru.

kdyby byl menší, tak by mi stačila paměť RAM

:-)

Díky
Miroun

Matematické Fórum

#1 08. 02. 2014 18:22

Soustava tří kvadratických rovnic se třemi neznámými

#2 09. 02. 2014 00:27

Re: Soustava tří kvadratických rovnic se třemi neznámými

#3 09. 02. 2014 01:21 — Editoval miroun (09. 02. 2014 03:11)

Re: Soustava tří kvadratických rovnic se třemi neznámými

#4 09. 02. 2014 10:22

Re: Soustava tří kvadratických rovnic se třemi neznámými

#5 09. 02. 2014 10:33

Re: Soustava tří kvadratických rovnic se třemi neznámými

#6 09. 02. 2014 12:54

Re: Soustava tří kvadratických rovnic se třemi neznámými

#7 09. 02. 2014 13:52

Re: Soustava tří kvadratických rovnic se třemi neznámými

#8 09. 02. 2014 14:30 — Editoval gadgetka (09. 02. 2014 14:38)

Re: Soustava tří kvadratických rovnic se třemi neznámými

#9 09. 02. 2014 17:14

Re: Soustava tří kvadratických rovnic se třemi neznámými

#10 09. 02. 2014 20:39 — Editoval miroun (09. 02. 2014 20:46)

Re: Soustava tří kvadratických rovnic se třemi neznámými

#11 09. 02. 2014 21:09

Re: Soustava tří kvadratických rovnic se třemi neznámými

#12 11. 02. 2014 13:43

Re: Soustava tří kvadratických rovnic se třemi neznámými

#13 12. 02. 2014 04:41

Re: Soustava tří kvadratických rovnic se třemi neznámými

Zápatí