ВВЕДЕНИЕ
Численноерешение СЛАУ – одна из наиболее часто встречающихся задач в научно-техническихисследованиях. Такая задача возникает в математической физике (численноерешение дифференциальных и интегральных уравнений), экономике, статистике. Приэтом прикладные задачи часто требуют решения больших и сверхбольших СЛАУ счислом неизвестных более 1000. К таким СЛАУ, например, приводит численноерешение двумерных и особенно трехмерных задач математической физики, в которыхусловия физической и геометрической аппроксимации двумерной и трехмернойобласти диктуют использование достаточно мелкой расчетной сетки с большимчислом расчетных узлов по линейному размеру.
Существующиебиблиотеки программ на языках высокого уровня, разработаны на основе, такназываемых, прямых методов решения СЛАУ, типа метода Гаусса и его модификаций.Число арифметических операций умножения для численного решения СЛАУразмерностью /> с помощью прямогометода — />. Кубическаязависимость числа арифметических операций от размера матрицы СЛАУ приводит при /> кнереально большому времени решения даже на самых современных ЭВМ. Кроме того,время решения несоразмерно возрастает при использовании прямых методов в случае/> попричине недостаточности объема оперативной памяти для хранения данных задачи.
Итерационныеметоды решения СЛАУ намного экономнее, как по машинному времени решения, так ипо использованию оперативной памяти. Так, если итерационный метод являетсябыстро сходящимся с числом итераций />,то время решения, пропорциональное уже квадрату размера матрицы ~ />,оказывается существенно меньше, примерно в /> раздля вещественной и /> раз длякомплексной СЛАУ. Кроме того, требуется хранить в оперативной памяти, какправило, только одну матрицу, например, матрицу перехода явного итерационногометода. При использовании быстро сходящихся итерационных методов вполнерешаемыми в реальном времени на современных ПЭВМ оказываются СЛАУ с комплекснойматрицей размерностью />.
Внастоящее время отсутствуют библиотеки подпрограмм широкого назначения длячисленного решения больших и сверхбольших СЛАУ. Таким образом, разработкаэффективных итерационных алгоритмов для широкого класса матриц СЛАУ большойразмерности и библиотек подпрограмм на их основе является актуальной задачей.
Наиболееалгоритмически простыми среди итерационных методов являются стационарныеитерационные методы, такие как оптимальный метод простой итерации и методрелаксации. В то же время показано, что можно добиться их эффективнойсходимости для достаточно широкого класса вещественных и комплексных матрицСЛАУ. Для нестационарных итерационных методов, таких как метод с чебышевскимнабором параметров, минимальных невязок, сопряженных градиентов, сходимостьдоказана в узком классе матриц, например, таких как вещественные симметричныеположительно определенные матрицы. И в этом узком классе матриц сходимостьоптимальных стационарных методов, опирающихся на известные спектральныематричные свойства, оказывается в некоторых случаях даже лучшей. При этом числоарифметических операций стационарного алгоритма минимально. Еще однимпреимуществом оптимального метода простой итерации является возможностьестественного распараллеливания алгоритма при постановке его на современныепараллельные ЭВМ, так как алгоритм по существу сводится к одному умножениюматрицы на вектор. Все эти аргументы указывают на выбор стационарныхитерационных методов в качестве алгоритмической основы для библиотекиподпрограмм по решению СЛАУ с большими матрицами. В курсовой работе рассмотренитерационный метод релаксации решения СЛАУ.
1.МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ
Рассмотримсистему линейных алгебраических уравнений
/>, (1.1)
где
А — матрица размерности />,
x=(x1,x2,...,xn)T-вектор решения,
f=(f1,f2,...,fn)T- вектор правых частей.
Численныеметоды решения данной системы принято разделять на два класса: прямые методы иитерационные.
Прямымиметодами называются методы, позволяющие получить решение системы уравнений (1.1)за конечное число арифметических операций.
Кпрямым методам относятся метод Крамера, метод Гаусса, LU — метод, метод прогонки и ряд других методов. Основным недостатком прямых методовявляется то, что для нахождения решения необходимо выполнить большое числоопераций.
Сутьитерационных методов состоит в том, что решение системы (1.1) находится какпредел последовательных приближений x(n)при n®¥,где n— номер итерации. Применение итерационныхметодов требует задания начального значения неизвестных х(0)и точности вычислений e>0. Вычисления проводятся до тех пор,пока не будет выполнена оценка
/>. (1.2)
Основноедостоинство итерационных методов состоит в том, что точность искомого решениязадается.
Числоитераций n=n(e),которое необходимо выполнить для получения заданной точности e,является основной оценкой качества метода. По этому числу проводится сравнениеразличных методов.
Главнымнедостатком этих методов является то, что вопрос сходимости итерационногопроцесса требует отдельного исследования. Доказанные в настоящее время теоремыо сходимости итерационных методов имеют место для систем, на матрицы которыхналожены ограничения.
Примеромобычных итерационных методов могут служить метод Якоби (метод простыхитераций), метод Зейделя, метод верхних релаксаций.
Кособому классу итерационных методов следует отнести вариационные итерационныеметоды: метод минимальных невязок, метод скорейшего спуска и т.д.
Итерационныеметоды также делятся на одношаговые, когда для определения решения на j+1итерации используются значения решения, найденные на jитерации, и многошаговые, когда для определения решения на j+1итерации используется несколько предыдущих итераций.
Заметим,что существуют системы, для которых итерационный процесс сходится, а векторневязки, получающийся при подстановке найденного решения в исходную систему
/>, (1.4)
получаетсябольшим по величине, т.е. найденное решение не удовлетворяет исходной системе.В этом случае в качестве критерия достижения точности решения может быть взятавеличина невязки, которая оценивается по одной из норм /> .
Продемонстрируемприменение одношагового итерационного метода Якоби на решении системы трехуравнений. Пусть система (1.1) имеет вид