8510

30

y x3 0,2x2 5,5x 1,5

Рис. 8. Графическое отделение корня для уравнения x3 0,2x2 5,5x 1,5 0 .

Результаты проведенных вычислений удобно представлять в виде

таблицы (табл. 3). Очевидно, что процесс уточнения корня достаточно бы-

3.5. Метод касательных (метод Ньютона)

Будем строить касательную к кривой y f (x) . Каждое приближе-

ние к точному решению будет абсциссой точки пересечения соответст-

вующей касательной и оси OX . Важным является вопрос о выборе на-

чального приближения x0 a; b . Начальное приближение удовлетворяет неравенству f (x0 ) f (x0 ) 0 . Принято следующее правило: если f (x) и

34

.....................................................

am1 x1 am2 x2 am3 x3 ... am mxm bm .

Вматричной форме записи эта система принимает вид:

Необходимо вычислить вектор x , являющийся решением системы

(4.2), по входному данному – вектору b . Будем предполагать, что матрица

A задана и является невырожденной. Известно, что в этом случае решение системы существует, единственно и устойчиво по входным данным. Это

означает, что рассматриваемая задача корректна.

Пусть x* (x1*, x2*, ...,xm* )T – приближенное решение системы (4.1).

Будем стремиться к получению решения, для которого погрешность

e x x* мала. Тем не менее, заметим, что качество полученного решения далеко не всегда характеризуется тем, насколько мала погрешность x x* .

Иногда вполне удовлетворительным является критерий малости невязки r b Ax* . Вектор r показывает, насколько отличается правая часть сис-

темы от левой, если подставить в нее приближенное решение. Заметим,

что r Ax Ax* A(x x*) , и поэтому погрешность и невязка связаны ра-

венством:

e x x* A 1r .

35

4.1.1. Метод Гаусса

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

Вычисления с помощью метода Гаусса состоят из двух основных этапов, называемых прямым ходом и обратным ходом (обратной подста-

новкой). Прямой ход метода Гаусса заключается в последовательном ис-

ключении неизвестных из системы (4.1) для преобразования ее к эквива-

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

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

Прямой ход состоит из m-1 шагов исключения.

1–й шаг. Целью этого шага является исключение неизвестного x1

из уравнений с номерами i 2,3,...,m . Предположим, что коэффициент a11 0 . Будем называть его главным (или ведущим) элементом 1-го шага.

Найдем величины:

называемые множителями 1–го шага. Вычтем последовательно из второго,

третьего,…, m –го уравнений системы (4.1) первое уравнение, умноженное соответственно на 21, 31,..., m1 x1 . Это позволит обратить в нуль коэф-

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

чим эквивалентную систему:

37

и вычтем последовательно из k 1 го, …, m го уравнений полученной на предыдущем шаге системы k е уравнение, умноженное соответствен-

но на k 1,k , k 2,k ,..., mk .

После m 1 го шага исключения получим систему уравнений

матрица A(m 1) которой является верхней треугольной. На этом вычисле-

ния прямого хода заканчиваются.

Обратный ход. Из последнего уравнения системы (4.7) находим xm .

Подставляя найденное значение xm в предпоследнее уравнение, получим xm 1 . Осуществляя обратную подстановку, далее последовательно находим xm 2 , xm 3,...,x1. Вычисления неизвестных здесь проводятся по формулам:

2. Метод Гаусса с выбором главного элемента по столбцу (схема частичного выбора). Описание метода. На k м шаге прямого хода коэф-

фициенты уравнений системы с номерами i k 1,...,m преобразуются по формулам:

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

сэтим ошибок нельзя допускать появления больших множителей ik .

Вметоде Гаусса с выбором главного элемента по столбцу гаранти-

варианта метода Гаусса от схемы единственного деления заключается в

38

том, что на k м шаге исключения в качестве главного элемента выбирают

максимальный по модулю коэффициент aik k при неизвестной xk в уравне-

ниях с номерами i k, k 1,...,m . Затем соответствующее выбранному ко-

эффициенту уравнение с номером ik меняют местами с k м уравнением

системы для того, чтобы главный элемент занял место коэффициента akk(k 1) . После этой перестановки исключение неизвестного xk производят,

как в схеме единственного деления.

3. Метод Гаусса с выбором главного элемента по всей матрице

(схема полного выбора).

В этой схеме допускается нарушение естественного порядка ис-

ключения неизвестных.

На 1–м шаге метода среди элементов aij определяют максимальный

по модулю элемент ai1 j1 . Первое уравнение системы и уравнение с номе-

ром i1 меняют местами. Далее стандартным образом производят исключе-

ние неизвестного x j1 из всех уравнений, кроме первого.

На k м шаге метода среди коэффициентов aij(k 1) при неизвестных в уравнениях системы с номерами i k,...,m выбирают максимальный по

модулю коэффициент ai(kj 1) . Затем k е уравнение и уравнение, содержа-

k k

щее найденный коэффициент, меняют местами и исключают неизвестное x jk из уравнений с номерами i k 1,...,m .

На этапе обратного хода неизвестные вычисляют в следующем по-

рядке: x jm , x jm 1 ,...,x j1 .

Пример. Методом Гаусса решить систему:

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

21 a21 /a11 5/10 0,5; 31 a31 / a113/10 0,3; 41 a41 / a11 0 /10 0.

Вычитая из второго, третьего и четвертого уравнений системы (4.10) пер-

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

32 a32(1) / a22(1) 3,2 /( 2) 1,6; 42 6 /( 2) 3.

Вычитая из третьего и четвертого уравнений системы (4.11) второе урав-

3-й шаг. Вычисляя множитель 43 ( 11) /( 4,4) 2,5 и вычитая из четвертого уравнения системы (4.12) третье уравнение, умноженное на

43, приводим систему к треугольному виду: