Вычислительная математика (стр. 5 из 20)
Метод ложного положения обладает только линейной сходимостью. Сходимость тем выше, чем меньше отрезок [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 = b1a21x1 + 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 b1a21 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 = b1a 
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 = b1a 
x2 + a 
x3 + …+ a 
xn = b 
a 
x3 + …+ a 
xn = b 
(3.8)