Идеи реализации

Комплексные числа являются чрезвычайно важным обобщением понятия вещественного числа. Комплексным числом называется выражение вида z = x + y , где x и y — вещественные числа, а мнимая единица, некий символ, смысл которого вскоре прояснится. Числа x и y называются вещественной и мнимой частями.

Два комплексных числа можно складывать и вычитать как обычные двучлены, приводя подобные слагаемые, содержащие мнимую единицу. Пусть z = x + y и w = u + v . Тогда z ± w = x ± u + y ± v .

Для комплексных чисел определяется также операция умножения. Два числа умножаются так же, как двучлены, только встретившиеся в полученном выражении квадраты мнимой единицы заменяются на 1 : z w = x + y u + v = x u + x v + y u + 2 y v = x u y v + x v + y u .

Чтобы определить деление комплексных чисел, преобразуем дробь z w , умножив её числитель и знаменатель на число w ¯ = u v , отличающееся от знаменателя знаком мнимой части (такое число называется комплексно-сопряжённым): z w = z w ¯ w w ¯ = x + y u v u + v u v = x u + y v + y u x v u 2 + v 2 . Конечно же знаменатель должен быть ненулевым.

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

Комплексное число z = x + y принято отождествлять с точкой на плоскости, заданной своими декартовыми координатами x y . Поэтому множество комплексных чисел называют также комплексной плоскостью. Попытки распространить арифметические операции с обычными свойствами на трёхмерное пространство не привели к успеху. Единственное обобщение комплексных чисел на многомерный случай более-менее удаётся для множества четвёрок вещественных чисел, но там, увы, умножение лишается переместительного закона. Полученное множество называется телом кватернионов. Мы упомянули о кватернионах только для того, чтобы подчеркнуть уникальность конструкции комплексных чисел.

Модуль (называемый ещё абсолютной величиной) комплексного числа z = x + y по определению равен z z ¯ = x 2 + y 2 . Геометрический смысл модуля — расстояние от комплексного числа до нуля на комплексной плоскости. Расстояние между двумя комплексными числами z и w, как нетрудно видеть, равно z w . Определение модуля комплексного числа находится в полном согласии с определением модуля вещественного: при y = 0 получаем z = x = x 2 .

Основная теорема алгебры утверждает, что любой многочлен n-й степени с комплексными коэффициентами имеет комплексный корень, то есть существует комплексное решение уравнения a 0 + a 1 z + a 2 z 2 + + a n z n = 0 . Как следствие, многочлен всегда раскладывается в произведение линейных двучленов: a 0 + a 1 z + a 2 z 2 + + a n z n = a n z λ 1 z λ 2 z λ n , где λ k — корни уравнения. Аналогичное свойство (оно называется алгебраической замкнутостью) не выполняется для вещественных чисел. Не каждый многочлен с вещественными коэффициентами раскладывается на линейные множители. Простейший пример даёт многочлен 1 + z 2 , не имеющий вещественных корней из-за своей положительности. В то же время комплексные корни этого многочлена равны λ 1 , 2 = ± , поэтому 1 + z 2 = z z + . Именно алгебраическая замкнутость делает комплексные числа совершенно незаменимой частью математики.

Рассмотрим квадратный многочлен f z = w + z 2 , где z w . Положим z 0 = 0 . Тогда с помощью многочлена можно построить рекуррентную последовательность комплексных чисел z k + 1 = f z k . Будем называть эту последовательность орбитой нуля (термин «орбита» уже употреблялся в главе 15. «Десятичные дроби»). Нуля — потому что первый элемент последовательности ноль. Итак, вот первые несколько элементов орбиты: 0 w w + w 2 w + w 2 + 2 w 3 + w 4 .

Орбиту будем называть ограниченной, если все её элементы остаются на комплексной плоскости внутри некоторого круга с центром в нуле. Остальные орбиты назовём, естественно, неограниченными. И сама орбита нуля, и её ограниченность зависят от числа w, и множество Мандельброта определяется как множество тех чисел w, для которых ограниченность имеет место.

Перед нами встала задача определения ограниченности или неограниченности орбиты нуля для каждого заданного комплексного числа w. К сожалению, выписать общую формулу для элементов орбиты z k = f f f f 0 , где k значков f, не представляется возможным. Так что вряд ли аналитические методы помогут решить задачу. Для наших целей практически неограниченной можно считать орбиту, которая, рано или поздно, вырывается за пределы некоторого круга с центром в нуле достаточно большого радиуса R, скажем, равного 100. Но это может произойти рано, поздно, или же не произойти никогда. Тем не менее, алгоритм, выясняющий ограниченность орбиты, должен быть в какой-то момент остановлен. Поэтому нам потребуется сформулировать ещё одно условие, при выполнении которого орбиту можно считать практически ограниченной.

Вспомним о том, что точное представление вещественного числа в компьютере невозможно, и что количество представимых чисел конечно, хоть и очень велико. Из-за этого конечным будет и количество комплексных чисел внутри некоторого круга. Любая орбита при вычислении на компьютере обязательно зациклится, поскольку её элементы принадлежат конечному множеству и вычисляются рекуррентно. Было бы разумно считать орбиту практически ограниченной, если она зациклится раньше, чем покинет большой круг. Определить момент зацикливания помогает метод Флойда, подробно изложенный нами в разделе «Метод Черепахи и Зайца». Напомним, что ключевым обстоятельством, на котором основан метод Флойда, является выполнение равенства z k = z 2 k для некоторого k, то есть совпадение элементов «черепашьей» последовательности z k и «заячьей» z 2 k . Как только равенство выполнится, можно утверждать, что Черепаха уже вступила в цикл.

Беда в том, что в самом худшем случае зацикливание может наступить не раньше, чем орбита (Черепаха) посетит по очереди все до единого комплексные числа, попавшие в круг, а их очень и очень много. Мы не будем дожидаться, когда наступит момент зацикливания. Вместо этого станем считать орбиту практически зациклившейся, если черепашья последовательность достаточно сблизится с заячьей, то есть выполнится условие z k z 2 k < 1 R .

Итак, если выяснится, что последовательность практически зациклена, прежде чем обнаружится её практическая неограниченность, она объявляется практически ограниченной.

Теперь для каждого комплексного числа w можно определить, принадлежит ли оно множеству Мандельброта, или нет. Можно раскрасить точки множества в чёрный цвет, оставив все остальные белыми. Но изображение на рисунке 48.1. «Множество Мандельброта» цветное. Каков же смысл этой раскраски? Само множество Мандельброта изображено красным цветом. Внешность множества зелёная. Чем быстрее орбита нуля покинет круг радиуса R, тем светлее зелёная раскраска точки w. Внутри множества, вопреки традиции, мы также использовали различные степени интенсивности красного цвета, чтобы получить более выразительное изображение. Красный цвет тем светлее, чем быстрее обнаруживается ограниченность орбиты.

Таким образом, для каждого числа w можно вычислять цвет, которым оно будет закрашено на изображении, как число I из отрезка 0 1 . Это будет интенсивность красного (для точек из множества) или зелёного (для всех остальных) цветов на картинке. В любом случае найденное число должно зависеть от количества n элементов орбиты, найденных до момента обнаружения её ограниченности или неограниченности, и убывать с ростом этого количества. Чтобы различать эти случаи ограниченности или неограниченности, припишем знак этому числу: для ограниченных орбит пусть это будет минус. Цвет, красный или зелёный, выбирается в зависимости от знака.

Мы экспериментировали, подбирая зависимость интенсивности цвета от n, и остановились на I n = ± 1 n 4 + 1 (прибавление единицы под знаком корня исключает деление на ноль при n = 0 , а деление на 4 осветляет картинку). Нетрудно понять, что самые большие значения n, и, следовательно, самые тёмные цвета обнаружатся вблизи границы множества Мандельброта, где орбита проводит особенно много времени, решая либо устремиться к бесконечности, либо остаться ограниченной. Рисунки 48.1 и 48.2 подтверждают эту мысль.

Рисунок 48.1 демонстрирует важное свойство множества Мандельброта — его симметричность относительно вещественной оси. Иными словами, при комплексном сопряжении множество переходит само в себя. Это легко доказать. Заметим, что ограниченность или неограниченность орбиты не изменится, если каждый её элемент подвергнуть комплексному сопряжению. Осталось доказать, что орбиты нуля для w и w ¯ симметричны друг другу при отражении относительно вещественной оси. Для w получаем орбиту O w = 0 w w + w 2 w + w 2 + 2 w 3 + w 4 , а для w ¯ O w ¯ = 0 w ¯ w ¯ + w ¯ 2 w ¯ + w ¯ 2 + 2 w ¯ 3 + w ¯ 4 . Поскольку все элементы орбиты O w являются многочленами от w с вещественными коэффициентами, остаётся доказать, что комплексное сопряжение можно выносить за знак таких многочленов: g w ¯ = g w ¯ . Последний факт вытекает из двух легко проверяемых свойств комплексного сопряжения: p ± q ¯ = p ¯ ± q ¯ и p q ¯ = p ¯ q ¯ для любых комплексных чисел p и q. Итак, O w ¯ = O w ¯ , что и требовалось доказать.

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

Информатика-54© А. Н. Швец