Е. Деза_ М.М. Деза. Энциклопедический словарь расстояний (2008) (Е. Деза_ М.М. Деза. Энциклопедический словарь расстояний (2008).pdf), страница 8
Описание файла
PDF-файл из архива "Е. Деза_ М.М. Деза. Энциклопедический словарь расстояний (2008).pdf", который расположен в категории "". Всё это находится в предмете "(ммо) методы машинного обучения" из 10 семестр (2 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 8 страницы из PDF
ï ËÏÂÂÚ ÔÎÓÚÌÓ ÔÓ‰ÏÌÓÊÂÒÚ‚Ó ˝ÎÂÏÂÌÚÓ‚ ÒÔÂËӉ˘ÂÒÍËÏË Ó·ËÚ‡ÏË) Ë Ú‡ÌÁËÚË‚ÌÓÈ (Ú.Â. ‰Îfl β·˚ı ‰‚Ûı ÌÂÔÛÒÚ˚ıÓÚÍ˚Ú˚ı ÔÓ‰ÏÌÓÊÂÒÚ‚ Ä, Ç ÏÌÓÊÂÒÚ‚‡ ï ÒÛ˘ÂÒÚ‚ÛÂÚ Ú‡ÍÓ ˜ËÒÎÓ n, ˜ÚÓf n ( A) ∩ B ≠ 0/) .åÂÚ˘ÂÒÍÓ ‡ÒÒÎÓÂÌËÂèÛÒÚ¸ (X,d) – ÔÓÎÌÓ ÏÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó. èÓ‰ÏÌÓÊÂÒÚ‚‡ å1 Ë å2ÏÌÓÊÂÒÚ‚‡ ï ̇Á˚‚‡˛ÚÒfl ˝Í‚ˉËÒÚ‡ÌÚÌ˚ÏË (‡‚ÌÓÓÚÒÚÓfl˘ËÏË), ÂÒÎË ‰ÎflÍ‡Ê‰Ó„Ó x ∈ M1 ÒÛ˘ÂÒÚ‚ÛÂÚ y ∈ M 2 Ò d(x,y), ‡‚Ì˚Ï ı‡ÛÒ‰ÓÙÓ‚ÓÈ ÏÂÚËÍ ÏÂʉÛÏÌÓÊÂÒÚ‚‡ÏË å1 Ë å2 .
åÂÚ˘ÂÒÍÓ ‡ÒÒÎÓÂÌË ÔÓÒÚ‡ÌÒÚ‚‡ (X,d) ÂÒÚ¸ ‡Á·ËÂÌË ÏÌÓÊÂÒÚ‚‡ ï ̇ ËÁÓÏÂÚ˘ÂÒÍË ‚Á‡ËÏÌÓ ˝Í‚ˉËÒÚ‡ÌÚÌ˚ Á‡ÏÍÌÛÚ˚ ÏÌÓÊÂÒÚ‚‡.åÂÚ˘ÂÒÍÓ هÍÚÓ-ÔÓÒÚ‡ÌÒÚ‚Ó X/ ̇ÒΉÛÂÚ Ì‡ÚۇθÌÛ˛ ÏÂÚËÍÛ, ‰ÎflÍÓÚÓÓÈ ‡ÒÒÚÓflÌÌÓ ÓÚÓ·‡ÊÂÌË fl‚ÎflÂÚÒfl ÔÓ‰ÏÂÚËÂÈ.ëÚÛÍÚÛ‡ ÏÂÚ˘ÂÒÍÓ„Ó ÍÓÌÛÒ‡èÛÒÚ¸ (X, d, x0) – ÔÛÌÍÚËÓ‚‡ÌÌÓ ÏÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó, Ú.Â. ÔÓÒÚ‡ÌÒÚ‚Ó (X, d) Ò ÙËÍÒËÓ‚‡ÌÌÓÈ ÚÓ˜ÍÓÈ x0 ∈ X. ëÚÛÍÚÛÓÈ ÏÂÚ˘ÂÒÍÓ„Ó ÍÓÌÛÒ‡ ̇ ÌÂÏfl‚ÎflÂÚÒfl (ÚӘ˜ÌÓ) ÌÂÔÂ˚‚ÌÓ ÒÂÏÂÈÒÚ‚Ó ft(t ∈ ≥ 0) ‡ÒÚflÊÂÌËÈ ÏÌÓÊÂÒÚ‚‡ ï,ÓÒÚ‡‚Îfl˛˘Ëı ËÌ‚‡Ë‡ÌÚÌÓÈ ÚÓ˜ÍÛ ı0 , Ú‡Í ˜ÚÓ d(ft(x,y), f t(y)) = td(x,y) ‰Îfl ‚ÒÂı ı, ÛË ft ⋅ fs = fts.Ň̇ıÓ‚Ó ÔÓÒÚ‡ÌÒÚ‚Ó ËÏÂÂÚ Ú‡ÍÛ˛ ÒÚÛÍÚÛÛ ‰Îfl ‡ÒÚflÊÂÌËÈ ft(x) == tx(t ∈ ≥ 0).
֢ ӉÌËÏ ÔËÏÂÓÏ fl‚ÎflÂÚÒfl ‚ÍÎˉӂ ÍÓÌÛÒ Ì‡‰ ÏÂÚ˘ÂÒÍËÏÔÓÒÚ‡ÌÒÚ‚ÓÏ (ÒÏ. åÂÚË͇ ÍÓÌÛÒ‡, „Î.9).åÂÚ˘ÂÒÍËÈ ÍÓÌÛÒåÂÚ˘ÂÒÍËÏ ÍÓÌÛÒÓÏ Ì‡Á˚‚‡ÂÚÒfl ÏÌÓÊÂÒÚ‚Ó ‚ÒÂı ÔÓÎÛÏÂÚËÍ Ì‡ ÏÌÓÊÂÒÚ‚ÂVn = {1,…,n}.å‡Úˈ‡ ‡ÒÒÚÓflÌËÈèÛÒÚ¸ (X = {x1,…,xn}, d) – ÍÓ̘ÌÓ ÏÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó. Ö„Ó Ï‡Úˈ‡‡ÒÒÚÓflÌËÈ – ˝ÚÓ ÒËÏÏÂÚ˘̇fl n × n χÚˈ‡ ((dij)), „‰Â dij = d(xi, xj) ‰Îfl β·˚ı1 ≤ i, j ≤ n.å‡Úˈ‡ ä˝ÎË–åÂ̄‡èÛÒÚ¸ (X = {x 1 ,…,xn}, d) – ÍÓ̘ÌÓ ÏÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó. å‡ÚˈÂÈ ä˝ÎË–åÂ̄‡ ‰Îfl ÌÂ„Ó fl‚ÎflÂÚÒfl ÒËÏÏÂÚ˘̇fl (n+1) × (n+1) χÚˈ‡0CM ( X , d ) = Tee,D„‰Â D = (dij)) ÂÒÚ¸ χÚˈ‡ ‡ÒÒÚÓflÌËÈ ÔÓÒÚ‡ÌÒÚ‚‡ (X , d ), ‡ –n-‚ÂÍÚÓ, ‚ÒÂÍÓÏÔÓÌÂÌÚ˚ ÍÓÚÓÓ„Ó ‡‚Ì˚ 1. éÔ‰ÂÎËÚÂθ χÚˈ˚ CM(X,d) ̇Á˚‚‡ÂÚÒflÓÔ‰ÂÎËÚÂÎÂÏ ä˝ÎË–åÂ̄‡.37É·‚‡ 1.
鷢ˠÓÔ‰ÂÎÂÌËflå‡Úˈ‡ ɇÏχèÛÒÚ¸ v1 ,…,vk – ˝ÎÂÏÂÌÚ˚ ‚ÍÎˉӂ‡ ÔÓÒÚ‡ÌÒÚ‚‡. å‡ÚˈÂÈ É‡Ïχ fl‚ÎflÂÚÒflÒËÏÏÂÚ˘̇fl k × k χÚˈ‡G( v1 ,...vk ) =(( v , v ))ijÔÓÔ‡Ì˚ı Ò͇ÎflÌ˚ı ÔÓËÁ‚‰ÂÌËÈ ˝ÎÂÏÂÌÚÓ‚ v1 ,…,vk.k × k χÚˈ‡ fl‚ÎflÂÚÒfl ÔÓÎÓÊËÚÂθÌÓ ÔÓÎÛÓÔ‰ÂÎÂÌÌÓÈ ÚÓ„‰‡ Ë ÚÓθÍÓ ÚÓ„‰‡,ÍÓ„‰‡ ˝ÚÓ Ï‡Úˈ‡ ɇÏχ. k × k χÚˈ‡ fl‚ÎflÂÚÒfl ÔÓÎÓÊËÚÂθÌÓ ÓÔ‰ÂÎÂÌÌÓÈÚÓ„‰‡ Ë ÚÓθÍÓ ÚÓ„‰‡, ÍÓ„‰‡ Ó̇ – χÚˈ‡ ɇÏχ Ò ÎËÌÂÈÌÓ ÌÂÁ‡‚ËÒËÏ˚ÏËÓÔ‰ÂÎfl˛˘ËÏË ‚ÂÍÚÓ‡ÏË.1G(v1,…,vk) = (( d E2 ( vi , v j ))) + d E2 ( v0 , v j ) − d E2 ( vi , v j ))), Ú.Â. Ò͇ÎflÌÓ ÔÓËÁ‚‰ÂÌËÂ2〈,〉 ÂÒÚ¸ ÔÓ‰Ó·ÌÓÒÚ¸ ÔÓËÁ‚‰ÂÌËfl ÉÓÏÓ‚‡ ‰Îfl Í‚‡‰‡Ú‡ ‚ÍÎˉӂ‡ ‡ÒÒÚÓflÌËfl d E2 .k × k χÚˈ‡ (( d E2 ( vi , v j ))) ÂÒÚ¸ ‡ÒÒÚÓflÌË ÓÚˈ‡ÚÂθÌÓ„Ó ÚËÔ‡; ‚Ò ڇÍË k × kχÚˈ˚ Ó·‡ÁÛ˛Ú (ÌÂÔÓÎË˝‰‡Î¸Ì˚) Á‡ÏÍÌÛÚ˚È ‚˚ÔÛÍÎ˚È ÍÓÌÛÒ ‚ÒÂı Ú‡ÍËı‡ÒÒÚÓflÌËÈ Ì‡ ‰‡ÌÌÓÏ k-ÏÌÓÊÂÒÚ‚Â.éÔ‰ÂÎËÚÂθ χÚˈ˚ ɇÏχ ̇Á˚‚‡ÂÚÒfl ÓÔ‰ÂÎËÚÂÎÂÏ É‡Ïχ; „ӂÂ΢Ë̇ ‡‚̇ Í‚‡‰‡ÚÛ k-ÏÂÌÓ„Ó Ó·˙Âχ Ô‡‡ÎÎÂÎÓÚÓÔ‡, ÔÓÒÚÓÂÌÌÓ„Ó Ì‡v1 ,…,vk.àÁÓÏÂÚËflèÛÒÚ¸ (X, dï) Ë (Y, dY) – ÏÂÚ˘ÂÒÍË ÔÓÒÚ‡ÌÒÚ‚‡.
îÛÌ͈Ëfl f : X → Y ̇Á˚‚‡ÂÚÒflËÁÓÏÂÚ˘ÂÒÍËÏ ‚ÎÓÊÂÌËÂÏ ï ‚ Y, ÂÒÎË Ó̇ ËÌ˙ÂÍÚ˂̇ Ë ‰Îfl ‚ÒÂı x, y ∈ X ËÏÂÂÚÏÂÒÚÓ ‡‚ÂÌÒÚ‚Ó dY(f(x), f(y)) = dX(x,y).àÁÓÏÂÚËÂÈ Ì‡Á˚‚‡ÂÚÒfl ·ËÂÍÚË‚ÌÓ ËÁÓÏÂÚ˘ÂÒÍÓ ‚ÎÓÊÂÌËÂ. Ñ‚‡ ÏÂÚ˘ÂÒÍËı ÔÓÒÚ‡ÌÒÚ‚‡ ̇Á˚‚‡˛ÚÒfl ËÁÓÏÂÚ˘ÂÒÍËÏË (ËÎË ËÁÓÏÂÚ˘ÂÒÍË ËÁÓÏÓÙÌ˚ÏË), ÂÒÎË ÏÂÊ‰Û ÌËÏË ÒÛ˘ÂÒÚ‚ÛÂÚ ËÁÓÏÂÚËfl.ë‚ÓÈÒÚ‚‡ ÏÂÚ˘ÂÒÍËı ÔÓÒÚ‡ÌÒÚ‚, ÒÓı‡Ìfl˛˘ËÂÒfl ËÌ‚‡Ë‡ÌÚÌ˚ÏË ÓÚÌÓÒËÚÂθÌÓ ËÁÓÏÂÚËÈ (ÔÓÎÌÓÚ‡, Ó„‡Ì˘ÂÌÌÓÒÚ¸ Ë Ú.Ô.), ̇Á˚‚‡˛ÚÒfl ÏÂÚs˘ÂÒÍËÏËÒ‚ÓÈÒÚ‚‡ÏË (ËÎË ÏÂÚ˘ÂÒÍËÏË ËÌ‚‡Ë‡ÌÚ‡ÏË).àÁÓÏÂÚËÂÈ ÔÛÚË (ËÎË ÎËÌÂÈÌÓÈ ËÁÓÏÂÚËÂÈ) fl‚ÎflÂÚÒfl ÔÂÓ·‡ÁÓ‚‡ÌËÂ ï ‚ Y (ÌÂÓ·flÁ‡ÚÂθÌÓ ·ËÂÍÚË‚ÌÓÂ), ÒÓı‡Ìfl˛˘Â ‰ÎËÌÛ ÍË‚˚ı.ÜÂÒÚÍÓ ÔÂÂÏ¢ÂÌË ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ÜÂÒÚÍËÏ ÔÂÂÏ¢ÂÌËÂÏ (ËÎË ÔÓÒÚÓ ÔÂÂÏ¢ÂÌËÂÏ) ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ (X,d) ̇Á˚‚‡ÂÚÒfl ËÁÓÏÂÚËfl (X,d) ̇ Ò·fl.ÑÎfl ÔÂÂÏ¢ÂÌËfl f ÙÛÌ͈Ëfl ÔÂÂÌÂÒÂÌËfl df (x) ‡‚̇ df (x, f(x)).
èÂÂÏ¢ÂÌË ḟÁ˚‚‡ÂÚÒfl ÔÓÎÛÔÓÒÚ˚Ï, ÂÒÎË inf d f ( x ) = d ( x 0 , f ( x 0 )) ‰Îfl ÌÂÍÓÚÓÓ„Ó x0 ∈ X,x ∈XË Ô‡‡·Ó΢ÂÒÍËÏ ‚ ÓÒڇθÌ˚ı ÒÎÛ˜‡flı. èÓÎÛÔÓÒÚÓ ÔÂÂÏ¢ÂÌË ̇Á˚‚‡ÂÚÒfl˝ÎÎËÔÚ˘ÂÒÍËÏ, ÂÒÎË inf d f ( x ) = 0 Ë ÓÒ‚˚Ï (ËÎË „ËÔ·Ó΢ÂÒÍËÏ) ‚ ÓÒڇθÌ˚ıx ∈XÒÎÛ˜‡flı. èÂÂÏ¢ÂÌË ̇Á˚‚‡ÂÚÒfl ÔÂÂÌÓÒÓÏ äÎËÙÙÓ‰‡, ÂÒÎË ÙÛÌ͈Ëfl ÔÂÂÌÂÒÂÌËfl df (x) fl‚ÎflÂÚÒfl ÍÓÌÒÚ‡ÌÚÓÈ ‰Îfl ‚ÒÂı x ∈ X.ëËÏÏÂÚ˘ÌÓ ÏÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚ÓåÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó (X,d) ̇Á˚‚‡ÂÚÒfl ÒËÏÏÂÚ˘Ì˚Ï, ÂÒÎË ‰ÎflÔÓËÁ‚ÓθÌÓÈ ÚÓ˜ÍË p ∈ X ÒÛ˘ÂÒÚ‚ÛÂÚ ÒËÏÏÂÚËfl ÓÚÌÓÒËÚÂθÌÓ ‰‡ÌÌÓÈ ÚÓ˜ÍË,38ó‡ÒÚ¸ I. å‡ÚÂχÚË͇ ‡ÒÒÚÓflÌËÈÚ.Â.
Ú‡ÍÓ ÔÂÂÏ¢ÂÌË f p ˝ÚÓ„Ó ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡, ˜ÚÓ fp (fp (x)) = x ‰Îfl‚ÒÂı x ∈ X, Ë fl‚ÎflÂÚÒfl ËÁÓÎËÓ‚‡ÌÌÓÈ ÙËÍÒËÓ‚‡ÌÌÓÈ ÚÓ˜ÍÓÈ fp .é‰ÌÓÓ‰ÌÓ ÏÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚ÓåÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó (X,d) ̇Á˚‚‡ÂÚÒfl Ó ‰ Ì Ó Ó ‰ Ì ˚ Ï (ËÎË ÒËθÌÓÚ‡ÌÁËÚË‚Ì˚Ï), ÂÒÎË ‰Îfl ͇ʉ˚ı ‰‚Ûı ÍÓ̘Ì˚ı ËÁÓÏÂÚ˘ÂÒÍËı ÔÓ‰ÏÌÓÊÂÒÚ‚Y = {y 1 , ..., ym} Ë Z = {z1 , ..., zm} ÏÌÓÊÂÒÚ‚‡ ï ÒÛ˘ÂÒÚ‚ÛÂÚ ÔÂÂÏ¢ÂÌË ï , ÓÚÓ·‡Ê‡˛˘Â Y ‚ Z. åÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó Ì‡Á˚‚‡ÂÚÒfl ÚӘ˜ÌÓ-Ó‰ÌÓÓ‰Ì˚Ï,ÂÒÎË ‰Îfl β·˚ı ‰‚Ûı Â„Ó ÚÓ˜ÂÍ ÒÛ˘ÂÒÚ‚ÛÂÚ ÔÂÂÏ¢ÂÌËÂ, ÓÚÓ·‡Ê‡˛˘Â ӉÌÛ ËÁ˝ÚËı ÚÓ˜ÂÍ ‚ ‰Û„Û˛. Ç Ó·˘ÂÏ ÒÎÛ˜‡Â Ó‰ÌÓÓ‰ÌÓ ÔÓÒÚ‡ÌÒÚ‚Ó ÂÒÚ¸ ÏÌÓÊÂÒÚ‚Ó ‚ÒÓ˜ÂÚ‡ÌËË Ò ‰‡ÌÌÓÈ Ú‡ÌÁËÚË‚ÌÓÈ „ÛÔÔÓÈ ÒËÏÏÂÚËÈ.åÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó (X,d) ̇Á˚‚‡ÂÚÒfl ÏÂÚ˘ÂÒÍË Ó‰ÌÓÓ‰Ì˚Ï É˛Ì·‡ÛÏ–äÂÎÎË ÏÂÚ˘ÂÒÍËÏ ÔÓÒÚ‡ÌÒÚ‚ÓÏ, ÂÒÎË {d(x, z) : z ∈ X} = {d(y, z) : z ∈ X} ‰Îflβ·˚ı x, y ∈ X.ê‡ÒÚflÊÂÌËÂèÛÒÚ¸ (X,d) – ÔÓËÁ‚ÓθÌÓ ÏÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó Ë r – ‰ÂÈÒÚ‚ËÚÂθÌÓÂÔÓÎÓÊËÚÂθÌÓ ˜ËÒÎÓ.
îÛÌ͈Ëfl f : X → X ̇Á˚‚‡ÂÚÒfl ‡ÒÚflÊÂÌËÂÏ, ÂÒÎË d(f(x),f(y)) = rd(x,y) ‰Îfl β·˚ı x, y ∈ X.åÂÚ˘ÂÒÍÓ ÔÂÓ·‡ÁÓ‚‡ÌËÂåÂÚ˘ÂÒÍÓ ÔÂÓ·‡ÁÓ‚‡ÌË ÂÒÚ¸ ‡ÒÒÚÓflÌËÂ, ÔÓÎÛ˜‡ÂÏÓÂ Í‡Í ÙÛÌ͈Ëfl ‰‡ÌÌÓÈÏÂÚËÍË (ÒÏ. „Î. 4).ÉÓÏÂÓÏÓÙÌ˚ ÏÂÚ˘ÂÒÍË ÔÓÒÚ‡ÌÒÚ‚‡Ñ‚‡ ÏÂÚ˘ÂÒÍËı ÔÓÒÚ‡ÌÒÚ‚‡ (X, dï) Ë (Y, dY) ̇Á˚‚‡˛ÚÒfl „ÓÏÂÓÏÓÙÌ˚ÏË (ËÎËÚÓÔÓÎӄ˘ÂÒÍË ËÁÓÏÓÙÌ˚ÏË), ÂÒÎË ÒÛ˘ÂÒÚ‚ÛÂÚ „ÓÏÂÓÏÓÙËÁÏ ËÁ ï ‚ Y, Ú.Â. ڇ͇fl·ËÂÍÚ˂̇fl ÙÛÌ͈Ëfl f : X → Y, ˜ÚÓ f Ë f–1 ÌÂÔÂ˚‚Ì˚ (ÔÓÓ·‡Á Í‡Ê‰Ó„Ó ÓÚÍ˚ÚÓ„ÓÏÌÓÊÂÒÚ‚‡ ‚ Y fl‚ÎflÂÚÒfl ÓÚÍ˚Ú˚Ï ‚ ï).Ñ‚‡ ÏÂÚ˘ÂÒÍËı ÔÓÒÚ‡ÌÒÚ‚‡ (X, dï) Ë (Y, dY ) ̇Á˚‚‡˛ÚÒfl ‡‚ÌÓÏÂÌÓËÁÓÏÓÙÌ˚ÏË, ÂÒÎË ÒÛ˘ÂÒÚ‚ÛÂÚ Ú‡Í‡fl ·ËÂÍÚ˂̇fl ÙÛÌ͈Ëfl f : X → Y, ˜ÚÓ f Ë f–1fl‚Îfl˛ÚÒfl ‡‚ÌÓÏÂÌÓ ÌÂÔÂ˚‚Ì˚ÏË ÙÛÌ͈ËflÏË.
(îÛÌ͈Ëfl g ·Û‰ÂÚ ‡‚ÌÓÏÂÌÓÌÂÔÂ˚‚ÌÓÈ, ÂÒÎË ‰Îfl β·Ó„Ó ε > 0 ÒÛ˘ÂÒÚ‚ÛÂÚ Ú‡ÍÓ δ > 0, ˜ÚÓ ‰Îfl β·˚ıx, y ∈ X ËÁ ̇‚ÂÌÒÚ‚‡ dX(x,y) < δ ÒΉÛÂÚ Ì‡‚ÂÌÒÚ‚Ó dY(g(x), f(y)) < ε; ÌÂÔÂ˚‚̇flÙÛÌ͈Ëfl fl‚ÎflÂÚÒfl ‡‚ÌÓÏÂÌÓ ÌÂÔÂ˚‚ÌÓÈ, ÂÒÎË ÔÓÒÚ‡ÌÒÚ‚Ó ï ÍÓÏÔ‡ÍÚÌÓ.)äÓÌÙÓÏÌÓ ÏÂÚ˘ÂÒÍÓ ÓÚÓ·‡ÊÂÌËÂèÛÒÚ¸ (X, dï) Ë (Y, dY) – ÏÂÚ˘ÂÒÍË ÔÓÒÚ‡ÌÒÚ‚‡. éÚÓ·‡ÊÂÌË f : X → ẎÁ˚‚‡ÂÚÒfl ÍÓÌÙÓÏÌ˚Ï ÏÂÚ˘ÂÒÍËÏ ÓÚÓ·‡ÊÂÌËÂÏ, ÂÒÎË ‰Îfl β·˚ı x ∈ Xd ( f ( x ), f ( y))ÒÛ˘ÂÒÚ‚ÛÂÚ Ô‰ÂÎ lim Y, ÍÓÚÓ˚È fl‚ÎflÂÚÒfl ÍÓ̘Ì˚Ï Ë ÔÓÎÓÊËy→ xd ( x, y)ÚÂθÌ˚Ï.䂇ÁËÍÓÌÙÓÏÌÓ ÏÂÚ˘ÂÒÍÓ ÓÚÓ·‡ÊÂÌËÂèÛÒÚ¸ (X, d ï) Ë (Y, dY) – ÏÂÚ˘ÂÒÍË ÔÓÒÚ‡ÌÒÚ‚‡. ÉÓÏÂÓÏÓÙËÁÏ f : X → ẎÁ˚‚‡ÂÚÒfl Í‚‡ÁËÍÓÌÙÓÏÌ˚Ï (ËÎË ë-Í‚‡ÁËÍÓÌÙÓÏÌ˚Ï) ÏÂÚ˘ÂÒÍËÏ ÓÚÓ·‡ÊÂÌËÂÏ, ÂÒÎË ÒÛ˘ÂÒÚ‚ÛÂÚ ÍÓÌÒÚ‡ÌÚ‡ ë, ڇ͇fl ˜ÚÓ ÒÓÓÚÌÓ¯ÂÌËÂlim supr→0max{dY ( f ( x ), f ( y)) : d X ( x, y) ≤ r}≤Cmin{dY ( f ( x ), f ( y)) : d X ( x, y) ≥ r}39É·‚‡ 1. 鷢ˠÓÔ‰ÂÎÂÌËfl‚˚ÔÓÎÌflÂÚÒfl ‰Îfl Í‡Ê‰Ó„Ó x ∈ X.
ç‡ËÏÂ̸¯‡fl ڇ͇fl ÍÓÌÒÚ‡ÌÚ‡ ë ̇Á˚‚‡ÂÚÒflÍÓÌÙÓÏÌ˚Ï ‡ÒÚflÊÂÌËÂÏ.䂇ÁËÍÓÌÙÓÏÌÓ ÓÚÓ·‡ÊÂÌË f ̇Á˚‚‡ÂÚÒfl Í‚‡ÁËÒËÏÏÂÚ˘Ì˚Ï, ÂÒÎË, ÍÓÏÂÚÓ„Ó, ÒÛ˘ÂÒÚ‚ÛÂÚ ÍÓÌÒÚ‡ÌÚ‡ ë', ڇ͇fl ˜ÚÓmax{dY ( f ( x ), f ( y)) : d X ( x, y) ≤ r}≤Cmin{dY ( f ( x ), f ( y)) : d X ( x, y) ≥ r}‚˚ÔÓÎÌflÂÚÒfl ‰Îfl ‚ÒÂı x ∈ X Ë ‚ÒÂı ÔÓÎÓÊËÚÂθÌ˚ı r.äÓÌÙÓÏ̇fl ‡ÁÏÂÌÓÒÚ¸ ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ (X,d) (è‡ÌÒ˛, 1989)fl‚ÎflÂÚÒfl ËÌÙËÏÛÏÓÏ ‡ÁÏÂÌÓÒÚË ï‡ÛÒ‰ÓÙ‡ ÔÓ ‚ÒÂÏ Í‚‡ÁËÍÓÌÙÓÏÌ˚ÏÓÚÓ·‡ÊÂÌËflÏ ÔÓÒÚ‡ÌÒÚ‚‡ (X,d) ‚ ÌÂÍÓÚÓÓ ÏÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó.ãËÔ¯ËˆÂ‚Ó ÓÚÓ·‡ÊÂÌËÂèÛÒÚ¸ Ò – ÔÓÎÓÊËÚÂθ̇fl ÍÓÌÒÚ‡ÌÚ‡. ÑÎfl ÏÂÚ˘ÂÒÍËı ÔÓÒÚ‡ÌÒÚ‚ (X, dï) Ë(Y, d Y) ÙÛÌ͈Ëfl f : X → Y ̇Á˚‚‡ÂÚÒfl ÎËԯˈ‚˚Ï ÓÚÓ·‡ÊÂÌËÂÏ (ËÎËÒ-ÎËԯˈ‚˚Ï, ÂÒÎË ÌÂÓ·ıÓ‰ËÏÓ ÛÔÓÏflÌÛÚ¸ ÔÓÒÚÓflÌÌÛ˛ Ò), ÂÒÎË Ì‡‚ÂÌÒÚ‚ÓdY ( f ( x ), f ( y)) ≤ cd X ( x, y)‚˚ÔÓÎÌflÂÚÒfl ‰Îfl ‚ÒÂı x, y ∈ X.Ò-ÎËÔ¯ËˆÂ‚Ó ÓÚÓ·‡ÊÂÌË ̇Á˚‚‡ÂÚÒfl ÛÍÓ‡˜Ë‚‡˛˘ËÏ, ÂÒÎË Ò = 1, Ë ÒÊËχ˛˘ËÏ, ÂÒÎË Ò < 1.ÅË-ÎËÔ¯ËˆÂ‚Ó ÓÚÓ·‡ÊÂÌËÂèÛÒÚ¸ Ò > 1 – ÔÓÎÓÊËÚÂθ̇fl ÍÓÌÒÚ‡ÌÚ‡.
íÓ„‰‡ ‰Îfl ÏÂÚ˘ÂÒÍËı ÔÓÒÚ‡ÌÒÚ‚ (X,dï) Ë (Y, dY) ÙÛÌ͈Ëfl f : X → Y ̇Á˚‚‡ÂÚÒfl ·Ë-ÎËԯˈ‚˚Ï ÓÚÓ·‡ÊÂÌËÂÏ (ËÎËÒ-·Ë-ÎËԯˈ‚˚Ï ÓÚÓ·‡ÊÂÌËÂÏ, Ò - ‚ÎÓÊÂÌËÂÏ), ÂÒÎË ÒÛ˘ÂÒÚ‚ÛÂÚ Ú‡ÍÓ ÔÓÎÓÊËÚÂθÌÓ ˜ËÒÎÓ r, ˜ÚÓ ‰Îfl β·˚ı x, y ∈ X ËÏÂ˛Ú ÏÂÒÚÓ Ì‡‚ÂÌÒÚ‚‡rd X ( x, y) ≤ dY ( f ( x ), f ( y)) ≤ crd X ( x, y).ä‡Ê‰Ó ·Ë-ÎËÔ¯ËˆÂ‚Ó ÓÚÓ·‡ÊÂÌË fl‚ÎflÂÚÒfl Í‚‡ÁËÍÓÌÙÓÏÌ˚Ï ÏÂÚ˘ÂÒÍËÏÓÚÓ·‡ÊÂÌËÂÏ.ç‡ËÏÂ̸¯‡fl ÍÓÌÒÚ‡ÌÚ‡ Ò, ‰Îfl ÍÓÚÓÓÈ f fl‚ÎflÂÚÒfl Ò-·Ë-ÎËԯˈ‚˚Ï ÓÚÓ·‡ÊÂÌËÂÏ, ̇Á˚‚‡ÂÚÒfl ËÒ͇ÊÂÌËÂÏ f.ÅÛ„‡ÈÌ ‰Ó͇Á‡Î, ˜ÚÓ Í‡Ê‰Ó k-ÚӘ˜ÌÓ ÏÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó Ò-‚ÎÓÊËÏÓ ‚ÌÂÍÓÚÓÓ ‚ÍÎË‰Ó‚Ó ÔÓÒÚ‡ÌÒÚ‚Ó Ò ËÒ͇ÊÂÌËÂÏ O(lnk).
àÒ͇ÊÂÌË ÉÓÏÓ‚‡ ‰ÎflÍË‚˚ı Ô‰ÒÚ‡‚ÎflÂÚ ÒÓ·ÓÈ Ï‡ÍÒËχθÌÓ ÓÚÌÓ¯ÂÌË ‰ÎËÌ˚ ‰Û„Ë Í ‰ÎËÌ ıÓ‰˚.Ñ‚Â ÏÂÚËÍË d1 Ë d2 ̇ ï ̇Á˚‚‡˛ÚÒfl ·Ë-ÎËÔ¯ËˆÂ‚Ó ˝Í‚Ë‚‡ÎÂÌÚÌ˚ÏË, ÂÒÎËÒÛ˘ÂÒÚ‚Û˛Ú Ú‡ÍË ÔÓÎÓÊËÚÂθÌ˚ ÍÓÌÒÚ‡ÌÚ˚ Ò Ë ë, ˜ÚÓ Ì‡‚ÂÌÒÚ‚Ócd1(x,y) ≤ d2 (x,y) ≤ Cd 1 (x,y) ‚˚ÔÓÎÌflÂÚÒfl ‰Îfl ‚ÒÂı x, y ∈ X, Ú.Â. ÚÓʉÂÒÚ‚ÂÌÌÓÂÓÚÓ·‡ÊÂÌË ÂÒÚ¸ ·Ë-ÎËÔ¯ËˆÂ‚Ó ÓÚÓ·‡ÊÂÌË (X, d1 ) ‚ (X, d2 ).ꇂÌÓÏÂÌÓ ÏÂÚ˘ÂÒÍÓ ÓÚÓ·‡ÊÂÌËÂèÛÒÚ¸ (X, dï) Ë (Y, dY) – ÏÂÚ˘ÂÒÍË ÔÓÒÚ‡ÌÒÚ‚‡. îÛÌ͈Ëfl f : X → Y ̇Á˚‚‡ÂÚÒfl‡‚ÌÓÏÂÌ˚Ï ÏÂÚ˘ÂÒÍËÏ ÓÚÓ·‡ÊÂÌËÂÏ, ÂÒÎË ÒÛ˘ÂÒÚ‚Û˛Ú Ú‡ÍË ‰‚ÂÌÂÛ·˚‚‡˛˘Ë ÙÛÌ͈ËË g1 Ë g2 ËÁ ≥ 0 ‚ Ò·fl Ò lim gi (r ) = ∞ ‰Îfl i = 1, 2, ˜ÚÓr →∞̇‚ÂÌÒÚ‚‡g1 ( d X ( x, y) ≤ dY ( f ( x ), f ( y)) ≤ g2 ( d X ( x, y))ËÏÂ˛Ú ÏÂÒÚÓ ‰Îfl ‚ÒÂı x, y ∈ X.40ó‡ÒÚ¸ I.