Матрица с диагональным преобладанием.

[nickname2014]

Привет всем.
Нужно привести матрицу к виду с диагональным преобладанием.
$ \left( \begin{array}{cccc} 1 & 5 & 3 & -4\\ 3 & 1 & -2 & 0\\ 5 & -7 & 0 & 10\\ 0 & 3 & -5 & 0 \end{array} \right)$
Т. е., как понимаю, модуль каждого диагонального элемента матрицы должен быть больше суммы модулей элементов на той же строке. Пытался применить элементарные преобразования: к одной строке прибавлял другую (или даже - другие), умноженную на некоторое число. Несколько раз уже получалось так, что одна строка все равно оказывалась не "диагонализированной"... :(
Может быть, есть какие-то алгоритмы, упрощающие поиск таких строк?
p. s. Есть ещё вектор свободных коэффициентов - но здесь он, думаю, не понадобится. Нужно получить решения системы - методами Якоби, Зейделя - но обязательно получить диагональное преобладание.

[мат-ламер]

Найдите максимальный элемент в объединении первого столбца и первой строки. Если он в первой строке - поменяйте местами первый столбец и столбец с максимальным элементом. Если он в первом столбце - поменяйте местами строки. Далее первую строку и столбец не трогайте и работайте точно также по индукции с матрицей размером на единицу меньше.

[GAA]

nickname2014, я алгоритм не знаю, но на мой взгляд, тут невозможно запутаться. Почти уверен, Вы уже всё сделали самостоятельно.

Во-первых, нужно проверить: есть ли уравнения c «диагональным преобладанием». В данном случае это последнее (четвёртое) уравнение. Его запишем в третью строчку новой системы.

Остальные уравнения нужно преобразовывать. Умножив второе уравнение на 3, и вычтя четвертое уравнение исходной системы, получим $9x + 0y -z = \ldots$. Это уравнение запишем в первую строку новой системы.

Прибавив к первому уравнению четвертое уравнение, получим ..., и запишем во вторую строку.

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

мат-ламер, я не понял Ваш алгоритм. Нельзя ли пояснить: как получается первое уравнение новой системы?

[ewert]

GAA в сообщении #934419 писал(а):

, я алгоритм не знаю,

А его и нет. Т.е. в общем случае невозможно привести матрицу к диагональному преобладанию хоть сколько-то универсальным способом. Т.е. алгоритмически эта задачка -- абсолютно незначима.

-- Сб ноя 22, 2014 01:27:05 --

мат-ламер в сообщении #934294 писал(а):

и работайте точно также по индукции с матрицей размером на единицу меньше.

Это проигрывает тупому методу Гаусса всего лишь в несколько раз, а надо бы проиграть -- хотя бы в несколько тысяч; только в этом случае можно было бы говорить хоть о каком-то преимуществе подобного подхода.

[мат-ламер]

GAA в сообщении #934419 писал(а):

мат-ламер, я не понял Ваш алгоритм. Нельзя ли пояснить: как получается первое уравнение новой системы?

Как выяснилось, я не совсем понял насчёт диагонального преобладания. В конечных методах (типа Гаусса) под диагональным преобладанием понимают ситуацию, когда диагональный элемент по модулю больше чем элементы справа и снизу от него. Это гарантирует отсутствие накопления ошибок при вычислениях. Мой алгоритм относился к этому случаю. А для итеративных методов требования по диагональному преобладанию жёстче.

[ewert]

мат-ламер в сообщении #934820 писал(а):

В конечных методах (типа Гаусса) под диагональным преобладанием понимают ситуацию,

В методах Гаусса подобную терминологию вообще не употребляют. Там потребляют типо "главный элемент", но это вообще в сторону.

А тут предлагалося исключительно некая игра в бисер: подсадить конкретную систему под методически извращённый метод. Который в боевой обстановке, естественно, никакого практического значения и не имеет. Просто поиграться захотелось.