close

Вход

Забыли?

вход по аккаунту

?

Итерационные методы решения СЛАУ

код для вставкиСкачать
ЛАБОРАТОРНАЯ РАБОТА №3
ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ
Итерационные методы решения систем линейных уравнений дают возможность вычислить решение системы как предел бесконечной последовательности промежуточных решений. Причем каждое последующее решение в случае сходимости итерационного процесса считается более точным. В этих методах, в отличие от точных, ошибки в начальном приближении и последующих вычислениях компенсируются, т.е. итерационные методы (в случае сходимости) позволяют получить решение более точное, чем прямые. Поэтому итерационные методы относят к самоисправляющимся.
Условия и скорость сходимости процесса в большей степени зависят от свойств уравнений, т.е. от свойств матрицы системы и от выбора начального приближения.
Пусть дана система линейных алгебраических уравнений (1.22) с неособенной матрицей.
или в матричном виде AX = B, где A - прямоугольная матрица размерности mn, X - вектор n-го порядка, B - вектор m-го порядка.
МЕТОД ПРОСТОЙ ИТЕРАЦИИ (ПОСЛЕДОВАТЕЛЬНЫХ ПРИБЛИЖЕНИЙ)
В методе простой итерации если аii  0, то исходная система может быть преобразована к виду хi = bi + aij хj , i  j, т.е. из каждого уравнения последовательно выражают хi.
Здесь bi = Fi / аii; aij = - аij / аii.
Таким образом, в матричном виде имеем Х = В + AХ. Полученную систему будем решать методом последовательных приближений.
За нулевое приближение Х(0) можно принять матрицу В: Х(0)= = B, и далее, подставив найденные значения в исходную систему, получим Х (1) = В + A Х(0) .
При бесконечном повторении этой вычислительной схемы имеем
, где и будет искомое решение системы.
Условия сходимости итерационного процесса определяются теоремами, которые приводятся нами без доказательств.
Теорема 1. Для того, чтобы последовательность приближений Х(n) сходилась, достаточно, чтобы все собственные значения матрицы A были по модулю меньше единицы: | i | < 1, i = 1, 2, ..., n.
Теорема 2. Если требовать, чтобы последовательность Х(n) сходилась к при любом начальном приближении Х(0) , то условие теоремы 1 является необходимым.
Применение теорем 1 и 2 требует знания всех собственных значений матрицы A, нахождение которых является очень не простой задачей. Поэтому на практике ограничиваются более простой теоремой, дающей достаточные условия сходимости.
Теорема 3. Если для системы Х = В + AХ выполняется хотя бы одно из условий:
;
,
то итерационный процесс сходится к единственному решению этой системы независимо от выбора начального приближения.
Для многих приложений важно знать, какой является скорость сходимости процесса, и оценить погрешность полученного решения.
Теорема 4. Если какая-либо норма матрицы A, согласованная с рассматриваемой нормой вектора Х, меньше единицы, то верна следующая оценка погрешности приближения в методе простой итерации:
. В библиотеках стандартного математического обеспечения ЭВМ всегда можно найти несколько вариантов программы, выполняющей решение системы линейных уравнений методом простой итерации.
РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ МЕТОДОМ ЗЕЙДЕЛЯ
Этот метод относится к итерационным, имеет более быструю сходимость по сравнению с методом простых итераций, но часто приводит к громоздким вычислениям.
Метод Зейделя применяют в двух расчетных схемах.
Рассмотрим каноническую форму (для схемы итераций).
Пусть система приведена к виду Х = Вх + b. В схеме простой итерации следующее приближение Х(k +1) находится путем подстановки предыдущего приближения Х(k) в правую часть выражения X(k +1) = B X (k) + b.
Для удобства рассуждений полагаем, что левые части уравнений содержат хi (элементы матрицы X(k +1)) с возрастающими номерами, т.е. сначала х1, затем х2, х3, ..., хn. Тогда решение системы уравнений Х = Вх + b на очередной (k +1) итерации будет иметь вид
,
т.е. каждое очередное найденное приближение хi(k +1) сразу же используется для определения . Условия сходимости для итерационного метода Зейделя дают те же теоремы, что и в методе простых итераций.
Вторая форма метода Зейделя требует предварительного приведения системы к виду, когда все диагональные элементы отличны от нуля. Если разложить матрицу А на сумму двух матриц R + С, где R - нижняя диагональная матрица, а С - верхняя с нулями на главной диагонали, то исходную систему можно записать как
Ax = (R + C)x = R x(k +1) + C x(k) = B или x(k +1) = R -1B - R -1C x(k) и тогда становится ясно, что метод Зейделя в канонической форме равносилен методу простой итерации, примененному к системе X = R -1B - R -1C X.
МЕТОД РЕЛАКСАЦИИ
Систему линейных алгебраических уравнений
AX=f
каким либо образом приведем к виду X=BX+g.
Для итерационного процесса важным является не только наличие сходимости процесса, но и скорость этой сходимости. Метод релаксации является изменением метода Зейделя с целью увеличения сходимости итерационного процесса. В алгоритм построения итерационной последовательности X(1), X(2), ..., X(k), по методу релаксации вводят параметр релаксации ω, который управляет сходимостью итерационного процесса. Формула для итерационной последовательности метода релаксации имеет вид:
X(k+1) = (1-ω)Х(k) + ω[LХ(k+1) + (R+D)Х(k) + g]
где L - нижняя треугольная матрица,
R - верхняя треугольная матрица,
D - диагональная матрица.
ω=const - параметр релаксации. Обычно значения этого параметра выбираются следующим образом 0<ω<2, чтобы обеспечить сходимость итерационного процесса.
При ω=1 алгоритм соответствует методу Зейделя.
При 2>ω>1 алгоритм называют методом верхней релаксации, при ω<1 - метод нижней релаксации. Согласно компоненты вектора X(k+1) вычисляются по формулам:
i=1,...n
Первый достаточный признак сходимости метода релаксации. Если матрица В и параметр релаксации ω удовлетворяют условиям ,0<ω<1, метод релаксации сходится.
Предполагая диагональные элементы aii матрицы А исходной задачи отличными от нуля, приведем систему AX=f к канонической форме X=BХ+g, разрешив первое уравнение системы (1) относительно х1, второе уравнение - относительно х2 третье - относительно х3 и т.д.:
Полученная система имеет вид X=BХ+g, где
b11=0, bij=, g=, i, j=1,2,....,n; .
В этом случае алгоритм метода релаксации примет вид:
Второй достаточный признак сходимости метода релаксации. Если матрица А является симметричной (А=АТ) и положительно определенной (A>0), а параметр релаксации ω выбирается в интервале 0<ω<2, то метод релаксации сходится.
При использовании метода релаксации важной является проблема выбора оптимального значения параметра релаксации ω=ωopt, при котором достигается наивысшая скорость сходимости итераций. Для некоторых важных частных случаев эта проблема решена. При оптимальном выборе параметра ω метод релаксации сходится значительно быстрее методов простых итераций и Зейделя.
Документ
Категория
Рефераты
Просмотров
3 698
Размер файла
93 Кб
Теги
решение, метод, слау, итерационные
1/--страниц
Пожаловаться на содержимое документа