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

--PAGE_BREAK--


Глава 2. Применение  численных методов для решения систем линейных алгебраических уравнений в теории и на практике §1 ЧИСЛЕННЫЕ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

Существуют два типа ме­тодов — прямые и итерационные. Мы рассматриваем прежде всего метод исключения Гаусса для систем об­щего вида и варианты — метод прогонки и методы мат­ричной прогонки для систем специального вида (с трех-диагональной или блочно-трех диагональной матрицами). Это — прямые методы. Их эффективность зависит от по­рядка системы nструктуры матрицы.

При изучении итерационных методов мы трактуем си­стему уравнений как операторное уравнение первого ро­да Au
=
f
и излагаем общую теорию итерационных ме­тодов для операторных уравнений при минимальных предположениях относительно оператора А. Общая тео­рия позволяет доказать сходимость итераций для метода Зейделя и метода верхней релаксации при минимальных ограничениях на оператор А. Рассмотрены два класса методов: 1) для случая, когда известны границы γi> О и γ2 >= γ1 спектра оператора А в некотором энергетиче­ском пространстве HD
; 2) для случая, когда границы γ1и γ2неизвестны. Весьма эффективным является попере­менно-треугольный метод.

Основная задача линейной ал­гебры — решение системы уравнений

Au
=
f
,                           (1)

где u=(u(1), ..., u(N)) — искомый вектор, f={f(1), f(2),… ..., f(n))—известный вектор размерности N
,
A
=(
aij
) (
i
,
j= 1, 2, ..., N
)— квадратная матрица размера NXNс элементами aij.

Будем предполагать, что матрица А невырождена, так что уравнение Аи = 0 имеет только триви­альное решение, и система (1) имеет единственноерешение

В курсе линейной алгебры решение системы (1) обыч­но выражают по формулам Крамера в виде отношений определителей. Для численного решения системы (1) эти формулы непригодны, так как они требуют вычисления N +1 определителей, что требует большого числа дей­ствий (порядка N! арифметических операций). Даже при выборе наилучшего метода вычисление одного определи­теля требует примерно такого же времени, что и реше­ние системы линейных уравнений современными числен­ными методами. Кроме того, следует иметь в виду, что вычисления по формулам Крамера часто ведут к боль­шим ошибкам округлений.

Особенность большинства численных методов для (1) состоит в отказе от нахождения обратной матрицы. Ос­новное требование к методу решения — минимум числа арифметических действий, достаточных для отыскания приближенного решения с заданной точностью е>0 (экономичность численного метода).

Выбор того или иного численного метода зависит от многих обстоятельств — от имеющихся программ, от вида матрицы А, от типа расчета и др. Поясним слова «тип расчета». Возможны разные постановки задачи:

1)   найти решение одной конкретной задачи (1);

2)   найти решение нескольких вариантов задачи (1) с одной и той же матрицей А и разными правыми частями. Может оказаться, что неоптимальный для одной задачи  метод является весьма эффективным для мно­говариантного расчета.

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

При теоретических оценках каче­ства алгоритмов их сравнение проводится по числу q
(
e
) арифметических действий, достаточных для нахождения решения задачи с заданной точностью е > 0 [15].

Прямые методы

         Метод Гаусса. Имеется несколько вычислительных вариантов метода Гаусса, основанного на идее последо­вательного исключения. Процесс решения системы ли­нейных алгебраических уравнений Ax
=
f(1) по методу Гаусса состоит из двух этапов.

Первый этап (прямой ход). Система (1) приво­дится к треугольному виду

х + В*х = φ,                      (2)

где x
=(
x
1
, ..., xN-)— неизвестный,  φ= (φ1,…,φN) —известный векторы, В* — верхняя треугольная матрица.

Второй этап (обратный ход). Неизвестные хN
,
xN
-1, ..., x
1
определяются по формулам (2) .

Метод квадратного корня. Этот метод пригоден для систем

Au
=
f
                          (3)

с эрмитовой (в действительном случае — симметричной) матрицей А. Матрица А разлагается в произведение

А -= S
*
DS
,                     (4)

где S— верхняя треугольная, D
— диагональная матрица. Решение уравнения Аu=fсводится к последователь­ному решению двух систем

S
*
Dy
=
f
,  
Su
=
y
.               (5)

Метод квадратного корня требует порядка N2/3 арифметических действий, т. е. при больших N он вдвое быстрее метода Гаусса и занимает вдвое меньше ячеек памяти. Это обстоятельство объясняется тем, что метод использует информацию о симметрии матрицы.

Итерационные методы

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

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

Au=f                              (6)

Для ее решения выбирается некоторое начальное приближение у0Hи последовательно находятся приближенные решения (итерации) уравнения (1). Значение итерации yh
+1
выражается через известные предыдущие итерации yk,
yk
-1
,… Если при вычислении yh
+1
используется толь­ко одна предыдущая итерация yh
, то итерационный метод называют одношаговым (или двухслойным) методом; если же yk
+1
выражается через две итерации yk
и yk
-1, то метод называется двухшаговым (или трехслойным). Мы будем рассматривать в основном одношаговые методы. Будем считать, что А: H
->
H
— линейный оператор в конеч­номерном пространстве H
со скалярным произведе­нием (•, •).

Важную роль играет запись итерационных методов в единой (канонической) форме. Любой двухслойный ите­рационный метод можно записать в следующей канони­ческой форме:

(7), где А: Н -> Н — оператор исходного уравнения (1), В: Н -> Н — линейный оператор, имеющий обратный В-1, k
— номер итерации, τ1 τ2, ..., τk+1, ...— итерационные параметры, τk+1> 0. Оператор В может, вообще говоря, зависеть от номера k
— для Для простоты изложения мы пред­полагаем всюду, что В не зависит от k
.

Если В = Е — единичный оператор, то метод(8) называют явным: yh
+1
находится по явной формуле


В общем случае, при В≠ Е, метод (7) называют не­явным итерационным методом: для определения yh
+1
надо решить уравнение:

(9)

Естественно требовать, чтобы объем вычислений для ре­шения.системы Byk+1= Fk
был меньше, чем объем вы­числений для прямого решения системы Au=f

Точность итерационного метода (7) характеризуется величиной погрешности zh
= ук — и, т. е. разностью между решением уравнения (7) и точным решением и исход­ной системы линейных алгебраических уравнений. Под­становка yk
=
zk
+
u
в (2) приводит к однородному урав­нению для погрешности:



    продолжение
--PAGE_BREAK--§2 ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

2.1 Общие сведения


К численным методам линейной алгебры относятся численные методы решения систем линейных алгебраических уравнений. Методы решения СЛАУ разбиваются на две группы. К первой группе принадлежат так называемые точные или прямые методы — алгоритм, позволяющий получить решение системы за конечное число арифметических действий. Вторую группу составляют приближенные методы, в частности итерационные методы решения СЛАУ.


2.2.1 Описание метода
Рассмотрим СЛАУ вида

Ax= B, где А — матрица. (1)
A= {aij}i, j= 1…n

B= {bi}x= {xi}
Если эту систему удалось привести к виду x= Cx+ D, то можно построить итерационную процедуру
xk= Cxk-1+ D
xk→ x*, где х* — решение заданной системы.

В конечном варианте система будет имееть вид:
x1=c11x1+c12x2+c13x3+…c1nxn+d1

x2=c21x1+c22x2+c23x3+…c2nxn+d1

x3=c31x1+c32x2+c33x3+…c1nxn+d3

…………………………………………. .

xn=cn1x1+cn2x2+cn3x3+…cnnxn+dn
Условием сходимости для матрицы С выполняется, если сумма модулей коэффициентов меньше единицы по строкам или по столбцам, т.е.
, или .
Необходимо, чтобы диагональные элементы матрицы А были ненулевыми.

Для преобразования системы можно выполнить следующие операции:
x1=a11-1 (c1-a12x2 — a13x3-… — a1nxn)

x2=a22-1 (c2-a21x2 — a23x3-… — a2nxn)

………………………. .

xn=ann-1 (cn-an1x2 — an3x3-… — an-1nxn-1)

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

x1=0+ c12x2+ c13x3-…+ c1n-1xn-1+ c1nxn+d1

x2= c21x2+0 +c23x3+…+ c2n-1xn-1+ c2nxn+d2

………………………………………………………. .

xn= cn1x1+ cn2x2 +cn3x3+…+ cnn-1xn-1+ 0+dn
В ней на главной диагонали матрицы С находятся нулевые элементы, остальные элементы выражаются по формулам:
сij=-aij/aii, di=ci/aii (i,j=1,2,3…n, ij)
Итерационный процесс продолжается до тех пор, пока значения х1(k),х2(k),х3(k) не станут близкими с заданной погрешностью к значениям х1(k-1),х2(k-1),х3(k-1).


2.2.2 Решение СЛАУ методом простых итераций


Решить СЛАУ методом простых итераций с точностью .

Для удобства преобразуем систему к виду:

Условие сходимости:
,


Принимаем приближение на 0-ом шаге:
,

,
На 1-м шаге выполняем следующее:

Подставляем принятые приближения в первоначальную систему уравнений







Смотрим не выполняется ли условие остановки итерационного процесса:
:


На 2-м шаге выполняем следующее:







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







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







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







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







Смотрим не выполняется ли условие остановки итерационного процесса:
:
Необходимая точность достигнута на 6-й итерации. Таким образом, итерационный процесс можно прекратить [14].



    продолжение
--PAGE_BREAK--