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

Размещено на http://www.allbest.ru/

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

Метод итераций (метод последовательных приближений).

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

Эффективность применения приближенных методов зависят от выбора начального вектора и быстроты сходимости процесса.

Рассмотрим метод итераций (метод последовательных приближений). Пусть дана система n линейных уравнений с n неизвестными:

Ах=b,

Предполагая, что диагональные элементы a_ii 0 (i = 2,…, n), выразим x_i через первое уравнение систем x₂ - через второе уравнение и т.д. В результате получим систему, эквивалентную системе (14):

Обозначим ; , где i == 1, 2,…, n; j == 1,2,…, n. Тогда система (15) запишется таким образом в матричной форме

Решим систему (16) методом последовательных приближений. За нулевое приближение примем столбец свободных членов. Любое (k+1) - е приближение вычисляют по формуле

Если последовательность приближений x(0),…, x(k) имеет предел , то этот предел является решением системы (15), поскольку в силу свойства предела , т.е. .

Метод Зейделя.

Метод Зейделя представляет собой модификацию метода последовательных приближений. В методе Зейделя при вычислении (k+1) - го приближения неизвестного xi (i>1) учитываются уже найденные ранее (k+1) - е приближения неизвестных xi-1.

Пусть дана линейная система, приведенная к нормальному виду:

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

Таким образом, предполагая, что k-е приближения известны, методом Зейделя строим (k+1) - е приближение по следующим формулам:

где k=0,1,…, n

Метод Ланцоша.

Для решения СЛАУ высокого порядка, матрица, коэффициентов которой хранится в компактном нижеописанном виде, наиболее удобным итерационным методом является метод Ланцоша, схема которого имеет вид:

где

Преимуществом данного метода является его высокая скорость сходимости к точному решению. Кроме того, доказано, что он обладает свойством «квадратичного окончания», т.е. для положительно определенной матрицы можно гарантировано получить точное решение при количестве итераций . Размер требуемой памяти на каждой итерации не изменяется, т.к. не требует преобразование матрицы . В качестве критерия остановки данного итерационного процесса обычно используют соотношение

,

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

линейный уравнение ланцош приближенный

Среднеквадратичную разность необходимо контролировать при выполнении каждых k наперед заданных итераций.

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

Список литературы

Зенкевич О., Морган К. Конечные методы и аппроксимация // М.: Мир, 1980

Зенкевич О., Метод конечных элементов // М.: Мир, 1975

Стрэнг Г., Фикс Дж. Теория метода конечных элементов // М.: Мир, 1977

Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы // М.: наука, 1987

Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления // М.: Наука, 1984

Бахвалов Н.С. Численные методы // М.: Наука, 1975

Годунов С.К. Решение систем линейных уравнений // Новосибирск: Наука, 1980

Размещено на Allbest.ru