Log in

   

Ґуґл і теорема Банаха про нерухому точку

Рекомендовані Ґуґл і теорема Банаха про нерухому точку Ґуґл і теорема Банаха про нерухому точку

Один з найвидатніших математиків 20-го століття Стефан Банах народився 125 років тому і у вересні у Львові відбудеться міжнародна конференція, присвячена цій даті. Результати Банаха в основному належали до функціонального аналізу та суміжних областей математики. Їх значення з роками лише зростає, що можна продемонструвати на прикладі теореми про нерухому точку для стискуючих відображень.

Нагадаю формулювання цієї теореми. Відображення f метричного простору (X,d) у себе називають стискуючим, якщо існує число c, 0 < c < 1, таке що d(f(x),f(y)) ≤ d(x,y) для всіх точок x,y простору X

Теорема (С. Банах). Для кожного стискуючого відображення f повного метричного простору X у себе існує нерухома точка, тобто така точка x*, що f(x*)=x*.

У математиці теорему Банаха застосовують, наприклад, до доведення існування і єдиності розв'язку звичайних диференціальних рівнянь. Одним з найважливіших застосувань є доведення існування локально самоподібних множин (фракталів), які в свою чергу використовуються для компресії зображень.

Тут ми розглянемо, як теорему Банаха можна застосувати  до задачі рангування веб-сторінок. Саме таке рангування нам пропонує відомий пошуковик Google. Авторами створенного біля 20 років тому алгоритму є С. Брін та Л. Пейдж. Отже, всю мережу зобразимо як орієнтований граф, у якому веб-сторінки є вершинами, а стрілка з вершини i у вершину j веде лише якщо існує лінк з i в j. У свою чергу, цей граф можна зобразити як матрицю H (гіперлінкову матрицю): її елементи Hij  задаються умовою:

Hij  = 0, якщо нема стрілки з  вершини i у вершину j,

Hij = 1/Oi, де Oi  - число стрілок, що виходять з вершини i (це число відмінне від нуля).

Модель телепортації основана на припущенні, що мандрівник по мережі йде за структурою мережі, але в якийсь момент робить випадковий стрибок на іншу сторінку, не пов’язану з попередніми. Гіперлінкова матриця H при цьому заміняється на матрицю G (Ґуґл-матрицю), що задається рівнянням (PageRank рівняння):

(тут n – число всіх веб-сторінок, а m – параметр, що відповідає за випадкове перескакування зі сторінки на сторінку, 0 < m < 1; усі елементи (n x n)-матриці рівні одиниці).

Тепер побудуємо метричний простір, де все відбуватиметься. Нехай X – множина всіх n-векторів (точніше, вектор-стовпчиків) з невід’ємними координатами, а метрика на X породжена l1-нормою. Іншими словами, це метрика таксиста (або, ще інакше, метрика Мангетена):

Тепер нескладно перевірити, що відображення, яке ставить у відповідність кожному елементові x простору X елемент Gx, коректно означене (тобто знову одержуємо елемент простору X) і стискуюче. За теоремою Банаха про нерухому точку існує вектор x* простору X, для якого x*=Gx*. Цей вектор і задає рангування веб-сторінок (за величинами координат). 

Перевага теореми Банаха над алгебраїчними методами (можна застосувати теорему Перрона-Фробеніуса для знаходження x*) полягає в тому, що застосування ітерацій

x, Gx, GGx, GGGx, …

дає швидке наближення до шуканого вектора (для практики цього достатньо).

Недавно алгоритм Бріна-Пейджа запропонували застосувати майже без змін до рангування наукових журналів. При цьому роль лінка відіграє перехід від журналу до журналу за цитуваннями. Не вдаючись у деталі, зауважу лише, що чомусь далеко не всі хочуть вірити у наукометричні показники для журналів, публікацій у них і, як наслідок, авторів, хоча всі (принаймні з тих, кого я знаю) беззастережно користуються ґуґлом, довіряючи йому всеможливі пошуки. 

На доступному з мережі матеріалі.

Рисунок автора.

 

М.М. Зарічний

доктор фізико-математичних наук, професор кафедри геометрії і топології

Сайт: www.franko.lviv.ua/faculty/mechmat/Departments/Topology/zarichnyi.html
  • Коментарі не знайдено

Залиште свій коментар

Post comment as a guest

0
«
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
»

Наші контакти


Ідея, веб-дизайн і т.д.:

Олег Романів
oromaniv at franko.lviv.ua