Вычислительная математика
Сравнение оценок (2.15) и (2.21) показывает, что p < 2, и метод секущих сходится медленнее, чем метод Ньютона. Но в методе Ньютона на каждой итерации надо вычислять и функцию, и производную, а в методе секущих – только функцию. Поэтому при одинаковом объеме вычислений в методе секущих можно сделать примерно вдвое больше итераций и получить более высокую точность.
Так же, как и метод Ньютона, при неудачном выборе начальных приближений (вдали от корня) метод секущих может расходиться. Кроме того применение метода секущих осложняется из-за того, что в знаменатель расчетной формулы метода (2.20) входит разность значений функции. Вблизи корня эта разность мала, и метод теряет устойчивость.
Критерий окончания. Критерий окончания итераций метода секущих такой же, как и для метода Ньютона. При заданной точности e > 0 вычисления нужно вести до тех пор, пока не будет выполнено неравенство
|xn – xn – 1| < e. (2.22)
Пример 2.4.
Применим метод секущих для вычисления положительного корня уравнения 4(1 – x2) – ex = 0 с точностью e = 10-3.
Корень этого уравнения находится на отрезке [0, 1], так как f (0) = 3 > 0, а f (1) = –e < 0. Подсчитаем вторую производную функции: f "(x) = –8 – ex. Условие f(x)f " (x) і 0 выполняется для точки b = 1. В качестве начального приближения возьмем x0 = b = 1. В качестве второго начального значения возьмем x1 = 0.5. Проведем вычисления по расчетной формуле (2.20). Результаты приведены в табл. 2.4.
Таблица 2.4
| n | xn |
|
0 1 2 3 4 5 |
1.0000 0.5000 0.6660 0.7093 0.7033 0.7034 |
2.7 Метод ложного положения
Рассмотрим еще одну модификацию метода Ньютона.
Пусть известно, что простой корень 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
| n | xn |
|
0 1 2 3 |
1.9 1.9254 1.9263 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
– m
a1j
, b
=
bi
– m
b1.
(3.5)
Легко
убедиться, что
для всех уравнений,
начиная со
второго, a
=
0, i = 2, 3, …,
n. Преобразованная
система запишется
в виде:
a11x1
+ a12
x2
+ a13x3
+ … + a1nxn
= b1
a
x2
+ a
x3
+ … + a
xn
= b![]()
a
x2
+ a
x3
+ … + a
xn
= b
(3.6)
a
x2
+ a
x3
+ … + a
xn
= b![]()
Все уравнения (3.6), кроме первого, образуют систему (n – 1)-го порядка. Применяя к ней ту же процедуру, мы можем исключить из третьего, четвертого, …, n-го уравнений переменную x2. Точно так же исключаем переменную x3 из последних n – 3 уравнений.
На
некотором k-ом
шаге в предположении,
что главный
элемент k-ого
шага a![]()
0,
переменная
xk
исключается
с помощью формул:
m
=
,
a
= a
– m
a
,
b
=
b
– m
b
,
i,
j = k + 1, k
+ 2,
…, n.
(3.7)
Индекс k принимает значения 1, 2, …, n – 1.
При k = n – 1 получим треугольную систему:
a11x1
+ a12
x2
+ a13x3
+ … + a1nxn
= b1
a
x2
+ a
x3
+ …+ a
xn
= b![]()
a
x3
+ …+ a
xn
= b
(3.8)
a
xn
= 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