Народ кажется не стал читать текст nabbla1 по ссылке и не въехал в чем проблема:
... разумеется, и здесь мы получили симметричную матрицу, так что уберём ненужный верхний треугольник:
Можно идти в разном порядке, но всегда это будет от левого верхнего угла к правому нижнему. Наверное, наиболее очевидный способ - идти по столбцам, слева направо, а в каждом столбце - сверху вниз.
Начинаем с первого столбца:
Каждый раз мы заменяем старое значение новым, по сути получив такую промежуточную матрицу:
Теперь обрабатываем второй столбец:
Действительно, мы использовали уже обработанные значения с первого столбца, и пока что необработанные со второго. Вычисления можно чуть упростить, заметив, что повсюду используется одно и то же выражение
так что, посчитав его один раз, можно сэкономить 2 умножения.
Обрабатываем третий столбец:
Количество работы в каждом компоненте растёт, зато их количество падает. Здесь мы снова можем чуточку сэкономить, введя переменные
экономия снова составит 2 умножения.
Наконец, на 4-м столбце у нас все один, диагональный элемент:
На этом преобразование завершено.
Посчитаем необходимое количество операций для матрицы N×N.
Количество делений составляет
квадратичная зависимость, в нашем случае N=4 имеем 6 делений, для N=6 получается 15 делений.
Количество умножений составляет (если не вводить временных переменных)
здесь зависимость уже кубическая - ничего не поделаешь, но у нас, по счастью, размерности не очень большие. Для N=4 получаем 20 умножений, для N=6: 70 умножений.
Если ввести временные переменные, или поменять местами 2 цикла (вычитать из всех элементов на текущем столбце по одному множителю, вместо вычисления каждого из них "в один присест"), то получим значение чуть лучше:
Для N=4, получаем 16 умножений (да, как и обещали - сэкономили по 2 в двух строках), а для N=6: 50 умножений. Неплохо :)
И наконец, можно подсчитать количество сложений/вычитаний (мы разницы между ними не делаем):
для N=4 получаем 10 сложений, для N=6: 35 сложений.
Метод славится устойчивостью: нам не нужно предварительно менять местами строки матрицы, стараясь расположить самые большие элементы на главной диагонали.
Там еще наблюдение что две "треугольные" матрицы (у симметричной матрицы нет смысла хранить вторую половину) удобнее всего хранить в качестве половинок прямоугольной - упрощается доступ к элементам каждой из них.
там еще надо например думать в каком порядке надо считать, чтобы вычисленные значения можно было размещать на месте старых, etc etc
Вот о механизации подобного увлекательного секса (которым мне тоже доводилось заниматься) и идет речь.