Укрощение бесконечности. История математики от первых чисел до теории хаоса - Йен Стюарт

Вторым важным приложением численных методов стало решение дифференциальных уравнений. Предположим, мы решаем уравнение

и нам дано, что x = x0 в момент времени t = 0. Согласно Эйлеру, простейший способ – аппроксимация dx/dt с помощью

где ε очень мала. Тогда аппроксимация дифференциального уравнения принимает вид:

Начиная с x(0) = x0 мы последовательно найдем значения f(ε), f(2ε), f(3ε) – в общем, f(nε) для любого целого n > 0. Обычное значение ε, скажем, 10–6. Миллион итераций (повторов) формулы покажет x(1), следующий миллион x(2) и т. д. Для современных компьютеров миллион вычислений – пустяк, и это уже вполне практичный метод.

Однако метод Эйлера оказался слишком прост для ученых, и пришлось изобрести множество улучшений. Самым известным стал целый класс методов Рунге – Кутты, названный в честь немецких математиков Карла Рунге и Мартина Кутты, впервые предложивших их в 1901 г. Один из них, так называемый метод Рунге – Кутты четвертого порядка, широко используется в инженерии, прикладной и теоретической математике.

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

Ньютоновский расчет площади под гиперболой

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

Используя симплектические интеграторы, Джек Уиздом, Жак Ласкар и другие ученые показали, что в длительных временных периодах поведение Солнечной системы хаотично, Уран и Нептун были гораздо ближе к Солнцу, чем сейчас, и в настоящее время орбита Меркурия смещается в сторону Венеры, так что одна из этих планет в итоге может оказаться вытесненной из Солнечной системы. Только симлектические интеграторы дают нам достаточную уверенность в том, что результаты для такого длительного промежутка точны.

Компьютеры помогают в математике, но и использование математики помогает компьютерам. Математические принципы были важным условием для работы ранних вычислительных устройств – как в плане доказательства самой концепции, так и в конструировании самих машин.

Все современные цифровые компьютеры работают на двоичной системе, где числа представляются последовательностями всего двух цифр: 0 и 1. Главное преимущество двоичной системы – в ее соответствии переключению: 0 – выключено, 1 – включено. Или 0 – нет напряжения, а 1 – это пять вольт или какой-то иной вариант, используемый в схеме проектирования. Символы 0 и 1 могут также быть интерпретированы в рамках математической логики как значения истинности: 0 означает ложь, 1 – истина. Иными словами, компьютеры могут выполнять логические вычисления так же, как и арифметические. Конечно, логические операции здесь базовые, а арифметические можно рассматривать как последствия логических. Алгебраический подход Буля к математике 0 и 1, изложенный в его «Исследовании законов мышления», обеспечивает эффективный формализм для логики компьютерных вычислений. Поисковые системы интернета выполняют булевы логические запросы: ищут ответы, определенные некоторой комбинацией логических критериев, такие как «содержит слово “кошка”, но не содержит слово “собака”».

Математика внесла свой вклад в компьютерную науку, но и компьютерная наука подтолкнула к открытию поразительной новой математики. По одному из определений, алгоритм – систематический порядок действий для решения задачи. Это слово восходит к арабскому ученому Аль-Хорезми. И тут возникает любопытный вопрос: как зависит время работы алгоритма от объема вводимых данных?

Например, алгоритм Евклида для нахождения наибольшего общего делителя двух целых чисел m и n, где m ≤ n, выглядит так.

• Разделить n на m и получить остаток r.

• Если r = 0, то наибольший общий делитель – m: СТОП.

• Если r > 0, тогда заменить n на m, а m на r и вернуться к началу.

Можно показать, что если m включает d десятичных цифр (мера объема вводимых данных для алгоритма), то алгоритм останавливается максимум после 5d шагов. Это значит, в частности, что если нам заданы два числа с 1000 цифр, то мы можем вычислить их наибольший общий делитель не более чем за 5000 шагов – на что современному компьютеру требуется доля секунды.