Самый важный алгоритм в истории [Veritasium]
[музыка] Это видео посвящено важнейшему алгоритму всех времен — быстрому преобразованию Фурье. Мы пользуемся им всё время, даже когда просто смотрим видео, как вы сейчас. На нём работают радары, гидролокаторы, 5G, Wi-Fi. В общем, везде, где нужно обрабатывать сигналы с большой вероятностью, используется быстрое преобразование Фурье. И вдобавок, его открыли учёные, которые хотели научиться обнаруживать тайные испытания ядерного оружия. Произойдя открытие чуть раньше, возможно, никакой гонки ядерных вооружений не было бы. Я всегда думал, что ядерная гонка была неизбежна, как только США сбросили атомные бомбы на Хиросиму и Нагасаки — у других держав не оставалось выбора, кроме как развивать эту отрасль.
Но вдруг стало ясно, что ядерное оружие всё меняет. Бомба, сброшенная на Хиросиму, выпустила в тысячу раз больше энергии, чем мощнейшие традиционные взрывчатые устройства. Несложно понять беспокойство других стран: в конце войны Канада и Великобритания запросили переговоры, на которых хотели обсудить, что делать с ядерным оружием. Что меня удивило, США с готовностью откликнулись. Штаты понимали, что недолго продержатся единственными обладателями подобного вооружения и пообещали списать все ядерные оружия, если другие страны обязуются никогда его не производить.
На обсуждение был вынесен так называемый план Баруха, и заключался он в том, чтобы добыча, обогащение и использование в мирных целях, например выработка атомной энергии, контролировались международным органом. Но Советский Союз отверг это предложение, усмотрев в нём очередную попытку США удержать лидерство в этой области. И тогда началась гонка ядерного вооружения. Создание нового оружия требовало основательных испытаний, и большая часть из них проходила в удалённых местах, вроде Арктики или южной части Тихого океана. Штаты устроили испытательный полигон в Неваде — радиоактивную пыль разносила по всей стране. Так что, если не считать Японию, большая часть пострадавших от американского ядерного оружия — это сами американцы.
США быстро перешли к термоядерному оружию, которое благодаря использованию реакции деления и синтеза одновременно давало ещё больше. Это был скачок, сравнимый с приходом от традиционного оружия к первым атомным бомбам. Мощность снова увеличилась в тысячу раз — уничтожение всей жизни на земле теперь оказалось в сфере технических возможностей. В 1954 году США испытали у атолла Бикини в Тихом океане новый вариант термоядерного оружия. Топливом выступил дитерий лития. Ожидалось, что устройство под кодовым названием "креветка" будет соответствовать 6 миллионам тонн тротиловому эквиваленту. Штаты просчитались: взрыв был в 2,5 раза мощнее. Дело в неучтённых реакциях с лития-7.
В результате образовалось больше радиоактивных продуктов и разнесло их дальше, чем планировалось. Население ближайших атолов эвакуировали только через три дня. К тому времени состояние людей уже заметно ухудшилось. Восточнее 23 человека с японского рыболовецкого судна накрыло шквалом радиоактивного пепла. К вечеру у них развелась острая лучевая болезнь, один из рыбаков через полгода умер от осложнений. После этого общественность активно выступила против испытаний ядерного оружия. В 1950-х появился Pacific — в нём зашифрованы обозначения семафора для английских букв N и D, означающих ядерное разоружение.
Некоторые государства начали призывать к полному запрету испытаний ядерного оружия для всех стран-ядерных держав. Этот призыв восприняли всерьёз и активно принимали участие во встречах с очень прямолинейными названиями, например, Конференция по прекращению ядерных испытаний, которая прошла в 1958 в Женеве. Чтобы показать серьёзность своих намерений, государства прекратили все испытания на время переговоров. Так, 1959 год надолго стал единственным годом, в котором не взорвался ни один ядерный заряд.
Но с достижением внятного полноценного договора возникает проблема: как узнать, что другая страна честно соблюдает его условия? США боялись, что Советский Союз втайне продолжит испытания и обгонит штаты в технологии. СССР опасался того же со стороны США. Со взаимным недоверием решили разобраться на совещании экспертов по изучению возможности обнаружения нарушений возможного соглашения о приостановке ядерных испытаний. Честное слово, так оно и называлось, я ничего не придумал. Засечь испытания в атмосфере было довольно просто: радиоактивные изотопы рассеиваются в воздухе, и заметить их можно с расстояния в тысячи километров. При испытаниях под водой взрыв, так сказать, звучит характерным образом, и поэтому его довольно просто засечь с помощью гидрофонов.
Но узнать с большого расстояния о том, что где-то проводятся подземные испытания, — сложная задача, радиация наружу практически не выходит. А опускать наблюдателей СССР не согласился — власти считали, что это шпионаж. По этой причине в 1963 году, когда договоренности так или иначе удалось достичь, был подписан только частичный запрет на испытания в воде, в атмосфере и в космосе, то есть там, где их легко отслеживать. Тесты под землёй не попали под запрет исключительно потому, что за ними, по сути, было невозможно следить. Но к тому времени учёные уже взялись за поиски надёжного способа определить, где проходят подземные испытания.
После встречи в Женеве американские и советские исследователи объединились в рабочую группу. Они надеялись, что сейсмометры за пределами страны, где проводятся испытания, смогут улавливать слабые толчки от взрывов под землёй. Но было не ясно, как отличить вибрации от ядерных испытаний от обычных подземных толчков. Каждый день в мире происходит около 300 землетрясений магнитудой 3 и выше.
Другой момент: контроль испытаний также помогает следить за успехами соседей, определяя мощность взрыва. Однако показания сейсмометров зависят не только от мощности заряда, но и от глубины, на которой его устанавливают. Чем глубже находится бомба, тем менее мощной она покажется. Так что учёным нужно было придумать, как отличить землетрясение от ядерных испытаний и точно определить мощность и глубину заряда. Конечно, вся эта информация присутствует в данных сейсмометра, но считать её просто, посмотрев на неровные зигзаги, невозможно. Нужно было знать, сколько и каких частот там сошлось.
А значит, стоило прибегнуть к преобразованию Фурье. Преобразование Фурье — это способ разложить сигнал на составляющие его чёткие синусоиды с определённой амплитудой и чистотой. Может показаться, что это какое-то волшебство; сумма нескольких синусоидальных волн может быть сколь угодно сложной и непохожей на компоненты, которые её составляют. Есть довольно красивые варианты того, как представить себе преобразование Фурье — ищите видео на канале Trible. Но в этом видео будем придерживаться более практического подхода.
Если нужно узнать, сколько определённой синусоиды в каком-то сигнале, нужно умножить на неё этот сигнал в каждой точке, потом сложить площади областей под кривой. Вот простой пример: допустим, наш сигнал — это обычная синусоида определённой частоты, но мы об этом не знаем. Поэтому нам надо выяснить, из каких синусоидальных волн состоит сигнал.
Если умножить его на синусоидальную волну произвольной частоты, получится независимые друг от друга волны. Можно найти участки, где волны имеют как одинаковый знак плюс или минус, так и противоположный. Получается, если волны перемножить, область над осью X окажется равна области под ней. При сложении они дадут 0. А значит, синусоида этой чистоты не является компонентом изучаемого сигнала.
То же самое будет верно почти для всех частот, которые мы решим проверить, если рассматриваем достаточно долгий участок. Единственным исключением будет частота волны, которая точно соответствует частоте сигнала. В этом случае волны будут коррелированы, их произведения всегда будут положительными, как и область под кривой, и всё это покажет нам, что эта волна является компонентом сигнала. Это упражнение срабатывает и когда сигнал состоит из нескольких частот — синусоиды, входящие в сигнал, будут коррелированными с ним, то есть при вычислении покажут значения, отличные от нуля, а площадь области говорит об относительной амплитуде синусоиды в составе сигнала.
Повторяем для каждой частоты синусы данных волн и получаем спектр частот, который показывает, какие частоты есть в сигнале и в какой пропорции. Пока мы говорили только о синусах и дальних волнах. Но если в сигнале есть волны с функцией косинуса, даже если мы умножим их на синусоидальные с абсолютно той же частотой, площадь под волной будет равняться нулю. Получается, что для каждой частоты придётся выполнять умножение на синус и косинус и потом искать амплитуду для этого и другого. Соотношение амплитуд указывает на фазу сигнала, то есть показывает, насколько он сдвинут влево или вправо.
Амплитуду синусов и косинусов можно вычислять по отдельности или по формуле Эйлера: она использует единый экспоненциальный множитель. Тогда вещественная часть суммы будет амплитудой косинуса, а мнимая — амплитудой синуса. В составе американской делегации на встрече в Женеве присутствовали физик Ричард Гарвин и математик Джон Кьюки. У них в советской делегации возник спор о том, чьи сейсмометры лучше. Гарвин устроил тест аппаратом из обеих стран, запустил симуляцию их работы на компьютере. В итоге все согласились, что особой разницы не было.
Проблема с тем, чтобы зафиксировать испытания, заключалась не в точности приборов, а в необходимости обширных вычислений, необходимых для того, чтобы расшифровывать сигналы с помощью преобразования Фурье. Вот пример сигнала сейсмометра и его Фурье-образ. Пока что мои объяснения подразумевали, что сигналы — это некие бесконечные непрерывные волны. Если к ним применять преобразование Фурье, то мы получим бесконечный непрерывный спектр частот. Но в реальном мире сигнал выглядит не так: они конечные, состоят из отдельных фрагментов или точек данных.
Показания сейсмографа выглядят как непрерывная линия, но это не значит, что он регистрирует данные с бесконечной точностью. Всегда есть некая фрагментарность. Получается, у нас есть имена отдельные точки данных, и к ним нельзя применить преобразование Фурье в его идеальном виде. Нужно другое — так называемое дискретное преобразование Фурье. Одна из его особенностей заключается в том, что спектр частот тоже дискретный и конечный.
Можно представить, что, например, частоты попадают в некоторое конечное число интервалов, их количество и размер соответствует по количеству и плотности точек в исходном сигнале. Например, чем дальше точки друг от друга, тем ниже максимальная частота, которую можно измерить — просто данные расположены недостаточно близко, чтобы зафиксировать колебания высокой частоты. Чем короче сигнал, тем сложнее отделить друг от друга похожие частоты, что снижает частотное разрешение. Чем короче сигнал, тем шире получаются интервалы.
Самая низкая не нулевая частота, которую можно измерить, — это та, у которой период равен длительности сигнала, а интервалы с более высокими частотами просто кратны наиболее низкой частоте, то есть они умещаются в исходный сигнал 2, 3, 4 раза и так далее. Общее число интервалов равно числу фрагментов сигнала. Если в сигнале 8 точек, то при преобразовании будет 8 интервалов от 0 до основной частоты, умноженной на 7.
Давайте разберемся на примере. Итак, у нас есть сигнал из восьми составляющих. Значит, при дискретном преобразовании Фурье будет 8 столбиков чистоты. Первый соответствует нулевой частоте, по сути такое бывает, если сигнал целиком смещён относительно оси X, по аналогии, например, с постоянным током смещения. Каждая точка умножается на 1. Затем они складываются — в данном случае получается 0. [музыка]
Следующий интервал соответствует частоте, которая вмещается один раз в продолжительный сигнал; в нашем случае это один герц. Умножаем каждую точку на синус и косинус этой частоты, а потом по отдельности их складываем. Для синуса получается 0, для косинуса — 4. Затем повторяем процесс для двух, трёх и так до семи и завершаем дискретное преобразование Фурье для этого довольно простого сигнала. В целом, такой метод отлично работает везде, где нужно дискретное преобразование Фурье. Но вот проблема: слишком уж много требуется вычислений, чтобы провести такое преобразование — нужно умножить N точек данных на N волн разных частот, N в квадрате комплексных умножений.
Если составляющих 8, то выглядит не страшно. Но что если их миллион? Тогда потребуется миллион в квадрате или триллион вычислительных операций. Со скоростью компьютеров начала 60-х, на это ушли бы три года всего на одно такое преобразование. Конечно, вряд ли на одной сейсмическое событие придётся сигнал из миллиона точек, но на анализ десятков событий, которые регистрируются на сотнях сейсмометров, ушло бы слишком много времени. И это обстоятельство заставило учёных искать другие варианты.
Решение нашли в 1963 году на встрече консультативного совета по науке при президенте США Джоне Кеннеди. Помимо прочих, встретились те самые физики-математики, которые ездили в Женеву. Хотя обсуждались вопросы государственной важности, программа Аполлона и убежища от радиоактивной пыли, встреча, вероятно, была довольно скучной. Гарвин говорил, что Тьюки всё время что-то рисовал. Однако на самом деле математик ломал голову над дискретным преобразованием Фурье.
В конце встречи Гарвин спросил Тьюки, что получилось. К своему удивлению он узнал, что теперь у них есть способ провести преобразование с наименьшим количеством вычислений, и теперь подсчёты, которые могли занять больше трёх лет, можно завершать всего за 35 минут. Нам этот способ известен как быстрое преобразование Фурье. И вот как оно происходит. Вспомним пример сигнала из восьми точек. Каждую из них нужно умножить на 8 волн разных частот.
Для простоты здесь у нас только косинусы. Логично, что нам должно понадобиться 8 на 8, то есть 64 операции комплексного умножения. Но синусоиды периодичны, и волны разных частот будут накладываться предсказуемым образом. Например, в середине все нечётные частоты будут иметь одно и то же значение, как собственно и все чётные. Получается, что вместо 8 раз мы можем произвести умножение всего дважды, и такая ситуация повторяется для других точек.
В общем счётом, вместо 64 вычислений нужно всего 24. Может быть, такое сокращение операций не впечатляет. Но на самом деле мы перешли от формулы N в квадрате по основанию 2, и чем больше N, тем заметнее, сколько мы экономим. Для расшифровки сигнала из тысячи точек потребуется в 100 раз меньше вычислений, а для миллиона количество необходимых вычислений сократится в 50 тысяч раз.
Но как узнать, какие из операций можно пропустить? Возьмём наши данные и выберем из них точки с чётными и нечётными номерами. Их всё равно придётся умножать на каждую из восьми частот, но теперь давайте взглянем только на чётные точки и сравним первые четыре частоты с четырьмя последними. Мы увидим, что на всех точках данных значение двух синусоид совпадает. То же самое мы заметим, если будем сравнивать нечётные индексные точки, с одним отличием: значение одной синусоиды противоположно по знаку значению другой.
В общем случае они связаны через комплексное число. Но что это всё означает? Что теперь нет необходимости проводить вычисления для последних четырёх частот. Если посчитать суммы для чётных и нечётных низких частот, те же значения можно использовать для более высоких, и вот количество вычислений сократилось вдвое. Но этого нам мало. Как же получить сокращение N на логарифм N по основанию 2? В общем-то, мы опять делим точки данных на чётные и нечётные снова и снова, пока не сведём их до отдельных точек данных. Каждый раз мы полагаемся на симметрию синусоидальных функций, и за счёт этого урезаем количество необходимых вычислений в два раза.
Таким образом, быстрое преобразование Фурье сокращает вычисления с N в квадрате до N логарифм N. Сейчас практически всегда, при необходимости использовать преобразование Фурье, используют именно такой вариант. Гарвин попросил исследователя из IBM Джеймса Кули запрограммировать компьютер на быстрое преобразование Фурье. Однако про отслеживание советских подземных ядерных испытаний тогда уточнять не стал. Алгоритм ему нужен был, чтобы определять спины атомов гелия-3 в кристаллах. Кули и Тьюки опубликовали алгоритм в работе 65 года, и он тут же стал популярным.
Однако к заключению договора о запрете ядерных испытаний учёные опоздали. К тому моменту Великобритания, Франция и Китай стали ядерными державами, наряду с Советским Союзом и США. А частичный запрет, вместо того чтобы остановить гонку ядерных вооружений, просто загнал испытания под землю. Логика была такой: если испытания можно проводить только под землёй, лучше поднажать, чтобы не отстать от других стран с ядерным оружием. Начиная с 1963 года, были проведены полторы тысячи испытаний — это примерно по одному в неделю в течение 30 лет.
Из-за сложившейся ситуации ядерных бомб произвели возмутительно много; запасы достигли пика в середине 80-х. Тогда в мире было 70 тысяч ядерных боеголовок. За 20 век США и СССР каждая потратила на них по 10 триллионов долларов с поправкой на инфляцию. Если бы учёные в начале 60-х были уверены, что смогут с расстояния обнаруживать испытания ядерного оружия, то можно было бы ввести полный запрет на них и зарубить ядерную гонку на корню. О том, насколько это реалистично, побеседовал с самим Ричардом Гарвином:
"Звучит, конечно, заманчиво — да, ещё как! Возможно, помогло бы, и всё было бы иначе. Но для этого открыть быстрое преобразование Фурье надо было раньше". Что интересно, так всё и было. Просто об этом забыли.
Ещё в 1805 году математик Карл Фридрих Гаусс исследовал недавно обнаруженные астероиды Палладу, Цереру и Юнону, чтобы высчитать орбиту Юноны. Гауссу пришлось разработать новый подход к гармоническому анализу, который остался в его записях, но никогда не использовался. То случайное озарение Гаус никогда не публиковал, но сейчас мы можем понять, что он открыл дискретное преобразование Фурье раньше публикации самого Жана Батиста Фурье в 1807-м, а быстрое преобразование Фурье Гаус открыл на полтора века раньше, чем Кули и Тьюки. Его открытие осталось без внимания, потому что впервые появилась публикация только после его смерти в третьем томе собрания работ. К тому же описано без привычной нотации версии латинского 19 века.
Как думаете, что случилось бы, если бы Гаус понял, насколько важное открытие он совершил, и опубликовал в таком виде, чтобы оно было понятно другим? С развитой сетью сейсмометров, современными компьютерами и быстрым преобразованием Фурье, мы можем фиксировать подземные толчки магнитудой 3 балла, которые соответствуют взрыву в 1 килотонну или около того почти в любой точке мира. После работы Кули и Тьюки быстрое преобразование Фурье тут же подхватили; оно легло в основу большинства алгоритмов сжатия, например, тех, которые позволяют смотреть видео и слушать меня. Вот как оно помогает сжать изображение.
Берём значение яркости пикселя в каждом ряду изображения и проводим быстрое преобразование Фурье — по сути, мы определяем, какие частоты присутствуют в значениях яркости каждом ряду картинки. Яркость здесь отражает величину каждого компонента частоты, а цвет — фазу, то есть сдвиг частоты влево или вправо. Затем быстрое преобразование Фурье проводится для столбиков пикселей. Не важно, что делать сначала — ряды или столбики, главное провести преобразование по двум измерениям.
Почти со всеми изображениями оказывается, что многие значения в преобразовании близки к нулю. Для наглядности я взял логарифм преобразования. Но если бы я этого не сделал, то было бы видно, что большинство значений, особенно ближе к краям, очень малы — они соответствуют большим частотам. Это значит, что из преобразованного изображения можно выбросить довольно много информации, скажем, 99 процентов. Но когда мы инвертируем всё это, то получается вполне сносная копия исходной картинки.
На компьютере большинство изображений хранится в таком виде, как двумерное быстрое преобразование Фурье. А когда вы решаете на них посмотреть, компьютер их инвертирует. Способов применения быстрого преобразования Фурье просто тьма: решение дифференциальных уравнений, радары, гидролокаторы, изучение структуры кристаллов, Wi-Fi, 5G — до практически везде, где нужна обработка сигнала. Именно поэтому математик Гилберт Стринг назвал быстрое преобразование Фурье важнейшим численным алгоритмом нашего времени. Если бы больше людей узнало о его открытии Гауссом, оно, вероятно, преобразовало бы наш мир ещё сильнее.