kouzdra (kouzdra) wrote,
kouzdra
kouzdra

Categories:

Линейно-алгебраическое-2

К этому: https://kouzdra.livejournal.com/4358531.html

Народ кажется не стал читать текст 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

Вот о механизации подобного увлекательного секса (которым мне тоже доводилось заниматься) и идет речь.
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 1 comment