szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 26 mar 2015, o 16:47 
Użytkownik

Posty: 10
Lokalizacja: Kraśnik
Na prostej l danych jest n punktów. Znaleźć punkt P, taki że suma odległości punktu P od danych punktów jest najmniejsza. Czy taki punkt jest wyznaczony jednoznacznie?

podstawiając za n kolejno małe liczby naturalne właściwie wychodzi, że dla n nieparzystego jest to jakby n środkowy, a dla n parzystego jest to przedział dwóch środkowych n z założeniem, że są to różne punkty. problem jest: jak dojść do tego algebraicznie?
Góra
Kobieta Offline
PostNapisane: 26 mar 2015, o 18:12 
Użytkownik
Avatar użytkownika

Posty: 2505
Zapisz funkcję. Jeżeli x_i to punkty, to chcesz zminimalizować \sum_{k=1}^n |x-x_k| = f(x). Żeby to zrobić, trzeba popatrzeć na pochodną. Wskazówka: patrz przedziałami, wtedy pochodna sumy to suma pochodnych, a te są równe \pm 1.
Góra
Mężczyzna Offline
PostNapisane: 26 mar 2015, o 18:17 
Użytkownik
Avatar użytkownika

Posty: 1229
Dla dwóch punktów x_1, x_2 na prostej rzeczywistej taki punkt to będzie

|x_1-x_2|.

Dla trzech punktów x_1, x_2, x_3 w \mathbb{R}^2 takim punktem faktycznie jest punkt po środku, bo ||x_1-x_3|| = ||x_1 - x_2|| + ||x_3-x_2||\le ||x_1-x'|| + ||x'-x_2|| + ||x_3-x'|| + ||x'-x_2|| dla dowolnego x'\in\mathbb{R}^2. Ta nierówność wynika z nierówności trójkąta (||\cdot,\cdot || oznacza odległość między punktami).

Uogólnienie może być nieco uciążliwe, jeśli rozumować w ten sposób dla dowolnego n.

Prostsze rozwiązanie zaproponowała Medea 2. Narysuj sobie wykres tej funkcji, zauważ, że jest kawałkami liniowa, zastanów się, gdzie ma "dzióbki".
Góra
Mężczyzna Offline
PostNapisane: 26 mar 2015, o 18:37 
Użytkownik
Avatar użytkownika

Posty: 504
Lokalizacja: Chełm
Oto wspomniane uciążliwe uogólnienie:
Rozważmy prostą i n punktów na niej. Ustalmy na niej jakiś punkt zerowy i niech x_k oznacza współrzędną punktu A_k, przy czym x_k < x_l \Leftrightarrow k<l.
Rozważmy punkt B, o współrzędnej x_p \le x_B < x_{p+1}. Niech a_B oznacza sumę odległości punktu B od punktów A_1, A_2, \ldots, A_n.
a_B=|x_B-x_1|+|x_B-x_2|+\ldots |x_B-x_n|=(x_B-x_1)+(x_B-x_2)+\ldots (x_B-x_k)+(x_{k+1}-x_B)+\ldots(x_n-x_B)=kx_B-(x_1+x_2+\ldots+x_k)+(x_n+x_{n-1}+\ldots +x_{k+1})-(n-k)x_B=(2k-n)x_B+(x_n+x_{n-1}+\ldots+x_{k+1})-(x_1+x_2+\ldots+x_k).
Widzimy więc, że spośród wszystkich punktów leżących w podanym przedziale najmniejszą sumę odległości ma punkt A_k. Możemy więc ograniczyć nasze rozważania do punktów A_1, A_2,\ldots A_n. Niech a_k oznacza sumę odległości punktu A_k od punktów A_1, A_2, \ldots, A_n.
Wtedy a_k=(2k-n)x_k+(x_n+x_{n-1}+\ldots+x_{k+1})-(x_1+x_2+\ldots+x_k). Policzmy a_{k+1}-a_k:
a_{k+1}-a_{k}=(2k-n)x_B+(x_n+x_{n-1}+\ldots+x_{k+1})-(x_1+x_2+\ldots+x_k)-\left[(2k+2-n)x_B+(x_n+x_{n-1}+\ldots+x_{k+2})-(x_1+x_2+\ldots+x_{k+1})\right]=(2k-n)(x_{k+1}-x_k).
Wiemy, że x_{k+1}-x_k>0.
Zauważmy, że dla k<\lfloor \frac{n}{2} \rfloor: a_{k+1}-a_k<0 \Rightarrow a_{k+1}<a_k, natomiast dla k>\lfloor \frac{n}{2} \rfloor: a_{k+1}-a_k>0 \Rightarrow a_{k+1}<a_k. Zatem naszym szukanym punktem jest A_{\lfloor \frac{n}{2} \rfloor}

Ufff :)
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Wyznacz punkt przecięcia się prostej z okręgiem  Anonymous  5
 Wzór na odległość punktu od prostej, odległość prost  Anonymous  1
 Znajdz równanie prostej stycznej do okręgu  Anonymous  8
 Równanie prostej przechodzącej przez 2 punkty  mnk  1
 Równanie prostej prostopadłej do prostej o równaniu y=x  apacz  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl