Я сидел на курсе Coursera. Курс был ориентирован на новичков в Java, и в одном из видеоуроков эта тема поднималась.
7 шагов для решения проблем .
Я с чистой совестью прослушал видеоурок, подумал про себя, дело это зашло далеко и надолго.
Остальная часть курса прошла легко и без стресса.
Но, по одному из предметов в университете, а именно по так называемому «Научному программированию», появилась следующая задача:
Решите систему линейных уравненийТема линейной алгебры, которую мы проходили на 1 курсе.
, используя следующее матричное разложение
:
Где
представляет собой нижнюю треугольную матрицу, а
— верхняя треугольная матрица.
Честно говоря, я вспомнил общие принципы работы с матрицами, векторами и святая святых — метод Гаусса.
Если вдуматься, никакого LU-разложения мы не изучали, но метод «Гугла» всегда выручает. Выручал меня, до этого момента.
Я нашел общий алгоритм поиска матриц 
И 
, но в полтретьего ночи никакое количество кофе не дало мне возможности реализовать это как следует (учитывая, что мы там кодировали на Октаве).
В результате я психанул и решил послушать умно названную поговорку.
1. Опишите проблему руками
Все, что вам нужно в жизни, — это понять, в чем настоящая проблема.Давайте возьмем описанную выше проблему в качестве примера и запишем ее на листе бумаги.
По-хорошему, для существования матриц должны выполняться следующие условия
И
:
— должна быть обратная матрица 
, Я имею в виду 
;
- все крупные миноры не должны быть вырожденными, т.е.
Отлично, значит, нам как минимум нужна «проверка на дурака», потому что обязательно найдутся умные люди, которые захотят использовать неподходящую для нас матрицу.
Но давайте пока оставим это в стороне.
Задача нам ясна: найти матрицы
И
, который будет соответствовать вышеуказанным условиям.
Если вы попытаетесь найти решения в Google, вам вряд ли удастся правильно реализовать алгоритм с первого раза (если вы плохо разбираетесь в линейной алгебре).
Пройдя массу попыток, мы, скорее всего, выработаем какую-то последовательность действий для решения нашей проблемы, а затем перейдем к шагу 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. Отладка неудачных тестов
Самый логичный и, вероятно, ожидаемый из шагов.Код необходимо отладить и скорректировать алгоритм.
Здесь больше нечего добавить.
Заключение
Могу сказать, что вряд ли бы я когда-либо серьезно отнесся к такому подходу к решению задач, если бы не мое сонное состояние.Но на этот метод стоит обратить внимание – он короткий, и вся его трудоемкость заключается лишь в том, что его необходимо использовать.
Примечание
Спасибо учебникам линейной алгебры за материал для решения задачи.Теги: #математика #программирование #Лайфхаки для гиков #моделирование #лайфхаки #октава
-
Lims И Исследования Стволовых Клеток
19 Oct, 24 -
Заметки Биоробота
19 Oct, 24 -
Провайдеры, Абоненты И Забавные Случаи
19 Oct, 24 -
Tut Не Размещает Порнографию И Спамеров!
19 Oct, 24
