Category: история

Контора пишет

Когда мне было двадцать или чуть более лет, я написал первую свою "научную статью".
Ну как написал, сначала действительно - написал. Руками (точнее - рукой).
После одобрения шефом отдали мои каракули машинистке.
Она (спасибо тебе, Надежда) как смогла напечатала текст в 5 экземплярах, оставляя пустое место для формул (хотя, может, формулы на отдельных листах прикладывались, а в тексте просто сноски - не помню уже подробности).
Я во все эти распечатанные листы вписал формулы - да-да, во все 5 экземпляров писал формулы, матерясь, конечно, при этом, и давая себе слово, что в следующей статье формул не будет. (Ха, а кто-то не ленился еще рисунки и графики вставлять. Я сразу понял - не мое).

Статья прошла ученый семинар (я выступал и меня строили,- правильно в целом), и была отправлена в журнал (а когда отправлял потом работы за бугор, то еще и к цензорам ездил за визой - что, мол, нет в статье секретных сведений). В советских журналах была очередь - полгода, год, полтора. Переписка с рецензентами, ага, - обычной почтой. В итоге статья вышла где-то через год ее написания, и я был горд и счастлив, впервые увидев свое имя напечатанным в журнале.
Статью прочитало три человека (я, шеф и рецензент), откликов и комментариев не было.

Это я все к чему. Сегодня я выложил на Хабре 3-ю часть своей околонаучной саги о спектрах данных. Написал (набил текст) ее за один день, с формулами и одной картинкой. За 3 часа ее просмотрело 1,5 тыс. человек, кому-то даже понравилось. Спасибо тебе, прогресс.

Суть спектрального разложения матриц (графов)

Смысл нахождения собственных значений и векторов матриц (вычисления спектра матрицы) от меня долго ускользал. Но поскольку недавно я вроде бы все-таки смог ухватить его за хвост, то постараюсь изложить, пока помню.
Для наглядности возьмем какую-либо прикладную матрицу, - например, матрицу расстояний между городами (ненаправленный граф). В общем случае расстояния между городами могут быть любыми,- в том смысле, что берем расстояния "реально дорожные" (фрактальные), а не просто "расстояния по прямой".Collapse )
На описанном свойстве спектров основан спектральный анализ данных электро(резисто)метрии для получение срезов по глубине. Значение резистенсов с глубиной падает, поэтому базовые (собственные) резистенсы можно связать с глубиной. Чем меньше собственное значение - тем глубже слой, который данное значение характеризует.

Эффективные сопротивления графа - что, как и почему

Это итоговый пост о свойствах потоков и потенциалов в симметричных графах. Даже более конкретно - о матрице эффективных сопротивлений (резистивных расстояний, резистенсов) R.
Сведем кратко и воедино все, что смогли уяснить, и закроем тему.
Collapse )

Расчет резистивной матрицы в направленном графе

Нарисовалась одна проблема. По старой традиции - описываю, поскольку пепельницы уже вытряхивал, по колесам стучал. Если кратко - то нужен метод быстрого расчета матрицы резистивных расстояний для направленных графов (ключевое слово - быстрого).
Collapse )

Биграммы - это матрицы потоков,

а не матрицы смежности.
Что-то я не сразу это сообразил, поэтому зафиксирую.
Матрицу потоков можно распознать по равенству втекающего и вытекающего потока - то есть сумма по i-й колонке и i-й строке равны (если не равны - то биграмма вычислена неверно).

Таким образом, обработка любой входящей последовательности (в биграммах - последовательности букв) через накапливание количества встретившихся пар дает на выходе матрицу потоков.

Хорошая новость в том, что для матрицы потоков собственный вектор потенциалов считается намного проще, чем для матрицы смежности. - Вектор потенциалов определяется сверткой (суммой) по колонкам (или строкам). Матрица смежности для биграмм - это матрица потоков, колонки (строки) которой нормированы на значения вектора (частоты) - то есть стандартная марковская матрица переходов.

Фиксируем итоги по потокам и потенциалам

Матрица Кирхгофа (МК) - интересная штука. Странно, что ей уделяется мало внимания в стандартных курсах про графы. Наверное, считается, что она имеет больше отношения к электрическим сетям (раз типа Кирхгоф). На самом же деле - это фундаментальная вещь, которую полезно знать всем, кто каким-то образом связан с бинарными отношениями (а в стандартной голове бинарные отношения и электрические сети никак не связаны).
Я исследовал МК на предмет применимости к прямой и обратной задаче электротомографии. Зафиксирую то, что обнаружил (и не встретил у других).
Collapse )

Маленькое открытие - расчет потенциалов по матрице Кирхгофа

Еще один важный полученный результат - это способ расчета потенциалов в графе, потоки которого сбалансированы. Данному расчету в этом журнале уделено несколько постов - как считать точно, как приближенно...
Оказывается, можно (и нужно) использовать матрицу Кирхгофа, которая в данном случае строится на матрице проводимостей орграфа.
Collapse )

3-й закон Кирхгофа

Продвижение по теме потоков в почти симметричных графах продолжается.
Было (кратко, ес-но) изучено состояние дел в теории электрических сетей (по работам "Random Walks and Electrical Networks", "Inverse Problems for Electrical Networks"). Обнаружено, что люди почему-то не используют мой прием - задание разности потенциалов в сети через введение асимметричного ребра. А мучаются со стандартной задачей Дирихле - то есть через задание краевых условий на потенциалы. Зря. Теряется общность и простота "графического" подхода. (Правда меня немного смущает, что такую асимметрию можно задать, просто воткнув в землю диод, без всяких источников тока).

Что еще понято. Наконец-то постиг, как доказывается пресловутый инвариант для графа любой размерности. Для этого пришлось, правда, ввести 3-й закон Кирхгофа )). Ну и наиболее интересная часть - продвинулся в решении обратной задачи для электрических сетей - вычисление проводимостей графа на основе известных разностей потенциала. Поскольку материала много, то разобью на несколько постов.

Начнем с Кирхгофа.
Collapse )

Электротомография

Возня с графами дала новые идеи к старой задаче - обратная задачи электроразведки (электротомография по современному). Зафиксирую то, что нарыл из "графического" подхода. Как на самом деле нужно мерять и обрабатывать результаты.
Collapse )