Мир фракталов

Матрица статей Список статей Всячина Контакты

Произведение Кронекера

Пусть $A$ — матрица размером $m \times n$ , $B$ — матрица размером $p \times q$ . Произведением Кронекера матриц $A$ и $B$ называется блочная матрица $A \otimes B$ размера $mp \times nq$ вида

$\left( \begin{array}{ccc} a_{11} B & \cdots & a_{1n}B \\ \vdots & \ddots & \vdots \\ a_{m1} B & \cdots & a_{mn} B \end{array} \right).$ Другими словами, элементы матрицы $C = A \otimes B$ вычисляются по формуле: $c_{p(i - 1) + u, q(j - 1) + v} = a_{ij} \cdot b_{uv}.$ Напишем функцию для вычисления произведения Кронекера матриц.

public static int[][] product(int[][] A, int[][] B) {
    int m = A.length;
    int n = A[0].length;
    int p = B.length;
    int q = B[0].length;
    int r = m * p;
    int s = n * q;
    int C[][] = new int[r][s];
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int u = 0; u < p; ++u) {
                for (int v = 0; v < q; ++v) {
                    C[i * p + u][j * q + v] = A[i][j] * B[u][v];
                }
            }
        }
    }
    return C;
}

Произведение Кронекера обладает многими хорошими свойствами, здесь же отметим только ассоциативность, и что матрица $(1)$ является нейтральным элементом относительно этой операции.

Определим $n$ -ую степень Кронекера матрицы $A$ , где $n$ — натуральное число, по формуле:

$A^n = \left\{ \begin{matrix}{ll} (1), & n = 0, \\ A^{n - 1} \otimes A, & n > 0. \end{matrix} \right.$

public static int[][] power(int[][] A, int n) {
    if (n == 0) {
        return new int[][] {{1}};
    }
    return product(power(A, n - 1), A);
}

Теперь по матрице $A$ построим изображение следующим очевидным образом: если $a_{ij}$ не равно нулю, то пиксель с координатами $(j, i)$ покрасим в чёрный цвет, иначе же покрасим в белый.

public static Image draw(int[][] A)
{
    int r = A.length;
    int s = A[0].length;
    BufferedImage image = 
	new BufferedImage(s, r, BufferedImage.TYPE_INT_RGB);
    Graphics2D graphics = image.createGraphics();
    graphics.setColor(Color.WHITE);
    graphics.fill(new Rectangle2D.Double(0, 0, s, r));
    graphics.setColor(Color.BLACK);
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < s; ++j) {
            if (A[i][j] != 0) {
                graphics.fillRect(j, i, 1, 1);
            }
        }
    }
    return image;
}

Пусть матрица $S$ имеет вид

$S = \left( \begin{array}{ccc} 1 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 1 \end{array} \right).$ Рассмотрим степень Кронекера $S^n$ матрицы $S$ . Несложно заметить, что получится $n$ -ое приближение ковра Серпинского.

public static Image drawSierpinskiCarpet(int n) {
    return draw(
            power(new int[][]
            {{1, 1, 1},
             {1, 0, 1},
             {1, 1, 1}},
            n));
}

public static Image image;

public static void main(String[] args) {
    image = drawSierpinskiCarpet(6);

    int width = image.getWidth(null);
    int height = image.getHeight(null);
    JFrame frame = new JFrame();
    frame.addNotify();
    frame.setSize(frame.getInsets().left +
            frame.getInsets().right + width,
            frame.getInsets().top +
            frame.getInsets().bottom + height);
    frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

    frame.add(new JPanel() {
        @Override
        public void paintComponent(Graphics g) {
            Graphics2D G = (Graphics2D) g;
            if (image != null) {
                G.drawImage(image, 0, 0, null);
            }
        }

    });
    frame.setVisible(true);
}

Рассматривая степени матрицы

$D = \left( \begin{array}{ccc} 1 & 0 & 1 \\ 0 & 0 & 0 \\ 1 & 0 & 1 \end{array} \right),$ получим пыль Кантора.

public static Image drawCantorDust(int n) {
    return draw(
        power(new int[][]
           {{1, 0, 1},
            {0, 0, 0},
            {1, 0, 1}},
            n));
}

public static Image drawBoxFractal(int n) {
    return draw(
        power(new int[][]
            {{1, 0, 1},
             {0, 1, 0},
             {1, 0, 1}},
            n));
}

public static Image drawSierpinskiTriangle(int n) {
    return draw(
        power(new int[][]
            {{1, 0},
             {1, 1}},
            n));
}

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

public static Image draw(int[][] A, int m) {
    Color[] colors = new Color[] {Color.WHITE, Color.RED, Color.GREEN, 
    	Color.BLUE, Color.ORANGE, Color.BLACK, Color.MAGENTA /*, ...*/};
    int r = A.length;
    int s = A[0].length;
    BufferedImage image = 
	new BufferedImage(s, r, BufferedImage.TYPE_INT_RGB);
    Graphics2D graphics = image.createGraphics();
    graphics.setColor(Color.WHITE);
    graphics.fill(new Rectangle2D.Double(0, 0, s, r));
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < s; ++j) {
            graphics.setColor(colors[A[i][j] % m]);
            graphics.fillRect(j, i, 1, 1);
        }
    }
    return image;
}

Построим модифицированный ковёр Серпинского.

public static Image drawModifiedSierpinskiCarpet(int n, int m) {
    return draw(
            power(new int[][]
            {{1, 1, 1},
             {1, 2, 1},
             {1, 1, 1}},
            n), m);
}

Ниже приведены избражения для $m = 3$ и $m = 4$ .

public static Image drawYetAnotherModifiedSierpinskiCarpet(int n, int m) {
    return draw(
            power(new int[][]
            {{1, 1, 1, 1, 1},
             {1, 2, 2, 2, 1},
             {1, 2, 0, 2, 1},
             {1, 2, 2, 2, 1},
             {1, 1, 1, 1, 1}},
            n), m);
}

Ниже приведены избражения для $m = 3$ и $m = 5$ .

public static Image drawModifiedSierpinskiTriangle(int n, int m) {
    return draw(
            power(new int[][]
            {{1, 0, 0},
             {1, 1, 0},
             {1, 2, 1}},
            n), m);
}

Аналогично, $m = 3$ и $m = 5$ .

Сделаем фрактальный смайлик.

public static Image drawSmile(int n)
{
    return draw(
            power(new int[][]
            {{0, 1, 1, 1, 1, 1, 0},
             {1, 1, 2, 1, 2, 1, 1},
             {1, 1, 2, 1, 2, 1, 1},
             {1, 1, 1, 1, 1, 1, 1},
             {1, 2, 1, 1, 1, 2, 1},
             {1, 1, 2, 2, 2, 1, 1},
             {0, 1, 1, 1, 1, 1, 0}},
            n), 3);
}

Ещё несколько картикок, без каких-либо комментариев.

Ещё одним способом построения фракталов, очень близким к рассмотренному, являются двумерные переписывающие системы. Идея следующая: пусть задана матрица $G$ с элементами из множества $X$ и набор матриц $R(x)$ , $x \in X$ . На первом шаге в матрице $G$ каждый элемент $g_{ij}$ заменим на блок $R(g_{ij})$ . К полученной матрице, на втором шаге применим ту же процедуру, и т. д.

Заметим, что если $X = \{0, 1\}$ , $G = (1)$ и $R(0)$ ялвяется нулевой матрицей, то в результате применения $n$ шагов переписывающей системы получится $n$ -ая степень Кронекера матрицы $R(1)$ . То есть, например, ковру Серпинского соответствует система

$\left{ 0 \to \left( \begin{array}{ccc} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array} \right), 1 \to \left( \begin{array}{ccc} 1 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 1 \end{array} \right) \right},$ $G = (1)$ .

Более интересным примером является ковёр Хафермана.

$\left{ 0 \to \left( \begin{array}{ccc} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{array} \right), 1 \to \left( \begin{array}{ccc} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{array} \right) \right},$ $G = (1)$ .

package ru.xaoc.fractalworld.rewritingsystems;

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Image;
import java.awt.geom.Rectangle2D;
import java.awt.image.BufferedImage;
import javax.swing.JFrame;
import javax.swing.JPanel;

public class Main {
    public static int[][] rewrite(int[][] A, int[][][] Rs) {
        int r = A.length;
        int s = A[0].length;
        int p = Rs[0].length;
        int q = Rs[0][0].length;

        int[][] C = new int[r * p][s * q];
        for (int i = 0; i < r; ++i) {
            for (int j = 0; j < s; ++j) {
                for (int m = 0; m < p; ++m) {
                    for (int n = 0; n < q; ++n) {
                        C[i * p + m][j * q + n] = Rs[A[i][j]][m][n];
                    }
                }
            }
        }
        return C;
    }

    public static int[][] system(int[][] G, int[][][] Rs, int n) {
        if (n == 0) {
            return G;
        }
        return system(rewrite(G, Rs), Rs, n - 1);
    }

    public static Image draw(int[][] A) {
        int r = A.length;
        int s = A[0].length;
        BufferedImage image = 
		new BufferedImage(s, r, BufferedImage.TYPE_INT_RGB);
        Graphics2D graphics = image.createGraphics();
        graphics.setColor(Color.WHITE);
        graphics.fill(new Rectangle2D.Double(0, 0, s, r));
        graphics.setColor(Color.BLACK);
        for (int i = 0; i < r; ++i) {
            for (int j = 0; j < s; ++j) {
                if (A[i][j] != 0) {
                    graphics.fillRect(j, i, 1, 1);
                }
            }
        }
        return image;
    }


    private static Image drawSierpinskiCarpet(int n) {
        return draw(
                system(new int[][] {{1}},
                new int[][][] {{
                    {0, 0, 0},
                    {0, 0, 0},
                    {0, 0, 0}},

                   {{1, 1, 1},
                    {1, 0, 1},
                    {1, 1, 1}}
            }, n));
    }


    private static Image drawHafermanCarpet(int n) {
        return draw(
                system(new int[][] {{1}},
                new int[][][] {{
                    {1, 1, 1},
                    {1, 1, 1},
                    {1, 1, 1}},

                   {{0, 1, 0},
                    {1, 0, 1},
                    {0, 1, 0}}
            }, n));
    }

    public static Image image;
    public static void main(String[] args) {
        //image = drawSierpinskiCarpet(6);
        image = drawHafermanCarpet(6);

        int width = image.getWidth(null);
        int height = image.getHeight(null);
        JFrame frame = new JFrame();
        frame.addNotify();
        frame.setSize(frame.getInsets().left +
                frame.getInsets().right + width,
                frame.getInsets().top +
                frame.getInsets().bottom + height);
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

        frame.add(new JPanel() {
            @Override
            public void paintComponent(Graphics g) {
                Graphics2D G = (Graphics2D) g;
                if (image != null) {
                    G.drawImage(image, 0, 0, null);
                }
            }

        });
        frame.setVisible(true);
    }
}

Ещё несколько картинок без комменариев.

Смотрите также:

Ссылки:

Газале М. ГНОМОН. От фараонов до фракталов. Москва-Ижевск: Институт компьютерных исследований, 2002, 209—231.
Box Fractal — from Wolfram MathWorld ,
Cantor Dust — from Wolfram MathWorld ,
Cantor Square Fractal — from Wolfram MathWorld ,
Sierpiński Carpet — from Wolfram MathWorld ,
String Rewriting System — from Wolfram MathWorld ,
Kronecker Product — from Wolfram MathWorld ,