Численные методы (стр. 3 )

Так как , то

; .

Так как , то .

2 РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

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

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

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

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

ной -го столбца матрицы столбцом правых частей .

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

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

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

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

Норма матрицы является некоторой обобщенной оценкой значений элементов матрицы. Для её вычисления можно использовать следующие выражения:

,

, .

2.2. Метод простой итерации

Для того чтобы применить метод простой итерации, необходимо систему уравнений

(1)

с квадратной невырожденной матрицей привести к виду

, (2)

где – квадратная невырожденная матрица с элементами ,
– вектор-столбец неизвестных , – вектор-столбец с элементами , . Существуют различные способы приведения системы (1) к виду (2). Рассмотрим самый простой.

Представим систему в развернутом виде:

(3)

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

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

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

(4)

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

(5)

Очевидно, что диагональные элементы матрицы должны быть отличны от нуля. Выберем произвольно начальное приближение. Обычно в качестве первого приближения берут или . Подставим начальное приближение в правую часть (4). Вычисляя левые части, получим значения . Продолжая этот процесс дальше, получим последовательность приближений, причем приближение строится следующим образом:

Последняя система представляет собой расчетные формулы метода простой итерации.

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

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

, (6)

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

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

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

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

, (7)

где .

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

Иначе достаточное условие (6) для матрицы может быть переформулирована так: если , то итерационный процесс (6) сходится к точному решению системы.

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

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

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

. (8)

В других случаях использование последнего критерия (8) неправомерно и может привести к преждевременному окончанию итерационного процесса.

Пример 3.

Применим метод простой итерации для решения системы уравнений

.

Заметим, что метод простой итерации сходится, так как выполняется условие преобладания диагональных элементов:

, ,

, .

Пусть требуемая точность . Вычисления будем проводить с четырьмя знаками после десятичной точки.

Приведем систему к виду:

Величина равна 0,1179, т. е. выполняется условие и можно пользоваться критерием окончания итерационного процесса (8). В качестве начального приближения возьмем элементы столбца свободных членов: . Вычисления будем вести до тех пор, пока все величины , , а следовательно, и не станут меньше .

Последовательно вычисляем:

при

при

.

при

.

при

.

Вычисляем модули разностей значений при и :

. Так как все они больше заданной точности , продолжаем итерации.

При

.

Вычисляем модули разностей значений при и :

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

.

Для сравнения приведем точные значения переменных:

.

2.3. Метод Зейделя

Модификацией метода простой итерации можно считать метод Зейделя.

В методе простой итерации на -ой итерации значения , вычисляются подстановкой в правую часть (6) вычисленных на предыдущей итерации значений. В методе Зейделя при вычислении используются значения , , , уже найденные на -ой итерации, а не , , …, , как в методе простой итерации, т. е. -е приближение строится следующим образом:

(9)

Эти формулы являются расчетными формулами метода Зейделя.

Введем нижнюю и верхнюю треугольные матрицы:

и .

Матричная запись расчетных формул (9) имеет вид: . Так как , точное решение исходной системы удовлетворяет равенству: .

Сходимость метода Зейделя. Достаточным условием сходимости метода Зейделя является выполнение неравенства:

. (10)

Неравенство (10) означает, что для сходимости метода Зейделя достаточно, чтобы любая норма матрицы был меньше единицы.

Если выполнено условие (10), то справедлива следующая оценка погрешности:

, (11)

где – норма матрицы.

Критерий окончания. Если требуется найти решение с точностью , итерационный процесс следует закончить, как только на -ом шаге выполнится неравенство: . Поэтому в качестве критерия окончания итерационного процесса можно использовать неравенство , где . Если выполняется условие

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

.

Метод Зейделя, как правило, сходится быстрее, чем метод простой итерации. Однако возможны ситуации, когда метод простой итерации сходится, а метод Зейделя сходится медленнее или вообще расходится.

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

При

.

При вычислении используем уже полученное значение :

.

При вычислении используем уже полученные значения и :

.

При вычислении используем уже полученные значения , , :

.

Аналогичным образом проведем вычисления при и .

Получим:

при

.

при

.

Известны точные значения переменных:

.

Сравнение с предыдущим примером показывает, что метод Зейделя сходится быстрее и дает более точный результат.

3. РЕШЕНИЕ СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ

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

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

, иначе .

В отличие от решения систем линейных алгебраических уравнений (СЛАУ) не существует прямых методов решения систем нелинейных урав­нений. Лишь в отдельных случаях эту систему можно решить непосредственно. Например, для случая двух неизвестных иногда удается выразить одно неизвестное через другое и таким об­ра­зом свести задачу к решению одного нелинейного уравнения относительно другого.

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

3.2. Метод Ньютона для системы нелинейных уравнений

В основе метода Ньютона для системы уравнений лежит использование разложения функ­ций в ряд Тейлора, причем члены, содержащие вторые производные (и производ­ные более высоких порядков), отбрасываются. Пусть приближенные значения неизвестных системы (например, полученные на предыду­щей итерации) равны соответственно . Задача состоит в нахождении приращений (по­пра­вок) к этим значениям , благодаря которым решение исходной системы за­пи­шется в виде: . Проведем разложение левых частей уравнений исходной системы в ряд Тэйлора, ограничи­ва­ясь лишь линейными членами относительно приращений:

Поскольку левые части этих выражений должны обращаться в нуль, то можно приравнять к ну­лю и правые части:

в матричном виде:

Значения и их производные вычисляются при .

Определителем последней системы является якобиан:

.

Для существования единственного решения системы якобиан должен быть отличным от нуля на каждой итерации.

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

.

В методе Ньютона также важен удачный выбор начального приближения для обеспечения хо­рошей сходимости. Сходимость ухудшается с увеличением числа уравнений системы. Итак, за расчетную формулу примем

или .

Сходимость метода. Теорема. Пусть в некоторой окрестности решения системы нелинейных уравнений функции дважды непрерывно дифференцируемы и определитель матрицы Якоби не равен нулю. Тогда найдется такая малая – окрестность решения , что при произвольном выборе начального приближения из этой окрестности, итерационная последовательность метода Ньютона не выходит за пределы окрестности и справедлива оценка: , – метод сходится с квадратичной скоростью.

В качестве примера можно рассмотреть использование метода Ньютона для решения систе­мы двух уравнений: , где и – непрерывно дифференцируемые функции. Пусть начальные значения неизвестных равны . После разложения исходной системы в ряд Тэйлора можно получить:

Предположим, что якобиан системы при и отличен от нуля:

.

Тогда значения и можно найти, используя матричный способ следующим образом:

.

Вычислив значения и можно найти и следующим образом:

.

Величины, стоящие в правой части, вычисляются при и .

Критерий окончания. Будем считать, что заданная точность достигнута, если или .

Пример. Методом Ньютона решить систему двух уравнений:

с точностью до 0,001.

Решение.

1) Начальные приближения можно определить графическим способом. Для этого перепи­шем систему в виде:

Первое из преобразованных уравнений определяет эллипс, а второе – гиперболу. Данная сис­те­ма имеет два решения. Для уточнения выбирают одно из них, принадлежащее области и .

За начальное приближение принимают и .

2) Находим

0,5	-0,1052	2	-8,76	49,32
-0,46	-0,3848	5	2,76
0,5742	0,0114	2,2968	-8,7306	51,2203
-0,4551	0,0052	5,1484	2,7306
0,5727	0,00006	2,2908	-8,7252	51,1375
-0,4542	-0,00011	5,1454	2,7252
0,5727
-0,4542

Поскольку , то .