Итерационные методы решения систем линейных уравнений с неединственными коэффициентами
Реферат - Математика и статистика
Другие рефераты по предмету Математика и статистика
Министерство образования Российской Федерации
Пермский Государственный Технический Университет
Курсовая работа
Итерационные методы решения линейных систем с неединственными коэффициентами
Выполнил:
Елисеев Александр Сергеевич, ММ-05-2
Научный руководитель:
Грайфер Лазарь Борисович
Пермь 2005
Оглавление
Введение3
1. Уточнение решения4
2. Метод простых итераций7
3. Метод Гаусса Зейделя14
4. Применение итерационных методов16
Список использованной литературы19
Введение
Все используемые на практике методы решения систем линейных алгебраических уравнений можно разделить на две большие группы: точные методы и итерационные методы.
Под точным методом решения понимается метод, позволяющий теоретически получить точное значение всех неизвестных в результате конечного числа арифметических операций. (метод Крамера)
Итерационные методы позволяют получить решение лишь в виде предела последовательности векторов, построение которого производится единообразным процессом, называется процессом итерации, или последовательных приближений.
Вдобавок, итерационные методы находят широкое применение и при решении еще одной вычислительной задачи линейной алгебры, называемой полной проблемой собственных значений (отыскание всех собственных значений и отвечающих им собственных векторов заданной матрицы), т.к. намного удобнее вычислить предел некоторых числовых последовательностей без предварительного определения коэффициентов характеристического многочлена.
Преимуществом итерационных методов является удобное применение в современной вычислительной технике, т.к. решения, полученные с помощью прямых методов обычно содержат погрешность. Итерационные методы же позволяют получить решение данной системы с заранее определенной погрешностью. Явным преимуществом является значительное превосходство над точные методы по скорости и удобнее реализуются на практике.
1. Уточнение решения
Полученные с помощью прямых численных методов решения обычно содержат погрешность, вызванную округлениями при выполнении операций над числами с плавающей точкой. В некоторых случаях эти погрешности могут оказаться недопустимо большими. Рассмотрим один из методов уменьшения погрешности численного решения СЛАУ.
Найдем решение системы линейных уравнений
(1.1)
Пусть с помощью некоторого метода получено приближенное решение (начальное приближение к решению). Подставив в (1.1), получим
(1.2)
Обозначим за погрешность полученного решения, - невязка.
Вычитаем (1.2) из (1.1), с учетом введенных обозначений
(1.3)
Решив эту систему получим новое значение погрешности , которое используем в качестве поправки к приближенному решению , получая таким способом новое приближение (следующее приближение к решению):
.
Таким же способом найдем следующее приближение и следующую поправку к приближению . Подобным образом будем искать очередные значения погрешности и поправки, пока погрешность не станет достаточно малым. Таким образом мы найдем приближенное решение системы с заданной точностью.
Рассмотренный выше процесс фактически является итерационным методом решения системы линейных уравнений, при этом следует отметить небольшой объем вычислений, т.к. на каждой итерации решаются системы уравнений вида (1.3) с одной и той же матрицей, т.е. нет необходимости преобразовывать матрицу. Такой подход позволяет строить экономичные с точки зрения машинного времени алгоритмов.
Следует заметить, что если при увеличении числа итераций приближенное решение стремится к точному:
,
то итерационный метод называют сходящимся.
Наличие сходимости и достижения заданной точности на практике можно определить (приближенно) несколькими способами. Так, при заданной погрешности
(1.4),
, (1.5),
, при (1.6).
Здесь в (1.4) отличие векторов и на ? понимается как малость модуля их разности. В (1.5) малость разностей всех компонентов вектора, в (1.6) в смысле малости относительных разностей компонент. В случае, когда система не является плохо обусловленной, то в качестве критерия достижения нужной точности можно принять условие малости невязки:
. (1.7)
2. Метод простых итераций (метод Якоби)
Рассмотрим квадратную систему линейных уравнений с вещественными коэффициентами, которую запишем в матричном виде (1.1).
.
Предполагая однозначную разрешимость системы (1.1), заменим матричное уравнение эквивалентным ему уравнением:
,(2.1)
где ? вещественное число, называемое стационарным параметром. С помощью (2.1) составим итерационную последовательность в?/p>