Лабы Антонова. Тема Решение задач вычислительными методами. Основные понятия
 Скачать 1.35 Mb.
|
|
Тема 3. Решение систем линейных алгебраических уравнений 3.1. Постановка задачи Требуется найти решение системы линейных уравнений: a 11 x 1 + a 12 x 2 + a 13 x 3 + … + a 1n x n = b 1 a 21 x 1 + a 22 x 2 + a 23 x 3 + … + a 2n x n = b 2 a 31 x 1 + a 32 x 2 + a 33 x 3 + … + a 3n x n = b 3 (3.1) ……………………………………………. a n1 x 1 + a n2 x 2 + a n3 x 3 + … + a nn x n = b n или в матричной форме: Ax = b, (3.2) где a 11 a 12 a 13 … a 1n x 1 b 1 a 21 a 22 a 23 … a 2n x 2 b 2 A = a 31 a 32 a 33 … a 3n , x = x 3 , b = b 3 ……………………… … … a n1 a n2 a n3 … a nn x n b n По правилу Крамера система n линейных уравнений имеет единственное решение, если определитель системы отличен от нуля (det A 0) и значение каждого из неизвестных определяет- ся следующим образом: x j = A A j det det , j = 1, …, n, (3.3) где det A j – определитель матрицы, получаемой заменой j-го столбца матрицы A столбцом правых частей b. Непосредственный расчет определителей для больших n является очень трудоемким по сравнению с вычислительными методами. Известные в настоящее время многочисленные приближенные методы решения систем ли- нейных алгебраических уравнений распадаются на две большие группы: прямые методы и методы итераций. Прямые методы всегда гарантируют получение решения, если оно существуют, однако, для больших n требуется большое количество операций, и возникает опасность накопления погрешно- стей. Этого недостатка лишены итерационные методы, но зато они не всегда сходятся и могут применяться лишь для систем определенных классов. Среди прямых методов наиболее распространенным является метод исключения Гаусса и его модификации, Наиболее распространенными итерационными методами является метод про- стых итераций Якоби и метод Зейделя. Эти методы будут рассмотрены в следующих разделах. 3.2. Метод исключения Гаусса. Схема единственного деления Основная идея метода исключений Гаусса состоит в том, что система уравнений (3.1) при- водится к эквивалентной ей системе с верхней треугольной матрицей (прямой ход исключений), а затем неизвестные вычисляются последовательной подстановкой (обратный ход исключений). Рассмотрим сначала простейший метод исключения Гаусса, называемый схемой единствен- ного деления. Прямой ход состоит из n – 1 шагов. На первом шаге исключается переменная x 1 из всех уравнений, кроме первого. Для этого нужно из второго, третьего, …, n-го уравнений вычесть пер- вое, умноженное на величину m 1 i = 11 1 a a i , i = 2, 3, …, n. (3.4) При этом коэффициенты при x 1 обратятся в нуль во всех уравнениях, кроме первого. Введем обозначения: a 1 ij = a ij – m 1 i a 1j , b 1 i = b i – m 1 i b 1 . (3.5) Легко убедиться, что для всех уравнений, начиная со второго, a 1 1 i = 0, i = 2, 3, …, n. Преоб- разованная система запишется в виде: a 11 x 1 + a 12 x 2 + a 13 x 3 + … + a 1n x n = b 1 a 1 22 x 2 + a 1 23 x 3 + … + a 1 2n x n = b 1 2 a 1 32 x 2 + a 1 33 x 3 + … + a 1 3n x n = b 1 3 (3.6) ……………………………………………. a 1 2 n x 2 + a 1 3 n x 3 + … + a 1 nn x n = b 1 n Все уравнения (3.6), кроме первого, образуют систему (n – 1)-го порядка. Применяя к ней ту же процедуру, мы можем исключить из третьего, четвертого, …, n-го уравнений переменную x 2 Точно так же исключаем переменную x 3 из последних n – 3 уравнений. На некотором k-ом шаге в предположении, что главный элемент k-ого шага a 1 k k k 0, пере- менная x k исключается с помощью формул: m k i = 1 1 k kk k ik a a , a k ij = a 1 k ij – m k i a 1 k k j , b k i = b 1 k i – m k i b 1 k k , i, j = k + 1, k +2, …, n. (3.7) Индекс k принимает значения 1, 2, …, n – 1. При k = n – 1 получим треугольную систему: a 11 x 1 + a 12 x 2 + a 13 x 3 + … + a 1n x n = b 1 a 1 22 x 2 + a 1 23 x 3 + …+ a 1 2n x n = b 1 2 a 2 33 x 3 + …+ a 2 3n x n = b 2 3 (3.8) …………..…………………………. a 1 n nn x n = b 1 n n с треугольной матрицей A n Приведение системы (3.1) к треугольному виду (3.8) составляет прямой ход метода Гаусса. При использовании метода Гаусса нет необходимости в предварительном обосновании су- ществования и единственности решения (т. е. доказательства, что det A 0). Если на k-ом шаге все элементы a 1 k ik (i = k, k +1, …, n) окажутся равными нулю, то система (3.1) не имеет единственного решения. Обратный ход состоит в вычислении переменных. Из последнего уравнения (3.8) определя- ем x n.. . Подставляя его в предпоследнее уравнение, находим x n-1 , и т. д. Общие формулы имеют вид: x n = 1 1 n nn n n a b , x k = 1 1 k kk a (b 1 k k - a 1 1 , k k k x k+1 - a 1 2 , k k k x k+2 - … - a 1 k k n x n ), k = n – 1, n – 2, …, 1 (3.9) Трудоемкость метода. Для реализации метода исключения Гаусса требуется примерно 2/3n 3 операций для прямого хода и n 2 операций для обратного хода. Таким образом, общее количе- ство операций составляет примерно 2/3n 3 + n 2 Пример 3.1. Применим метод исключения Гаусса по схеме единственного деления для решения системы уравнений: 2.0x 1 + 1.0x 2 – 0.1x 3 + 1.0x 4 = 2.7 0.4x 1 + 0.5x 2 + 4.0x 3 – 8.5x 4 = 21.9 0.3x 1 – 1.0x 2 + 1.0x 3 + 5.2x 4 = –3.9 (3.10) 1.0x 1 + 0.2x 2 + 2.5x 3 – 1.0x 4 = 9.9 Будем делать округление чисел до четырех знаков после десятичной точки. Прямой ход. 1-ый шаг. Вычислим множители: m 1 2 = 11 21 a a = 0 2 4 0 = 0.2; m 1 3 = 11 31 a a = 0 2 3 0 = 0.15; m 1 4 = 11 41 a a = 0 2 0 1 = 0.5. Вычитая из второго, третьего и четвертого уравнений системы (3.10) первое уравнение, умноженное соответственно на m 1 2 , m 1 3 , m 1 4 , получим новую систему: 2.0x 1 + 1.0x 2 – 0.1x 3 + 1.0x 4 = 2.7 0.3x 2 + 4.02x 3 – 8.70x 4 = 21.36 –1.15x 2 + 1.015x 3 + 5.05x 4 = –4.305 (3. 11) –0.30x 2 + 2.55x 3 –1.50x 4 = 8.55 2-ой шаг. Вычислим множители: m 2 3 = 1 22 1 32 a a = 3 0 15 1 = – 3.83333; m 2 4 = 1 22 1 42 a a = 3 0 30 0 = –1.0. Вычитая из третьего и четвертого уравнений системы (3.11) второе уравнение, умноженное соответственно на m 2 3 и m 2 4 , приходим к системе: 2.0x 1 + 1.0x 2 – 0.1x 3 + 1.0x 4 = 2.7 0.3x 2 + 4.02x 3 – 8.70x 4 = 21.36 16. 425x 3 – 28.300x 4 = 77.575 (3.12) 6.570x 3 –10.200x 4 = 29.910 3-ий шаг. Вычислим множитель: m 3 4 = 2 33 2 43 a a = 425 16 570 6 = 0.4. Вычитая из четвертого уравнения системы (3.12) третье, умноженное на m 3 4 , приведем си- стему к треугольному виду: 2.0x 1 + 1.0x 2 – 0.1x 3 + 1.0x 4 = 2.7 0.3x 2 + 4.02x 3 – 8.70x 4 = 21.36 16. 425x 3 – 28.300x 4 = 77.575 (3.13) 1.12x 4 = –1.12 Обратный ход. Из последнего уравнения системы (3.13) находим x 4 = 1.000. Подставляя значение x 4 в третье уравнение, получим x 3 = 2.000. Подставляя найденные значения x 4 и x 3 во вто- рое уравнение, найдем x 2 = 3.000. Наконец, из первого уравнения, подставив в него найденные зна- чения x 4 , x 3 и x 2 , вычислим x 1 = –1.000. Итак система (3.10) имеет следующее решение: x 1 = 1.000, x 2 = 2.000, x 3 = 3.000, x 4 = – 1.000. 3.3. Метод исключения Гаусса с выбором главного элемента по столбцу Хотя метод Гаусса является точным методом, ошибки округления могут привести к суще- ственным погрешностям результата. Кроме того исключение по формулам (3.7) нельзя проводить, если элемент главной диагонали a 1 k k k равен нулю. Если элемент a 1 k k k мал, то велики ошибки округ- ления при делении на этот элемент. Для уменьшения ошибок округления применяют метод исклю- чения Гаусса с выбором главного элемента по столбцу. Прямой ход так же, как и для схемы един- ственного деления, состоит из n – 1 шагов. На первом шаге прежде, чем исключать переменную x 1 , уравнения переставляются так, чтобы в левом верхнем углу был наибольший по модулю коэффи- циент a i1 , i = 1, 2, …, n. В дальнейшем, на k-м шаге, прежде, чем исключать переменную x k , урав- нения переставляются так, чтобы в левом верхнем углу был наибольший по модулю коэффициент a ik , i = k, k + 1, …, n. После этой перестановки исключение переменной x k производят, как в схеме единственного деления. Трудоемкость метода. Дополнительные действия по выбору главных элементов требуют примерно n 2 операций, что практически не влияет на общую трудоемкость метода. Пример 3.2. Применим метод исключения Гаусса с выбором главного элемента по столбцу для решения системы уравнений (3.10) из примера 3.1. Прямой ход. 1-ый шаг. Так как коэффициент a 11 = 2.0 наибольший из коэффициентов первого столбца, перестановки строк не требуется и 1-ый шаг пол- ностью совпадает с 1-ым шагом примера 3.1. Из второго, третьего и четвертого уравнений исклю- чается переменная x 1 и система приводится к виду (3.11). 2-ой шаг. Наибольший по модулю коэффициент при x 2 в системе (3.11) a 1 32 = –1.15. Поэто- му переставим уравнения следующим образом: 2.0x 1 + 1.0x 2 – 0.1x 3 + 1.0x 4 = 2.7 –1.15x 2 + 1.015x 3 + 5.05x 4 = –4.305 (3.14) 0.3x 2 + 4.02x 3 – 8.70x 4 = 21.36 –0.30x 2 + 2.55x 3 –1.50x 4 = 8.55 Вычислим множители: m 2 3 = 1 22 1 32 a a = 15 1 3 0 = –0.26087 m 2 4 = 1 22 1 42 a a = 15 1 30 0 = 0.26087. Вычитая из третьего и четвертого уравнений системы (3.14) второе уравнение, умноженное соответственно на m 2 3 и m 2 4 , приходим к системе: 2.0x 1 + 1.0x 2 – 0.1x 3 + 1.0x 4 = 2.7 –1.15x 2 + 1.015x 3 + 5.05x 4 = –4.305 (3.15) 4.28478x 3 – 7.38261x 4 = 20.23696 2.28522x 3 – 2.81739x 4 = 9.67305 3-ий шаг. Вычислим множитель: m 3 4 = 2 33 2 43 a a = 425 16 4 28522 2 = 0.53333. Вычитая из четвертого уравнения системы (3.15) третье, умноженное на m 3 4 , приведем си- стему к треугольному виду: 2.0x 1 + 1.0x 2 – 0.1x 3 + 1.0x 4 = 2.7 –1.15x 2 + 1.015x 3 + 5.05x 4 = –4.305 (3.16) 4.28478x 3 – 7.38261x 4 = 20.23696 1.11998x 4 = –1.11998 Обратный ход. Обратный ход полностью совпадает с обратным ходом примера 3.1. Реше- ние системы имеет вид: x 1 = 1.000, x 2 = 2.000, x 3 = 3.000, x 4 = – 1.000. 3.4. Вычисление определителя методом исключения Гаусса Из курса линейной алгебры известно, что определитель треугольной матрицы равен произ- ведению диагональных элементов. В результате метода исключений Гаусса система линейных уравнений (3.2) с квадратной матрицей A приводится к эквивалентной ей системе (3.8) с треуголь- ной матрицей A n . Поэтому det A = (–1) s det A n , где s – число перестановок строк, (s = 0, если использовался метод Гаусса по схеме единственного деления).Таким образом, det A = (–1) s a 11 a 1 22 a 2 33 …a 1 n nn . (3.17) Итак, для вычисления определителя det A необходимо выполнить процедуру прямого хода в методе Гаусса для системы уравнений Ax = 0, затем найти произведение главных элементов, стоя- щих на диагонали треугольной матрицы и умножить это произведение на (–1) s , где s – число пере- становок строк. Пример 3.3. Вычислим определитель det A = 2.0 1.0 0.1 1.0 0.4 0.5 4.0 8.5 0.3 1.0 1.0 5.2 1.0 0.2 2.5 1.0 Данный определитель совпадает с определителем системы, рассмотренной в примере 3.1. Он равен произведению диагональных элементов треугольной матрицы (3.13): det A = 2.0 0.30 16.425 1.12 = 11.0376. Если же обратиться к примеру 3.2, то, учитывая, что была одна перестановка строк, т.е. s = 1, получим: det A = (–1) 2.0 (–1.15) 4.28478 1.11998 = 11.0375. 3.5. Вычисление обратной матрицы методом исключения Гаусса Обратной матрицей к матрице A называется матрица A -1 , для которой выполнено соотно- шение: A A -1 = E, (3.18) где E – единичная матрица: 1 0 0 … 0 0 1 0 … 0 E = 0 0 1 … 0 . (3.19) ……………. 0 0 0 … 1 Квадратная матрица A называется невырожденной, если det A 0. Всякая невырожденная матрица имеет обратную матрицу. Вычисление обратной матрицы можно свести к рассмотренной выше задаче решения си- стемы уравнений. Пусть A – квадратная невырожденная матрица порядка n: a 11 a 12 a 13 … a 1n a 21 a 22 a 23 … a 2n A = a 31 a 32 a 33 … a 3n ……………………… a n1 a n2 a n3 … a nn и A -1 – ее обратная матрица: x 11 x 12 x 13 … x 1n x 21 x 22 x 23 … x 2n A -1 = x 31 x 32 x 33 … x 3n ……………………… x n1 x n2 x n3 … x nn Используя соотношения (3.18), (3. 19) и правило умножения матриц, получим систему из n 2 уравнений с n 2 переменными x ij , i, j = 1, 2, …, n. Чтобы получить первый столбец матрицы E, нужно почленно умножить каждую строку матрицы A на первый столбец матрицы A -1 и приравнять полу- ченное произведение соответствующему элементу первого столбца матрицы E. В результате полу- чим систему уравнений: a 11 x 11 + a 12 x 21 + a 13 x 31 + … + a 1n x n1 = 1 a 21 x 11 + a 22 x 21 + a 23 x 31 + … + a 2n x n1 = 0 a 31 x 11 + a 32 x 21 + a 33 x 31 + … + a 3n x n1 = 0(3.20) ………………………………………………. a n1 x 11 + a n2 x 21 + a n3 x 31 + … + a nn x n1 = 0 Аналогично, чтобы получить второй столбец матрицы E, нужно почленно умножить каж- дую строку матрицы A на второй столбец матрицы A -1 и приравнять полученное произведение со- ответствующему элементу второго столбца матрицы E. В результате получим систему уравнений: a 11 x 12 + a 12 x 22 + a 13 x 32 + … + a 1n x n2 = 0 a 21 x 12 + a 22 x 22 + a 23 x 32 + … + a 2n x n2 = 1 a 31 x 12 + a 32 x 22 + a 33 x 32 + … + a 3n x n2 = 0(3.21) ………………………………………………. a n1 x 12 + a n2 x 22 + a n3 x 32 + … + a nn x n2 = 0 и т. д. Всего таким образом получим n систем по n уравнений в каждой системе, причем все эти си- стемы имеют одну и ту же матрицу A и отличаются только свободными членами. Приведение мат- рицы A к треугольной по формулам (3.7) делается при этом только один раз. Затем по последней из формул (3.7) преобразуются все правые части, и для каждой правой части делается обратный ход. Пример 3.4. Вычислим обратную матрицу A -1 для матрицы A = 1.8 –3.8 0.7 –3.7 0.7 2.1 –2.6 –2.8 7.3 8.1 1.7 –4.9 1.9 –4.3 –4.3 –4.7 По формулам (3.7) за три шага прямого хода преобразуем матрицу A в треугольную матрицу 1.8 –3.8 0.7 –3.7 0 3.57778 –2.87222 –1.36111 0 0 17.73577 19.04992 0 0 0 5.40155 Далее, применим процедуру обратного хода четыре раза для столбцов свободных членов, преобразованных по формулам (3.7) из столбцов единичной матрицы: 1 0 0 0 0 1 0 0 0 , 0 , 1 , 0 . 0 0 0 1 Каждый раз будем получать столбцы матрицы A -1 . Опустив промежуточные вычисления, приведем окончательный вид матрицы A -1 : –0.21121 –0.46003 0.16248 0.26956 –0.03533 0.16873 0.01573 –0.08920 0.23030 0.04607 –0.00944 –0.19885 . –0.29316 –0.38837 0.06128 0.18513 3.6. Метод простой итерации Якоби Метод Гаусса обладает довольно сложной вычислительной схемой. Кроме того, при вычис- лениях накапливается ошибка округления, что может привести к недостаточно точному результату. Рассмотрим метод простой итерации Якоби, свободный от этих недостатков, хотя требующий при- ведения исходной системы уравнений к специальному виду. Для того, чтобы применить метод простой итерации, необходимо систему уравнений Ax = b (3.22) с квадратной невырожденной матрицей A привести к виду x = Bx + c, (3.23) где B – квадратная невырожденная матрица с элементами b ij , i, j = 1, 2, …, n, x – вектор-столбец не- известных x i , c – вектор-столбец с элементами c i , i = 1, 2, …, n. Существуют различные способы приведения системы (3.22) к виду (3.23). Рассмотрим самый простой. Представим систему (3.22) в развернутом виде: a 11 x 1 + a 12 x 2 + a 13 x 3 + … + a 1n x n = b 1 a 21 x 1 + a 22 x 2 + a 23 x 3 + … + a 2n x n = b 2 a 31 x 1 + a 32 x 2 + a 33 x 3 + … + a 3n x n = b 3 (3.24) ……………………………………………. a n1 x 1 + a n2 x 2 + a n3 x 3 + … + a nn x n = b n Из первого уравнения системы (3.24) выразим неизвестную x 1 : x 1 = a 1 11 (b 1 – a 12 x 2 – a 13 x 3 – … – a 1n x n ), из второго уравнения – неизвестную x 2 : x 2 = a 1 22 (b 2 – a 21 x 1 – a 23 x 3 – … – a 2n x n ), и т. д. В результате получим систему: x 1 = b 12 x 2 + b 13 x 3 + … + b 1,n-1 x n-1 + b 1n x n + c 1 x 2 = b 21 x 1 + b 23 x 3 + … + b 2,n-1 x n-1 + b 2n x n + c 2 x 3 = b 31 x 1 + b 32 x 2 + … + b 3,n-1 x n-1 + b 3n x n + c 3 (3.25) ………………………………………………………………….. x n = b n1 x 1 + b n2 x 2 + b n3 x 3 + b n,n-1 x n-1 + c n Матричная запись системы (3.25) имеет вид (3.23). На главной диагонали матрицы B нахо- дятся нулевые элементы, а остальные элементы вычисляются по формулам: b ij = ii ij a a , c i = ii i a b , i, j = 1,2, …n, i j. (3.26) Очевидно, что диагональные элементы матрицы A должны быть отличны от нуля. Выберем произвольно начальное приближение Обычно в качестве первого приближения бе- рут x 0 i = c i или x 0 i = 0. Подставим начальное приближение в правую часть (3.25). Вычисляя левые части, получим значения x 1 1 , x 1 2 , …, x 1 n . Продолжая этот процесс дальше, получим последователь- ность приближений, причем (k + 1)-е приближение строится следующим образом: x 1 1 k = b 12 x k 2 + b 13 x k 3 + … + b 1,n-1 x k n 1 + b 1n x k n + c 1 x 1 2 k = b 21 x k 1 1 + b 23 x k 3 + … + b 2,n-1 x k n 1 + b 2n x k n + c 2 x 1 3 k = b 31 x k 1 + b 32 x k 2 + … + b 3,n-1 x k n 1 + b 3n x k n + c 3 (3.27) ………………………………………………………………………………….. x 1 k n = b n1 x k 1 + b n2 x k 2 + b n3 x k 3 + b n,n-1 x k n 1 + c. n Система (3.27) представляет собой расчетные формулы метода простой итерации Якоби. Сходимость метода простой итерации. Известно следующее достаточное условие сходи- мости метода простой итерации Якоби. Если элементы матрицы A удовлетворяют условию: |a ii | > n i j j ij a , 1 | | , i = 1, 2, …, n. (3.28) то итерационная последовательность x k сходится к точному решению x * Условие (3.28) называют условием преобладания диагональных элементов матрицы A, так как оно означает, что модуль диагонального элемента i-ой строки больше суммы модулей осталь- ных элементов этой строки, i = 1, 2, …, n. Необходимо помнить, что условие сходимости (3.28) является лишь достаточным. Его вы- полнение гарантирует сходимость метода простых итераций, но его невыполнение, вообще говоря, не означает, что метод расходится. Справедлива следующая апостериорная оценка погрешности: max|x * i - x k i | 1 max|x 1 k i – x k i |, i = 1, 2, …, n, (3.29) где = max |b ij | i, j = 1, 2, …, n. Правую часть оценки (3.29) легко вычислить после нахождения очередного приближения. Критерий окончания. Если требуется найти решение с точностью , то в силу (3.29) итера- ционный процесс следует закончить как только на (k+1)-ом шаге выполнится неравенство: 1 max|x 1 k i – x k i | < , i = 1, 2, …, n. (3.30) Поэтому в качестве критерия окончания итерационного процесса можно использовать нера- венство max|x 1 k i – x k i | < 1 , i = 1, 2, …, n. (3.31) где 1 = 1 . Если выполняется условие 2 1 , то можно пользоваться более простым критерием окон- чания: max|x 1 k i – x k i | < , i = 1, 2, …, n. (3.32) В других случаях использование критерия (3.32) неправомерно и может привести к прежде- временному окончанию итерационного процесса. Пример 3.5. Применим метод простой итерации Якоби для решения системы уравнений 20.9x 1 + 1.2 x 2 + 2.1x 3 + 0.9x 4 = 21.70 1.2x 1 + 21.2 x 2 + 1.5x 3 + 2.5x 4 = 27.46 2.1x 1 + 1.5 x 2 + 19.8x 3 + 1.3x 4 = 28.76 (3.33) 0.9x 1 + 2.5 x 2 + 1.3x 3 + 32.1x 4 = 49.72 Заметим, что метод простой итерации сходится, т. к. выполняется условие преобладания диагональных элементов (3.28): |20.9| > |1.2 + 2.1 + 0.9|, |21.2| > |1.2| + |1.5| + |2.5|, |19.8| > |2.1| + |1.5| + |1.3|, |32.1| > |0.9| + |2.5| + |1.3|. Пусть требуемая точность = 10 -3 . Вычисления будем проводить с четырьмя знаками после десятичной точки. Приведем систему к виду (3.25): x 1 = – 0.0574 x 2 – 0.1005x 3 – 0.0431x 4 + 1.0383 x 2 = –0.0566x 1 – 0.0708x 3 – 0.1179x 4 + 1.2953 x 3 = –0.1061x 1 – 0.0758 x 2 – 0.0657x 4 + 1.4525 (3.34) x 4 = –0.0280x 1 – 0.0779 x 2 – 0.0405x 3 + 1.5489 Величина = max |b ij |, i, j = 1, 2, 3,4 равна 0.1179, т. е. выполняется условие 2 1 , и можно пользоваться критерием окончания итерационного процесса (3.32). В качестве начального приближения возьмем элементы столбца свободных членов: x 0 1 = 1.0383, x 0 2 = 1.2953, x 0 3 = 1.4525, x 0 4 = 1.5489. (3.35) Вычисления будем вести до тех пор, пока все величины |x 1 k i – x k i |, i = 1, 2, 3, 4, а следова- тельно, и max|x 1 k i – x k i | не станут меньше = 10 -3 Последовательно вычисляем: при k = 1 x 1 1 = – 0.0574x 0 2 – 0.1005x 0 3 – 0.0431x 0 4 + 1.0383 = 0.7512 x 1 2 = –0.0566x 0 1 – 0.0708x 0 3 – 0.1179x 0 4 + 1.2953 = 0.9511 x 1 3 = –0.1061x 0 1 – 0.0758 x 0 2 – 0.0657x 0 4 + 1.4525 = 1.1423 x 1 4 = –0.0280x 0 1 – 0.0779x 0 2 – 0.0405x 0 3 + 1.5489 = 1.3601 при k = 2 x 2 1 = 0.8106, x 2 2 = 1.0118, x 2 3 = 1.2117, x 2 4 = 1.4077. при k = 3 x 3 1 = 0.7978, x 3 2 = 0.9977, x 3 3 = 1.1975, x 3 4 = 1.3983. при k = 4 x 4 1 = 0.8004, x 4 2 = 1.0005, x 4 3 = 1.2005, x 4 4 = 1.4003. Вычисляем модули разностей значений x k i при k = 3 и k = 4: | x 4 1 – x 3 1 | = 0.026, | x 4 2 – x 3 2 | = 0.028, | x 4 3 – x 3 3 | = 0.0030, | x 4 4 – x 3 4 | = 0.0020. Так как все они больше заданной точности = 10 -3 , продолжаем итерации. При k = 5 x 5 1 = 0.7999, x 5 2 = 0.9999, x 5 3 = 1.1999, x 5 4 = 1.3999. Вычисляем модули разностей значений x k i при k = 4 и k = 5: | x 5 1 – x 4 1 | = 0.0005, | x 5 2 – x 4 2 | = 0.0006, | x 5 3 – x 4 3 | = 0.0006, | x 5 4 – x 4 4 | = 0.0004. Все они меньше заданной точности = 10 -3 , поэтому итерации заканчиваем. Приближенным решением системы являются следующие значения: x 1 0.7999, x 2 0.9999, x 3 1.1999, x 4 1.3999. Для сравнения приведем точные значения переменных: x 1 = 0.8, x 2 = 1.0, x 3 = 1.2, x 4 = 1.4. 3.7. Метод Зейделя Модификацией метода простых итераций Якоби можно считать метод Зейделя. В методе Якоби на (k+1)-ой итерации значения x 1 k i , i = 1, 2, …, n. вычисляются подстанов- кой в правую часть (3.27) вычисленных на предыдущей итерации значений x k i . В методе Зейделя при вычислении x 1 k i используются значения x 1 1 k , x 1 2 k , x 1 1 k i , уже найденные на (k+1)-ой итерации, а не x k 1 , x k 2 , …, x k i 1 , как в методе Якоби, т.е. (k + 1)-е приближение строится следующим образом: x 1 1 k = b 12 x k 2 + b 13 x k 3 + … + b 1,n-1 x k n 1 + b 1n x k n + c 1 x 1 2 k = b 21 x 1 1 k + b 23 x k 3 + … + b 2,n-1 x k n 1 + b 2n x k n + c 2 x 1 3 k = b 31 x 1 1 k + b 32 x 1 2 k + … + b 3,n-1 x k n 1 + b 3n x k n + c 3 (3.36) ………………………………………………………………………………….. x 1 k n = b n1 x 1 1 k + b n2 x x 1 2 k + b n3 x x 1 3 k + … + b n,n-1 x 1 1 k n + c. n Формулы (3.36) являются расчетными формулами метода Зейделя. Введем нижнюю и верхнюю треугольные матрицы: 0 0 0 … 0 0 b 12 b 13 … b 1n b 21 0 0 … 0 00 b 23 … b 2n B 1 = b 31 b 32 0 … 0 и B 2 = 00 0 … b 3n . ……………………… …..……………… b n1 b n2 b n3 …0 0 0 0 … 0 Матричная запись расчетных формул (3.36) имеет вид: x k+1 = B 1 x k+1 + B 2 x k + c.(3.37) Так как B = B 1 + B 2 , точное решение x * исходной системы удовлетворяет равенству: x * = B 1 x * + B 2 x * + c.(3.38) Сходимость метода Зейделя. Достаточным условием сходимости метода Зейделя является выполнение неравенства: = max |b ij |,< 1, i, j = 1, 2, …, n. (3.39) Неравенство (3.39) означает, что для сходимости метода Зейделя достаточно, чтобы макси- мальный по модулю элемент матрицы B был меньше единицы. Если выполнено условие (3.39), то справедлива следующая апостериорная оценка погрешно- сти: max|x * i - x k i | 1 2 max|x 1 k i – x k i | i = 1, 2, …, n, (3.40) где – максимальный элемент матрицы B, 2 – максимальный элемент матрицы B 2 . Правую часть оценки (3.40) легко вычислить после нахождения очередного приближения. Критерий окончания. Если требуется найти решение с точностью , то в силу (3.37) итера- ционный процесс следует закончить как только на (k+1)-ом шаге выполнится неравенство: 1 2 max|x 1 k i – x k i | < , i = 1, 2, …, n. (3.41) Поэтому в качестве критерия окончания итерационного процесса можно использовать нера- венство max|x 1 k i – x k i | < 1 , i = 1, 2, …, n. (3.42) где 1 = 2 1 . Если выполняется условие 2 1 , то можно пользоваться более простым критерием окон- чания: max|x 1 k i – x k i | < , i = 1, 2, …, n. (3.43) Метод Зейделя как правило сходится быстрее, чем метод Якоби. Однако возможны ситуа- ции, когда метод Якоби сходится, а метод Зейделя сходится медленнее или вообще расходится. Пример 3.6. Применим метод Зейделя для решения системы уравнений (3.33) из примера 3.5. Первые шаги полностью совпадают с процедурой решения по методу Якоби, а именно: система приводится к виду (3.34), затем в качестве начального приближения выбираются элементы столбца свободных членов (3.35). Проведем теперь итерации методом Зейделя. При k = 1 x 1 1 = – 0.0574x 0 2 – 0.1005x 0 3 – 0.0431x 0 4 + 1.0383 = 0.7512 При вычислении x 1 2 используем уже полученное значение x 1 1 : x 1 2 = –0.0566 x 1 1 – 0.0708x 0 3 – 0.1179x 0 4 + 1.2953 = 0.9674 При вычислении x 1 3 используем уже полученные значения x 1 1 и x 1 2 : x 1 3 = –0.1061 x 1 1 – 0.0758 x 1 2 – 0.0657x 0 4 + 1.4525 = 1.1977 При вычислении x 1 4 используем уже полученные значения x 1 1 , x 1 2 , x 1 3 : x 1 4 = –0.0280 x 1 1 – 0.0779 x 1 2 – 0.0405x x 1 3 + 1.5489 = 1.4037 Аналогичным образом проведем вычисления при k = 2 и k = 3. Получим: при k = 2 x 2 1 = 0.8019, x 2 2 = 0.9996, x 2 3 = 1.9996, x 2 4 = 1.4000. при k = 3 x 3 1 = 0.80006, x 3 2 = 1.00002, x 3 3 = 1.19999, x 3 4 = 1.40000. Известны точные значения переменных: x 1 = 0.8, x 2 = 1.0, x 3 = 1.2, x 4 = 1.4. Сравнение с примером 3.5 показывает, что метод Зейделя сходится быстрее и дает более точный результат. |