Сидел я значит на курсе Coursera. Курс был нацелен на начинающих по Java, и в одном из видеоуроков была поднята тема 7 Steps for Solving Problems.

Я с чистой совестью прослушал видеоурок, подумал про себя, пошло это дело далеко и надолго.

Остальная часть курса прошла легко, ненапряжно. Но, на одном из предметов в универе, а именно по так называемому «Научному программированию» появилось следующее задание:

Решить систему линейных уравнений $$, используя следующее разложение матрицы $$:

$$

где $$ — нижняя треугольная матрица, а $$ — верхняя треугольная матрица.

Тема линейной алгебры, которую мы проходили на 1 курсе. Говоря откровенно — я помнил общие принципы операций с матрицами, векторами, ну и святая святых — Метод Гаусса. Если пораскинуть мозгами, то никакого LU-разложения мы не изучали, зато метод «загугли» всегда выручает. Выручал, до этого момента.

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

1. Опиши проблему руками

Все, чего тебе не хватает в жизни, это понять — в чем реально заключается проблема. Давай возьмем в пример вышеописанную задачку и распишем ее на листочке. По-хорошему, должны выполняться следующие условия для существования матриц $$ и $$:

— должна существовать матрица, обратная $$, то бишь $$;
— все главные миноры не должны быть вырожденным, то бишь $$

Отлично, значит нам как минимум нужна «проверка на дурака», потому что обязательно найдутся умники, которые захотят использовать неподходящую для нас матрицу. Но это пока опустим.

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

2. Опиши то, что ты сделал

Возьмем в пример матрицу

$$

Теперь применим к ней наш метод Гаусса и избавимся от лишних элементов в 3 строке, засчет вычитания из нее первой строки, умноженной на отношение первого элемента 3 строки на первый элемент 1 строки:

$$

Теперь, избавимся от второго элемента 3 строки похожим действием:

$$

В результате получим матрицу

$$

А теперь, найденные нами коэффициенты (результат отношения элементов $$) возьмем за значения матрицы $$, и получим

$$

Проглядывается шаблон, не правда ли?

3. Нахождение шаблонов

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

Итак, исходя из примера, можно сформировать следующий алгоритм/шаблон решения:

1. Задаем квадратную матрицу $$-го порядка;
2. Задаем матрицу $$, где $$ — единичная матрица $$-го порядка;
3. Задаем матрицу $$;
4. Циклично применяем к матрицам следующие последовательные преобразование, при условии, что $$

$$

При $$, получаем:

$$

4. Проверка шаблона/алгоритма

Есть алгоритм — есть миллионы матриц для его проверки! За этот шаблон можете не переживать, он очевидно верен (лично проверено на самых невырожденных из возможных матриц). Но помните: поспешишь — людей насмешишь. Так что всегда проверяйте созданные вами шаблоны, чтобы дальше не скакать как чертям окаянным к самому началу.

5. Перевод алгоритма в код

Очевидный шаг, все нужное зачастую уже есть в синтаксисе языка, а если нет — никто не мешает вам создать классы и функции для решения этой проблемы, алгоритм то у вас есть. Так как я реализовывал этот алгоритм в рамках образовательной университетской программы, то и для реализации я мог использовать только Octave, поэтому весь код я представляю вам именно в его синтаксисе (он крайне схож с Python, поэтому для форматирования я буду использовать его подсветку):

A = input("Enter the matrix A: ")
numOfRows = size(A, 1)
numOfCols = size(A, 2)

if numOfRows ~= numOfCols
    disp("Wrong matrix.")
else
    n = numOfCols
    disp("----------------")
    L = eye(3)
    disp("Making U = A")
    U = A
    disp("----------------")

    for i=2:n
        disp("Step "), disp(i-1)
        for j=1:i-1
            L(i,j) = U(i,j)/U(j,j)
            U(i,:) = U(i,:) - U(j,:)*L(i,j)
        end
        disp("----------------")
    end

    disp("Check the answer of L*U: "), disp(L*U)
end

6. Поиск неудачных тестов

Всегда надо пытаться «сломать» свой код. Здесь (очевидно) нет полной «защиты от дурака», но я взял за основу допущение, что вводиться будет изначально верная матрица.

На этом шаге вы должны найти все возможные ошибки, неточности вашего кода, в следствие чего может выявиться и необъективность вами построенного алгоритма. Поэтому здесь вы должны опробовать как можно больше упущений, которые могли быть допущены.

7. Дебаг неудачных тестов

Самый логичный, и наверное, ожидаемый из шагов. Код должен быть продебажен, а алгоритм исправлен. Здесь особо больше ничего не добавишь.

Заключение

Могу сказать, что вряд ли я когда-нибудь бы серьезно отнесся к этому подходу решения проблем, если бы не мое сонное состояние. Но стоит обратить внимание на этот метод — он краток, и вся его трудоемкость заключяется лишь в том, что его надо использовать.

Примечание

Спасибо учебникам линейной алгебры за материал для решения задачи.