Jaki tok obliczeń zastosować?

Witam

Mam problem ze znalezieniem metody jak obliczyć pewną rzecz. Otóż wyjaśniam o co chodzi:

Oto przykład:

Załóżmy, że każdy kolor charakteryzuje jakaś krzywa matematyczna.
Gdybyśmy rozszczepili ten kolor na składowe, to każdą z tych składowych charakteryzuje jakaś inna krzywa. Teraz np. chcemy zrobić jakiś kolor z innych. Dla przykładu weźmy np 3 kolory składowe:

		  1 kolor	   2 kolor	    3 kolor		             Barwa wynikowa
		   -------	     -------		-------		---------------------------------------

		     10		        20		    5		 40%*10+50%+20+10%*5  = 14,5	
		     50		        20		   60		40%*50+50%*20+10%*60 = 36,0
		     40		        60		   35		40%*40+50%*60+10%*35 = 49,5

	Suma:	100%		100%		100%                                   Suma:       100%

Udział procentowy: 40% 50% 10%

I teraz tak: Mamy np. jakąś barwę, która jest barwą wynikową i znamy jej krzywą. Wiemy z jakich kolorów składowych się ona składa i jak wyglądają poszczególne krzywe tych składowych. Pytanie za 100 pkt :) :

Jak obliczyć udział procentowy każdej barwy składowej? Chcę jeszcze zaznaczyć, że obliczone udziały procentowe nie zawsze dadzą idealną krzywą barwy wynikowej. Chodzi o to, żeby obliczyć takie udziały procentowe, żeby ta krzywa wynikowa była jak najbardziej zbliżona do barwy wynikowej...

Dziękuję

Aha! Zapomniałem dopisać, że może być nawet 8 kolorów składowych a krzywa może się skłądać nie z trzech punktów jak podałem w przykładzie, tylko np z 17.

Wygląda to na szukanie minimum funkcji: |Ax-y|, gdzie:

|.| jest normą
A - macierz kolorów
x - wektor reprezentujący udział procentowy
y - wektor barwy wynikowej

Jeśli udziały procentowe dają wynik dokładny, to oczywiście rozwiązanie jest trywialne:
x=A^-1 * y

Jeśli nie, to pozostaje wyznaczyć minimum |Ax-y|. O ile pamięc mnie nie myli, to przy szukaniu korzystało się z nierówność trójkąta dla norm: |Ax-y|<=|Ax-y0|+|y-y0| i szukało rzutu chyba wektora y na przestrzeń generowaną przez wektory z A. Gdzieś pod koniec pojawiały się rozkłady SVD macierzy.

Można też zastosować inne podejście do minimalizacji funkcji |Ax-y|, np. algorytmy genetyczne, bądź inne metody optymalizacji nieliniowej.

pzdr,

Dzięki wielkie, to jakaś wskazówka.

AlgorytmNieznany napisał(a)

Dzięki wielkie, to jakaś wskazówka.

Dodam jeszcze, że jeśli za normę przyjmiesz normę kwadratową, to warto zapoznać się z tematem "Metoda najmniejszy kwadratów".

pzdr,

Panowie, błądzę...
Potrzebuje gotowca...

;-)

@AlgorytmNieznany: nie myl pojęcia koloru i barwy. Kolory, które są odcieniami szarości są bezbarwne ;)

Minimum funkcji ? Hmmm. Mi to wygląda na zwykłą kombinację liniową. Weź książkę do algebry, znajdź jak przejść z bazy euklidesowej do dowolnej innej bazy. Hmm, ale 8 wektorów (kolorów) bazowych to za mało aby tworzyć 17 wymiarową przestrzeń liniową. Oznacza to, że w skład twojej przestrzenie nie wchodzą wszystkie kolory.

Wektor kolumnowy będę oznaczać w nawiasach kwadratowych, wektor wierszowy w okrągłych.

W przykładzie twoja baza (nazwijmy ją baza V) składa się z 3 wektorów (kolorów) bazowych:
v1 = (10 50 40), v2 = (20 20 60), v3 = (5 60 32)
Wektory w tej bazie to udziały procentowe.
Baza euklidesowa (nazwijmy ją baza E) składa się z wersorów:
e1 = (1 0 0), e2 = (0 1 0), e3 = (0 0 1)
Wektory w tej bazie to krzywe kolorów.

Na początku w przykładzie pokazałeś operację odwrotną, do tej o którą pytasz. Wziąłeś wektor własnej bazy
v = [40% 50% 10%]
i przedstawiłeś go jako wektor bazy euklidesowej
e = [14,5 36,0 49,5].
Operacje tę wykonałeś przez mnożenie, które można zapisać macierzowo:
e = A * v
'A' nazywa sie macierzą przejścia z bazy V do bazy E. Jako że przejście odbywa się do bazy euklidesowej macierz przejścia (A) składa się po prostu z kolejno ułożonych jeden pod drugim wektorów bazowych bazy V
A = [v1 v2 v3]
Pytasz natomiast o przejście odwrotne z bazy E do bazy V. Macierz takiego przejścia to macierz odwrotna do macierzy A. Znajdź ją, a będzie po problemie. Jeśli oznaczymy ją A' to mając wektor e bazy E (krzywą koloru) z łatwością znajdziemy jego reprezentację v w bazie V (udziały procentowe) wykonując mnożenie:
v = A' * e

Matematycznie wygląda to następująco (podaję to jedynie jako ciekawostkę). Cała zależność opiera się na równości kombinacji liniowych:
[v1 v2 v3] * v = [e1 e2 e3] * e
Wersory e1, e2, e3 tworzą macierz jednostkową I=[e1 e2 e3], więc można ją wywalić z równania i zostaje:
[v1 v2 v3] * v = e
Ty pytasz jak znaleźć 'v' znając 'e' oraz 'v1', 'v2' i 'v3' . No to mnożymy obie strony równania przez macierz odwrotną (A'):
[v1 v2 v3]' * [v1 v2 v3] * v = [v1 v2 v3]' * e
I * v = [v1 v2 v3]' * e
v = [v1 v2 v3]' * e
Jak widzimy zostaje znaleźć macierz A' = [v1 v2 v3]'

Jeśli macierz A okaże się nieodwracalna oznaczać to będzie, że kolory bazowe nie generują przestrzeni liniowej, gdyż nie są liniowo niezależne. Innymi słowy nie będą tworzyć bazy i operacja którą chcesz wykonać będzie nie możliwa, przejście które wykonujesz na początku będzie zazwyczaj nieodwracalne.

Jak już pisałem wcześnie 8 wektorów to za mało aby tworzyć 17 wymiarową przestrzeń. Niektóre 17-wymiarowe kolory (krzywe kolorów) nie będą wchodzić w skład twojej 8-wymiarowej przestrzeni. Jeśli weźmiesz krzywą koloru który nie należy do twojej przestrzeni i pomnożysz przez nią macierz (A') przejścia do twojej bazy V to otrzymasz udziały procentowe ujemne lub większe od 100%

Z pierwszego posta:

Chodzi o to, żeby obliczyć takie udziały procentowe, żeby ta krzywa wynikowa była jak najbardziej zbliżona do barwy wynikowej...

adf88 napisał(a)

@AlgorytmNieznany: nie myl pojęcia koloru i barwy. Kolory, które są odcieniami szarości są bezbarwne ;)
Minimum funkcji ? Hmmm. Mi to wygląda na zwykłą kombinację liniową.

Tak, masz rację. Jest to zwykła kombinacja liniowa jeśli istnieje dokładne rozwiązanie. Wtedy układ równań liniowych Ax=y ma trywialne rozwiązanie: x=A^-1*y.

Jeśli jednak dokładne rozwiązanie nie istnieje, to szukamy przybliżonego rozwiązania u, takiego że błąd e=A*u-y jest możliwie najmniejszy. Teraz pojawia się pytanie, jak sensownie mierzyć wielkość tego błędu? I tu pojęcie normy wydaje się być sensowną odpowiedzią ;)

pzdr,