Учебное пособие 1395

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

Пример. Решить методом квадратных корней систему

Найдем коэффициенты матрицы L:

21

1.2.7. Метод прогонки

Еще одним методом, предназначенным для решения систем линейных уравнений с матрицами специального вида, является метод прогонки. Он эффективно применяется для решения систем с разреженной трехдиагональной матрицей вида

22

элементы b1,b2,...,bn , над ней — элементы c1,c2,...,cn 1, под ней — элементы a2,a3,...,an . Остальные элементы матрицы

равны нулю.

Как и метод Гаусса, метод прогонки включает в себя два этапа: прямой ход и обратный ход.

Прямой ход метода прогонки состоит в вычислении

Обратный ход состоит в последовательном вычислении неизвестных xi , начиная с xn :

xn dn anBn 1 ,

bn anAn 1

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

Пример. Используя метод прогонки, решить систему уравнений

23

24

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

1.3.1. Определение сходимости итерационных методов по норме матрицы коэффициентов

Норма матрицы – это некоторая скалярная числовая характеристика, которую ставят в соответствие матрице.

В задачах линейной алгебры наиболее часто используются три нормы:

1) первая норма квадратной матрицы A { ij}

2) бесконечная норма квадратной матрицы А

3) евклидова норма квадратной матрицы А

Для сходимости итерационных методов к единственно правильному решению необходимо, чтобы хотя бы для одной нормы выполнялось условие A 1.

1.3.2. Метод простой итерации

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

Для того чтобы применить метод простой итерации к решению систем уравнений AX B, необходимо преобразовать ее к виду

X X .

25

Самый простой способ приведения системы к виду, удобному для итераций, состоит в выделении диагональных элементов. Для этого из первого уравнения выразим x1, из второго - x2 и т.д. В результате получим систему

в которой на главной диагонали матрицы находятся нули, а остальные элементы вычисляются по формулам

системы уравнений, приведенной к виду, удобному для итераций, находим первое приближение

X(1) X(0) .

Подставляя найденное значение, получим следующее

приближение X(2) и т.д. В общем виде вычисления выполняются по формуле

X(k) X(k 1) ,

где k 1,2,... - номер итерации.

В развернутой форме записи эта формула выглядит так:

В качестве критерия окончания итерационного процесса часто используется критерий

26

где - требуемая точность вычислений.

Пример. С помощью метода простой итерации найдем решение системы уравнений с точностью 0.001

x1 2x2 3x3 0.

Приведем систему уравнений к виду, удобному для итераций. Для этого выразим неизвестные x1, x2 , x3 из

первого, второго и третьего уравнений, соответственно. Значения коэффициентов будет округлять до 3 знаков после

x3 0.333x1 0.667x2.

Вкачестве начального приближения возьмем вектор

свободных коэффициентов уравнений X(0) {1, 1.167, 0}. Подставим эти значения в уравнения для поиска следующего приближения:

x3 найденные значения x1(1) , x(21) , x(31) , получим значения неизвестных x1(2), x(22), x(32) и т.д. Для удобства занесем результаты вычислений в табл. 3.

27

Таблица 3

Как видно из таблицы, решение достаточной дочности получено на 9-й итерации, поскольку выполнилось условие xi(k) x(ik 1) для всех неизвестных xi .

1.3.3. Метод Гаусса-Зейделя

Метод Гаусса-Зейделя является модификацией метода простой итерации. Основной смысл модификации заключается

в том, что при вычислении очередных значений x(ik)

используются не x(ik 1) , а уже найденные на текущей итерации значения x(ik) .

В формализованном виде метод Гаусса-Зейделя записывается следующим образом:

предыдущей итерации. Для определения x(2k 1) берется уже найденное на текущей итерации значение x1(k 1) и неизвестные

28

x(3k),...,x(nk) , вычисленные на предыдущем шаге. Для

нахождения значения x(nk 1) подставляются уже полученные

величины x1(k 1),...,x(nk 11).

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

Пример. Решить систему уравнений из предыдущего примера с помощью метода Гаусса-Зейделя.

Перепишем систему, уже приведенную к виду,

x3 0.333x1 0.667x2.

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

Здесь при вычислении x1(1) использовались значения x(20) и x3(0) . Для нахождения x(21) подставили неизвестные x1(1) и x3(0) . При определении x3(1) брали величины x1(1) и x(21) .

Занесем данные вычислений в табл. 4.

29

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

Контрольные вопросы

1.На какие группы делятся численные методы для решения систем линейных уравнений? Какие преимущества и недостатки есть у каждой группы методов?

2.В чем заключаются метод Крамера и метод обратной матрицы? Какие недостатки есть у этих методов?

3.Из каких этапов состоит метод Гаусса? В чем они заключаются? Какие модификации есть у метода Гаусса?

4.Как можно использовать метод Гаусса для вычисления определителей и обратных матриц?

5.Какие методы существуют для решения систем уравнений с матрицами специального вида?

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

Задания для самостоятельной работы

Решить систему линейных уравнений с помощью метода Гаусса:

2x1 x2 0.1x3 3.7,

1.1.0.4x1 0.5x2 4x3 13.4,0.3x1 x2 x3 1.3.

30