Метод релаксации переменных решения СЛАУ (стр. 1 из 4)

ВВЕДЕНИЕ

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

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

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

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

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

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

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

1. МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ

Рассмотрим систему линейных алгебраических уравнений

,

(1.1)

где

А- матрица размерности

,

x=(x₁,x₂,...,x_n)^T- вектор решения,

f=(f₁,f₂,...,f_n)^T- вектор правых частей.

Численные методы решения данной системы принято разделять на два класса: прямые методы и итерационные.

Прямыми методами называются методы, позволяющие получить решение системы уравнений (1.1) за конечное число арифметических операций.

К прямым методам относятся метод Крамера, метод Гаусса, LU- метод, метод прогонки и ряд других методов. Основным недостатком прямых методов является то, что для нахождения решения необходимо выполнить большое число операций.

Суть итерационных методов состоит в том, что решение системы (1.1) находится как предел последовательных приближений x⁽ⁿ⁾ при n®¥, где n- номер итерации. Применение итерационных методов требует задания начального значения неизвестных х⁽⁰⁾ и точности вычислений e>0. Вычисления проводятся до тех пор, пока не будет выполнена оценка

.

(1.2)

Основное достоинство итерационных методов состоит в том, что точность искомого решения задается.

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

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

Примером обычных итерационных методов могут служить метод Якоби (метод простых итераций), метод Зейделя, метод верхних релаксаций.

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

Итерационные методы также делятся на одношаговые, когда для определения решения на j+1 итерации используются значения решения, найденные на j итерации, и многошаговые, когда для определения решения на j+1 итерации используется несколько предыдущих итераций.

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

,

(1.4)

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

.

Продемонстрируем применение одношагового итерационного метода Якоби на решении системы трех уравнений. Пусть система (1.1) имеет вид

(1.5)

начальное приближение

(верхний индекс указывает номер итерации), требуемая точность решения -e. Первая итерация находится из выражения

(1.6)

Непосредственная проверка условия (1.2) связана с необходимостью знания точного решения. Поэтому на практике используется несколько упрощенное правило, т.е. проверяют, достигнута заданная точность или нет, сравнивая два итерационных значения x

(1.7)

Если точность не достигнута, то выполняется следующая итерация. В системе (1.5)

заменяем на и находим значения . После этого вновь проверяем, достигнута точность решения или нет.

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

Запишем выражение i+1- итерации черезi:

(1.8)

Если точность решения достигнута, то счет прекращается.

Для систем m-го порядка имеем

(1.9)

Запишем метод простых итераций в матричной форме. Представим матрицу А в виде суммы трех матриц