Сравнительный анализ прямых и итерационных методов решения систем линейных алгебраических уравнений

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

Все методы решения СЛАУ делятся на две группы – точные (прямые) и итерационные. Точные методы позволяют получить решение системы линейных уравнений за конечное число арифметических операций (метод Гаусса, метод квадратного корня, правило Крамара и т. д.). Использование итерационных методов дает возможность найти приближенное решение системы с заданной степенью точности (метод простой итерации, метод Зейделя, метод последовательной релаксации).

При решении СЛАУ возникает необходимость выбора того или иного метода, который позволит получить эффективный результат с использованием вычислительной техники. В этой ситуации актуализируется проблема сравнительного анализа прямых и итерационных методов решения СЛАУ.

Исследованию методов решения систем линейных алгебраических уравнений уделяется большое внимание в современной математике. Среди ученых, научные интересы которых посвящены этой проблеме, необходимо выделить С. Годунова, В. Воеводина, А. Островского,    Дж. Форсайта, К. Молера и др. При этом, сравнению итерационных и прямых методов решения СЛАУ с помощью вычислительной техники уделяется не достаточно внимания. Это вызывает необходимость дальнейшего рассмотрения данного вопроса в аспектах разработки критериев сравнения, рекомендаций выбора оптимального метода решения и т. д.

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

Для возможности проведения сравнения этих методов обобщим систему критериев. Согласно исследованиям В. Воеводина  [3, с. 85],  Д. Мак-Кракена [7, c. 297], результаты решения системы линейных уравнений (1), полученные как точными, так и итерационными методами, имеют определенную степень погрешности, что требует проведения оценки этого параметра для каждого из методов.

image001

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

В вопросах выбора того или иного способа решения СЛАУ важно учитывать область применения прямых и итерационных методов. Это связано с тем, что не каждый метод дает возможность получить гарантированный результат для определенной системы линейных уравнений, на что обращают внимание в своих работах  В. Жигульская [6], С. Годунов [4]. Таким образом, целесообразно выделить в качестве еще одного критерия сравнения область применения метода решения  СЛАУ.

Эффективность результата решения системы линейных уравнений с реализацией на ЭВМ зависит от времени, затраченного на решение. Это актуально для случая, когда рассматриваются сверхбольшие матрицы СЛАУ. Поэтому, временные затраты на решение СЛАУ выберем в качестве третьего  критерия.

Таким образом, критериями сравнения точных и итерационных методов решения СЛАУ с использованием вычислительной техники будут:

  • область применения метода;
  • временные затраты на решение;
  • погрешность результата.

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

Кроме того, область применения методов решения СЛАУ ограничивается видом матрицы А системы (1), и в первую очередь —  ее размерностью.

image0021

Известно, что прикладные задачи часто требуют решения больших и сверхбольших СЛАУ с числом неизвестных более 1000. К таким СЛАУ, например, приводит численное решение двумерных и особенно трехмерных задач математической физики, в которых условия физической и геометрической аппроксимации двумерной и трехмерной области диктуют использование достаточно мелкой расчетной сетки с большим числом расчетных узлов по линейному размеру. Анализ работ [1; 2; 5] показывает, что решения задач СЛАУ большой размерности целесообразно осуществлять итерационными методами, так как  использование прямых методов невозможно из-за ограничений доступной оперативной памяти ЭВМ, а также из-за необходимости выполнения чрезмерно большого числа арифметических операций.

Эффективность итерационных методов, используемых на ЭВМ,  в решении СЛАУ с разреженными матрицами  показана в работах [3; 6; 7]. Использование этих методов позволяет сохранить свойство  разреженности матрицы. Применение прямых методов для таких систем приводит к тому, что большое число нулевых элементов превращается в ненулевые, и матрица теряет разреженность.

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

Сравним прямые и итерационные методы по временным затратам. При реализации на языках высокого уровня алгоритмов прямых методов решения систем линейных уравнений размерностью N  необходимо учитывать, что число арифметических операций умножения будет составлять N3. Для систем с размерностью эта кубическая зависимость приводит к большим затратам количества времени при решении даже на самых современных ЭВМ N>1000.

Итерационные методы решения СЛАУ намного экономнее по затратам машинного времени. Так, если итерационный метод является быстро сходящимся с числом итераций m << N, то время решения пропорционально квадрату размера матрицы ~ m-N2. Эти затраты меньше, по сравнению с точными методами, в N/m раз для вещественной, и 2N/m раз для комплексной СЛАУ.

В качестве примера на рис. 1 показана зависимость времени решения от размерности матрицы для решения СЛАУ методами Гаусса и Зейделя.

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

image013

Рис. 1. Зависимость времени решения от размерности матрицы при использовании прямого и итерационного метода

Проанализируем прямые и точные методы решения СЛАУ по критерию погрешности полученного результаты решения. Точным методам решения СЛАУ присуща погрешность округления, которая может возникать в ходе вычисления, а  так же в процессе реализации этих  методов на ЭВМ. В данном случае  из-за ограниченности разрядной сетки ЭВМ вносятся погрешности округления при задании вектора b и матрицы A. Все это приводит к получению не точного, а приближенного решения системы Ax = b. Так, в исследованиях В.В. Воеводина  на примере  метода Гаусса доказывается, что относительная погрешность решения системы (1)  составляет [3,  с. 85]:

image014

где:  n – порядок матрицы A;

t – число двоичных разрядов мантиссы числа на  используемой ЭВМ.

Например, для персональных ЭВМ 2t≈ 10−7. В свою очередь число обусловленности матрицы A, которое  характеризует степень зависимости относительной погрешности решения от относительной погрешности правой части, составляет: image017

В случае с итерационными методами, суть которых состоит в том, что решение системы (1) находится как предел последовательных приближений x(n) при n → ∞, где n — номер итерации, требует задания начального значения неизвестных х(0) и точности вычислений e>0. Вычисления проводятся до тех пор, пока не будет выполнена оценка

image019

Основное достоинство итерационных методов состоит в том, что точность искомого решения задается. Число итераций n=n(e), которое необходимо выполнить для получения заданной точностиe, является основной оценкой качества метода. По этому числу проводится сравнение различных итерационных методов.

Обобщим проведенный сравнительный анализ точных и итерационных методов решения СЛАУ по обозначенным выше критериям в табл. 1.

Особенности применения прямых и точных методов решения СЛАУ  для реализации на ЭВМ

Критерий сравнения Прямые методы Итерационные методы
Область применения метода
  1. неэффективны при реше-нии матриц большой размерности из-за выпол-нения чрезмерного числа арифметических операций;
  2. приводят к потере свойства разреженности в разряженных матрицах.
  3. область применения зависит от свойства сходимости;
  4. эффективны при решении разряженных матриц и матриц большой размерности.
  1. область применения зависит от свойства сходимости;
  2. эффективны при решении разряженных матриц и матриц большой размерности.
Временные затраты
  1. приводит к необходимос-ти затраты большого количества времени при решении системы из-за кубической зависимость числа арифметических операций от размера матрицы
  2. экономичны,  в плане затраты машинного времени и  использования оперативной памяти т. к. время решения, пропорционально квадрату размера матрицы.
  1. экономичны,  в плане затраты машинного времени и  использования оперативной памяти т. к. время решения, пропорционально квадрату размера матрицы.
Погрешность результата
  1. нет сведений о точности полученного решения;
  1. позволяют получить решение с любой заданной точностью.

На основе выделенных особенностей прямых и точных методов СЛАУ разработаем алгоритм выбора метода решения для системы линейных алгебраических уравнений  (рис.2).

image0201

Рис. 2. Блок-схема алгоритма выбор метода решения СЛАУ

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

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

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

На основе проведенного анализа был разработан алгоритм выбора метода решения СЛАУ. Однако окончательное решение о применении итерационных или прямых методов решения СЛАУ необходимо принимать на основе анализа структуры исследуемой математической задачи.

Литература

1. Бахвалов Н.С. Численные методы / Н.С. Бахвалов. – М.: Наука, 1975. – 468 с. 2. Баландин М. Ю. Методы решения СЛАУ большой размерности. / М.Ю. Баландин., Э.П. Шурина.–Новосибирск: Изд-во НГТУ, 2000. – 70 с. 3. Воеводин В.В. Матрицы и вычисления / В.В. Воеводин, Ю.А. Кузнецов. –М.: Наука, 1984. – 450 с. 4. Годунов С.К. Решение систем линейных уравнений / С.К.  Годунов.– Новосибирск: Наука, 1980. – 250 с. 5. Джордж А. Численное решение больших разреженных систем уравнений / Джордж А., Дж. Лиу. – М.: Мир, 1984. – 390 с. 6.Жигульская В. Ю. Численные методы / В. Ю.  Жигульская.– Луганск: Альма-матер, 2005 – 137 с. 7. Мак-Кракен Д.Численные методы и программирование на фортране / Мак-Кракен Д., У. Дорн.–  М.: Мир, 1977 – 579 с.