Лабораторная работа №1
ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ
СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ
Цель лабораторной работы – закрепить на практике теоретические вопросы, рассмотренные на лекционных занятиях при изучении численных методов решения систем линейных алгебраических уравнений, в том числе:
вырожденные, невырожденные и плохо обусловленные системы;
итерационный метод Якоби;
итерационный метод Гаусса-Зейделя;
достаточные условия сходимости итерационного метода Гаусса-Зейделя;
геометрическое истолкование итерационных методов;
скорость сходимости итерационных методов;
прямой метод Гаусса;
погрешности решения СЛАУ прямыми и итерационными методами.
В результате проведения лабораторной работы студенты должны
знать:
особенности применения и алгоритмы реализации различных численных методов решения СЛАУ;
ограничения, налагаемые на методы решения СЛАУ в зависимости от вида системы;
практические подходы к решению СЛАУ различными методами.
уметь
выбирать и реализовывать методы численного решения СЛАУ с учетом скорости сходимости итерационного процесса к решению и вида самой системы.
1 Системы линейных алгебраических уравнений
Они появляются почти в каждой области прикладной математики. Мы будем рассматривать системы из n уравнений с n неизвестными. Каждый член такого уравнения содержит только одно неизвестное, и каждое неизвестное входит только в 1-ой степени. Такая система уравнений называется линейной. В случае 2-х неизвестных каждое уравнение графически изображается прямой линией, в случае 3-х уравнений – ему соответствует плоскость в трехмерном пространстве, а для 4-х и более неизвестных – гиперплоскость. Искомое решение системы уравнений – набор значений неизвестных, удовлетворяющих одновременно всем уравнениям.
Относительно решений системы можно рассмотреть 3 случая.
1.Решение системы существует и является единственным.
Рассмотрим систему (1):
(1)
Решение этой системы единственно, и никакие другие значения х и у не способны одновременно удовлетворять этим двум уравнениям.
Рисунок 1.1 – Геометрическое решение системы (1)
Геометрическое решение системы (1) – точка пересечения двух прямых.
2. Система уравнений вообще не имеет решений.
Рассмотрим систему (2):
(2)
Оба уравнения этой системы представлены графически на рис.1.2.
Рисунок 1.2 – Геометрическое представление уравнений системы (2)
Две прямые параллельны, они не пересекаются, и система уравнений не имеет решения.
3. Система уравнений имеет бесконечное множество решений
Рассмотрим систему (3):
(3)
Эти два уравнения описывают одну и ту же прямую линию (Рис.1.3). Любая точка, лежащая на этой линии является решением такой системы уравнений.
Рисунок 1.3 – Геометрическое решение системы (3)
Система имеет бесконечное множество решений.
Системы уравнений типа (2) и (3) называются вырожденными.
Иногда непосредственно из поставленной задачи бывает ясно, что система уравнений не может быть вырожденной. Если же эта информация отсутствует, то приходится проверять вырожденность системы уравнений или в процессе решения, или исследовать такую возможность.
Непосредственная проверка состоит в вычислении определителя системы, и равенство определителя нулю указывает на ее вырожденность. Однако вычислить определитель ничуть не легче, чем просто решить систему уравнений.
С точки зрения обычной математики система линейных уравнений всегда является или вырожденной, или невырожденной. С точки зрения практических вычислений могут существовать почти вырожденные системы, при решении которых получаются недостоверные значения неизвестных.
Рассмотрим систему:
(4)
Эта система имеет единственное решение х=1, у=1.
Рисунок 1.4 – Геометрическое представление системы (4)
Если рассмотреть пару значений неизвестных х=2,415 , у=0, и подставить их в уравнение (4), то получим:
При округлении до двух значащих цифр получаем исходную систему. Значит, эти значения неизвестных так же хорошо удовлетворяют решению системы, как и х=1, у=1.
Причина заключается в том, что линии, описываемые уравнениями, почти параллельны. Точка х=2,415; у=0 не лежит ни на одной из этих линий, но очень близка к ним.
Системы типа (4) называются плохо обусловленными.
В любом случае, когда две лини (либо плоскости, гиперплоскости) почти параллельны, система уравнений становится плохо обусловленной. В этом случае найти численное решение системы трудно, а точность его весьма сомнительна.
Более того, система из 3-х и более уравнений может оказаться плохо обусловленной, даже если никакие плоскости не являются параллельными или почти параллельными (например, грани треугольной призмы не пересекутся в одной точке; если же одна грань будет слегка наклонена, то система уравнений будет плохо обусловленной).
Методы численного решения систем линейных уравнений подразделяются на 2 типа:
прямые (конечные);
итерационные (бесконечные).
Понятно, что никакой метод не может быть бесконечным. Имеется в виду, что в принципе прямые методы (с точностью до ошибки округления) могут дать точное решение, если оно существует, за конечное число арифметических операций.
С другой стороны, итерационные методы требует бесконечного числа арифметических операций, приводящих к точному решению. Поэтому при реальном использовании итерационного метода появляется ошибка ограничения, отсутствующая в прямых методах.
Это не значит, что решение, полученное с помощью прямого метода, обязательно будет точнее. При решении большой плохо обусловленной системы прямым методом ошибки округления могут привести к бессмысленным результатам. В этом случае итерационный метод может оказаться наиболее удобным, т.к. при его использовании ошибки округления не накапливаются.
Оба подхода удобны и полезны для практических вычислений, и каждый из них имеет свои достоинства и недостатки.