Пусть известно, что простой корень x* уравнения f(x) = 0 находится на отрезке [a, b] и на одном из концов отрезка выполняется условие f(x)f"(x) ³ 0. Возьмем эту точку в качестве начального приближения. Пусть для определенности это будет b. Положим x0 = a. Будем проводить из точки B = (b, f(b)) прямые через расположенные на графике функции точки Bn с координатами (xn, f(xn), n = 0, 1, … . Абсцисса точки пересечения такой прямой с осью OX есть очередное приближение xn+1.

Геометрическая иллюстрация метода приведена на рис. 2.10.

Рис. 2.10

Прямые на этом рисунке заменяют касательные в методе Ньютона (рис. 2.8). Эта замена основана на приближенном равенстве

f '(xn) » . (2.23)

Заменим в расчетной формуле Ньютона (2.13) производную f '(xn) правой частью приближенного равенства (2.23). В результате получим расчетную формулу метода ложного положения:

xn +1 = xn –.. (2.24)

Метод ложного положения обладает только линейной сходимостью. Сходимость тем выше, чем меньше отрезок [a, b].

Критерий окончания. Критерий окончания итераций метода ложного положения такой же, как и для метода Ньютона. При заданной точности e > 0 вычисления нужно вести до тех пор, пока не будет выполнено неравенство

|xn – xn – 1| < e. (2.25)

Пример 2.5.

Применим метод ложного положения для вычисления корня уравнения x3 + 2x – 11 = 0 с точностью e = 10-3.

Корень этого уравнения находится на отрезке [1, 2], так как f (1) = –8 < 0, а f (2) = 1 > 0. Для ускорения сходимости возьмем более узкий отрезок [1.9, 2], поскольку f (1.9) < 0, а f (2) > 0. Вторая производная функции f (x) = x3 + 2x – 11 равна 6x. Условие f(x)f"(x) ³ 0 выполняется для точки b = 2. В качестве начального приближения возьмем x0 = a = 1.9. По формуле (2.24) имеем

x1 = x0 –. = 1.9 + » 1.9254.

Продолжая итерационный процесс, получим результаты, приведенные в табл. 2.5.

Таблица 2.5

1.9

1.9254

1.9263

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

3.1 Постановка задачи

Требуется найти решение системы линейных уравнений:

a11x1 + a12 x2 + a13x3 + … + a1nxn = b1

a21x1 + a22 x2 + a23x3 + … + a2nxn = b2

a31x1 + a32 x2 + a33x3 + … + a3nxn = b3 (3.1)

an1x1 + an2 x2 + an3x3 + … + annxn = bn

или в матричной форме:

Ax = b, (3.2)

где

a11 a12 a13 … a1n x1 b1

a21 a22 a23 … a2n x2 b2

A = a31 a32 a33 … a3n x =x3 , b =b3

an1 an2 an3 ann xn bn

По правилу Крамера система n линейных уравнений имеет единственное решение, если определитель системы отличен от нуля (det A 0) и значение каждого из неизвестных определяется следующим образом:

xj = , j = 1, …, n, (3.3)

где det Aj – определитель матрицы, получаемой заменой j-го столбца матрицы A столбцом правых частей b.

Непосредственный расчет определителей для больших n является очень трудоемким по сравнению с вычислительными методами.

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

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

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

Среди прямых методов наиболее распространенным является метод исключения Гаусса и его модификации, Наиболее распространенными итерационными методами является метод простых итераций Якоби и метод Зейделя.

Эти методы будут рассмотрены в следующих разделах.

3.2 Метод исключения Гаусса. Схема единственного деления

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

Рассмотрим сначала простейший метод исключения Гаусса, называемый схемой единственного деления.

Прямой ход состоит из n – 1 шагов. На первом шаге исключается переменная x1 из всех уравнений, кроме первого. Для этого нужно из второго, третьего, …, n-го уравнений вычесть первое, умноженное на величину

m = , i = 2, 3, …, n. (3.4)

При этом коэффициенты при x1 обратятся в нуль во всех уравнениях, кроме первого.

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

a = aij – ma1j , b= bi – mb1. (3.5)

Легко убедиться, что для всех уравнений, начиная со второго, a= 0, i = 2, 3, …, n. Преобразованная система запишется в виде:

a11x1 + a12 x2 + a13x3 + … + a1nxn = b1

ax2 + ax3 + … + axn = b

a x2 + ax3 + … + axn = b (3.6)

ax2 + ax3 + … + axn = b

Все уравнения (3.6), кроме первого, образуют систему (n – 1)-го порядка. Применяя к ней ту же процедуру, мы можем исключить из третьего, четвертого, …, n-го уравнений переменную x2. Точно так же исключаем переменную x3 из последних n – 3 уравнений.

На некотором k-ом шаге в предположении, что главный элемент k-ого шага a0, переменная xk исключается с помощью формул:

m = ,

a = a – ma ,

b= b – mb, i, j = k + 1, k + 2, …, n. (3.7)

Индекс k принимает значения 1, 2, …, n – 1.

При k = n – 1 получим треугольную систему:

a11x1 + a12 x2 + a13x3 + … + a1nxn = b1

ax2 + ax3 + …+ axn = b

ax3 + …+ axn = b (3.8)

axn = b

с треугольной матрицей An.

Приведение системы (3.1) к треугольному виду (3.8) составляет прямой ход метода Гаусса.

При использовании метода Гаусса нет необходимости в предварительном обосновании существования и единственности решения (т. е. доказательства, что det A ¹ 0). Если на k-ом шаге все элементы a (i = k, k + 1, …, n) окажутся равными нулю, то система (3.1) не имеет единственного решения.

Обратный ход состоит в вычислении переменных. Из последнего уравнения (3.8) определяем xn... Подставляя его в предпоследнее уравнение, находим xn-1, и т. д. Общие формулы имеют вид:

xn = ,

xk = (b- a xk+1 - a xk+2 - … - a xn), k = n – 1, n – 2, …, 1 (3.9)

Трудоемкость метода. Для реализации метода исключения Гаусса требуется примерно 2/3n3 операций для прямого хода и n2 операций для обратного хода. Таким образом, общее количество операций составляет примерно 2/3n3 + n2.

Пример 3.1.

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

2.0x1 + 1.0x2 – 0.1x3 + 1.0x4 = 2.7

0.4x1 + 0.5x2 + 4.0x3 – 8.5x4 = 21.9

0.3x1 – 1.0x2 + 1.0x3 + 5.2x4 = – 3.9 (3.10)

1.0x1 + 0.2x2 + 2.5x3 – 1.0x4 = 9.9

Будем делать округление чисел до четырех знаков после десятичной точки.

Прямой ход. 1-ый шаг. Вычислим множители:

m = = = 0.2; m = = = 0.15; m = = = 0.5.

Вычитая из второго, третьего и четвертого уравнений системы (3.10) первое уравнение, умноженное соответственно на m, m, m, получим новую систему:

2.0x1 + 1.0x2 – 0.1x3 + 1.0x4 = 2.7

0.3x2 + 4.02x3 – 8.70x4 = 21.36

–1.15x2 + 1.015x3 + 5.05x4 = – 4.305 (3. 11)

– 0.30x2 + 2.55x3 – 1.50x4 = 8.55

2-ой шаг. Вычислим множители:

m = = = – 3.83333; m = = = –1.0.

Вычитая из третьего и четвертого уравнений системы (3.11) второе уравнение, умноженное соответственно на m и m, приходим к системе:

2.0x1 + 1.0x2 – 0.1x3 + 1.0x4 = 2.7

0.3x2 + 4.02x3 – 8.70x4 = 21.36

16. 425x3 – 28.300x4 = 77.575 (3.12)

6.570x3 – 10.200x4 = 29.910

3-ий шаг. Вычислим множитель:

m = = = 0.4.

Вычитая из четвертого уравнения системы (3.12) третье, умноженное на m, приведем систему к треугольному виду:

2.0x1 + 1.0x2 – 0.1x3 + 1.0x4 = 2.7

0.3x2 + 4.02x3 – 8.70x4 = 21.36

16. 425x3 – 28.300x4 = 77.575 (3.13)

1.12x4 = –1.12

Обратный ход. Из последнего уравнения системы (3.13) находим x4 = 1.000. Подставляя значение x4 в третье уравнение, получим x3 = 2.000. Подставляя найденные значения x4 и x3 во второе уравнение, найдем x2 = 3.000. Наконец, из первого уравнения, подставив в него найденные значения x4, x3 и x2, вычислим x1 = –1.000.

Итак система (3.10) имеет следующее решение:

x1 = 1.000, x2 = 2.000, x3 = 3.000, x4 = – 1.000.

3.3 Метод исключения Гаусса с выбором главного элемента по столбцу

Хотя метод Гаусса является точным методом, ошибки округления могут привести к существенным погрешностям результата. Кроме того исключение по формулам (3.7) нельзя проводить, если элемент главной диагонали a равен нулю. Если элемент a мал, то велики ошибки округления при делении на этот элемент. Для уменьшения ошибок округления применяют метод исключения Гаусса с выбором главного элемента по столбцу. Прямой ход так же, как и для схемы единственного деления, состоит из n – 1 шагов. На первом шаге прежде, чем исключать переменную x1, уравнения переставляются так, чтобы в левом верхнем углу был наибольший по модулю коэффициент ai1, i = 1, 2, …, n. В дальнейшем, на k-м шаге, прежде, чем исключать переменную xk, уравнения переставляются так, чтобы в левом верхнем углу был наибольший по модулю коэффициент aik, i = k, k + 1, …, n. После этой перестановки исключение переменной xk производят, как в схеме единственного деления.

Трудоемкость метода. Дополнительные действия по выбору главных элементов требуют примерно n2 операций, что практически не влияет на общую трудоемкость метода.

Пример 3.2.

Применим метод исключения Гаусса с выбором главного элемента по столбцу для решения системы уравнений (3.10) из примера 3.1. Прямой ход. 1-ый шаг. Так как коэффициент a11 = 2.0 наибольший из коэффициентов первого столбца, перестановки строк не требуется и 1-ый шаг полностью совпадает с 1-ым шагом примера 3.1. Из второго, третьего и четвертого уравнений исключается переменная x1 и система приводится к виду (3.11).

2-ой шаг. Наибольший по модулю коэффициент при x2 в системе (3.11) a = –1.15. Поэтому переставим уравнения следующим образом:

2.0x1 + 1.0x2 – 0.1x3 + 1.0x4 = 2.7

–1.15x2 + 1.015x3 + 5.05x4 = – 4.305 (3.14)

0.3x2 + 4.02x3 – 8.70x4 = 21.36

– 0.30x2 + 2.55x3 – 1.50x4 = 8.55

Вычислим множители:

m = = = –0.26087 m = = = 0.26087.

Вычитая из третьего и четвертого уравнений системы (3.14) второе уравнение, умноженное соответственно на m и m, приходим к системе:

2.0x1 + 1.0x2 – 0.1x3 + 1.0x4 = 2.7

–1.15x2 + 1.015x3 + 5.05x4 = – 4.305 (3.15)

4.28478x3 – 7.38261x4 = 20.23696

2.28522x3 – 2.81739x4 = 9.67305

3-ий шаг. Вычислим множитель:

m = = = 0.53333.

Вычитая из четвертого уравнения системы (3.15) третье, умноженное на m, приведем систему к треугольному виду:

2.0x1 + 1.0x2 – 0.1x3 + 1.0x4 = 2.7

–1.15x2 + 1.015x3 + 5.05x4 = – 4.305 (3.16)

4.28478x3 – 7.38261x4 = 20.23696

1.11998x4 = –1.11998

Обратный ход. Обратный ход полностью совпадает с обратным ходом примера 3.1. Решение системы имеет вид:

x1 = 1.000, x2 = 2.000, x3 = 3.000, x4 = – 1.000.

3.4 Вычисление определителя методом исключения Гаусса

Из курса линейной алгебры известно, что определитель треугольной матрицы равен произведению диагональных элементов. В результате метода исключений Гаусса система линейных уравнений (3.2) с квадратной матрицей A приводится к эквивалентной ей системе (3.8) с треугольной матрицей An. Поэтому

det A = (–1)s det An,

где s – число перестановок строк, (s = 0, если использовался метод Гаусса по схеме единственного деления).Таким образом,

det A = (–1)s a11 aa …a (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:

a11 a12 a13 … a1n

a21 a22 a23 … a2n

A = a31 a32 a33 … a3n

an1 an2 an3 … ann

и A-1 – ее обратная матрица:

x11 x12 x13 … x1n

x21 x22 x23 … x2n

A-1 = x31 x32 x33 … x3n

xn1 xn2 xn3 … xnn

Используя соотношения (3.18), (3. 19) и правило умножения матриц, получим систему из n2 уравнений с n2 переменными xij, i, j = 1, 2, …, n. Чтобы получить первый столбец матрицы E, нужно почленно умножить каждую строку матрицы A на первый столбец матрицы A-1 и приравнять полученное произведение соответствующему элементу первого столбца матрицы E. В результате получим систему уравнений:

a11x11 + a12 x21 + a13x31 + … + a1nxn1 = 1

a21x11 + a22 x21 + a23x31 + … + a2nxn1 = 0

a31x11 + a32 x21 + a33x31 + … + a3nxn1 = 0 (3.20)

an1x11 + an2 x21 + an3x31 + … + annxn1 = 0

Аналогично, чтобы получить второй столбец матрицы E, нужно почленно умножить каждую строку матрицы A на второй столбец матрицы A-1 и приравнять полученное произведение соответствующему элементу второго столбца матрицы E. В результате получим систему уравнений:

a11x12 + a12 x22 + a13x32 + … + a1nxn2 = 0

a21x12 + a22 x22 + a23x32 + … + a2nxn2 = 1

a31x12 + a32 x22 + a33x32 + … + a3nxn2 = 0 (3.21)

an1x12 + an2 x22 + an3x32 + … + annxn2 = 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 – квадратная невырожденная матрица с элементами bij, i, j = 1, 2, …, n, x – вектор-столбец неизвестных xi, c – вектор-столбец с элементами ci, i = 1, 2, …, n.

Существуют различные способы приведения системы (3.22) к виду (3.23). Рассмотрим самый простой. Представим систему (3.22) в развернутом виде:

a11x1 + a12 x2 + a13x3 + … + a1nxn = b1

a21x1 + a22 x2 + a23x3 + … + a2nxn = b2

a31x1 + a32 x2 + a33x3 + … + a3nxn = b3 (3.24)

an1x1 + an2 x2 + an3x3 + … + annxn = bn

Из первого уравнения системы (3.24) выразим неизвестную x1:

x1 = a(b1 – a12x2 – a13x3 – … – a1nxn),

из второго уравнения – неизвестную x2:

x2 = a(b2 – a21x1 – a23x3 – … – a2nxn),

и т. д. В результате получим систему:

x1 = b12 x2 + b13x3 + … + b1,n-1xn-1 + b1nxn + c1

x2 = b21x1 + b23x3 + … + b2,n-1xn-1 + b2nxn + c2

x3 = b31x1 + b32 x2+ … + b3,n-1xn-1 + b3nxn + c3 (3.25)

xn= bn1x1 + bn2 x2 + bn3x3 + bn,n-1xn-1 + cn

Матричная запись системы (3.25) имеет вид (3.23). На главной диагонали матрицы B находятся нулевые элементы, а остальные элементы вычисляются по формулам:

bij = , ci = , i, j = 1,2, …n, i j. (3.26)

Очевидно, что диагональные элементы матрицы A должны быть отличны от нуля.

Выберем произвольно начальное приближение Обычно в качестве первого приближения берут x= ci или x= 0. Подставим начальное приближение в правую часть (3.25). Вычисляя левые части, получим значения x, x, …, x. Продолжая этот процесс дальше, получим последовательность приближений, причем (k + 1)-е приближение строится следующим образом:

x = b12 x + b13 x + … + b1,n-1 x + b1n x + c1

x = b21 x1 + b23 x + … + b2,n-1 x + b2n x + c2

x= b31 x + b32 x + … + b3,n-1 x + b3n x + c3 … (3.27)

x= bn1x + bn2 x + bn3 x + bn,n-1 x + c.n

Система (3.27) представляет собой расчетные формулы метода простой итерации Якоби.

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

Если элементы матрицы A удовлетворяют условию:

|aii| > , i = 1, 2, …, n. (3.28)

то итерационная последовательность xk сходится к точному решению x*.

Условие (3.28) называют условием преобладания диагональных элементов матрицы A, так как оно означает, что модуль диагонального элемента i-ой строки больше суммы модулей остальных элементов этой строки, i = 1, 2, …, n.

Необходимо помнить, что условие сходимости (3.28) является лишь достаточным. Его выполнение гарантирует сходимость метода простых итераций, но его невыполнение, вообще говоря, не означает, что метод расходится.

Справедлива следующая апостериорная оценка погрешности:

max|x - x| £ max|x– x|, i = 1, 2, …, n, (3.29)

где b = max |bij| i, j = 1, 2, …, n.

Правую часть оценки (3.29) легко вычислить после нахождения очередного приближения.

Критерий окончания. Если требуется найти решение с точностью e, то в силу (3.29) итерационный процесс следует закончить как только на (k+1)-ом шаге выполнится неравенство:

max|x– x| < e, i = 1, 2, …, n. (3.30)

Поэтому в качестве критерия окончания итерационного процесса можно использовать неравенство

max|x– x| < e1, i = 1, 2, …, n. (3.31)

где e1 = e.

Если выполняется условие b £ , то можно пользоваться более простым критерием окончания:

max|x– x| < e, i = 1, 2, …, n. (3.32)

Страницы: 1, 2, 3, 4, 5