Математика \ Вычислительная математика

Численные методы решения систем линейных уравнений, страница 6

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

Сформулируем алгоритм метода итераций

1) Задана система линейных уравнений с невырожденной матрицей. Преобразуем систему линейных уравнений к виду: , где C – квадратная матрица, D – вектор. Причем системы являются эквивалентными и .

2) Выбираем произвольный вектор начального приближения: .

3) Строим последовательность: .

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

Пример 1

Построить и обосновать алгоритм решения системы линейных уравнений методом итераций с точностью :

Решение

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

Теорема

Если для матрицы А выполняются n неравенств , то матрица А невырожденная.

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

Эту теорему можно сформулировать и в другом виде, используя перенумерацию строк (столбцов). Определитель матрицы А не равен нулю, если в каждой строке (столбце) А имеется преобладающий элемент и эти элементы расположены в различных столбцах (строках).

В нашем случае:

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

, – эти системы эквивалентны.

Найдем С и докажем, что :

Вычислим первую норму С:

2. Выбираем вектор начального приближения:

Так как , то итерационный процесс: сходится для любого начального приближения.

3. Формула метода: .

4. Условие остановки итерационного процесса:

;

, следовательно, .

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

Пример 2

Оценить число шагов, необходимых для достижения точности , при решении системы линейных уравнений методом итераций.

Решение

Рассмотрим ту же систему линейных уравнений. Воспользуемся следствием из априорной оценкой погрешности. Условие на матрицу C выполнено:

, следовательно, метод итераций сходится и справедливо неравенство:

Мы вычисляли первую норму матрицы С, следовательно, и у вектора D также необходимо вычислять первую норму:

, следовательно, .

Оценку сложности алгоритма метода итераций(по времени) мы получаем из априорной оценки погрешности

На каждом шаге итерационного процесса мы выполняем О(n²) арифметических действий, где n – порядок матрицы, следовательно, общее число арифметических действий: kО(n²).

Для реализации алгоритма метода итераций на каждом шаге необходимо хранить матрицу С, , и D, следовательно, требуется памяти О(n²).

Если ||C|| < 1, то алгоритм метода итераций для решения система линейных уравнений является устойчивым по отношению к вычислительной погрешности.

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

1) Нет общего приема для перехода от матрицы А к матрице С таким образом, чтобы .

2) Метод итераций медленно сходится, если близка к 1.

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

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