Решение систем методом Зейделя

Тема. Решение систем линейных алгебраических уравнений

1. Решение систем линейных уравнений методом итераций

Дана система линейных уравнений

(1)

Или в матричном виде:

АХ = В (2)

где

, , .

Пусть диагональные элементы главной матрицы системы для всех i.

Выразим х₁ из первого уравнения системы, х₂ - из второго уравнения и т.д. В результате получим систему, эквивалентную системе (1):

(3)

Введя обозначения: .

Тогда система (3) запишется в виде:

(3′)

Система (3′) называется системой, приведенной к нормальному виду, и вводя обозначения:

Запишем систему (3′) в матричной форме:

= + · (4)

Решим систему (4) методом последовательных приближений. За нулевое приближение примем столбец свободных членов:

= - нулевое приближение, далее строим матрицы - столбцы:

первое приближение: = + · ;

второе приближение: = + · и т.д.

Любое (k + 1 )-е приближение вычисляется по формуле:

(k = 0, 1, …, n) (5)

Если последовательность приближений , , …., имеет предел, то этот предел является решением системы (3).

Условие сходимости итерационного процесса.

Пусть дана приведенная к нормальному виду система линейных уравнений . Итерационный процесс и его сходимость зависят от величины элементов матрица следующим образом: если сумма модулей элементов строк или сумма модулей элементов столбцов меньше единицы, то процесс итерации для данной системы сходится к единственному решению независимо от выбора начального вектора.

Следовательно, условие сходимости можно записать так:

или

Следствия.

1) Процесс итерации заведомо сходится, если элементы матрицы удовлетворяют неравенству , где n - число неизвестных данной системы.

2) Сходимость итерационного процесса связана с нормами матрицы следующими соотношениями: (*)

либо (**)

либо (***)

то процесс итерации линейной системы сходится к единственному решению.

Оценка погрешности приближенного процесса метода итерации.

Если задана допустимая оценка погрешности ε и Х_i - вектор точных значений неизвестных линейной системы, а есть k-е приближение значений неизвестных, вычисленное методом итерации, то для оценки погрешности метода применяется формула:

(6)

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

Т.е. , , логарифмируя, определим k.

Пример.

Дана система уравнений

1) Записать систему в матричном виде и решить: а) методом Крамера;

б) методом Гаусса;

2) Привести систему к нормальному виду, записать ее в матричном виде и решить методом итераций, с точностью ε = 10^-3.

Решение.

1) Ведем матрицы А = ; ; , тогда система в матричном виде А·Х = В.

а) Метод Крамера. Главный определитель системы: ; дополнительные определители системы:

Т.о. ; .

б) Метод Гаусса. Расширенная матрица системы: Х ;

2) Приведем систему к нормальному виду, т.е выразим х₁ и х₂ соответственно из первого и второго уравнений:

или

Введем матрицы , ,

Вычислим нормы матрицы :

< 1 (суммы по строке)

< 1 (сумма по столбцам)

< 1

Используя норму по формуле (6)

= =

логарифмируем

; ; ;

, но как правило, теоретическая оценка числа итераций, необходимых для обеспечения заданной точности, практически оказывается завышенной.

В качестве нулевого приближения примем столбец свободных членов:

Х⁽⁰⁾ = =

Первое приближение:

Х⁽¹⁾ = = + · = + =

Второе приближение:

Х⁽²⁾ = = + · = + =

Третье приближение:

Х⁽³⁾ = = + · = + =

Четвертое приближение:

Х⁽⁴⁾ = = + · = + =

Пятое приближение:

Х⁽⁵⁾ = = + · = + =

Шестое приближение:

Х⁽⁶⁾ = = + · = + =

Таким образом, приближенное решение:

= =

Решение систем методом Зейделя

Модификация метода последовательных приближений: при вычислении -го приближения неизвестного х_i учитывается уже найденное ранее -е приближение неизвестных x₁, x₂, …, x_i-1.