Точность решения СЛАУ прямыми методами

[Andrey_Kireew]

В процессе оптимизации симплекс-таблицы с помощью простого симплекс-метода выполняется множество жордановых исключений. Разумно предположить, что если число итераций велико и намного превосходит количество переменных плана, то такая оптимизация может сопровождаться существенным накоплением ошибки и непосредственное решение СЛАУ для найденного оптимального плана позволит уточнить решение (либо выявить, что план в действительности не оптимален).

Для решения СЛАУ я использовал тот же самый метод жордановских исключений, с выбором максимального разрешающего элемента по всей матрице (в литературе говорится, что это позволяет получить наиболее точные результаты).

Удивительно, но при численном эксперименте выяснилось, что результаты непосредственного решения СЛАУ оказываются менее точными, чем решение симплекс-метода.

Это наталкивает на мысль, что правило выбора разрешающего элемента как максимального элемента матрицы пусть и хорошее, но не самое лучшее.

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

Исходные данные генерировались по определённому уравнению, а потом оценивались его коэффициенты. Ошибки вычислений я оценивал по расхождению заданных значений коэффициентов и вычисленных.

Вообще, абсолютные значения расхождений небольшие $e=10^{-16}$ - для симплекс-метода, и $e=10^{-12}$ - для прямого решения СЛАУ. Но это на модельной задаче, в других случаях расхождения могут оказаться и большими. Главная неприятность в том, что в таких условиях уточнение оптимального плана может и не быть уточнением вовсе и проверить это будет никак нельзя.

Может быть кто то сможет посоветовать, какой ни будь более эффективный способ определения порядка жордановых исключений? (насколько я понимаю pLU - разложение - это почти то же самое, выигрыша в точности оно не даст)

Единственным выходом в данной ситуации мне представляется использовать для решение QR разложение,
но это весьма затратная в вычислительном отношении процедура, и не хотелось бы без особой нужды её использовать.

[Евгений Машеров]

А можно подробностей по методике сравнения?

[Andrey_Kireew]

Задаю вектор независимой переменной:

1. >>x=(1:300)'; 

Вычисляю вектор зависимой переменной по заданному уравнению:

1. >>y=3+6*x-71.003*x.^3; 

Создаю матрицу Грамма:

1. M(1,ii)=3*ones(300,1); 
2. M(2,ii)=6*(1:300); 
3. M(3,ii)=zeros(300,1); 
4. M(4,ii)=-71.003*(1:300).^3; 

Ищу решение системы:
$ Mb=y $

Потом сравниваю найденное решение с заданными коэффициентами уравнения $(3; 6; 0; -71.003)$.

[Евгений Машеров]

Я потрясён способностью метода справиться с вырожденной задачей. У Вас столбец из нулей, матрица неполного ранга. Зачем он Вам?!

[Andrey_Kireew]

Если Вы про пример - то на нулевом коэффициенте хорошо видна ошибка вычислений,
я ставил вместо нуля небольшое число - тогда после уточнения точность старшего коэффициента повышается (он вычисляется совершенно без ошибки, хотя специально взято дробное число с 5 значащими цифрами. Тем не менее точность остальных коэффициентов всё равно падает, так как и раньше.

Что касается вырожденности - то это только с позиции МНК. В моей постановке задачи ЛП оптимальный план получается не вырожденным, хотя и очень плохо обусловленным.
Точность метода меня самого приятно удивила, но почему так получается - пока не совсем понятно.

Пока попробую QR разложение с вращениями Гивенса, возможно это поможет если не повысить точность, то хотя бы приблизится к исходной.

[svv]

Может, что-то полезное найдёте в книжке:
«Гарантированная точность решения систем линейных уравнений в евклидовых пространствах»
Годунов, Антонов, Кирилюк и др.

[Andrey_Kireew]

Большое спасибо! скачал, сейчас почитаю

[Andrey_Kireew]

Честно говоря не понравилась мне книжка, слишком уж односторонний подход, да и чрезмерно теоретизировано там всё.
Хотелось бы что то обороне, и по ближе к практике. Сам читаю [Амосов А.А., Дубинский Ю.А., Копченова Н.В. Вычислительные методы для инженеров: Учеб. пособие. — М.: Высш. шк., 1994. — 544 с.]

[Andrey_Kireew]

Реализовал алгоритм на вращениях Гивенса. Без выбора ведущего элемента он не работает вовсе (видимо на диагонали попадаются нули). При выборе ведущего столбца по максимальному элементу ведущей строки (порядок строк сохраняется) алгоритм работает, но ошибка даже больше чем в методе Жордана с выбором ведущего элемента по всей матрице.

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

Повторные вычисления показывают, что симплекс-алгоритм (построенный на жордановых исключениях) даёт ошибку только в последней значащей цифре, в то время как при пересчёте найденного оптимального плана методом Жордана с выбором разрешающего элемента как максимального элемента матрицы 3 последние цифры результата получаются неверные.