Итерационные методы решений систем алгебраических уравнений

Точные методы

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

Метод Гаусса

Прямой ход метода

1-й шаг. Предположим, что а₁₁¹0. Поделим первое уравнение на этот элемент:

.                                  (1.3)

Остальные уравнений системы (1.1) запишем в виде

,                                 (1.4)

где i= .

Уравнение (1.3) умножаем на a_i1 и вычитаем из i-го уравнения системы (1.4).

Получим систему вида:

.                        (1.5)

.

Система (1.5) имеет матрицу вида:

.

Работаем с укороченной системой, т.к. х₁ входит только в 1-ое уравнение

.

2-й шаг. Если , то из укороченной системы аналогично исключаем неизвестное x₂ и получаем матрицу коэффициентов такого вида:

.

Аналогично повторяем указанные действия для неизвестных х₃,х₄,...,

х_m-1  и приходим к системе с матрицей вида:

.                           (1.6)

Эта матрица является верхней треугольной:

.

Обратный ход метода. Из последнего уравнения системы (1.6) находим х_m, из предпоследнего х_m-1, ..., из первого уравнения – х₁.

Общая формула: 

x_m=y_m/c_mm,

, (i=m-1,…,1).

Для реализации метода Гаусса требуется примерно (2/3)m³ арифметических операций, причем большинство из них приходится на прямой ход.

Ограничение метода единственного деления заключается в том, что угловые элементы не равны нулю, т.е. .

Ведущие элементы – – элементы на k-ом шаге исключения. Но если ведущий элемент близок к нулю, то в процессе вычисления может накапливаться погрешность. В этом случае на каждом шаге исключают не х_k, a х_j (при j¹k). Такой подход называется методом выбора главного элемента. Для этого выбирают неизвестные x_j с наибольшим по абсолютной величине коэффициентом либо в строке, либо в столбце, либо во всей матрице. Для его реализации требуется  - арифметических действий.

1.1.2 Связь метода Гаусса с разложением матрицы на множители. Теорема об LU разложении.

Пусть дана система Aх=B (1.1), которая при прямом ходе преобразуется в эквивалентную систему (1.6) и которую запишем в виде

Cх=y,                                                      (1.7)

 где С – верхняя треугольная матрица с единицами на главной диагонали.

Как связаны в системе (1.1) элементы В и элементы y из (1.7)?

Если внимательно посмотреть на прямой ход метода Гаусса, то можно увидеть, что

.

Для произвольного j имеем

,                           (1.7)

где j= , d_ji – числовые коэффициенты:

.                                                    (1.8)

Это можно записать в виде:

В=Dy,

где D-нижняя треугольная матрица с элементами  на главной диагонали (j= , ).

В связи с тем, что в методе Гаусса угловые коэффициенты не равны нулю , то на главной диагонали матрицы D стоят не нулевые элементы. Следовательно, эта матрица имеет обратную, тогда y=D^-1В, Сx= D^-1В. Тогда

D´Cx=B.                                              (1.9)

В результате использования метода Гаусса, получили разложение матрицы А на произведение двух матриц

A = D´C,

где D - нижняя треугольная матрица, у которой элементы на главной диагонали не равны нулю, а C - верхняя треугольная матрица с единичной диагональю.

 Таким образом, если задана матрица A и вектор B, то в методе Гаусса сначала производится разложение этой матрицы А на произведение D и C, а затем последовательно решаются две системы:

  Dy=B,

Cx=y.                                                   (1.10)

Из последней системы находят искомый вектор x. При этом разложение матрицы А на произведение СD – есть прямой ход метода Гаусса, а решение систем (1.10) обратный ход. Обозначим нижнюю треугольную матрицу через L, верхнюю треугольную матрицу - U.

Теорема об LU разложении

Введем обозначения:  - угловой минор порядка j матрицы А, т.е.

Теорема.Пусть все угловые миноры матрицы А не равны нулю (Δj¹0 для j= ). Тогда матрицу А можно представить единственным образом в виде произведения А=L*U.

Идея доказательства.Рассмотрим матрицу А второго порядка и будем искать разложение этой матрицы в виде L и U.

.

Сопоставляя эти два равенства, определяем элементы матриц L и U (перемножим и приравняем неизвестные). Система имеет единственное решение. Методом математической индукции сказанное можно обобщить для матрицы размерности m´m.

Следствие. Метод Гаусса (схема единственного деления) можно применять только в том случае, когда угловые миноры матрицы А не равны нулю.

1.1.3 Метод Гаусса с выбором главного элемента

Может оказаться так, что система (1.1) имеет единственное решение, хотя какой либо из миноров матрицы А равен нулю. Заранее неизвестно, что все угловые миноры матрицы А не равны нулю. Избежать этого можно с выбором главного элемента.

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

ПРИМЕР. Пусть дана система второго порядка

при ½а₁₂½>½ а₁₁½, тогда на первом шаге вместо неизвестного х₁ исключают х₂:

.

К этой системе применяем первый шаг прямого хода метода Гаусса.

2. Выбор главного элемента по столбцу.

       Предположим, что ½а₂₁½>½ а₁₁½и переставим уравнения

и применяем первый шаг прямого хода метода Гаусса. Здесь имеет место перенумерация строк.

3. Поиск главного элемента по всей матрице заключается в совместном применении методов 1 и 2. Всё это приводит к уменьшению вычислительной погрешности.

1.1.4 Метод Холецкого (метод квадратных корней)

Пусть дана система

Ах=В ,                                              (1.11)

где матрица А - симметричная матрица. Тогда решение системы (1.11) проводится в два этапа:

1. Симметричная матрица А представляется как произведение двух матриц

А = L * L^Т.

Рассмотрим метод квадратных корней на примере системы 4-го порядка:

.

Перемножаем матрицы в левой части разложения и сравниваем с элементами в левой части:

, , , , ,

, , .

2. Решаем последовательно две системы

Ly=B,

L^Tx=у.

Особенности.

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

2) Возможно переполнение - если угловые элементы близки к нулю.

Итерационные методы решений систем алгебраических уравнений

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

Суть итерационных методов заключается в том, что решение х системы (1.1) находится как предел последовательности .

Так как за конечное число итераций предел не может быть достигнут, то задаётся малое число e - точность, и последовательные приближения вычисляют до тех пор, пока не будет выполнено неравенство

,

где n=n(e) – функция e,  - норма вектора.

Прямые методы рассчитаны для решения систем, если её порядок не больше 100, иначе используются итерационные методы.